Todd Trimble Theory of units and tabulations in allegories

Contents

Introduction
Preliminaries
Domains and coreflexives
Units
Tabulations in allegories

Preliminaries on tabulations
Pretabularity and tabularity

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

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

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

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

Domains and coreflexives

Definition

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

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

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

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 .

Corollary

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

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

Units

Definition

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

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 , 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

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)$ .

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

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 .

Proposition

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

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 . 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 ). Similarly $g j = k$ .

Corollary

Tabulations are unique up to unique isomorphism.

Proposition

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 .

Corollary

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 to finish.

Corollary

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

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

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

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 ). 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 . This completes the proof.

Theorem

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 , the tabulation is of the form $(h, h)$ where $h$ is monic, and by an application of proposition , 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 , there exists a unique $q \colon a \to e$ such that $f = i q$ . Following the proof of proposition , 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 , 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 . This means $q'$ is strong epi, and we are done.

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