Relation (mathematics)
In mathematics, a relation on a set may, or may not, hold between two given members of the set. As an example, "is less than" is a relation on the set of natural numbers; it holds, for instance, between the values 1 and 3 (denoted as 1 < 3), and likewise between 3 and 4 (denoted as 3 < 4), but not between the values 3 and 1 nor between 4 and 4, that is, 3 < 1 and 4 < 4 both evaluate to false. As another example, "is sister of" is a relation on the set of all people, it holds e.g. between Marie Curie and Bronisława Dłuska, and likewise vice versa. Set members may not be in relation "to a certain degree" – either they are in relation or they are not.
Formally, a relation R over a set X can be seen as a set of ordered pairs (x,y) of members of X.^{[1]} The relation R holds between x and y if (x,y) is a member of R. For example, the relation "is less than" on the natural numbers is an infinite set R_{less} of pairs of natural numbers that contains both (1,3) and (3,4), but neither (3,1) nor (4,4). The relation "is a nontrivial divisor of" on the set of onedigit natural numbers is sufficiently small to be shown here: R_{dv} = { (2,4), (2,6), (2,8), (3,6), (3,9), (4,8) }; for example 2 is a nontrivial divisor of 8, but not vice versa, hence (2,8) ∈ R_{dv}, but (8,2) ∉ R_{dv}.
If R is a relation that holds for x and y one often writes xRy. For most common relations in mathematics, special symbols are introduced, like "<" for "is less than", and "" for "is a nontrivial divisor of", and, most popular "=" for "is equal to". For example, "1 < 3", "1 is less than 3", and "(1,3) ∈ R_{less}" mean all the same; some authors also write "(1,3) ∈ (<)".
Various properties of relations are investigated. A relation R is reflexive if xRx holds for all x, and irreflexive if xRx holds for no x. It is symmetric if xRy always implies yRx, and asymmetric if xRy implies that yRx is impossible. It is transitive if xRy and yRz always implies xRz. For example, "is less than" is irreflexive, asymmetric, and transitive, but neither reflexive nor symmetric. "is sister of" is transitive, but neither reflexive (e.g. Pierre Curie is not a sister of himself), nor symmetric, nor asymmetric; while being irreflexive or not may be a matter of definition (is every woman a sister of herself?), "is ancestor of" is transitive, while "is parent of" is not. Mathematical theorems are known about combinations of relation properties, such as "a transitive relation is irreflexive if, and only if, it is asymmetric".
Of particular importance are relations that satisfy certain combinations of properties. A partial order is a relation that is reflexive, antisymmetric, and transitive,^{[2]} an equivalence relation is a relation that is reflexive, symmetric, and transitive,^{[3]} a function is a relation that is univalent and lefttotal (see below).^{[4]}^{[5]}
Since relations are sets, they can be manipulated using set operations, including union, intersection, and complementation, leading to the algebra of sets. Furthermore, the calculus of relations includes the operations of taking the converse and composing relations.^{[6]}^{[7]}^{[8]}
The above concept of relation^{[loweralpha 1]} has been generalized to admit relations between members of two different sets (heterogeneous relation, like "lies on" between the set of all points and that of all lines in geometry), relations between three or more sets (finitary relation, like "person x lives in town y at time z"), and relations between classes^{[loweralpha 2]} (like "is an element of" on the class of all sets, see Binary relation § Sets versus classes).
Definition
Given a set X, a relation R over X is a set of ordered pairs of elements from X, formally: R ⊆ { (x,y)  x, y ∈ X }.^{[1]}^{[9]}
The statement (x,y) ∈ R reads "x is Rrelated to y" and is written in infix notation as xRy.^{[6]}^{[7]} The order of the elements is important; if x ≠ y then yRx can be true or false independently of xRy. For example, 3 divides 9, but 9 does not divide 3.
Representation of relations
y x

1  2  3  4  6  12 

1  
2  
3  
4  
6  
12  
Representation of R_{div} as a Boolean matrix 
A relation R on a finite set X may be represented as:
 Directed graph: Each member of X corresponds to a vertex; a directed edge from x to y exists if and only if (x,y) ∈ R.
 Boolean matrix: The members of X are arranged in some fixed sequence x_{1}, ..., x_{n}; the matrix has dimensions n × n, with the element in line i, column j, being , if (x_{i},x_{j}) ∈ R, and , otherwise.
 2Dplot: As a generalization of a Boolean matrix, a relation on the –infinite– set R of real numbers can be represented as a twodimensional geometric figure: using Cartesian coordinates, draw a point at (x,y) whenever (x,y) ∈ R.
