nLab
2-congruence

Idea

The notion of 2-congruence is the generalization of the notion of congruence from category theory to 2-category theory.

The correct notions of regularity and exactness for 2-categories is one of the subtler parts of the theory of first-order structure. In particular, we need a suitable replacement for the 1-categorical notion of equivalence relation. The (almost) correct definition was probably first written down in StreetCBS.

One way to express the idea is that in an n-category, every object is internally a $(n-1)$-category; exactness says that conversely every “internal $(n-1)$-category” is represented by an object. When $n=1$, an “internal 0-category” means an internal equivalence relation; thus exactness for 1-categories says that every equivalence relation is a kernel (i.e. is represented by some object). Thus, we need to find a good notion of “internal 1-category” in a 2-category.

Of course, there is an obvious notion of an internal category in a 2-category, as a straightforward generalization of internal categories in a 1-category. But internal categories in Cat are double categories, so we need to somehow cut down the double categories to those that really represent honest 1-categories. These are the 2-congruences.

Definition

Before we define 2-congruences below in def. 3, we need some preliminaries.

2-Congruences

Definition

If $K$ is a finitely complete 2-category, a homwise-discrete category in $K$ consists of

• a discrete morphism $D_1\to D_0\times D_0$, together

• with composition and identity maps $D_0\to D_1$ and $D_1{\times }_{D_0}{D}_1\to D_1$ in $K/(D_0\times D_0)$,

which satisfy the usual axioms of an internal category up to isomorphism.

Together with the evident notions of internal functor and internal natural transformation there is a 2-category $\mathrm{HDC}(K)$ of hom-wise discrete 2-categories in $K$.

Remark

Since $D_1\to D_0\times D_0$ is discrete, the structural isomorphisms will automatically satisfy any coherence axioms one might care to impose.

Remark

The transformations between functors $D\to E$ are a version of the notion for internal categories, thus given by a morphism $D_0\to E_1$ in $K$. The 2-cells in $K(D_0,E_0)$ play no explicit role, but we will recapture them below.

Remark

By homwise-discreteness, any “modification” between transformations is necessarily a unique isomorphism, so (after performing some quotienting, if we want to be pedantic) we really have a 2-category $\mathrm{HDC}(K)$ rather than a 3-category.

Definition

If $f:A\to B$ is any morphism in $K$, there is a canonical homwise-discrete category $(f/f)\to A\times A$, where $(f/f)$ is the comma object of $f$ with itself. We call this the kernel $\ker (f)$ of $f$ (the “comma kernel pair” or “comma Cech nerve” of $f$).

In particular, if $f=1_A$ then $(1_A/1_A)=A^2$, so we have a canonical homwise-discrete category $A^2\to A\times A$ called the kernel $\ker (A)$ of $A$.

Remark

It is easy to check that taking kernels of objects defines a functor $\Phi :K\to \mathrm{HDC}(K)$; this might first have been noticed by Street. See prop. 1 below.

Theorem

If $D_1\rightrightarrows D_0$ is a homwise-discrete category in $K$, the following are equivalent.

1. $D_0\leftarrow D_1\to D_0$ is a two-sided fibration in $K$.

2. There is a functor $\ker (D_0)\to D$ whose object-map $D_0\to D_0$ is the identity.

Actually, homwise-discreteness is not necessary for this result, but we include it to avoid worrying about coherence isomorphisms, and since that is the case we are most interested in here.

Proof

We consider the case $K=\mathrm{Cat}$; the general case follows because all the notions are defined representably. A homwise-discrete category in $\mathrm{Cat}$ is, essentially, a double category whose horizontal 2-category is homwise-discrete (hence equivalent to a 1-category). We say “essentially” because the pullbacks and diagrams only commute up to isomorphism, but up to equivalence we may replace $D_1\to D_0\times D_0$ by an isofibration, obtaining a (pseudo) double category in the usual sense. Now the key is to compare both properties to a third: the existence of a companion for any vertical arrow.

Suppose first that $D_0\leftarrow D_1\to D_0$ is a two-sided fibration. Then for any (vertical) arrow $f:x\to y$ in $D_0$ we have cartesian and opcartesian morphisms (squares) in $D_1$:

(1)$$\begin{array}{ccccccc}x& \stackrel{\mathrm{id}}{\to }& x& & x& \stackrel{f_1}{\to }& y\prime \\ {}^{\cong }\downarrow & \mathrm{opcart}& {\downarrow }^f& & {}^f\downarrow & \mathrm{cart}& {\downarrow }^{\cong }\\ x\prime & \stackrel{f_2}{\to }& y& & y& \stackrel{\mathrm{id}}{\to }& y\end{array}$$\array{ x & \overset{id}{\to} & x & \qquad & x & \overset{f_1}{\to} & y' \\ {}^{\mathllap{\cong}}\downarrow & opcart & \downarrow^{\mathrlap{f}} & \qquad & {}^{\mathllap{f}}\downarrow & cart & \downarrow^{\mathrlap{\cong}} \\ x' & \overset{f_2}{\to} & y & \qquad & y & \overset{id}{\to} & y }

The vertical arrows marked as isomorphisms are so by one of the axioms for a two-sided fibration. Moreover, the final compatibility axiom for a 2-sided fibration says that the square

