nLab
1-category equipped with relations

Idea

A 2-category equipped with proarrows is a 2-category together with a 2-category of “proarrows” which are intended to generalize the arrows of $K$ in the same way that profunctors generalize the functors in Cat. Since profunctors are a categorification of relations, it is natural to think of decategorifying such equipments to give a structure on a 1-category that equips it with “relations”. We call this structure a 1-category equipped with relations.

Definition

(1,2)-categories equipped with proarrows

Recall that a 2-category equipped with proarrows (aka “proarrow equipment” or “equipment”) can be defined as a certain sort of double category, with $𝒱(\underline{K})=K$. If, in such a double category, any two squares with the same boundary are equal, we say that it is is a (1,2)-category equipped with proarrows, or a (1,2)-category proarrow equipment. This is equivalent to requiring that the 2-category of proarrows (and hence also the underlying 2-category of arrows) is locally posetal, i.e. a (1,2)-category.

For example, if $V$ is any quantale, then $V\mathrm{Cat}$ is naturally a (1,2)-category equipped with proarrows. In particular, taking $V=𝟚$, we have a (1,2)-category proarrow equipment whose objects are preorders.

1-categories equipped with relations

A 1-category equipped with relations is a (1,2)-category equipped with proarrows, regarded as a double category $\underline{K}$, together with an involution ${\underline{K}}^{h\mathrm{op}}\cong \underline{K}$ which is (isomorphic to) the identity on objects and (vertical) arrows. Here ${\underline{K}}^{h\mathrm{op}}$ denotes the horizontal opposite of a double category obtained by reversing the horizontal (pro-)arrows but not the vertical ones. We also call this structure a relation equipment or a 1-category proarrow equipment.

In particular, the definition implies that we have an involution $K\cong K^{\mathrm{co}}$ which is the identity on objects and arrows, which for a (1,2)-category means that $K$ is actually (equivalent to) a 1-category. Note though that the 2-category of proarrows (which we now call “relations”) is still (like Rel) a (1,2)-category, not necessarily a 1-category.

For example, for any quantale $V$, the sub-2-category of $V\mathrm{Cat}$ consisting of the symmetric $V$-categories (those where $A(x,y)=A(y,x)$) is a 1-category equipped with relations. In particular, for $V=𝟚$, we have the relation equipment $\underline{\mathrm{Rel}}$ of sets, functions, and binary relations.

In general, we can think of a relation equipment as generalizing some of the properties of $\underline{\mathrm{Rel}}$. For instance, internal relations in any regular category also form a relation equipment.

See also

Other attempted axiomatizations of the same idea “something that acts like the category of relations in a regular category” include:

• allegory

• bicategory of relations

Cartesian 1-categories equipped with relations

It is proven in

• Carboni, Kelly, Wood, “A 2-categorical approach to change of base and geometric morphisms, I” (PDF)

that a (1,2)-category is a cartesian bicategory precisely when it is a cartesian object in a suitable 2-category of proarrow equipments (where we make a bicategory $M$ into an equipment by taking the proarrows to be those of $M$ and the arrows to be the “maps” in $M$, i.e. the morphisms having right adjoints). Here is a rough sketch of the argument, using the double-category description of equipments.

Theorem

Let $\underline{K}$ be a 1-category equipped with relations, which is a cartesian object in the 2-category of relation equipments (that is, it is a cartesian relation equipment). Then $\mathscr{H}(\underline{K})$ is a cartesian bicategory.

Proof

That $\underline{K}$ is a cartesian object means, in particular, that it is a pseudomonoid in the 2-category of equipments. By lifting the coherence data from arrows to representable proarrows, it follows that $\mathscr{H}(\underline{K})$ is a monoidal 2-category. Being a cartesian object also gives a cartesian product on objects and proarrows, with diagonals $\Delta :X\to X\times X$, and lifting these arrows to representable proarrows ${\Delta }_{•}$ and ${\Delta }^{•}$ gives each object a commutative monoid and comonoid structure. Now for any proarrow $\varphi :X\to Y$, the square

