18B10, 18A32, 18E08<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Quotients of Span Categories That Are Allegories
and the representation of regular categories

S.N. Hosseini  A.R. Shir Ali Nasab  W. Tholen  L. Yeganeh  Mathematics
Department
Shahid Bahonar University of Kerman
Kerman, Iran

Department of Mathematics and Statistics
York University, Toronto, Canada

###### Abstract

We consider the ordinary category $\mathsf{Span}(\mathcal{C})$ of (isomorphism
classes of) spans of morphisms in a category $\mathcal{C}$ with finite limits
as needed, composed horizontally via pullback, and give a general criterion
for a quotient of $\mathsf{Span}(\mathcal{C})$ to be an allegory. In
particular, when $\mathcal{C}$ carries a pullback-stable, but not necessarily
proper, $(\mathcal{E},\mathcal{M})$-factorization system, we establish a
quotient category $\mathsf{Span}_{\mathcal{E}}(\mathcal{C})$ that is
isomorphic to the category $\mathsf{Rel}_{\mathcal{M}}(\mathcal{C})$ of
$\mathcal{M}$-relations in $\mathcal{C}$, and show that it is a (unitary and
tabular) allegory precisely when $\mathcal{M}$ is a class of monomorphisms in
$\mathcal{C}$. Without this restriction, one can still find a least pullback-
stable and composition-closed class $\mathcal{E}_{\bullet}$ containing
$\mathcal{E}$ such that $\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$
is a unitary and tabular allegory. In this way one obtains a left adjoint to
the 2-functor that assigns to every unitary and tabular allegory the regular
category of its Lawverian maps. With the Freyd-Scedrov Representation Theorem
for regular categories, we conclude that every finitely complete category with
a stable factorization system has a reflection into the huge 2-category of all
regular categories.

###### keywords:

span category, relation, stable system, regular category, (unitary, tabular)
allegory, representation of allegories.

Acknowledgements: The second author’s research was in part supported by a
grant from IPM. The third author acknowledges support under the Discovery
Grants Program by the National Sciences and Engineering Council of Canada

##  1 Introduction

By identifying vertically isomorphic morphisms (= 1-cells) in Benabou’s
bicategory $\mathcal{S}\emph{pan}(\mathcal{C})$ of spans of morphisms in a
category $\mathcal{C}$ with pullbacks (see [Bénabou 1967], [Borceux 1994]) one
obtains the (ordinary) category

$\mathsf{Span}(\mathcal{C}),$

in which spans get composed horizontally via pullback in $\mathcal{C}$. If
$\mathcal{C}$ is regular, so that $\mathcal{C}$ has also binary products and a
stable (regular epi, mono)-factorization system, one may similarly form the
category

$\mathsf{Rel}(\mathcal{C})$

of sets and relations (= isomorphism classes of monic spans) in $\mathcal{C}$,
with the horizontal composite of a composable pair of relations obtained as a
regular image of their span composite. This category inherits from the
bicategory $\mathcal{S}\emph{pan}(\mathcal{C})$ the structure of a (strict)
2-category, with 2-cells given by order; actually, $\mathsf{Rel}(\mathcal{C})$
is the prototypical example of a (unitary and tabular) allegory: see [Freyd,
Scedrov 1990], [Johnstone 2002].

More generally, as done in [Pavlović 1995] (with predecessors of this work
presented under more restrictive conditions in [Klein 1970] and [Meisen 1974],
and with a weakening of the pullback-stability constraint given in
[Jayewardene, Wyler 1996]), without any epi- or mono restrictions one may
consider an arbitrary stable factorization system $(\mathcal{E},\mathcal{M})$
of a category $\mathcal{C}$ with binary products and pullbacks and form the
category

${\mathsf{Rel}}_{\mathcal{M}}(\mathcal{C}).$

Its morphisms are represented by those spans $(A\longleftarrow
R\longrightarrow B)$ whose induced morphism $R\longrightarrow A\times B$ lies
in $\mathcal{M}$. In this paper we take a fresh look at this category, by
treating it as a quotient category of $\mathsf{Span}(\mathcal{C})$. In fact,
for any pullback-stable class $\mathcal{E}$ of morphisms in $\mathcal{C}$ that
contains all isomorphisms and is closed under composition, we describe a
compatible equivalence relation $\sim_{\mathcal{E}}$ on
$\mathsf{Span}(\mathcal{C})$ which renders its quotient category

$\mathsf{Span}_{\mathcal{E}}(\mathcal{C})$

isomorphic to $\mathsf{Rel}_{\mathcal{M}}(\mathcal{C})$ when $\mathcal{M}$ is
a factorization partner of $\mathcal{E}$; see Theorem 2.4.

Folklore knowledge says that ${\mathsf{Rel}}_{\mathcal{M}}(\mathcal{C})$ is
still an allegory, provided that $\mathcal{M}$ is a class of monomorphisms in
$\mathcal{C}$; indeed, in Section 4 of this paper we give a novel proof of
this fact. In [Milius 2000] it was shown that the provision
$\mathcal{M}\subseteq\ \mathrm{Mono}(\mathcal{C})$ is essential for obtaining
an allegory; for example; the stable factorization system (bijective on
objects, fully faithful) of the ordinary category ${\sf Cat}$ of small
categories, ${\sf Rel}_{\\{\mathrm{fully\,faithful}\\}}({\sf Cat})$ fails to
be an allegory. In Theorem 4.10 we will actually show that the provision
$\mathcal{M}\subseteq{\mathrm{Mono}}(\mathcal{C})$ is also necessary for ${\sf
Rel}_{\mathcal{M}}(\mathcal{C})$ to form an allegory.

This last result is a consequence of our answer to the more general question
suggested by the title of the paper: When does a compatible equivalence
relation $\sim$ on $\mathsf{Span}(\mathcal{C})$ make its quotient category an
allegory? The necessary and sufficient condition given in Theorem 3.8 may in
particular be exploited in the case that $\sim$ is the relation
$\sim_{\mathcal{E}}$ induced by a stable morphism class $\mathcal{E}$ as above
(Theorem 4.3), which then leads to the aforementioned Theorem 4.10 whenever
$\mathcal{E}$ belongs to a stable factorization system
$(\mathcal{E},\mathcal{M})$ of $\mathcal{C}$.

Somewhat surprisingly, in the presence of a stable factorization system
$(\mathcal{E},\mathcal{M})$ with
$\mathcal{M}\subseteq{\mathrm{Mono}}(\mathcal{C})$, the allegory
$\mathsf{Span}_{\mathcal{E}}(\mathcal{C})$ is (in the terminology of [Freyd,
Scedrov 1990]) already unitary and tabular (Corollary 5.15). This important
addendum follows with the help of the principal result of the paper: Given any
stable factorization system $(\mathcal{E},\mathcal{M})$ in a finitely complete
category $\mathcal{C}$, there is a least stable and composition-closed class
$\mathcal{E}_{\bullet}$ containing $\mathcal{E}$ that makes
$\mathsf{Span}_{{\mathcal{E}}_{\bullet}}(\mathcal{C})$ a unitary tabular
allegory (Theorem 5.13).

The global significance of this result is outlined in Section 6, where we set
up the huge 2-categories of unitary tabular allegories on one hand, and of
finitely complete categories equipped with a stable factorization system on
the other hand. We then show that the construction of Theorem 5.13 gives us a
left adjoint to the 2-functor

$\mathsf{Map}:\mathfrak{UTabAll}\longrightarrow\mathfrak{StabFact},$

which assigns to a unitary tabular allegory its category of (Lawverian) maps,
equipped with its stable factorization system that makes it a regular
category. With the Freyd-Scedrov Representation Theorem [Freyd, Scedrov 1990,
2.154], which lets us present $\mathfrak{UTabAll}$ as 2-equivalent to the full
subcategory $\mathfrak{RegCat}$ of $\mathfrak{StabFact}$, given by all regular
categories, we see that every finitely complete category with a stable
factorization system allows for a reflection into $\mathfrak{RegCat}$.

##  2 Categories of relations as quotients of the span category

Throughout this paper, we let $\mathcal{C}$ be a category with binary products
and pullbacks.

For objects $A,B$ in $\mathcal{C}$, a span $(f,g)$ in $\mathcal{C}$ with
domain $A$ and codomain $B$ is given by a pair of morphisms

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
6.75pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{A}$}}}}}}}{\hbox{\kern 30.75pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.92395pt\raise 6.1111pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 6.75002pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
52.39445pt\raise 5.1875pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.8264pt\hbox{$\scriptstyle{g}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 69.30695pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
69.30695pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{B}$}}}}}}}\ignorespaces}}}}\ignorespaces\;.$

These are the objects of the category
$\mathcal{S}\emph{pan}(\mathcal{C})(A,B)$ whose morphisms
$u:(f,g)\longrightarrow(\tilde{f},\tilde{g})$ are given by
$\mathcal{C}$-morphisms $u$ with $\tilde{f}u=f$ and $\tilde{g}u=g$, to be
composed vertically as in $\mathcal{C}$.

$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{u}$$\scriptstyle{g}$$\textstyle{A}$$\textstyle{B}$$\textstyle{\tilde{D}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tilde{f}}$$\scriptstyle{\tilde{g}}$

$\mathcal{S}\emph{pan}(\mathcal{C})$ becomes a bicategory when one composes
the spans $(f,g):A\longrightarrow B$ and $(h,k):B\longrightarrow C$
horizontally via (a tacitly chosen) pullback in the usual fashion, as shown by

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h^{\prime}}$$\scriptstyle{g^{\prime}}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{\rm{pb}}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$$\textstyle{A}$$\textstyle{B}$$\textstyle{C}$

that is:

$(h,k)\circ(f,g):=(fh^{\prime},kg^{\prime}).$

In this paper we are mostly interested in the quotient categories of the
ordinary category

$\sf{Span}(\mathcal{C})$

whose objects are those of $\mathcal{C}$, and whose morphisms are (vertical)
isomorphism classes of spans in $\mathcal{C}$, with their horizontal
composition. For simplicity, we denote the (vertical) isomorphism class of
$(f,g)$ again by $(f,g)$. The category $\sf{Span}(\mathcal{C})$ comes with the
involution

$(f,g)^{\circ}=(g,f),$

making it a self-dual category.

For a class $\mathcal{E}$ of morphisms in $\mathcal{C}$ we define:

######  Definition 2.1.

(1) The class $\mathcal{E}$ is a stable system in $\mathcal{C}$ if it contains
the isomorphisms of $\mathcal{C}$ and is closed under composition and stable
under pullback in $\mathcal{C}$.

(2) For the stable system $\mathcal{E}$ in $\mathcal{C}$ and spans
$(f,g),(\tilde{f},\tilde{g}):A\to B$, using the vertical structure of the
bicategory $\mathcal{S}\text{pan}(\mathcal{C})$, we define the relation
$\leq_{\mathcal{E}}$ by

$(f,g)\leq_{\mathcal{E}}(\tilde{f},\tilde{g})\iff\exists\,x\in\mathcal{E}\;(x:(f,g)\to(\tilde{f},\tilde{g})\;\emph{in}\;\mathcal{S}pan(\mathcal{C})).$

(3) Since the stable system $\mathcal{E}$ contains the isomorphisms of
$\mathcal{C}$ and is closed under composition, $\leq_{\mathcal{E}}$ is
reflexive and transitive. The least equivalence relation on ${\sf
Span}(\mathcal{C})$ containing $\leq_{\mathcal{E}}$ is denoted by
$\sim_{\mathcal{E}}$; it is described by $\leq_{\mathcal{E}}$-zigzags:

$(f,g)\sim_{\mathcal{E}}(\tilde{f},\tilde{g})\iff\exists\;s\geq
1,(f_{0},g_{0}),...,(f_{s},g_{s}):$
$(f,g)=(f_{0},g_{0})\leq_{\mathcal{E}}(f_{1},g_{1})\geq_{\mathcal{E}}(f_{2},g_{2})\leq_{\mathcal{E}}...\geq_{\mathcal{E}}(f_{s},g_{s})=(\tilde{f},\tilde{g}).$

We denote the $\sim_{\mathcal{E}}$-equivalence classes of $(f,g)$ by
$[f,g]_{\mathcal{E}}$. (Note that, according to our notational convention
above, for $[f,g]_{\mathrm{Iso}(\mathcal{C})}$ we write just $(f,g)$.) The
horizontal composition of two classes
$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[f,g]_{\mathcal{E}}}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[h,k]_{\mathcal{E}}}$$\textstyle{C}$
is defined by the horizontal composition of their representatives:

$[h,k]_{\mathcal{E}}\circ[f,g]_{\mathcal{E}}:=[(h,k)\circ(f,g)]_{\mathcal{E}}=[fh^{\prime},kg^{\prime}]_{\mathcal{E}}.$

To make sure that the quotient category

${\sf Span}_{\mathcal{E}}(\mathcal{C}):={\sf
Span}(\mathcal{C})/\sim_{\mathcal{E}}$