(2)$$\begin{array}{ccc}x& \stackrel{f_1}{\to }& y\prime \\ \cong \downarrow & & \downarrow \cong \\ x\prime & \stackrel{f_2}{\to }& y,\end{array}$$\array{ x & \overset{f_1}{\to} & y'\\ \cong \downarrow & & \downarrow\cong \\ x' & \overset{f_2}{\to} & y,}

induced by factoring the horizontal identity square of $f$ through these cartesian and opcartesian squares, must be an isomorphism. We can then show that $f_1$ (or equivalently $f_2$) is a companion for $f$ just as in (Shulman 07, theorem 4.1). Conversely, from a companion pair we can show that $D_0\leftarrow D_1\to D_0$ is a two-sided fibration just as as in loc cit.

The equivalence between the existence of companions and the existence of a functor from the kernel of $D_0$ is essentially found in (Fiore 06), although stated only for the “edge-symmetric” case. In their language, a kernel $\ker (A)$ is the double category $\square A$ of commutative squares in $A$, and a functor $\ker (D_0)\to D$ which is the identity on $D_0$ is a thin structure on $D$. In one direction, clearly $\ker (D_0)$ has companions, and this property is preserved by any functor $\ker (D_0)\to D$. In the other direction, sending any vertical arrow to its horizontal companion is easily checked to define a functor $\ker (D_0)\to D$.

In particular, we conclude that up to isomorphism, there can be at most one functor $\ker (D_0)\to D$ which is the identity on objects.

Definition

A 2-congruence in a finitely complete 2-category $K$ is a homwise-discrete category, def. 1 in $K$ satisfying the equivalent conditions of Theorem 1.

Example

The kernel $\ker (A)$, def. 2 of any object is a 2-congruence.

More generally, the kernel $\ker (f)$ of any morphism is also a 2-congruence.

2-Forks and Quotients

The idea of a 2-fork is to characterize the structure that relates a morphism $f$ to its kernel $\ker (f)$. The kernel then becomes the universal 2-fork on $f$, while the quotient of a 2-congruence is the couniversal 2-fork constructed from it.

Definition

A 2-fork in a 2-category consists of a 2-congruence $s,t:D_1\rightrightarrows D_0$, $i:D_0\to D_1$, $c:D_1{\times }_{D_0}{D}_1\to D_1$, and a morphism $f:D_0\to X$, together with a 2-cell $\varphi :fs\to ft$ such that $\varphi i=f$ and such that

$$\begin{array}{ccccc}{D}_1{\times }_{D_0}{D}_1& \to & D_1& =& D_1\\ \downarrow & & \downarrow & {\Downarrow }_{\varphi }& \downarrow \\ D_1& \to & D_0& & D_0\\ \mid \mid & {\Downarrow }_{\varphi }& & {\searrow }^f& \downarrow f\\ D_1& \to & D_0& \stackrel{f}{\to }& X\end{array}=\begin{array}{c}{D}_1{\times }_{D_0}{D}_1\\ & {\searrow }^c\\ & & D_1& \to & D_0\\ & & \downarrow & {\Downarrow }_{\varphi }& \downarrow f\\ & & D_1& \stackrel{f}{\to }& X.\end{array}$$\array{ D_1\times_{D_0} D_1 & \to & D_1 & = & D_1\\ \downarrow && \downarrow & \Downarrow_\phi & \downarrow\\ D_1 & \to & D_0 && D_0\\ || &\Downarrow_\phi && \searrow^f & \downarrow f\\ D_1 & \to & D_0 & \overset{f}{\to} & X } \qquad = \qquad \array{ D_1\times_{D_0} D_1 \\ & \searrow^c\\ && D_1 & \to & D_0\\ && \downarrow & \Downarrow_\phi & \downarrow f\\ && D_1 & \overset{f}{\to} & X. }

The comma square in the definition of the kernel of a morphism $f:A\to B$ gives a canonical 2-fork

$$(f/f)\rightrightarrows A\stackrel{f}{\to }B.$$(f/f) \;\rightrightarrows\; A \overset{f}{\to} B.

It is easy to see that any other 2-fork

$$D_1\rightrightarrows D_0=A\stackrel{f}{\to }B$$D_1 \;\rightrightarrows\; D_0 = A \overset{f}{\to} B

factors through the kernel by an essentially unique functor $D\to \ker (f)$ that is the identity on $A$.

If $D_1\rightrightarrows D_0\stackrel{f}{\to }X$ is a 2-fork, we say that it equips $f$ with an action by the 2-congruence $D$. If $g:D_0\to X$ also has an action by $D$, say $\psi :gs\to gt$, a 2-cell $\alpha :f\to g$ is called an action 2-cell if $(\alpha t).\varphi =\psi .(\alpha s)$. There is an evident category $\mathrm{Act}(D,X)$ of morphisms $D_0\to X$ equipped with actions.

Definition

A quotient for a 2-congruence $D_1\rightrightarrows D_0$ in a 2-category $K$ is a 2-fork $D_1\rightrightarrows D_0\stackrel{q}{\to }Q$ such that for any object $X$, composition with $q$ defines an equivalence of categories

$$K(Q,X)\simeq \mathrm{Act}(D,X).$$K(Q,X) \simeq Act(D,X).

A quotient can also, of course, be defined as a suitable 2-categorical limit.

Lemma

The quotient $q$ in any 2-congruence is eso.

Proof

If $m:A\to B$ is ff, then the square we must show to be a pullback is