$$\begin{array}{ccc}X& \stackrel{\varphi }{\to }& Y\\ {}^{\Delta }\downarrow & \Downarrow & {\downarrow }^{\Delta }\\ X\times X& \underset{\varphi \times \varphi }{\to }& Y\times Y\end{array}$$\array{X & \overset{\phi}{\to} & Y\\ ^\Delta \downarrow & \Downarrow & \downarrow^\Delta\\ X\times X& \underset{\phi\times \phi}{\to} & Y\times Y}

in $\underline{K}$ induces 2-cells, i.e. inequalities, ${\Delta }_{•}\varphi \le (\varphi \times \varphi ){\Delta }_{•}$ and $\varphi {\Delta }^{•}\le {\Delta }^{•}(\varphi \times \varphi )$.

A bicategory of relations is a (1,2)-category which is a cartesian bicategory, and which also satisfies some additional conditions. We can also construct this structure starting from a relation equipment.

Theorem

Let $\underline{K}$ be a relation equipment satisfying the hypotheses of the previous theorem, and suppose in addition that every proarrow $\varphi :x\nrightarrow y$ in $\underline{K}$ can be written as $f_{•}{g}^{•}$ for some (vertical) arrows $f$ and $g$. (That is, “tabulations” in a certain sense exist.) Then $\mathscr{H}(\underline{K})$ is a bicategory of relations.

Sketch of Proof

We first verify the axiom ${\Delta }^{•}{\Delta }_{•}=1$. Since ${\Delta }^{•}{\Delta }_{•}$ is the restriction of $1_{X\times X}$ along $\Delta$ on both sides, it suffices to show that

$$\begin{array}{ccc}X& \stackrel{1_X}{\to }& X\\ {}^{\Delta }\downarrow & \Downarrow & {\downarrow }^{\Delta }\\ X\times X& \underset{1_{X\times X}}{\to }& X\times X\end{array}$$\array{X & \overset{1_X}{\to} & X\\ ^\Delta\downarrow &\Downarrow& \downarrow^\Delta\\ X\times X& \underset{1_{X\times X}}{\to} & X\times X}

is a cartesian 2-cell in $\underline{K}$. But if we have any other square

$$\begin{array}{ccc}A& \stackrel{\varphi }{\to }& B\\ {}^{(f,g)}\downarrow & \Downarrow & {\downarrow }^{(h,k)}\\ X\times X& \underset{1_{X\times X}}{\to }& X\times X\end{array}$$\array{A & \overset{\phi}{\to} & B\\ ^{(f,g)}\downarrow &\Downarrow& \downarrow^{(h,k)}\\ X\times X& \underset{1_{X\times X}}{\to} & X\times X}

then $(f,g)$ factoring through $\Delta$ means that $f=g$, and likewise $h=k$. Composing the given square with the projection

$$\begin{array}{ccc}X\times X& \stackrel{1_{X\times X}}{\to }& X\times X\\ \downarrow & \Downarrow & \downarrow \\ X& \underset{1_X}{\to }& X\end{array}$$\array{X\times X & \overset{1_{X\times X}}{\to} & X\times X\\ \downarrow &\Downarrow & \downarrow\\ X& \underset{1_X}{\to} & X}

(which comes from being a cartesian object in $\mathrm{Equipments}$), we obtain a square

$$\begin{array}{ccc}A& \stackrel{\varphi }{\to }& B\\ {}^f\downarrow & \Downarrow & {\downarrow }^g\\ X& \underset{1_X}{\to }& X\end{array}$$\array{A & \overset{\phi}{\to} & B \\ ^f\downarrow &\Downarrow & \downarrow^g\\ X& \underset{1_X}{\to} & X}

which factors the given square through the putative cartesian one. The factorization is unique since all 2-cells are unique.

We now verify the Frobenius axiom ${\Delta }^{•}{\Delta }_{•}=(1\times {\Delta }_{•})({\Delta }^{•}\times 1)$. Since $\Delta$ is associative, we have a square

