Contents

Introduction

In this article we establish a connection between pretabular unitary allegories and bicategories of relations, and also between tabular unitary allegories and regular categories. The material is entirely adapted from Categories, Allegories; we have merely changed some details of arrangement, notation, and terminology.

Preliminaries

We write the composite of morphisms $r:a\to b$, $s:b\to c$ as $sr:a\to c$.

An allegory is a $\mathrm{Pos}$-enriched $†$-category $A$ where each hom-poset has binary meets, and the modular law is satisfied. The modular law takes two forms, whenever the left sides of the inequalities make sense:

• $rs\wedge t\le r\left(s\wedge {r}^{†}t\right)$

• $rs\wedge t\le \left(r\wedge t{s}^{†}\right)s$

(and of course there are variations, using commutativity of $\wedge$). Each of these forms can be derived from the other, using the $†$-structure.

The $†$-operation, which we henceforth denote by $\left(-{\right)}^{o}$, preserves meets since it preserves order and is an involution.)

Lemma

For any $r:a\to b$, we have $r\le r{r}^{o}r$.

Proof

We have $r\le r{1}_{b}\wedge r\le r\left(1\wedge {r}^{o}r\right)\le r{r}^{o}r$ where the middle inequality uses the modular law.

Recall that a map in an allegory is a morphism $f:a\to b$ such that $f⊣{f}^{o}$. A relation $r:a\to b$ is well-defined if we merely have a counit inclusion $r{r}^{o}\le {1}_{b}$, and is total if we merely have a unit inclusion ${1}_{a}\le {r}^{o}r$. Clearly maps are closed under composition, as are total relations and well-defined relations.

Lemma

If $f:a\to b$ is a map, then for any $r,s\in \mathrm{hom}\left(b,c\right)$ we have $\left(r\wedge s\right)f=rf\wedge sf$.

Proof

The non-trivial inclusion follows from

$rf\wedge sf\le \left(r\wedge sf{f}^{o}\right)f\le \left(r\wedge s\right)f$r f \wedge s f \leq (r \wedge s f f^o)f \leq (r \wedge s)f

where the first inequality is an instance of the modular law, and the second holds for any well-defined relation $f$.

Lemma

If $f,g:a\to b$ are maps and $f\le g$, then $f=g$.

Since the dagger operation $\left(-{\right)}^{o}:\mathrm{hom}\left(a,b\right)\to \mathrm{hom}\left(b,a\right)$ preserves order, we have ${f}^{o}\le {g}^{o}$. But also the inclusion $f\le g$ between left adjoints is mated to an inclusion ${g}^{o}\le {f}^{o}$ between right adjoints. Hence ${f}^{o}={g}^{o}$, and therefore $f=g$.

Domains and coreflexives

Definition

Let $r:a\to b$ be a morphism. We define the domain $dom\left(r\right)$ to be ${1}_{a}\wedge {r}^{o}r$. A morphism $e:a\to a$ is coreflexive if $e\le {1}_{a}$; in particular, domains are coreflexive. $\mathrm{Cor}\left(a\right)$ denotes the poset of coreflexives in $\mathrm{hom}\left(a,a\right)$.

Lemma

Coreflexives $r:a\to a$ are symmetric and transitive. (Symmetric and transitive imply idempotent.)

Proof

We have $r\le r{r}^{o}r\le {1}_{a}{r}^{o}{1}_{a}\le {r}^{o}$ where the first inequality is lemma 1. Of course also $rr\le {1}_{a}r=r$. (If $r$ is symmetric and transitive, then $r\le r{r}^{o}r=rrr\le rr$ as well.)

Lemma

For $r,s\in \mathrm{hom}\left(a,b\right)$, we have $dom\left(r\wedge s\right)={1}_{a}\wedge {r}^{o}s$.

Proof

One inclusion is trivial:

$dom\left(r\wedge s\right)={1}_{a}\wedge \left(r\wedge s{\right)}^{o}\left(r\wedge s\right)\le {1}_{a}\wedge {r}^{o}s.$\dom(r \wedge s) = 1_a \wedge (r \wedge s)^o (r \wedge s) \leq 1_a \wedge r^o s.

