# On Finitary Functors and Their Presentations

Jiří Adámek, Stefan Milius, Lawrence S. Moss

► To cite this version:

Jiří Adámek, Stefan Milius, Lawrence S. Moss. On Finitary Functors and Their Presentations. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. pp.51-70, 10.1007/978-3-642-32784-1_4 . hal-01539879

HAL Id: hal-01539879

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

Submitted on 15 Jun 2017

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>
# On Finitary Functors and Their Presentations

Jiří Adámek¹, Stefan Milius¹, and Lawrence S. Moss²

¹ Institut für Theoretische Informatik, Technische Universität Braunschweig, Germany
{J.Adamek,S.Milius}@tu-bs.de

² Department of Mathematics, Indiana University, Bloomington, IN, USA
lsm@indiana.edu

**Abstract.** Finitary endofunctors of locally presentable categories are proved to have equational presentations. Special attention is paid to the Hausdorff functor of non-empty compact subsets of a complete metric space.

*Key Words:* Finitary functors, Hausdorff functor, presentation of functors

## 1 Introduction

Finitary endofunctors, i.e., those preserving filtered colimits, play an important role in algebra and coalgebra. One indication of this is the sufficient conditions for the existence of initial algebras and final coalgebras: the initial algebra for a finitary functor $F$ always exists and it is the colimit

$$ \mu F = \colim_{n<\omega} F^n 0 $$

of the initial $\omega$-chain

$$ 0 \xrightarrow{\omega} F0 \xrightarrow{F\omega} FF0 \xrightarrow{FF\omega} \dots $$

see [2]. The final coalgebra exists whenever the base category is locally presentable, as proved by M. Makkai and R. Paré [11], see a shorter argument for the category of sets in [6]. Moreover, if $F$ preserves monomorphisms, the final coalgebra has, for some ordinal $\alpha$, the form

$$ \nu F = \lim_{n<\alpha} F^n 1 $$

of the limit of the dual (op-)chain of length $\alpha$, see [5].

This paper presents some new results on finitary endofunctors. First, every finitary endofunctor of a locally finitely presentable category has a presentation by operations and equations. This is based on the idea of a (finitary) signature in a category due to M. Kelly and J. Power [9]. We then turn to an endofunctor of the category CMS of complete metric spaces of special interest: the Hausdorff
functor $\mathcal{H}$ assigning to every space $X$ the space $\mathcal{H}X$ of all non-empty compact subsets of $X$ with the Hausdorff metric. F. van Breugel et al [8] proved that $\mathcal{H}$ is a $\lambda$-accessible functor for some cardinal $\lambda$. We sharpen their result here by proving that $\mathcal{H}$ is finitary.

**Related Work.** Section 4 on presentation of functors is closely related to the recent paper of A. Kurz and J. Velebil [12]. When the preliminary version of Section 4 was presented at the PSSL Workshop in Braunschweig in April 2010, J. Velebil told us about his parallel joint work and sent us a preliminary version of the above paper. Since our presentation is quite different, we decided not to change our section. We are grateful to J. Velebil for his comments on the formulation of that section.

## 2 Locally Presentable Categories

This is a preliminary section: we recall the concept of a locally finitely presentable and locally countably presentable category and mention examples we use throughout the paper.

Recall that a category is *filtered* if every finite subcategory has a cocone in it, and *filtered colimits* are colimits of diagrams with filtered domains. A *funitary* functor is a functor $F: \mathcal{A} \to \mathcal{B}$ such that $\mathcal{A}$ has filtered colimits and $F$ preserves them. An object $A$ of $\mathcal{A}$ is *finitely presentable* if its hom-functor $\mathcal{A}(A, -)$ is finitary.

**Definition 2.1.** A category $\mathcal{A}$ is **locally finitely presentable** if it has colimits and a set $\mathcal{F}$ of finitely presentable objects such that every object is a filtered colimit of objects from $\mathcal{F}$. We consider $\mathcal{F}$ as a full subcategory of $\mathcal{A}$.

**Examples 2.2.** (1) **Set** is locally finitely presentable; finite sets are precisely the finitely presentable objects. For $\mathcal{F}$ we can choose the set $\mathcal{F}$ of all natural numbers $n = \{0, 1, \dots, n-1\}$.

(2) **Pos**, the category of posets and order-preserving functions, is finitely presentable. Here $\mathcal{F}$ is a set of representatives of all finite (= finitely presentable) posets up to isomorphism.

(3) **K-Vec**, the category of vector spaces over the field $K$, is locally finitely presentable. Finitely presentable objects are the finite-dimensional spaces. We can put $\mathcal{F} = \{K^n; n \in \mathbb{N}\}$.

(4) If $\mathcal{A}$ is a locally finitely presentable category, then every functor category $\mathcal{A}^{\mathcal{C}}$ ($\mathcal{C}$ a small category) is also locally finitely presentable, (see [3]).

(5) The category

### MS

of metric spaces with distances in $[0, 1]$ and nonexpanding functions is not locally finitely presentable. In fact, the only finitely presentable objects are the finite discrete spaces (with all distances 0 or 1). The argument that the finitely presentable objects in **Set** are the finite sets shows that finitely presentable objects in **MS** must be finite spaces. Let $(A, d)$ be finitely presentable. Denote by $d_n$ the metric
defined by $d_n(x, y) = \min(1, d(x, y) + \frac{1}{n})$ for $x \neq y$. The $\omega$-chain of spaces $(A, d_n)$ with connecting maps $id_A$ has the filtered colimit $(A, d)$. Since the hom-functor of $(A, d)$ preserves this filtered colimit, for some $n$, $id_A: (A, d) \to (A, d)$ factorizes through the colimit map $id_A: (A, d_n) \to (A, d)$. But distances in $A$ which are strictly between 0 and 1 are increased in $A_n$. So $A$ must be discrete.

**Remark 2.3.** (1) Let $\mathcal{A}$ be a locally finitely presentable category. A finitary endofunctor $F$ is determined by its values on the full subcategory $J: \mathcal{F} \hookrightarrow \mathcal{A}$. In fact, $F$ is a left Kan extension of its domain restriction to $\mathcal{F}: F = \text{Lan}_J(F \cdot J)$. Consequently, the category $\mathcal{A}^{\mathcal{F}}$ of all functors from $\mathcal{F}$ to $\mathcal{A}$ is equivalent to the category of all finitary endofunctors of $\mathcal{A}$. Thus, the category of finitary endofunctors on a locally finitely presentable category is locally finitely presentable.

(2) For $\mathcal{A} = \mathbf{Set}$ a functor is finitary iff for every set $X$, every element of $FX$ lies in the image of $Fm$ for some finite subset $m: Y \hookrightarrow X$. For example, the finite power-set functor $\mathcal{P}_f X = \{M; M \subseteq X, M \text{ finite}\}$ is finitary. Given a set $A$, the functor $FX = X^A$ is finitary iff $A$ is finite.

**Remark 2.4.** Let $\lambda$ be a regular infinite cardinal (i.e., one that is not cofinal to any smaller cardinal). A category is called $\lambda$-filtered for an infinite cardinal $\lambda$ (*countably filtered* in the case $\lambda = \aleph_1$) if every subcategory of less than $\lambda$ morphisms (countable, in the case $\lambda = \aleph_1$) has a cocone in it. For example, $\omega$ is filtered, but not countably filtered. The first uncountable ordinal $\omega_1$ is countably filtered. A functor $F$ is called $\lambda$-accessible if its domain has $\lambda$-filtered colimits and $F$ preserves them. An object $A$ of $\mathcal{A}$ is $\lambda$-presentable if its hom-functor $\mathcal{A}(A, -)$ is $\lambda$-accessible.