A transitive^{[loweralpha 3]} relation R on a finite set X may be also represented as
 Hasse diagram: Each member of X corresponds to a vertex; directed edges are drawn such that a directed path from x to y exists if and only if (x,y) ∈ R. Compared to a directedgraph representation, a Hasse diagram needs fewer edges, leading to a less tangled image. Since the relation "a directed path exists from x to y" is transitive, only transitive relations can be represented in Hasse diagrams. Usually the diagram is laid out such that all edges point in an upward direction, and the arrows are omitted.
For example, on the set of all divisors of 12, define the relation R_{div} by
 x R_{div} y if x is a divisor of y and x ≠ y.
Formally, X = { 1, 2, 3, 4, 6, 12 } and R_{div} = { (1,2), (1,3), (1,4), (1,6), (1,12), (2,4), (2,6), (2,12), (3,6), (3,12), (4,12), (6,12) }. The representation of R_{div} as a Boolean matrix is shown in the middle table; the representation both as a Hasse diagram and as a directed graph is shown in the left picture.
The following are equivalent:
 x R_{div} y is true.
 (x,y) ∈ R_{div}.
 A path from x to y exists in the Hasse diagram representing R_{div}.
 An edge from x to y exists in the directed graph representing R_{div}.
 In the Boolean matrix representing R_{div}, the element in line x, column y is "".
As another example, define the relation R_{el} on R by
 x R_{el} y if x^{2} + xy + y^{2} = 1.
The representation of R_{el} as a 2Dplot obtains an ellipse, see right picture. Since R is not finite, neither a directed graph, nor a finite Boolean matrix, not a Hasse diagram can be used to depict R_{el}.
Properties of relations
Some important properties that a relation R over a set X may have are:
 Reflexive
 for all x ∈ X, xRx. For example, ≥ is a reflexive relation but > is not.
 Irreflexive (or strict)
 for all x ∈ X, not xRx. For example, > is an irreflexive relation, but ≥ is not.
The previous 2 alternatives are not exhaustive; e.g., the red relation y = x^{2} given in the diagram below is neither irreflexive, nor reflexive, since it contains the pair (0,0), but not (2,2), respectively.
 Symmetric
 for all x, y ∈ X, if xRy then yRx. For example, "is a blood relative of" is a symmetric relation, because x is a blood relative of y if and only if y is a blood relative of x.
 Antisymmetric
 for all x, y ∈ X, if xRy and yRx then x = y. For example, ≥ is an antisymmetric relation; so is >, but vacuously (the condition in the definition is always false).^{[10]}
 Asymmetric
 for all x, y ∈ X, if xRy then not yRx. A relation is asymmetric if and only if it is both antisymmetric and irreflexive.^{[11]} For example, > is an asymmetric relation, but ≥ is not.
Again, the previous 3 alternatives are far from being exhaustive; as an example over the natural numbers, the relation xRy defined by x > 2 is neither symmetric (e.g. 5R1, but not 1R5) nor antisymmetric (e.g. 6R4, but also 4R6), let alone asymmetric.
 Transitive
 for all x, y, z ∈ X, if xRy and yRz then xRz. A transitive relation is irreflexive if and only if it is asymmetric.^{[12]} For example, "is ancestor of" is a transitive relation, while "is parent of" is not.
 Connected
 for all x, y ∈ X, if x ≠ y then xRy or yRx. For example, on the natural numbers, < is connected, while "is a divisor of" is not (e.g. neither 5R7 nor 7R5).
 Strongly connected
 for all x, y ∈ X, xRy or yRx. For example, on the natural numbers, ≤ is strongly connected, but < is not. A relation is strongly connected if, and only if, it is connected and reflexive.
Uniqueness properties:
 Injective^{[loweralpha 4]} (also called leftunique^{[13]})
 For all x, y, z ∈ X, if xRy and zRy then x = z. For example, the green and blue relations in the diagram are injective, but the red one is not (as it relates both −1 and 1 to 1), nor is the black one (as it relates both −1 and 1 to 0).
 Univalent^{[8]}^{[loweralpha 4]} (also called rightunique,^{[13]} rightdefinite^{[14]})
 For all x, y, z ∈ X, if xRy and xRz then y = z. Such a relation is called a partial function. For example, the red and green relations in the diagram are functional, but the blue one is not (as it relates 1 to both −1 and 1), nor is the black one (as it relates 0 to both −1 and 1).
