Relations

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:

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.