nLab
Rel

RelRel

Idea

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

Definition

RelRel is a 2-poset (a category enriched in the category of posets), whose objects or 00-cells are sets, whose morphisms or 11-cells XYX \to Y are relations RX×YR \subseteq X \times Y, and whose 2-morphisms or 22-cells RSR \to S are inclusions of relations. The composite SRS \circ R of morphisms R:XYR: X \to Y and S:YZS: Y \to Z is defined by 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\} \hookrightarrow X \times Z

and the identity 1 X:XX1_X: X \to X is the equality relation, in other words the usual diagonal embedding

{(x,x):xX}X×X.\{(x, x): x \in X\} \hookrightarrow X \times X.

Another important operation on relations is taking the opposite: any relation R:XYR: X \to Y induces a relation

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

and this operation obeys a number of obvious identities, such as (SR) op=R opS op(S \circ R)^{op} = R^{op} \circ S^{op} and 1 X op=1 X1_X^{op} = 1_X.

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

Relations in a category

More generally, given any regular category CC, one can form a 2-category of relations Rel(C)Rel(C) in similar fashion. The objects of Rel(C)Rel(C) are objects of CC, the morphisms r:cdr: c \to d in Rel(C)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)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 Rel(C)

There is also a functor

i:CRel(C)i: C \to 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

category: category

Revised on August 23, 2013 01:28:39 by Urs Schreiber (150.212.98.234)