**Definition 2.5.** A category $\mathcal{A}$ is called **locally $\lambda$-presentable** if it has colimits and a set $\mathcal{A}_\lambda$ of $\lambda$-presentable objects such that every object is a $\lambda$-filtered colimit of objects of $\mathcal{A}_\lambda$. In the case $\lambda = \aleph_1$ we speak about **locally countably presentable category**, and write $\mathcal{C}$ instead of $\mathcal{A}_{\aleph_1}$.

*Examples 2.6.* (1) **Set**, **Pos** and **K-Vec** are locally countably presentable (since this is weaker than locally finitely presentable). In **Set** and **Pos** the countably presentable objects are precisely the countable ones, in **K-Vec** precisely the countably dimensional spaces.

(2) The category $\omega$**CPO** of all posets with joins of increasing $\omega$-chains (and all $\omega$-continuous functions) is not locally finitely presentable: no nontrivial object is finitely presentable. However, it is locally countably presentable.

(3) The category **MS** is locally countably presentable. So is the larger category

PMS

of all pseudometric spaces (where distinct elements may have distance 0) with distances in $[0, 1]$ and nonexpanding functions. Indeed, **PMS** is obviously complete with colimits computed on the level of underlying sets (and endowed with the supremum of all pseudometrics making all colimit maps nonexpanding). Consequently, **MS** is cocomplete, since this full subcategory is reflective
in CMS (see point (4) below): a reflection of a pseudometric space $(X, d)$ is its quotient modulo the equivalence $x \sim y$ iff $d(x, y) = 0$.

Every (pseudo)metric space is a countably filtered colimit of its countable subspaces. In Lemma 2.7 we will see that these spaces are countably presentable. This proves that **MS** and **PMS** are locally countably presentable categories. In both cases $\mathcal{C}$ is a choice set of all countable spaces up to isometry.

(4) The full subcategory

CMS

of **MS** formed by all complete spaces (in which every Cauchy sequence has a limit point) is also locally countably presentable. Indeed, **CMS** is a reflective subcategory of **MS**, where the reflection of a space $(X, d)$ is its Cauchy completion $e: (X, d) \to (X^*, d^*)$. Recall that $e$ is an isometry such that every element of $X^*$ is a limit of a Cauchy sequence in $X$. For every nonexpanding function $f: (X, d) \to (Y, \bar{d})$ where $(Y, \bar{d})$ is complete we have the unique extension $f^*: X^* \to Y$ defined in $x \in X^*$ by

$$f^*(x) = \lim_{n \to \infty} f(x_n)$$

for an arbitrary Cauchy sequence $(x_n)$ converging to $x$. To see that $f^*$ is non-expanding, use that $f$ is, and that the distance of two elements $x = \lim x_n$ and $y = \lim y_n$ in $X^*$ is simply $\lim_{n \to \infty} d(x_n, y_n)$.

Thus, **CMS** is cocomplete. Choose a set $\mathcal{C}$ of representatives of all separable complete metric spaces (which means complete spaces with a countable dense subset). We prove in Corollary 2.9 below that every separable space is countably presentable in **CMS**. And every complete space $X$ is a countably filtered colimit of separable spaces: this follows from the fact that given $M \subseteq X$ countable, the closure of $M$ in $X$ is separable.

Thus, **CMS** is a locally countably presentable category.

**Lemma 2.7.** Given a countably filtered diagram in PMS with a colimit cocone

$$c_t: C_t \to C \quad (t \in T),$$

then for every countable subset $M \subseteq C$ there exists $t \in T$ and a countable subset $M' \subseteq C_t$ such that $c_t$ restricts to an isometry from $M'$ to $M$.

*Proof.* Let $d_t$ denote the pseudometric of $C_t$ and $d$ that of $C$. Since our diagram is filtered, it follows from Example 2.6(3) that for every pair $x, y \in C$ we have

$$d(x, y) = \inf d_t(x', y')$$

where $t$ ranges through $T$ and $x' \in c_t^{-1}(x)$ and $y' \in c_t^{-1}(y)$.

(a) Assume first that $M$ consists of precisely two elements, $M = \{x, y\}$. For every $n \in \mathbb{N}$ choose $t(n) \in T$ and elements $x_n \in c_{t(n)}^{-1}(x)$ and $y_n \in c_{t(n)}^{-1}(y)$ with

$$d_{t(n)}(x_n, y_n) \le d(x, y) + \frac{1}{n}. \qquad (2.1)$$
Since our diagram is countably filtered, there exists $s \in T$ and connecting morphisms $f_n: c_{t_n} \to c_s$ for all $n \in \mathbb{N}$.

The countable set $\{f_n(x_n); n \in \mathbb{N}\}$ is mapped by $c_s$ to the single element $x$, since $c_s \cdot f_n = c_{t(n)}$, thus, since our diagram is countably filtered, there exists $t \in T$ and a connecting morphism $g: C_s \to C_t$ also mapping all elements $f_n(x_n)$ to a single element $x'$ of $C_t$. Thus $c_t(x') = c_s \cdot g(x_n) = x$. Analogously for the countable set $\{f_n(y_n); n \in \mathbb{N}\}$; we can assume without loss of generality, using that our diagram is filtered, that the choice of $t$ and $g$ is the same for the latter set. Thus we have $y' \in C_t$ with $c_t(y') = c_s \cdot g(y_n) = y$. We now prove that the set $M' = \{x', y'\}$ has the desired property:

$$d_t(x', y') = d(x, y).$$

In fact, since $g \cdot f_n$ is nonexpanding, we derive from (2.1)

$$d_t(x', y') \le d_{t(n)}(x_n, y_n) \le d(x, y) + \frac{1}{n}$$

and since $c_t$ is nonexpanding, $d(x, y) \le d_t(x', y')$.

(b) Let $M \subseteq C$ be a countable set. Then so is $M \times M$. For every pair $(x, y)$ in $M \times M$ find $t_{x,y} \in T$ and $x', y' \in C_{t_{x,y}}$ as in (a). Since our diagram is countably filtered, we can choose $t$ independent of the given pair. Given $x \in M$, all the chosen elements $x'$ in $C_t$ (for all $y \in M$) form a countable set that $c_t$ maps to $x$. This implies, since our diagram is countably filtered, that there exists a connecting map $f: C_t \to C_{\bar{t}}$ which also maps all these elements $x'$ to one element, say $\bar{x}$, of $C_{\bar{t}}$. Moreover, since $M$ is countable, we can assume that $t$ and $\bar{t}$ are chosen to be the same for all $x \in M$. It follows that the set $\overline{M} = \{\bar{x}; x \in M\}$ is mapped by $c_{\bar{t}}$ isometrically to $M$: for every pair $x, y \in M$ we have unique $\bar{x}, \bar{y} \in M$ with $c_{\bar{t}}(\bar{x}) = x$ and $c_{\bar{t}}(\bar{y}) = y$, and since $f$ is nonexpanding