$$\begin{array}{ccc}\mathrm{Act}(D,A)& \stackrel{}{\to }& \mathrm{Act}(D,B)\\ \downarrow & & \downarrow \\ K(D_0,A)& \underset{}{\to }& K(D_0,B)\end{array}$$\array{Act(D,A) & \overset{}{\to} & Act(D,B)\\ \downarrow && \downarrow\\ K(D_0,A)& \underset{}{\to} & K(D_0,B)}

But this just says that an action of $D$ on $A$ is the same as an action of $D$ on $B$ which happens to factor through $m$, and this follows directly from the assumption that $m$ is ff.

Definition

A 2-fork $D_1\rightrightarrows D_0\stackrel{f}{\to }X$ is called exact if $f$ is a quotient of $D$ and $D$ is a kernel of $f$.

This is the 2-categorical analogue of the notion of exact fork in a 1-category, and plays an analogous role in the definition of a regular 2-category and an exact 2-category.

The 2-category of 2-conguences

There is an evident but naive 2-category of 2-congruences in any 2-category. And there is a refined version where internal functors are replaced by internal anafunctors.

Definition

For $K$ a 2-category, write $2{\mathrm{Cong}}_s(K)$ for the full sub-2-category of that of hom-wise discrete internal categories, def. 1 on the 2-congruences, def. 3

$$2{\mathrm{Cong}}_s(K)\hookrightarrow \mathrm{HDC}(K).$$2 Cong_s(K) \hookrightarrow HDC(K) \,.

Proposition

There is a 2-functor

$$\Phi :K\to 2{\mathrm{Cong}}_s(K)$$\Phi : K\to 2Cong_s(K)

sending each object to its kernel, def. 2.

Definition

Let the 2-category $K$ be equipped with the structure of a 2-site. With this understood, write

$$2\mathrm{Cong}(K)$$2 Cong(K)

for the 2-category of 2-congruences with morphisms the anafunctors between them.

Remark

The evident inclusion

$$2{\mathrm{Cong}}_s(K)\hookrightarrow 2\mathrm{Cong}(K)$$2 Cong_s(K) \hookrightarrow 2 Cong(K)

is a homwise-full sub-2-category closed under finite limits.

Properties

Opposites

The opposite of a homwise-discrete category is again a homwise-discrete category. However, the opposite of a 2-congruence in $K$ is a 2-congruence in $K^{\mathrm{co}}$, since 2-cell duals interchange fibrations and opfibrations. Likewise, passage to opposites takes 2-forks in $K$ to 2-forks in $K^{\mathrm{co}}$, and preserves and reflects kernels, quotients, and exactness.

Regularity

We discuss that when the ambient 2-category $K$ has finite 2-limits, then its 2-category $2{\mathrm{Cong}}_s(K)$ of 2-congruences, def. 7 is a regular 2-category. This is theorem 2 below. A sub-2-category of ${\mathrm{Cong}}_s(K)$ is the regular completion of $K$.

In the following and throughout, ”$n$” denotes either of (see (n,r)-category)

$$n=(0,1),(1,1),(2,1),(2,2).$$n = (0,1), (1,1), (2,1), (2,2) \,.

Lemma

Suppose that $K$ has finite 2-limits. Then:

1. $\mathrm{HDC}(K)$ (def. 1) has finite limits.

2. $n{\mathrm{Cong}}_s(K)$ is closed under finite limits in $\mathrm{HDC}(K)$.

3. The 2-functor $\Phi :K\to 2{\mathrm{Cong}}_s(K)$, prop. 1, is 2-fully-faithful (that is, an equivalence on hom-categories) and preserves finite limits.

Proof

It suffices to deal with finite products, inserters, and equifiers. Evidently $\Phi (1)$ is a terminal object. If $D$ and $E$ are homwise-discrete categories, define $P_0=D_0\times E_0$ and $P_1=D_1\times E_1$; it is easy to check that then $P_1\rightrightarrows P_0$ is a homwise-discrete category that is the product $D\times E$ in $\mathrm{HDC}(K)$. Since $(D_0\times E_0{)}^2\simeq (D_0{)}^2\times (E_0{)}^2$, and products preserve ffs, we see that $P$ is an $n$-congruence if $D$ and $E$ are and that $\Phi$ preserves products.

For inserters, let $f,g:C\rightrightarrows D$ be functors in $\mathrm{HDC}(K)$, define $i_0:I_0\to C_0$ by the pullback

$$\begin{array}{ccc}{I}_0& \to & D_1\\ i_0\downarrow & & \downarrow \\ C_0& \stackrel{(f_0,g_0)}{\to }& D_0\times D_0,\end{array}$$\array{I_0 & \to & D_1\\ i_0 \downarrow && \downarrow \\ C_0 & \overset{(f_0,g_0)}{\to} & D_0\times D_0,}

and define $i_1:I_1\to C_1$ by the pullback

$$\begin{array}{ccc}{I}_1& \to & X\\ i_1\downarrow & & \downarrow \\ C_1& \stackrel{(f_1,g_1)}{\to }& D_1\times D_1\end{array}$$\array{I_1 & \to & X\\ i_1\downarrow && \downarrow\\ C_1 & \overset{(f_1,g_1)}{\to} & D_1\times D_1}

