In mathematics, a finitary relation over sets X_{1}, ..., X_{n} is a subset of the Cartesian product X_{1} × ⋯ × X_{n}; that is, it is a set of ntuples (x_{1}, ..., x_{n}) consisting of elements x_{i} in X_{i}.^{[1]}^{[2]}^{[3]} Typically, the relation describes a possible connection between the elements of an ntuple. For example, the relation "x is divisible by y and z" consists of the set of 3tuples such that when substituted to x, y and z, respectively, make the sentence true.
The nonnegative integer n giving the number of "places" in the relation is called the arity, adicity or degree of the relation. A relation with n "places" is variously called an nary relation, an nadic relation or a relation of degree n. Relations with a finite number of places are called finitary relations (or simply relations if the context is clear). It is also possible to generalize the concept to infinitary relations with infinite sequences.^{[4]}
An nary relation over sets X_{1}, ..., X_{n} is an element of the power set of X_{1} × ⋯ × X_{n}.
0ary relations count only two members: the one that always holds, and the one that never holds. This is because there is only one 0tuple, the empty tuple (). They are sometimes useful for constructing the base case of an induction argument.
Unary relations can be viewed as a collection of members (such as the collection of Nobel laureates) having some property (such as that of having been awarded the Nobel prize).
Binary relations are the most commonly studied form of finitary relations. When X_{1} = X_{2} it is called a homogeneous relation, for example:
 Equality and inequality, denoted by signs such as = and < in statements such as "5 < 12", or
 Divisibility, denoted by the sign  in statements such as "13143".
Otherwise it is a heterogeneous relation, for example:
 Set membership, denoted by the sign ∈ in statements such as "1 ∈ N".
YouTube Encyclopedic

1/5Views:564 042124 73222 203186 1161 421 071

RELATIONS  DISCRETE MATHEMATICS

What is a Relation?  Don't Memorise

Discrete Math  9.1.1 Introduction to Relations

Reflexive, Symmetric, and Transitive Relations on a Set

Relations and functions  Functions and their graphs  Algebra II  Khan Academy
Transcription
Example
Consider the ternary relation R "x thinks that y likes z" over the set of people P = {Alice, Bob, Charles, Denise}, defined by:
 R = {(Alice, Bob, Denise), (Charles, Alice, Bob), (Charles, Charles, Alice), (Denise, Denise, Denise)}.
R can be represented equivalently by the following table:
P  P  P 

Alice  Bob  Denise 
Charles  Alice  Bob 
Charles  Charles  Alice 
Denise  Denise  Denise 
Here, each row represents a triple of R, that is it makes a statement of the form "x thinks that y likes z". For instance, the first row states that "Alice thinks that Bob likes Denise". All rows are distinct. The ordering of rows is insignificant but the ordering of columns is significant.^{[1]}
The above table is also a simple example of a relational database, a field with theory rooted in relational algebra and applications in data management.^{[5]} Computer scientists, logicians, and mathematicians, however, tend to have different conceptions what a general relation is, and what it is consisted of. For example, databases are designed to deal with empirical data, which is by definition finite, whereas in mathematics, relations with infinite arity (i.e., infinitary relation) are also considered.
Definitions
When two objects, qualities, classes, or attributes, viewed together by the mind, are seen under some connexion, that connexion is called a relation.
— Augustus De Morgan^{[6]}
The first definition of relations encountered in mathematics is:
 Definition 1
 An nary relation R over sets X_{1}, ⋯, X_{n} is a subset of the Cartesian product X_{1} × ⋯ × X_{n}.^{[1]}
The second definition of relations makes use of an idiom that is common in mathematics, stipulating that "such and such is an ntuple" in order to ensure that such and such a mathematical object is determined by the specification of mathematical objects with n elements. In the case of a relation R over n sets, there are n + 1 things to specify, namely, the n sets plus a subset of their Cartesian product. In the idiom, this is expressed by saying that R is a (n + 1)tuple.
 Definition 2
 An nary relation R over sets X_{1}, ⋯, X_{n} is an (n + 1)tuple (X_{1}, ⋯, X_{n}, G) where G is a subset of the Cartesian product X_{1} × ⋯ × X_{n} called the graph of R.
