nLab
1-category equipped with relations

Contents

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 KK 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 𝒱(K̲)=K\mathcal{V}(\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 VV is any quantale, then VCatV Cat is naturally a (1,2)-category equipped with proarrows. In particular, taking V=𝟚V=\mathbb{2}, 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 K̲\underline{K}, together with an involution K̲ hopK̲\underline{K}^{h op} \cong \underline{K} which is (isomorphic to) the identity on objects and (vertical) arrows. Here K̲ hop\underline{K}^{h 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 KK coK \cong K^{co} which is the identity on objects and arrows, which for a (1,2)-category means that KK 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 VV, the sub-2-category of VCatV Cat consisting of the symmetric VV-categories (those where A(x,y)=A(y,x)A(x,y) = A(y,x)) is a 1-category equipped with relations. In particular, for V=𝟚V=\mathbb{2}, we have the relation equipment Rel̲\underline{Rel} of sets, functions, and binary relations.

In general, we can think of a relation equipment as generalizing some of the properties of Rel̲\underline{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:

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 MM into an equipment by taking the proarrows to be those of MM and the arrows to be the “maps” in MM, i.e. the morphisms having right adjoints). Here is a rough sketch of the argument, using the double-category description of equipments.

Theorem

Let K̲\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 (K̲)\mathcal{H}(\underline{K}) is a cartesian bicategory.

Proof

That K̲\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 (K̲)\mathcal{H}(\underline{K}) is a monoidal 2-category. Being a cartesian object also gives a cartesian product on objects and proarrows, with diagonals Δ:XX×X\Delta\colon X\to X\times X, and lifting these arrows to representable proarrows Δ \Delta_\bullet and Δ \Delta^\bullet gives each object a commutative monoid and comonoid structure. Now for any proarrow ϕ:XY\phi\colon X\to Y, the square

X ϕ Y Δ Δ X×X ϕ×ϕ Y×Y\array{X & \overset{\phi}{\to} & Y\\ ^\Delta \downarrow & \Downarrow & \downarrow^\Delta\\ X\times X& \underset{\phi\times \phi}{\to} & Y\times Y}

in K̲\underline{K} induces 2-cells, i.e. inequalities, Δ ϕ(ϕ×ϕ)Δ \Delta_\bullet \phi \le (\phi\times\phi)\Delta_\bullet and ϕΔ Δ (ϕ×ϕ)\phi \Delta^\bullet \le \Delta^\bullet(\phi\times\phi).

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 K̲\underline{K} be a relation equipment satisfying the hypotheses of the previous theorem, and suppose in addition that every proarrow ϕ:xy\phi\colon x\nrightarrow y in K̲\underline{K} can be written as f g f_\bullet g^\bullet for some (vertical) arrows ff and gg. (That is, “tabulations” in a certain sense exist.) Then (K̲)\mathcal{H}(\underline{K}) is a bicategory of relations.

Sketch of Proof

We first verify the axiom Δ Δ =1\Delta^\bullet \Delta_\bullet = 1. Since Δ Δ \Delta^\bullet \Delta_\bullet is the restriction of 1 X×X1_{X\times X} along Δ\Delta on both sides, it suffices to show that

X 1 X X Δ Δ X×X 1 X×X X×X\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 K̲\underline{K}. But if we have any other square

A ϕ B (f,g) (h,k) X×X 1 X×X X×X\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)(f,g) factoring through Δ\Delta means that f=gf=g, and likewise h=kh=k. Composing the given square with the projection

X×X 1 X×X X×X X 1 X X\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 EquipmentsEquipments), we obtain a square

A ϕ B f g X 1 X X\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 Δ Δ =(1×Δ )(Δ ×1)\Delta^\bullet \Delta_\bullet = (1\times \Delta_\bullet)(\Delta^\bullet \times 1). Since Δ\Delta is associative, we have a square

X 1 X X Δ Δ X×X X×X 1×Δ Δ×1 X×X×X 1 X×X×X X×X×X\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

X×X Δ Δ X×X 1×Δ Δ×1 X×X×X 1 X×X×X X×X×X\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

A ϕ B (f,g,g) (h,h,k) X×X×X 1 X×X×X X×X×X.\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 gg and hh appear twice is equivalent to saying that the left and right boundaries of this square factor through 1×Δ1\times\Delta and Δ×1\Delta\times 1, respectively. Now by assumption, ϕ=u v \phi = u_\bullet v^\bullet for some u:CBu\colon C\to B and v:CAv\colon C\to A. Thus our square is equivalent to one

C 1 C C (fv,gv,gv) (hu,hu,ku) X×X×X 1 X×X×X X×X×X.\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 KK, which is a 1-category; hence we have (fv,gv,gv)=(hu,hu,ku)(f v,g v, g v) = (h u, h u, k u) and thus fv=hu=gv=kuf v = h u = g v = k u. Calling their common value mm, we thus have a composite square

C = C = C (m,m) m (m,m) X×X Δ X Δ X×X\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 Δm=(m,m)\Delta m = (m,m)) which gives us the desired factorization. The other Frobenius axiom is, of course, dual.

Corollary

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

Proof

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

Revised on December 3, 2009 22:45:45 by Toby Bartels (173.60.119.197)