is well defined, we have to show:

######  Proposition 2.2.

For a stable system $\mathcal{E}$ in $\mathcal{C}$, the equivalence relation
$\sim_{\mathcal{E}}$ is compatible with the (horizontal) composition of
morphisms in ${\sf Span}(\mathcal{C})$.

######  Proof 2.3.

Since we have the isomorphism $(-)^{\circ}$, we only need to show that, for
$(f,g),(m,n):A\to B$ and $(h,k):B\to C$, one has the implication

$(f,g)\sim_{\mathcal{E}}(m,n)\Longrightarrow(h,k)\circ(f,g)\sim_{\mathcal{E}}(h,k)\circ(m,n).$

In fact, it is sufficient to show this implication when $\sim_{\mathcal{E}}$
is replaced by $\leq_{\mathcal{E}}$. Hence, we just show:

$(f,g)\leq_{\mathcal{E}}(\tilde{f},\tilde{g}):A\to B,\;(h,k):B\to
C\Longrightarrow(h,k)\circ(f,g)\leq_{\mathcal{E}}(h,k)\circ(\tilde{f},\tilde{g}).$

To this end, with $x:(f,g)\to(\tilde{f},\tilde{g})$ for $x\in\mathcal{E}$, and
with $(h^{\prime},g^{\prime})={\rm pb}(g,h)$ as above and
$(\tilde{h}^{\prime},\tilde{g}^{\prime})={\rm pb}(\tilde{g},h)$, one obtains a
unique morphism $x^{\prime}$ making the diagram

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{x^{\prime}}$$\scriptstyle{h^{\prime}}$$\scriptstyle{g^{\prime}}$$\textstyle{\tilde{P}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tilde{g}^{\prime}}$$\scriptstyle{\tilde{h}^{\prime}}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{x}$$\scriptstyle{g}$$\textstyle{\tilde{D}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tilde{g}}$$\textstyle{B}$

commute. With the outer rectangle and the right square being pullback
diagrams, so is the left square. Hence, as a pullback of $x$, also
$x^{\prime}$ lies in $\mathcal{E}$, which shows
$(h,k)\circ(f,g)\leq_{\mathcal{E}}(h,k)\circ(\tilde{f},\tilde{g})$.

If the morphism class $\mathcal{E}$ belongs to a (pullback-)stable
factorization system $(\mathcal{E},\mathcal{M})$ in $C$, then $\mathcal{E}$ is
certainly a stable system, and we may construct the quotient category ${\sf
Span}_{\mathcal{E}}(\mathcal{C})$. On the other hand, granted the existence of
binary products in $\mathcal{C}$, still without assuming that $\mathcal{M}$ be
a class of monomorphisms in $C$, we may also form the category

$\sf{Rel}_{\mathcal{M}}(\mathcal{C})$

of $\mathcal{M}$-relations in $\mathcal{C}$ (see [Milius 2000]); its objects
are the objects of $\mathcal{C}$, and a morphism $(f,g):A\rightarrow B$ is
(the isomorphism class of) a span in $\mathcal{C}$ such that $\langle
f,g\rangle:D\rightarrow A\times B$ lies in $\mathcal{M}$; its composite with
$(h,k):B\rightarrow C$ in $\sf{Rel}_{\mathcal{M}}(\mathcal{C})$ is defined by

$(h,k)\cdot(f,g):=(p_{1}m,p_{2}m),$

where $m$ is the $\mathcal{M}$-part of the
$(\mathcal{E},\mathcal{M})$-factorization of $\langle
fh^{\prime},kg^{\prime}\rangle:P\rightarrow A\times C$, with $p_{1},p_{2}$
denoting the projections of the product $A\times C$.

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h^{\prime}}$$\scriptstyle{g^{\prime}}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{pb}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$$\textstyle{A}$$\textstyle{B}$$\textstyle{C}$

We note that, for a span $(f,g)$ with the decomposition $\langle
f,g\rangle=me$ where $m\in\mathcal{M}$ and $e\in\mathcal{E}$, one clearly has
$[f,g]_{\mathcal{E}}=[\pi_{1}m,\pi_{2}m]_{\mathcal{E}}$, where $\pi_{1}$ and
$\pi_{2}$ are the projections of $A\times B$.

######  Theorem 2.4.

For a stable factorization system $(\mathcal{E},\mathcal{M})$ in a finitely
complete category $\mathcal{C}$, the categories

$\sf{Rel}_{\mathcal{M}}(\mathcal{C})\cong\sf{Span}_{\mathcal{E}}(\mathcal{C})$

are isomorphic. If $\mathcal{C}$ is a regular category, with
$\mathcal{E}=\mathrm{RegEpi}(\mathcal{C})$,
$\mathcal{M}=\mathrm{Mono}(\mathcal{C})$ and
$\sf{Rel}(\mathcal{C})=\sf{Rel}_{\mathcal{M}}(\mathcal{C})$, one has in
particular

$\sf{Rel}(\mathcal{C})\cong\sf{Span}_{\mathcal{E}}(\mathcal{C}).$

######  Proof 2.5.

For every $\mathcal{M}$-relation $(f,g):A\to B$ one has the induced
$\sim_{\mathcal{E}}$-equivalence class $S(f,g)=[f,g]_{\mathcal{E}}$ of the
span $(f,g)$. With the note above the Theorem it follows immediately that one
obtains a functor
$S:\sf{Rel}_{\mathcal{M}}(\mathcal{C})\longrightarrow\sf{Span}_{\mathcal{E}}(\mathcal{C})$
which maps objects identically.

Conversely we show that taking $[f,g]_{\mathcal{E}}:A\rightarrow B$ to the
$\mathcal{M}$-relation $R[f,g]_{\mathcal{E}}=(\pi_{1}m,\pi_{2}m):A\rightarrow
B$, with $m$ the $\mathcal{M}$-part of $\langle f,g\rangle$, defines a functor
$R:\sf{Span}_{\mathcal{E}}(\mathcal{C})\longrightarrow\sf{Rel}_{\mathcal{M}}(\mathcal{C})$.
Indeed, to show that $R$ is well-defined, we suppose that
$(f,g)\leq_{\mathcal{E}}(h,k)$, so that $he=f$ and $ke=g$ for some
$e\in\mathcal{E}$. This means $\langle f,g\rangle=\langle h,k\rangle e$, which
implies that the $\mathcal{M}$-part of $\langle f,g\rangle$ is isomorphic to
the $\mathcal{M}$-part of $\langle h,k\rangle$.

To show that $R$ preserves the composition, let
$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[f,g]_{\mathcal{E}}}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[h,k]_{\mathcal{E}}}$$\textstyle{C}$
be a pair of morphisms in $\sf{Span}_{\mathcal{E}}(\mathcal{C})$ and $\langle
f,g\rangle=me$ and $\langle h,k\rangle=m^{\prime}e^{\prime}$ for
$e,e^{\prime}\in\mathcal{E}$ and $m,m^{\prime}\in\mathcal{M}$. In the
following diagram, $f_{1},g_{1},h_{1},k_{1}$ are defined to make the bottom
triangles with the product projections $\pi_{1},\pi_{2},p_{1},p_{2}$ commute,
and $g^{\prime},h^{\prime},g_{1}^{\prime},h_{1}^{\prime}$ are such that
$gh^{\prime}=hg^{\prime}$ and $g_{1}h_{1}^{\prime}=h_{1}g_{1}^{\prime}$ become
pullback squares.

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h^{\prime}}$$\scriptstyle{g^{\prime}}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{e}$$\scriptstyle{g}$$\textstyle{Q\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h_{1}^{\prime}}$$\scriptstyle{g_{1}^{\prime}}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{e^{\prime}}$$\scriptstyle{k}$$\scriptstyle{m}$$\scriptstyle{f_{1}}$$\scriptstyle{g_{1}}$$\scriptstyle{m^{\prime}}$$\scriptstyle{h_{1}}$$\scriptstyle{k_{1}}$$\textstyle{A}$$\textstyle{A\times
B\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{2}}$$\textstyle{B}$$\textstyle{B\times
C\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{1}}$$\scriptstyle{p_{2}}$$\textstyle{C}$

Let $\textstyle{A}$$\textstyle{A\times
C\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q_{1}}$$\scriptstyle{q_{2}}$$\textstyle{C}$
be product projections and $n$ be the $\mathcal{M}$-part of the morphism
$\langle f_{1}h_{1}^{\prime},k_{1}g_{1}^{\prime}\rangle:Q\rightarrow A\times
C$. Then we have

$[h,k]_{\mathcal{E}}\circ[f,g]_{\mathcal{E}}=[h_{1},k_{1}]_{\mathcal{E}}\circ[f_{1},g_{1}]_{\mathcal{E}}=[f_{1}h^{\prime}_{1},k_{1}g^{\prime}_{1}]_{\mathcal{E}}=[q_{1}n,q_{2}n]_{\mathcal{E}},$

and the functoriality of $R$ may be seen easily now:

$R([h,k]_{\mathcal{E}}\circ[f,g]_{\mathcal{E}})=R[q_{1}n,q_{2}n]_{\mathcal{E}}=(q_{1}n,q_{2}n)=(h_{1},k_{1})\cdot(f_{1},g_{1})=R[h,k]_{\mathcal{E}}\cdot
R[f,g]_{\mathcal{E}}.$

The identities $RS=\mathrm{Id}$ and $SR=\mathrm{Id}$ follow directly from the
definitions of $S$ and $R$.

##  3 Allegories arising as quotients of span categories

Recall that an allegory [Freyd, Scedrov 1990] is a category $\mathcal{A}$ such
that

  * •

$\mathcal{A}$ is poset-enriched, so that each hom-set carries a partial order
which is preserved by the composition $\cdot$ of $\mathcal{A}$;

  * •

$\mathcal{A}$ carries an involution $(-)^{\circ}:\mathcal{A}^{\rm
op}\to\mathcal{A}$, i.e., a contravariant self-inverse functor;

  * •

binary infima exist in each hom-set, and the involution preserves them;

  * •

Freyd’s modular law holds in $\mathcal{A}$:

$(s\cdot r)\wedge t\leq s\cdot(r\wedge(s^{\circ}\cdot t)),$

for all $r:A\to B,\,s:B\to C,\,t:A\to C$ in $\mathcal{A}$.

Of the various derived rules valid in an allegory, we will use in particular
the special modular law:

$r\leq r\cdot r^{\circ}\cdot r$

for all morphisms $r$ in $\mathcal{A}$ (see [Freyd, Scedrov 1990, 2.112]);
indeed, with Freyd’s modular law, one has

$r\leq(r\cdot 1)\wedge r\leq r\cdot(1\wedge(r^{\circ}\cdot r))\leq
r\cdot(r^{\circ}\cdot r).$

As mentioned in the Introduction, the standard example of an allegory is the
category ${\sf Rel}(\mathcal{C})$ for a regular category $\mathcal{C}$, and
this fact may be generalized to the case of a stable factorization system
$(\mathcal{E},\mathcal{M})$ in $\mathcal{C}$, provided that $\mathcal{M}$ is a
class of monomorphisms in $\mathcal{C}$; indeed, Corollary 4.5 provides a
novel proof that ${\sf Rel}_{\mathcal{M}}(\mathcal{C})$ is an allegory under
this provision. In Theorem 4.10 we prove that the provision
$\mathcal{M}\subseteq{\rm{Mono}}(\mathcal{C})$ is actually necessary for ${\sf
Rel}_{\mathcal{M}}(\mathcal{C})$ being an allegory.

Since, in the presence of a stable factorization system, ${\sf
Rel}_{\mathcal{M}}(\mathcal{C})$ has been presented as a quotient of ${\sf
Span}(\mathcal{C})$ (see Theorem 2.4), without any reference to such a system
it is natural to ask what it takes for an equivalence relation $\sim$ on ${\sf
Span}(\mathcal{C})$ to make the quotient category with its horizontal
composition an allegory.

To answer this question, we first recall that one trivially has the involution

${\sf Span}(\mathcal{C})^{\rm op}\to{\sf
Span}(\mathcal{C}),\;(f,g)\mapsto(f,g)^{\circ}=(g,f).$

Next, the hom-sets of ${\sf Span}(\mathcal{C})$ inherit from the local
categories of the bicategory $\mathcal{S}\emph{pan}(\mathcal{C})$ a (up to
isomorphism) commutative and associative operation which, by the isomorphism

$\mathcal{S}\emph{pan}(\mathcal{C})(A,B)\cong\mathcal{C}/A\times B$

for all objects $A,B$ in $\mathcal{C}$, is given by the direct product in the
comma category on the right. Denoting the direct product in
$\mathcal{C}/A\times B$ of (the induced arrows to $A\times B$ of) spans
$(f,g),(p,q):A\to B$ by $(f,g)\wedge(p,q)$, we observe that it is constructed
by pullback in $\mathcal{C}$, as

