Regular Categories - Category Theory

7 Regular Categories

Definition 7.1 (Image, cover). We say a category $C$ has images if, for every $A \overset{f}{\to} B$ in $C$ , there exists a least $m : B^{'} ↣ B$ in $Sub (B)$ through which $f$ factors. We call $m$ the image of $f$ , and we say $f$ is a cover if its image is $1_{B}$ .

We write $A \overset{f}{⇾} B$ to indicate that $f$ is a cover.

Lemma 7.2. Any strong epimorphism is a cover. The converse holds if $C$ has equalisers and pullbacks.

Proof. If $f$ is strong epic, applying the definition to commutative squares of the form

shows that

f

is a cover.

For the converse, a cover $A \overset{f}{\to} B$ is epic since it can’t factor through the equaliser of any $B ⇉_{h}^{g} C$ with $g \neq h$ . To verify the other condition, suppose given

then the pullback of

m

along

h

is monic by Lemma 4.15, and

f

factors through it, so it’s an isomorphism. So we get

B \to C

by composing with the top edge of the pullback square. □

Here, if $C$ has images, image facorisation defines a functor $[2, C] \to [3, C]$ : given

if we form the image factorisations

we get a unique

I \to J

making both squares commute.

Definition 7.3 (Regular category). We say $C$ is regular if it has finite limits and images, and image factorisations are stable under pullback, i.e. if the left hand square above is a pullback then so are both right hand squares. (This is equivalent to saying that covers are stable under pullback).

Example 7.4.

(a) $S e t$ is regular and coregular: all monomorphisms and epimorphisms are strong, and so the two factorisations coincide and epimorphisms (respectively monomorphisms) are stable under pullback (respectively pushout).
(b) If $C$ is regular, so is any $[D, C]$ with images constructed pointwise (they’re stable under pushout since pullbacks are also constructed pointwise).
(c) If $C$ is regular, then so $C^{𝕋}$ for any monad $𝕋$ whose underlying functor $T$ preserves covers. If $f : (A, α) \to (B, β)$ is a morphism of $C^{𝕋}$ and $A ⇾ I ↣ B$ is the image factorisation of $f$ in $C$ , then in
we get a unique $ι$ making both squares commute, making $(I, ι)$ into a $𝕋$ -algebra, and it’s the image of $f$ in $C^{𝕋}$ .
In particular, any category monadic over $S e t$ is regular.
(d) If $C$ is a preorder, every morphism is its own image, and covers are isomorphisms. So $C$ is regular if and only if it has finite meets.
(e) $T o p$ has images and coimages: given $X \overset{f}{\to} Y$ , its image (respectively coimage) is its set-theoretic image topologised as a quotient of $X$ (respectively subspace of $Y$ ). $T o p$ isn’t regular, but it is coregular.

Proposition 7.5. Assuming that:

$C$ a regular

Then covers coincide with regular epimorphisms.

Proof.

$\Leftarrow$ Regular epimorphism implies strong epimorphism by Exercise 21˙4.
$\Rightarrow$ Suppose $A \overset{f}{⇾} B$ is a cover; let $R ⇉_{b}^{a} A$ be its kernel-pair, i.e. the pullback of
Suppose given $g : A \to C$ with $g a = g b$ ; form the image $A \overset{e}{⇾} \overset{(h, k)}{↣} B \times C$ of $A \overset{(f, g)}{\to} B \times C$ . We’ll show $h$ is an isomorphism, so that $k h^{- 1}$ is a factorisation of $g$ through $f$ . $h$ is a cover since $h e = f$ is, so we need to prove $h$ is monic.
Let $D ⇉_{m}^{l} I$ such that $h l = h m$ ; form the pullback
$e \times e$ factors as $A \times A \overset{1 \times e}{⇾} A \times I \overset{e \times 1}{⇾} I \times I$ , so $e \times e$ is a cover, and $p$ is a cover.

Now $f q = h e q = h l p = h m p = h e r = f r$ so $(q, r)$ factors through $(a, b)$ . But $(h, k) e a = (f, g) a = (f, g) b = (h, k) e b$ and $(h, k)$ is monic, so $e a = e b$ , so $e q = e r$ , i.e. $l p = m p$ . Also $p$ is epic, so $l = m$ . □

By a relation $A ↬ B$ in a category $C$ with finite products, we mean an isomorphism class of subobjects $R ↣ A \times B$ .

If $C$ has images, we define the composite of $A \overset{R}{↬} B \overset{S}{↬} C$ by forming the pullback

forming the image of

(a p, d q) : P \to A \times C

This is well-defined up to isomorphism and has the $A \overset{(1_{A}, 1_{A})}{↣} A \times A$ as $2$ -sided identities.

Lemma 7.6. Composition of relations in $C$ is associative if and only if $C$ is regular.

Proof.

$\Rightarrow$ Suppose given $A \overset{f}{\to} B \overset{e}{⇽} C$ . Consider the relations
Composing the right hand pair first, we get
and thus we get
Composing the left hand pair first, we begin by forming the pullback
and we endup with the image of $(p,!_{P}) : P \to A \times 1$ ; so $p$ must be a cover.
$\Leftarrow$ Suppose given relations $A \overset{R}{↬} B \overset{S}{↬} C \overset{T}{↬} D$ . If we form the pullbacks
then both $T \circ (S \circ R)$ and $(T \circ S) \circ R$ are the image of $U \to A \times D$ . □

We write $R e l (C)$ for the category whose objects are those of $C$ and whose morphisms are relations. Note that $R e l (S e t)$ is just $R e l$ as defined in Example 1.3(e).

We have a faithful functor $C \to R e l (C)$ which is the identity on objects and sends $A \overset{f}{\to} B$ to $A \overset{(1, f)}{↣} A \times B$ (for faithfulness, see Exercise 4.22(i)). We write $f_{∙}$ for $(1_{A}, f)$ .

Note that there’s an isomporphism $R e l (C) \to R e l (C^{o p})$ which is the identity on objects and sends $R \overset{(a, b)}{↣} A \times B$ to $R \overset{(b, a)}{↣} B \times A$ ; we denote this by $R^{\circ}$ , and write $f^{∙}$ for ${(f_{∙})}^{\circ}$ .

Also, $R e l (C)$ is enriched over $P o s e t$ (provided $R e l (C)$ is locally small, i.e. $C$ is well-powered), i.e. each $R e l (C) (A, B)$ has a partial order which is preserved by composition.

We say $A \overset{R}{↬} B$ is left adjoint to $B \overset{S}{↬} A$ if $1_{A} \leq S \circ R$ and $R \circ S \leq 1_{B}$ .

Proposition 7.7. $A \overset{R}{↬} B$ is a left adjoint in $R e l (C)$ if and only if it is of the form $f_{∙}$ .

Proof.

$\Leftarrow$ We show $(f_{∙} ⊣ f^{∙})$ : the composite $f^{∙} f_{∙}$ is just the kernel-pair $R \overset{(a, b)}{↣} A \times A$ of $f$ , and $A \overset{(1_{A}, 1_{A})}{↣} A \times A$ factors through it. Also $f_{∙} f^{∙}$ is the image of
so it contains $(1_{B}, 1_{B})$ .
$\Rightarrow$ Conversely, suppose $R \overset{(a, b)}{↣} A \times B$ has a right adjoint $R^{'} \overset{(b^{'}, a^{'})}{↣} B \times A$ . In forming $R^{'} \circ R$ , we take the pullback
So the image of $(a p, a^{'} p^{'})$ contains $A \overset{(1_{A}, 1_{A})}{\to} A \times A$ , so $a p$ factors as a cover followed by a split epimorphism, so $a$ is a cover.
Now, in the pullback
$q$ and $q^{'}$ are covers, but the image of $(b q, b^{'} q)$ is contained in $(1_{B}, 1_{B})$ so $b q = b^{'} q^{'}$ . But $a q = a^{'} q^{'}$ , so $R^{'} = R^{\circ}$ , $a = a^{'}$ , $b = b^{'}$ and $q = q^{'}$ . So $a$ is monic, and hence an isomorphism, so $R = (b a^{- 1})$ . □

