# Approximate Coalgebra Homomorphisms and Approximate Solutions

Jiří Adámek

► To cite this version:

Jiří Adámek. Approximate Coalgebra Homomorphisms and Approximate Solutions. 15th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2020, Dublin, Ireland. pp.11-31, 10.1007/978-3-030-57201-3_2. hal-03232353

HAL Id: hal-03232353

https://inria.hal.science/hal-03232353

Submitted on 21 May 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Approximate Coalgebra Homomorphisms and Approximate Solutions

Jiří Adámek*

Faculty of Electrical Engineering, Technical University Prague, Czech Republic
j.adamek@tu-bs.de

**Abstract.** Terminal coalgebras $\nu F$ of finitary endofunctors $F$ on categories called strongly lfp are proved to carry a canonical ultrametric on their underlying sets. The subspace formed by the initial algebra $\mu F$ has the property that for every coalgebra $A$ we obtain its unique homomorphism into $\nu F$ as a limit of a Cauchy sequence of morphisms into $\mu F$ called approximate homomorphisms. The concept of a strongly lfp category includes categories of sets, posets, vector spaces, boolean algebras, and many others.

For the free completely iterative algebra $\Psi B$ on a pointed object $B$ we analogously present a canonical ultrametric on its underlying set. The subspace formed by the free algebra $\Phi B$ on $B$ has the property that for every recursive equation in $\Psi B$ we obtain the unique solution as a limit of a Cauchy sequence of morphisms into $\Phi B$ called approximate solutions. A completely analogous result holds for the free iterative algebra $RB$ on $B$.

# 1 Introduction

A number of important types of state-based systems can be expressed as coalgebras for finitary endofunctors $F$ of **Set**. That is, endofunctors such that every element of $FX$ lies in the image of $Fm$ for some finite subset $m: M \hookrightarrow X$. Examples include deterministic automata, dynamic systems and finitely branching LTS. The terminal coalgebra $\nu F$ carries a canonical ultrametric, see [4]. Recall from [13] that $\nu F$ represents the set of all possible state behaviors, and given a system as a coalgebra $A$ for $F$, the unique homomorphism $h: A \to \nu F$ assigns to every state its behavior. We are going to prove that whenever $F$ is grounded, i.e., $F\emptyset \neq \emptyset$, then the initial algebra $\mu F$ forms a dense subspace of the ultrametric space $\nu F$. And the coalgebra strucure of $\nu F$ is determined as the unique continuous extension of the inverted algebra structure of $\mu F$. Moreover, for every coalgebra $A$ we present a canonical Cauchy sequence of morphisms $h_k: A \to \mu F$ ($k < \omega$) converging to $h$ in the power space $(\nu F)^A$. We thus see that given state-based systems represented by a finitary set functor, (infinite) behaviour of states has canonical finite approximations, see Proposition 18.

<footnote>*Supported by the Grant Agency of the Czech Republic under the grant 19-00902S.</footnote>
All this generalizes from **Set** to every strongly locally finitely presentable category. These categories, introduced in [3] and recalled in Section 2 below, include vector spaces, posets and all locally finite varieties (e.g., boolean algebras or $\mathbb{S}$-**Mod**, semimodules over finite semirings $\mathbb{S}$). Every such category has a natural forgetful functor $U$ into **Set**. And the underlying set $U(\nu F)$ of the terminal coalgebra $\nu F$ carries a canonical ultrametric for every finitary endofunctor preserving monomorphisms. For example, consider the endofunctor of $\mathbb{S}$-**Mod** representing weighted automata, $FX = \mathbb{S} \times X^{\Sigma}$ (where $\Sigma$ is a finite set of inputs). It has the terminal coalgebra $\nu F = \mathbb{S}^{\Sigma^*}$, the semimodule of weighted languages. The ultrametric assigns to distinct languages $L_1, L_2$ the distance $2^{-k}$ for the least $k$ such that for some word $w \in \Sigma^*$ of length $k$ the two weights are different, see Example 13(4).

If $F$ is grounded, we again define, for every coalgebra $A$, a canonical sequence of morphisms $h_k: A \to \mu F$ converging to the unique coalgebra homomorphism $h: A \to \nu F$ in the power of the above ultrametric space. A concrete example: for every object $\Sigma$ consider the endofunctor $FX = X \times \Sigma + 1$ where $1$ is the terminal object. The underlying set of $\nu F$ is the set of all finite and infinite words over $U\Sigma$. And in case $U$ preserves finite coproducts, the underlying set of $\mu F$ is the set of all finite words. The distance of two distinct words is $2^{-k}$ for the least $k$ such that their prefixes of lengths at most $k$ are distinct.

Recursive equations in the terminal coalgebra (considered as an algebra) have a unique solution. That is, the algebra $\nu F$ is completely iterative, see [12]. We define, analogously, a canonical Cauchy sequence of approximate solutions into the initial algebra. And we prove that this sequence converges to the unique solution in $\nu F$. We recall from Milius [12] the concept of an algebra $A$ for $F$ being completely iterative in Section 4. Shortly, this means that for every object $X$ (of recursion variables) and every equation morphism $e: X \to FX + A$ there exists a unique solution, which is a morphism $e^\dagger: X \to A$ satisfying a simple recursive condition. Milius proved that the free completely iterative algebra $\Psi B$ on an object $B$ is precisely the terminal coalgebra for the endofunctor $F(-) + B$:

$$ \Psi B = \nu X.FX + B. $$

The functor $F(-) + B$ is grounded whenever $B$ has a global element. Thus we have the canonical ultrametric on the underlying set of $\Psi B$. Moreover, the free algebra $\Phi B$ for $F$ on $B$ is well-known to be the initial algebra for the functor $F(-) + B$:

$$ \Phi B = \mu X.FX + B. $$

We are going to present, for every recursive equation $e$ in $\Psi B$, a canonical Cauchy sequence of 'approximate solutions' $e_k^\dagger: X \to \Phi B$ in the free algebra which converges to the solution $e^\dagger$ in the power space of $\nu F$, see Theorem 31.

Finally, the same result is proved for the free iterative algebra $RB$: solutions are limits of sequences of approximate solutions. Recall that 'iterative' is the weakening of 'completely iterative' by restricting the objects $X$ (of recursion variables) to finitely presentable ones.
**Related Work** For finitary set functors preserving $\omega^{OP}$-limits Barr proved that the canonical ultrametric of $\nu F$ is complete, and in case $F$ is grounded this is the Cauchy completion of the subspace $\mu F$, see [11]. This was generalized to strongly lfp categories in [3]. The fact that preservation of $\omega^{OP}$-limits is not needed is new, and so is the fact that the algebra structure of $\mu F$ determines the coalgebra structure of $\nu F$.

The idea of approximate homomorphisms and approximate solutions has been used for set functors in the recent paper [5] where instead of ultrametrics complete partial orders were applied. It turns out that the present approach is much more natural and needs less technical preparations.

## 2 Strongly lfp categories

Throughout the paper we work with a finitary endofunctor $F$ of a locally finitely presentable (shortly lfp) category. In this preliminary section we recall basic properties of lfp categories and introduce strongly lfp categories.

Recall that an object $A$ of a category $\mathcal{K}$ is called *finitely presentable* if its hom-functor $\mathcal{K}(A, -)$ preserves filtered colimits. And a category $\mathcal{K}$ is called *lfp*, or *locally finitely presentable*, if it has colimits and a set of finitely presentable objects whose closure under filtered colimits is all of $\mathcal{K}$. Every lfp category is complete ([8], Remarkk 1.56.)

Recall further that an endofunctor is called *finitary* if it preserves filtered colimits.

**Examples 1 (See [6])** (1) Set is lfp. An endofunctor $F$ is finitary iff every element of $FX$ lies in the image of $Fm$ for some finite subset $m: M \hookrightarrow X$.

(2) K-Vec, the category of vector space over a field $K$, is lfp. An endofunctor $F$ is finitary iff every element of $FX$ lies in the image of $Fm$ for some finite-dimensional subspace $m: M \hookrightarrow X$.