$(f,g)\wedge(p,q)=(\pi_{1}d,\pi_{2}d),\quad{\rm with}\quad d=\langle
f,g\rangle\rho_{1}=\langle p,q\rangle\rho_{2},$

where $\rho_{1},\rho_{2}$ are pullback projections and $\pi_{1},\pi_{2}$ are
product projections in $\mathcal{C}$.

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\rho_{1}}$$\scriptstyle{\rho_{2}}$$\scriptstyle{d}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{\langle
f,g\rangle}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
p,q\rangle}$$\scriptstyle{q}$$\textstyle{A}$$\textstyle{A\times
B\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{2}}$$\textstyle{B}$
(1)

As an operation on the hom-sets of ${\sf Span}(\mathcal{C})$, $\wedge$ is
(strictly) commutative and associative; furthermore, $(\pi_{1},\pi_{2})$ is
neutral in ${\sf Span}(\mathcal{C})(A,B)$ with respect to $\wedge$. More
importantly, the diagram above shows immediately that $(f,g)\wedge(p,q)$ may
be presented as a horizontal composite, as in formula (1) of the following
proposition, which also lists three further important observations.

######  Proposition 3.1.

For all spans $(f,g),(p,q):A\to B,\;(h,k):B\to C,\;(m,n):A\to C$ one has:

  * (1)

$(f,g)\wedge(p,q)=(\langle p,q\rangle,q)\circ(f,\langle f,g\rangle)$ (meet via
composition);

  * (2)

$(f,f)\wedge(1_{A},1_{A})=(f,f)$ (meet neutrality of identity morphisms);

  * (3)

there is a canonical 2-cell

$d:(h,k)\circ((f,g)\wedge(p,q))\longrightarrow((h,k)\circ(f,g))\wedge((h,k)\circ(p,q))$

in $\mathcal{S}\text{pan}(\mathcal{C})$, witnessing the lax distributivity of
the composition over meet;

  * (4)

there is a canonical 2-cell

$c:((h,k)\circ(f,g))\wedge(m,n)\longrightarrow(h,k)\circ((f,g)\wedge((h,k)^{\circ}\circ(m,n)))$

in $\mathcal{S}\text{pan}(\mathcal{C})$, which we call the Freyd modularity
morphism of the given spans.

######  Proof 3.2.

Formula (1) follows from the above diagram, and (2) follows easily from the
definition. For proving (3), we let the composites $(h,k)\circ(f,g)$ and
$(h,k)\circ(p,q)$ be constructed by the pullback squares of the diagrams

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h^{\prime}}$$\scriptstyle{g^{\prime}}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\scriptstyle{f}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$$\textstyle{A}$$\textstyle{B}$$\textstyle{C}$
$\textstyle{Q\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q^{\prime}}$$\scriptstyle{h^{\prime\prime}}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{q}$$\scriptstyle{p}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$$\textstyle{A}$$\textstyle{B}$$\textstyle{C}$

and the meets $(f,g)\wedge(p,q)$ and
$((h,k)\circ(f,g))\wedge((h,k)\circ(p,q)))$ by the pullback diagrams

$\textstyle{U\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{u_{1}}$$\scriptstyle{u_{2}}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
f,g\rangle}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
p,q\rangle}$$\textstyle{A\times B}$
$\textstyle{V\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{v_{2}}$$\scriptstyle{v_{1}}$$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
fh^{\prime},kg^{\prime}\rangle}$$\textstyle{Q\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
ph^{\prime\prime},kq^{\prime}\rangle}$$\textstyle{A\times C}$

With the composite $(h,k)\circ((f,g)\wedge(p,q))$ given by

