Relation (mathematics)

Illustration of an example relation on a set Template:Math. An arrow from Template:Mvar to Template:Mvar indicates that the relation holds between Template:Mvar and Template:Mvar. The relation is represented by the set Template:Math Template:Math Template:Math Template:Math Template:Math Template:Math Template:Math Template:Math of ordered pairs.

In mathematics, a relation denotes some kind of relationship between two objects in a set, which may or may not hold. As an example, "is less than" is a relation on the set of natural numbers; it holds, for instance, between the values Template:Math and Template:Math (denoted as Template:Math), and likewise between Template:Math and Template:Math (denoted as Template:Math), but not between the values Template:Math and Template:Math nor between Template:Math and Template:Math, that is, Template:Math and Template:Math both evaluate to false. As another example, "is sister ofTemplate:-" 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 Template:Mvar over a set Template:Mvar can be seen as a set of ordered pairs Template:Math of members of Template:Mvar.Template:Sfn The relation Template:Mvar holds between Template:Mvar and Template:Mvar if Template:Math is a member of Template:Mvar. For example, the relation "is less than" on the natural numbers is an infinite set Template:Math of pairs of natural numbers that contains both Template:Math and Template:Math, but neither Template:Math nor Template:Math. The relation "is a nontrivial divisor ofTemplate:-" on the set of one-digit natural numbers is sufficiently small to be shown here: Template:Math; for example Template:Math is a nontrivial divisor of Template:Math, but not vice versa, hence Template:Math, but Template:Math.

If Template:Mvar is a relation that holds for Template:Mvar and Template:Mvar one often writes Template:Math. For most common relations in mathematics, special symbols are introduced, like "Template:Math" for "is less than", and "Template:Math" for "is a nontrivial divisor of", and, most popular "Template:Math" for "is equal to". For example, "Template:Math", "Template:Math is less than Template:Math", and "Template:Math" mean all the same; some authors also write "Template:Math".

Various properties of relations are investigated. A relation Template:Mvar is reflexive if Template:Math holds for all Template:Mvar, and irreflexive if Template:Math holds for no Template:Mvar. It is symmetric if Template:Math always implies Template:Math, and asymmetric if Template:Math implies that Template:Math is impossible. It is transitive if Template:Math and Template:Math always implies Template:Math. For example, "is less than" is irreflexive, asymmetric, and transitive, but neither reflexive nor symmetric. "is sister ofTemplate:-" 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 ofTemplate:-" is transitive, while "is parent ofTemplate:-" 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,Template:Sfn an equivalence relation is a relation that is reflexive, symmetric, and transitive,Template:Sfn a function is a relation that is right-unique and left-total (see below).Template:Sfn

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.Template:Sfn

The above concept of relationTemplate:Efn 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 Template:Math lives in town Template:Math at time Template:Math"), and relations between classesTemplate:Efn (like "is an element ofTemplate:-" on the class of all sets, see Template:Section link).

Definition

Given a set Template:Math, a relation Template:Math over Template:Math is a set of ordered pairs of elements from Template:Math, formally: Template:Math.Template:SfnTemplate:Sfn

The statement Template:Math reads "Template:Math is Template:Math-related to Template:Math" and is written in infix notation as Template:Math. The order of the elements is important; if Template:Math then Template:Math can be true or false independently of Template:Math. For example, Template:Math divides Template:Math, but Template:Math does not divide Template:Math.

Representation of relations

The representation of the relation Template:Math Template:Math Template:Math as a 2D-plot yields an ellipse.

Template:Diagonal split header	1	2	3	4	6	12
1	Template:Ya	Template:Ya	Template:Ya	Template:Ya	Template:Ya	Template:Ya
2	Template:Na	Template:Ya	Template:Na	Template:Ya	Template:Ya	Template:Ya
3	Template:Na	Template:Na	Template:Ya	Template:Na	Template:Ya	Template:Ya
4	Template:Na	Template:Na	Template:Na	Template:Ya	Template:Na	Template:Ya
6	Template:Na	Template:Na	Template:Na	Template:Na	Template:Ya	Template:Ya
12	Template:Na	Template:Na	Template:Na	Template:Na	Template:Na	Template:Ya
Representation of Template:Math as a Boolean matrix

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

A relation Template:Math on a finite set Template:Math may be represented as:

• Directed graph: Each member of Template:Math corresponds to a vertex; a directed edge from Template:Math to Template:Math exists if and only if Template:Math.
• Boolean matrix: The members of Template:Math are arranged in some fixed sequence Template:Math, ..., Template:Math; the matrix has dimensions Template:Math, with the element in line Template:Math, column Template:Math, being Template:Text, if Template:Math, and Template:Text, otherwise.
• 2D-plot: As a generalization of a Boolean matrix, a relation on the –infinite– set Template:Math of real numbers can be represented as a two-dimensional geometric figure: using Cartesian coordinates, draw a point at Template:Math whenever Template:Math.

A transitiveTemplate:Efn relation Template:Math on a finite set Template:Math may be also represented as