*Remark 1.* (1) In an lfp category, given a filtered colimit $a_t: A_t \to A (t \in T)$ of a diagram $D$ with all connecting morphisms monic, it follows that

(a) each $a_t$ is monic, and

(b) for every cocone $f_t: A_t \to X$ of monomorphisms for $D$ the unique factorization morphism $f: A \to X$ is monic.

See [8], Proposition 1.62.

(2) In any category the corresponding statement is true for limits $a_t: A \to A_t$, $t < \lambda$, of $\lambda$-chains of monomorphisms for all limit ordinals $\lambda$:

(a) each $a_t$ is monic, and

(b) for every cone $f_t: X \to A_t$ of monomorphisms the factorization morphism $f: X \to A$ is monic.

Indeed, (a) follows from the fact that the cone of all $a_s$ with $t \le s$ is collectively monic. And (b) is trivial: since $a_0 \cdot f$ is monic, so is $f$.

(3) Every lfp category has (strong epi, mono)-factorizations of morphisms, see [8], Proposition 1.61. An epimorphism $e: A \to B$ is called *strong* if for every
monomorphism $m: U \to V$ the following diagonal fill-in property holds: given a commutative square $v \cdot e = m \cdot u$ (for some $u: A \to U$ and $v: B \to V$) there exists a unique 'diagonal' morphism $d: B \to U$ with $u = d \cdot e$ and $v = m \cdot d$.

(4) An object $A$ of an lfp category $\mathcal{K}$ is called *finitely generated* if it is a strong quotient of a finitely presentable object. Equivalently: $\mathcal{K}(A, -)$ preserves filtered colimits of monomorphisms, see [8], Proposition 1.69.

(5) The initial object of $\mathcal{K}$ is denoted by $0$. We call it *simple* if it has no proper strong quotients or, equivalently, if the unique morphism from it to any given object is monic. This holds e.g. in **Set** and **K-Vec**. In the lfp category **Alg**$_{1,0}$ of unary algebras with a constant the initial object is the algebra of natural numbers with the successor operation, and it is not simple.

**Notation 2** (1) We denote by $F^n 0$ ($n < \omega$) the initial-algebra $\omega$-chain

$$0 \xrightarrow{!} F0 \xrightarrow{F!} F^2 0 \xrightarrow{F^2!} \dots$$

with connecting maps $w_{n,k}: F^n 0 \to F^k 0$, where $w_{0,1} =!$ is unique and $w_{n+1,k+1} = Fw_{n,k}$. The colimit cocone $w_{n,\omega}: F^n 0 \to F^\omega 0$ ($n < \omega$) of this chain yields, since $F$ is finitary, a colimit cocone $Fw_{n,\omega}: F^{n+1} 0 \to F(F^\omega 0)$. Consequently, we obtain a unique morphism

$$\varphi: F(F^\omega 0) \to F^\omega 0 \quad \text{with} \quad \varphi \cdot Fw_{n,\omega} = w_{n+1,\omega} \quad (n < \omega).$$

Then $F^\omega 0$ is the initial algebra with the algebra structure $\varphi$, see the second proposition of [1].

(2) We denote by $F^i 1$ ($i \in \text{Ord}$) the terminal-coalgebra chain indexed by all ordinals, dually ordered:

$$1 \xleftarrow{!} F1 \xleftarrow{F!} FF1 \xleftarrow{F^2!} \dots \quad F^i 1 \leftarrow \dots$$

It is given by transfinite recursion: $F^0 1 = 1$, $F^{i+1} 1 = F(F^i 1)$ and, for limit ordinals $i$, $F^i 1 = \lim_{j<i} F^j 1$. The connecting maps $v_{ij}: F^i 1 \to F^j 1$ (for $i \ge j$ in Ord) are determined by transfinite recursion as follows:

$$v_{1,0} =!: F1 \to 1 \quad (\text{unique}), \quad v_{i+1,j+1} = Fv_{i,j}$$

and for limit ordinals $i$ the above limit $F^i 1$ has limit projections $v_{ij}$ ($j < i$).

(3) In case $F$ preserves limits of $\omega^{op}$-sequences the morphism $v_{\omega+1,\omega}$ is invertible, thus

$$\nu F = F^\omega 1,$$

with the coalgebra structure given by $\tau = v_{\omega+1,\omega}^{-1}$.

**Theorem 3** ([10], **Thm. 2.6**). If a finitary endofunctor $F$ of an lfp category preserves monomorphisms, then it has a terminal coalgebra $\nu F = F^i 1$ for some ordinal $i \ge \omega$ with $v_{i+1,i}$ invertible. The coalgebra structure is $\tau = v_{i+1,i}^{-1}: F^i 1 \to F(F^i 1)$.
**Proposition 4** Let $\mathcal{K}$ be an lfp category with a simple initial object. For every finitary endofunctor $F$ preserving monomorphisms the initial algebra is a canonical subobject of the terminal coalgebra: the unique algebra homomorphism

$$m: (\mu F, \varphi) \to (\nu F, \tau^{-1})$$

is monic.

*Proof.* The initial-algebra $\omega$-chain has a unique cocone $m_k: F^k 0 \to \nu F$ ($k < \omega$) satisfying the following recursion

$$m_{k+1} \equiv F(F^k 0) \xrightarrow{Fm_k} F(\nu F) \xrightarrow{\tau^{-1}} \nu F \quad (k < \omega).$$

Since $m_0: 0 \to \nu F$ is monic and $F$ preserves monomorphisms, each $m_k$ is monic. Therefore, the unique morphism

$$m: F^\omega 0 \to \nu F \quad \text{with} \quad m \cdot w_{k,\omega} = m_k \quad (k < \omega)$$

is monic, see Remark 1(1). And this is an algebra homomorphism, i.e., $m \cdot \varphi = \tau^{-1} \cdot Fm: F(\mu F) \to \nu F$. To verify this, recall that $F$ preserves colimits of chains, hence $(Fw_{k,\omega})_{k<\omega}$ is a collectively epic cocone. Thus, we only need to verify

$$m \cdot \varphi \cdot Fw_{k,\omega} = \tau^{-1} \cdot Fm \cdot Fw_{k,\omega} \quad (k < \omega).$$

By definition of $\varphi$, the left-hand side is $m \cdot w_{k+1,\omega} = m_{k+1}$. The right-hand one is the same: $\tau^{-1} \cdot Fm_k = m_{k+1}$.

*Remark 2.* An object $G$ of $\mathcal{K}$ is called a *generator* if its hom-functor $U = \mathcal{K}(G, -)$ is faithful. Thus $\mathcal{K}$ becomes a concrete category w.r.t. that hom-functor. For example $K$ is a generator of $K-\text{Vec}$, and the terminal object 1 is a generator of Set or Pos (the category of posets). In all these examples the above functor $U$ is naturally isomorphic to the usual forgetful functor.

**Definition 5** (See [4]) An lfp category is called strongly lfp provided that (a) for every limit cone $a_k: A \to A_k$ ($k < \omega$) of an $\omega^{\text{OP}}$-chain and every monomorphism $m: M \to A$ with $M$ finitely generated there exists $k$ with $a_k \cdot m: M \to A_k$ monic, and

(b) a generator $G$ is given.

In [4] the generator was assumed to be projective, but we do not need this assumption. Moreover, in that paper instead of our present factorization system (strong epi, mono) the system (epi, strong mono) was used.

**Examples 6** (1) Set is strongly lfp. Indeed, given an $\omega^{\text{OP}}$-limit $a_k: A \to A_k$ ($k < \omega$) and a finite subset $m: M \to A$, for every pair $x \neq y$ in $M$ there exists $k$ with $a_k(x) \neq a_k(y)$. Since $M \times M$ is finite, $k$ can be chosen independent of $x$, $y$. Thus, $a_k \cdot m$ is monic.
(2) Every variety of algebras which is locally finite (i.e., finitely generated algebras are finite) is strongly lfp. The free algebra $G$ on one generator is a generator. And since limits are formed on the level of sets, the $\omega^{\text{OP}}$-limit condition is verified precisely as in (1).