The other inclusion follows from fairly tricky applications of the modular law:

$\begin{array}{ccc}{1}_{a}\wedge {s}^{o}r& \le & {1}_{a}\wedge \left({1}_{a}\wedge \left({1}_{a}\wedge {s}^{o}r\right)\right)\\ & \le & {1}_{a}\wedge \left({1}_{a}\wedge {s}^{o}\left(s\wedge r\right)\right)\\ & \le & {1}_{a}\wedge \left(\left(s\wedge r{\right)}^{o}\wedge {s}^{o}\right)\left(s\wedge r\right)\\ & \le & {1}_{a}\wedge \left(s\wedge r{\right)}^{o}\left(s\wedge r\right)\\ & =& dom\left(s\wedge r\right).\end{array}$\array{ 1_a \wedge s^o r & \leq & 1_a \wedge (1_a \wedge (1_a \wedge s^o r)) \\ & \leq & 1_a \wedge (1_a \wedge s^o(s \wedge r)) \\ & \leq & 1_a \wedge ((s \wedge r)^o \wedge s^o)(s \wedge r) \\ & \leq & 1_a \wedge (s \wedge r)^o (s \wedge r) \\ & = & \dom(s \wedge r). }
Lemma

For $r:a\to b$ and coreflexives $c\in \mathrm{hom}\left(a,a\right)$, we have $dom\left(r\right)\le c$ if and only if $r\le rc$. In particular, $r\le r\circ dom\left(r\right)$.

Proof

If ${1}_{a}\wedge {r}^{o}r\le c$, then

$r\le r{1}_{a}\wedge r\le r\left({1}_{a}\wedge {r}^{o}r\right)\le rc.$r \leq r 1_a \wedge r \leq r(1_a \wedge r^o r) \leq r c.

If $r\le rc$, then

${1}_{a}\wedge {r}^{o}r\le {1}_{a}\wedge {r}^{o}rc\le \left({c}^{o}\wedge {r}^{o}r\right)c\le {c}^{o}c\le c$1_a \wedge r^o r \leq 1_a \wedge r^o r c \leq (c^o \wedge r^o r)c \leq c^o c \leq c

where the antepenultimate inequality uses the modular law, and the last uses lemma 4.

Corollary

For $r:a\to b$ and $s:b\to c$, we have $dom\left(sr\right)\le dom\left(r\right)$.

By lemma 6, it suffices that $sr\le sr\circ dom\left(r\right)$. But this follows from the last sentence of lemma 6.

Units

Definition

An object $t$ is a unit in an allegory if ${1}_{t}$ is maximal in $\mathrm{hom}\left(t,t\right)$ and if for every object $a$ there is $f:a\to t$ such that ${1}_{a}\le {f}^{o}f$ (i.e., $f$ is total).

Of course by maximality we also have $f{f}^{o}\le {1}_{t}$, so such $f$ must also be a map.

We say $A$ is unital (Freyd-Scedrov say unitary) if $A$ has a unit.

Proposition

Let $t$ be a unit. Then $dom:\mathrm{hom}\left(a,t\right)\to \mathrm{Cor}\left(a\right)$ is an injective order-preserving function.

Proof

Order-preservation is clear. If $r,s:a\to t$ and $dom\left(r\right)\le dom\left(s\right)$, then $r\le s$:

$r\le r\circ dom\left(r\right)\le r\circ dom\left(s\right)\le r{s}^{o}s\le s$r \leq r \circ \dom(r) \leq r \circ \dom(s) \leq r s^o s \leq s

where the first inequality uses lemma 6, and the last inequality follows from $r{s}^{o}\le {1}_{t}$ (since ${1}_{t}$ is maximal in $\mathrm{hom}\left(t,t\right)$). Therefore $dom\left(r\right)=dom\left(s\right)$ implies $r=s$.

Corollary