• Hasse diagram: Each member of Template:Math corresponds to a vertex; directed edges are drawn such that a directed path from Template:Math to Template:Math exists if and only if Template:Math. 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 Template:Math to Template:Math" 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 Template:Math, define the relation Template:Math by

Template:Math if Template:Math is a divisor of Template:Math and Template:Math.

Formally, Template:Math and Template:Math. The representation of Template:Math 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:

• Template:Math is true.
• Template:Math.
• A path from Template:Math to Template:Math exists in the Hasse diagram representing Template:Math.
• An edge from Template:Math to Template:Math exists in the directed graph representing Template:Math.
• In the Boolean matrix representing Template:Math, the element in line Template:Math, column Template:Math is "Template:Text".

As another example, define the relation Template:Math on Template:Math by

Template:Math if Template:Math.

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

Properties of relations

Some important properties that a relation Template:Mvar over a set Template:Mvar may have are:

Template:Em

for all Template:Math, Template:Math. For example, Template:Math is a reflexive relation but Template:Math is not.

Template:Em (or Template:Em)

for all Template:Math, not Template:Math. For example, Template:Math is an irreflexive relation, but Template:Math is not.

The previous 2 alternatives are not exhaustive; e.g., the red relation Template:Math given in the diagram below is neither irreflexive, nor reflexive, since it contains the pair Template:Math, but not Template:Math, respectively.

Template:Em

for all Template:Math, if Template:Math then Template:Math. For example, "is a blood relative of" is a symmetric relation, because Template:Mvar is a blood relative of Template:Mvar if and only if Template:Mvar is a blood relative of Template:Mvar.

Template:Em

for all Template:Math, if Template:Math and Template:Math then Template:Math. For example, Template:Math is an antisymmetric relation; so is Template:Math, but vacuously (the condition in the definition is always false).Template:Sfn

Template:Em

for all Template:Math, if Template:Math then not Template:Math. A relation is asymmetric if and only if it is both antisymmetric and irreflexive.Template:Sfn For example, Template:Math is an asymmetric relation, but Template:Math is not.

Again, the previous 3 alternatives are far from being exhaustive; as an example over the natural numbers, the relation Template:Math defined by Template:Math is neither symmetric (e.g. Template:Math, but not Template:Math) nor antisymmetric (e.g. Template:Math, but also Template:Math), let alone asymmetric.

Template:Em

for all Template:Math, if Template:Math and Template:Math then Template:Math. A transitive relation is irreflexive if and only if it is asymmetric.Template:Sfn For example, "is ancestor of" is a transitive relation, while "is parent of" is not.

Template:Em

for all Template:Math, if Template:Math then Template:Math or Template:Math. For example, on the natural numbers, Template:Math is connected, while "is a divisor ofTemplate:-" is not (e.g. neither Template:Math nor Template:Math).

Template:Em

for all Template:Math, Template:Math or Template:Math. For example, on the natural numbers, Template:Math is strongly connected, but Template:Math is not. A relation is strongly connected if, and only if, it is connected and reflexive.

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:

InjectiveTemplate:Efn (also called left-unique)

For all Template:Math, if Template:Math and Template:Math then Template:Math. For example, the green and blue relations in the diagram are injective, but the red one is not (as it relates both Template:Math and Template:Math to Template:Math), nor is the black one (as it relates both Template:Math and Template:Math to Template:Math).

FunctionalTemplate:Efn (also called right-unique, right-definiteTemplate:Sfn or univalentTemplate:Sfn)

For all Template:Math, if Template:Math and Template:Math then Template:Math. Such a relation is called a Template:Em. For example, the red and green relations in the diagram are functional, but the blue one is not (as it relates Template:Math to both Template:Math and Template:Math), nor is the black one (as it relates 0 to both −1 and 1).

Totality properties:

Template:EmTemplate:Efn (also called Template:Em or Template:Em)

For all Template:Math, there exists some Template:Math such that Template:Math. 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 Template:Math to any real number), nor is the black one (as it does not relate Template:Math to any real number). As another example, Template:Math is a serial relation over the integers. But it is not a serial relation over the positive integers, because there is no Template:Mvar in the positive integers such that Template:Math.Template:Sfn However, Template:Math is a serial relation over the positive integers, the rational numbers and the real numbers. Every reflexive relation is serial: for a given Template:Mvar, choose Template:Math.

SurjectiveTemplate:Efn (also called right-total or onto)

For all Template:Math, there exists an Template:Math such that Template:Math. 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 Template:Math), nor is the black one (as it does not relate any real number to Template:Math).

Combinations of properties

Relations that satisfy certain combinations of the above properties are particularly useful, and thus have received names by their own.

Template:Em

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:

Template:Em

A relation that is reflexive, antisymmetric, and transitive.

Template:Em

A relation that is irreflexive, asymmetric, and transitive.

Template:Em

A relation that is reflexive, antisymmetric, transitive and connected.Template:Sfn

Template:Em

A relation that is irreflexive, asymmetric, transitive and connected.

Uniqueness properties:

One-to-oneTemplate:Efn

Injective and functional. For example, the green relation in the diagram is one-to-one, but the red, blue and black ones are not.

One-to-manyTemplate:Efn