where $X$ is the “object of commutative squares in $D$.” Then $I_1\rightrightarrows I_0$ is a homwise-discrete category and $i:I\to C$ is an inserter of $f,g$. Also, $I$ is an $n$-congruence if $C$ is, and $\Phi$ preserves inserters.

Finally, for equifiers, suppose we have functors $f,g:C\rightrightarrows D$ and 2-cells $\alpha ,\beta :f\rightrightarrows g$ in $\mathrm{HDC}(K)$, represented by morphisms $a,b:C_0\rightrightarrows D_1$ such that $(s,t)a\cong (f_0,g_0)\cong (s,t)b$. Let $e_0:E_0\to C_0$ be the universal morphism equipped with an isomorphism $\varphi :a{e}_0\cong b{e}_0$ such that $(s,t)\varphi$ is the given isomorphism $(s,t)a\cong (s,t)b$ (this is a finite limit in $K$.) Note that since $(s,t):D_1\to D_0\times D_0$ is discrete, $e_0$ is ff. Now let $E_1=(e_0\times e_0{)}^{*}{C}_1$; then $E_1\rightrightarrows E_0$ is a homwise-discrete category and $e:E\to C$ is an equifier of $\alpha$ and $\beta$ in $\mathrm{HDC}(K)$. Also $E$ is an $n$-congruence if $C$ is, and $\Phi$ preserves equifiers.

For any morphism $f:A\to B$ in $K$, $\Phi (f)$ is the functor $\ker (A)\to \ker (B)$ that consists of $f:A\to B$ and $f^2:A^2\to B^2$. A transformation between $\Phi (f)$ and $\Phi (g)$ is a morphism $A\to B^2$ whose composites $A\to B^2\rightrightarrows B$ are $f$ and $g$; but this is just a transformation $f\to g$ in $K$. Thus, $\Phi$ is homwise fully faithful. And homwise essential-surjectivity follows from the essential uniqueness of thin structures, or equivalently a version of Prop 6.4 in FBMF.

Moreover, we have:

Theorem

If $K$ is an $n$-category with finite limits, then $n{\mathrm{Cong}}_s(K)$ is regular.

Proof

It is easy to see that a functor $f:C\to D$ between $n$-congruences is ff in $n{\mathrm{Cong}}_s(K)$ iff the square

$$\begin{array}{ccc}{C}_1& \to & D_1\\ \downarrow & & \downarrow \\ C_0\times C_0& \to & D_0\times D_0\end{array}$$\array{C_1 & \to & D_1\\ \downarrow && \downarrow\\ C_0\times C_0 & \to & D_0\times D_0}

is a pullback in $K$.

We claim that if $e:E\to D$ is a functor such that $e_0:E_0\to D_0$ is split (that is, $e_{0}s\cong 1_{D_0}$ for some $s:D_0\to E_0$), then $e$ is eso in $n{\mathrm{Cong}}_s(K)$. For if $e\cong fg$ for some ff $f:C\to D$ as above, then we have $g_{0}s:D_0\to C_0$ with $f_0{g}_{0}s\cong e_{0}s\cong 1_{D_0}$, and so the fact that $C_1$ is a pullback induces a functor $h:D\to C$ with $h_0=g_{0}s$ and $fh\cong 1_D$. But this implies $f$ is an equivalence; thus $e$ is eso.

Moreover, if $e_0:E_0\to D_0$ is split, then the same is true for any pullback of $e$. For the pullback of $e:E\to D$ along some $k:C\to D$ is given by a $P$ where $P_0=E_0{\times }_{D_0}{D}_{\mathrm{iso}}{\times }_{D_0}{C}_0$; here $D_{\mathrm{iso}}\hookrightarrow D_1$ is the “object of isomorphisms” in $D$. What matters is that the projection $P_0\to C_0$ has a splitting given by combining the splitting of $e_0$ with the “identities” morphism $D_0\to D_{\mathrm{iso}}$.

Now suppose that $f:D\to E$ is any functor in $n{\mathrm{Cong}}_s(K)$. It is easy to see that if we define $Q_0=D_0$ and let $Q_1$ be the pullback

$$\begin{array}{ccc}{Q}_1& \to & E_1\\ \downarrow & & \downarrow \\ Q_0\times Q_0& \stackrel{f_0\times f_0}{\to }& E_0\times E_0\end{array}$$\array{ Q_1 & \to & E_1 \\ \downarrow && \downarrow\\ Q_0 \times Q_0 & \overset{f_0\times f_0}{\to} & E_0\times E_0}

then $f\cong me$ where $e:D\to Q$ and $m:Q\to E$ are the obvious functors. Moreover, clearly $m$ is ff, and $e$ satisfies the condition above, so any pullback of it is eso. It follows that if $f$ itself were eso, then it would be equivalent to $e$, and thus any pullback of it would also be eso; hence esos are stable under pullback.

Since $m$ is ff, the kernel of $f$ is the same as the kernel of $e$, so to prove $K$ regular it remains only to show that $e$ is a quotient of that kernel. If $C\rightrightarrows D$ denotes $\ker (f)$, then $C$ is the comma object $(f/f)$ and thus we can calculate

$$C_0=D_0{\times }_{E_0}{E}_1{\times }_{E_0}{D}_0\cong Q_1.$$C_0 = D_0\times_{E_0} E_1 \times_{E_0} D_0 \cong Q_1.