For a unit $t$ and any $a$, there is at most one total relation = map $r:a\to t$ (because in that case $dom\left(r\right)={1}_{a}$, and we apply the previous proposition), and this is maximal in $\mathrm{hom}\left(a,t\right)$. Thus $t$ is terminal in $\mathrm{Map}\left(A\right)$.

Let ${\epsilon }_{a}:a\to t$ denote the maximal element of $\mathrm{hom}\left(a,t\right)$. For any $r:a\to b$, we then have $r\le {\epsilon }_{b}^{o}{\epsilon }_{a}$ since this is mated to the inequality ${\epsilon }_{b}r\le {\epsilon }_{a}$. Therefore ${\epsilon }_{b}^{o}{\epsilon }_{a}$ is the maximal element of $\mathrm{hom}\left(a,b\right)$.

Tabulations in allegories

Recall from Categories, Allegories that a tabulation of $r:a\to b$ is a pair of maps $f:x\to a$, $g:x\to b$ such that $r=g{f}^{o}$ and ${f}^{o}f\wedge {g}^{o}g={1}_{x}$.

Preliminaries on tabulations

Lemma

For maps $f:x\to a$, $g:x\to b$, the condition ${f}^{o}f\wedge {g}^{o}g={1}_{x}$ implies $\left(f,g\right)$ is a jointly monic pair in $\mathrm{Map}\left(A\right)$.

Proof

Let $h,h\prime :y\to x$ be maps, and suppose $fh=fh\prime$ and $gh=gh\prime$. If ${f}^{o}f\wedge {g}^{o}g={1}_{x}$, then

$h=\left({f}^{o}f\wedge {g}^{o}g\right)h={f}^{o}fh\wedge {g}^{o}gh={f}^{o}fh\prime \wedge {g}^{o}gh\prime =\left({f}^{o}f\wedge {g}^{o}gg\right)h\prime =h\prime$h = (f^o f \wedge g^o g)h = f^o f h \wedge g^o g h = f^o f h' \wedge g^o g h' = (f^o f \wedge g^o g g)h' = h'

where the second and fourth equations use lemma 2.

Proposition

Suppose $r:a\to b$ is tabulated by $\left(f:x\to a,g:x\to b\right)$, and suppose $h:y\to a$, $k:y\to b$ are maps. We have $k{h}^{o}\le g{f}^{o}$ if and only if there exists a map $j:y\to x$ such that $h=fj$ and $k=gj$ (this $j$ is unique by lemma 7).

Proof

One direction is easy: if $h=fj$ and $k=gj$ for some map $j$, then

$k{h}^{o}=gj{j}^{o}{f}^{o}\le g{f}^{o}.$k h^o = g j j^o f^o \leq g f^o.

In the other direction: suppose $k{h}^{o}\le g{f}^{o}$. Put $j={f}^{o}h\wedge {g}^{o}k$. First we check that $j$ is a map. We have ${1}_{y}\le {j}^{o}j$ from

${1}_{y}\le {1}_{y}\wedge \left({k}^{o}k\right)\left({h}^{o}h\right)\le {1}_{y}\wedge {k}^{o}g{f}^{o}h\le dom\left({f}^{o}h\wedge {g}^{o}k\right)=dom\left(j\right)$1_y \leq 1_y \wedge (k^o k)(h^o h) \leq 1_y \wedge k^o g f^o h \leq \dom(f^o h \wedge g^o k) = \dom(j)

using lemma 5. We have $j{j}^{o}\le {1}_{x}$ from

$\left({f}^{o}h\wedge {g}^{o}k\right)\left({h}^{o}f\wedge {k}^{o}g\right)\le \left({f}^{o}h{h}^{o}f\right)\wedge \left({g}^{o}k{k}^{o}g\right)\le \left({f}^{o}f\wedge {g}^{o}g\right)\le {1}_{x}$(f^o h \wedge g^o k)(h^o f \wedge k^o g) \leq (f^o h h^o f) \wedge (g^o k k^o g) \leq (f^o f \wedge g^o g) \leq 1_x

