nLab
relation

Idea

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.

Definitions

General case

Given a family $(A_i{)}_{i:I}$ of sets, a relation on that family is a subset of the cartesian product ${\prod }_{i:I}{A}_i$. Equivalently, a relation is a function from ${\prod }_{i:I}{A}_i$ to the set $TV$ of truth values (because $TV$ is the subobject classifier in Set).

Special cases

A nullary relation is a relation on the empty family of sets. This is the same as a truth value.

A unary relation on $A$ is a relation on the singleton family $(A)$. This is the same as a subset of $A$.

A binary relation on $A$ and $B$ is a relation on the family $(A,B)$, that is a subset of $A\times B$. This is also called a relation from $A$ to $B$, especially in the context of the $2$-category Rel described below.

A binary relation on $A$ is a relation on $(A,A)$, that is a relation from $A$ to itself. This is sometimes called simply a relation on $A$.

An $n$-ary relation on $A$ is a relation on a family of $n$ copies of $A$, that is a subset of $A^n$.

For a binary relation, one often uses a symbol such as $\sim$ and writes $a\sim b$ instead of $(a,b)\in \sim$. Actually, even when a relation is given by a letter such as $R$, one often sees $aRb$ instead of $(a,b)\in R$, although now that does not look so good.

Morphisms

If $A$ and $B$ are each sets equipped with a relation, then what makes a function $f:A\to B$ 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 $\sim$, but any fixed arity would work.)

• $f$ preserves the relation if $x\sim y\Rightarrow f(x)\sim f(y)$ always;
• f reflects the relation if $x\sim y\Leftarrow f(x)\sim f(y)$ always.

Now, if $f$ is a bijection, then it preserves the relation if and only if its inverse reflects it, so clearly an isomorphism of relation-equipped sets should do both. What about a mere morphism?

In general, it's more natural to require only preservation; these are the morphisms you get if you consider a set with a relation as a models of a finite-limit theory or a simply directed graph.

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

Binary relations are especially widely used.

Kinds of binary relations

Special kinds of relations from $A$ to $B$ include:

• functional relations,
• entire relations,
• one-to-one relation?s,
• onto relation?s.

Combinations of the above properties of binary relations produce:

• functions,
• partial functions,
• injections,
• surjections,
• bijections.

Special kinds of binary relations on $A$ (so from $A$ to itself) additionally include:

• reflexive and irreflexive relations;
• symmetric, antisymmetric, and asymmetric relations;
• transitive relations and comparisons?;
• left and right euclidean relations?;
• total and connected relations;
• extensional and well-founded relations.

Combinations of the above properties of binary relations produce:

• equivalence relations,
• partial equivalence relations,
• apartness relations,
• the various kinds of orders (which see).

The $2$-poset of binary relations

Binary relations form a $2$-category (in fact a $2$-poset) Rel, which is the basic example of an allegory.

The objects are sets, the morphisms from $A$ to $B$ are the binary relations on $A$ and $B$, and there is a $2$-morphism from $R$ to $S$ (both from $A$ to $B$) if $R$ implies $S$ (that is, when $(a,b)\in R$, then $(a,b)\in S$).

The interesting definition is composition: If $R$ is a relation from $A$ to $B$ and $S$ is a relation from $B$ to $C$, then the composite (written $S\circ R$ or $R;S$) from $A$ to $C$ is defined as follows:

$$(a,c)\in R;S\iff \exists b:B,(a,b)\in R\wedge (b,c)\in S.$$(a,c) \in R;S \;\Leftrightarrow\; \exists b: B,\; (a,b) \in R \;\wedge\; (b,c) \in S.

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.

As a function may be seen as a functional, entire relation, so the category Set of sets and functions is a subcategory of Rel (in fact a replete and locally full sub-$2$-category).

Generalisation

Most of the preceding makes sense in any category with enough products; giving rise to internal relations, for instance congruences in the case of internal equivalence relations.

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.

Related concepts

• graph