left and right euclidean;
A relation is the extension of a predicate. That is, if you have a statement whose truth value may depend on some variables, then you get a relation that consists of those instantiations of the variables that make the statement true. Equivalently, you can think of a relation as a function whose target is the set of truth values.
For the 2-element set (a binary relation) this is in particular a binary correspondence
A nullary relation is a relation on the empty family of sets. This is the same as a truth value.
A unary relation on is a relation on the singleton family . This is the same as a subset of .
A binary relation on and is a relation on the family , that is a subset of . This is also called a relation from to , especially in the context of the -category Rel described below.
A binary relation on is a relation on , that is a relation from to itself. This is sometimes called simply a relation on .
An -ary relation on is a relation on a family of copies of , that is a subset of .
For a binary relation, one often uses a symbol such as and writes instead of . Actually, even when a relation is given by a letter such as , one often sees instead of , although now that does not look so good.
If and are each sets equipped with a relation, then what makes a function a morphism of sets so equipped?
There are really two ways to do this, shown below. (We will write these as if each set is equipped with a binary relation , but any fixed arity would work.) * preserves the relation if always; * f reflects the relation if always.
But in some contexts, particularly when dealing only with irreflexive relations, we instead require (only) that a morphism reflect the relation. Sometimes an even stricter condition is imposed, as for well-orders. But even in these cases, the definition of isomorphism comes out the same.
Binary relations are especially widely used.
Special kinds of relations from to include:
Special kinds of binary relations on (so from to itself) additionally include:
The interesting definition is composition
If is a relation from to and is a relation from to , then their composite relation – written or – from to is defined as follows:
The identity morphism is given by equality.
The special properties of the kinds of binary relations listed earlier can all be described in terms internal to Rel; most of them make sense in any allegory. Irreflexive and asymmetric relations are most useful if the allegory's hom-posets have bottom elements, and linear relations require this. Comparisons require the hom-posets to have finite unions, and well-founded relations require some sort of higher-order structure.
Probably the trickiest bit is the definition of composition of binary relations, so not every category with finite products has an allegory of relations. In fact, in a certain precise sense, a category has an allegory of relations if and only if it is regular. It can then be recovered from this allegory by looking at the functional entire relations.