A (binary) relation is an association between, or a condition on, ordered pairs of objects. For example, motherhood is a relation between certain pairs of human beings, (usually expressed in a statement of the form "x is the mother of y"). Formally, any set of ordered pairs is considered to define a relation, and so a relation between two sets X and Y is sometimes defined as being some subset of X×Y. Given such a definition of a relation R, if <x,y>∈R then this is usually expressed in a statement of the form x R y. It is common for the "name" R for a relation to be a special symbol. Not all relations can be defined like this. For example "is a subset of" is a relation which may or may not hold between any two sets, but there is no "set of all sets", so there is no way of expressing this relation as a set of ordered pairs. When a relation is defined as a subset of X×Y the set X is called the domain of the relation, and the set Y is called the codomain.
A relation is sometimes also called a relationship or a correspondence. The word "relationship" is sometimes more natural grammatically. However the use of the word "correspondence" for a relation is less usual, and is probably best avoided.
Commonly a relation will be defined between elements of the same set X, (so that is a subset of X×X). There are several important properties that such a relation may or may not have:
- It is said to be transitive if whenever it is true that x R y and y R z then x R z. For example "is taller than" or "is heavier than" define transitive relations between humans, but "knows" defines a relation that is not transitive: if x knows y and y knows z it does not follow that x knows z.
- R is said to be reflexive if for any x in the domain x R x. In everyday language words that define relations tend to exclude this possibility, but in mathematical usage reflexive relations are both common and important, and it is often the case that both reflexive and non-reflexive "versions" of a relation are defined. For example the relation ⊂ between sets is not reflexive, but the relation ⊆ is. Similarly, for numbers, the < relation is not reflexive, but the ≤ relation is.
- R is said to be symmetric if whenever x R y then also y R x. For example "knows" usually would be considered to be a symmetric relationship between humans. Or, to make things clear, we might replace "knows" by "has met", which is certainly symmetric. Another symmetric relation between humans is "is a sibling of" (whereas the relation "is a brother of" is not symmetric (why?)).
- Conversely, a relation R is said to be antisymmetric if whenever both x R y and y R x then x = y. Such relations do not arise often in everyday life, but they are again both common and important in mathematics. For example the ⊆ relation between sets has this property, and the ≤ relation between numbers has it.
- A relation is said to be asymmetric if it is never the case that both x R y and y R x. "is the mother of" is a relation that has this property.
- Given arbitrary x,y it may be the case that either x R y or y R x. "is divisible by" is a relation between natural numbers that does not have this property: 7 is not divisible by 3, nor is 3 divisible by 7. By contrast "is less than or equal to" does have this property. Although everyday relations such as "is taller than", or "is heavier than" do not quite have this property, the very similar relations "is not shorter than" and "is not lighter than" do have it. A relation with this property is sometimes said to be connected or complete, though neither of these terms are particularly common in this connection, and the latter is probably best avoided.
A relation that is transitive, reflexive, and symmetric is called an equivalence relation.
A relation that is transitive, reflexive, and anti-symmetric is called a partial ordering. If a partial ordering is also connected then it is called a total ordering or a linear ordering. Both these latter terms, and especially "total ordering" are applied to relations more commonly than the term connected. The ⊆ relation between sets is an example of a partial ordering that is not a total ordering.
Both ordering (whether partial or total) and equivalence relations are of great importance. Another very important type of relation is one in which if x R y and x R z then y=z. Such a relation is called a function.