Examples include semilattices, boolean algebras, categories $\mathbb{S}$-Mod of left semimodules over a finite semiring $\mathbb{S}$, and categories $M$-Set of sets with an action of a finite monoid $M$.

(3) The category $K$-Vec of vector spaces is strongly lfp for every (possibly infinite) field $K$, see [3], Example 4.5(5).

(4) The category Pos of posets is strongly lfp whose terminal object is a generator. The $\omega^{\text{OP}}$-limit condition is verified as in (1) above.

(5) The category Gra of graphs (sets with a binary relation) and graph homomorphisms is strongly lfp. The single-vertex graph $G$ without edges is a generator, and the $\omega^{\text{OP}}$-limit condition is verified as in (1).

**Notation 7** Given a strongly lfp category $\mathcal{K}$ with a generator $G$, we denote by

$$U: \mathcal{K} \to \mathbf{Set}$$

the hom-functor of $G$. This is a faithful functor preserving limits (in particular, it preserves monomorphisms).

*Remark 3.* (1) In contrast to examples (2) and (3) above, the categories $\mathbb{Z}$-Mod of abelian groups and $\mathbb{Z}$-Set of unary algebras on one operation are not strongly lfp, see [3], Example 4.5.

(2) Worrell proved that for every finitary set functor $F$ all the connecting maps $v_{i,\omega}$, $i > \omega$, are monic. This can be generalized as follows.

**Theorem 8.** Let $\mathcal{K}$ be a strongly lfp category. For every finitary endofunctor $F$ preserving monomorphisms the terminal coalgebra $\nu F = F^i 1$ (see Theorem 3) is a canonical subobject of $F^\omega 1$: the morphism $v_{i\omega}$ is monic.

*Proof.* We prove that for all ordinals $j > \omega$ the connecting maps $v_{j\omega}$ are monic by transfinite induction.

(1) $v_{\omega+1,\omega}: F(F^\omega 1) \to F^\omega 1$ is monic. To prove this, use the fact that $\mathcal{K}$ is lfp and choose a filtered diagram $D$ of finitely presentable objects $A_t$ ($t \in T$) with a colimit cocone $a_t: A_t \to F^\omega 1$. Due to Remark 1(3) we have a factorization $a_t = b_t \cdot e_t$ for a strong epimorphism $e_t: A_t \to B_t$ and a monomorphism $b_t: B_t \to F^\omega 1$. The objects $B_t$ ($t \in T$) form a filtered diagram $\bar{D}$ whose connecting morphisms are derived via diagonal fill-in: given a connecting morphism $a_{t,t'}: A_t \to A_{t'}$ in $D$, we obtain a connecting morphism $b_{t,t'}: B_t \to B_{t'}$ of $\bar{D}$ by means of the
following diagonal:

<figure><img src="image_2.png" /></figure>

It is easy to verify that $\bar{D}$ a filtered diagram (since $D$ is) and the morphisms $b_t: B_t \to F^\omega 1$ ($t \in T$) form the colimit cocone of $\bar{D}$. Moreover, each connecting morphism $b_{t,t'}$ is monic (since its composite with $b_t$ is). Hence, our assumption that $F$ is finitary and preserves monomorphisms implies that we have a filtered diagram $F\bar{D}$ of all $FB_t$ ($t \in T$) whose connecting morphisms are monic and whose colimit is $(Fb_t)_{t \in T}$. Using Remark 1(1) it is sufficient, for proving that $v_{\omega+1,\omega}$ is monic, to verify that (for every $t \in T$)

$$v_{\omega+1,\omega} \cdot Fb_t: FB_t \to F^\omega 1 \text{ is monic.}$$

Since our category is strongly lfp and $B_t$ is finitely generated (being a strong quotient of the finitely presentable object $A_t$), it follows that for the monomorphism $b_t$ there exists $k < \omega$ with $v_{\omega,k} \cdot b_t$ monic. Thus, the morphism $Fv_{\omega,k} \cdot Fb_t = v_{\omega,k+1} \cdot v_{\omega+1,\omega} \cdot Fb_t = v_{\omega+1,\omega} \cdot Fb_t$ is monic, as desired.

(2) Each $v_{i,\omega}$ for $i > \omega$ is monic. This is easily seen by transfinite induction on $i$. The case $i = \omega+1$ has just been proved. If $v_{i,\omega}$ is monic, so is $Fv_{i,\omega} = v_{i+1,\omega+1}$, therefore, the composite $v_{i+1,\omega} = v_{\omega+1,\omega} \cdot v_{i+1,\omega+1}$ is also monic. And given a limit ordinal $i > \omega$, then each connecting map $v_{k,j}$, where $\omega \le j \le k < i$ is monic, since $v_{j,\omega} \cdot v_{k,j} = v_{k,\omega}$ is monic, see Remark 1(2). Now $F^j 1$ is a limit of the chain $F^{j+1}$ for all $\omega \le j < i$ whose connecting morphisms are monic. This implies that the limit cone consists of monomorphisms. In particular, $v_{i,\omega}$ is monic, as required.

**Lemma 9** For $i$ in Theorem 8 the following squares commute:

$$\begin{tikzcd}
& & \mu F \arrow[r, "m"] \arrow[d, "w_{k,\omega}"] & \nu F = F^i 1 \arrow[d, "v_{i,k}"] \\
F^k 0 & F^k 1 & &
\end{tikzcd} \quad (k < \omega)$$

*Proof.* We proceed by induction, the case $k = 0$ is clear. Recall that $m$ is an algebra homomorphism:

$$m \cdot \varphi = \tau^{-1} \cdot Fm = v_{i+1,i} \cdot Fm. \qquad (2.1)$$

By definition of $\varphi$ we have $\varphi \cdot Fw_{k,\omega} = w_{k+1,\omega}$ (Notation 2(1)), thus,

$$m \cdot w_{k+1,\omega} = v_{i+1,i} \cdot Fm \cdot Fw_{k,\omega}. \qquad (2.2)$$
Assuming the above square commutes for $k$, we prove it for $k+1$:

$$
\begin{align*}
F^{k+1}! &= F(v_{i,k} \cdot m \cdot w_{k,\omega}) & \text{induction hypothesis} \\
&= v_{i+1,k+1} \cdot Fm \cdot Fw_{k,\omega} & v_{i+1,k+1} = Fv_{i,k} \\
&= v_{i,k+1} \cdot v_{i+1,i} \cdot Fm \cdot Fw_{k,\omega} & \\
&= v_{i,k+1} \cdot m \cdot w_{k+1,\omega} & \text{by (2.2)}
\end{align*}
$$

Since $v_{i,k}$ is the composite $v_{\omega,k} \cdot v_{i,\omega}$, we obtain the following corollary of
Theorem 8:

**Corollary 10** If the initial object is simple, then the following monomorphism

$$
\bar{u} \equiv \mu F \xrightarrow{m} F^i 1 \xrightarrow{v_{i,\omega}} F^{\omega} 1
$$

makes the squares below commutative

$$
\begin{tikzcd}
& & \mu F \arrow[r, "\bar{u}"] \arrow[d, "w_{k,\omega}"] & F^k 1 \arrow[d, "v_{i,k}"] \\
F^k 0 \arrow[r, "F^{k!}"] & & F^k 1 & \\
& & &
\end{tikzcd}
\qquad (k < \omega)
$$

3 Approximate Homomorphisms

**Assumption 11** Throughout the rest of the paper $\mathcal{K}$ denotes a strongly lfp category with a simple initial object, and $F$ a finitary endofunctor preserving monomorphisms.

Recall that the initial algebra $\mu F$ is a canonical subobject of the terminal coalgebra $\nu F$ (Proposition 4). For the forgetful functor of Notation 7 we present a canonical ultrametric on the underlying set $U(\nu F)$ of the terminal coalgebra. Then $U(\mu F)$ is a subspace of that ultrametric space, since $U$ preserves monomorphisms. We prove that those two ultrametric spaces have the same Cauchy completion. Moreover, given an arbitrary coalgebra $\alpha: A \to FA$, the unique homomorphism into $\nu F$ is determined by a Cauchy sequence of (approximate) morphisms from $A$ to $\mu F$.

*Remark 4.* (1) Recall that a metric *d* is called an *ultrametric* if the triangle inequality can be strengthened to *d(x, z) ≤ max(*d(x, y)*, *d(y, z*)). We denote by **UMet** the category of ultrametric space with distances at most 1 and non-expanding functions. That is, functions *f*: (*X*, *d*) → (*X*', *d*') with *d(x, y) ≥ d'(f(x), f(y))* for all *x*, *y* ∈ *X*.
(2) The category **UMet** has products w.r.t. the supremum metric. In particular, for every set $M$ the power $(X, d)^M$ is the ultrametric space of all functions $f: M \to X$ with distances given by

$$d(f, f') = \sup_{m \in M} (d(f(m), f'(m))) \quad \text{for } f, f' \in X^M.$$