$$\begin{array}{ccc}X& \stackrel{1_X}{\to }& X\\ {}^{\Delta }\downarrow & & {\downarrow }^{\Delta }\\ X\times X& \Downarrow & X\times X\\ {}^{1\times \Delta }\downarrow & & {\downarrow }^{\Delta \times 1}\\ X\times X\times X& \underset{1_{X\times X\times X}}{\to }& X\times X\times X\end{array}$$\array{X & \overset{1_X}{\to} & X\\ ^\Delta\downarrow && \downarrow^\Delta\\ X\times X & \Downarrow & X\times X\\ ^{1\times \Delta}\downarrow && \downarrow^{\Delta\times 1}\\ X\times X\times X & \underset{1_{X\times X\times X}}{\to} & X\times X\times X}

and therefore a square

$$\begin{array}{ccc}X\times X& \stackrel{{\Delta }^{•}{\Delta }_{•}}{\to }& X\times X\\ {}^{1\times \Delta }\downarrow & & {\downarrow }^{\Delta \times 1}\\ X\times X\times X& \underset{1_{X\times X\times X}}{\to }& X\times X\times X\end{array}$$\array{X\times X & \overset{\Delta^\bullet \Delta_\bullet}{\to} & X\times X\\ ^{1\times \Delta}\downarrow && \downarrow^{\Delta\times 1}\\ X\times X\times X & \underset{1_{X\times X\times X}}{\to} & X\times X\times X}

and it suffices to show that this is a cartesian 2-cell. So suppose given a square

$$\begin{array}{ccc}A& \stackrel{\varphi }{\to }& B\\ {}^{(f,g,g)}\downarrow & \Downarrow & {\downarrow }^{(h,h,k)}\\ X\times X\times X& \underset{1_{X\times X\times X}}{\to }& X\times X\times X.\end{array}$$\array{A & \overset{\phi}{\to} & B\\ ^{(f,g,g)}\downarrow & \Downarrow & \downarrow^{(h,h,k)}\\ X\times X\times X & \underset{1_{X\times X\times X}}{\to} & X\times X\times X.}

The fact that $g$ and $h$ appear twice is equivalent to saying that the left and right boundaries of this square factor through $1\times \Delta$ and $\Delta \times 1$, respectively. Now by assumption, $\varphi =u_{•}{v}^{•}$ for some $u:C\to B$ and $v:C\to A$. Thus our square is equivalent to one

$$\begin{array}{ccc}C& \stackrel{1_C}{\to }& C\\ {}^{(fv,gv,gv)}\downarrow & \Downarrow & {\downarrow }^{(hu,hu,ku)}\\ X\times X\times X& \underset{1_{X\times X\times X}}{\to }& X\times X\times X.\end{array}$$\array{C & \overset{1_C}{\to} & C\\ ^{(f v,g v,g v)}\downarrow & \Downarrow & \downarrow^{(h u,h u,k u)}\\ X\times X\times X & \underset{1_{X\times X\times X}}{\to} & X\times X\times X.}

But this is just a 2-cell in the vertical category $K$, which is a 1-category; hence we have $(fv,gv,gv)=(hu,hu,ku)$ and thus $fv=hu=gv=ku$. Calling their common value $m$, we thus have a composite square

$$\begin{array}{ccccc}C& =& C& =& C\\ {}^{(m,m)}\downarrow & & {\downarrow }^m& & {\downarrow }^{(m,m)}\\ X\times X& \underset{{\Delta }^{•}}{\to }& X& \underset{{\Delta }_{•}}{\to }& X\times X\end{array}$$\array{C & = & C & = & C\\ ^{(m,m)}\downarrow && \downarrow^{m} && \downarrow^{(m,m)}\\ X\times X & \underset{\Delta^\bullet }{\to} & X & \underset{\Delta_\bullet}{\to} & X\times X}

(since $\Delta m=(m,m)$) which gives us the desired factorization. The other Frobenius axiom is, of course, dual.

Corollary

If $\underline{K}$ is a relation equipment satisfying the hypotheses of the theorem, then $\mathscr{H}(\underline{K})$ is an allegory.

Proof

It is shown here that any bicategory of relations is an allegory.