Therefore, if $g:D\to X$ is equipped with an action by $\ker (f)$, then the action 2-cell is given by a morphism $Q_1=C_0\to X_1$, and the action axioms evidently make this into a functor $Q\to X$. Thus, $Q$ is a quotient of $\ker (f)$, as desired.

Remark

There are three “problems” with the 2-category $n{\mathrm{Cong}}_s(K)$.

1. It is too big. It is not necessary to include every $n$-congruence in order to get a regular category containing $K$, only those that occur as kernels of morphisms in $K$.
2. It is too small. While it is regular, it is not exact.
3. It doesn’t remember information about $K$. If $K$ is already regular, then passing to $n{\mathrm{Cong}}_s(K)$ destroys most of the esos and quotients already present in $K$.

The solution to the first problem is straightforward.

Definition

If $K$ is a 2-category with finite limits, define

$$K_{\mathrm{reg}/\mathrm{lex}}\hookrightarrow 2{\mathrm{Cong}}_s(K)$$K_{reg/lex} \hookrightarrow 2 Cong_s(K)

to be the sub-2-category of $2{\mathrm{Cong}}_s(K)$ spanned by the 2-congruences which occur as kernels of morphisms in $K$.

Remark

If $K$ is an $n$-category then any such kernel is an $n$-congruence, so in this case $K_{\mathrm{reg}/\mathrm{lex}}$ is contained in $n{\mathrm{Cong}}_s(K)$ and is an $n$-category. Also, clearly $\Phi$ factors through $K_{\mathrm{reg}/\mathrm{lex}}$.

Theorem

For any finitely complete 2-category $K$, the 2-category $K_{\mathrm{reg}/\mathrm{lex}}$ is regular?, and the functor $\Phi :K\to K_{\mathrm{reg}/\mathrm{lex}}$ induces an equivalence

$$\mathrm{Reg}(K_{\mathrm{reg}/\mathrm{lex}},L)\simeq \mathrm{Lex}(K,L)$$Reg(K_{reg/lex},L) \simeq Lex(K,L)

for any regular 2-category $K$.

Here $\mathrm{Reg}(-,-)$ denotes the 2-category of regular functors, transformations, and modifications between two regular 2-categories, and likewise $\mathrm{Lex}(-,-)$ denotes the 2-category of finite-limit-preserving functors, transformations, and modifications between two finitely complete 2-categories.

Proof

It is easy to verify that $K_{\mathrm{reg}/\mathrm{lex}}$ is closed under finite limits in $2{\mathrm{Cong}}_s(K)$, and also under the eso-ff factorization constructed in Theorem 2; thus it is regular. If $F:K\to L$ is a lex functor where $L$ is regular, we extend it to $K_{\mathrm{reg}/\mathrm{lex}}$ by sending $\ker (f)$ to the quotient in $L$ of $\ker (Ff)$, which exists since $L$ is regular. It is easy to verify that this is regular and is the unique regular extension of $F$.

In particular, if $K$ is a regular 1-category, $K_{\mathrm{reg}/\mathrm{lex}}$ is the ordinary regular completion of $K$. In this case our construction reduces to one of the usual constructions (see, for example, the Elephant).

To solve the second and third problems with $n{\mathrm{Cong}}_s(K)$, we need to modify its morphisms.

Exactness

Let now the ambient 2-category $K$ be equipped with the structure of a 2-site. Recall from def. 8 the 2-category $2\mathrm{Cong}(K)$ whose objects are 2-congruences in $K$, and whose morpisms are internal anafunctors between these, with respect to the given 2-site structure.

Notice that when $K$ is a regular 2-category it comes with a canonical structure of a 2-site: its regular coverage.

Theorem

For any subcanonical and finitely complete 2-site $K$ (such as a regular coverage), the 2-category $2\mathrm{Cong}(K)$ from def. 8

• is finitely complete;

• contains $2{\mathrm{Cong}}_s(K)$, def. 7 as a homwise-full sub-2-category (that is, $2{\mathrm{Cong}}_s(K)(D,E)\hookrightarrow 2\mathrm{Cong}(K)(D,E)$ is ff) closed under finite limits.

Proof

It is easy to see that products in $2{\mathrm{Cong}}_S(K)$ remain products in $n\mathrm{Cong}(K)$. Before dealing with inserters and equifiers, we observe that if $A\leftarrow F\to B$ is an anafunctor in $2\mathrm{Cong}(K)$ and $e:X_0\to F_0$ is any eso, then pulling back $F_1$ to $X_0\times X_0$ defines a new congruence $X$ and an anafunctor $A\leftarrow X\to B$ which is isomorphic to the original in $2\mathrm{Cong}(K)(A,B)$. Thus, if $A\leftarrow F\to B$ and $A\leftarrow G\to B$ are parallel anafunctors in $2\mathrm{Cong}(K)$, by pulling them both back to $F{\times }_{A}G$ we may assume that they are defined by spans with the same first leg, i.e. we have $A\leftarrow X\rightrightarrows B$.

Now, for the inserter of $F$ and $G$ as above, let $E\to X$ be the inserter of $X\rightrightarrows B$ in $2{\mathrm{Cong}}_s(K)$. It is easy to check that the composite $E\to X\to A$ is an inserter of $F,G$ in $2\mathrm{Cong}(K)$. Likewise, given $\alpha ,\beta :F\rightrightarrows G$ with $F$ and $G$ as above, we have transformations between the two functors $X\rightrightarrows B$ in $2{\mathrm{Cong}}_s(K)$, and it is again easy to check that their equifier in $2{\mathrm{Cong}}_s(K)$ is again the equifier in $2\mathrm{Cong}(K)$ of the original 2-cells $\alpha ,\beta$. Thus, $2\mathrm{Cong}(K)$ has finite limits. Finally, by construction clearly the inclusion of $2{\mathrm{Cong}}_s(K)$ preserves finite limits.