P. Freyd developed a theory of allegories which have the structure of categories of relations and axiomatised those allegories $A$ for which the subcategory $A_{l a}$ is regular.

In a regular category $C$ , we say a relation $R : A ↬ A$ is reflexive if $𝟙_{A} \leq R$ , symmetric if $R^{\circ} = R$ , and transitive if $R \circ R \leq R$ . $R$ is an equivalence relation if it has all three properties. For any $A \overset{f}{\to} B$ in $C$ , the kernel-pair $R \overset{(a, b)}{\to} A \times A$ of $f$ is an equivalence relation. We say an equivalence relation $R$ is effective if it occurs as a kernel-pair, and $C$ is effective regular if all equivalence relations are effective.

$t f A b G p$ is regular but not effective regular: ${(m, n) \in ℤ \times ℤ | m \equiv n (m o d 2)}$ is a non-effective equivalence relation on $ℤ$ .

Note that an equivalence relation is idempotent in $R e l (C)$ , and if $A$ is an allegory and $E$ is a class of symmetric idempotents in $A$ then $A [\overset{ˇ}{E}]$ (as defined in Exercise 1.18) is an allegory; and if $A$ is $R e l (C)$ for a regular category $C$ , then:

Proposition 7.8. Assuming that:

$C$ a regular category
$E$ is the class of equivalence relations in $C$