As a rule, whatever definition best fits the application at hand will be chosen for that purpose, and if it ever becomes necessary to distinguish between the two definitions, then an entity satisfying the second definition may be called an embedded or included relation.
Both statements (x_{1}, ⋯, x_{n}) ∈ R (under the first definition) and (x_{1}, ⋯, x_{n}) ∈ G (under the second definition) read "x_{1}, ⋯, x_{n} are Rrelated" and are denoted using prefix notation by Rx_{1}⋯x_{n} and using postfix notation by x_{1}⋯x_{n}R. In the case where R is a binary relation, those statements are also denoted using infix notation by x_{1}Rx_{2}.
The following considerations apply under either definition:
 The set X_{i} is called the ith domain of R.^{[1]} Under the first definition, the relation does not uniquely determine a given sequence of domains. In the case where R is a binary relation, X_{1} is also called simply the domain or set of departure of R, and X_{2} is also called the codomain or set of destination of R.
 When the elements of X_{i} are relations, X_{i} is called a nonsimple domain of R.^{[1]}
 The set of ∀x_{i} ∈ X_{i} for which there exists (x_{1}, ⋯, x_{i − 1}, x_{i + 1}, ⋯, x_{n}) ∈ X_{1} × ⋯ × X_{i − 1} × X_{i + 1} × ⋯ × X_{n} such that Rx_{1}⋯x_{i − 1}x_{i}x_{i + 1}⋯x_{n} is called the ith domain of definition or active domain of R.^{[1]} In the case where R is a binary relation, its first domain of definition is also called simply the domain of definition or active domain of R, and its second domain of definition is also called the codomain of definition or active codomain of R.
 When the ith domain of definition of R is equal to X_{i}, R is said to be total on X_{i}. In the case where R is a binary relation, when R is total on X_{1}, it is also said to be lefttotal or serial, and when R is total on X_{2}, it is also said to be righttotal or surjective.
 When ∀x ∀y ∈ X_{i}. ∀z ∈ X_{j}. xR_{ij}z ∧ yR_{ij}z ⇒ x = y, where i ∈ I, j ∈ J, R_{ij} = π_{ij} R, and {I, J} is a partition of {1, ..., n}, R is said to be unique on {X_{i}}_{i ∈ I}, and {X_{i}}_{i ∈ J} is called a primary key^{[1]} of R. In the case where R is a binary relation, when R is unique on {X_{1}}, it is also said to be leftunique or injective, and when R is unique on {X_{2}}, it is also said to be rightunique or functional.
 When all X_{i} are the same set X, it is simpler to refer to R as an nary relation over X, called a homogeneous relation. Otherwise R is called a heterogeneous relation.
 When any of X_{i} is empty, the defining Cartesian product is empty, and the only relation over such a sequence of domains is the empty relation R = ∅. Hence it is commonly stipulated that all of the domains be nonempty.