$\textstyle{W\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{w_{1}}$$\scriptstyle{w_{2}}$$\textstyle{U\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{gu_{1}=qu_{2}}$$\scriptstyle{fu_{1}=pu_{2}}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$$\textstyle{A}$$\textstyle{B}$$\textstyle{C}$

one first obtains the morphisms $x:W\to P,\;y:W\to Q$, uniquely determined by
$h^{\prime}x=u_{1}w_{1},\,g^{\prime}x=w_{2},\,h^{\prime\prime}y=u_{2}w_{1},\,q^{\prime}y=w_{2}$,
and then the unique morphism $d:W\to V$ with $v_{1}d=x,\,v_{2}d=y$. One
readily checks that $d$ is the desired 2-cell of spans.

For showing (4), we let the composites $(h,k)\circ(f,g)$ and
$(h,k)^{\circ}\circ(m,n)$ be constructed by the pullback squares of the
diagrams

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h^{\prime}}$$\scriptstyle{g^{\prime}}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\scriptstyle{f}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$$\textstyle{A}$$\textstyle{B}$$\textstyle{C}$
$\textstyle{Q\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{n^{\prime}}$$\scriptstyle{k^{\prime}}$$\textstyle{G\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{n}$$\scriptstyle{m}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{k}$$\scriptstyle{h}$$\textstyle{A}$$\textstyle{C}$$\textstyle{B}$

and the meets $((h,k)\circ(f,g))\wedge(m,n)$ and
$(f,g)\wedge((h,k)^{\circ}\circ(m,n))$ by the pullback diagrams

$\textstyle{S\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{s_{1}}$$\scriptstyle{s_{2}}$$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
fh^{\prime},kg^{\prime}\rangle}$$\textstyle{G\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
m,n\rangle}$$\textstyle{A\times C}$
$\textstyle{T\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{t_{2}}$$\scriptstyle{t_{1}}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
f,g\rangle}$$\textstyle{Q\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
mk^{\prime},hn^{\prime}\rangle}$$\textstyle{A\times B}$

One readily verifies that there is a unique morphism $a:S\to Q$ satisfying
$k^{\prime}a=s_{2},\,n^{\prime}a=g^{\prime}s_{1}$, and then a unique morphism
$b:S\to T$ with $t_{1}b=h^{\prime}s_{1},\,t_{2}b=a$. With the diagram

$\textstyle{R\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r_{1}}$$\scriptstyle{r_{2}}$$\textstyle{T\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{gt_{1}}$$\scriptstyle{ft_{1}}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$$\textstyle{A}$$\textstyle{B}$$\textstyle{C}$

displaying the span $(h,k)\circ((f,g)\wedge((h,k)^{\circ}\circ(m,n)))$, we
finally obtain the unique morphism $c:S\to R$ in $\mathcal{C}$ with
$r_{1}c=b,\,r_{2}c=n^{\prime}a$. The identities
$(ft_{1}r_{1})c=ft_{1}b=fh^{\prime}s$ and
$(kr_{2})c=kn^{\prime}a=kg^{\prime}s_{1}=ns_{2}$ show that $c$ is in fact the
desired 2-cell of spans.

We will return to items (2–4) of Proposition 3.1 only in Theorem 3.8. Item (1)
helps us to first specify the properties of an equivalence relation for spans
which will enable us to form a quotient category that inherits the operations
$(-)^{\circ}$ and $\wedge$, as follows.

######  Definition 3.3.

Let $\sim$ be a relation for spans in $\mathcal{C}$ such that only spans with
the same domain and codomain may be related, and that vertically isomorphic
spans are always related (so that $\sim$ is reflexive for the isomorphism
classes of spans). We call $\sim$

  * •

inv(olution)-compatible if $(f,g)\sim(\tilde{f},\tilde{g})$ implies
$(g,f)\sim(\tilde{g},\tilde{f})$;

  * •

comp(osition)-compatible if $(f,g)\sim(\tilde{f},\tilde{g})$ implies
$(h,k)\circ(f,g)\sim(h,k)\circ(\tilde{f},\tilde{g})$;

  * •

meet-compatible if $(f,g)\sim(\tilde{f},\tilde{g})$ implies $(f,\langle
f,g\rangle)\sim(\tilde{f},\langle\tilde{f},\tilde{g}\rangle)$,

whenever $(f,g),(\tilde{f},\tilde{g}):A\to B,\,(h,k):B\to C$. If $\sim$ enjoys
all three properties, we will simply say that $\sim$ is compatible.

When $\sim$ is inv-compatible, it is easy to see that then $\sim$ is

  * •

comp-compatible if, and only if, $(h,k)\sim(\tilde{h},\tilde{k})$ implies
$(h,k)\circ(f,g)\sim(\tilde{h},\tilde{k})\circ(f,g),$

and when $\sim$ is inv- and comp-compatible, then $\sim$ is

  * •

meet-compatible if, and only if, $(f,g)\sim(\tilde{f},\tilde{g})$ implies
$(\langle f,g\rangle,g)\sim(\langle\tilde{f},\tilde{g}\rangle,\tilde{g})$.

For the last claim, exploit the defining property for
$(g,f)\sim(\tilde{g},\tilde{f})$ and observe that one has $(g,\langle
f,g\rangle)=(1_{B\times A},t)\circ(g,\langle g,f\rangle)$, with the “twist”
morphism $t:B\times A\to A\times B$.

It is a routine exercise, and a fact used frequently in this paper, that each
of the three compatibility properties is inherited from the given relation by
the least equivalence relation generated by it.

For a compatible equivalence relation $\sim$ for spans in $\mathcal{C}$, we
denote the $\sim$-equivalence class of $(f,g)$ by $[f,g]_{\sim}$, or just by
$[f,g]$ when the context makes it clear which relation $\sim$ we are referring
to. We can now define

  * •

$[f,g]^{\circ}:=[g,f]$;

  * •

$[h,k]\circ[f,g]:=[(h,k)\circ(f,g)]$;

  * •

$[f,g]\wedge[p,q]:=[(f,g)\wedge(p,q)]$.

One can easily verify that the above operations are well-defined for
$\sim$-equivalence classes. Writing

$\sf{Span}_{\sim}(\mathcal{C})$

for the resulting quotient category with its horizontal composition, we can
now summarize our observations, as follows:

######  Proposition 3.4.

For a compatible equivalence relation $\sim$ for spans in $\mathcal{C}$, the
quotient category $\sf{Span}_{\sim}(\mathcal{C})$ carries an involution
$(-)^{\circ}:\sf{Span}_{\sim}(\mathcal{C})^{\rm
op}\to\sf{Span}_{\sim}(\mathcal{C})$ and a commutative, associative binary
operation $\wedge$ that is preserved by the involution. The two operations are
determined by the property that the projection functor ${\sf
Span}(\mathcal{C})\to{\sf Span}_{\sim}(\mathcal{C})$ becomes a homomorphism
with respect to them.

We can now narrow down the question posed at the beginning of this section and
ask, under which condition on a compatible equivalence relation $\sim$ the
quotient category ${\sf Span}_{\sim}(\mathcal{C})$ may become an allegory when
equipped with the involution and the meet operation as described by the
proposition. For the meet operation to induce a partial order on the hom-sets
one needs the idempotency law $[f,g]\wedge[f,g]=[f,g]$ to hold in ${\sf
Span}_{\sim}(\mathcal{C})$. The following definition describes an easy
sufficient condition for that law to hold, which will turn out to be necessary
as well.

######  Definition 3.5.

We call a relation $\sim$ for $\mathcal{C}$-spans allegorical if

$(1_{A},f)\sim(f,f)\circ(1_{A},f)$

for all morphisms $f:A\to B$ in $\mathcal{C}$. If $\sim$ is inv-compatible,
this condition is equivalent to

$(f,1_{A})\sim(f,1_{A})\circ(f,f)$

for all morphisms $f$. Note that, with the graph functor

$\Gamma:\mathcal{C}\to{\sf Span}(\mathcal{C}),\;(f:A\to
B)\longmapsto((1_{A},f):A\to B),$

these conditions may also be written as $\Gamma f\sim\Gamma f\circ(\Gamma
f)^{\circ}\circ\Gamma f$ or $(\Gamma f)^{\circ}\sim(\Gamma
f)^{\circ}\circ\Gamma f\circ(\Gamma f)^{\circ},$ simply because every span
$(f,g)$ may be written as

$(f,g)=\Gamma g\circ(\Gamma f)^{\circ}.$

The following lemma is fundamental for our further investigations:

######  Lemma 3.6.

Let the relation $\sim$ for $\mathcal{C}$-spans be inv- and comp-compatible
and allegorical. If there exists a 2-cell $u:(f,g)\to(p,q)$ in
$\mathcal{S}\text{pan}(\mathcal{C})$, then

$(f,g)\wedge(p,q)\sim(f,g).$

In particular, for all spans $(f,g)$ one has $(f,g)\wedge(f,g)\sim(f,g)$.

######  Proof 3.7.

Putting $r=\langle f,g\rangle:D\to A\times B,\;s=\langle p,q\rangle:E\to
A\times B$, so that $su=r$, and denoting by $\pi_{2}:A\times B\to B$ the
product projection, under the assumptions on $\sim$ we obtain

$\displaystyle(f,g)\wedge(p,q)$ $\displaystyle=(s,q)\circ(f,r)$
$\displaystyle=(1_{A\times B},\pi_{2})\circ(s,s)\circ(1_{E},s)\circ(f,u)$
$\displaystyle\sim(1_{A\times B},\pi_{2})\circ(1_{E},s)\circ(f,u)$
$\displaystyle=(1_{E},q)\circ(f,u)$ $\displaystyle=(f,g).$

With Proposition 3.1, our Lemma 3.6 facilitates the proof of the following
theorem.

######  Theorem 3.8.

For a compatible equivalence relation $\sim$ for spans, the operations
$(-)^{\circ}$ and $\wedge$ of Proposition 3.4 make ${\sf
Span}_{\sim}(\mathcal{C})$ an allegory if, and only if, $\sim$ is allegorical.

######  Proof 3.9.

Suppose first that ${\sf Span}_{\sim}(\mathcal{C})$ is an allegory, with the
operations as described. Hence, its hom-sets carry the partial order induced
by $\wedge$, that is:

$(\ast)\qquad\qquad[f,g]\leq[m,n]\Longleftrightarrow[f,g]\wedge[m,n]=[f,g].$

By first applying the special modular law and then Proposition 3.1(2) we
obtain for all $f:A\to B$ in $\mathcal{C}$ the inequalities

$\displaystyle[1_{A},f]$
$\displaystyle\leq[1_{A},f]\circ[1_{A},f]^{\circ}\circ[1_{A},f]$
$\displaystyle=[f,f]\circ[1_{A},f]$
$\displaystyle=([f,f]\wedge[1_{B},1_{B}])\circ[1_{A},f]$
$\displaystyle\leq[1_{B},1_{B}]\circ[1_{A},f]$ $\displaystyle=[1_{A},f].$

Consequently, $(1_{A},f)\sim(f,f)\circ(1_{A},f)$, as desired.

Conversely, assuming $\sim$ to be allegorical, by Proposition 3.4 and Lemma
3.6, ${\sf Span}_{\sim}(\mathcal{C})$ carries the involution $(-)^{\circ}$ and
the operation $\wedge$ which induces a partial order on the hom-sets, as in
$(\ast)$ above. Furthermore, from Proposition 3.1(3) and Lemma 3.6 one obtains

$[h,k]\circ([f,g]\wedge[p,q])\leq([h,k]\circ[f,g])\wedge([h,k]\circ[p,q]),$

which renders the composition of ${\sf Span}_{\sim}(\mathcal{C})$ monotone.
Likewise, Proposition 3.1(4) and Lemma 3.6 show that Freyd’s modular law holds
in ${\sf Span}_{\sim}(\mathcal{C})$.

The existence of a 2-cell $u:(f,g)\to(p,q)$ as in Lemma 3.6 describes the
natural preorder for spans, seen as the objects of the local categories of the
bicategory $\mathcal{S}\text{pan}(\mathcal{C})$. Considering their reflection
onto posets produces the largest allegorical quotient of ${\sf
Span}(\mathcal{C})$, as follows:

######  Corollary 3.10.

There is a least compatible and allegorical equivalence relation $\approx$ on
${\sf Span}(\mathcal{C})$, described by

$(f,g)\approx(p,q)\Longleftrightarrow\exists\,u,v\;(u:(f,g)\to(p,q),\;v:(p,q)\to(f,g)).$

Consequently, for every compatible and allegorical relation $\sim$ on ${\sf
Span}(\mathcal{C})$, one has a projection functor

${\sf Span}_{\approx}(\mathcal{C})\to{\sf
Span}_{\sim}(\mathcal{C}),\,[f,g]_{\approx}\mapsto[f,g]_{\sim},$

which maps objects identically and is a morphism of allegories, i.e., it
preserves the involution and the binary meet.

######  Proof 3.11.

One routinely shows that, when defining the relation $\approx$ as described,
one obtains a compatible and allegorical equivalence relation. Considering any
compatible and allegorical equivalence relation $\sim$, with Lemma 3.6 one
obtains immediately the implication

$(f,g)\approx(p,q)\Longrightarrow(f,g)\sim(p,q),$

which confirms the first claim. The second claim is an obvious consequence of
the first one.

##  4 Allegories arising from stable systems

As an easy exercise one shows that for every stable system $\mathcal{E}$ in
$\mathcal{C}$ the equivalence relation $\sim_{\mathcal{E}}$ of Definition
2.1(1) is compatible. The next step is to consider the question under which
conditions $\sim_{\mathcal{E}}$ will be allegorical. To this end, we first
give a simplified description of the relation $\sim_{\mathcal{E}}$, as
follows.

######  Lemma 4.1.

For a stable system $\mathcal{E}$ in $\mathcal{C}$, one has
$(f,g)\sim_{\mathcal{E}}(h,k)$ if, and only if, there are $x,y\in\mathcal{E}$
such that the following diagram commutes.

$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{A}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{x}$$\scriptstyle{y}$$\textstyle{B}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$
(2)

######  Proof 4.2.

The sufficiency of the condition is trivial. Its necessity follows from the
fact that every sequence $(f,g)\leq_{\mathcal{E}}(p,q)\geq_{\mathcal{E}}(h,k)$
may be replaced by a sequence
$(f,g)\geq_{\mathcal{E}}(p^{\prime},q^{\prime})\leq_{\mathcal{E}}(h,k)$.
Indeed, the first sequence yields the commutative diagram

$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{z}$$\textstyle{A}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p}$$\scriptstyle{q}$$\textstyle{B}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\scriptstyle{k}$$\scriptstyle{z^{\prime}}$
(3)

with $z,z^{\prime}\in\mathcal{E}$. Then, by setting $(x,y)={\rm
pb}(z,z^{\prime})$, we have $x,y\in\mathcal{E}$ and, with $p^{\prime}=fx$ and
$q^{\prime}=gx$, obtain a sequence of the second type.

Calling a split epimorphism (= retraction) $r$ in $\mathcal{C}$ effective if
there exists a morphism $r^{\prime}$ such that $(r,r^{\prime})$ is a kernel
pair in $\mathcal{C}$, we are ready to state a criterion that answers the
question we stated above.

######  Theorem 4.3.

For a stable system $\mathcal{E}$ in $\mathcal{C}$, the equivalence relation
$\sim_{\mathcal{E}}$ is allegorical if, and only if, for every effective
retraction $r$, there is a morphism $z\in\mathcal{E}$ such that
$rz\in\mathcal{E}$.

######  Proof 4.4.

Let $\sim_{\mathcal{E}}$ be allegorical and $r$ be an effective retraction;
then there exist morphisms $r^{\prime},f$ such that $(r,r^{\prime})$ is a
kernel pair of $f$. Since by hypothesis
$(1,f)\sim_{\mathcal{E}}(f,f)\circ(1,f)=(r,fr^{\prime})$, by Lemma 4.1 there
are morphisms $z,z^{\prime}\in\mathcal{E}$ such that $z^{\prime}=rz$ and
$fz^{\prime}=fr^{\prime}z$. In particular, $rz\in\mathcal{E}$, as desired.

Conversely, given any morphism $f:A\to B$ in $\mathcal{C}$ with kernel pair
$(r,r^{\prime})$, the split epimorphism $r$ is effective. Then, by hypothesis,
there exists a morphism $z\in\mathcal{E}$ with $rz\in\mathcal{E}$. Looking at
the trivially commuting diagram

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1}$$\scriptstyle{f}$$\textstyle{A}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{rz}$$\scriptstyle{z}$$\textstyle{B}$$\textstyle{K\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r}$$\scriptstyle{fr^{\prime}}$
(4)

we conclude $(1,f)\sim_{\mathcal{E}}(f,f)\circ(1,f)$. This means that
$\sim_{\mathcal{E}}$ is allegorical.

######  Corollary 4.5.

For a stable system $\mathcal{E}$ in a category $\mathcal{C}$ containing all
split epimorphisms, the equivalence relation $\sim_{\mathcal{E}}$ is
allegorical, making the category ${\sf Span}_{\mathcal{E}}(\mathcal{C})$ an
allegory.

######  Proof 4.6.

Under the condition $\mathrm{SplitEpi}(\mathcal{C})\subseteq\mathcal{E}$, for
every effective retraction $r$ one has $1\in\mathcal{E}$ and
$r1=r\in\mathcal{E}$, so that $\sim_{\mathcal{E}}$ is allegorical by Theorem
4.3, making the quotient category an allegory, by Theorem 3.8.

######  Remark 4.7.

The converse statement of Corollary 4.5 manifestly fails. In fact, in any
category $\mathcal{C}$ with pullbacks that contains some split epimorphism
that is not an isomorphism, one can find a stable system $\mathcal{E}$ not
containing all split epimorphisms, for which $\sim_{\mathcal{E}}$ is
nevertheless allegorical: just consider the class $\mathcal{E}$ of all
monomorphisms in $\mathcal{C}$ ! Indeed, $\mathcal{E}$ is trivially a stable
system that, by hypothesis, cannot contain all split epimorphism; but since
any section $s$ of a given retraction $r$ trivially belongs to $\mathcal{E}$,
as well as $rs=1$, the relation $\sim_{\mathcal{E}}$ is allegorical.

However, the condition of Corollary 4.5 does become necessary for
$\sim_{\mathcal{E}}$ to be allegorical whenever $\mathcal{E}$ belongs to a
stable factorization system $(\mathcal{E},\mathcal{M})$ in $\mathcal{C}$, as
we show in the next theorem. For that it is useful to recall a well-known
equivalent formulation of the condition that all retractions must lie in
$\mathcal{E}$; we provide a proof of the equivalence since resorting to the
standard source for it (the dual of Proposition 14.11 in [Adamek, Herrlich,
Strecker 2004]) would ask us to unnecessarily assume the existence of binary
coproducts in $\mathcal{C}$.

######  Lemma 4.8.

For any factorization system $(\mathcal{E},\mathcal{M})$ in a category
$\mathcal{D}$ with kernel pairs, one has the equivalence

$\mathrm{SplitEpi}(\mathcal{D})\subseteq\mathcal{E}\iff\mathcal{M}\subseteq\mathrm{Mono}(\mathcal{D}).$

######  Proof 4.9.

$\Longrightarrow$: For the kernel pair $(m_{1},m_{2})$ of a morphism
$m\in\mathcal{M}$, the projection $m_{1}$ is in $\mathcal{M}$ as a pullback of
$m$, but as a retraction also in $\mathcal{E}$, by hypothesis. Consequently,
$m_{1}$ is an isomorphism, which makes $m$ monic.

$\Longleftarrow$: For any retraction $r$, considering its factorization $r=me$
with $m\in\mathcal{M}$ and $e\in\mathcal{E}$, we see that also $m$ is a
retraction, in addition to being monic by hypothesis. Hence, the morphism $m$,
now shown to be an isomorphism, makes $r=me$ lie in $\mathcal{E}$.

######  Theorem 4.10.

For every stable factorization system $(\mathcal{E},\mathcal{M})$ of
$\mathcal{C}$, the relation $\sim_{\mathcal{E}}$ is allegorical if, and only
if, every morphism in $\mathcal{M}$ is a monomorphism in $\mathcal{C}$;
equivalently, if every retraction in $\mathcal{C}$ lies in $\mathcal{E}$.

######  Proof 4.11.

By Corollary 4.5 and Lemma 4.8, only the necessity of the condition
$\mathcal{M}\subseteq\mathrm{Mono}(\mathcal{C})$ still needs to be proved. But
when $\sim_{\mathcal{E}}$ is allegorical, for every $m\in\mathcal{M}$ one has
$(1,m)\sim_{\mathcal{E}}(m,m)\circ(1,m)$, so that with Lemma 4.1 one obtains
morphisms $x,y$ in $\mathcal{E}$ making the diagram

$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1}$$\scriptstyle{m}$$\textstyle{\cdot}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{x}$$\scriptstyle{y}$$\textstyle{\cdot}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{m_{1}}$$\scriptstyle{mm_{2}}$
(5)

commute, where $(m_{1},m_{2})$ is a kernel pair for $m$. Since both,
$m_{1}y=x$ and $y$ lie in $\mathcal{E}$, also $m_{1}$ does. But $m_{1}$
already belongs to $\mathcal{M}$ as a pullback of $m$ and is therefore an
isomorphism. Consequently, $m$ is a monomorphism.

So, with Theorems 2.4 and 4.10 we obtain:

######  Corollary 4.12.

For a category $\mathcal{C}$ with a stable factorization system
$(\mathcal{E},\mathcal{M})$, the category ${\sf
Span}_{\mathcal{E}}(\mathcal{C})\cong\sf{Rel}_{\mathcal{M}}(\mathcal{C})$ is
an allegory if, and only if,
$\mathrm{SplitEpi}(\mathcal{C})\subseteq\mathcal{E}$; equivalently, if
$\mathcal{M}\subseteq\mathrm{Mono}(\mathcal{C})$.

######  Definition 4.13.

For every stable system $\mathcal{E}$ in $\mathcal{C}$, we denote by
$\mathcal{E}_{\circ}$ the least stable system that contains both $\mathcal{E}$
and $\mathrm{SplitEpi}(\mathcal{C})$. Since these classes are both stable
under pullback, $\mathcal{E}_{\circ}$ is just the closure of the class
$\mathcal{E}\cup\mathrm{SplitEpi}(\mathcal{C})$ under composition in
$\mathcal{C}$:

$\mathcal{E}_{\circ}=(\mathcal{E}\cup\mathrm{SplitEpi}(\mathcal{C}))^{\mathrm{c}}.$

With Corollary 4.5, Lemma 4.8 and Theorem 2.4 we conclude:

######  Corollary 4.14.

For every stable system $\mathcal{E}$ in $\mathcal{C}$, the category
$\mathsf{Span}_{\mathcal{E}_{\circ}}(\mathcal{C})$ is an allegory, and when
$\mathcal{E}$ belongs to a stable factorization system
$(\mathcal{E},\mathcal{M})$ of $\mathcal{C}$, it may be presented as a
quotient category of $\mathsf{Rel}_{\mathcal{M}}(\mathcal{C})$, via

$\sf{Rel}_{\mathcal{M}}(\mathcal{C})\longrightarrow\sf{Span}_{\mathcal{E}_{\circ}}(\mathcal{C}),\;(f,g)\longmapsto[f,g]_{\sim_{\mathcal{E}_{\circ}}}.$

When $\mathcal{M}$ is a class of monomorphisms, then
$\mathcal{E}_{\circ}=\mathcal{E}$, and this functor is an isomorphism.

##  5 Unitary tabular allegories arising from stable factorization systems

In this section, for a compatible equivalence relation $\sim$ on
$\mathcal{C}$, we explore the question when the quotient category ${\sf
Span}_{\sim}(\mathcal{C})$ is an allegory that is even unitary and tabular in
the sense of [Freyd, Scedrov 1990]. We give a complete answer in the case when
$\sim$ is induced by a stable system $\mathcal{E}$ in $\mathcal{C}$. Let us
first recall that, in an allegory $\mathcal{A}$,

  * •

a morphism $r$ is called a map if $1\leq r^{\circ}\cdot r$ and $r\cdot
r^{\circ}\leq 1$; the maps in $\mathcal{A}$ are the morphisms of the
subcategory

$\mathsf{Map}(\mathcal{A})$

of $\mathcal{A}$, which has the same class of objects as $\mathcal{A}$;

  * •

a pair $(f,g)$ of maps tabulates a morphism $r$ if $r=g\cdot f^{\circ}$ and
$(f^{\circ}\cdot f)\wedge(g^{\circ}\cdot g)=1$; in this case $r$ is called
tabular; the allegory $\mathcal{A}$ is tabular if all of its morphisms are;

  * •

an object $E$ in $\mathcal{A}$ is a partial unit if $1_{E}$ is the maximum in
$\mathcal{A}(E,E)$; if, in addition, for every object $A$ there is a morphism
$r:A\to E$ such that $1_{A}\leq r^{\circ}\cdot r$, then $E$ is said to be a
unit; $\mathcal{A}$ is unitary if it has a unit.

In order to establish some necessary conditions, we first consider a
compatible and allegorical equivalence relation on $\mathcal{C}$ and start off
by affirming that a morphism of $\mathcal{C}$ becomes a map once transferred
to the $\sim$ \- equivalence class of its graph (Definition 3.5), by the
functor

$\Gamma_{\sim}:\mathcal{C}\longrightarrow\sf{Span}_{\sim}(\mathcal{C}),\quad
f\longmapsto[1,f]_{\sim}.$

######  Lemma 5.1.

For every morphism $f:A\to B$ in $\mathcal{C}$, $[1_{A},f]_{\sim}$ is a map in
the allegory $\sf{Span}_{\sim}(\mathcal{C})$.

######  Proof 5.2.

Writing $[-,-]$ for $[-,-]_{\sim}$, we need to establish the inequalities

$[1_{A},f]\circ[f,1_{A}]\leq[1_{B},1_{B}]\quad\text{ and
}\quad[1_{A},1_{A}]\leq[f,1_{A}]\circ[1_{A},f].$

The LHS of the first inequality trivially computes to $[f,f]$, so it suffices
to show the identity $[f,f]=[f,f]\wedge[1_{B},1_{B}]$; and the RHS of the
second inequality equals $[f_{1},f_{2}]$ with $(f_{1},f_{2})$ a kernel pair of
$f$, so it suffices to show the identity
$[1_{A},1_{A}]=[f_{1},f_{2}]\wedge[1_{A},1_{A}]$. But the validity of the two
needed identities may be seen easily, since the relevant meets may be
displayed by the following two square diagrams. Indeed, as the morphisms
$\langle 1_{B},1_{B}\rangle$ and $\langle f_{1},f_{2}\rangle$ are monic, they
are both pullback squares, with diagonals $\langle f,f\rangle$ and $\langle
1_{A},1_{A}\rangle$ respectively.

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{1_{A}}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
1_{B},1_{B}\rangle}$$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
f,f\rangle\quad}$$\textstyle{B\times B}$
$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1_{A}}$$\scriptstyle{\langle
1_{A},1_{A}\rangle}$$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
1_{A},1_{A}\rangle}$$\textstyle{A\times_{B}A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
f_{1},f_{2}\rangle}$$\textstyle{A\times A}$

