It has been suggested that Draft:Correspondence (mathematics) be merged into this article. (Discuss) Proposed since January 2021. |
Binary relations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A "✓" indicates that the column property is required in the row definition. For example, the definition of an equivalence relation requires it to be symmetric. All definitions tacitly require transitivity and reflexivity. |
In mathematics (specifically set theory), a binary relation over sets X and Y is a subset of the Cartesian product X × Y; that is, it is a set of ordered pairs (x, y) consisting of elements x in X and y in Y.^{[1]} It encodes the common concept of relation: an element x is related to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation. A binary relation is the most studied special case n = 2 of an n-ary relation over sets X_{1}, ..., X_{n}, which is a subset of the Cartesian product X_{1} × ... × X_{n}.^{[1]}^{[2]}
An example of a binary relation is the "divides" relation over the set of prime numbers and the set of integers , in which each prime p is related to each integer z that is a multiple of p, but not to an integer that is not a multiple of p. In this relation, for instance, the prime number 2 is related to numbers such as -4, 0, 6, 10, but not to 1 or 9, just as the prime number 3 is related to 0, 6, and 9, but not to 4 or 13.
Binary relations are used in many branches of mathematics to model a wide variety of concepts. These include, among others:
A function may be defined as a special kind of binary relation.^{[3]} Binary relations are also heavily used in computer science.
A binary relation over sets X and Y is an element of the power set of X × Y. Since the latter set is ordered by inclusion (?), each relation has a place in the lattice of subsets of X × Y.
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, for which there are textbooks by Ernst Schröder,^{[4]}Clarence Lewis,^{[5]} and Gunther Schmidt.^{[6]} A deeper analysis of relations involves decomposing them into subsets called concepts, and placing them in a complete lattice.
In some systems of axiomatic set theory, relations are extended to classes, which are generalizations of sets. This extension is needed for, among other things, modeling the concepts of "is an element of" or "is a subset of" in set theory, without running into logical inconsistencies such as Russell's paradox.
The terms correspondence,^{[7]}dyadic relation and two-place relation are synonyms for binary relation, though some authors use the term "binary relation" for any subset of a Cartesian product X × Y without reference to X and Y, and reserve the term "correspondence" for a binary relation with reference to X and Y.
Given sets X and Y, the Cartesian product X × Y is defined as {(x, y) | x ? X and y ? Y}, and its elements are called ordered pairs.
A binary relation R over sets X and Y is a subset of X × Y.^{[1]}^{[8]} The set X is called the domain^{[1]} or set of departure of R, and the set Y the codomain or set of destination of R. In order to specify the choices of the sets X and Y, some authors define a binary relation or correspondence as an ordered triple (X, Y, G), where G is a subset of X × Y called the graph of the binary relation. The statement (x, y) ? R reads "x is R-related to y" and is denoted by xRy.^{[4]}^{[5]}^{[6]}^{[note 1]} The domain of definition or active domain^{[1]} of R is the set of all x such that xRy for at least one y. The codomain of definition, active codomain,^{[1]}image or range of R is the set of all y such that xRy for at least one x. The field of R is the union of its domain of definition and its codomain of definition.^{[10]}^{[11]}^{[12]}
When X = Y, a binary relation is called a homogeneous relation (or endorelation). To emphasize the fact that X and Y are allowed to be different, a binary relation is also called a heterogeneous relation.^{[13]}^{[14]}^{[15]}
In a binary relation, 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.
ball | car | doll | cup | |
---|---|---|---|---|
John | + | - | - | - |
Mary | - | - | + | - |
Venus | - | + | - | - |
ball | car | doll | cup | |
---|---|---|---|---|
John | + | - | - | - |
Mary | - | - | + | - |
Ian | - | - | - | - |
Venus | - | + | - | - |
The following example shows that the choice of codomain is important. Suppose there are four objects A = {ball, car, doll, cup} and four people B = {John, Mary, Ian, Venus}. A possible relation on A and B is the relation "is owned by", given by R = {(ball, John), (doll, Mary), (car, Venus)}. That is, John owns the ball, Mary owns the doll, and Venus owns the car. Nobody owns the cup and Ian owns nothing. As a set, R does not involve Ian, and therefore R could have been viewed as a subset of A × {John, Mary, Venus}, i.e. a relation over A and {John, Mary, Venus}.
Some important types of binary relations R over sets X and Y are listed below.
Uniqueness properties:
Totality properties (only definable if the domain X and codomain Y are specified):
Uniqueness and totality properties (only definable if the domain X and codomain Y are specified):
If R and S are binary relations over sets X and Y then R ? S = {(x, y) | xRy or xSy} is the union relation of R and S over X and Y.
The identity element is the empty relation. For example, = is the union of > and =.
If R and S are binary relations over sets X and Y then R ? S = {(x, y) | xRy and xSy} is the intersection relation of R and S over X and Y.
The identity element 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".
If R is a binary relation over sets X and Y, and S is a binary relation over sets Y and Z then S ? R = {(x, z) | there exists y ? Y such that xRy and ySz} (also denoted by R; S) is the composition relation of R and S over X and Z.
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".
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 =. A binary relation is equal to its converse if and only if it is symmetric.
If R is a binary relation over sets X and Y then R = {(x, y) | not xRy} (also denoted by R or ¬ R) is the complementary relation of R over X and Y.
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:
If X = Y, the complement has the following properties:
If R is a binary relation over a set X and S is a subset of X then R_{|S} = {(x, y) | xRy and x ? S and y ? S} is the restriction relation of R to S over X.
If R is a binary relation over sets X and Y and S is a subset of X then R_{|S} = {(x, y) | xRy and x ? S} is the left-restriction relation of R to S over X and Y.
If R is a binary relation over sets X and Y and S is a subset of Y then R^{|S} = {(x, y) | xRy and y ? S} is the right-restriction relation of R to S over X and Y.
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 are its restrictions too.
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.
Also, the various concepts of completeness (not to be confused with being "total") do not carry over to restrictions. For example, over the real numbers a property of the relation non-empty subset S of R with an upper bound in R has a least upper bound (also called supremum) in R. However, for the rational numbers this supremum is not necessarily rational, so the same property does not hold on the restriction of the relation
A binary 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 > ? >.
Binary relations over sets X and Y can be represented algebraically by logical matrices indexed by X and Y with entries in the Boolean semiring (addition corresponds to OR and multiplication to AND) where matrix addition corresponds to union of relations, matrix multiplication corresponds to composition of relations (of a relation over X and Y and a relation over Y and Z),^{[18]} the Hadamard product corresponds to intersection of relations, the zero matrix corresponds to the empty relation, and the matrix of ones corresponds to the universal relation. Homogeneous relations (when X = Y) form a matrix semiring (indeed, a matrix semialgebra over the Boolean semiring) where the identity matrix corresponds to the identity relation.^{[19]}
Certain mathematical "relations", such as "equal to", "subset of", and "member of", cannot be understood to be binary relations as defined above, because their domains and codomains cannot be taken to be sets in the usual systems of axiomatic set theory. For example, if we try to model the general concept of "equality" as a binary relation =, we must take the domain and codomain to be the "class of all sets", which is not a set in the usual set theory.
In most mathematical contexts, references to the relations of equality, membership and subset are harmless because they can be understood implicitly to be restricted to some set in the context. The usual work-around to this problem is to select a "large enough" set A, that contains all the objects of interest, and work with the restriction =_{A} instead of =. Similarly, the "subset of" relation ? needs to be restricted to have domain and codomain P(A) (the power set of a specific set A): the resulting set relation can be denoted by ?_{A}. Also, the "member of" relation needs to be restricted to have domain A and codomain P(A) to obtain a binary relation ?_{A} that is a set. Bertrand Russell has shown that assuming ? to be defined over all sets leads to a contradiction in naive set theory.
Another solution to this problem is to use a set theory with proper classes, such as NBG or Morse-Kelley set theory, and allow the domain and codomain (and so the graph) to be proper classes: in such a theory, equality, membership, and subset are binary relations without special comment. (A minor modification needs to be made to the concept of the ordered triple (X, Y, G), as normally a proper class cannot be a member of an ordered tuple; or of course one can identify the binary relation with its graph in this context.)^{[20]} With this definition one can for instance define a binary relation over every set and its power set.
A homogeneous relation (also called endorelation) over a set X is a binary relation over X and itself, i.e. it is a subset of the Cartesian product X × X.^{[15]}^{[21]}^{[22]} It is also simply called a binary relation over X. An example of a homogeneous relation is the relation of kinship, where the relation is over people.
A homogeneous relation R over a set X may be identified with a directed simple graph permitting loops, or if it is symmetric, with an undirected simple graph permitting loops, where X is the vertex set and R is the edge set (there is an edge from a vertex x to a vertex y if and only if xRy). It is called the adjacency relation of the graph.
The set of all homogeneous relations over a set X is the set 2^{X × X} which is a Boolean algebra augmented with the involution of mapping of a relation to its converse relation. Considering composition of relations as a binary operation on , it forms a semigroup with involution.
Some important particular homogeneous relations over a set X are:
For arbitrary elements x and y of X:
Some important properties that a homogeneous relation R over a set X may have are:
The previous 4 alternatives are far from being exhaustive; e.g., the red binary relation y = x^{2} given in the section Special types of binary relations is neither irreflexive, nor coreflexive, nor reflexive, since it contains the pair (0, 0), and (2, 4), but not (2, 2), respectively. The latter two facts also rule out quasi-reflexivity.
A binary relation is quasi-reflexive if and only if it is both left quasi-reflexive and right quasi-reflexive.
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.
Again, the previous 5 alternatives are not exhaustive. For example, the relation xRy if (y = 0 or y = x+1) satisfies none of these properties. On the other hand, the empty relation trivially satisfies all of them.
A preorder is a relation that is reflexive and transitive. A total preorder, also called connex preorder or weak order, is a relation that is reflexive, transitive, and connex.
A partial order, also called order,^{[]} is a relation that is reflexive, antisymmetric, and transitive. A strict partial order, also called strict order,^{[]} is a relation that is irreflexive, antisymmetric, and transitive. A total order, also called connex order, linear order, simple order, or chain, is a relation that is reflexive, antisymmetric, transitive and connex.^{[31]} A strict total order, also called strict semiconnex order, strict linear order, strict simple order, or strict chain, is a relation that is irreflexive, antisymmetric, transitive and semiconnex.
A partial equivalence relation is a relation that is symmetric and transitive. An equivalence relation is a relation that is reflexive, symmetric, and transitive. It is also a relation that is symmetric, transitive, and serial, since these properties imply reflexivity.
If R is a homogeneous relation over a set X then each of the following is a homogeneous relation over X:
All operations defined in the section Operations on binary relations also apply to homogeneous relations.
Reflexivity | Symmetry | Transitivity | Connexity | Symbol | Example | |
---|---|---|---|---|---|---|
Directed graph | -> | |||||
Undirected graph | Symmetric | |||||
Dependency | Reflexive | Symmetric | ||||
Tournament | Irreflexive | Antisymmetric | Pecking order | |||
Preorder | Reflexive | Yes | Preference | |||
Total preorder | Reflexive | Yes | Connex | |||
Partial order | Reflexive | Antisymmetric | Yes | Subset | ||
Strict partial order | Irreflexive | Antisymmetric | Yes | < | Strict subset | |
Total order | Reflexive | Antisymmetric | Yes | Connex | Alphabetical order | |
Strict total order | Irreflexive | Antisymmetric | Yes | Semiconnex | < | Strict alphabetical order |
Partial equivalence relation | Symmetric | Yes | ||||
Equivalence relation | Reflexive | Symmetric | Yes | ~, ? | Equality |
The number of distinct homogeneous relations over an n-element set is 2^{n2} (sequence in the OEIS):
Elements | Any | Transitive | Reflexive | Preorder | Partial order | Total preorder | Total order | Equivalence relation |
---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 355 | 219 | 75 | 24 | 15 | |||
n | 2^{n2} | 2^{n2-n} | ?n k=0 k! S(n, k) |
n! | ?n k=0 S(n, k) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Notes:
The homogeneous relations can be grouped into pairs (relation, complement), except that for n = 0 the relation is its own complement. The non-symmetric ones can be grouped into quadruples (relation, complement, inverse, inverse complement).