nLab Rel

RelRel

Idea

RelRel is the category whose objects are sets and whose morphisms are (binary) relations between sets. It becomes a 2-category Rel\mathbf{Rel} (in fact, a 2-poset) by taking 2-morphisms to be inclusions of relations.

Definition

RelRel is a category whose objects or 00-cells are sets, whose morphisms or 11-cells XYX \to Y are relations RX×YR \subseteq X \times Y, and where the composite SRS \circ R of morphisms R:XYR: X \to Y and S:YZS: Y \to Z is defined as the usual relational composite:

{(x,z)X×Z: yY(x,y)R(y,z)S}X×Z.\{(x, z) \in X \times Z: \exists_{y \in Y} (x, y) \in R \wedge (y, z) \in S\} \subseteq X \times Z .

Another important operation on relations is taking the opposite, also known as the transpose or sometimes the converse. Any relation R:XYR: X \to Y induces a relation

R ={(y,x)Y×X:(x,y)R}Y×XR^\dagger = \{(y, x) \in Y \times X: (x, y) \in R\} \subseteq Y \times X

This makes RelRel into a dagger-category: in other words, we have (SR) =R S (S \circ R)^\dagger = R^\dagger \circ S^\dagger, 1 X =1 X1_X^\dagger = 1_X, and (R ) =R(R^{\dagger})^{\dagger} = R.

We can enhance RelRel to a 2-category, which we can call Rel\mathbf{Rel} to distinguish it from the mere category, by taking 2-morphisms or 22-cells RSR \Rightarrow S to be inclusions of relations. Since there is at most one 2-morphism between parallel 1-morphisms, Rel\mathbf{Rel} is a 2-poset: that is, an category enriched in the category of posets.

Relations and spans

It is useful to be aware of the connections between the bicategory of relations and the bicategory of spans. Recall that a span from XX to YY is a diagram of the form

XSYX \leftarrow S \to Y

and there is an obvious category whose objects are spans from XX to YY and whose morphisms are morphisms between such diagrams. The terminal span from XX to YY is

Xπ 1X×Yπ 2YX \stackrel{\pi_1}{\leftarrow} X \times Y \stackrel{\pi_2}{\to} Y

and a relation from XX to YY is just a subobject of the terminal span, in other words an isomorphism class of monos into the terminal span.

To each span SS from XX to YY, there is a corresponding relation from XX to YY, defined by taking the image of the unique morphism of spans SX×YS \to X \times Y between XX and YY. It may be checked that this yields a lax morphism of bicategories

SpanRelSpan \to Rel

Limits and colimits

The category RelRel does have products and coproducts; they coincide (by self-duality) and are just disjoint unions of sets. However, otherwise RelRel has very few (co)limits; it doesn’t even have splittings of all idempotents. All symmetric idempotents have splittings, but the order-relation {0,1}×{0,1}\leq \; \subseteq \{0,1\} \times \{0,1\} can’t be split. It follows that it can’t have (co)equalisers.

Since the category RelRel is the category of free algebras (Kleisli category) for the powerset monad?, there is, indeed, very little chance of a limit of such algebras being free again. To get decent limits, one has to move to the Eilenberg-Moore category of the powerset monad, viz., the category of complete suplattices.

Weak equalizers and completion

As the category RelRel has weak equalizers, one can take its exact completion. This happens to be the category of complete sup-lattices and sup-preserving maps. And the tensor product on RelRel extends to the exact completion.

The Freyd completion of RelRel, which is equivalent to the category of basic pairs which appear in formal topology, has all limits exactly because RelRel has products and weak equalizers. The Freyd completion adds freely a strong factorization system to a(ny) category CC. The Freyd completion has products if CC has products, and it has equalizers if CC has weak equalizers.

In the double category of relations

If you insert the category RelRel into the double category RRel\mathrm{RRel} of sets, mappings and relations, one has a double category with all double limits and colimits. For instance, the obvious cartesian product a×b:X×YX×Ya \times b : X \times Y \to X' \times Y' (resp. sum a+b:X+YX+Ya+b : X + Y \to X' + Y') of two relations is indeed a product (resp. a sum) in the double category.

