Todd Trimble Theory of units and tabulations in allegories

Redirected from "torsion-free abelian group".
Note: torsion subgroup and torsion-free module both redirect for "torsion-free abelian group".

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