By the lemma, we may restrict the codomain of the functor $\Gamma_{\sim}$ and
consider it as a functor
$\mathcal{C}\longrightarrow\mathsf{Map}(\mathsf{Span}_{\sim}(\mathcal{C}))$.
Its behaviour on pullbacks is described in the following proposition which we
will use in Section 6.

######  Proposition 5.3.

Let $\sim$ be a compatible and allegorical equivalence relation on
$\mathsf{Span}(\mathcal{C})$. Then $\Gamma_{\sim}$ maps a pullback square

$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{k^{\prime}}$$\scriptstyle{h^{\prime}}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{k}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h}$$\textstyle{\cdot}$

in $\mathcal{C}$ to a pullback square in
$\mathsf{Map}(\mathsf{Span}_{\sim}(\mathcal{C}))$ if the pair
$(\Gamma_{\sim}\,k^{\prime},\Gamma_{\sim}\,h^{\prime})$ tabulates the morphism
$(\Gamma_{\sim}\,k)^{\circ}\circ(\Gamma_{\sim}\,h)$ in
$\mathsf{Span}_{\sim}(\mathcal{C})$. This condition is not only sufficient,
but also necessary, provided that the morphism
$(\Gamma_{\sim}\,k)^{\circ}\circ(\Gamma_{\sim}\,h)$ has any tabulation in
$\mathsf{Span}_{\sim}(\mathcal{C})$.

######  Proof 5.4.

Continuing to write $[-,-]$ for $[-,-]_{\sim}$, we first assume that the pair
$([1,k^{\prime}],[1,h^{\prime}])$ tabulates $[1,k]^{\circ}\circ[1,h]$. In
order to show the pullback property in
$\mathsf{Map}(\mathsf{Span}_{\sim}(\mathcal{C}))$, we consider any maps $x,y$
in $\mathsf{Span}_{\sim}(\mathcal{C})$ with $[1,h]\circ x=[1,k]\circ y$. Then,
by [Freyd, Scedrov 1990, 2.146], we get $y\circ
x^{\circ}\leq[1,k]^{\circ}\circ[1,h]$, and by [Freyd, Scedrov 1990, 2.143],
this inequality suffices to guarantee the existence of a unique map $z$ with
$[1,k^{\prime}]\circ z=x$ and $[1,k^{\prime}]\circ z=y$. This shows that
$\Gamma_{\sim}$ preserves the given pullback in $\mathcal{C}$.

Conversely, suppose that the functor $\Gamma_{\sim}$ maps the given pullback
in $\mathcal{C}$ to a pullback in
$\mathsf{Map}(\mathsf{Span}_{\sim}(\mathcal{C}))$, and assume that
$[1,k]^{\circ}\circ[1,h]$ has some tabulation $(x,y)$. Then, invoking [Freyd,
Scedrov 1990, 2.143 and 2.146] again, we see that the square

$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{x}$$\scriptstyle{y}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[1,k]}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[1,h]}$$\textstyle{\cdot}$

is a pullback diagram in $\mathsf{Map}(\mathsf{Span}_{\sim}(\mathcal{C}))$
and, hence, isomorphic to the $\Gamma_{\sim}$-image of the given pullback in
$\mathcal{C}$. Consequently, $([1,k^{\prime}],[1,h^{\prime}])$ tabulates the
morphism $[1,k]^{\circ}\circ[1,h]$.

The assertion of the previous proposition may be strengthened when the
relation $\sim$ is finer than the relation $\sim_{\mathcal{E}}$ induced by a
stable factorization system $(\mathcal{E},\mathcal{M})$, as we show with the
following proposition.

######  Proposition 5.5.

Let $(\mathcal{E},\mathcal{M})$ be a stable factorization system in
$\mathcal{C}$ and $\sim$ a compatible and allegorical equivalence relation on
$\mathsf{Span}(\mathcal{C})$ containing $\sim_{\mathcal{E}}$. Then the
following two conditions on the allegory $\mathsf{Span}_{\sim}(\mathcal{C})$
are equivalent:

  * (i)

for all morphisms $m\in\mathcal{M}$, the pair $([1,m]_{\sim},[1,m]_{\sim})$
tabulates $[m,m]_{\sim}$;

  * (ii)

for all spans $(f,g):A\to B$ in $\mathcal{C}$, the pair
$([1,\pi_{1}m]_{\sim},[1,\pi_{2}m]_{\sim})$ tabulates $[f,g]_{\sim}$, with
$\pi_{1},\pi_{2}$ denoting product projections, and with $m\in\mathcal{M}$
arising from the $(\mathcal{E},\mathcal{M})$-factorization of $\langle
f,g\rangle:\cdot\to A\times B$.

If either condition holds, then the functor
$\Gamma_{\sim}:\mathcal{C}\longrightarrow\sf{Map}(\sf{Span}_{\sim}(\mathcal{C}))$
preserves pullbacks.

######  Proof 5.6.

(i)$\Longrightarrow$(ii): Let $\langle f,g\rangle=me$ be a factorization with
$m\in\mathcal{M}$ and $e\in\mathcal{E}$. Then, since
$\sim_{\mathcal{E}}\,\subseteq\,\sim$, one trivially has
$[f,g]_{\sim}=[\pi_{1}m,\pi_{2}m]_{\sim}=[1,\pi_{2}m]_{\sim}\circ[1,\pi_{1}m]^{\circ}_{\sim}$.
It therefore suffices to show that the meet
$[1,\pi_{1}m]_{\sim}^{\circ}\circ[1,\pi_{1}m]_{\sim}\wedge[1,\pi_{2}m]_{\sim}^{\circ}\circ[1,\pi_{2}m]_{\sim}$
is an identity morphism. But the LHS of this meet is represented by the kernel
pair of $\pi_{1}m$, and its RHS by the kernel pair of $\pi_{2}m$ which, as a
routine calculation in $\mathcal{C}$ shows, makes the meet to be represented
by the kernel pair $(m_{1},m_{2})$ of $m$. Now, with hypothesis (i), we obtain
the desired identity

$[m_{1},m_{2}]_{\sim}=[1,m]_{\sim}^{\circ}\circ[1,m]_{\sim}=[1,m]_{\sim}^{\circ}\circ[1,m]_{\sim}\wedge[1,m]_{\sim}^{\circ}\circ[1,m]_{\sim}=1.$

(ii)$\Longrightarrow$(i): Consider $m\in\mathcal{M}$ and form the
factorizations $\langle m,m\rangle=nc$ and $\pi_{1}n=n^{\prime}c^{\prime}$
with $c,c^{\prime}\in\mathcal{E}$ and $n,n^{\prime}\in\mathcal{M}$. Then
$n^{\prime}(c^{\prime}c)=\pi_{1}\langle m,m\rangle=m$ is an
$(\mathcal{E},\mathcal{M})$-factorization of $m$, which forces $c^{\prime}c$
to be an isomorphism and, hence, makes $c$ a (split) monomorphism lying in
$\mathcal{E}$. Consequently, in $\mathsf{Span}(\mathcal{C})$ we have

$(c,1)\circ(1,c)=(1,1)\quad\text{and}\quad(1,c)\circ(c,1)=(c,c)\leq_{\mathcal{E}}(1,1),$

so that $[1,c]_{\sim}$ becomes an isomorphism in
$\mathsf{Span}_{\sim}(\mathcal{C})$. Since trivially

$(1,\pi_{1}n)\circ(1,c)=(1,m)=(1,\pi_{2}n)\circ(1,c),$

we have the commutative diagram

$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[1,m]_{\sim}}$$\scriptstyle{[1,c]_{\sim}}$$\scriptstyle{[1,m]_{\sim}}$$\textstyle{\cdot}$$\textstyle{\cdot}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[1,\pi_{1}n]_{\sim}}$$\scriptstyle{[1,\pi_{2}n]_{\sim}}$
(6)