Similarly, many bicategories of spans, cospans, relations, profunctors, etc. have poor (co)limits, but can be usefully embedded in weak double categories (with the same objects, “strict morphisms”, “same morphisms”, suitable double cells) that have all limits and colimits.

As an enriched category

Writing 𝒱\mathcal{V} for the category of suplattices, RelRel is a 𝒱\mathcal{V}-category (see enriched category). With that in mind, the parallel:

is remarkable. This was probably first noticed by Dana May Latch, in the 20th century, for the category of 𝒱\mathcal{V} of complete suplattices.

The matrix algebra for maps to products, from coproducts, and most especially, from coproducts to products, works just as it does in the case of additive categories, when it comes to these 𝒱\mathcal{V}-categories.

In spans

See van Kampen colimit.

Mono/epimorphisms

It is not hard to see that a relation RA×BR \subseteq A \times B is a monomorphism ABA \to B iff the map 𝒫A𝒫B\mathcal{P}A \to \mathcal{P}B sending a subset of A to the set of all R-relatives of its members is injective; dually for epimorphisms.

2-categorical aspects

Recall that we are using Rel\mathbf{Rel} to stand for the 2-category of sets, relations and inclusions. Various facts about relations can be recast in these terms. For example, a relation L:XYL : X \to Y is a function from XX to YY iff it has a right adjoint R:YXR : Y \to X in Rel\mathbf{Rel}. In this case, its right adjoint equals its transpose L :YXL^\dagger : Y \to X.

Similarly, a monad T:XXT : X \to X in the 2-category Rel\mathbf{Rel} is exactly a preorder on XX, since the existence of a unit i:1 XTi: 1_X \Rightarrow T says that TT is reflexive and the existence of the multiplication m:T 2Tm: T^2 \Rightarrow T says that TT is transitive. This monad has an Eilenberg-Moore object iff it is an equivalence relation, in which case the Eilenberg-Moore object is the set of equivalence classes of the relation.

Relations in a category

More generally, given any regular category CC, one can form a 2-category of relations Rel(C)\mathbf{Rel}(C) in similar fashion. The objects of Rel(C)\mathbf{Rel}(C) are objects of CC, the morphisms r:cdr: c \to d in Rel(C)\mathbf{Rel}(C) are defined to be subobjects of the terminal span from cc to dd, and 2-cells rsr \to s are subobject inclusions. To form the composite of rc×dr \subseteq c \times d and sd×es \subseteq d \times e, one takes the image of the unique span morphism

r× csc×er \times_c s \to c \times e

in the category of spans from cc to ee, thus giving a mono into the terminal span from cc to ee. The subobject class of this mono defines the relation

src×es \circ r \subseteq c \times e

and the axioms of a regular category ensure that Rel(C)\mathbf{Rel}(C) is a 2-category with desirable properties. Similar to what was said above, there is again a lax morphism of bicategories

Span(C)Rel(C)Span(C) \to \mathbf{Rel}(C)

There is also a functor

i:CRel(C)i: C \to \mathbf{Rel}(C)

that takes a morphism f:cdf: c \to d to the functional relation defined by ff, i.e., the relation defined by the subobject class of the mono

1,f:cc×d\langle 1, f\rangle: c \to c \times d

Such functional relations may also be characterized as precisely those 1-cells in Rel(C)Rel(C) which are left adjoints; the right adjoint of 1,f\langle 1, f \rangle is the opposite relation f,1\langle f, 1\rangle. The unit amounts to a condition

1 cf,11,f1_c \subseteq \langle f, 1 \rangle \circ \langle 1, f \rangle

which says that the functional relation is total, and the counit amounts to a condition

1,ff,11 d\langle 1, f \rangle \circ \langle f, 1 \rangle \subseteq 1_d

which says the functional relation is well-defined.

A category of correspondences is a generalization of a category of relations. The composition of relations is that of correspondences followed by (-1)-truncation.

For generalizations of RelRel see

References

Relations may be considered in any category with a stable proper factorisation system?, but this is no more general than considering relations in a regular category, as proven in

  • Gregory Maxwell Kelly. A note on relations relative to a factorization system. Category Theory. Springer, Berlin, Heidelberg, 1991.

An axiomatization of the category of sets and relations is found in:

category: category

Last revised on January 30, 2024 at 11:49:14. See the history of this page for a list of all contributions to it.