Relation (mathematics)

In mathematics, a relation on a set may, or may not, hold between two given members of the set. As an example, "is less than" is a relation on the set of natural numbers; 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 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 R over a set X can be seen as a set of ordered pairs (x,y) of members of X.^[1] 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 R_less of pairs of natural numbers that contains both (1,3) and (3,4), but neither (3,1) nor (4,4). The relation "is a nontrivial divisor of" on the set of one-digit natural numbers is sufficiently small to be shown here: R_dv = { (2,4), (2,6), (2,8), (3,6), (3,9), (4,8) }; for example 2 is a nontrivial divisor of 8, but not vice versa, hence (2,8) ∈ R_dv, but (8,2) ∉ R_dv.

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) ∈ R_less" 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,^[2] an equivalence relation is a relation that is reflexive, symmetric, and transitive,^[3] a function is a relation that is univalent and left-total (see below).^[4][5]

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.^[6][7][8]

The above concept of relation^[a] 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^[b] (like "is an element of" on the class of all sets, see Binary relation § Sets versus classes).

Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).