Totality properties:
 Serial^{[loweralpha 4]} (also called total or lefttotal)
 For all x ∈ X, there exists some y ∈ X such that xRy. Such a relation is called a multivalued function. For example, the red and green relations in the diagram are total, but the blue one is not (as it does not relate −1 to any real number), nor is the black one (as it does not relate 2 to any real number). As another example, > is a serial relation over the integers. But it is not a serial relation over the positive integers, because there is no y in the positive integers such that 1 > y.^{[15]} However, < is a serial relation over the positive integers, the rational numbers and the real numbers. Every reflexive relation is serial: for a given x, choose y = x.
 Surjective^{[loweralpha 4]} (also called righttotal^{[13]} or onto)
 For all y ∈ Y, there exists an x ∈ X such that xRy. For example, the green and blue relations in the diagram are surjective, but the red one is not (as it does not relate any real number to −1), nor is the black one (as it does not relate any real number to 2).
Combinations of properties
Relations by property Script error: No such module "Vertical header". Script error: No such module "Vertical header". Script error: No such module "Vertical header". Script error: No such module "Vertical header". Script error: No such module "Vertical header". Partial order Refl Antisym Yes Subset Strict partial order Irrefl Asym Yes Strict subset Total order Refl Antisym Yes Yes Alphabetical order Strict total order Irrefl Asym Yes Yes Strict alphabetical order Equivalence relation Refl Sym Yes Equality
Relations that satisfy certain combinations of the above properties are particularly useful, and thus have received names by their own.
 Equivalence relation
 A relation that is reflexive, symmetric, and transitive. It is also a relation that is symmetric, transitive, and serial, since these properties imply reflexivity.
Orderings:
 Partial order
 A relation that is reflexive, antisymmetric, and transitive.
 Strict partial order
 A relation that is irreflexive, asymmetric, and transitive.
 Total order
 A relation that is reflexive, antisymmetric, transitive and connected.^{[16]}
 Strict total order
 A relation that is irreflexive, asymmetric, transitive and connected.
Uniqueness properties:
 Onetoone^{[loweralpha 4]}
 Injective and univalent. For example, the green relation in the diagram is onetoone, but the red, blue and black ones are not.
 Onetomany^{[loweralpha 4]}
 Injective and not univalent. For example, the blue relation in the diagram is onetomany, but the red, green and black ones are not.
 Manytoone^{[loweralpha 4]}
 Univalent and not injective. For example, the red relation in the diagram is manytoone, but the green, blue and black ones are not.
 Manytomany^{[loweralpha 4]}
 Not injective nor univalent. For example, the black relation in the diagram is manytomany, but the red, green and blue ones are not.
Uniqueness and totality properties:
 A function^{[loweralpha 4]}
 A relation that is univalent and total. For example, the red and green relations in the diagram are functions, but the blue and black ones are not.
 An injection^{[loweralpha 4]}
 A function that is injective. For example, the green relation in the diagram is an injection, but the red, blue and black ones are not.
 A surjection^{[loweralpha 4]}
 A function that is surjective. For example, the green relation in the diagram is a surjection, but the red, blue and black ones are not.
 A bijection^{[loweralpha 4]}
 A function that is injective and surjective. For example, the green relation in the diagram is a bijection, but the red, blue and black ones are not.
Operations on relations
 Union^{[loweralpha 5]}
 If R and S are relations over X then R ∪ S = { (x, y)  xRy or xSy } is the union relation of R and S. The identity element of this operation is the empty relation. For example, ≤ is the union of < and =, and ≥ is the union of > and =.
 Intersection^{[loweralpha 5]}
 If R and S are relations over X then R ∩ S = { (x, y)  xRy and xSy } is the intersection relation of R and S. The identity element of this operation is the universal relation. For example, "is a lower card of the same suit as" is the intersection of "is a lower card than" and "belongs to the same suit as".
 Composition^{[loweralpha 5]}
 If R and S are relations over X then S ∘ R = { (x, z)  there exists y ∈ X such that xRy and ySz } (also denoted by R; S) is the composition relation of R and S. The identity element is the identity relation. The order of R and S in the notation S ∘ R, used here agrees with the standard notational order for composition of functions. For example, the composition "is mother of" ∘ "is parent of" yields "is maternal grandparent of", while the composition "is parent of" ∘ "is mother of" yields "is grandmother of". For the former case, if x is the parent of y and y is the mother of z, then x is the maternal grandparent of z.
 Converse^{[loweralpha 5]}
 If R is a relation over sets X and Y then R^{T} = { (y, x)  xRy } is the converse relation of R over Y and X. For example, = is the converse of itself, as is ≠, and < and > are each other's converse, as are ≤ and ≥.
 Complement^{[loweralpha 5]}
 If R is a relation over X then R = { (x, y)  x, y ∈ X and not xRy } (also denoted by
Ror ¬R) is the complementary relation of R. For example, = and ≠ are each other's complement, as are ⊆ and ⊈, ⊇ and ⊉, and ∈ and ∉, and, for total orders, also < and ≥, and > and ≤. The complement of the converse relation R^{T} is the converse of the complement: [math]\displaystyle{ \overline{R^\mathsf{T}} = \bar{R}^\mathsf{T}. }[/math]
 Restriction^{[loweralpha 5]}
 If R is a relation over X and S is a subset of X then R_{S} = { (x, y)  xRy and x, y ∈ S } is the restriction relation of R to S. The expression R_{S} = { (x, y)  xRy and x ∈ S } is the leftrestriction relation of R to S; the expression R^{S} = { (x, y)  xRy and y ∈ S } is called the rightrestriction relation of R to S. If a relation is reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive, total, trichotomous, a partial order, total order, strict weak order, total preorder (weak order), or an equivalence relation, then so too are its restrictions. However, the transitive closure of a restriction is a subset of the restriction of the transitive closure, i.e., in general not equal. For example, restricting the relation "x is parent of y" to females yields the relation "x is mother of the woman y"; its transitive closure does not relate a woman with her paternal grandmother. On the other hand, the transitive closure of "is parent of" is "is ancestor of"; its restriction to females does relate a woman with her paternal grandmother.