in $\mathsf{Span}_{\sim}(\mathcal{C})$, of which the lower span tabulates
$[m,m]_{\sim}$, by hypothesis (ii). Therefore, with $[1,c]_{\sim}$ being an
isomorphism, its upper span tabulates $[m,m]_{\sim}$ as well.

The preservation of pullbacks by $\Gamma_{\sim}$ remains to be shown. For
that, given a pullback in $\mathcal{C}$ as in Proposition 5.3, it suffices to
prove that the pair $([1,k^{\prime}]_{\sim},[1,h^{\prime}]_{\sim})$ tabulates
the morphism $[1,k]_{\sim}^{\circ}\circ[1,h]_{\sim}$ which, trivially, equals
$[k^{\prime},h^{\prime}]_{\sim}$. By hypothesis (ii), that morphism is
tabulated by the pair
$([1,\pi_{1}m^{\prime}]_{\sim},[1,\pi_{2}m^{\prime}]_{\sim})$, where
$m^{\prime}\in\mathcal{M}$ belongs to the factorization $\langle
k^{\prime},h^{\prime}\rangle=m^{\prime}e^{\prime}$ with
$e^{\prime}\in\mathcal{E}$. As $\langle k^{\prime},h^{\prime}\rangle$ is
monic, so is $e^{\prime}$, so that one concludes that $[1,e^{\prime}]_{\sim}$
is an isomorphism—just like for $[1,c]_{\sim}$ above. And similarly to the
above argumentation one can finish the proof by just pointing to the trivially
commuting diagram

$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[1,k^{\prime}]_{\sim}}$$\scriptstyle{[1,e^{\prime}]_{\sim}}$$\scriptstyle{[1,h^{\prime}]_{\sim}}$$\textstyle{\cdot}$$\textstyle{\cdot}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[1,\pi_{1}m^{\prime}]_{\sim}}$$\scriptstyle{[1,\pi_{2}m^{\prime}]_{\sim}}$
(7)

Given a stable factorization system $(\mathcal{E},\mathcal{M})$ in
$\mathcal{C}$, the question remains how to refine the relation
$\sim_{\mathcal{E}}$ such that the finer relation satisfies the equivalent
conditions of Proposition 5.5. The following notion of conjugation of
morphisms in $\mathcal{M}$ as provided in [Hosseini, Shir Ali Nasab, Tholen
2020] turns out to be crucial to answer this question.

######  Definition 5.7.

In the following commutative diagram in $\mathcal{C}$, let the back and front
squares be pullbacks and $m\in\mathcal{M}$. We then call the (unique) morphism
$m^{*}$ the conjugate of $m$ along $f$ and $s$ and denote by $\mathcal{M}^{*}$
the closure under pullbacks of the class all morphisms that are presentable as
conjugates of some $m\in\mathcal{M}$ along some morphisms $f$ and $s$.

$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{\prime}}$$\scriptstyle{s^{\prime}}$$\scriptstyle{m^{*}}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{s}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g^{\prime}}$$\scriptstyle{t^{\prime}}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{t}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{m}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{\cdot}$

Let us note immediately that the formation of the class $\mathcal{M}^{*}$ may
be important only when $\mathcal{M}$ is not a class of monomorphisms in
$\mathcal{C}$. Indeed, when $m$ is a monomorphism, the right panel of the cube
is a pullback which, since the back and front panels are pullbacks, makes also
the left panel a pullback. But then $m^{*}$ must be an isomorphism, as a
pullback of an identity morphism. Consequently, $\mathcal{M}^{*}$ is just the
class $\mathsf{Iso}(\mathcal{C})$ when
$\mathcal{M}\subseteq\mathsf{Mono}(\mathcal{C})$.

Determining membership in $\mathcal{M}^{*}$ in the general case is a lot
harder. But at least one can easily see that split monomorphisms with a
retraction lying in $\mathcal{M}$ belong to $\mathcal{M}^{*}$, as follows:

######  Lemma 5.8.

Suppose $rs=1$ with $r\in\mathcal{M}$. Then $s\in\mathcal{M}^{*}$.

######  Proof 5.9.

The diagram

$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1}$$\scriptstyle{s}$$\scriptstyle{s}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{s}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r}$$\scriptstyle{1}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r}$$\textstyle{\cdot\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r}$$\textstyle{\cdot}$

shows that $s$ is the conjugate of $r$ along $1$ and $s$. Thus
$s\in\mathcal{M}^{*}$.

Trading $\mathrm{SplitEpi}(\mathcal{C})$ for $\mathcal{M}^{*}$ in Definition
4.13, we define:

######  Definition 5.10.

For a stable factorization system $(\mathcal{E},\mathcal{M})$ in
$\mathcal{C}$, we denote by $\mathcal{E}_{\bullet}$ the least stable system
containing both $\mathcal{E}$ and $\mathcal{M}^{*}$:

$\mathcal{E}_{\bullet}=(\mathcal{E}\cup\mathcal{M}^{*})^{c}.$

We note that, when $\mathcal{M}$ is a class of monomorphisms in $\mathcal{C}$,
so that $\mathcal{M}^{*}=\mathrm{Iso}(\mathcal{C})$, one has
$\mathcal{E}_{\bullet}=\mathcal{E}=\mathcal{E}_{\circ}$, but generally the
classes $\mathcal{E}_{\bullet}$ and $\mathcal{E}_{\circ}$ may be incomparable
by inclusion. Nevertheless, their induced equivalence relations are comparable
by inclusion:

######  Proposition 5.11.

Let $(\mathcal{E},\mathcal{M})$ be a stable factorization system in
$\mathcal{C}$. Then the equivalence relation $\sim_{\mathcal{E}_{\circ}}$ is
included in $\sim_{\mathcal{E}_{\bullet}}$, and
$\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$ is an allegory.

######  Proof 5.12.

It suffices to show that $(f,g)\leq_{\mathcal{E}_{\circ}}(h,k)$ implies
$(f,g)\sim_{\mathcal{E}_{\bullet}}(h,k)$. The hypothesis
$(f,g)\leq_{\mathcal{E}_{\circ}}(h,k)$ gives us a morphism
$r\in\mathcal{E}_{\circ}$ such that $\langle f,g\rangle=\langle h,k\rangle r$.
As $r$ is a composite of morphisms in
$\mathcal{E}\cup\mathrm{SplitEpi}(\mathcal{C})$, one may reason inductively
and restrict oneself to the only non-trivial case, that is that $r$ is a
retraction. There is then a morphism $s$ with $rs=1$, and factoring $r=me$,
with $m\in\mathcal{M}$ and $e\in\mathcal{E}$, we have $mes=1$. Thus, by Lemma
5.8, $es\in\mathcal{M}^{*}$. Since $\langle h,k\rangle=\langle f,g\rangle
s=\langle hm,km\rangle es$, this implies
$(h,k)\leq_{\mathcal{E}_{\bullet}}(hm,km)$. Since $\langle f,g\rangle=\langle
hm,km\rangle e$ trivially gives $(f,g)\leq_{\mathcal{E}_{\bullet}}(hm,km)$, we
can conclude that$(f,g)\sim_{\mathcal{E}_{\bullet}}(h,k)$ holds.

The relation $\sim_{\mathcal{E}_{\circ}}$ is allegorical by Corollary 4.5, and
one sees at once that this property gets inherited by any finer compatible
equivalence relation. Hence, by Proposition 5.11,
$\sim_{\mathcal{E}_{\bullet}}$ is also allegorical, so that by Theorem 3.4,
${\sf Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$ is an allegory.

In what follows, we are now ready to show that the allegory
$\sf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$ is even unitary and tabular.
We denote the $\sim_{\mathcal{E}_{\bullet}}$-equivalence class of a span
$(f,g)$ by $[f,g]_{\mathcal{E}_{\bullet}}$.

######  Theorem 5.13.

For a finitely complete category $\mathcal{C}$ with a stable factorization
structure $(\mathcal{E},\mathcal{M})$, the category
$\sf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$ is a unitary tabular
allegory. The terminal object in $\mathcal{C}$ serves as a unit in
$\sf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$, and the tabulation of a
morphism $[f,g]_{\mathcal{E}_{\bullet}}:A\to B$ is given by

$[f,g]_{\mathcal{E}_{\bullet}}=[1,\pi_{2}m]_{{\mathcal{E}}_{\bullet}}\circ[1,\pi_{1}m]^{\circ}_{\mathcal{E}_{\bullet}},$

where $m\in\mathcal{M}$ belongs to the
$(\mathcal{E},\mathcal{M})$-factorization of the morphism $\langle
f,g\rangle:\cdot\to A\times B$, with $\pi_{1}$, $\pi_{2}$ denoting the product
projections.

######  Proof 5.14.

As mentioned at the beginning of Section 3, the span $(\pi_{1},\pi_{2})$ given
by the projections of $A\times B$ is obviously neutral with respect to
$\wedge$ in the hom-set $\mathsf{Span}(\mathcal{C})(A,B)$, for any objects
$A,B$; this holds in particular for $A=B=E$ a terminal object in
$\mathcal{C}$. But in this case the projections are isomorphisms, and the
maximality of
$1_{E}=[1_{E},1_{E}]_{\mathcal{E}_{\bullet}}=[\pi_{1},\pi_{2}]_{\mathcal{E}_{\bullet}}$
in $\sf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})(E,E)$ follows. Furthermore,
for any object $A$ one has the morphism
$r=[1_{A},!_{A}]_{{\mathcal{E}}_{\bullet}}:A\to E$ which trivially satisfies
$r^{\circ}\cdot r\geq 1_{A}$. Hence, $E$ is a unit in
$\sf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$.

In order to prove that morphisms in
$\sf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$ may be tabulated as described
in the theorem, according to Proposition 5.5 we just need to show that, for
every $m\in\mathcal{M}$, the pair
$([1,m]_{{\mathcal{E}}_{\bullet}},[1,m]_{{\mathcal{E}}_{\bullet}})$ tabulates
$[m,m]_{\mathcal{E}_{\bullet}}$. Indeed, one trivially has
$[m,m]_{\mathcal{E}_{\bullet}}=[1,m]_{\mathcal{E}_{\bullet}}\circ[1,m]^{\circ}_{\mathcal{E}_{\bullet}}$,
and

$[m,1]_{\mathcal{E}_{\bullet}}\circ[1,m]_{\mathcal{E}_{\bullet}}\wedge[m,1]_{\mathcal{E}_{\bullet}}\circ[1,m]_{\mathcal{E}_{\bullet}}=[m,1]_{\mathcal{E}_{\bullet}}\circ[1,m]_{\mathcal{E}_{\bullet}}=[m_{1},m_{2}]_{\mathcal{E}_{\bullet}}$

is simply given by the kernel pair $(m_{1},m_{2})$ of $m$. By Lemma 5.8, the
common section of $m_{1},m_{2}$ lies in
$\mathcal{M}^{*}\subseteq\mathcal{E}_{\bullet}$, so that
$[m_{1},m_{2}]_{\mathcal{E}_{\bullet}}=[1,1]_{\mathcal{E}_{\bullet}}$ follows.
Hence, the allegory $\sf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$ is
tabular.

Recalling that $\mathcal{M}\subseteq\mathrm{Mono}(\mathcal{C})$ implies
$\mathcal{M}^{*}=\mathrm{Iso}(\mathcal{C})$ and then
$\mathcal{E}_{\bullet}=\mathcal{E}=\mathcal{E}_{\circ}$, we may now augment
the assertion of Corollary 4.12, as follows:

######  Corollary 5.15.

For a finitely complete category $\mathcal{C}$ with a stable factorization
system $(\mathcal{E},\mathcal{M})$, the category ${\sf
Span}_{\mathcal{E}}(\mathcal{C})\cong\sf{Rel}_{\mathcal{M}}(\mathcal{C})$ is
an allegory if, and only if,
$\mathrm{SplitEpi}(\mathcal{C})\subseteq\mathcal{E}$ or, equivalently,
$\mathcal{M}\subseteq\mathrm{Mono}(\mathcal{C})$, and it is then even unitary
and tabular.

##  6 Assigning to an allegory its regular category of maps is a right adjoint

We recall from [Johnstone 2002, A1 and A3] that, for a unitary and tabular
allegory, the category $\mathsf{Map}(\mathcal{A})$ is a finitely complete and
regular category, that is: it comes equipped with a stable (regular epi,
mono)-factorization system. The regular epimorphisms (also known as covers) in
$\mathsf{Map}(\mathcal{A})$ are described as those maps $f$ in $\mathcal{A}$
with $ff^{\circ}=1$, and the monomorphisms as those satisfying $f^{\circ}f=1$.
The unit of $\mathcal{A}$ serves as a terminal object in
$\mathsf{Map}(\mathcal{A})$.

In what follows we set up two (huge) 2-categories whose objects are
respectively given by the unitary tabular allegories and the finitely complete
categories equipped with a stable factorization system. They allow us to treat
the formation of the map category of an allegory as a 2-functor