Theorem

If $K$ is a subcanonical finitely complete $n$-site, then the functor $\Phi :K\to n\mathrm{Cong}(K)$, prop. 1, is 2-fully-faithful.
If $K$ is an $n$-exact $n$-category equipped with its regular coverage, then

$$\Phi :K\to n\mathrm{Cong}(K)$$\Phi : K \to n Cong(K)

is an equivalence of 2-categories.

Proof

Since $\Phi :K\to n{\mathrm{Cong}}_s(K)$ is 2-fully-faithful and $n{\mathrm{Cong}}_s(K)\to n\mathrm{Cong}(K)$ is homwise fully faithful, $\Phi :K\to n\mathrm{Cong}(K)$ is homwise fully faithful. For homwise essential-surjectivity, suppose that $\ker (A)\leftarrow F\to \ker (B)$ is an anafunctor. Then $h:F_0\to A$ is a cover and $F_1$ is the pullback of $A^2$ along it; but this just says that $F_1=(h/h)$. The functor $F\to B$ consists of morphisms $g:F_0\to B$ and $F_1=(h/h)\to B^2$, and functoriality says precisely that the resulting 2-cell equips $g$ with an action by the congruence $F$. But since $F$ is precisely the kernel of $h:F_0\to A$, which is a cover in a subcanonical 2-site and hence the quotient of this kernel, we have an induced morphism $f:A\to B$ in $K$. It is then easy to check that $f$ is isomorphic, as an anafunctor, to $F$. Thus, $\Phi$ is homwise an equivalence.

Now suppose that $K$ is an $n$-exact $n$-category and that $D$ is an $n$-congruence. Since $K$ is $n$-exact, $D$ has a quotient $q:D_0\to Q$, and since $D$ is the kernel of $q$, we have a functor $D\to \ker (Q)$ which is a weak equivalence. Thus, we can regard it either as an anafunctor $D\to \ker (Q)$ or $\ker (Q)\to D$, and it is easy to see that these are inverse equivalences in $n\mathrm{Cong}(K)$. Thus, $\Phi$ is essentially surjective, and hence an equivalence.

Note that by working in the generality of 2-sites, this construction includes the previous one.

Remark

If $K$ is a finitely complete 2-category equipped with its minimal coverage, in which the covering families are those that contain a split epimorphism, then

$$n\mathrm{Cong}(K)\simeq n{\mathrm{Cong}}_s(K).$$n Cong(K) \simeq n Cong_s(K) \,.

Proof

This is immediate from the proof of Theorem 2, which implies that the first leg of any anafunctor relative to this coverage is both eso and ff in $n{\mathrm{Cong}}_s(K)$, and hence an equivalence.

Theorem

If $K$ is a 2-exact 2-category with enough groupoids, then

$$K\simeq 2\mathrm{Cong}(\mathrm{gpd}(K)).$$K\simeq 2 Cong(gpd(K)) \,.

Likewise, if $K$ is 2-exact and has enough discretes, then

$$K\simeq 2\mathrm{Cong}(\mathrm{disc}(K)).$$K\simeq 2 Cong(disc(K)) \,.

Proof

Define a functor $K\to 2\mathrm{Cong}(\mathrm{gpd}(K))$ by taking each object $A$ to the kernel of $j:J\to A$ where $j$ is eso and $J$ is groupoidal (for example, it might be the core of $A$). Note that this kernel lives in $2\mathrm{Cong}(\mathrm{gpd}(K))$ since $(j/j)\to J\times J$ is discrete, hence $(j/j)$ is also groupoidal. The same argument as in Theorem 5 shows that this functor is 2-fully-faithful for any regular 2-category $K$ with enough groupoids, and essentially-surjective when $K$ is 2-exact; thus it is an equivalence. The same argument works for discrete objects.

In particular, the 2-exact 2-categories having enough discretes are precisely the 2-categories of internal categories and anafunctors in 1-exact 1-categories.

Our final goal is to construct the $n$-exact completion of a regular $n$-category, and a first step towards that is the following.

Theorem

If $K$ is a regular $n$-category, so is $n\mathrm{Cong}(K)$. The functor $\Phi :K\to n\mathrm{Cong}(K)$ is regular, and moreover for any $n$-exact 2-category $L$ it induces an equivalence

$$\mathrm{Reg}(n\mathrm{Cong}(K),L)\to \mathrm{Reg}(K,L).$$Reg(n Cong(K), L) \to Reg(K,L).

Proof

We already know that $n\mathrm{Cong}(K)$ has finite limits and $\Phi$ preserves finite limits. The rest is very similar to Theorem 2. We first observe that an anafunctor $A\leftarrow F\to B$ is an equivalence as soon as $F\to B$ is also a weak equivalence (its reverse span $B\leftarrow F\to A$ then provides an inverse.) Also, $A\leftarrow F\to B$ is ff if and only if

