Todd Trimble Theory of units and tabulations in allegories

Contents

1. Introduction
2. Preliminaries
3. Domains and coreflexives
4. Units
5. Tabulations in allegories

Preliminaries on tabulations
Pretabularity and tabularity

1. 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.

2. Preliminaries

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

An allegory is a $Pos$ -enriched $\dagger$ -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:

$r s \wedge t \leq r(s \wedge r^\dagger t)$
$r s \wedge t \leq (r \wedge t s^\dagger)s$

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

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

Lemma 2.1. For any $r \colon a \to b$ , we have $r \leq r r^o r$ .

Proof. We have $r \leq r 1_b \wedge r \leq r(1 \wedge r^o r) \leq r r^o r$ where the middle inequality uses the modular law. ▮

Recall that a map in an allegory is a morphism $f \colon a \to b$ such that $f \dashv f^o$ . A relation $r \colon a \to b$ is well-defined if we merely have a counit inclusion $r r^o \leq 1_b$ , and is total if we merely have a unit inclusion $1_a \leq r^o r$ . Clearly maps are closed under composition, as are total relations and well-defined relations.

Lemma 2.2. If $f \colon a \to b$ is a map, then for any $r, s \in \hom(b, c)$ we have $(r \wedge s)f = r f \wedge s f$ .

Proof. The non-trivial inclusion follows from

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 2.3. If $f, g \colon a \to b$ are maps and $f \leq g$ , then $f = g$ .

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

3. Domains and coreflexives

Definition 3.1. Let $r \colon a \to b$ be a morphism. We define the domain $\dom(r)$ to be $1_a \wedge r^o r$ . A morphism $e \colon a \to a$ is coreflexive if $e \leq 1_a$ ; in particular, domains are coreflexive. $Cor(a)$ denotes the poset of coreflexives in $\hom(a, a)$ .

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

Proof. We have $r \leq r r^o r \leq 1_a r^o 1_a \leq r^o$ where the first inequality is lemma 2.1. Of course also $r r \leq 1_a r = r$ . (If $r$ is symmetric and transitive, then $r \leq r r^o r = r r r \leq r r$ as well.) ▮

Lemma 3.3. For $r, s \in \hom(a, b)$ , we have $\dom(r \wedge s) = 1_a \wedge r^o s$ .

Proof. One inclusion is trivial:

\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:

\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 3.4. For $r \colon a \to b$ and coreflexives $c \in \hom(a, a)$ , we have $\dom(r) \leq c$ if and only if $r \leq r c$ . In particular, $r \leq r \circ \dom(r)$ .

Proof. If $1_a \wedge r^o r \leq c$ , then

r \leq r 1_a \wedge r \leq r(1_a \wedge r^o r) \leq r c.

If $r \leq r c$ , then

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 3.2. ▮

Corollary 3.5. For $r \colon a \to b$ and $s \colon b \to c$ , we have $\dom(s r) \leq \dom(r)$ .

By lemma 3.4, it suffices that $s r \leq s r \circ \dom(r)$ . But this follows from the last sentence of lemma 3.4. ▮

4. Units

Definition 4.1. An object $t$ is a unit in an allegory if $1_t$ is maximal in $\hom(t, t)$ and if for every object $a$ there is $f \colon a \to t$ such that $1_a \leq f^o f$ (i.e., $f$ is total).

Of course by maximality we also have $f f^o \leq 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 4.2. Let $t$ be a unit. Then $\dom \colon \hom(a, t) \to Cor(a)$ is an injective order-preserving function.

Proof. Order-preservation is clear. If $r, s \colon a \to t$ and $\dom(r) \leq \dom(s)$ , then $r \leq 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 3.4, and the last inequality follows from $r s^o \leq 1_t$ (since $1_t$ is maximal in $\hom(t, t)$ ). Therefore $\dom(r) = \dom(s)$ implies $r = s$ . ▮

Corollary 4.3. For a unit $t$ and any $a$ , there is at most one total relation = map $r \colon a \to t$ (because in that case $\dom(r) = 1_a$ , and we apply the previous proposition), and this is maximal in $\hom(a, t)$ . Thus $t$ is terminal in $Map(A)$ .

Let $\varepsilon_a \colon a \to t$ denote the maximal element of $\hom(a, t)$ . For any $r \colon a \to b$ , we then have $r \leq \varepsilon_b^o \varepsilon_a$ since this is mated to the inequality $\varepsilon_b r \leq \varepsilon_a$ . Therefore $\varepsilon_b^o \varepsilon_a$ is the maximal element of $\hom(a, b)$ .