$\mathsf{Map}:\mathfrak{UTabAll}\longrightarrow\mathfrak{StabFact},$

and then to show that the assignment
$(\mathcal{C},\mathcal{E},\mathcal{M})\longmapsto\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$
of Theorem 5.13 may be seen as the object part of its left adjoint, which we
will call $\mathsf{All}$.

In greater detail, in the 2-category $\mathfrak{UTabAll}$,

  * •

objects are unitary tabular allegories;

  * •

morphisms $R:\mathcal{A}\longrightarrow\mathcal{B}$ are unitary
representations ([Freyd, Scedrov 1990, 2.154]), i.e., functors preserving
units and commuting with the involutions and the meet operations;

  * •

2-cells $\phi:R\Longrightarrow S:\mathcal{A}\longrightarrow\mathcal{B}$ are
natural transformations whose components are maps and whose naturality squares
involving maps are pullbacks in $\mathsf{Map}(\mathcal{B})$.

In the 2-category $\mathfrak{StabFact}$,

  * •

objects $(\mathcal{C},\mathcal{E},\mathcal{M})$ are given by finitely complete
categories $\mathcal{C}$ that come equipped with a pullback-stable
factorization system $(\mathcal{E},\mathcal{M})$;

  * •

morphisms
$F:(\mathcal{C},\mathcal{E},\mathcal{M})\longrightarrow(\mathcal{D},\mathcal{F},\mathcal{N})$
are finite-limit preserving functors $F:\mathcal{C}\to\mathcal{D}$ with
$F(\mathcal{E})\subseteq\mathcal{F}$ and $F(\mathcal{M})\subseteq\mathcal{N}$;

  * •

2-cells $\theta:F\Longrightarrow G$ are natural transformations whose
naturality squares are pullbacks in $\mathcal{D}$.

Of course, in both 2-categories, the horizontal and vertical compositions
proceed as in the (huge) 2-category $\mathfrak{Cat}$ of all categories.

Since the notions of map and tabulation in an allegory are definable
equationally with the operations $\circ$ and $\wedge$, a unitary
representation $R:\mathcal{A}\longrightarrow\mathcal{B}$ preserves these
notions. Consequently, $R$ restricts to a functor
$\mathsf{Map}(\mathcal{A})\longrightarrow\mathsf{Map}(\mathcal{B})$ which
preserves the terminal object and pullbacks (these being given respectively by
the unit and by tabulation) and, hence, all finite limits. Likewise, the
restriction of $R$ to the map categories preserves regular epimorphisms and
monomorphisms, as these are again characterized equationally via $\circ$.
Finally, our definitions of 2-cells in the two huge 2-categories under
consideration guarantee that we indeed have the 2-functor

$\mathsf{Map}:\mathfrak{UTabAll}\longrightarrow\mathfrak{StabFact},\;\mathcal{A}\longmapsto(\mathsf{Map}(\mathcal{A}),\mathrm{RegEpi}(\mathsf{Map}(\mathcal{A})),\mathrm{Mono}(\mathsf{Map}(\mathcal{A}))),$

which operates on morphisms and 2-cells by restriction to the categories of
maps. Next we establish the aforementioned 2-functor $\mathsf{All}$, going in
the opposite direction.

######  Proposition 6.1.

There is a 2-functor

$\mathsf{All}:\mathfrak{StabFact}\longrightarrow\mathfrak{UTabAll},\;(\mathcal{C},\mathcal{E},\mathcal{M})\longmapsto\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C}).$

######  Proof 6.2.

By Theorem 5.13, $\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$ is a
unitary tabular allegory. For a morphism
$F:(\mathcal{C},\mathcal{E},\mathcal{M})\longrightarrow(\mathcal{D},\mathcal{F},\mathcal{N})$
in $\mathfrak{StabFact}$, we first note that the inclusion
$F(\mathcal{M})\subseteq\mathcal{N}$ and the preservation of pullbacks imply
$F(\mathcal{M}^{*})\subseteq\mathcal{N}^{*}$ which, in conjunction with
$F(\mathcal{E})\subseteq\mathcal{F}$, gives
$F(\mathcal{E}_{\bullet})\subseteq\mathcal{F}_{\bullet}$. Invoking pullback
preservation once more, we see that $F$ induces a well-defined functor

$\mathsf{All}(F):=\overline{F}:\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})\longrightarrow\mathsf{Span}_{\mathcal{F}_{\bullet}}(\mathcal{D}),\;([f,g]_{\mathcal{E}_{\bullet}}:A\to
B)\longmapsto([Ff,Fg]_{\mathcal{F}_{\bullet}}:FA\to FB).$

Further, as required, the functor $\overline{F}$ obviously commutes with the
involution, and it preserves the $\wedge$-operation as well as units since $F$
preserves finite products. Hence, $\overline{F}$ is a morphism in
$\mathfrak{UTabAll}$.

Let us now consider a 2-cell $\theta:F\Longrightarrow
G:(\mathcal{C},\mathcal{E},\mathcal{M})\longrightarrow(\mathcal{D},\mathcal{F},\mathcal{N})$
and prove that

$\mathsf{All}(\theta):=\overline{\theta}:\overline{F}\Longrightarrow\overline{G}\quad\text{with}\quad\overline{\theta}_{A}:=[1,\theta_{A}]_{\mathcal{F}_{\bullet}}:{F}A\longrightarrow{G}A$

defines a 2-cell in $\mathfrak{UTabAll}$. Clearly, the components of
$\overline{\theta}$ are maps in
$\mathsf{Span}_{\mathcal{F}_{\bullet}}(\mathcal{D})$. Next we observe that,
since the naturality squares of $\theta$ are pullbacks in $\mathcal{D}$, for
all spans
$\textstyle{A}$$\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{g}$$\textstyle{B}$
in $\mathcal{C}$ we have that the left square of the diagram

$\textstyle{FA\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(Ff,Fg)}$$\scriptstyle{(1,\theta_{A})}$$\textstyle{FB\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(1,\theta_{B})}$$\textstyle{GA\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(Gf,Gg)}$$\textstyle{GB}$
$\textstyle{FA\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{F}([f,g]_{\mathcal{E}_{\bullet}})}$$\scriptstyle{\overline{\theta}_{A}}$$\textstyle{FB\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{\theta}_{B}}$$\textstyle{GA\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{G}([f,g]_{\mathcal{E}_{\bullet}})}$$\textstyle{GB}$

commutes in $\mathsf{Span}(\mathcal{D})$, whence the right square commutes in
$\mathsf{Span}_{\mathcal{F}_{\bullet}}(\mathcal{D})$. This shows the
naturality of $\overline{\theta}$, and we are left with having to prove that
the right diagram is a pullback in
$\mathsf{Map}(\mathsf{Span}_{\mathcal{F}_{\bullet}}(\mathcal{D}))$ whenever
$[f,g]_{\mathcal{E}_{\bullet}}$ is a map in
$\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$. To this end, using again
the fact that the naturality squares of $\theta$ are pullbacks, we note that
the left square above decomposes as shown on the left of the following
diagram, whence the right square above decomposes as shown on the right below:

$\textstyle{FA\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(Ff,1)}$$\scriptstyle{(1,\theta_{A})}$$\textstyle{FD\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(1,Fg)}$$\scriptstyle{(1,\theta_{D})}$$\textstyle{FB\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(1,\theta_{B})}$$\textstyle{GA\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(Gf,1)}$$\textstyle{GD\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(1,Gg)}$$\textstyle{GB}$
$\textstyle{FA\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[Ff,1]_{\mathcal{F}_{\bullet}}}$$\scriptstyle{[1,\theta_{A}]_{\mathcal{F}_{\bullet}}}$$\textstyle{FD\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[1,Fg]_{\mathcal{F}_{\bullet}}}$$\scriptstyle{[1,\theta_{D}]_{\mathcal{F}_{\bullet}}}$$\textstyle{FB\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[1,\theta_{D}]_{\mathcal{F}_{\bullet}}}$$\textstyle{GA\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[Gf,1]_{\mathcal{F}_{\bullet}}}$$\textstyle{GD\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{[1,Gg]_{\mathcal{F}_{\bullet}}}$$\textstyle{GB}$

The right part of the double square on the right is a pullback, by Proposition
5.5, since it is the image of a naturality square of $\theta$ under the
functor
$\Gamma_{\sim_{\mathcal{F}_{\bullet}}}:\mathcal{D}\longrightarrow\mathsf{Map}(\mathsf{Span}_{\mathcal{F}_{\bullet}}(\mathcal{D}))$.
Hence , it suffices to show that also its left part is a pullback, and for
that it is sufficient to show that $[Ff,1]_{\mathcal{F}_{\bullet}}$ and
$[Gf,1]_{\mathcal{F}_{\bullet}}$ are isomorphisms in
$\mathsf{Map}(\mathsf{Span}_{\mathcal{F}_{\bullet}}(\mathcal{D}))$. In fact,
by functoriality of $\overline{F}$ and $\overline{G}$, it suffices to show
that $[f,1]_{\mathcal{E}_{\bullet}}$ is an isomorphism in
$\mathsf{Map}(\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C}))$. But this
last fact one sees easily: as $[f,g]_{\mathcal{E}_{\bullet}}$ is assumed to be
a map, the pairs
$([1,1]_{\mathcal{E}_{\bullet}},[f,g]_{\mathcal{E}_{\bullet}})$ and
$([1,f]_{\mathcal{E}_{\bullet}},[1,g]_{\mathcal{E}_{\bullet}})$ both tabulate
$[f,g]_{\mathcal{E}_{\bullet}}$, so the two tabulations can differ only by an
isomorphism, which makes $[1,f]_{\mathcal{E}_{\bullet}}$ an isomorphism since
$[1,1]_{\mathcal{E}_{\bullet}}$ is an isomorphism, and its inverse must be
$[1,f]_{\mathcal{E}_{\bullet}}^{\circ}=[f,1]_{\mathcal{E}_{\bullet}}$ (see
[Freyd, Scedrov 1990, 2.35]).

We are now ready to put the assertion of Theorem 5.13 into a ”global
perspective”:

######  Theorem 6.3.

There is a $2$-adjunction

$\textstyle{\mathsf{All}\dashv\mathsf{Map}:\mathfrak{UTabAll}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathfrak{StabFact}}$

whose counit is an isomorphism. Hence, up to 2-equivalence,
$\mathfrak{UTabAll}$ may be considered as a 2-reflective subcategory of
$\mathfrak{StabFact}$.

######  Proof 6.4.

For an object $(\mathcal{C},\mathcal{E},\mathcal{M})$ in
$\mathfrak{StabFact}$, we define the
$(\mathcal{C},\mathcal{E},\mathcal{M})$-component of the desired 2-natural
transformation $\Gamma:\mathrm{Id}\Longrightarrow\mathsf{Map}\mathsf{All}$ to
be the (identity-on-objects) functor

$\Gamma_{\sim_{\mathcal{E}_{\bullet}}}:\mathcal{C}\longrightarrow\mathsf{Map}(\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})),\quad
f\longmapsto[1,f]_{\mathcal{E}_{\bullet}},$

which, by Proposition 5.5, preserves pullbacks, as well as the terminal object
(see Theorem 5.13). Item (i) of Proposition 5.5 also confirms that, for
$m\in\mathcal{M}$, one has
$[1,m]^{\circ}_{\mathcal{E}_{\bullet}}\circ[1,m]_{\mathcal{E}_{\bullet}}=1$,
which makes $\Gamma_{\sim_{\mathcal{E}_{\bullet}}}m$ a monomorphism. For
$e\in\mathcal{E}$, since $(e,e)\leq_{\mathcal{E}}(1,1)$, one trivially has
$[1,e]\circ[1,e]^{\circ}_{\mathcal{E}_{\bullet}}=1$ and, therefore, that
$\Gamma_{\sim_{\mathcal{E}_{\bullet}}}e$ is a regular epimorphism in
$\mathsf{Map}(\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C}))$. This
establishes $\Gamma_{\sim_{\mathcal{E}_{\bullet}}}$ as a morphism in
$\mathfrak{StabFact}$.

In order to show the 2-naturality of $\Gamma$, one must confirm that, for all
morphisms
$F,\,G:(\mathcal{C},\mathcal{E},\mathcal{M})\longrightarrow(\mathcal{D},\mathcal{F},\mathcal{N})$
and every 2-cell $\theta:F\Longrightarrow G$, the diagram

$\textstyle{(\mathcal{C},\mathcal{E},\mathcal{M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Gamma_{\sim_{\mathcal{E}_{\bullet}}}}$$\scriptstyle{F}$$\scriptstyle{\hskip
2.84526pt\Longrightarrow^{{{}^{\theta}}}}$$\scriptstyle{G}$$\textstyle{\mathsf{Map}(\sf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C}))\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\hskip
11.38109pt\Longrightarrow^{{}^{\ \
\overline{\theta}}}}$$\scriptstyle{\overline{F}}$$\scriptstyle{\overline{G}}$$\textstyle{(\mathcal{D},\mathcal{F},\mathcal{N})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Gamma_{\sim_{\mathcal{F}_{\bullet}}}}$$\textstyle{\mathsf{Map}(\sf{Span}_{\mathcal{E}^{\prime}_{\bullet}}(\mathcal{D}))}$