$$\begin{array}{ccc}{F}_1& \to & B_1\\ \downarrow & & \downarrow \\ F_0\times F_0& \to & B_0\times B_0\end{array}$$\array{F_1 & \to & B_1\\ \downarrow && \downarrow \\ F_0\times F_0 & \to & B_0\times B_0}

is a pullback.

Now we claim that if $A\leftarrow F\to B$ is an anafunctor such that $F_0\to B_0$ is eso, then $F$ is eso. For if we have a composition

$$\begin{array}{ccccc}& & & & F\\ & & & \swarrow & & \searrow \\ & & G& & & & M\\ & \swarrow & & \searrow & & \swarrow & & \searrow \\ A& & & & C& & & & B\end{array}$$\array{ &&&& F \\ &&& \swarrow && \searrow\\ && G &&&& M\\ & \swarrow && \searrow && \swarrow && \searrow\\ A &&&& C &&&& B}

such that $M$ is ff, then $F_0\to B_0$ being eso implies that $M_0\to B_0$ is also eso; thus $M\to B$ is a weak equivalence and so $M$ is an equivalence. Moreover, by the construction of pullbacks in $n\mathrm{Cong}(K)$, anafunctors with this property are stable under pullback.

Now suppose that $A\leftarrow F\to B$ is any anafunctor, and define $C_0=F_0$ and let $C_1$ be the pullback of $B_1$ to $C_0\times C_0$ along $C_0=F_0\mathrm{to}{B}_0$. Then $C$ is an $n$-congruence, $C\to B$ is ff in $n{\mathrm{Cong}}_s(K)$ and thus also in $n\mathrm{Cong}(K)$, and $A\leftarrow F\to B$ factors through $C$. (In fact, $C$ is the image of $F\to B$ in $n{\mathrm{Cong}}_s(K)$.) The kernel of $A\leftarrow F\to B$ can equally well be calculated as the kernel of $F\to B$, which is the same as the kernel of $F\to C$.

Finally, given any $A\leftarrow G\to D$ with an action by this kernel, we may as well assume (by pullbacks) that $F=G$ (which leaves $C$ unchanged up to equivalence). Then since the kernel acting is the same as the kernel of $F\to C$, regularity of $n{\mathrm{Cong}}_s(K)$ gives a descended functor $C\to D$. Thus, $A\leftarrow F\to C$ is the quotient of its kernel; so $n\mathrm{Cong}(K)$ is regular.

Finally, if $L$ is $n$-exact, then any functor $K\to L$ induces one $n\mathrm{Cong}(K)\to n\mathrm{Cong}(L)$, but $n\mathrm{Cong}(L)\simeq L$, so we have our extension, which it can be shown is unique up to equivalence.

When $K$ is a regular 1-category, it is well-known that $1\mathrm{Cong}(K)$ (which, in that case, is the category of internal equivalence relations and functional relations) is the 1-exact completion of $K$ (the reflection of $K$ from regular 1-categories into 1-exact 1-categories). Theorem 7 shows that in general, $n\mathrm{Cong}(K)$ will be the $n$-exact completion of $K$ whenver it is $n$-exact. However, in general for $n>1$ we need to “build up exactness” in stages by iterating this construction.

It is possible that the iteration will converge at some finite stage, but for now, define $n{\mathrm{Cong}}^r(K)=n\mathrm{Cong}(n{\mathrm{Cong}}^{r-1}(K))$ and let $K_{n\mathrm{ex}/\mathrm{reg}}={\mathrm{colim}}_{r}n{\mathrm{Cong}}^r(K)$.

Theorem

For any regular $n$-category $K$, $K_{n\mathrm{ex}/\mathrm{reg}}$ is an $n$-exact $n$-category and there is a 2-fully-faithful regular functor $\Phi :K\to K_{n\mathrm{ex}/\mathrm{reg}}$ that induces an equivalence

$$\mathrm{Reg}(K_{n\mathrm{ex}/\mathrm{reg}},L)\simeq \mathrm{Reg}(K,L)$$Reg(K_{n ex/reg},L) \simeq Reg(K,L)

for any $n$-exact 2-category $L$.

Proof

Sequential colimits preserve 2-fully-faithful functors as well as functors that preserve finite limits and quotients, and the final statement follows easily from Theorem 7. Thus it remains only to show that $K_{n\mathrm{ex}/\mathrm{reg}}$ is $n$-exact. But for any $n$-congruence $D_1\rightrightarrows D_0$ in $K_{n\mathrm{ex}/\mathrm{reg}}$, there is some $r$ such that $D_0$ and $D_1$ both live in $n{\mathrm{Cong}}^r(K)$, and thus so does the congruence since $n{\mathrm{Cong}}^r(K)$ sits 2-fully-faithfully in $K_{n\mathrm{ex}/\mathrm{reg}}$ preserving finite limits. This congruence in $n{\mathrm{Cong}}^r(K)$ is then an object of $n{\mathrm{Cong}}^{r+1}(K)$ which supplies a quotient there, and thus also in $K_{n\mathrm{ex}/\mathrm{reg}}$.

Examples

In $\mathrm{Grpd}$

Under construction.

Let $K:=$ Grpd be the 2-category of groupoids.

We would like to see that the following statement is true:

The 2-category of 2-congruences in $\mathrm{Grpd}$ is equivalent to the 2-category Cat of small categories.