where the last step uses one of the tabulation conditions. So $j$ is a map.

Finally, we have $fj\le f\left({f}^{o}h\right)\le h$, which implies $fj=h$ (lemma 3). Similarly $gj=k$.

Corollary

Tabulations are unique up to unique isomorphism.

Proposition

A diagram in $\mathrm{Map}\left(A\right)$

$\begin{array}{ccc}p& \stackrel{h}{\to }& a\\ {}^{k}↓& & {↓}^{f}\\ b& \underset{g}{\to }& c\end{array}$\array{ p & \stackrel{h}{\to} & a \\ ^\mathllap{k} \downarrow & & \downarrow^\mathrlap{f} \\ b & \underset{g}{\to} & c }

commutes if and only if $k{h}^{o}\le {g}^{o}f$.

Proof

An identity inclusion $gk=fh$ is certainly mated to an inclusion $k{h}^{o}\le {g}^{o}f$. Conversely, an inclusion $k{h}^{o}\le {g}^{o}f$ is mated to $gk\le fh$, and we can use lemma 3.

Corollary

Given $f:a\to c$ and $g:b\to c$ in $\mathrm{Map}\left(A\right)$, a tabulation $\left(h:p\to a,k:p\to b\right)$ of $r={g}^{o}f$ provides a pullback of $\left(f,g\right)$.

Proof

Indeed, by definition of tabulation we then have $k{h}^{o}={g}^{o}f$, so $gk=fh$. For the universality of $\left(h,k\right)$: if $gk\prime =fh\prime$, then $k\left(h\prime {\right)}^{o}\le {g}^{o}f$, and we can apply proposition 2 to finish.

Corollary

If $i:a\to b$ is a monomorphism in $\mathrm{Map}\left(A\right)$ and ${i}^{o}i$ has a tabulation, then ${i}^{o}i={1}_{a}$.

Proof

The tabulation of ${i}^{o}i$ gives a pullback of the pair $\left(i,i\right)$, but since this pullback is already $\left({1}_{a},{1}_{a}\right)$, the conclusion is clear.

Lemma

If $r:a\to a$ is coreflexive, then for any tabulation $\left(f,g\right)$ of $r$, we have $f=g$ and $f$ is monic.

Proof

The inclusion $g{f}^{o}=r\le {1}_{a}$ is mated to $g\le f$ which must be an identity $g=f$. If $\left(f,g\right)=\left(f,f\right)$ is jointly monic, then $f$ is monic.

Pretabularity and tabularity

Definition

An allegory is tabular if every morphism $r:a\to b$ admits a tabulation. A unital allegory is pretabular if for all $a,b$, the maximal morphism ${\epsilon }_{b}^{o}{\epsilon }_{a}\in \mathrm{hom}\left(a,b\right)$ (see the last sentence of the Units section) admits a tabulation.

It is immediate from corollary 4 that if $A$ is tabular, then $\mathrm{Map}\left(A\right)$ has pullbacks.

Likewise, it is immediate from the preceding corollary that if $A$ is unital and pretabular, then $\mathrm{Map}\left(A\right)$ has products, because we can form the pullback of the maps ${\epsilon }_{a}:a\to t$, ${\epsilon }_{b}:b\to t$ to the terminal object $t$.

Lemma

In a tabular allegory $A$, a map $q:a\to e$ is a strong epi in $\mathrm{Map}\left(A\right)$ if $q{q}^{o}={1}_{e}$.

Proof

If $q{q}^{o}={1}_{e}$, then it is first of all clear that $q$ is an epi in $\mathrm{Map}\left(A\right)$ because it retracts ${q}^{o}$ in $A$. We show $q$ is orthogonal to monomorphisms in $\mathrm{Map}\left(A\right)$. That is, consider a commutative diagram

$\begin{array}{ccc}a& \stackrel{q}{\to }& e\\ {}^{f}↓& & {↓}^{j}\\ b& \underset{i}{\to }& x\end{array}$\array{ a & \stackrel{q}{\to} & e \\ ^\mathllap{f} \downarrow & & \downarrow^\mathrlap{j} \\ b & \underset{i}{\to} & x }