commutes in an obvious sense (where we have omitted listing the regular
factorization systems of the RHS categories). But this confirmation involves
only short calculations referring exclusively to the applicable definitions,
which we can omit here.

We now proceed to establish the prospective counit
$\Delta:\mathsf{AllMap}\Longrightarrow\mathrm{Id}$ of the desired
2-adjunction. For that, we use the Freyd-Scedrov Representation Theorem for
(unitary) tabular allegories [Freyd, Scedrov 1990, 2.148]: for every (unitary)
tabular allegory, one has the (natural) tabulation isomorphism

$\mathsf{Rel}(\mathsf{Map}(\mathcal{A}))\longrightarrow\mathcal{A},\quad(h,k)\longmapsto
k\cdot h^{\circ},$

which we may precompose with the isomorphism (in $\mathfrak{Cat}$; see Theorem
2.4)

$\mathsf{Span}_{\mathcal{R}}(\mathsf{Map}(\mathcal{A}))\longrightarrow\mathsf{Rel}(\mathsf{Map}(\mathcal{A})),\quad[f,g]_{\mathcal{E}}\longmapsto(\pi_{1}m,\pi_{2}m),$

where $\mathcal{R}=\mathcal{R}_{\bullet}$ is the class
$\mathrm{RegEpi}(\mathsf{Map}(\mathcal{A}))$ and $m$ is the regular image of
$\langle f,g\rangle:\cdot\to A\times B$. The composite of these two
isomorphisms defines the $\mathcal{A}$-component of $\Delta$. It clearly
commutes with the involutions and meet-operations of the participating
allegories and is therefore an isomorphism in $\mathfrak{UTabAll}$. We can
omit the proof that $\Delta$ is indeed a 2-natural transformation, which
proceeds as routinely as the corresponding proof for $\Gamma$.

It remains for us to establish the triangular identities

$\mathsf{Map}\Delta\circ\Gamma\mathsf{Map}=1_{\mathsf{Map}}\quad\text{and}\quad\Delta\mathsf{All}\circ\mathsf{All}\,\Gamma=1_{\mathsf{All}}.$

For the first identity, we need to show that, for a unitary tabular allegory
$\mathcal{A}$ and $\mathcal{R}=\mathrm{RegEpi}(\mathsf{Map}(\mathcal{A}))$,
the composite functor

$\textstyle{\mathsf{Map}(\mathcal{A})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Gamma_{\sim_{\mathcal{R}}}\qquad}$$\textstyle{\mathsf{Map}(\mathsf{Span}_{\mathcal{R}}(\mathsf{Map}(\mathcal{A})))\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\qquad\mathsf{Map}(\Delta_{\mathcal{A}})}$$\textstyle{\mathsf{Map}(\mathcal{A})}$

is the identity functor. Indeed, the first functor sends a map $f$ in
$\mathcal{A}$ to $[1,f]_{\mathcal{R}}$ which, as a map, tabulates itself
trivially, and (the map-restriction of) $\Delta_{\mathcal{A}}$, as a morphism
of allegories, preserves the trivial tabulation, so that one gets $f\cdot
1^{\circ}=f$.

For the second identity, we consider $(\mathcal{C},\mathcal{E},\mathcal{M})$
in $\mathfrak{StabFact}$ and show that the composite functor

$\textstyle{\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{All}(\Gamma_{\mathcal{E}_{\bullet}})\qquad}$$\textstyle{\mathsf{Span}_{\mathcal{R}}(\mathsf{Map}(\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})))\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\qquad\Delta_{\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})}}$$\textstyle{\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})}$

maps every morphism $[f,g]_{\mathcal{E}_{\bullet}}$ in
$\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathcal{C})$ identically. Indeed, the
first functor maps $[f,g]_{\mathcal{E}_{\bullet}}$ to the morphism
$[\Gamma_{\mathcal{E}_{\bullet}}(f),\Gamma_{\mathcal{E}_{\bullet}}(g)]_{\mathcal{R}}$,
which then the second functor tabulates as

$\Gamma_{\mathcal{E}_{\bullet}}(g)\circ\Gamma_{\mathcal{E}_{\bullet}}(f)^{\circ}=[1,g]_{\mathcal{E}_{\bullet}}\circ[f,1]_{\mathcal{E}_{\bullet}}=[f,g]_{\mathcal{E}_{\bullet}},$

as desired.

As an important consequence of the Theorem, we obtain that the image under the
right-adjoint 2-functor $\mathsf{Map}$ is 2-equivalent to the 2-category
$\mathfrak{UTabAll}$ and 2-reflective in $\mathfrak{StabFact}$. Furthermore,
that image is precisely the (huge) 2-category

$\mathfrak{RegCat}$

of regular finitely complete categories, defined as a full sub-2-category of
$\mathfrak{StabFact}$; its equivalence with $\mathfrak{UTabAll}$ was
formulated explicitly (in the small one-dimensional version) in [Freyd,
Scedrov 1990, 2.154] and shown comprehensively in [Johnstone 2002, Theorem
3.2.10].

######  Corollary 6.5.

The 2-category $\mathfrak{UTabAll}$ is 2-equivalent to $\mathfrak{RegCat}$,
which is a 2-reflective full sub-2-category of $\mathfrak{StabFact}$.

Without reference to allegories, we can formulate explicitly the one-
dimensional part of the universal property describing the reflectivity
statement, as follows:

######  Corollary 6.6.

For every finitely complete category $\mathcal{C}$ with a (not necessarily
proper) stable $(\mathcal{E},\mathcal{M})$-factorization system, there is a
finite-limit-preserving functor $\Gamma:\mathcal{C}\to\mathcal{D}$ to a
regular category $\mathcal{D}$ which maps morphisms in $\mathcal{E}$ to
regular epimorphisms and morphisms in $\mathcal{M}$ to monomorphisms in
$\mathcal{D}$, such that any other functor
$\mathcal{C}\to\mathcal{D}^{\prime}$ of this type factors through $\Gamma$, by
a uniquely determined functor $\mathcal{D}\to\mathcal{D}^{\prime}$ that
preserves finite limits and regular epimorphisms. Moreover, the category
$\mathcal{D}$ may be constructed to have the same objects as $\mathcal{C}$,
mapped identically by $\Gamma$.

We end this article by presenting an easy example of a category $\mathcal{C}$
with a stable factorization system $(\mathcal{E},\mathcal{M})$ for which
$\mathcal{E}\nsubseteq\mathrm{Epi}(\mathcal{C})$ and
$\mathcal{M}\nsubseteq\mathrm{Mono}(\mathcal{C})$, such that the allegory
$\mathcal{A}=\mathsf{All}(\mathcal{C},\mathcal{E},\mathcal{M})$ admits a non-
trivial representation $\mathcal{A}\longrightarrow\mathsf{Rel}$ to the
allegory $\mathbf{Rel}=\mathsf{Rel}(\mathbf{Set})$ of sets and relations.

######  Example 6.7.

In the (ordinary) category $\mathcal{C}=\mathbf{Cat}$ of small categories we
have the stable factorization system $(\mathcal{E},\mathcal{M})$ where
$\mathcal{E}$ stands for “surjective on objects” and $\mathcal{M}$ for “fully
faithful and injective on objects”. Being right adjoint, the set-of-objects
functor $\mathrm{ob}:\mathbf{Cat}\to\mathbf{Set}$ to the regular category
$\mathbf{Set}$ preserves all limits, and it maps the classes $\mathcal{E}$ and
$\mathcal{M}$ appropriately to make it a morphism in $\mathfrak{StabFact}$.
Since $\mathbf{Set}\cong\mathsf{Map}(\mathbf{Rel})$, by the adjunction of
Theorem 6.3 the functor $\mathrm{ob}$ corresponds to a representation
$\mathcal{A}\to\mathbf{Rel}$, where the objects of the allegory
$\mathcal{A}=\mathsf{All}(\mathbf{Cat},\mathcal{E},\mathcal{M})$ are those of
$\mathbf{Cat}$. This representation maps objects like the functor
$\mathrm{ob}$ does, and a morphism $[f,g]_{\mathcal{E}_{\bullet}}:A\to B$ in
$\mathcal{A}=\mathsf{Span}_{\mathcal{E}_{\bullet}}(\mathbf{Cat})$ gets mapped
to the relation given by the image of the function
$\langle\mathrm{ob}\,f,\mathrm{ob}\,g\rangle$ in
$\mathrm{ob}A\times\mathrm{ob}B$.

Consequently, the morphisms of $\mathcal{A}$ offer a new type of
categorification of the notion of relation between sets.

## References

  * [Adamek, Herrlich, Strecker 2004] J. Adámek, H. Herrlich, G.E. Strecker. Abstract and Concrete Categories, John Wiley & Sons, New York 1990. Online edition: 2004.
  * [Bénabou 1967] J. Bénabou. Introduction to Bicategories, Lecture Notes in Mathematics 40, Springer, Berlin, 1967.
  * [Borceux 1994] F. Borceux. Handbook of Categorical Algebra 1. Basic Category Theory, Cambridge University Pres, 1994.
  * [Freyd, Scedrov 1990] P. J. Freyd and A. Scedrov. Categories, Allegories, North Holland, Amsterdam 1990.
  * [Hosseini, Shir Ali Nasab, Tholen 2020] S.N. Hosseini, A.R. Shir Ali Nasab, W. Tholen. Fraction, restriction and range categories from stable classes of morphisms, Journal of Pure and Applied Algebra 224(9):106361, 2020.
  * [Jayewardene, Wyler 1996] R. Jayewardene and O. Wyler. Categories of relations and functional relations, Applied Categorical Structures 8:279–305, 1996.
  * [Johnstone 2002] P. Johnstone. Sketches of an Elephant: A Topos Theory Compendium, vol. 1, Oxford University Press, Oxford 2002.
  * [Klein 1970] A. Klein. Relations in categories, Illinois Journal of Mathematics, 14:536–550, 1970.
  * [Meisen 1974] J. Meisen. On bicategories of relations and pullback spans, Communications in Algebra, 1(5):377–401, 1974.
  * [Milius 2000] S. Milius. Relations in Categories, Master’s thesis, York University, Toronto, Ontario, June 2000.
  * [Pavlović 1995] D. Pavlović. Maps I: Relative to a factorization system, Journal of Pure and Applied Algebra 99:9–34, 1995.


* [Ni] V. Nikulin, Integral symmetric bilinear forms and some of their applications, Math. USSR Izv. 14 (1980), 103–167.
  * [Sa] Indubala I. Satija, A tale of two fractals: The Hofstadter butterfly and the integral Apollonian gaskets, The European Physical Journal Special Topics, Volume 225, pages 2533-2547, (2016).
  * [Sh] N. Shah, Limiting distributions of curves under geodesic flow on hyperbolic manifolds, Duke Math. J. 148, no. 2 (2009), 251-279
  * [SSV] N. Sibony, A. Soldatenkov, M. Verbitsky, Rigid currents on compact hyperkähler manifolds, arXiv:2303.11362
  * [So] A. Soldatenkov, On the Hodge structures of compact hyperkähler manifolds, Math. Res. Lett. 28 (2021), no. 2, 623–635
  * [Th] W. Thurston, Geometry and topology of 3-manifolds, 1980, Prince- ton lecture notes, http://www.msri.org/publications/books/gt3m/.
  * [V1] M. Verbitsky, Mapping class group and a global Torelli theorem for hyperkähler manifolds, with an appendix by E. Markman, Duke Math. J. 162 (2013), no. 15, 2929–2986.
  * [V2] M. Verbitsky, Ergodic complex structures on hyperkähler manifolds: an erratum, arXiv:1708.05802

Ekaterina Amerik
Laboratory of Algebraic Geometry,
National Research University HSE,
Department of Mathematics, 6 Usacheva Str. Moscow, Russia,
<EMAIL_ADDRESS>also:
Université Paris-11,
Laboratoire de Mathématiques,
Campus d’Orsay, Bâtiment 425, 91405 Orsay, France

Andrey Soldatenkov
<EMAIL_ADDRESS>
Instituto Nacional de Matemática Pura e Aplicada (IMPA)
Estrada Dona Castorina, 110
Jardim Botânico, CEP 22460-320
Rio de Janeiro, RJ - Brasil

Misha Verbitsky
Instituto Nacional de Matemática Pura e Aplicada (IMPA)
Estrada Dona Castorina, 110
Jardim Botânico, CEP 22460-320
Rio de Janeiro, RJ - Brasil
<EMAIL_ADDRESS>
also:
Laboratory of Algebraic Geometry,
National Research University HSE,
Department of Mathematics, 6 Usacheva str.
Moscow, Russia.