$$2\mathrm{Cong}(\mathrm{Grpd})\simeq \mathrm{Cat}.$$2Cong(Grpd) \simeq Cat \,.

Let’s check:

For $C$ a small category, construct a 2-congruence $ℂ$ in $\mathrm{Grpd}$ as follows.

• let ${ℂ}_0:=\mathrm{Core}(C)\in \mathrm{Grpd}$ be the core of $C$;

• let ${ℂ}_1:=\mathrm{Core}(C^{\Delta [1]})\in \mathrm{Grpd}$ be the core of the arrow category of $C$;

• let $(s,t):{ℂ}_1\to {ℂ}_0$ be image under $\mathrm{Core}:\mathrm{Cat}\to \mathrm{Grpd}$ of the endpoint evaluation functor

$$C^{\Delta [0]\coprod \Delta [0]\to \Delta [1]}:C^{\Delta [1]}\to C^{\Delta [0]\coprod \Delta [0]}=C\times C.$$C^{\Delta[0] \coprod \Delta[0] \to \Delta[1]} : C^{\Delta[1]} \to C^{\Delta[0] \coprod \Delta[0]} = C \times C \,.

(Here we are using the canonical embedding $\Delta \hookrightarrow \mathrm{Cat}$ of the simplex category.)

This is clearly a faithful functor. Moreover, every morphism in Grpd is trivially a conservative morphism. So ${ℂ}_1\to {ℂ}_0\times {ℂ}_0$ is a discrete morphism in Grpd.

Since Grpd is a (2,1)-category, the 2-pullbacks in Grpd are homotopy pullbacks. Using that $(s,t)$ is (under the right adjoint nerve embedding $N:\mathrm{Grpd}\hookrightarrow \mathrm{sSet}$) a Kan fibration (by direct inspection, but also as a special case of standard facts about the model structure on simplicial sets), the object of composable morphisms is found to be

$${ℂ}_1{\times }_{{ℂ}_0}{ℂ}_1\simeq \mathrm{Core}(C^{\Delta [2]}).$$\mathbb{C}_1 \times_{\mathbb{C}_0} \mathbb{C}_1 \simeq Core(C^{\Delta[2]}) \,.

Accordingly, let the internal composition in $ℂ$ be induced by the given composition in $C$:

$${ℂ}_1{\times }_{{ℂ}_0}{ℂ}_1\simeq \mathrm{Core}(C^{\Delta [2]})\stackrel{}{\to }\mathrm{Core}(C^{\Delta [1]})\simeq {ℂ}_1.$$\mathbb{C}_1 \times_{\mathbb{C}_0} \mathbb{C}_1 \simeq Core(C^{\Delta[2]}) \stackrel{}{\to} Core(C^{\Delta[1]}) \simeq \mathbb{C}_1 \,.

This is clearly associative and unital and hence makes $ℂ$ a hom-wise discrete category, def. 1, internal to $\mathrm{Grpd}$.

Observe next (for instance using the discussion and examples at homotopy pullback, see also path object) that

$$\ker ({ℂ}_0)=({ℂ}_0^{\Delta [1]}\overrightarrow{\to }{ℂ}_0).$$ker(\mathbb{C}_0) = ( \mathbb{C}_0^{\Delta[1]} \stackrel{\to}{\to} \mathbb{C}_0) \,.

Notice that up to equivalence of groupoids, this is just the diagonal $\Delta :{ℂ}_0\to {ℂ}_0\times {ℂ}_0$.

Therefore there is an evident internal functor $\ker ({ℂ}_0)\to ℂ$, which on the first equivalent incarnation of $\ker ({ℂ}_0)$ given by the inclusion

$$\ker ({ℂ}_0)\simeq {ℂ}_0^{\Delta [1]}\simeq \mathrm{Core}(C{)}^{\Delta [1]}\hookrightarrow \mathrm{Core}(C^{\Delta [1]}),$$ker(\mathbb{C}_0) \simeq \mathbb{C}_0^{\Delta[1]} \simeq Core(C)^{\Delta[1]} \hookrightarrow Core(C^{\Delta[1]}) \,,

but which in the second version above simply reproduces the identity-assigning morphism of the internal category $ℂ$.

It follows that $ℂ$ is indeed a 2-congruence, def. 3.

Conversely, given a 2-congruence $ℂ$ in $\mathrm{Grpd}$, define a category $C$ as follows:

(…)

Remark

In the notation of the above proof, we can also form internally the core of $ℂ$. This is evidently the internally discrete category ${ℂ}_0\stackrel{\stackrel{\mathrm{id}}{\to }}{\underset{\mathrm{id}}{\to }}{ℂ}_0$.

This means that the 2-congruences $ℂ$ in the above proof are complete Segal spaces

$$ℂ:[n]\mapsto \mathrm{Core}(C^{\Delta [n]}),$$\mathbb{C} : [n] \mapsto Core(C^{\Delta[n]}) \,,

hence are internal categories in an (∞,1)-category in the (2,1)-category Grpd.

In a general $(2,1)$-category

(…)

Related concepts

• congruence

• n-congruence

References

The above material is taken from

• Mike Shulman, 2-congruence

and

• Mike Shulman, exact completion of a 2-category

Some lemmas are taken from

• Mike Shulman, Framed bicategories and monoidal fibrations (arXiv:0706.1286)

and

• Thomas Fiore, Pseudo Algebras and Pseudo Double Categories (arXiv:0608760)