where $i$ is monic. We wish to show there exists a filler map $g:e\to b$ such that $gq=f$ and $ig=j$. The uniqueness of a filler map is clear since $i$ is monic.

Put $g=f{q}^{o}$. We first check that $g$ is a map. Notice that the identity inclusion $if=jq$ is mated to an inclusion $f{q}^{o}\le {i}^{o}j$, so we have $g\le {i}^{o}j$. In that case we have

$g{g}^{o}\le {i}^{o}j{j}^{o}i\le {i}^{o}i\le {1}_{e}$g g^o \leq i^o j j^o i \leq i^o i \leq 1_e

where the last inclusion holds because $i$ is monic (corollary 5). This gives the counit for $gdashv{g}^{o}$. For the unit, use

${1}_{b}=q{q}^{o}\le q{f}^{o}f{q}^{o}={g}^{o}g.$1_b = q q^o \leq q f^o f q^o = g^o g.

So $g=f{q}^{o}$ is a map. We also have

$j=jq{q}^{o}=if{q}^{o}=ig,$j = j q q^o = i f q^o = i g,

and finally we have

$f\le f{q}^{o}q=gq$f \leq f q^o q = g q

so that $f=gq$ by lemma 3. This completes the proof.

Theorem

If $A$ is tabular, then $\mathrm{Map}\left(A\right)$ has equalizers. Moreover, every map has a (strong epi)-mono factorization, and strong epis are preserved by pullbacks. In short, $\mathrm{Map}\left(A\right)$ is a locally regular category. If $A$ is moreover unital, then $\mathrm{Map}\left(A\right)$ is regular.

Proof

The equalizer of a pair of maps $f,g:a\to b$ may be constructed as a tabulation of the coreflexive arrow $dom\left(f\wedge g\right)$. By lemma 8, the tabulation is of the form $\left(h,h\right)$ where $h$ is monic, and by an application of proposition 2, one sees it is the universal map that equalizes $f$ and $g$.

For any map $f:a\to b$, consider a tabulation of the coreflexive $dom\left({f}^{o}\right)=f{f}^{o}:b\to b$ by a pair of maps $\left(i,i\right)$. Notice that $i:e\to b$ is monic in $\mathrm{Map}\left(A\right)$, and $i{i}^{o}=f{f}^{o}$. By proposition 2, there exists a unique $q:a\to e$ such that $f=iq$. Following the proof of proposition 2, the map $q$ is constructed as ${i}^{o}f$. We have

${1}_{e}\le {i}^{o}i{i}^{o}i={i}^{o}f{f}^{o}i=q{q}^{o}$1_e \leq i^o i i^o i = i^o f f^o i = q q^o

i.e., $dom\left({q}^{o}\right)={1}_{e}$ (${q}^{o}$ is total). By lemma 9, this means $q$ is a strong epi in $\mathrm{Map}\left(A\right)$. Thus we have factored $f$ into a strong epi followed by a mono.

Now suppose $q:a\to e$ is any strong epi and $g:d\to e$ is a map, and that $\left(g\prime :p\to a,q\prime :p\to d\right)$ is a pullback of $\left(g,q\right)$. Then $\left(g\prime ,q\prime \right)$ is a tabulation of ${q}^{o}g$, so ${q}^{o}g=g\prime \left(q\prime {\right)}^{o}$. Now the left side of this equation is total, and therefore so is the right: ${1}_{e}\le dom\left(g\prime \left(q\prime {\right)}^{o}\right)$. But then

${1}_{e}\le dom\left(g\prime \left(q\prime {\right)}^{o}\right)\le dom\left(\left(q\prime {\right)}^{o}\right)$1_e \leq \dom(g' (q')^o) \leq \dom((q')^o)

where the second inequality uses corollary 1. This means $q\prime$ is strong epi, and we are done.

Revised on August 27, 2012 20:46:33 by Todd Trimble