(3) Completeness of an ultrametric space means that every Cauchy sequence has a limit. Every $\omega^{\text{op}}$-sequence of morphisms $a_{k+1,k}: A_{k+1} \to A_k$ ($k < \omega$) in **Set** carries a canonical complete ultrametric on its limit $A = \lim_{k<\omega} A_k$ in **Set** (with limit projections $a_k: A \to A_k$)): Given elements $x \neq y$ of $A$, their distance is defined by

$$d(x, y) = 2^{-k}$$

for the least $k$ with $a_k(x) \neq a_k(y)$. It is easy to verify that $(A, d)$ is a complete ultrametric space, see also [4], Lemma 32.

(4) We apply this to the limit $F^1 = \lim_{n<\omega} F^n$ of Notation 2(2). Since the forgetful functor $U = \mathcal{K}(G, -)$ preserves limits, $U(F^1)$ is a limit with projections $Uv_{\omega,k}$ ($k < \omega$).

**Corollary 12** *The underlying set of $F^1$ carries the following complete ultrametric: given distinct elements $x, y: G \to F^1$ of $U(F^1)$, their distance is $2^{-k}$ for the least $k$ with $v_{\omega,k} \cdot x \neq v_{\omega,k} \cdot y$.*

The monomorphisms

$$m: \mu F \to \nu F \quad \text{and} \quad v_{i,\omega}: \nu F \to F^1$$

of Proposition 4 and Theorem 3 are preserved by $U$, thus we have ultrametric subspaces $U(\mu F) \subseteq U(\nu F) \subseteq U(F^1)$.

**Examples 13** (1) For the set functor $FX = \Sigma \times X + 1$ (whose coalgebras are dynamic systems with inputs from $\Sigma$ and terminating states) the terminal-coalgebra chain

$$1 \leftarrow \Sigma + 1 \leftarrow \Sigma \times \Sigma + \Sigma + 1 \leftarrow \dots$$

is given by $F^k 1 = \text{words of length} \leq k$. And $v_{k+1,k}$ deletes the first letter in every word of length $k+1$. The limit of this $\omega^{\text{op}}$-sequence is

$$\nu F = F^1 = \Sigma^\omega + \Sigma^*.$$

The projection $v_{\omega,k}$ leaves words of length $\leq k$ unchanged and otherwise forms prefixes of length $k$. Thus the distance of distinct words is $2^{-k}$ for the least $k$ for which their prefixes of length at most $k$ are distinct.

The initial-algebra chain

$$0 \to 1 \to \Sigma + 1 \to (\Sigma \times \Sigma) + \Sigma + 1 \to \dots$$
is given by $F^k 0 = \text{words of length less than } k$. And $w_{k,k+1}$ is the inclusion. This
yields the colimit

$\mu F = \Sigma^*$

with the above ultrametric.

(2) More generally, given a set $B$, then $FX = \Sigma \times X + B$ has the terminal coalgebra $\nu F = \Sigma^\omega + \Sigma^* \times B$. Words in $\Sigma^* \times B$ with distinct $B$-components have distance 1, otherwise the ultrametric is analogous to (1). And $\mu F = \Sigma^* \times B$.

(3) Deterministic automata with the input alphabet $\Sigma$ are coalgebras of the
set functor $FX = \{0,1\} \times X^{\Sigma}$. The terminal-coalgebra chain

$$
1 \leftarrow \{0,1\} \leftarrow \{0,1\}^{1+\Sigma} \leftarrow \{0,1\}^{1+\Sigma+\Sigma^2} \leftarrow \dots
$$

is given by powers of $\{0,1\}$ to $\coprod_{n=0}^k \Sigma^n$. Thus, $F^k 1$ are all formal languages using words of length at most $k$. And $v_{k+1,k}$ deletes the first letter in every word of length $k+1$. Since $F$ preserves limits of $\omega^{op}$-sequences, we have

$$
\nu F = F^{\omega} 1 = \text{all formal languages.}
$$

The distance of distinct languages is $2^{-k}$ for the least $k$ such that there is a
word of length $k$ lying in precisely one of those languages. Here $\mu F = \emptyset$.

(4) Weighted automata with weights in a finite semiring $\mathbb{S}$ and the input alphabet $\Sigma$ are coalgebras for the endofunctor of $\mathbb{S}\text{-Mod}$ defined by $FX = \mathbb{S} \times X^{\Sigma}$. The terminal-coalgebra chain is given by left-hand projections $\pi_1$:

$$
1 \leftarrow \pi_1=0 \quad \mathbb{S} \leftarrow \pi_1 \quad \mathbb{S} \times \mathbb{S}^{\Sigma} \leftarrow \pi_1 \quad (\mathbb{S} \times \mathbb{S}^{\Sigma}) \times \mathbb{S}^{\Sigma \times \Sigma} \simeq \mathbb{S}^{1+\Sigma+\Sigma^2} \leftarrow \pi_1 \quad \dots
$$

This yields as $F^k 1$ the set of all weighted languages with weight 0 for all words
longer than $k$. And $v_{k+1,k}$ changes weights of words of length $k+1$ to 0. Here,
again, $F$ preserves limits of $\omega^{op}$-sequences, thus

$\nu F = F^{\omega} 1 = \mathbb{S}^{\Sigma^{*}}$

the set of all weighted languages. The distance of distinct languages is $2^{-k}$ for
the least $k$ with their $k$-components distinct.

The initial-algebra chain has the same objects, and $w_{k,k+1}$ are the coproduct
injections (using that in $\mathbb{S}\text{-Mod}$ we have $A+B = A \times B$). Thus the initial
algebra is

$$
\mu F = \text{all bounded weighted languages,}
$$

where bounded means that for some number $k$ all words of nonzero weight have
length at most $k$.

(5) Let $\Gamma$ be a signature, $\Gamma = (\Gamma_n)_{n \in \mathbb{N}}$. The polynomial set functor $H_{\Gamma} X = \coprod_{n \in \mathbb{N}} \Gamma_n \times X^n$ has the terminal coalgebra $\nu H_{\Gamma}$ consisting of all $\Gamma$-trees, i.e., trees labelled by $\Gamma$ so that a node with a label in $\Gamma_n$ has $n$ successors. (We always
consider trees up to isomorphism.) We can represent $H_{\Gamma}^{k}0$ by the set of all $\Gamma$-trees of height less than $k$, thus the colimit

$$ \mu H_{\Sigma} = \bigcup_{k \in \mathbb{N}} H_{\Gamma}^{k} 0 $$

is given by all finite $\Gamma$-trees.

The distance of trees $t \neq s$ in $\nu H_{\Gamma}$ is $2^{-k}$ for the least $k$ such that by cutting $t$ and $s$ at level $k$ one obtains distinct trees.

**Remark 5.** Example (1) above generalizes to all strongly lfp categories whose forgetful functor $U = \mathcal{K}(G, -)$ preserves finite coproducts, e.g. **Pos** and **Gra**. Given an object $\Sigma$, the functor $FX = X \times \Sigma + 1$ is finitary and the forgetful functor $U$ (preserving all limits) takes the terminal-coalgebra chain