A relation R over sets X and Y is said to be contained in a relation S over X and Y, written R ⊆ S, if R is a subset of S, that is, for all x ∈ X and y ∈ Y, if xRy, then xSy. If R is contained in S and S is contained in R, then R and S are called equal written R = S. If R is contained in S but S is not contained in R, then R is said to be smaller than S, written R ⊊ S. For example, on the rational numbers, the relation > is smaller than ≥, and equal to the composition > ∘ >.
Theorems about relations
 A relation is asymmetric if, and only if, it is antisymmetric and irreflexive.
 A transitive relation is irreflexive if, and only if, it is asymmetric.
 A relation is reflexive if, and only if, its complement is irreflexive.
 A relation is strongly connected if, and only if, it is connected and reflexive.
 A relation is equal to its converse if, and only if, it is symmetric.
 A relation is connected if, and only if, its complement is antisymmetric.
 A relation is strongly connected if, and only if, its complement is asymmetric.^{[17]}
 If relation R is contained in relation S, then
 If R is reflexive, connected, strongly connected, lefttotal, or righttotal, then so is S.
 If S is irreflexive, asymmetric, antisymmetric, leftunique, or rightunique, then so is R.
 A relation is reflexive, irreflexive, symmetric, asymmetric, antisymmetric, connected, strongly connected, and transitive if its converse is, respectively.
Examples
 Order relations, including strict orders:
 Greater than
 Greater than or equal to
 Less than
 Less than or equal to
 Divides (evenly)
 Subset of
 Equivalence relations:
 Equality
 Parallel with (for affine spaces)
 Is in bijection with
 Isomorphic
 Tolerance relation, a reflexive and symmetric relation:
 Dependency relation, a finite tolerance relation
 Independency relation, the complement of some dependency relation
 Kinship relations
Generalizations
The above concept of relation has been generalized to admit relations between members of two different sets. Given sets X and Y, a heterogeneous relation R over X and Y is a subset of { (x,y)  x∈X, y∈Y }.^{[1]}^{[18]} When X = Y, the relation concept described above is obtained; it is often called homogeneous relation (or endorelation)^{[19]}^{[20]} to distinguish it from its generalization. The above properties and operations that are marked "^{[loweralpha 4]}" and "^{[loweralpha 5]}", respectively, generalize to heterogeneous relations. An example of a heterogeneous relation is "ocean x borders continent y". The bestknown examples are functions^{[loweralpha 6]} with distinct domains and ranges, such as sqrt : N → R_{+}.
See also
 Incidence structure, a heterogeneous relation between set of points and lines
 Order theory, investigates properties of order relations
Notes
 ↑ called "homogeneous binary relation (on sets)" when delineation from its generalizations is important
 ↑ a generalization of sets
 ↑ see below
 ↑ ^{4.00} ^{4.01} ^{4.02} ^{4.03} ^{4.04} ^{4.05} ^{4.06} ^{4.07} ^{4.08} ^{4.09} ^{4.10} ^{4.11} ^{4.12} These properties also generalize to heterogeneous relations.
 ↑ ^{5.0} ^{5.1} ^{5.2} ^{5.3} ^{5.4} ^{5.5} ^{5.6} This operation also generalizes to heterogeneous relations.
 ↑ that is, rightunique and lefttotal heterogeneous relations
