Terminal Coalgebras for Finitary Functors

As we have mentioned above, our DCC condition was inspired by Urbat and Schröder [19]. However, the results here are disjoint from the ones in op. cit.

The most closely related paper to this one is our previous work [1]. That paper also contains results on endofunctors having terminal coalgebras in $\omega +\omega$ steps. But those results pertain to endofunctors belonging to one of several inductively defined classes. For example, for sets it studies the Kripke polynomial functors. This is the smallest class of endofunctors containing the constant functors and the finite power-set functor, and closed under products, coproducts, and composition. We have shown [1, Thm. 3.5] that every Kripke polynomial set functor has a terminal coalgebra in $\omega +\omega$ steps. Similarly, we have shown [1, Thm. 5.9] a result for the category of metric spaces and non-expanding maps, replacing the finite power-set functor with the Hausdorff functor: this assigns to a space the set of its compact subsets, using a well-known metric $\overline{d}$ (cf. Example 6.6). Again, every Hausdorff polynomial functor has a terminal coalgebra in $\omega +\omega$ steps. However, since the Hausdorff functor is not finitary on the category of all metric spaces, these results cannot be inferred from Theorem 5.1. In contrast, the results in this paper apply to categories not mentioned in op. cit: see Example 4.3 and Proposition 4.4. Both the theory and the specific results that follow are new.

A slightly stronger condition than our DCC was introduced in previous work [9]. The relationship of the two condition is dicussed in Section 4.

Another related result concerns the category of complete metric spaces: locally contracting endofunctors $F$ on this category satisfying $F\mathrm{\varnothing }\ne \mathrm{\varnothing }$ have a terminal coalgebra obtained in $\omega$ steps [6] (see also [5, Cor. 5.2.18]). Moreover, this is then also an initial algebra.

We recall the following characterization of limits of ${\omega }^{\mathrm{𝗈𝗉}}$-chains.

We continue with a terse review of locally finitely presentable categories; see [7] for background. A diagram $𝒟\to 𝒜$ is directed if its domain $𝒟$ is a directed poset (i.e. nonempty and such that every pair of elements has an upper bound). A functor is finitary if it preserves directed colimits. An object $A$ of a category $𝒜$ is finitely presentable if its hom-functor $𝒜(A,-):𝒜\to \mathrm{𝖲𝖾𝗍}$ preserves directed colimits. A category is locally finitely presentable (lfp, for short) if it is cocomplete and has a set of finitely presentable objects such that every object is a directed colimit of objects from that set.

Let $V_i$ be defined for all ordinals $i$ by $V_0=1$, $V_{i+1}=F{V}_i$, and for limit ordinals $i$. The ${\omega }^{\mathrm{𝗈𝗉}}$-chain (1.1) is its beginning, (2.1) defines the connecting morphism $m:V_{\omega +1}\to V_{\omega }$, and the ${\omega }^{\mathrm{𝗈𝗉}}$-chain (2.2), repeated below, is the continuation of the chain in (1.1) up to :

From Items 1 and 2, the morphisms $F^{i}m$ are monic. By ˜2.9.3, we may assume without loss of generality that $V_{\omega +\omega }$ is not strictly initial. So by Item 3, $F$ preserves this limit. It follows that $\nu F=V_{\omega +\omega }$, as explained at the beginning of Section 2. $◀$

Our proof proceeds in several steps.

1. 1.

   The finitely presentable objects of $\mathrm{𝖭𝗈𝗆}$ are precisely the orbit-finite nominal sets [15, Prop. 2.3.7]. By equivariance, a subobject of a nominal set $X$ is given by a number of orbits. So the DCC on subobjects of an orbit-finite nominal set clearly holds.