$$ 1 \leftarrow \Sigma + 1 \leftarrow \Sigma \times \Sigma + \Sigma + 1 \leftarrow \dots $$

in $\mathcal{K}$ to the terminal-coalgebra chain of the set-functor $(-) \times U\Sigma + 1$. The terminal coalgebra $\nu F$ has the underlying set $U(\nu F) = (U\Sigma)^{\omega} + (U\Sigma)^{*}$, and the distance of words is as described above. If, moreover, $G$ is a finitely presentable generator (which is true in all of our examples), then $U$ also takes the initial-algebra chain of $F$ to that of the set functor $(-) \times U\Sigma + 1$. Thus, $U(\mu F) = (U\Sigma)^{*}$.

**Definition 14** An endofunctor $F$ is grounded if $F0$ has a global element, i.e., a morphism $p: 1 \to F0$ is given.

**Proposition 15** The ultrametric subspace $U(\mu F)$ is dense in $U(\nu F)$ whenever $F$ is grounded. These two spaces have the same Cauchy completion, viz, $U(F^{\omega}1)$.

*Proof.* (1) We prove that the embedding $U\bar{u}: U(\mu F) \to U(F^{\omega}1)$, see Corollary 10, is dense. Since $U(F^{\omega}1)$ is complete, both statements above follow from this fact. Thus given an element $x: G \to F^{\omega}1$ of $U(F^{\omega}1)$, we are to present a sequence $x_k: G \to F^{\omega}1$ ($k < \omega$) of morphisms factorizing through $\bar{u}$ with $x = \lim_{k \to \infty} x_k$ in the supremum metric of Remark 4(2).

(2) For every $k < \omega$ consider the following endomorphism of $F^{\omega}1$ using the global element $p: 1 \to F0$:

$$ r_k \equiv F^{\omega}1 \xrightarrow{v_{\omega,k}} F^k 1 \xrightarrow{F^{k}p} F^{k+1} 0 \xrightarrow{w_{k+1,\omega}} F^{\omega} 0 \xrightarrow{\bar{u}} F^{\omega} 1. \quad (3.1) $$

It fulfils, due to Corollary 10

$$ v_{\omega,k+1} \cdot r_k = F^{k+1}! \cdot F^k p \cdot v_{\omega,k}. \quad (3.2) $$

In Notation 2 we see that $v_{k+1,k} = F^k v_{1,0}$, thus the (obvious) equality $v_{1,0} \cdot F! \cdot p = \mathrm{id}_1$ yields

$$ v_{k+1,k} \cdot F^{k+1}! \cdot F^k p = \mathrm{id}_{F^k 1}. \quad (3.3) $$

Consequently

$$ v_{\omega,k} \cdot r_k = v_{\omega,k}. \quad (3.4) $$
Indeed, by (3.2) and $v_{\omega,k} = v_{k+1,k} \cdot v_{\omega,k+1}$ we see that the left-hand side is $v_{k+1,k} \cdot F^{k+1} \cdot F^k p \cdot v_{\omega,k}$ which is $v_{\omega,k}$ by (3.3).

(3) The desired sequence is

$$x_k = r_k \cdot x.$$

It converges to $x$ because (3.4) yields $v_{\omega,k} \cdot (r_k \cdot x) = v_{\omega,k} \cdot x$, thus $d(r_k \cdot x, x) < 2^{-k}$. And since $r_k$ factorizes through $\bar{u}$, this concludes the proof.

The following corollary was already proved by Barr [11]:

**Corollary 16** If, moreover, $F$ preserves limits of $\omega^{\text{OP}}$ sequences, then the ultrametric space corresponding to $\nu F$ is the Cauchy completion of the subspace $\mu F$.

For every coalgebra $\alpha: A \to FA$ carried by a set $M = UA$ the unique coalgebra homomorphism $h: A \to \nu F$ lies in the metric space $U(\nu F)^M$, see Remark 4(2). And $U(\mu F)^M$ is a subspace via the post-composition with $m$ of Proposition 4. We are going to prove that $h$ is the limit of a canonical Cauchy sequence in the subspace $U(\mu F)^M$.

**Definition 17** For every coalgebra $(A, \alpha)$ we define the sequence $h_k: A \to \mu F$ ($k < \omega$) of approximate homomorphisms by induction as follows

$$h_0 \equiv A \xrightarrow{!} 1 \xrightarrow{p} F 0 \xrightarrow{w_{1,\omega}} \mu F$$

and

$$h_{k+1} \equiv A \xrightarrow{\alpha} F A \xrightarrow{Fh_k} F(\mu F) \xrightarrow{\varphi} \mu F. \qquad (3.5)$$

Thus $h_0$ is a trivial approximation, independent of the given coalgebra structure: it just uses the global element $p$. Given an approximation $h_k$, the next one is given by a square similar to the square defining coalgebra homomorphisms:

$$\begin{tikzcd}
A \arrow[r, "h_{k+1}", "\alpha"] & \mu F \arrow[d, "\varphi^{-1}"] \\
FA \arrow[r, "Fh_k"] & F(\mu F)
\end{tikzcd}$$

Let us remark that we do not claim that $h_k$ are coalgebra homomorphisms.

**Proposition 18** For every coalgebra $(A, \alpha)$ on the set $M = UA$ the unique coalgebra homomorphism $h: A \to \nu F$ is a limit of the approximate homomorphisms. More precisely: in the ultrametric space $U(\nu F)^M$ we have

$$Uh = \lim_{k \to \infty} U(m \cdot h_k).$$
*Proof.* We prove by induction on $k$ that $d(Uh, U(m \cdot h_k)) \le 2^{-k}$. This is trivial for $k=0$ (recall that we assume that all distances are at most 1). If this holds for $k$, we prove it for $k+1$. Since $h$ is a coalgebra homomorphism and we have an ordinal $i$ with $\tau^{-1} = v_{i+1,i}$ (see Theorem 3), we get

$$h = v_{i+1,i} \cdot Fh \cdot \alpha. \qquad (3.6)$$

As $m$ is an algebra homomorphism (see Proposition 4), we have

$$m \cdot \varphi = \tau^{-1} \cdot Fm = v_{i+1,i} \cdot Fm \qquad (3.7)$$

The induction hypothesis is that $v_{i,k-1}$ merges $h$ and $m \cdot h_k$:

$$v_{i,k-1} \cdot h = v_{i,k-1} \cdot m \cdot h_k \qquad (3.8)$$

and our task is to prove that $v_{i,k}$ merges $h$ and $m \cdot h_{k+1}$:

$$
\begin{align*}
v_{i,k} \cdot h &= v_{i,k} \cdot v_{i+1,i} \cdot Fh \cdot \alpha && \text{by (3.6)} \\
&= Fv_{i,k-1} \cdot Fh \cdot \alpha && v_{i,k} \cdot v_{i+1,i} = v_{i+1,k} = Fv_{i,k-1} \\
&= F(v_{i,k-1} \cdot m \cdot h_k) \cdot \alpha && \text{by (3.8)} \\
&= v_{i,k} \cdot v_{i+1,i} \cdot Fm \cdot Fh_k \cdot \alpha && \text{as above} \\
&= v_{i,k} \cdot m \cdot \varphi \cdot Fh_k \cdot \alpha && \text{by (3.7)} \\
&= v_{i,k} \cdot m \cdot h_{k+1} && \text{by (3.5)}
\end{align*}
$$

**Notation 19** Define morphisms $\partial_k: \nu F \to \mu F$ for $k < \omega$ as the following composites

$$\partial_k \equiv F^i 1 \xrightarrow{v_{i,k}} F^k 1 \xrightarrow{F^k p} F^{k+1} 0 \xrightarrow{w_{k+1,\omega}} F^\omega 0.$$

We prove below that this sequence (prolonged by the embedding $m: \mu F \to \nu F$) converges to $\mathrm{id}_{\nu F}$. The following examples give an intuition how these approximations of the identity morphism work.