Injective and not functional. For example, the blue relation in the diagram is one-to-many, but the red, green and black ones are not.

Many-to-oneTemplate:Efn

Functional and not injective. For example, the red relation in the diagram is many-to-one, but the green, blue and black ones are not.

Many-to-manyTemplate:Efn

Not injective nor functional. For example, the black relation in the diagram is many-to-many, but the red, green and blue ones are not.

Uniqueness and totality properties:

A Template:EmTemplate:Efn

A relation that is functional and total. For example, the red and green relations in the diagram are functions, but the blue and black ones are not.

An Template:EmTemplate:Efn

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 Template:EmTemplate:Efn

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 Template:EmTemplate:Efn

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

Template:EmTemplate:Efn

If Template:Math and Template:Math are relations over Template:Math then Template:Math is the Template:Em of Template:Math and Template:Math. The identity element of this operation is the empty relation. For example, Template:Math is the union of Template:Math and Template:Math, and Template:Math is the union of Template:Math and Template:Math.

Template:EmTemplate:Efn

If Template:Math and Template:Math are relations over Template:Math then Template:Math is the Template:Em of Template:Math and Template:Math. 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".

Template:EmTemplate:Efn

If Template:Math and Template:Math are relations over Template:Math then Template:Math (also denoted by Template:Math) is the relative product of Template:Math and Template:Math. The identity element is the identity relation. The order of Template:Math and Template:Math in the notation Template:Math, used here agrees with the standard notational order for composition of functions. For example, the composition "is mother of" Template:Math "is parent of" yields "is maternal grandparent of", while the composition "is parent of" Template:Math "is mother of" yields "is grandmother of". For the former case, if Template:Math is the parent of Template:Math and Template:Math is the mother of Template:Math, then Template:Math is the maternal grandparent of Template:Math.

Template:EmTemplate:Efn

If Template:Math is a relation over sets Template:Math and Template:Math then Template:Math is the converse relation of Template:Math over Template:Math and Template:Math. For example, Template:Math is the converse of itself, as is Template:Math, and Template:Math and Template:Math are each other's converse, as are Template:Math and Template:Math.

Template:EmTemplate:Efn

If Template:Math is a relation over Template:Math then Template:Math (also denoted by Template:Math or Template:Math) is the complementary relation of Template:Math. For example, Template:Math and Template:Math are each other's complement, as are Template:Math and Template:Math, Template:Math and Template:Math, and Template:Math and Template:Math, and, for total orders, also Template:Math and Template:Math, and Template:Math and Template:Math. The complement of the converse relation Template:Math is the converse of the complement: $\overline{R^{𝖳}}={\overline{R}}^{𝖳}.$

Template:EmTemplate:Efn

If Template:Math is a relation over Template:Math and Template:Math is a subset of Template:Math then Template:Math is the Template:Em of Template:Math to Template:Math. The expression Template:Math is the Template:Em of Template:Math to Template:Math; the expression Template:Math is called the Template:Em of Template:Math to Template:Math. 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 "Template:Math is parent of Template:Math" to females yields the relation "Template:Math is mother of the woman Template:Math"; 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 Template:Math over sets Template:Math and Template:Math is said to be Template:Em a relation Template:Math over Template:Math and Template:Math, written Template:Math, if Template:Math is a subset of Template:Math, that is, for all Template:Math and Template:Math, if Template:Math, then Template:Math. If Template:Math is contained in Template:Math and Template:Math is contained in Template:Math, then Template:Math and Template:Math are called equal written Template:Math. If Template:Math is contained in Template:Math but Template:Math is not contained in Template:Math, then Template:Math is said to be Template:Em than Template:Math, written Template:Math. For example, on the rational numbers, the relation Template:Math is smaller than Template:Math, and equal to the composition Template:Math.

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 anti-symmetric.
• A relation is strongly connected if, and only if, its complement is asymmetric.Template:Sfn
• If Template:Math and Template:Math are relations over a set Template:Math, and Template:Math is contained in Template:Math, then
  • If Template:Math is reflexive, connected, strongly connected, left-total, or right-total, then so is Template:Math.
  • If Template:Math is irreflexive, asymmetric, anti-symmetric, left-unique, or right-unique, then so is Template:Math.
• A relation is reflexive, irreflexive, symmetric, asymmetric, anti-symmetric, 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 Template:Math and Template:Math, a heterogeneous relation Template:Math over Template:Math and Template:Math is a subset of Template:Math.Template:Sfn When Template:Math, the relation concept described above is obtained; it is often called homogeneous relation (or endorelation)Template:SfnTemplate:Sfn to distinguish it from its generalization. The above properties and operations that are marked "Template:Efn" and "Template:Efn", respectively, generalize to heterogeneous relations. An example of a heterogeneous relation is "ocean Template:Math borders continent Template:Math". The best-known examples are functionsTemplate:Efn with distinct domains and ranges, such as Template:Math.

See also

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

Bibliography

• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Citation
• Template:Cite book
• Template:Citation
• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Citation
• Template:Cite book
• Template:Cite book
• Template:Citation
• Template:Cite book
• Template:Cite journal