Then

C_{eff} = {(R e l (C) [\overset{ˇ}{E}])}_{l a}

is effective regular, and the embedding

R e l (C) \to R e l (C) [\overset{ˇ}{E}]

restricts to a full and faithful regular functor

C \to C_{eff}

which is universal among regular functors

C \to D

where

D

is effective regular.

Note that if $C$ is effective regular, its equivalence relations are split idempotents in $R e l (C)$ : if $A \overset{R}{↬} A$ is the kernel-pair of $A \overset{f}{⇾} B$ then it splits as $f^{∙} f_{∙}$ (as we saw for $C = S e t$ in Exercise 1.19).

Definition 7.9 (Topos). A topos is a regular category $E$ for which the embedding $E \to R e l (E)$ sending $f$ to $f_{∙}$ has a right adjoint. We write the effect of the right adjoint on objects by $A \mapsto P A$ , and the unit $A \to P A$ as ${}_{A}$ , and the counit $P A ↬ A$ as $\exists_{A} ↣ P A \times A$ .

In $S e t$ , $P A$ is the power-set of $A$ , the unit is the mapping $a \mapsto {a}$ of Example 1.7(c), and $\exists_{A} = {(A^{'}, a) | a \in A^{'}} \subseteq P A \times A$ .

Note that (isomorphism classes of) subobjects of $A$ are in bijection with morphisms $1_{} \to P A$ . C. J. Mikkelses showed that any topos has finite colimits; we’ll give Bob Paré’s proof, which is much simpler.

Proposition 7.10. Assuming that:

$E$ a topos

Then there exists a monadic functor

E^{o p} \to E

. In particular,

E^{o p}

has finite colimits and if

E

has limits of shape

J

then it also has colimits of shape

J^{o p}

Proof. We make the assignment $A \mapsto P A$ into a functor $P : E \to E$ and a functor $P^{*} : E^{o p} \to E$ : given $f : A \to B$ , $P f : P A \to P B$ corresponds to the image of $\exists_{A} ↣ P A \times A \overset{1_{} \times f}{\to} P A \times B$ , and $P^{*} f$ corresponds to the pullback of

Given

C \overset{g}{\to} P A

corresponding to

R ↣ C \times A

(P f) g

corresponds to the image of

R ↣ C \times A \overset{1_{} \times f}{\to} C \times B

and similarly given

S ↣ D \times B

, composing with

P^{*} f

corresponds to pulling back along

D \times A \overset{1_{} \times f}{\to} D \times B

Given a pullback square

E

commutes, since both ways correspond to the image of the left vertical composite in

where both squares are pullbacks.

Now, as in Example 5.14(d), we have that if $E \overset{e}{\to} A ⇉_{g}^{f} B$ is a coreflexive in $E$ , then

is a split coequaliser coequaliser in

E

. Also,

P^{*}

is self-adjoint on the right, and it reflects isomorphisms by Exercise 7.17(v). The second assertion follows from Proposition 5.8(i). □

Definition 7.11 (Support, totally supported, capital).

(a)
By the support of an object $A$ in a regular category, we mean the image of $A \to 1$ . We say $A$ is well-supported if $A \to 1$ is a cover.
(b)
We say a regular category $C$ is totally supported if every object is well-supported. We say $C$ is almost totally supported if every object is either well-supported or a strict initial object, where we cann an object $0$ strict if every $A \to 0$ is an isomorphism. (Given finite limits, a strict object is initial since for any $A$ there exists $0 \overset{π^{- 1}}{\to} 0 \times A \overset{π_{2}}{\to} A$ , and the equaliser of any pair $0 ⇉_{}^{} A$ is $a$ ).
(c)
We say a regular category $C$ is capital if its terminal object $1$ is a detector, i.e. $C (1, ∙)$ reflects isomorphisms.

Example. $G p$ and $A b G p$ are totally-supported since their terminal objects are initial. $S e t$ is almost totally-supported and capital. Note that capital implies almost totally-supported since if $A$ isn’t well-supported there are no morphisms $1 \to A$ .

A representable functor $C (A, ∙)$ always preserves limits, so it’s a regular functor if and only if $A$ is cover-projective (c.f. Definition 2.10).

Lemma 7.12. Assuming that:

$C$ a locally small capital regular category

Then

1

is cover-projective.

Proof. Since covers are stable under pullback, we need to show that every $A ⇾ 1$ is split epic. If $A ≅ 1$ , nothing to prove. If not, the projections $A \times A ⇉_{}^{} A$ aren’t equal (since their coequaliser is $A ⇾ 1$ , by Proposition 7.5). So there exists $1 \to A \times A$ not factoring through their equaliser, so there exists $1 \to A \times A \to A$ . □

If $C$ is regular, the full subcategory $C_{ws}$ of well-supported objects is closed under finite products since

is a pullback, and under pullbacks of covers since if

A ⇾ B

then

A

and

B

have the same support.

We write $C_{tv}$ for the category obtained from $C_{ws}$ by adjoining a strict initial object $0$ : this is regular and almost totally-supported and the functor $C \to C_{tv}$ sending all non-well-supported objects to $0$ is regular (c.f. Exercise 5.19).

Lemma 7.13. Assuming that:

$C$ a small almost totally-supported regular category

Then there exists an isomorphism-reflecting regular functor

I : C \to C^{'}

, where

C^{'}

is also small and almost totally-supported, such that for every well-supported

A \in ob C

there exists a morphism

1 \to I A

C^{'}

not factoring through

I (m)

for any proper subobject

m : A^{'} ↣ A

C

Proof. Recall from Exercise 7.17: $C$ regular implies $C ∕ A$ regular for any $A$ , and for any $f : A \to B$ in $C$ pullback along $f$ defines a regular functor $f^{*} : C ∕ B \to C ∕ A$ , which has a left adjoint $Σ_{f} : C ∕ A \to C ∕ B$ sending $g : C \to A$ to $f g$ . And $f^{*}$ reflects isomorphisms if and only if $f$ is a cover.

We’ll define $C^{'}$ as ${(\hat{C})}_{tv}$ where $\hat{C}$ is easier to describe.

To satisfy the desired conclusion for a single well-supported object $A$ , enough to take ${(!)}_{A}^{*} : C ≅ C ∕ 1 \to C ∕ A$ , since ${(!_{A})}^{*} A = (A \times A \overset{π_{2}}{\to} A)$ acquires a point $Δ : (A \overset{1}{\to} A) \to (A \times A \to A)$ not factoring through $(A^{'} \times A \to A)$ for any proper $A ↣ A$ .

More generally, for any finite list $A_{1}, \dots, A_{n}$ of well-supported objects, we can take $C ∕ \prod_{i = 1}^{n} A_{i}$ .

We define a base to be a finite list $\vec{A} = (A_{1}, \dots, A_{n})$ of distinct well-supported objecs of $C$ . We preorder the set $B$ of bases by $\vec{A} \leq \vec{B}$ if $\vec{B}$ contains all the members of $\vec{A}$ . We write $\prod \vec{A}$ for the product $\prod_{i = 1}^{n} A_{i}$ and if $\vec{A} \leq \vec{B}$ we write $π_{\vec{B}, \vec{A}}$ for the product projection $\prod \vec{B} \to \prod \vec{A}$ . This makes $\vec{A} \mapsto \prod \vec{A}$ into a functor $B^{o p} \to C$ .

Hence the assignment $\vec{A} \to C ∕ \prod \vec{A}$ , $π_{\vec{B}, \vec{A}} \mapsto π_{\vec{B}, \vec{A}}^{*}$ is ‘almost’ a functor $B \to C a t$ .

We now define $\hat{C}$ : its objects are pairs $(\vec{B}, f)$ where $\vec{B}$ is a base and $f : A \to \prod \vec{B}$ is an object of $C ∕ \prod \vec{B}$ . Morphisms $(\vec{B}, f) \to ({\vec{B}}^{'}, f^{'})$ are represented by pairs $(\vec{C}, g)$ where $\vec{C}$ is a base containing $\vec{B}$ and ${\vec{B}}^{'}$ and $g : π^{*} f \to {π^{'}}^{*} f^{'}$ in $C ∕ \prod \vec{C}$ , subject to the relation which identifies $(\vec{C}, g)$ with $({\vec{C}}^{'}, g^{'})$ if $\vec{C} \leq {\vec{C}}^{'}$ and the pullback of $g$ to $C ∕ \prod \vec{C}$ is isomorphic to $g^{'}$ .

Clearly, each $C ∕ \prod \vec{B}$ sits inside $\hat{C}$ as a non-full subcategory; so in particular $C ≅ C ∕ \prod []$ is a subcategory of $\hat{C}$ , $\hat{C}$ is regular, and the inclusions $C ∕ \prod \vec{B} \to \hat{C}$ are isomorphism-reflecting regular functors.

Given a finite diagram in $\hat{C}$ , we can choose $\vec{B}$ such that all edges of the diagram appear as morphisms in $C ∕ \prod \vec{B}$ , and take the limit there, and this is a limit in $\hat{C}$ . Similarly for images.

Also, if a morphism $f$ becomes an isomorphism in $\hat{C}$ , its inverse must live $C ∕ \prod \vec{B}$ for some $\vec{B}$ , hence $f$ is an isomorphism $C ∕ \prod \vec{B}$ .

We define $C^{'} = {(\hat{C})}_{tv}$ : the induced functor $C \to \hat{C} \to C^{'}$ is still isomorphism reflecting since $C$ is almost totally-supported. □

Lemma 7.14. Assuming that:

$C$ a small regular and almost totally-supported category

Then there exists an isomorphism reflecting regular functor

C \to \hat{C}

where

\hat{C}

is capital, small and regular. Hence in particular, there is an isomorphism-reflecting regular functor

C \to S e t

Proof. Consider the sequence

C = C_{0} \to C_{1} \to C_{2} \to \dots,

where each $C_{n + 1}$ is obtained from $C_{n}$ by the construction of Lemma 7.13.

We define $\hat{C}$ to be the pseudo-colimit of this sequence: objects are pairs $(n, A)$ where $A \in ob C_{n}$ , and morphisms $(n, A) \to (m, B)$ are represented by pairs $(p, f)$ where $p \geq \max {m, n}$ and $F : I A \to I^{'} B$ in $C_{p}$ , modulo the identification of $(p, f)$ with $(p^{'}, f^{'})$ if $p \leq p^{'}$ and $f^{'} = I f$ .

The proof that $C$ is regular, and that the embeddings $C_{n} \to \hat{C}$ are isomorphism-reflecting regular functors, is as in Lemma 7.13.

Given any non-invertible monomorphism $A^{'} ↣ A$ in $\hat{C}$ , it lives in $C_{n}$ for some $n$ , so there exists $1 \to A$ in $C_{n + 1}$ not factoring through $A^{'} ↣ A$ .

But if $A \overset{f}{\to} B$ isn’t monic in $\hat{C}$ , the legs $R ⇉_{b}^{a} A$ of its kernel-pair aren’t equal, so there exists $1 \overset{r}{\to} R$ not factoring through their equation, so $1 ⇉_{b r}^{a r} A$ are distinct but have the same composite with $f$ .

So $\hat{C} (1, ∙)$ reflects monomorphisms and hence reflects isomorphisms. □

Theorem 7.15. Assuming that:

$C$ small and regular

Then there exists a set

I

and an isomorphism-reflecting regular functor

C \to {S e t}^{I}

Proof. Let $I$ be a representative set of subobjects of $1$ in $C$ , and for each $U \in I$ consider the composite

C \overset{{(!_{U})}^{*}}{\to} C ∕ U \to {(C ∕ U)}_{tv} \to \hat{{(C ∕ U)}_{tv}} \to S e t,

where the third factor is the functor of Lemma 7.14 and the fourth is represented by $1$ .

Given any non-invertible morphism $A \overset{f}{\to} B$ in $C$ , if $U$ is the support of $B$ then ${(!)}_{H}^{*} f$ remains non-invertible in $C ∕ U$ and its codomain is well-supported there, so it remains non-invertible in ${(C ∕ U)}_{tv}$ and hence in $S e t$ .

So these functors collectively reflect isomorphisms. □

Remark 7.16.

(a) Barr’s original embedding theorem produces a full and faithful regular functor $C \to [D, S e t]$ for some small category $D$ . Moreover if $C$ is almost totally-supported we can take $D$ to be a monoid.
(b) Theorem 7.15 yields a ‘meta theorem’ saying that ‘anything we can prove in $S e t$ is true in all regular categories’.
For example to prove Proposition 7.5 (cover implies regular epic), given a cover $A \overset{f}{⇾} B$ in a regular category $C$ , and a $A \overset{g}{\to} C$ having equal composites with the kernel-pair $R ⇉_{}^{} A$ of $f$ , we can cut down to a small subcategory $C^{'}$ containing $f$ and $g$ and closed under finite limits and images, and then show that the first component of $I \overset{(h, k)}{↣} A \times C$ becomes an isomorphism in ${S e t}^{I}$ .
(c) Abelian categories are regular categories enriched over $A b G p$ (i.e. for any two objects $A$ and $B$ , $A (A, B)$ has an abelian group structure and composition distributes over addition).
Abelian categories are totally-supported since their terminal objects are initial, so for any small abelian $A$ we get an isomorphism-reflecting regular functor $A \to S e t$ and hence an isomorphism-reflecting functor $A ≅ A b G p (A) \to A b G p (S e t) = A b G p$ .