[[File:Relación binaria 01.svg|thumb|300px|Illustration of an example relation on a set A = . An arrow from x to y indicates that the relation holds between x and y. The relation is represented by the set {{math|{ (a,a),}} (a,b), (a,d), (b,a), (b,d), (c,b), (d,c), {{math|(d,d) } }} of ordered pairs.]] In , a denotes some kind of ship between two in a , which may or may not hold. As an example, "is less than" is a relation on the set of ; it holds, for instance, between the values 1 and 3 (denoted as 1 < 3 ), and likewise between 3 and 4 (denoted as 3 < 4 ), but not between the values 3 and 1 nor between 4 and 4 , that is, 3 < 1 and 4 < 4 both evaluate to false. As another example, "is sister of is a relation on the set of all people, it holds e.g. between and , 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 (x,y) of members of X. 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 Rless of pairs of natural numbers that contains both (1,3) and (3,4) , but neither (3,1) nor (4,4) . The relation "is a of on the set of one-digit natural numbers is sufficiently small to be shown here: Rdv = 2 is a nontrivial divisor of 8 , but not vice versa, hence (2,8) ∈ Rdv , but (8,2) ∉ Rdv . 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) ∈ Rless " mean all the same; some authors also write " (1,3) ∈ (<) ". 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), nor 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 reflexive, antisymmetric, and transitive, an equivalence relation is a relation that is reflexive, symmetric, and transitive, a function is a relation that is right-unique and left-total (see below). 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. The above concept of relation 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 (like "is an element of on the class of all sets, see '').

Definition

Given a set X , a relation R over X is a set of ordered pairs of elements from X , formally: R ⊆ . The statement (x,y) ∈ R reads " x is R -related to y " and is written in infix notation as xRy . 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 .

Representation of relations

A relation R on a finite set X may be represented as: X corresponds to a vertex; a directed edge from x to y exists if and only if (x,y) ∈ R . X are arranged in some fixed sequence x1 , ..., xn n × n , with the element in line i , column j , being Yes check.svg, if (xi,xj) ∈ R , and Dark Red x.svg, otherwise. R 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 relation R on a finite set X may be also represented as X corresponds to a vertex; 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 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 12 , define the relation Rdiv by x Rdiv y if x is a divisor of y and x ≠ y . Formally, X = and Rdiv = . The representation of Rdiv 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 Rdiv y is true. (x,y) ∈ Rdiv . x to y exists in the Hasse diagram representing Rdiv . x to y exists in the directed graph representing Rdiv . Rdiv , the element in line x , column y is "Yes check.svg". As another example, define the relation Rel on R by x Rel y if x2 + xy + y2 = 1 . The representation of Rel as a 2D-plot obtains an ellipse, see right picture. Since R is not finite, neither a directed graph, nor a finite Boolean matrix, nor a Hasse diagram can be used to depict Rel .

Properties of relations

Some important properties that a relation R over a set X may have are: x ∈ X , xRx . For example, ≥ is a reflexive relation but

is not. 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 = x2 given in the diagram below is neither irreflexive, nor reflexive, since it contains the pair (0,0) , but not (2,2) , respectively. 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. 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). x, y ∈ X , if xRy then not yRx . 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 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. x, y, z ∈ X , if xRy and yRz then xRz . 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. 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 ). x, y ∈ X , xRy or yRx . 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. Uniqueness properties: 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 ). x, y, z ∈ X , if xRy and xRz then y = z . 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 1 to both −1 and 1 ), nor is the black one (as it relates 0 to both −1 and 1). Totality properties: 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 . 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 . 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 ).

Combinations of properties

! ! ! ! ! ! ! Partial order ! Strict partial order ! Total order ! Strict total order ! Equivalence relation Relations that satisfy certain combinations of the above properties are particularly useful, and thus have received names by their own. Orderings: Uniqueness properties: Uniqueness and totality properties:

Operations on relations

R and S are relations over X then R ∪ S = is the 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

. R and S are relations over X then R ∩ S = is the 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". R and S are relations over X then S ∘ R = (also denoted by R; S ) is the 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 . 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 . R is a relation over sets X and Y then RT = 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 ≥ . R is a relation over X then R = (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 RT is the converse of the complement: R is a relation over X and S is a subset of X then Rundefined = is the of R to S . The expression Rundefined = is the of R to S Rundefined = is called the 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 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 than S , written R ⊊ S . For example, on the rational numbers, the relation

is smaller than ≥ , and equal to the composition

∘ > .

Theorems about relations

R is contained in relation S , then R is reflexive, connected, strongly connected, left-total, or right-total, then so is S . S is irreflexive, asymmetric, anti-symmetric, left-unique, or right-unique, then so is R .

Examples

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 . When X = Y , 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 x borders continent y ". The best-known examples are functions with distinct domains and ranges, such as sqrt : N → R+ .