References
 ↑ ^{1.0} ^{1.1} ^{1.2} Codd 1970
 ↑ Halmos 1968, Ch 14
 ↑ Halmos 1968, Ch 7
 ↑ "Relation definition – Math Insight". https://mathinsight.org/definition/relation.
 ↑ Halmos 1968, Ch 8
 ↑ ^{6.0} ^{6.1} Ernst Schröder (1895) Algebra und Logic der Relative, via Internet Archive
 ↑ ^{7.0} ^{7.1} C. I. Lewis (1918) A Survey of Symbolic Logic, pp. 269–279, via internet Archive
 ↑ ^{8.0} ^{8.1} Schmidt 2010, Chapt. 5
 ↑ Enderton 1977, Ch 3. p. 40
 ↑ Smith, Eggen & St. Andre 2006, p. 160
 ↑ Nievergelt 2002, p. 158
 ↑ Flaška et al. 2007, p.1 Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".
 ↑ ^{13.0} ^{13.1} ^{13.2} Kilp, Knauer & Mikhalev 2000, p. 3. The same four definitions appear in the following: Pahl & Damrath 2001, p. 506, Best 1996, pp. 19–21, Riemann 1999, pp. 21–22
 ↑ Mäs 2007
 ↑ Yao & Wong 1995
 ↑ Rosenstein 1982, p. 4
 ↑ Schmidt & Ströhlein 1993
 ↑ Enderton 1977, Ch 3. p. 40
 ↑ Müller 2012, p. 22
 ↑ Pahl & Damrath 2001, p. 496
Bibliography
 Semantics of Sequential and Parallel Programs. Prentice Hall. 1996. ISBN 9780134606439.
 Codd, Edgar Frank (June 1970). "A Relational Model of Data for Large Shared Data Banks". Communications of the ACM 13 (6): 377–387. doi:10.1145/362384.362685. https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf. Retrieved 20200429.
 Codd, Edgar Frank (1990). The Relational Model for Database Management: Version 2. Boston: AddisonWesley. ISBN 9780201141924. https://codeblab.com/wpcontent/uploads/2009/12/rmdbcodd.pdf.
 Enderton, Herbert (1977). Elements of Set Theory. Boston: Academic Press. ISBN 9780122384400.
 Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I. Prague: School of Mathematics – Physics Charles University. http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf.
 Halmos, Paul R. (1968). Naive Set Theory. Princeton: Nostrand.
 Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander (2000). Monoids, Acts and Categories: with Applications to Wreath Products and Graphs. Berlin: De Gruyter. ISBN 9783110152487.
 Mäs, Stephan (2007), "Reasoning on Spatial Semantic Integrity Constraints", Spatial Information Theory: 8th International Conference, COSIT 2007, Melbourne, Australia, September 19–23, Proceedings, Lecture Notes in Computer Science, 4736, Springer, pp. 285–302, doi:10.1007/9783540747888_18
 Müller, M. E. (2012). Relational Knowledge Discovery. Cambridge University Press. ISBN 9780521190213.
 Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, SpringerVerlag
 Pahl, Peter J.; Damrath, Rudolf (2001). Mathematical Foundations of Computational Engineering: A Handbook. Springer Science & Business Media. ISBN 9783540679950.
 Peirce, Charles Sanders (1873). "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 (2): 317–178. doi:10.2307/25058006. Bibcode: 1873MAAAS...9..317P. https://archive.org/details/descriptionanot00peirgoog/mode/2up. Retrieved 20200505.
 Riemann, RobertChristoph (1999). Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus. Herbert Utz Verlag. ISBN 9783896756299.
 Rosenstein, Joseph G. (1982), Linear orderings, Academic Press, ISBN 0125976801
 Schmidt, Gunther (2010). Relational Mathematics. Cambridge: Cambridge University Press. ISBN 9780521762687. https://books.google.com/books?id=E4dREBTs5WsC.
 Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. 1993. ISBN 9783642779701. https://books.google.com/books?id=ZgarCAAAQBAJ.
 Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), A Transition to Advanced Mathematics (6th ed.), Brooks/Cole, ISBN 0534399002
 Yao, Y.Y.; Wong, S.K.M. (1995). "Generalization of rough sets using relationships between attribute values". Proceedings of the 2nd Annual Joint Conference on Information Sciences: 30–33. http://www2.cs.uregina.ca/~yyao/PAPERS/relation.pdf.
Original source: https://en.wikipedia.org/wiki/Relation (mathematics).
Read more 