Illustration of an example relation on a set

A = { a, b, c, d }

. An arrow from

x

to

y

indicates that the relation holds between

x

and

y

. The relation is represented by the set

{ (a,a), (a,b), (a,d),

(b,a), (b,d),

(c,b), (d,c), (d,d) }

of ordered pairs.

In mathematics, a relation on a set may, or may not, hold between two given set members. For example, "is less than" is a relation on the set of natural numbers; it holds e.g. between 1 and 3 (denoted as 1<3) , and likewise between 3 and 4 (denoted as 3<4), but neither between 3 and 1 nor between 4 and 4. 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 one-digit natural numbers is sufficiently small to be shown here: $R div = { (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) \in R div$ , but $(8,2) \notin R div$ .

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) \in R less$ " mean all the same; some authors also write " $(1,3) \in (<)$ ".

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), 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 irreflexive, asymmetric, and transitive, an equivalence relation is a relation that is reflexive, symmetric, and transitive,^{[citation needed]} a function is a relation that is right-unique and left-total (see below).^[2]

Since relations are sets, they can be manipulated using set operations, including union, intersection, and complementation, and satisfying the laws of an algebra of sets. Beyond that, operations like the converse of a relation and the composition of relations are available, satisfying the laws of a calculus of relations.^[3]^[4]^[5]

The above concept of relation^{[note 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^{[note 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 \subseteq {(x,y): x,y \in X}$ .^[1]^[6]

The statement $(x, y) \in R$ reads "x is R-related to y" and is written in infix notation as xRy.^[3]^[4] The order of the elements is important; if $x \neq 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

Representation as Hasse diagram (black lines) and directed graph (all lines)

Representation as boolean matrix
y x	1	2	3	4	6	12
1
2
3
4
6
12

This section needs expansion. You can help by adding to it. (December 2022)

A relation on a finite set may be represented as:

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) }. The representation of R_div as a boolean matrix is shown in the left table; the representation both as a Hasse diagram and as a directed graph is shown in the right 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.
A vertice from x to y exists in the directed graph representing R_div.
In the boolean maxtrix representing R_div, the element in line x, column y is "

".

Properties of relations

Some important properties that a relation $R$ over a set $X$ may have are:

Reflexive: for all $x \in X$ , $xRx$ . For example, ≥ is a reflexive relation but > is not.

Irreflexive (or strict): for all $x \in X$ , not $xRx$ . For example, > is an irreflexive relation, but ≥ is not.

The previous 2 alternatives are not exhaustive; e.g., the red binary relation $y = x 2$ given in the section § Special types of binary relations is neither irreflexive, nor reflexive, since it contains the pair $(0, 0)$ , but not $(2, 2)$ , respectively.

Symmetric: for all $x, y \in 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 \in 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).^[7]

Asymmetric: for all $x, y \in X$ , if $xRy$ then not $yRx$ . A relation is asymmetric if and only if it is both antisymmetric and irreflexive.^[8] 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 nor antisymmetric, let alone asymmetric.

Transitive: for all $x, y, z \in X$ , if $xRy$ and $yRz$ then $xRz$ . A transitive relation is irreflexive if and only if it is asymmetric.^[9] For example, "is ancestor of" is a transitive relation, while "is parent of" is not.

Connected: for all $x, y \in X$ , if $x \neq y$ then $xRy$ or $yRx$ . This property is sometimes called "total", which is distinct from the definitions of "total" given in the section Relation (mathematics) § Properties of (heterogeneous) relations.

Strongly connected: for all $x, y \in X$ , $xRy$ or $yRx$ . This property is sometimes called "total", which is distinct from the definitions of "total" given in the section Relation (mathematics) § Properties of (heterogeneous) relations.

Well-founded: every nonempty subset $S$ of $X$ contains a minimal element with respect to $R$ . Well-foundedness implies the descending chain condition (that is, no infinite chain ... $x n R ... Rx 3 Rx 2 Rx 1$ can exist). If the axiom of dependent choice is assumed, both conditions are equivalent.^[10]^[11]

Uniqueness properties:

Injective^{[note 3]} (also called left-unique)^[12]: For all $x, y, z \in X$ , if $xRy$ and $zRy$ then $x = z$ . For example, the green and blue binary 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).
Functional^{[note 3]} (also called right-unique,^[12] right-definite^[13] or univalent)^[5]: For all $x, y, z \in X$ , if $xRy$ and $xRz$ then $y = z$ . Such a binary relation is called a partial function. For example, the red and green binary 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^{[note 3]} (also called total or left-total): For all $x \in X$ , there exists some $y \in X$ such that $xRy$ . Such a relation is called a multivalued function. For example, the red and green binary 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$ .^[14] 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^{[note 3]} (also called right-total^[12] or onto): For all y in X, there exists an x in X such that xRy. For example, the green and blue binary 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
	Reflexivity	Symmetry	Transitivity	Connectedness	Example
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, antisymmetric, and transitive.

Total order: A relation that is reflexive, antisymmetric, transitive and connected.^[15]

Strict total order: A relation that is irreflexive, antisymmetric, transitive and connected.

Uniqueness properties:

Examples of four types of binary relations over the real numbers: one-to-one (in green), one-to-many (in blue), many-to-one (in red), many-to-many (in black).

One-to-one^{[note 3]}: Injective and functional. For example, the green binary relation in the diagram is one-to-one, but the red, blue and black ones are not.
One-to-many^{[note 3]}: Injective and not functional. For example, the blue binary relation in the diagram is one-to-many, but the red, green and black ones are not.
Many-to-one^{[note 3]}: Functional and not injective. For example, the red binary relation in the diagram is many-to-one, but the green, blue and black ones are not.
Many-to-many^{[note 3]}: Not injective nor functional. For example, the black binary relation in the diagram is many-to-many, but the red, green and blue ones are not.