$$d(x, y) = d_{t_{x,y}}(x', y') \ge d_{\bar{t}}(\bar{x}, \bar{y}).$$

Since $c_{\bar{t}}$ is nonexpanding, $d(x, y) \le d_{\bar{t}}(\bar{x}, \bar{y})$. $\square$

**Corollary 2.8.** Every countable space in **MS** or in **PMS** is a countably presentable object.

*Proof.* Let $A$ be a countable space in **PMS**. Consider a colimit as in Lemma 2.7. The hom-functor of $A$ preserves it because for every morphism $f: A \to C$ there exists an essentially unique factorization through some $c_t$: apply the lemma to $M = f[A]$.

The argument for **MS** is analogous: **MS** is clearly closed under (countably) filtered colimits in **PMS**. $\square$

**Corollary 2.9.** Every separable space in **CMS** is a countably presentable object.

*Proof.* Let $A$ be a complete metric space with a countable dense set $M \subseteq A$. To verify that $\mathrm{CMS}(A, -)$ preserves countably filtered colimits, we first observe
that CMS is closed under such colimits in PMS. (To see this, consider a colimit as in Lemma 2.7 and take a Cauchy sequence $x_n$ in C. There exists, for $M = \{x_n; n \in N\}$, an index $t \in T$ and a Cauchy sequence $x'_n$ in $C_t$ with $x_n = c_t(x'_n)$ for every $n$. Then $x'_n$ has a limit $y'$ in $C_t$, yielding a limit $y = f(y')$ of $x_n$ in C.) For every nonexpanding map $f: A \to C = \text{colim } C_t$ there exists $t$ and $M' \subseteq C_t$ such that the colimit map $c_t$ is an isometry between $M'$ and $f[M]$. It follows easily that, since $M$ is dense in A, there exists a factorization $f = c_t \cdot f'$ where $f': A \to C_t$ is nonexpanding. Consequently, CMS(A, C) is a colimit of CMS(A, $C_t$) in Set, as required. □

**Remark 2.10.** No non-empty space is finitely presentable in CMS. To see this, express the real interval $[0, 1]$ as a filtered colimit in CMS of $[\frac{1}{n}, 1]$ for $n = 1, 2, 3, \dots$. If $A \neq \emptyset$, then the constant map $f: A \to [0, 1]$ with value 0 does not factorize through any of the colimit maps.

**Fact 2.11.** Remark 2.3(1) generalizes as follows: Let $\mathcal{A}$ be a locally $\lambda$-presentable category. Every $\lambda$-accessible endofunctor $F$ is determined by its values on $\mathcal{A}_\lambda$: we have $F = \text{Lan}_J(F \cdot J)$ for the full embedding $J: \mathcal{A}_\lambda \to \mathcal{A}$.

Consequently, the category of all $\lambda$-accessible endofunctors on $\mathcal{A}$ is locally $\lambda$-presentable.

## 3 The Hausdorff Functor

The aim of this section is to prove that on the category CMS of complete metric spaces the Hausdorff functor $\mathcal{H}$ introduced in Example 3.12 below is finitary.

It was proved by F. van Breugel et al [8] that $\mathcal{H}X$ is the free semilattice on $X$ in CMS. Thus, this functor is a special case of the monad $M^{\mathcal{T}}$ on CMS induced by free $\mathcal{T}$-algebras for a Lawvere algebraic theory $\mathcal{T}$. We start by proving that $M^{\mathcal{T}}$ is a finitary functor for every algebraic theory $\mathcal{T}$, then we turn to the special case.

Recall from [10] that an algebraic theory $(\mathcal{T}, T)$ is a category $\mathcal{T}$ whose objects are natural numbers, together with a functor $T: \mathbb{F}^{\text{op}} \to \mathcal{T}$ (see Example 2.2(1)) which is identity on objects and preserves finite products. This means that in $\mathcal{T}$ the object $n$ is a product $n = 1 \times \dots \times 1$ with projections

$$Tp_0, \dots, Tp_{n-1}: n \to 1$$

for the canonical injections $p_i: 1 \to n$ in $\mathbb{F}$.

**Notation 3.1.** Let $\mathcal{A}$ be a category with finite products. A $\mathcal{T}$-algebra in $\mathcal{A}$ is a functor $A: \mathcal{T} \to \mathcal{A}$ preserving finite products. The category of $\mathcal{T}$-algebras,

$$\mathbf{Alg}_{\mathcal{A}} \mathcal{T}$$

is the full subcategory of the functor category $\mathcal{A}^{\mathcal{T}}$. We denote by

$$U_{\mathcal{A}}^{\mathcal{T}}: \mathbf{Alg}_{\mathcal{A}} \mathcal{T} \to \mathcal{A}$$

the forgetful functor defined by $A \mapsto A(1)$ for all algebras $A: \mathcal{T} \to \mathcal{A}$.
**Example 3.2.** Semilattices. These are algebras on one binary operation which is commutative, associative, and idempotent. Let $\mathcal{T}_s$ be the corresponding algebraic theory, i.e., its morphisms from $n$ to 1 are the semilattice-terms on $n$ variables.

A $\mathcal{T}_s$-algebra in a category $\mathcal{A}$ is an object $A$ together with a morphism $\alpha: A \times A \to A$ for which the following three diagrams

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

commute (where $\sigma$ is the swapping isomorphism).

For example, $\mathbf{Alg}_{\mathbf{CMS}} \mathcal{T}_s$ is the category of complete metric spaces with a nonexpanding semilattice operation.

**Proposition 3.3.** Let $(\mathcal{T}, T)$ be an algebraic theory. For every locally finitely presentable category $\mathcal{A}$ the category $\mathbf{Alg}_{\mathcal{A}} \mathcal{T}$ is also locally finitely presentable, and $U_{\mathcal{A}}^{\mathcal{T}}$ is a finitary functor having a left adjoint.

*Proof.* $\mathcal{A}^{\mathcal{T}}$ is locally finitely presentable, and it is clear that the category of algebras is closed under limits and filtered colimits in it. Thus, it is also locally finitely presentable category, see [3], Theorem 2.48. It is also clear that $U_{\mathcal{A}}^{\mathcal{T}}$ preserves limits and is finitary, thus, it has a left adjoint by [3], Theorem 1.66.

□

*Remark 3.4.* Analogously, if $\mathcal{A}$ is a locally countably presentable category, then so is $\mathbf{Alg}_{\mathcal{A}} \mathcal{T}$, and $U_{\mathcal{A}}^{\mathcal{T}}$ is countably accessible.

*Notation 3.5.* We denote by $F_{\mathcal{A}}^{\mathcal{T}}$ the left adjoint of $U_{\mathcal{A}}^{\mathcal{T}}$, and by

$$M_{\mathcal{A}}^{\mathcal{T}} = U_{\mathcal{A}}^{\mathcal{T}} \cdot F_{\mathcal{A}}^{\mathcal{T}} : \mathcal{A} \to \mathcal{A}$$

the corresponding monad on $\mathcal{A}$.

**Example 3.6.** For $\mathcal{A} = \mathbf{PMS}$ we conclude that $U_{\mathbf{PMS}}^{\mathcal{T}}$ is countably accessible for every algebraic theory $\mathcal{T}$. But here we can do better: $U_{\mathbf{PMS}}^{\mathcal{T}}$ is always finitary. In fact, the functor from $\mathbf{PMS}^{\mathcal{T}}$ to $\mathbf{PMS}$ given by evaluation at 1 preserves colimits, and $U_{\mathbf{PMS}}^{\mathcal{T}}$ is its composite with the full embedding $\mathbf{Alg}_{\mathbf{PMS}} \mathcal{T} \hookrightarrow \mathbf{PMS}^{\mathcal{T}}$. Thus, it is sufficient to show that $\mathcal{T}$-algebras are closed under filtered colimits in $\mathbf{PMS}^{\mathcal{T}}$. This follows from the next
**Lemma 3.7.** *Filtered colimits commute with finite products in PMS.*

*Proof.* Let $(A, d) = \operatorname{colim}_{i \in I}(A_i, d_i)$ and $(A', d') = \operatorname{colim}_{j \in J}(A'_j, d'_j)$ be two filtered colimits. Let $(c_i)$ and $(c'_j)$ be the colimit cocones. Then the product $(A, d) \times (A', d')$ carries the maximum pseudometric $d_0$:

$$d_0((a, a'), (b, b')) = \max\{d(a, b), d'(a', b')\}$$

where

$$d(a, b) = \inf\{d_i(a_i, b_i); i \in I, a_i \in c_i^{-1}(a) \text{ and } b_i \in c_i^{-1}(b)\}$$

and analogously $d'(a', b')$.

We now form the filtered diagram of all

$$(A_i, d_i) \times (A'_j, d'_j)$$

indexed by $I \times J$. Its colimit has the same underlying cocone $c_i \times c'_j : A_i \times A'_j \to A \times A'$ as above. And its pseudometric is

$$d_1((a, a'), (b, b')) = \inf\{\max\{d_i(a_i, b_i), d'_j(a'_j, b'_j)\}; \\ (i, j) \in I \times J, a_i \in c_i^{-1}(a), b_i \in c_i^{-1}(b), a'_j \in (c'_j)^{-1}(a') \text{ and } b'_j \in (c'_j)^{-1}(b')\}.$$

This is the same pseudometric as $d_0$.

□

**Corollary 3.8.** *The forgetful functor from Alg$_{PMS}$ $\mathcal{T}$ to PMS is finitary for every algebraic theory $\mathcal{T}$.*

*Remark 3.9.* We have seen in Example 2.6 that **CMS** is a full reflective subcategory of **PMS**, i.e., the embedding $E: \mathcal{CMS} \to \mathcal{PMS}$ has a left adjoint $R: \mathcal{PMS} \to \mathcal{CMS}$. Indeed, **CMS** is reflective in **MS**, where the reflector $R_1: \mathcal{MS} \to \mathcal{CMS}$ is given by Cauchy completion, and **MS** is reflective in **PMS**, where the reflector $R_2: \mathcal{PMS} \to \mathcal{MS}$ is the quotient modulo zero distance (see Example 2.6(3)). Thus

$$R = R_1 \cdot R_2: \mathcal{PMS} \to \mathcal{CMS}$$

is a left adjoint to $E$.

**Lemma 3.10.** Let $\mathcal{A}$ be a cocomplete category with finite products and $\mathcal{B}$ a full reflective subcategory whose reflector $R: \mathcal{A} \to \mathcal{B}$ preserves finite products. For every algebraic theory $\mathcal{T}$ the forgetful functor $U_{\mathcal{T}}$ preserves every type of colimits that $U_{\mathcal{T}}$ preserves.

**Corollary 3.11.** *The forgetful functor of Alg$_{CMS}$ $\mathcal{T}$ is finitary for every algebraic theory $\mathcal{T}$.*

This follows from Lemma 3.10 applied to $\mathcal{A} = \mathcal{PMS}$, see Corollary 3.8, and the observation that $R$ in Remark 3.9 preserves finite products since both $R_1$ and $R_2$ do.
*Example 3.12.* The Hausdorff functor $\mathcal{H}$. Recall that for a metric space $(X, d)$, the distance of a point $x \in X$ to a set $M \subseteq X$ is $d(x, M) = \inf\{d(x, m); m \in M\}$. The Hausdorff distance of sets $M, N$ in $\mathcal{P}X$ is

$$d^*(M, N) = \max\left\{\sup_{x \in M} d(x, N), \sup_{y \in N} d(y, M)\right\}.$$

The Hausdorff functor is the endofunctor $\mathcal{H}$ of CMS defined on objects $X$ by

$$\mathcal{H}(X, d) = \text{all non-empty compact subsets of } X \text{ with the metric } d^*,$$

and on morphisms by direct images. For the theory $\mathcal{T}_s$ of Example 3.2 this is an algebra with the semilattice operation

$$\alpha(M, N) = M \cup N.$$

As proved in [8], $\mathcal{H}(X, d)$ is the free semilattice in CMS over $(X, d)$. In other words, for the monad $M_{\mathcal{T}}$ of Notation 3.5 we have

$$\mathcal{H} = M_{\mathcal{CMS}}^{\mathcal{T}}.$$

**Corollary 3.13.** The functor $\mathcal{H}$ and all other endofunctors of CMS obtained by combinations of it, the constant functors and the identity functor using composition, finite products or arbitrary coproducts, are finitary.

In particular, each such combination $F: \text{CMS} \to \text{CMS}$ has a final coalgebra obtained by some transfinite iteration of $F$ on 1. This follows from the fact that $F$ clearly preserves monomorphisms (since $\mathcal{H}$ does) and every finitary, monos-preserving endofunctor $F$ of a locally presentable category has the final coalgebra of the form $F^i$ for some ordinal $i$, see [5].

*Open problem 3.14.* The Plotkin power-domain is a complete analogy of the Hausdorff functor with CMS substituted by the category $\omega$ CPO of $\omega$-cpo's. Indeed, the Plotkin power-domain can be characterized as a free semilattice on $\omega$ CPO, see e.g. [1]. Is the corresponding endofunctor of $\omega$ CPO finitary?

# 4 Equational Presentation of Functors

Finitary set functors $F$ can, as proved in [4], be presented by a signature $\Sigma$ and a set of “flat” equations. Then $F$-algebras are precisely the $\Sigma$-algebras satisfying those equations. We recall this quickly and then generalize it to finitary endofunctors of all locally finitely presentable categories.

*Example 4.1.* The set functor

$$FX = \text{all unordered pairs in } X$$
is presented by a single binary operation, corresponding to the polynomial func-
tor $HX = X \times X$, and the commutativity equation. The latter can be expressed
by the parallel pair of morphisms

$u, u': 1 \to H2$

(recall 2 = {0, 1} from Example 2.2(1)) representing the elements (0, 1) and (1, 0)
of H2, respectively. In fact, the obvious natural transformation ε: H → F given
by (x, y) ↦→ {x, y} is universal w.r.t. the property that ε₂ merges u and u'.

*Example 4.2.* The functor $\mathcal{P}_f$ of all non-empty finite subsets can be presented by the signature $\Sigma$ of one $n$-ary operation $\sigma_n$ for every $n = 1, 2, \dots$, corresponding to the polynomial functor

$$
H_{\Sigma} X = X + X \times X + \dots = X^{+}
$$

via all the equations

$$
\sigma_l(x_0, \dots, x_{l-1}) = \sigma_k(y_0, \dots, y_{k-1})
$$

where for some $l \le k$ in $\mathbb{N}$ we have $\{x_0, \dots, x_{l-1}\} = \{y_0, \dots, y_{k-1}\}$. Again, each
such an equation corresponds to a parallel pair

$u, u' : 1 \to H_{\Sigma} k$

and the obvious natural transformation $\varepsilon: H_{\Sigma} \to \mathcal{P}_f$ is universal w.r.t.

$$
\varepsilon_k \cdot u = \varepsilon_k \cdot u' \quad \text{for each } u, u' \text{ above.}
$$

*Remark 4.3.* (1) Recall that for every signature $\Sigma = (\Sigma_k)_{k \in \mathbb{N}}$ the classical $\Sigma$-algebras are precisely the algebras for the *polynomial endofunctor* for **Set** given by

$$
H_{\Sigma} X = \Sigma_{0} + \Sigma_{1} \times X + \Sigma_{2} \times X^{2} + \dots
$$

(2) An equation $u = u'$ is just a notation for a pair of terms. We call it *flat* if both of the terms have the form $\sigma(x_1, \dots, x_n)$ for some $\sigma \in \Sigma_n$ and some $n$-tuple of variables. This is precisely a parallel pair

$u, u': 1 \to H_{\Sigma} X \quad \text{where} \quad X = \{x_1, \dots, x_n\}.$

**Definition 4.4 (See [4].)** A set functor $F$ is *presented* by a signature $\Sigma$ and a set of flat equations $u_i, u'_i : 1 \to H_\Sigma X_i$ ($i \in I$) provided that there exists a natural transformation $\varepsilon: H_\Sigma \to F$ universal w.r.t. the commutativity of the squares

<figure><img src="image_3.png" /></figure>
**Remark 4.5.** We will see later that every presentation defines a finitary set functor, and every finitary set functor has a presentation.

**Remark 4.6.** As we pointed out in Remark 2.3(2), the category of finitary functors on a locally finitely presentable category $\mathcal{A}$ is equivalent to the presheaf category $\mathcal{A}^{\mathcal{F}}$. Hence, from now on we will not distinguish between a finitary endofunctor on $\mathcal{A}$ and the corresponding presheaf.

**Observation 4.7.** The signature $\Sigma$ can be considered as a functor from $\mathbb{F}^0$, the discrete category of natural numbers, into **Set**. We thus obtain the category

$$ \mathbf{Sgn} = \mathbf{Set}^{\mathbb{F}^0} $$

of signatures as a functor category. Its morphisms are functions $f: \Sigma \to \Sigma'$ preserving the arity (or, equivalently, collections of functions $f_n: \Sigma_n \to \Sigma'_n$).

Denote by

$$ I: \mathbb{F}^0 \to \mathbb{F} $$

the non-full embedding. Then the polynomial functor $H_{\Sigma}$, considered as an object of $\mathbf{Set}^{\mathbb{F}}$, can be characterized, up to natural isomorphism, as the left Kan extension of $\Sigma: \mathbb{F}^0 \to \mathbf{Set}$ along $I$:

$$ H_{\Sigma} = \mathrm{Lan}_{I} \Sigma. $$

That is, given a finitary functor considered as $G \in \mathbf{Set}^{\mathbb{F}}$, natural transformations $\alpha: H_{\Sigma} \to G$ correspond bijectively to natural transformations $\bar{\alpha}: \Sigma \to G \cdot I$ via precomposition with $I$ (see Lemma 4.17).

**Definition 4.8 (M. Kelly and J. Power [9]).** Let $\mathcal{A}$ be a locally finitely presentable category. By a **signature** is meant a collection $\Sigma = (\Sigma_n)_{n \in \mathcal{F}}$ of objects of $\mathcal{A}$ indexed by representatives of finitely presentable objects.

A $\mathcal{A}$-**algebra** is an object $A$ of $\mathcal{A}$ together with a function assigning to morphisms in $\mathcal{A}(n, A)$ morphisms in $\mathcal{A}(\Sigma_n, A)$:

$$ \frac{n \xrightarrow{f} A}{\Sigma_n \xrightarrow{\hat{f}} A} \quad \text{for every } n \in \mathcal{F}. $$

Given another $\mathcal{A}$-algebra $B$, a $\mathcal{A}$-**homomorphism** is a morphism $h: A \to B$ of $\mathcal{A}$ satisfying

$$ h \cdot \hat{f} = \widehat{h \cdot f} \quad \text{for all } n \in \mathcal{F} \text{ and } f: n \to A. $$

**Example 4.9. Set.** For $\mathbb{F}$ of Example 2.2, signature has the usual meaning. And the same holds for $\mathcal{A}$-algebras: given a set $A$ with $n$-ary operations $\sigma^A: A^n \to A$ for all $\sigma \in \Sigma_n$, we obtain a map assigning to every $n$-tuple in $A$, $f: n \to A$, the function

$$ \hat{f}: \Sigma_n \to A, \quad \sigma \mapsto \sigma^A(f). $$

Conversely, given a $\mathcal{A}$-algebra $A$ as in Definition 4.8, define for every $\sigma \in \Sigma_n$ the $n$-ary operation $\sigma^A: f \mapsto \hat{f}(\sigma)$.

Under this bijective translation homomorphisms in the sense of Definition 4.8 are the usual homomorphisms of $\mathcal{A}$-algebras.
**Example 4.10. Pos.** Here $\Sigma$ is indexed by (representatives of) finite posets. We denote for every $n \in \mathbb{N}$ by $c(n)$ the chain of length $n$ and by $d(n)$ the discretely ordered set of $n$ elements. We also denote by 0 the initial (empty) poset and by $1 = d(1)$ the terminal one.

(1) The signature $\Sigma$ with

$$ \Sigma_{d(2)} = c(2) \quad \text{and} \quad \Sigma_n = 0 \quad \text{for all } n \neq d(2) $$

corresponds to algebras on posets $(A, \leq)$ with two binary operations $\sigma, \tau$ satisfying $\sigma(x, y) \leq \tau(x, y)$ for all pairs $(x, y)$. In fact, this is the same as giving a function

$$ \frac{d(2) \xrightarrow{f} A}{c(2) \xrightarrow{\hat{f}} A} $$

An example of a $\Sigma$-algebra: $\mathbb{N} \setminus \{0, 1\}$ where $\sigma$ is addition and $\tau$ is multiplication.

(2) The signature $\Sigma'$ with

$$ \Sigma'_{c(2)} = 1 \quad \text{and} \quad \Sigma_n = 0 \quad \text{for all } n \neq c(2) $$

corresponds to algebras given by a binary operation $\sigma$ defined iff the pair $(x, y)$ satisfies $x \leq y$. This is the same as giving a function

$$ \frac{c(2) \xrightarrow{f} A}{1 \xrightarrow{\hat{f}} A} $$

An example of a $\Sigma$-algebra: $\mathbb{N} \setminus \{0\}$ ordered by divisibility, where the operation $\sigma$ is division.

**Example 4.11. K-Vec.** Here $\mathcal{F} = \{K^n; n \in \mathbb{N}\}$ and signatures thus have the same form as in **Set**. However, due to the coincidence of binary products and coproducts, formally different signatures yield equal categories of algebras. For example, let us consider the signature that in **Set** corresponds to one binary and one unary operation:

$$ \Sigma_{K^2} = K, \quad \Sigma_K = K \quad \text{and} \quad \Sigma_n = 0 \quad \text{else.} $$

Then a $\Sigma$-algebra is given by a vector space $A$ and two linear functions $A \times A \to A$ and $A \to A$. This is equivalent to giving three linear functions $A \to A$, thus, the signature

$$ \Sigma'_{K} = K^3 \quad \text{and} \quad \Sigma'_{n} = 0 \quad \text{else} $$

yields the same algebras.

**Example 4.12. MS.** Let $\delta$ be the metric space of two elements of distance $\frac{1}{2}$. The signature

$$ \Sigma_{\delta} = 1 \quad \text{and} \quad \Sigma_n = 0 \quad \text{else} $$

corresponds to algebras on a metric space $(A, d)$ with one binary operation defined in precisely the pairs $(x, y)$ with $d(x, y) \leq \frac{1}{2}$.
**Definition 4.13.** The polynomial functor

$$H_{\Sigma}: \mathcal{A} \to \mathcal{A}$$

of a given signature $\Sigma$ is defined on objects X by

$$H_{\Sigma}X = \coprod_{n \in \mathcal{F}} \mathcal{A}(n, X) \bullet \Sigma_n$$

where $M \bullet \Sigma_n$ denotes a copower of $M$ copies of the object $\Sigma_n$.

*Example 4.14.* For **Set** this is the formula of Remark 4.3, since $\mathbf{Set}(n, X) \bullet \Sigma_n = \Sigma_n \times X^n$.

The polynomial functors of Example 4.10 are

$$H_{\Sigma}(X, \leq) = (X \times X) \bullet c(2) \quad \text{and} \quad H_{\Sigma'}(X, \leq) = \mathbf{Pos}(c(2), (X, \leq)).$$

**Lemma 4.15.** The category of $\Sigma$-algebras and homomorphisms is equivalent to Alg $H_{\Sigma}$.

*Proof.* Every $\Sigma$-algebra $A$ defines for every $n \in \mathcal{F}$ a morphism from $\mathcal{A}(n, A) \bullet \Sigma_n$ to $A$ whose component at $f: n \to A$ is $\hat{f}: \Sigma_n \to A$. We thus obtain a $H_{\Sigma}$-algebra where

$$\alpha: \coprod_{n \in \mathcal{F}} \mathcal{A}(n, A) \bullet \Sigma_n \to A$$

has the above components. Conversely, given an $H_{\Sigma}$-algebra $\alpha: H_{\Sigma}A \to A$ the function

$$\frac{n \xrightarrow{f} A}{\Sigma_n \xrightarrow{\hat{f}} A}$$

is defined by having $\hat{f}$ equal to the component of $\alpha$ corresponding to $f \in \mathcal{A}(n, A)$.

It is easy to see that the above functions extend to functors $\Sigma$-Alg $\to$ Alg $H_{\Sigma}$ and Alg $H_{\Sigma} \to \Sigma$-Alg which form an isomorphism of categories. In fact, a homomorphism $h$ of $H_{\Sigma}$-algebras:

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

is precisely a morphism $h: A \to B$ in $\mathcal{A}$ such that $h \cdot \hat{f} = \hat{h} \cdot f$ for every $n \in \mathcal{F}$ and $f \in \mathcal{A}(n, A)$. $\square$
**Example 4.20.** The endofunctor $G$ of **Pos** defined by

$$G(X, \leq) = \{(x, y) \in X^2; x < y\} \cup \{*\}$$

on objects and on morphisms $f: (X, \leq) \to (Y, \leq)$ by

$$Gf(x, y) = (f(x), f(y)) \quad \text{if} \quad f(x) \prec f(y)$$

whereas $Gf$ has else the value $*$, has the presentation by the signature $\Sigma'$ of Example 4.10 and the flat equation

$$\sigma(x, x) = \sigma(y, y).$$

**Construction 4.21.** A finitary endofunctor presented by a given set $u_i, u'_i$: $n_i \to H_\Sigma k_i$ ($i \in I$) of flat equations.

Define a signature $\bar{\Sigma}$ by

$$\bar{\Sigma}_k = \coprod_{i \in I, k_i = k} n_i \quad \text{for all } k \in \mathcal{F}.$$

Then the morphisms $u_i$ define a natural transformation from $\bar{\Sigma}$ to $H_\Sigma \cdot I$: its component at $k \in \mathcal{F}$ is simply

$$[u_i]: \coprod_{i \in I, k_i = k} n_i \to H_\Sigma k.$$

From Lemma 4.17 we obtain the corresponding natural transformation

$$\bar{u}: H_{\bar{\Sigma}} \to H_{\Sigma}.$$

Analogously for $\bar{u'}$: $H_{\bar{\Sigma}} \to H_{\Sigma}$. In the (cocomplete) category $\mathcal{A}\mathcal{F}$ of all finitary endofunctors form the coequalizer

$$H_{\bar{\Sigma}} \xrightarrow{\bar{u}} H_{\Sigma} \xrightarrow{\varepsilon} F.$$

Then $F$ is presented by the given flat equations.

Indeed, for every $k$ the equation $\varepsilon_k \cdot u_k = \varepsilon_k \cdot u'_k$ guarantees that $\varepsilon$ satisfies the equations $u_i, u'_i$ for all $i \in I$. Conversely, let $\varepsilon'$: $H_\Sigma \to F'$ be a natural transformation with $\varepsilon'_{k_i} \cdot u_i = \varepsilon'_{k_i} \cdot u'_i$ for all $i \in I$. Then obviously $\varepsilon' \cdot \bar{u} = \varepsilon' \cdot \bar{u}'$, thus, $\varepsilon'$ factorizes uniquely through $\varepsilon$.

**Proposition 4.22.** Every finitary endofunctor of a locally finitely presentable category has a presentation by a signature and a set of flat equations.

*Proof.* Precomposition with $I: \mathcal{F}^0 \to \mathcal{F}$ defines a functor

$$\cdot I: \mathcal{A}\mathcal{F} \to \mathcal{A}\mathcal{F}^0$$

which is monadic. Indeed, this functor has both a left and a right adjoint, and it reflects isomorphisms: given a morphism $\alpha: F \to G$ in $\mathcal{A}\mathcal{F}$ which is invertible in $\mathcal{A}\mathcal{F}^0$ (i.e., has invertible components), then $\alpha$ is a natural isomorphisms,
i.e., it is invertible in $\mathcal{A}\mathcal{F}$. Thus, monadicity follows from Beck's Theorem, see e.g. [7], Theorem 4.4.4. Consequently, finitary endofunctors of $\mathcal{A}$ are precisely the monadic algebras of the corresponding monad $\mathbb{T}$ on the category $\mathcal{A}\mathcal{F}^0$ of signatures. It follows from Lemma 4.17 that this monad assigns to every signature $\Sigma$ the signature $T(\Sigma) = H_{\Sigma} \cdot I$. The free $\mathbb{T}$-algebra on $\Sigma$ is then $H_{\Sigma}$.

Every finitary endofunctor $F$, i.e., every Eilenberg-Moore algebra for $\mathbb{T}$, is a coequalizer of a parallel pair of homomorphisms between free $\mathbb{T}$-algebras:

$$H_{\Sigma} \xrightarrow{u} H_{\Sigma} \xrightarrow{\varepsilon} F.$$

Consider, for every $k \in \mathcal{F}$, the object $H_{\Sigma}k$ as a filtered colimit of objects $n_i$ ($i \in I_k$) in $\mathcal{F}$ with the colimit cocone $v_i^{(k)}: n_i \to H_{\Sigma}k$. Then the flat equations

$$u_k \cdot v_i^{(k)}, u'_k \cdot v_i^{(k)}: n_i \to H_{\Sigma}k$$

(where $k$ ranges through $\mathcal{F}$ and $i$ through $I_k$) form an equational presentation of $F$.

Indeed, from $\varepsilon \cdot u = \varepsilon \cdot u'$ it follows that each of the above parallel pairs is merged by $\varepsilon_k$. Let $\hat{\varepsilon}: H_{\Sigma} \to \hat{F}$ another morphism of $\mathcal{A}\mathcal{F}$ such that each of the above parallel pairs is merged by $\hat{\varepsilon}_k$. To prove that $\hat{\varepsilon}$ uniquely factorizes through $\varepsilon$ we need to verify that $\hat{\varepsilon} \cdot u = \hat{\varepsilon} \cdot u'$. Equivalently, $\hat{\varepsilon}_k \cdot u_k = \hat{\varepsilon}_k \cdot u'_k$ for every $k \in \mathcal{F}$. This follows from $\hat{\varepsilon}_k \cdot u_k \cdot v_i^{(k)} = \hat{\varepsilon}_k \cdot u'_k \cdot v_i^{(k)}$ since the cocone $v_i^{(k)}$, $i \in I_k$, is collectively epic (being a colimit cocone). $\square$

**Remark 4.23.** (1) The above proof shows that we always have a canonical presentation of a finitary functor $F$: take the signature $\Sigma$ defined by

$$\Sigma_n = F(n)$$

for all $n \in \mathcal{F}$. Obtain a canonical natural transformation $\varepsilon: H_{\Sigma} \to F$ whose component

$$\varepsilon_k: \coprod_{n \in \mathcal{F}} \mathcal{A}(n, k) \bullet F_n \to F_k$$

is given by $[Ff]: \coprod_{f \in \mathcal{A}(n,k)} F_n \to Fk$. Then consider all the flat equations formed by all parallel pairs

$$u, u': n \to H_{\Sigma}k \quad (n, k \in \mathcal{F}) \quad \text{with } \varepsilon_k \cdot u = \varepsilon_k \cdot u'$$

(2) We can, as we have seen e.g. in Example 4.1, often obtain a much simpler equational presentation. Another example:

**Example 4.24.** Let $F$ be the set-functor obtained from $X \mapsto X \times X$ by merging the diagonal to a single element *:

$$FX = \{(x, y); x, y \in X, x \neq y\} \cup \{*\}.$$

$F$ has a presentation using a single binary operation $\sigma$ and the equation

$$\sigma(x, x) = \sigma(y, y).$$
**Definition 4.25.** A $\Sigma$-algebra $A$ is said to **satisfy** a flat equation morphism $u, u'$: $n \to H_\Sigma k$ provided that its algebra structure $\alpha: H_\Sigma A \to A$ merges $H_\Sigma f \cdot u$ and $H_\Sigma f \cdot u'$ for all $f: k \to A$.

**Example 4.26.** In **Set** this is the usual concept of fulfilling an equation with $k$ variables: given any interpretation $f: k \to A$ of the variables, the elements of $A$ computed from the two sides of the equation are equal.

**Lemma 4.27.** If a functor $F$ is presented by a signature $\Sigma$ and flat equations $u, u'$ ($i \in I$), then the category **Alg** $F$ of $F$-algebras is equivalent to the category of all $\Sigma$-algebras satisfying those equations.

**Remark 4.28.** There is an alternative definition of what it means for a $\Sigma$-algebra $A$ to satisfy a flat equation morphism—and fortunately, the result is the same as above. This is based on the following idea of M. Kelly and J. Power [9]: given objects $A$ and $B$ of $\mathcal{A}$, let $\langle A, B \rangle$ be the endofunctor of $\mathcal{A}$ assigning to $X$ the power of $B$ to the set $\mathcal{A}(X, A)$:

$$ \langle A, B \rangle X = B^{\mathcal{A}(X, \mathcal{A})}. $$

In other words, $\langle A, B \rangle$ is the following composite

$$ \mathcal{A} \xrightarrow{\mathcal{A}(-, A)} \mathrm{Set}^{\mathrm{op}} \xrightarrow{B^{(-)}} \mathcal{A}. $$

Then natural transformations from $F$ to $\langle A, A \rangle$ are, for every endofunctor $F$, in a canonical bijective correspondence to $F$-algebra structures on $A$. In fact, to every algebra $\alpha: FA \to A$ assign $\alpha^*: F \to \langle A, A \rangle$ where the components $\alpha_X^*: FX \to A^{\mathcal{A}(X, A)}$ are given by

$$ \alpha_X^* = \langle \alpha \cdot Ff \rangle_f: X \to \mathcal{A} : FX \to \langle A, A \rangle X = A^{\mathcal{A}(X, A)}. $$

It is now natural to say that an $\Sigma$-algebra $\alpha: H_\Sigma A \to A$ satisfies a flat equation $u, u'$: $n \to H_\Sigma k$ iff

$$ \alpha_k^* \cdot u = \alpha_k^* \cdot u': n \to \langle A, A \rangle k. $$

But this tells us precisely that $\alpha \cdot H_\Sigma f \cdot u = \alpha \cdot H_\Sigma f \cdot u'$ for all $f: X \to \mathcal{A}$.

**Remark 4.29.** Everything above generalizes without any problem from finitary functors to accessible ones. Let $\mathcal{A}$ be a locally $\lambda$-presentable category (see Definition 2.5).

By a $\lambda$-ary signature is meant a collection $\Sigma = (\Sigma_n)_{n \in \mathcal{A}_\lambda}$ of objects of $\mathcal{A}$. The corresponding polynomial endofunctor $H_\Sigma$ is given by

$$ H_\Sigma X = \coprod_{n \in \mathcal{A}_\lambda} \mathcal{A}(n, X) \bullet \Sigma_n. $$

A flat $\lambda$-ary equation is a parallel pair of morphisms $u, u'$: $n \to H_\Sigma k$ with $n, k \in \mathcal{A}_\lambda$. A $\lambda$-accessible endofunctor $F$ is said to have a $\lambda$-ary presentation if there exists a $\lambda$-ary signature $\Sigma$ and a collection $u_i, u'_i: n_i \to H_\Sigma k_i$ of $\lambda$-ary flat equations such that there is a universal natural transformation $\varepsilon: H_\Sigma \to F$ w.r.t. $\varepsilon_{k_i} \cdot u_i = \varepsilon_{k_i} \cdot u'_i$ for every $i$.
**Proposition 4.30.** Every $\lambda$-accessible endofunctor of a locally $\lambda$-presentable category has a $\lambda$-ary presentation, and every $\lambda$-ary presentation defines a $\lambda$-accessible endofunctor.

The proof is completely analogous to Construction 4.21 and Proposition 4.22.

*Example 4.31.* The countable power-set functor $\mathcal{P}_c$ is presented by one $\aleph_0$-ary operation $\sigma$ and one constant together with the flat equations

$$ \sigma(x_0, x_1, x_2, \dots) = \sigma(y_0, y_1, y_2, \dots) \quad \text{whenever} \quad \{x_i\}_{i \in \mathbb{N}} = \{y_i\}_{i \in \mathbb{N}}. $$

# 5 An Equational Presentation of the Hausdorff Functor

We end this paper with a concrete presentation of $\mathcal{H}$. This happens to be the same presentation that $\mathcal{P}_f$ has in **Set**. More to the point, consider the parallel pairs $u, u': 1 \to k^+$ presenting $\mathcal{P}_f$ in Example 4.2. We interpret $X^+ = \coprod_{n>0} X^n$, using the coproduct of finite powers in **CMS**; this is the disjoint union of the spaces of finite tuples with the maximum metric. Notice that this is not a polynomial functor in the sense of Definition 4.13; in fact, the polynomial functor given by the signature with one operation symbol of arity $n$ for any non-empty finite discrete space $n$ maps a space $X$ to $\coprod_{n>0} X^n$ with the discrete metric.

We now use the same family of pairs $u, u': 1 \to k^+$ as in Example 4.2. We claim that the joint coequalizer in **CMS** of this family is the natural transformation $\varepsilon : (-)^+ \to \mathcal{H}$ given by

$$ \varepsilon_X : X^+ \to \mathcal{H}X \quad (x_1, \dots, x_n) \mapsto \{x_1, \dots, x_n\}. $$

The set $\mathcal{P}_f(X)$ of all non-empty finite sets is dense in $\mathcal{HX}$ for any space $X$. To see this, let $C$ be a non-empty compact subset of $X$. Fix $\delta > 0$. The collection of open balls of radius $\delta$ which meet $C$ covers $C$. By compactness, there is a finite subcollection which covers $C$. The set of centers gives a finite, hence compact, $F \subseteq X$, and its distance to $C$ in the Hausdorff metric is at most $\delta$.

And since $\varepsilon \cdot u = c \cdot u'$ for all the above pairs $u, u': 1 \to k^+$, our claim that $\varepsilon$ is their joint equalizer follows from the following fact.

**Lemma 5.1.** For every pair $M, N$ of non-empty finite subsets of a complete metric space $X$, there are words $m, n \in X^+$ so that $\varepsilon_X(m) = M$, $\varepsilon_X(n) = N$, and

$$ d_{X^+}(m, n) = d_{\mathcal{HX}}(M, N). $$

*Proof.* Put $M = \{x_0, \dots, x_p\}$ and $N = \{y_0, \dots, y_{q-1}\}$. We may assume that $x_0$ and $y_0$ are such that $d_{\mathcal{HX}}(M, N) = d_X(x_0, y_0)$. Define $(p+q)$-tuples in $X$ by

$$ \begin{aligned} m &= (x_0, \dots, x_{p-1}, x[y_0], \dots, x[y_{q-1}]) \\ n &= (y[x_0], \dots, y[x_{p-1}], y_0, \dots, y_{q-1}) \end{aligned} $$

where we choose $x[y_i]$ such that $d(x_i, x[y_i]) \le d(x_0, y_0)$ for all $i$, and analogously $d(x[y_j], y_j) \le d(x_0, y_0)$ for all $j$. Then $d_{X^+}(m, n) = d(x_0, y_0)$. Moreover, $\varepsilon_X(m) = M$ and $\varepsilon_X(n) = N$.
**Proposition 5.2.** The Hausdorff functor is presented in CMS by all the parallel pairs $u, u'$ of Example 4.2, with the discrete metric on $k = \{0, ..., k-1\}$.

*Proof.* It is our task to prove that for the above endofunctor $(-)^+$ of CMS, the natural transformation $\varepsilon : (-)^+ \to \mathcal{H}$ is a joint coequalizer of all pairs $u_i, u'_i$. Clearly $\varepsilon$ is non-expanding. Let $X$ and $Y$ be complete metric spaces, and let $f : X^+ \to Y$ satisfy $f \cdot u_i = f \cdot u'_i$ for all $i \in I$. There is a unique $g_0 : \mathcal{P}_f(X) \to Y$ such that $g_0 \cdot \varepsilon_{X^+} = f$. By Lemma 5.1 and since $f$ is non-expanding, $g_0$ is non-expanding, too. Since $\mathcal{P}_f(X)$ is dense in $\mathcal{H}(X)$, $g_0$ extends to a unique $g : \mathcal{H}(X) \to Y$.

*Remark 5.3.* We find it surprising that $\mathcal{H}$ has the same presentation in CMS that $\mathcal{P}_f$ has in Set. Let us observe that, nonetheless, this presentation is not a finitary presentation in the sense of Definition 4.4 for two reasons: (a) $(-)^+$ is not a polynomial functor and (b) no non-empty space is finitely presentable (see Remark 2.10).

Ad (a) one can define the notion of presentation in an enriched setting as in [9], and then $(-)^+$ is indeed a polynomial functor so that, ad (b), the presentation of the Hausdorff functor we showed in this section is then a countable presentation (even though only operations of finite arity are used).

Also notice that A. Kurz and J. Velebil [12, Proposition 5.4] provide (in the enriched setting) a presentation of a related functor mapping a complete metric space $X$ to the space of its closed and separable subsets with the Hausdorff metric. Their presentation is countable using besides $n$-ary operations as above also an $\omega$-ary operation.

# 6 Conclusions

We have shown that finitary endofunctors of locally finitely presentable categories have an equational presentation using finitary signatures in the sense of M. Kelly and J. Power [9]. There are important categories which are not locally finitely presentable, but are locally countably presentable, e.g. $\omega$ CPO and CMS (complete metric spaces). There every countably accessible endofunctor has an equational presentation using signatures of countable arity. The main result of our paper is that the Hausdorff functor on CMS, which was proved to be accessible by F. van Breugel et al [8], is in fact finitary. It has a presentation which is completely analogous to the presentation of the finite non-empty power set functor on Set.

# References

1. Abramsky, S., A. Jung, A.: Domain Theory. In Handbook of Logic in Computer Science, Clarendon Press, Oxford 1994

2. Adámek, J.: Free algebras and automata realizations in the language of categories. Comment. Math. Univ. Carolinae **15** (1974) 589–609
3. Adámek, J., Rosický, J.: Locally Presentable and Accessible Categories. Cambridge University Press 1993

4. Adámek, J., Trnková, V.: Automata and Algebras in Categories. Kluwer Academic Publ., Dordrecht 1990

5. Adámek, J., Trnková, V.: Relatively terminal coalgebras. To appear in J. Pure Appl. Algebra

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

7. Borceux, F.: Handbook of Categorical Algebra, Vol. 2. Cambridge University Press 1994

8. van Breugel, F., Hermida, C., Makkai, M., Worrell, J.: Recursively defined metric spaces without contraction

9. Kelly, G. M, Power, J.: Adjunctions whose counits are coequalizers and presentations of finitary enriched monads. J. Pure Appl. Algebra **89** (1993) 163–179

10. Lawvere, F. W.: Functional semantics of algebraic theories. Dissertation, Columbia University 1963

11. Makkai, M., Paré, R.: Accessible Categories. Amer. Math. Soc., Providence, Rhode Island 1989

12. Velebil, J., Kurz, A. Equational presentations of functors and monads. Math. Structures Comput. Sci. **21** (2011), 363–381