5. Tabulations in allegories

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

Preliminaries on tabulations

Lemma 5.1. For maps $f \colon x \to a$ , $g \colon x \to b$ , the condition $f^o f \wedge g^o g = 1_x$ implies $(f, g)$ is a jointly monic pair in $Map(A)$ .

Proof. Let $h, h' \colon y \to x$ be maps, and suppose $f h = f h'$ and $g h = g h'$ . If $f^o f \wedge g^o g = 1_x$ , then

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.2. ▮

Proposition 5.2. Suppose $r: a \to b$ is tabulated by $(f \colon x \to a, g \colon x \to b)$ , and suppose $h \colon y \to a$ , $k \colon y \to b$ are maps. We have $k h^o \leq g f^o$ if and only if there exists a map $j \colon y \to x$ such that $h = f j$ and $k = g j$ (this $j$ is unique by lemma 5.1).

Proof. One direction is easy: if $h = f j$ and $k = g j$ for some map $j$ , then

k h^o = g j j^o f^o \leq g f^o.

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

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 3.3. We have $j j^o \leq 1_x$ from

(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 $f j \leq f(f^o h) \leq h$ , which implies $f j = h$ (lemma 2.3). Similarly $g j = k$ . ▮

Corollary 5.3. Tabulations are unique up to unique isomorphism.

Proposition 5.4. A diagram in $Map(A)$

\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 \leq g^o f$ .

Proof. An identity inclusion $g k = f h$ is certainly mated to an inclusion $k h^o \leq g^o f$ . Conversely, an inclusion $k h^o \leq g^o f$ is mated to $g k \leq f h$ , and we can use lemma 2.3. ▮

Corollary 5.5. Given $f \colon a \to c$ and $g \colon b \to c$ in $Map(A)$ , a tabulation $(h \colon p \to a, k \colon p \to b)$ of $r = g^o f$ provides a pullback of $(f, g)$ .

Proof. Indeed, by definition of tabulation we then have $k h^o = g^o f$ , so $g k = f h$ . For the universality of $(h, k)$ : if $g k' = f h'$ , then $k (h')^o \leq g^o f$ , and we can apply proposition 5.2 to finish. ▮

Corollary 5.6. If $i \colon a \to b$ is a monomorphism in $Map(A)$ 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 $(i, i)$ , but since this pullback is already $(1_a, 1_a)$ , the conclusion is clear. ▮

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

Proof. The inclusion $g f^o = r \leq 1_a$ is mated to $g \leq f$ which must be an identity $g = f$ . If $(f, g) = (f, f)$ is jointly monic, then $f$ is monic. ▮

Pretabularity and tabularity

Definition 5.8. An allegory is tabular if every morphism $r \colon a \to b$ admits a tabulation. A unital allegory is pretabular if for all $a, b$ , the maximal morphism $\varepsilon_b^o \varepsilon_a \in \hom(a, b)$ (see the last sentence of the Units section) admits a tabulation.

It is immediate from corollary 5.5 that if $A$ is tabular, then $Map(A)$ has pullbacks.

Likewise, it is immediate from the preceding corollary that if $A$ is unital and pretabular, then $Map(A)$ has products, because we can form the pullback of the maps $\varepsilon_a \colon a \to t$ , $\varepsilon_b \colon b \to t$ to the terminal object $t$ .

Lemma 5.9. In a tabular allegory $A$ , a map $q \colon a \to e$ is a strong epi in $Map(A)$ 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 $Map(A)$ because it retracts $q^o$ in $A$ . We show $q$ is orthogonal to monomorphisms in $Map(A)$ . That is, consider a commutative diagram

\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 \colon e \to b$ such that $g q = f$ and $i g = 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 $i f = j q$ is mated to an inclusion $f q^o \leq i^o j$ , so we have $g \leq i^o j$ . In that case we have

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.6). This gives the counit for $g \dash v g^o$ . For the unit, use

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 = j q q^o = i f q^o = i g,

and finally we have

f \leq f q^o q = g q

so that $f = g q$ by lemma 2.3. This completes the proof. ▮

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

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

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

1_e \leq i^o i i^o i = i^o f f^o i = q q^o

i.e., $\dom(q^o) = 1_e$ ( $q^o$ is total). By lemma 5.9, this means $q$ is a strong epi in $Map(A)$ . Thus we have factored $f$ into a strong epi followed by a mono.

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

1_e \leq \dom(g' (q')^o) \leq \dom((q')^o)

where the second inequality uses corollary 3.5. This means $q'$ is strong epi, and we are done. ▮

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