**Examples 20** (1) For $FX = X \times \Sigma + B$ of Example 13(2) with a chosen element $p \in B$ the map $\partial_k: \Sigma^\omega + \Sigma^* \times B \to \Sigma^* \times B$ assigns to an infinite word $w$ the pair $(w', p)$ where $w'$ is the prefix of length $k$. And to pairs $(w, b) \in \Sigma^* \times B$ it assigns analogously $(w', p)$ if $|w| \ge k$, whereas $\partial_k(w, b) = (w, b)$ if $|w| < k$.

(2) For a polynomial functor $H_\Gamma$ of Example 13(4) we have $\partial_k: \nu H_\Gamma \to \mu H_\Gamma$ which cuts every $\Gamma$-tree at height $k$ and relabels all leaves of height $k$ by $p$ (the chosen nullary symbol).

**Lemma 21** For every $k < \omega$ we have $v_{i,k} = v_{i,k} \cdot m \cdot \partial_k$. Therefore, the sequence $m \cdot \partial_k$ converges to $\mathrm{id}_{\nu F}$ in the ultrametric space of endomorphisms of $U(\nu F)$:

$$\lim_{k \to \infty} U(m \cdot \partial_k) = \mathrm{id}_{U(\nu F)}.$$
*Proof.* It is sufficient to prove that first identity, since this implies that $\mathrm{id}_{U(\nu F)}$ and $U(m \cdot \partial_k)$ have distance smaller than $2^{-k}$.

From Notation 2 we know that $v_{i,k} = v_{k+1,k} \cdot v_{i,k+1}$. Thus

$$ 
\begin{align*}
v_{i,k} \cdot m \cdot \partial_k &= v_{k+1,k} \cdot v_{i,k+1} \cdot m \cdot w_{k+1,\omega} \cdot F^k p \cdot v_{i,k} && \text{by def. of } \partial_k \\
&= v_{k+1,k} \cdot F^{k+1}! \cdot F^k p \cdot v_{i,k} && \text{Lemma 9} \\
&= F^k (v_{1,0} \cdot F! \cdot p) \cdot v_{i,k} && \text{$v_{k+1,k} = F v_{1,0}^k$} \\
&= v_{i,k} && \text{$v_{1,0} \cdot F! \cdot p = \mathrm{id}_1$}
\end{align*}
$$

# 4 Approximate Solutions

We apply the above results to the finitary endofunctor

$$F_B = F(-) + B$$

for an arbitrary object $B$. We want $F_B$ to preserve monomorphisms whenever $F$ does. We therefore need the following (mild) additional assumption:

**Assumption 22** *Additionally to the assumptions of Section 3 we assume that $\mathcal{K}$ has monic coproduct injections and that $m + B: X + B \to Y + B$ is monic for every monomorphism $m: X \to Y$. (This holds in all Examples of 6.)*

**Notation 23** *Assume that $B$ is a pointed object, i.e., a global element $p: 1 \to B$ is given. Then $F_B$ is a grounded endofunctor w.r.t. the following global element*

$$p_B \equiv 1 \xrightarrow{p} B \xrightarrow{\mathrm{inr}} F0 + B = F_B0.$$

**Definition 24 (See [12])** *Let an algebra $\alpha: FA \to A$ be given. A (recursive) equation with an object $X$ (of recursive variables) is a morphism $e: X \to FX+A$. A solution of $e$ is a morphism $e^\dagger: X \to A$ making the following square*

<figure><img src="image_3.png" /></figure>

commutative.

An algebra in which every equation has a unique solution is said to be completely iterative.

**Examples 25 (see [12])** (1) The terminal coalgebra $\nu F$ considered as an algebra (via $\tau^{-1}$) is completely iterative.
(2) Denote by $\Psi_B$ the terminal coalgebra of the endofunctor $F_B = F(-) + B$,

$$ \Psi_B = \nu F_B . $$

Its coalgebra structure $\tau_B: \Psi B \to F(\Psi B) + B$ yields an inverse with components

$$ \psi_B: F(\Psi B) \to \Psi B \quad \text{and} \quad \eta_B: B \to \Psi B . $$

The resulting algebra $\Psi B$ for $F$ is completely iterative.

Indeed, this is the free completely iterative algebra on $B$. That is, for every completely iterative algebra $\alpha: FA \to A$ and every morphism $f: B \to A$ there exists a unique algebra homomorphism $f^\# : \Psi B \to A$ with $f = f^\# \cdot \eta_B$.

(3) Let us illustrate the iterativity of $\Psi B$ on the set functor $FX = \Sigma \times X$ where $\Sigma = \{\sigma, \tau\}$. From Example 13(2) we know that $\Psi B = \Sigma^\omega + \Sigma^* \times B$. Let $e$ be the following equation with recursive variables $X = \{x, y, z\}$:

$$ e(x) = (\sigma, y), \quad e(y) = (\tau, x) \quad \text{and} \quad e(z) = (\sigma\tau, b). $$

The solution $e^\dagger: X \to \Sigma^\omega + \Sigma^* \times B$ is, clearly, given by

$$ e^\dagger(x) = (\sigma\tau)^\omega, \quad e^\dagger(y) = (\tau\sigma)^\omega \quad \text{and} \quad e^\dagger(z) = (\sigma\tau, b). $$

For a general equation $e: X \to \Sigma \times X + (\Sigma^\omega + \Sigma^* \times B)$ the solution $e^\dagger: X \to \Sigma^\omega + \Sigma^* \times B$ is defined by the following corecursion: if $e(x)$ lies in the right-hand summand $\Sigma^\omega + \Sigma^* \times B$ then simply $e^\dagger(x) = e(x)$. Otherwise we have a pair $(\sigma_1, x_1) \in \Sigma \times X$ with $e(x) = (\sigma_1, x_1)$ and $e^\dagger$ assigns to $x$ the word assigned to $x_1$ with the prefix $\sigma_1$ added:

$$ e^\dagger(x) = \sigma_1 e^\dagger(x_1). $$

(4) Given an arbitrary polynomial functor $H_\Gamma$ of Example 13(5) the functor $H_\Gamma(-) + B$ is also polynomial for the signature $\Gamma + B$, where $B$ consists of constants. Thus $\Psi B$ is the algebra for all $\Gamma$-trees over $B$, i.e., leaves are labelled in the set $\Gamma_0 + B$ and nodes with $n > 0$ successors in $\Gamma_n$.

A solution of an equation $e: X \to H_\Gamma X + (B + \Psi B)$ is the map $e^\dagger: X \to B + \Psi B$ assigning to a variable $x$ with $e(x)$ in the right-hand summand the value $e^\dagger(x) = e(x)$. For the left-hand summand we have

$$ e(x) = \sigma(x_1, \dots, x_n) $$

for some $n$-ary symbol $\sigma$, and $e^\dagger(x)$ is the tree with root labelled by $\sigma$ and with the $n$ maximum subtrees given by $e^\dagger(x_1)), \dots, e^\dagger(x_n)$.

**Remark 6.** For the terminal coalgebra $\nu F$ considered as an algebra we now show how solutions of equations $e: X \to FX + \nu F$ can be approximated by sequences of morphisms $e_k^\dagger: X \to \mu F$ into the intial algebra. Recall that the morphisms
$\partial_k: \nu F \to \mu F$ of Lemma 21 converge to $\text{id}_{\nu F}$. This indicates that the equation morphism $e$ is well approximated by the following sequence of equation morphisms in $\mu F$:

$$e_k \equiv X \xrightarrow{e} FX + \nu F \xrightarrow{FX+\partial_k} FX + \mu F \quad (k < \omega). \quad (4.1)$$

We use them to define approximate solutions of $e$:

**Definition 26** Let an equation in $\nu F$ be given, $e: X \to FX + \nu F$. We define its approximate solutions $e_k^\ddagger: X \to \mu F$ by induction as follows: first put

$$e_0^\ddagger \equiv X \xrightarrow{!} 1 \xrightarrow{p} F0 \xrightarrow{w_1, \omega} \mu F. \quad (4.2)$$

Given $e_k^\ddagger$ define $e_{k+1}^\ddagger$ as the following composite:

$$\begin{tikzcd}
& & X \arrow[r, "e_{k+1}^\ddagger"] & \mu F \arrow[d, "e_k"] \\
FX + \mu F & & & F(e_k^\ddagger + \mu F) + \mu F \arrow[u, "\varphi, \mu F"]
\end{tikzcd} \quad (4.3)$$

where $e_k = (FX + \partial_k) \cdot e$.

Observe that the first approximation $e_0^\ddagger$ does not use the algebra structure of $\mu F$. For the subsequent approximations the square defining solutions in Definition 24 is quite analogous to (4.4). We see that, however, $e_k^\ddagger$ is not a solution of $e_k$ in $\mu F$ in general.

**Proposition 27** The solution of every equation $e: X \to FX + \nu F$ in the terminal coalgebra (considered as algebra) is a limit of approximate solutions. More precisely, we have

$$Ue^\dagger = \lim_{k \to \infty} U(m \cdot e_k^\ddagger).$$

in the power of the ultrametric space $U(\nu F)$ to $UX$.

We are going to prove a more general result about approximate solutions for equation in $\Psi B$, the free completely iterative algebra, below. Since for $B = 0$ we have $\nu F = \Psi 0$, the above proposition then follows.

**Examples 28** Consider the equation of Example 25(3). We are given a pointed set $B$ with $p \in B$. Here $e_0^\ddagger$ is constant with the value $(\varepsilon, p) \in \Sigma^* \times B$, thus, $e_1^\ddagger$ takes $x$ and $z$ to $(\sigma, p)$ and $y$ to $(\tau, p)$, using the first letter of the value of $e^\dagger$. Then $e_2^\ddagger$ takes $x$ to $(\sigma\tau, p)$ and $y$ to $(\tau\sigma, p)$, whereas $z$ is taken to $(\sigma\tau, b)$. In general, $e_k^\ddagger$ for $k \ge 2$ takes $x$ and $y$ to $(w, p)$ where $w$ is the prefix of length $k$ of $(\sigma\tau)^\omega$ and $(\tau, \sigma)^\omega$, resp., and it takes $z$ to $(\sigma\tau, b)$.
**Notation 29** The free algebra on an object B is denoted by $\Phi B$. We show below that this is precisely the initial algebra of $F_B$:

$$ \Phi B = \mu X.FX + B. $$

The components of the algebra structure $F(\Phi B) + B \to \Phi B$ are denoted by $\varphi_B: F(\Phi B) \to \Phi B$ and $\eta'_B: B \to \Phi B$, resp. The first one makes $\Phi B$ an algebra for $F$.

The algebra $\Phi B$ is free on $B$ w.r.t. $\eta'_B: B \to \Phi B$. Indeed, given an algebra $\alpha: FA \to A$ for $F$ together with a morphism $f: B \to A$, we obtain an algebra $[\alpha, f]: FA + B \to A$ for $F_B$. And a morphism $h: \Phi B \to A$ is a homomorphism for $F_B$ iff it is a homomorphism for $F$ satisfying $h \cdot \eta'_B = f$.

We now proceed analogously to Definition 26, defining approximate solutions of equations in $\Psi B$. This means that we move from $F$ to $F_B$. Let $\partial_k^B: \Psi B \to \Phi B$ be the morphisms of Notation 19 related to $F_B$. Then every equation morphism $e: X \to F_B X + \Psi B$ yields morphisms

$$ e_k = (F_B X + \partial_k^B) \cdot e: X \to FX + \Phi B $$

as in (4.1) above.

**Definition 30** Let $B$ be a pointed object. For every equation $e: X \to FX + \Psi B$ in the free completely iterative algebra its approximate solutions in the free algebra $\Phi B$ are the morphisms $e_k^\dagger: X \to \Phi B$ defined by induction as follows: first put

$$ e_0^\dagger \equiv X \xrightarrow{!} 1 \xrightarrow{p_B} F_B 0 \xrightarrow{w_{1,\omega}} \mu F_B = \Phi B. $$

Given $e_k^\dagger$ define $e_{k+1}^\dagger$ as the following composite

$$ \begin{tikzcd} & & \Phi B \arrow[r] \arrow[d, "e_k^\dagger"] & X \arrow[r, "e_{k+1}^\dagger"] & \Phi B \arrow[d, "[\varphi_B, \Phi B]"'] \\ FX + \Phi B \arrow[r, "Fe_k^\dagger+\Phi B"'] & F(\Phi B) + \Phi B & & & \end{tikzcd} \quad (4.4) $$

We denote by $m_B: \Phi B \to \Psi B$ the morphism of Proposition 4 related to the functor $F_B$.

**Theorem 31.** The solution of every equation $e: X \to FX + \Psi B$ in the free completely iterative algebra $\Psi B$ is a limit of the sequence of approximate solutions $e_k^\dagger: X \to \Phi B$ in the free algebra $\Phi B$. More precisely

$$ U e^\dagger = \lim_{k \to \infty} U(m_B \cdot e_k^\dagger). $$

in the power of the ultrametric space $U(\Psi B)$ to $UX$.
*Proof.* There is an ordinal $i$ with $\Psi B = F_B^i 1$, see Theorem 3 applied to $F_B$, and for the connecting morphism $v_{i,k}: F_B^i 1 \to F_B^k 1(k < \omega)$ we prove $v_{i,k} \cdot e^\dagger = v_{i,k} \cdot m_B \cdot e_k^\dagger$. Then the statement follows since $Ue^\dagger$ has distance less than $2^{-k}$ from $U(m_B \cdot e_k^\dagger)$. We proceed by induction, the case $k=0$ is trivial.

From $v_{i,k} \cdot m_B \cdot e_k^\dagger = v_{i,k} \cdot e^\dagger$ we derive $v_{i,k+1} \cdot m_B \cdot e_{k+1}^\dagger = v_{i,k+1} \cdot e^\dagger$ as follows. By definition of $e_k$ and $e_k^\dagger$ the left-hand side is

$$v_{i,k+1} \cdot m_B \cdot [\varphi_B, \Phi B] \cdot (Fe_k^\dagger + \Phi B) \cdot (FX + \partial_k^B) \cdot e.$$

Recall from (2.1) that $m_B \cdot \varphi_B = v_{i+1,i} \cdot Fm_B$. Thus,

$$v_{i,k+1} \cdot m_B \cdot \varphi_B = v_{i+1,k+1} \cdot Fm_B = F(v_{i,k} \cdot m_B).$$

The left-hand side can thus be simplified to

$$[F(v_{i,k} \cdot m_B), v_{i,k+1} \cdot m_B] \cdot (Fe_k^\dagger + \partial_k^B) \cdot e = [F(v_{i,k} \cdot m_B \cdot e_k^\dagger), v_{i,k+1} \cdot m_B \cdot \partial_k^B] \cdot e.$$

By induction hypothesis and Lemma 21 this yields

$$v_{i,k} \cdot m_B \cdot e_k^\dagger = [F(v_{i,k} \cdot e^\dagger), v_{i,k+1}] \cdot e.$$

The right-hand side yields the same result. Indeed, we have

$$v_{i,k+1} \cdot e^\dagger = v_{i,k+1} \cdot [\tau_B^{-1}, \Psi B] \cdot (Fe^\dagger + \Psi B) \cdot e$$

by definition of $e^\dagger$. Since $\tau_B^{-1} = v_{i+1,i}$ and $v_{i+1,k+1} = Fv_{i,k}$, we get

$$v_{i,k+1} \cdot e^\dagger = [F(v_{i,k} \cdot e^\dagger), v_{i,k+1}] \cdot e.$$

A completely analogous result holds for solutions in the free iterative algebra on $B$ which we denote by $RB$. Recall from [7] that the difference between 'iterative' and 'completely iterative' is the restriction of the objects $X$ of recursive variables to finitely presentable ones:

**Definition 32 (see [7])** An algebra $\alpha$: $FA \to A$ is called iterative if every equation morphism $e$: $X \to FX + A$ with a finitely presentable object $X$ has a unique solution.

**Examples 33 (see [7])** (1) In Example 13(3) we have seen that for deterministic automata all formal languages form the terminal coalgebra. Here $\rho F$ consists of all the regular languages.

(2) The colimit $\varrho F$ of all coalgebras $\gamma$: $C \to FC$ with $C$ finitely presentable is an iterative algebra. More precisely, denote by $\gamma^\#$: $C \to \varrho F$ the colimit cone. The unique morphism $i$: $\varrho F \to F(\varrho F)$ making all $\gamma^\#$ coalgebra homomorphisms is invertible. And the algebra $(\varrho F, i^{-1})$ is iterative. Indeed, this is the initial iterative algebra.

(3) As a concrete example, for the polynomial functor $H_\Gamma$ we have seen that the terminal coalgebra consists of all $\Gamma$-trees. $\rho H_\Gamma$ is the subcoalgebra of
all rational trees, which are those having up to isomorphism only finitely many
subtrees. Thus e.g. for the set functor $FX = \Sigma \times X + B$ we have $\wp F$ as the
subalgebra of $\nu F = \Sigma^\omega + \Sigma^* \times B$ (see Example 13(2)) consisting of all eventually
periodic words in $\Sigma^\omega$ (i.e., words of the form $\nu u^\omega$) and all elements of $\Sigma^* \times B$.

**Notation 34** (1) The initial iterative algebra of $F_B = F(-) + B$ is denoted by $RB = \wp F_B$. Its algebra structure $F(RB) + B \to RB$ has components denoted by $i_B: F(RB) \to RB$ and $\hat{\eta}: B \to RB$.

(2) We denote by $\bar{m}_B: \Phi B \to RB$ the unique algebra homomorphism for $F_B$ and by $s_B: RB \to \Psi B$ the unique coalgebra homomorphism. Since $\Psi B$ is a terminal coalgebra, the homomorphism $m_B: \Phi B \to \Psi B$ is their composite:

$m_B = s_B \cdot \bar{m}_B .$

Since $m_B$ is monic by Proposition 4, we see that $\bar{m}_B$ is monic.

For the functor $H_\Gamma$ of Example 13(5) $s_B: RB \to \Psi B$ is the inclusion of the set of all rational $\Gamma$-trees on $B$.

**Proposition 35 ([7], 3.9)** *The algebra $i_B: F(RB) \to RB$ is a free iterative algebra for $F$ w.r.t. $\hat{\eta}: B \to RB$. If finitely generated objects of $\mathcal{K}$ coincide with finitely presentable ones, then $s_B: RB \to \Psi B$ is a monomorphism.*

Thus, we have subobjects $\Phi B \xrightarrow{\bar{m}_B} RB \xrightarrow{s_B} \Psi B$ and $U(RB)$ is a canonical ultrametric space, as a subspace of $U(\Psi B)$.

**Definition 36** Let $e: X \to FX+RB$ be an equation in the free iterative algebra with $X$ finitely presentable. We define equations $e_k$ in the free algebra $\Phi B$ as follows:

$$
e_k \equiv X \xrightarrow{e} FX + RB \xrightarrow{FX+s_B} FX + \Psi B \xrightarrow{FX+\partial_k} FX + \Phi B
$$

The approximate solutions $e_k^\dagger: X \to \mu F$ of $e$ are then defined as in Definition 26.

**Corollary 37** Suppose that finitely generated and finitely presentable objects coincide. For every equation $e: X \to FX + RB$ in the free iterative algebra ($X$ finitely presentable), its solution is a limit of approximate solutions in the free algebra. More precisely

$$
U e^{\dagger} = \lim_{k \to \infty} U(\bar{m}_B \cdot e_k^{\dagger}).
$$

in the power of the ultrametric space $U(RB)$ to $UX$.

This follows from Theorem 31 applied to the equation

$$
\bar{e} \equiv X \xrightarrow{e} FX + RB \xrightarrow{FX+s_B} FX + \Psi B.
$$

Indeed, on the one hand, we have $\bar{e}_k^\dagger = e_k^\dagger$ for every $k$ (by an easy induction).
We verify below that $\bar{e}^\dagger = s_B \cdot e^\dagger$. Then the corollary follows from $m_B = s_B \cdot \bar{m}_B$
since $s_B$ is monic.
Thus we are to prove that $s_B \cdot e^\dagger$ solves $\bar{e}$. This is clear from the diagram below

<figure><img src="image_4.png" /></figure>

Indeed, the left-hand square commutes since $e^\dagger$ solves $e$, the right-hand part commutes since $s_B: (RB, i_B^{-1}) \to (\psi B, \tau_B^{-1})$ is a homomorphism of algebras for $F_B$. The lower part clearly commutes. Thus, the outward square commutes, and its left-hand vertical arrow is $\bar{e}$.

# 5 Conclusions

We have studied colagebras for finitary endofunctors preserving monomorphisms on a wide collection of categories such as sets, vector spaces, posets, boolean algebras etc. Each such endofunctor $F$ carries a canonical ultrametric on the underlying set of the terminal coalgebra $\nu F$. Moreover, if $F$ is grounded, i.e., $F0$ has a global element, the underlying set of the initial algebra $\mu F$ is a dense subspace of that ultrametric space. Given a coalgebra on an object $A$, we have presented a canonical Cauchy sequence of morphisms from $A$ to $\mu F$ which converges to the unique coalgebra homomorphism from $A$ to $\nu F$ in the power of the above ultrametric space $\nu F$.

For every pointed object $B$ we formed the free iterative algebra $RB$ and the free completely iterative algebra $\Psi B$ on $B$. We derived a canonical ultrametric on the underlying set of each of them. And the free $F$-algebra $\Phi B$ forms a dense subspace of both $RB$ and $\Psi B$. Moreover, for every recursive equation $e$ in $\Psi B$ we have presented a canonical Cauchy sequence of morphisms into $\Phi B$ converging to the unique solution $e^\dagger$ of $e$ in $\Psi B$ (again, in the corresponding power of the space $U(\Psi B)$). Analogously for recursive equations with finitely presentable variable-objects in the algebra $RB$.

# References

1. J. Adámek. Free algebras and automata realizations in the language of categories. *Comment. Math. Univ. Carolinae*, 15:589–602, 1974.

2. J. Adámek. Final coalgebras are ideal completions of initial algebras. *J. Logic Comput.*, 2:217–242, 2002.
3. J. Adámek. On final coalgebras of continuous functors. *Theoret. Comput. Sci.*, 294:3–29, 2003.

4. J. Adámek. On terminal coalgebras derived from initial algebras. In *Proc. Coalgebraic and Algebraic Methods in Computer Science (CALCO 2019), LIPIcs*, volume 139, 2019.

5. J. Adámek. On free completely iterative algebras. In *Proc. Computer Science Logic (CSL 2020), LIPIcs*, volume 152, 2020.

6. J. Adámek, S. Milius, L. Sousa, and T. Wißmann. On finitary functors. *Theory Appl. Categ.*, 34:1134–1164, 2019.

7. J. Adámek, S. Milius, and J. Velebil. Iterative algebras at work. *Math. Structures Comput. Sci.*, 16:1085–1131, 2006.

8. J. Adámek and J. Rosický. *Locally presentable and accessible categories*. Cambridge University Press, 1994.

9. J. Adámek and V. Trnková. *Automata and Algebras in Categories*. Kluwer Acad. Publ., London, 1990.

10. J. Adámek and V. Trnková. Relatively terminal coalgebras. *J. Pure Appl. Algebra*, 216:1887–1895, 2012.

11. M. Barr. Terminal coalgebras in well-founded set theory. *Theoret. Comput. Sci.*, 114:299–315, 1993.

12. S. Milius. Completely iterative algebras and completely iterative monads. *Information and Computation*, 196:1–41, 2005.

13. J. Rutten. Universal coalgebra. *Theoret. Comput. Sci.*, 249:3–80, 2000.

14. J. Worrell. On the final sequence of a finitary set functor. *Theoret. Comput. Sci.*, 338:184–199, 2005.