Relation (mathematics)

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 R-related 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.

The representation of the relation Rel = { (x,y)∈ℝ×ℝ: x2+xy+y2=1 } as 2D-plot yields an ellipse.

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

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

A relation R on a finite set X may be represented as:

• Directed graph: Each member of X corresponds to a vertice; 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₁,...,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.
• 2D-plot: As a generalization of a boolean matrix, a relation on the -infinite- set ℝ of real numbers can be represented as a two-dimensional geometric figure: using Cartesian coordinates, draw a point at (x,y) whenever (x,y) ∈ R.

A transitive[note 3] relation R on a finite set X may be also represented as

• Hasse diagram: Each member of X corresponds to a vertice; directed edges are drawn such that a directed path from x to y exists if, and only if, (x,y) ∈ R. Compared to a directed-graph 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 layouted 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 ℝ by

x R_el y if x²+xy+y²=1.

The representation of R_el as a 2D-plot obtains an ellipse, see right picture. Since ℝ is not finite, neither a directed graph, nor a finite boolean matrix, not a Hasse diagram can be used to depict R_el.

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² 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.

Examples of four types of 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). 2D-plot representation is used.

Uniqueness properties:

Injective[note 4] (also called left-unique)[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).

Functional[note 4] (also called right-unique,[13] right-definite[14] or univalent)[8]

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[note 4] (also called total or left-total)

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[note 4] (also called right-total[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).

Union[note 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[note 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[note 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[note 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[note 5]

If R is a relation over X then R = {(x, y) | x, y ∈ X and not xRy} (also denoted by R or ¬ 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: ${\displaystyle {\overline {R^{\mathsf {T}}}}={\bar {R}}^{\mathsf {T}}.}$

Restriction[note 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 left-restriction relation of R to S; the expression R^|S = {(x, y) | xRy and y ∈ 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 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 ${\displaystyle R\subseteq S,}$ if R is a subset of S, that is, for all ${\displaystyle x\in X}$ and ${\displaystyle 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 > ∘ >.

• 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 anti-symmetric.
• 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, left-total, or right-total, then so is S.
  • If S is irreflexive, asymmetric, anti-symmetric, left-unique, or right-unique, then so is R.
• A relation is reflexive, irreflexive, symmetric, asymmetric, anti-symmetric, connected, strongly connected, and transitive if its converse is, respectively.

• 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

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 "[note 4]" and "[note 5]", respectively, generalize to heterogeneous relations. An example of a heterogeneous relation is "ocean x borders continent y". The best-known examples are functions[note 6] with distinct domains and ranges, such as ${\displaystyle sqrt:\mathbb {N} \rightarrow \mathbb {R} _{+}.}$

• Incidence structure, a heterogeneous relation between set of points and lines
• Order theory, investigates properties of order relations

• Codd, Edgar Frank (1990). The Relational Model for Database Management: Version 2 (PDF). Boston: Addison-Wesley. ISBN 978-0201141924.
• Enderton, Herbert (1977). Elements of Set Theory. Boston: Academic Press. ISBN 978-0-12-238440-0.
• Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander (2000). Monoids, Acts and Categories: with Applications to Wreath Products and Graphs. Berlin: De Gruyter. ISBN 978-3-11-015248-7.
• 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. Bibcode:1873MAAAS...9..317P. doi:10.2307/25058006. hdl:2027/hvd.32044019561034. JSTOR 25058006. Retrieved 2020-05-05.
• Schmidt, Gunther (2010). Relational Mathematics. Cambridge: Cambridge University Press. ISBN 978-0-521-76268-7.