2. 2.

   For the descending chain condition for strong quotients, first recall that in $\mathrm{𝖭𝗈𝗆}$ all quotients are strong, and they are represented by the surjective equivariant maps. We first consider single-orbit nominal sets and recall that the supports of elements of an orbit all have the same cardinality. We also recall the standard fact [16, Exercise 5.1] that every single-orbit nominal set $X$ whose elements have supports of cardinality $n$ (this is the degree of $X$) is a quotient of the nominal set ${\mathrm{𝔸}}^{\mathrm{\#}n}=\{(a_1,\mathrm{\dots },a_n):|\{a_1,\mathrm{\dots },a_n\}|=n\}$, where $\mathrm{𝔸}$ denotes the set of names (or atoms). Now observe that a quotient of ${\mathrm{𝔸}}^{\mathrm{\#}n}$ having degree $n$ is determined by a subgroup $G$ of the symmetric group $S_n$. More specifically, the quotient determined by $G$ identifies $(a_1,\mathrm{\dots },a_n)$ and $(a_{\pi (1)},\mathrm{\dots },a_{\pi (n)})$ for every $(a_1,\mathrm{\dots },a_n)\in {\mathrm{𝔸}}^{\mathrm{\#}n}$ and every $\pi \in G$. Conversely, given a quotient $e:{\mathrm{𝔸}}^{\mathrm{\#}n}\twoheadrightarrow X$ we obtain $G$ as consisting of all those $\pi$ for which $e$ identifies the above two $n$-tuples for every $a_1,\mathrm{\dots },a_n$ in $\mathrm{𝔸}$. We conclude that every strictly descending chain of quotients of ${\mathrm{𝔸}}^{\mathrm{\#}n}$ all having degree $n$ corresponds to a strictly descending chain of subgroups of $S_n$; the same holds of course for every single-orbit nominal set of degree $n$. Such a chain must be finite, since so is $S_n$. In fact, more can be said: For $n\ge 2$, such a chain of subgroups of $S_n$ has length at most $2n-3$ [10] (and for $n=1$, $S_n$ is trivial, of course, so chains of subgroups have length 0).

3. 3.

   For general orbit-finite sets we now conclude that for every proper strong quotient of a nominal set $X$ one of the following three numbers strictly decreases while the other two do not increase: the number of orbits, the degree of some orbit of $X$, or the maximum length of the above chain of subgroups of $S_n$ for some orbit. Thus, $\mathrm{𝖭𝗈𝗆}$ is DCC.

4. 4.

   To see that $\mathrm{𝖭𝗈𝗆}$ is even graduated, observe that we can assign to each orbit-finite nominal set $X$ the sum of the three numbers mentioned in point 3 above. It is then clear that for every proper nominal subset or proper quotient of $X$ the grade is strictly smaller.

$◀$

Let $𝒜$ be a DCC-category. Let ${\mathrm{\ell }}_n:L\to A_n$ be a limit cone of an ${\omega }^{\mathrm{𝗈𝗉}}$-chain $D=(A_n)$ with connecting morphisms $a_{n+1}:A_{n+1}\to A_n$. Given a finitely presentable object $M$ and a monomorphism $m:M\rightarrowtail L$, factorize ${\mathrm{\ell }}_n\cdot m$ as a strong epimorphism $e_n:M\twoheadrightarrow B_n$ followed by a monomorphism $u_n:B_n\rightarrowtail A_n$ (˜2.4.2). We obtain a subchain $(B_n)$ of $(A_n)$ with connecting maps $b_n$ given by the diagonal fill-ins, as shown below:

Notice that $b_n$ is a strong epimorphism, since so is $e_n$. We thus have a descending chain $(B_n)$ of strong quotients of the finitely presentable object $M$: $e_0\ge e_1\ge e_2\ge \mathrm{\cdots }$. By the DCC condition, there is some $k$ such that for $n\ge k$, $b_n$ is an isomorphism. For $n\ge k$, let $b_{n,k}:B_n\to B_k$ be the composites recursively defined by $b_{n+1,k}=b_{n,k}\cdot b_n$. Thus, for every $n\ge k$, the triangle below commutes, where the lower part commutes by (4.1):

Let $D^{\prime }$ be the ${\omega }^{\mathrm{𝗈𝗉}}$ chain ${(A_n)}_{n\ge k}$. This is a shortening of our original ${\omega }^{\mathrm{𝗈𝗉}}$-chain $D$, and so its limit is ${\mathrm{\ell }}_n:L\to A_n$ ($n\ge k)$. The commutativity of all diagrams (4.2) shows that we have a cone ${(u_n\cdot b_{n,k}^{-1})}_{n\ge k}$ of $D^{\prime }$. Thus, there exists $b:B_k\to L$ such that

Consider the following diagram for $n\ge k$:

The square commutes, and we now prove that so does the outside. We show that for all $n\ge k$ and all $0\le i\le n-k$,

We argue by induction on $i$. For $i=0$, this holds using $b_{n,n}=\mathrm{𝗂𝖽}$ and the factorization $u_n\cdot e_n={\mathrm{\ell }}_n\cdot m$. Assume (4.4) for $i$. Fix $n\ge k$ such that $n-k\ge i+1$. Then

The induction completed, we take $i=n-k$ in (4.4) to see the commutativity of the outside of (4.3) for all $n$. Since the limit cone ${({\mathrm{\ell }}_n)}_{n\ge k}$ is collectively monic, the triangle in (4.3) commutes: $m=b\cdot e_k$. As $m$ is monic, so is $e_k$. Thus, ${\mathrm{\ell }}_k\cdot m=u_k\cdot e_k$ is also monic. $◀$

We will apply Proposition 3.1. Due to ˜2.9.3 we can assume without loss of generality that $V_i$ is not strictly initial for any $i\le \omega +\omega$.

1. 1.

   We first show that the canonical morphism $m:V_{\omega +1}\to V_{\omega }$ is monic. Consider a parallel pair $q,q^{\prime }:Q\rightrightarrows F{V}_{\omega }$ such that $m\cdot q=m\cdot q^{\prime }$. We prove that $q=q^{\prime }$. By ˜2.4.5, we may assume that $Q$ is a finitely presentable object. Using that $V_{\omega }$ can be assumed not to be strictly initial and ˜2.9.2, we may express $V_{\omega }$ as a directed colimit of nonempty finitely presentable subobjects, say $m_t:M_t\rightarrowtail V_{\omega }$ ($t\in T$). Since $F$ is finitary, $F{m}_t:F{M}_t\to F{V}_{\omega }$ is also a directed colimit. Hence, $q$ and $q^{\prime }$ factorize through $F{m}_t$ for some $t$. We denote the factorizing morphisms by $r$ and $r^{\prime }$, respectively. It is sufficient to show that they are equal. To this end consider the following diagram:

   $$\begin{array}{c}\text{<object type="image/svg+xml" data="dagpub-standalone-tikzcd-2025-06-12-10-53-26-6.pdf2svg.svg" id="S5.E1.m1.1.g1nest" class="ltx\_graphics ltx\_img\_landscape" width="209" height="55" style="width: 418px; height: unset; max-width: 100\%"></object>}\end{array}$$

   (5.1)

   The limit $v_{\omega ,i}:V_{\omega }\to V_i$ is finitary (Proposition 4.7). Thus, there is some $i$ so that $v_{\omega ,i}\cdot m_t:M_t\to V_i$ is monic, and this monomorphism is nonempty. Since $F$ preserves nonempty binary intersections, it preserves nonempty monomorphisms (˜2.6). Hence, the following morphism is monic:

   $$\mathrm{\ell }=\left(F{M}_t\stackrel{F{m}_t}{\to }F{V}_{\omega }\stackrel{F{v}_{\omega ,i}}{\to }F{V}_i\right).$$

   It is enough to show that $\mathrm{\ell }$ merges $r$ and $r^{\prime }$. The triangle on the right in (5.1) commutes. Thus we obtain

   $$\mathrm{\ell }=F{v}_{\omega ,i}\cdot F{m}_t=v_{\omega ,i+1}\cdot m\cdot F{m}_t.$$

   Using that $m$ merges $q$ and $q^{\prime }$, we see that $\mathrm{\ell }$ merges $r$ and $r^{\prime }$:

   	$\mathrm{\ell }\cdot r$	$=v_{\omega ,i+1}\cdot m\cdot F{m}_t\cdot r$
   		$=v_{\omega ,i+1}\cdot m\cdot q$
   		$=v_{\omega ,i+1}\cdot m\cdot q^{\prime }$
   		$=v_{\omega ,i+1}\cdot m\cdot F{m}_t\cdot r^{\prime }$
   		$=\mathrm{\ell }\cdot r^{\prime }.$

   Since $\mathrm{\ell }$ is monic, we have $r=r^{\prime }$ whence $q=q^{\prime }$, as desired.

2. 2.

   Next, we prove that $F$ preserves nonempty intersections of ${\omega }^{\mathrm{𝗈𝗉}}$-chains of subobjects. Consider such a chain $a_i:A_{i+1}\rightarrowtail A_i$, and let its limit cone be ${\mathrm{\ell }}_i:L\rightarrowtail A_i$, where $L$ is not strictly initial. It follows that neither is any of the $A_i$. Take a cone

   Our task is to find a morphism $q:Q\to FL$ such that $q_i=F{\mathrm{\ell }}_i\cdot q$ for all $i$. (This is unique: all maps ${\mathrm{\ell }}_i$ are nonempty monic, whence all $F{\mathrm{\ell }}_i$ are monic.)

   Using ˜2.4.4, we can assume, without loss of generality, that $Q$ is finitely presentable: for a general object $Q$, express it as a colimit of finitely presentable subobjects $Q_t$, and use the result which we prove for each $Q_t$.

   Choose a nonempty, finitely presentable subobject $c:C\rightarrowtail L$ (˜2.9.1). Note that this gives nonempty, finitely presentable subobjects

   which, moreover, form a cone: $c_i=a_i\cdot c_{i+1}$ for every .

   By recursion on $i$ we define a subchain $(B_i)$ of $(A_i)$ given by intersections

   together with a cone $p_i:Q\to F{B}_i$ such that $F{u}_i\cdot p_i=q_i$ and a cone $m_i:C\rightarrowtail B_i$ such that $c_i=u_i\cdot m_i$; this shows that all the intersections are nonempty.

   To define $B_0$ and $u_0$, express $A_0$ as a directed colimit of all its finitely presentable subobjects $u:B\rightarrowtail A_0$ that contain $c_0$ (˜2.4.4). Then use that $F$ preserves this colimit: for the morphism $q_0:Q\to F{A}_0$ we may find a subobject $u_0:B_0\rightarrowtail A_0$ containing $c_0$ such that $q_0$ factorizes through $F{u}_0$ via some $p_0:Q\to F{B}_0$, say:

   Since $u_0$ contains the subobject $c_0$, we have a monomorphism $m_0:C_0\rightarrowtail B_0$ such that $c_0=u_0\cdot m_0$.

   In the induction step we are given $B_i$, $u_i$, $p_i$, and $m_i$. Form the intersection of $u_i$ and $a_i$ to obtain $B_{i+1}$, $b_i$, and $u_{i+1}$ as shown in the left-hand square below:

   The outside commutes by induction hypothesis: $u_i\cdot m_i=c_i=a_i\cdot c_{i+1}$. Hence, we obtain the monomorphism $m_{i+1}$ as indicated such that the upper part and right-hand triangle commute, as desired. Since $C$ is not strictly initial, neither is $B_{i+1}$, whence the intersection of $a_i$ and $u_i$ is nonempty.

   So by hypothesis, $F$ preserves the above pullback. Since the square below commutes

   there is a unique morphism $p_{i+1}:Q\to F{B}_{i+1}$ such that

   $$p_i=F{b}_i\cdot p_{i+1}\text{and}{q}_{i+1}=F{u}_{i+1}\cdot p_{i+1}.$$

   For all , we form the composite morphism

   $$b_{j,i}=\left(\text{<object type="image/svg+xml" data="dagpub-standalone-tikzcd-2025-06-12-10-53-26-12.pdf2svg.svg" id="S5.Ex15.m1.g1nest" class="ltx\_graphics ltx\_img\_landscape" width="221" height="17" style="width: 442px; height: unset; max-width: 100\%"></object>}\right).$$

   We obtain a descending chain of subobjects $b_{j,0}:B_j\rightarrowtail B_0$ of the finitely presentable object $B_0$. Since $𝒜$ is DCC, there is some such that $b_{k^{\ast },0}$ represents the same subobject as $b_{j,0}$ for every $j\ge k^{\ast }$. Hence, the morphism $b_{j,k^{\ast }}$ is an isomorphism.

   The shortened ${\omega }^{\mathrm{𝗈𝗉}}$-chain ${(A_i)}_{i\ge k^{\ast }}$ has the limit cone ${({\mathrm{\ell }}_i)}_{i\ge k^{\ast }}$. The morphisms

   $$h_i=\left(B_{k^{\ast }}\stackrel{b_{i,k^{\ast }}^{-1}}{\to }{B}_i\stackrel{u_i}{\to }{A}_i\right)(i\ge k^{\ast })$$

   form a cone: we see that $h_i=a_i\cdot h_{i+1}$ from the commutativity of the diagram below:

   So there is a unique morphism $h:B_{k^{\ast }}\to L$ such that ${\mathrm{\ell }}_i\cdot h=u_i\cdot b_{i,k^{\ast }}^{-1}$ for $i\ge k^{\ast }$.

   The desired morphism is

   $$q=\left(Q\stackrel{p_{k^{\ast }}}{\to }F{B}_{k^{\ast }}\stackrel{Fh}{\to }FL\right).$$

   In order to verify that $q_i=F{\mathrm{\ell }}_i\cdot q$, it is sufficient to show this for $i\ge k^{\ast }$; it then follows also for all , since the $q_i$ and ${\mathrm{\ell }}_i$ form cocones:

   Now observe first that since $(p_i)$ form a cone of $(F{B}_i)$, we have

   $$F{b}_{i,k^{\ast }}\cdot p_i=p_{k^{\ast }}.$$

   By definition of $h$, we also have $u_i={\mathrm{\ell }}_i\cdot h\cdot b_{i,k^{\ast }}$. Therefore for all $i\ge k^{\ast }$, we obtain

   $$q_i=F{u}_i\cdot p_i=F{\mathrm{\ell }}_i\cdot Fh\cdot F{b}_{i,k^{\ast }}\cdot p_i=F{\mathrm{\ell }}_i\cdot Fh\cdot p_{k^{\ast }}=F{\mathrm{\ell }}_i\cdot q.$$

   This extends to all , the argument is as above.

Having checked all the conditions in Proposition 3.1, we are done. $◀$

Indeed, every set functor preserves nonempty binary intersections [18, Prop. 2.1], and every endofunctors on $K\text{-}\mathrm{𝖵𝖾𝖼}$ preserves finite intersections [9, Ex. 4.3].

The following example demonstrates that without extra conditions there is no uniform bound on the convergence of the terminal-coalgebra chain for finitary functors on locally finitely presentable categories.

Fix a metric space $M$. Let $f_S:S\to A$ be a cocone of the diagram of all finite subspaces $m_S:S\hookrightarrow M$ of $M$. Then there is a unique map $f:M\to A$ which restricts to $f_S$ for each finite subspace: $f\cdot m_S=f_S$. This map is non-expanding: given elements $x,y\in M$, let $S$ be the subspace of $M$ given by $\{x,y\}$. Since $f_S:S\hookrightarrow A$ is non-expanding, the distance of $f(x)$ and $f(y)$ in $A$ is at most equal to the distance of $x$ and $y$ in $M$, that is, in $S$. $◀$

This follows since $\mathrm{𝖲𝖾𝗍}$ has finitary ${\omega }^{\mathrm{𝗈𝗉}}$-limits (Proposition 4.7) because the forgetful functor into $\mathrm{𝖲𝖾𝗍}$ (1) preserves limits and (2) preserves and reflects monomorphisms. $◀$

1. 1.

   Given a directed diagram $D$ in $\mathrm{𝖬𝖾𝗍}$ of metric spaces $A_i$ ($i\in I$) and subspace embeddings $a_{i,j}:A_i\hookrightarrow A_j$ ($i\le j$), the colimit $C$ is the union ${\bigcup }_{i\in I}{A}_i$ with the metric inherited from the subspaces: for $x,y\in {\bigcup }_{i\in I}{A}_i$, the distance $d(x,y)$ in $C$ is their distance in $A_i$ for any $i\in I$ such that $x,y\in A_i$.

   An analogous statement holds for a directed diagram whose connecting morphisms are isometric embeddings.

2. 2.

   Given $q:Q\to FM$, let $D_M$ be the directed diagram of all finite subspaces of $M$ and all inclusion maps. Its colimit is $M$, using Item 1. Since $F$ is finitary, $FM$ is the colimit of $F{D}_M$, which is a directed diagram of isometric embeddings. The image $q[Q]$ is a finite subspace of $FM$. By Item 1, there exists a finite subspace $m:S\hookrightarrow M$ such that the colimit injection $Fm$ of $FC=𝖼𝗈𝗅𝗂𝗆F{D}_M$ satisfies $q[Q]\subseteq Fm[FS]$. Let $q^{\prime }:Q\to FS$ be the unique map such that $q=Fm\cdot q^{\prime }$. Then $q^{\prime }$ is non-expanding because so is $q$ and because $Fm$ is an isometric embedding.

$◀$

The following theorem has a proof analogous to that of Theorem 5.1. Recall that a functor preserving nonempty binary intersections also preserves nonempty monomorphisms (˜2.6). This time, we need an extra condition that isometric embeddings are preserved:

We again use Proposition 3.1. By ˜2.9.3, we may assume without loss of generality that all $V_i$, $i\le \omega +\omega$ are nonempty.

1. 1.

   The morphism $m:V_{\omega +1}\to V_{\omega }$ is monic: given a non-empty space $Q$ and $q,q^{\prime }:Q\to F{V}_{\omega }$ such that $m\cdot q=m\cdot q^{\prime }$, we prove that $q=q^{\prime }$. By Lemma 6.1, we may assume that $Q$ is finite. Thus, there exists a nonempty finite subspace $m_t:M_t\hookrightarrow Q$ such that both $q$ and $q^{\prime }$ factorize through $F{m}_t$: we have morphisms $r,r^{\prime }:Q\to F{M}_t$ such that $q=F{m}_t\cdot r$ and $q^{\prime }=F{m}_t\cdot r^{\prime }$. As in Item 1 of the proof of Theorem 5.1, we derive $r=r^{\prime }$. Since $F{m}_t$ is monic (because $F$ preserves nonempty binary intersections), this proves $q=q^{\prime }$.

2. 2.

   We prove that $F$ preserves nonempty limits of ${\omega }^{\mathrm{𝗈𝗉}}$-chains of monomorphisms

   Let ${\mathrm{\ell }}_i:L\to A_i$ be the limit cone. Given a cone $q_i:Q\to F{A}_i$ (), we only need to find a morphism $q:Q\to FL$ such that $q_i=F{\mathrm{\ell }}_i\cdot q$ ().

   Using Lemma 6.1, we may assume that $Q$ is finite. We define a subchain $(B_i)$ of $(A_i)$ carried by nonempty binary subspaces $u_i:B_i\hookrightarrow A_i$, together with cones $p_i:Q\to F{B}_i$ and $m_i:C\to B_i$ such that $F{u}_i\cdot p_i=q_i$ and $c_i=u_i\cdot m_i$. We use recursion analogous to that in Item 2 of the proof of Theorem 5.1. In order to define $B_0$, $u_0$, and $p_0$ use Lemma 6.4: there is a nonempty binary subspace $u_0:B_0\hookrightarrow A_0$ and a morphism $p_0:Q\to F{B}_0$ such that $q_0=F{u}_0\cdot p_0$. The induction step and the rest of the proof is as in Theorem 5.1.

$◀$