Let a Boolean domain B be a twoelement set, say, B = {0, 1}, whose elements can be interpreted as logical values, typically 0 = false and 1 = true. The characteristic function of R, denoted by χ_{R}, is the Booleanvalued function χ_{R}: X_{1} × ⋯ × X_{n} → B, defined by χ_{R}((x_{1}, ⋯, x_{n})) = 1 if Rx_{1}⋯x_{n} and χ_{R}((x_{1}, ⋯, x_{n})) = 0 otherwise.
In applied mathematics, computer science and statistics, it is common to refer to a Booleanvalued function as an nary predicate. From the more abstract viewpoint of formal logic and model theory, the relation R constitutes a logical model or a relational structure, that serves as one of many possible interpretations of some nary predicate symbol.
Because relations arise in many scientific disciplines, as well as in many branches of mathematics and logic, there is considerable variation in terminology. Aside from the settheoretic extension of a relational concept or term, the term "relation" can also be used to refer to the corresponding logical entity, either the logical comprehension, which is the totality of intensions or abstract properties shared by all elements in the relation, or else the symbols denoting these elements and intensions. Further, some writers of the latter persuasion introduce terms with more concrete connotations (such as "relational structure" for the settheoretic extension of a given relational concept).
History
The logician Augustus De Morgan, in work published around 1860, was the first to articulate the notion of relation in anything like its present sense. He also stated the first formal results in the theory of relations (on De Morgan and relations, see Merrill 1990).
Charles Peirce, Gottlob Frege, Georg Cantor, Richard Dedekind and others advanced the theory of relations. Many of their ideas, especially on relations called orders, were summarized in The Principles of Mathematics (1903) where Bertrand Russell made free use of these results.
In 1970, Edgar Codd proposed a relational model for databases, thus anticipating the development of data base management systems.^{[1]}
See also
References
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} Codd, Edgar Frank (June 1970). "A Relational Model of Data for Large Shared Data Banks" (PDF). Communications of the ACM. 13 (6): 377–387. doi:10.1145/362384.362685. S2CID 207549016. Retrieved 20200429.
 ^ "Relation  Encyclopedia of Mathematics". www.encyclopediaofmath.org. Retrieved 20191212.
 ^ "Definition of nary Relation". cs.odu.edu. Retrieved 20191212.
 ^ Nivat, Maurice (1981). Astesiano, Egidio; Böhm, Corrado (eds.). "Infinitary relations". Caap '81. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 112: 46–75. doi:10.1007/3540108289_54. ISBN 9783540387169.
 ^ "Relations — CS441" (PDF). www.pitt.edu. Retrieved 20191211.
 ^ De Morgan, A. (1858) "On the syllogism, part 3" in Heath, P., ed. (1966) On the syllogism and other logical writings. Routledge. P. 119,
Bibliography
 Codd, Edgar Frank (1990). The Relational Model for Database Management: Version 2 (PDF). Boston: AddisonWesley. ISBN 9780201141924.
 Bourbaki, N. (1994) Elements of the History of Mathematics, John Meldrum, trans. SpringerVerlag.
 Carnap, Rudolf (1958) Introduction to Symbolic Logic with Applications. Dover Publications.
 Halmos, P.R. (1960) Naive Set Theory. Princeton NJ: D. Van Nostrand Company.
 Lawvere, F.W., and R. Rosebrugh (2003) Sets for Mathematics, Cambridge Univ. Press.
 Lewis, C.I. (1918) A Survey of Symbolic Logic, Chapter 3: Applications of the Boole—Schröder Algebra, via Internet Archive
 Lucas, J. R. (1999) Conceptual Roots of Mathematics. Routledge.
 Maddux, R.D. (2006) Relation Algebras, vol. 150 in "Studies in Logic and the Foundations of Mathematics". Elsevier Science.
 Merrill, Dan D. (1990) Augustus De Morgan and the logic of relations. Kluwer.
 Peirce, C.S. (1870), "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic", Memoirs of the American Academy of Arts and Sciences 9, 317–78, 1870. Reprinted, Collected Papers CP 3.45–149, Chronological Edition CE 2, 359–429.
 Peirce, C.S. (1984) Writings of Charles S. Peirce: A Chronological Edition, Volume 2, 18671871. Peirce Edition Project, eds. Indiana University Press.
 Russell, Bertrand (1903/1938) The Principles of Mathematics, 2nd ed. Cambridge Univ. Press.
 Suppes, Patrick (1960/1972) Axiomatic Set Theory. Dover Publications.
 Tarski, A. (1956/1983) Logic, Semantics, Metamathematics, Papers from 1923 to 1938, J.H. Woodger, trans. 1st edition, Oxford University Press. 2nd edition, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.
 Ulam, S.M. and Bednarek, A.R. (1990), "On the Theory of Relational Structures and Schemata for Parallel Computation", pp. 477–508 in A.R. Bednarek and Françoise Ulam (eds.), Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators, University of California Press, Berkeley, CA.
 Ulam, S.M. (1990) Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators in A.R. Bednarek and Françoise Ulam, eds., University of California Press.
 Roland Fraïssé (2000) [1986] Theory of Relations, North Holland