Relation (mathematics)

Given a set , a relation over is a set of ordered pairs of elements from , formally: . The statement reads " is -related to " and is written in infix notation as . The order of the elements is important; if then can be true or false independently of . For example, divides , but does not divide . == Representation of relations ==

A relation on a finite set may be represented as: • Directed graph: Each member of corresponds to a vertex; a directed edge from to exists if and only if . • Boolean matrix: The members of are arranged in some fixed sequence , ..., ; the matrix has dimensions , with the element in line , column , being , if , 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 whenever . A transitive relation on a finite set may be also represented as • Hasse diagram: Each member of corresponds to a vertex; directed edges are drawn such that a directed path from to exists if and only if . 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 to " 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 , define the relation by : if is a divisor of and . Formally, and . The representation of 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: • is true. • . • A path from to exists in the Hasse diagram representing . • An edge from to exists in the directed graph representing . • In the Boolean matrix representing , the element in line , column is "". As another example, define the relation on by : if . The representation of as a 2D-plot obtains an ellipse, see right picture. Since is not finite, neither a directed graph, nor a finite Boolean matrix, nor a Hasse diagram can be used to depict . == Properties of relations ==

Some important properties that a relation over a set may have are: ; : for all , . For example, is a reflexive relation but is not. ; (or ): for all , not . For example, is an irreflexive relation, but is not. The previous 2 alternatives are not exhaustive; e.g., the red relation given in the diagram below is neither irreflexive, nor reflexive, since it contains the pair , but not , respectively. ; : for all , if then . For example, "is a blood relative of" is a symmetric relation, because is a blood relative of if and only if is a blood relative of . ; : for all , if and then . For example, is an antisymmetric relation; so is , but vacuously (the condition in the definition is always false). ; : for all , if then not . A relation is asymmetric if and only if it is both antisymmetric and irreflexive. 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 defined by is neither symmetric (e.g. , but not ) nor antisymmetric (e.g. , but also ), let alone asymmetric. ; : for all , if and then . A transitive relation is irreflexive if and only if it is asymmetric. For example, "is ancestor of" is a transitive relation, while "is parent of" is not. ; : for all , if then or . For example, on the natural numbers, is connected, while "is a divisor of is not (e.g. neither nor ). ; : for all , or . 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. s: 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 (also called left-unique (also called right-unique, right-definite or univalent) : For all , if and then . Such a relation is called a . For example, the red and green relations in the diagram are functional, but the blue one is not (as it relates to both and ), nor is the black one (as it relates 0 to both −1 and 1). Totality properties ; (also called or ): For all , there exists some such that . For example, the red and green relations in the diagram are total, but the blue one is not (as it does not relate to any real number), nor is the black one (as it does not relate 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 in the positive integers such that . However, is a serial relation over the positive integers, the rational numbers and the real numbers. Every reflexive relation is serial: for a given , choose . ; Surjective (also called right-total or onto): For all , there exists an such that . 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 ), nor is the black one (as it does not relate any real number to ). Combinations of properties : Relations that satisfy certain combinations of the above properties are particularly useful, and thus have received names by their own. ; : 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 ; : A relation that is reflexive, antisymmetric, and transitive. ; : A relation that is irreflexive, asymmetric, and transitive. ; : A relation that is reflexive, antisymmetric, transitive and connected. ; : A relation that is irreflexive, asymmetric, transitive and connected. Uniqueness properties ; One-to-one: 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-many: 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-one: 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-many: 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 : 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 : 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 : 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 : 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 ==

; : If and are relations over then is the of and . The identity element of this operation is the empty relation. For example, is the union of and , and is the union of and . ; : If and are relations over then is the of and . 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". ; : If and are relations over then (also denoted by ) is the relative product of and . The identity element is the identity relation. The order of and in the notation , 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 is the parent of and is the mother of , then is the maternal grandparent of . ; : If is a relation over sets and then is the converse relation of over and . For example, is the converse of itself, as is , and and are each other's converse, as are and . ; : If is a relation over then (also denoted by or ) is the complementary relation of . 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 is the converse of the complement: \overline{R^\mathsf{T}} = \bar{R}^\mathsf{T}. ; : If is a relation over and is a subset of then is the of to . The expression is the of to ; the expression is called the of to . 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 " is parent of " to women yields the relation " is mother of the woman "; 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 women does relate a woman with her paternal grandmother. A relation over sets and is said to be a relation over and , written , if is a subset of , that is, for all and , if , then . If is contained in and is contained in , then and are called equal written . If is contained in but is not contained in , then is said to be than , written . 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 anti-symmetric. • A relation is strongly connected if, and only if, its complement is asymmetric. • If and are relations over a set , and is contained in , then • If is reflexive, connected, strongly connected, left-total, or right-total, then so is . • If is irreflexive, asymmetric, anti-symmetric, left-unique, or right-unique, then so is . • 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 and , a heterogeneous relation over and is a subset of . When , the relation concept described above is obtained; it is often called homogeneous relation (or endorelation) to distinguish it from its generalization. The above properties and operations that are marked "" and "", respectively, generalize to heterogeneous relations. An example of a heterogeneous relation is "ocean borders continent ". The best-known examples are functions with distinct domains and ranges, such as . == See also ==