Uniqueness and totality properties:

A function^{[note 3]}: A binary relation that is functional and total. For example, the red and green binary relations in the diagram are functions, but the blue and black ones are not.
An injection^{[note 3]}: A function that is injective. For example, the green binary relation in the diagram is an injection, but the red, blue and black ones are not.
A surjection^{[note 3]}: A function that is surjective. For example, the green binary relation in the diagram is a surjection, but the red, blue and black ones are not.
A bijection^{[note 3]}: A function that is injective and surjective. For example, the green binary relation in the diagram is a bijection, but the red, blue and black ones are not.

Operations on relations

Union^{[note 4]}: If R and S are relations over X then $R \cup 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^{[note 4]}: If R and S are binary relations over X then $R \cap 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, the relation "is divisible by 6" is the intersection of the relations "is divisible by 3" and "is divisible by 2".^[clarify]

Composition^{[note 4]}: If R and S are binary relations over X then $S \circ R = {(x, z) | there exists y \in 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 \circ 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^{[note 4]}: If R is a binary 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 ≥. A binary relation is equal to its converse if and only if it is symmetric.

Complement^{[note 4]}: If R is a binary relation over X then $R = {(x, y) | x, y \in X and not xRy}$ (also denoted by R or $\neg 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: ${\overline {R^{\mathsf {T))))={\bar {R))^{\mathsf {T)).$

Restriction^{[note 4]}: If R is a relation over X and S is a subset of X then $R | S = {(x, y) | xRy and x, y \in S}$ is the restriction relation of R to S. The expression $R | S = {(x, y) | xRy and x \in S}$ is the left-restriction relation of R to S; the expression $R | S = {(x, y) | xRy and y \in S}$ is called the right-restriction 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 doesn't 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 binary relation R over sets X and Y is said to be contained in a relation S over X and Y, written $R\subseteq S,$ if R is a subset of S, that is, for all $x\in X$ and $y\in 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 $> \circ >.$

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 \in X, y \in Y}$ .^[1]^[16] When $X = Y$ , the relation concept describe above is obtained; it is often called homogeneous relation (or endorelation)^[17]^[18] to distinguish it from its generalization. The above properties and operations that are marked "^{[note 3]}" and "^{[note 4]}", respectively, generalize to heterogeneous relations. An example of a heterogeneous relation is "ocean x borders continent y". The best-known examples are functions^{[note 5]} with distinct domains and ranges, such as $sqrt:\mathbb {N} \rightarrow \mathbb {R} _{+}.$

Notes

References

^ ^a ^b ^c 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 2020-04-29.
^ "Relation definition – Math Insight". mathinsight.org. Retrieved 2019-12-11.
^ ^a ^b Ernst Schröder (1895) Algebra und Logic der Relative, via Internet Archive
^ ^a ^b C. I. Lewis (1918) A Survey of Symbolic Logic , pages 269 to 279, via internet Archive
^ ^a ^b Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7, Chapt. 5
^ Enderton 1977, Ch 3. pg. 40
^ Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), A Transition to Advanced Mathematics (6th ed.), Brooks/Cole, p. 160, ISBN 0-534-39900-2
^ Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Springer-Verlag, p. 158.
^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I (PDF). Prague: School of Mathematics – Physics Charles University. p. 1. Archived from the original (PDF) on 2013-11-02. Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".
^ "Condition for Well-Foundedness". ProofWiki. Archived from the original on 20 February 2019. Retrieved 20 February 2019.
^ Fraisse, R. (15 December 2000). Theory of Relations, Volume 145 - 1st Edition (1st ed.). Elsevier. p. 46. ISBN 9780444505422. Retrieved 20 February 2019.
^ ^a ^b ^c
Kilp, Knauer and Mikhalev: p. 3. The same four definitions appear in the following:
- Peter J. Pahl; Rudolf Damrath (2001). Mathematical Foundations of Computational Engineering: A Handbook. Springer Science & Business Media. p. 506. ISBN 978-3-540-67995-0.
- Eike Best (1996). Semantics of Sequential and Parallel Programs. Prentice Hall. pp. 19–21. ISBN 978-0-13-460643-9.
- Robert-Christoph Riemann (1999). Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus. Herbert Utz Verlag. pp. 21–22. ISBN 978-3-89675-629-9.
^ Mäs, Stephan (2007), "Reasoning on Spatial Semantic Integrity Constraints", Spatial Information Theory: 8th International Conference, COSIT 2007, Melbourne, Australia, September 19–23, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4736, Springer, pp. 285–302, doi:10.1007/978-3-540-74788-8_18
^ Yao, Y.Y.; Wong, S.K.M. (1995). "Generalization of rough sets using relationships between attribute values" (PDF). Proceedings of the 2nd Annual Joint Conference on Information Sciences: 30–33..
^ Joseph G. Rosenstein, Linear orderings, Academic Press, 1982, ISBN 0-12-597680-1, p. 4
^ Enderton 1977, Ch 3. pg. 40
^ M. E. Müller (2012). Relational Knowledge Discovery. Cambridge University Press. p. 22. ISBN 978-0-521-19021-3.
^ Peter J. Pahl; Rudolf Damrath (2001). Mathematical Foundations of Computational Engineering: A Handbook. Springer Science & Business Media. p. 496. ISBN 978-3-540-67995-0.