# Polyadic Sets and Homomorphism Counting

Luca Reggio  Department of Computer Science, University of Oxford, United
Kingdom<EMAIL_ADDRESS>
###### Abstract.

A classical result due to Lovász (1967) shows that the isomorphism type of a
graph is determined by homomorphism counts. That is, graphs $G$ and $H$ are
isomorphic whenever the number of homomorphisms $K\to G$ is the same as the
number of homomorphisms $K\to H$ for all graphs $K$. Variants of this result,
for various classes of finite structures, have been exploited in a wide range
of research fields, including graph theory and finite model theory.

We provide a categorical approach to homomorphism counting based on the
concept of polyadic (finite) set. The latter is a special case of the notion
of polyadic space introduced by Joyal (1971) and related, via duality, to
Boolean hyperdoctrines in categorical logic. We also obtain new homomorphism
counting results applicable to a number of infinite structures, such as
finitely branching trees and profinite algebras.

Research supported by the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement No
837724, and partially supported by the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation program (grant
agreement No 670624).

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries and Basic Notions
  3. 3 Polyadic Sets
    1. 3.1 The amalgamation property
    2. 3.2 Polyadic sets and Stirling kernels
    3. 3.3 Pointwise isomorphisms
  4. 4 Homomorphism Counting in Locally Finite Categories
  5. 5 Beyond Locally Finite Categories
    1. 5.1 Nerves and hom-spaces
    2. 5.2 Locally finitely presentable categories
    3. 5.3 Coalgebras for comonads of finite rank
  6. 6 Examples
    1. 6.1 Trees
    2. 6.2 Profinite algebras
    3. 6.3 Finite-variable logics
  7. A Proper Factorisation Systems
  8. B Comonads of Finite Rank

##  1\. Introduction

A celebrated result of Lovász [25] states that two (finite, directed) graphs
$G$ and $H$ are isomorphic if and only if, for all graphs $K$, the number of
graph homomorphisms $K\to G$ is the same as the number of graph homomorphisms
$K\to H$.111Lovász proved this result, more generally, for finite
$\sigma$-structures over a finite relational signature $\sigma$. This is a
prototypical example of homomorphism counting result. Extensions and
variations of this theorem have been exploited in a broad range of research
areas, such as graph theory, finite model theory and quantum information [11,
16, 29].

Categorical generalisations of Lovász’ result were proved by Pultr [36] and
Isbell [19], cf. also [26], utilising a direct generalisation of Lovász’
combinatorial counting argument. A different approach, which is generalised in
the present paper, was adopted in a recent joint work with Dawar and Jakl [9].
These results apply to a large class of _locally finite_ categories, i.e.
categories with only finitely many morphisms between any two objects. Examples
include graphs, finite groups and, more generally, finite members of any
equationally defined class of universal algebras.

The aim of this article is two-fold. On the one hand, we show that
homomorphism counting results are basically a consequence of a more general
result about polyadic (finite) sets, a special case of Joyal’s polyadic spaces
[21]. The latter are dual—in the sense of Stone duality for Boolean algebras
[42]—to Boolean hyperdoctrines, a fundamental tool of categorical logic [24];
for more details, see [30]. This exposes a new connection between homomorphism
counting, as studied in graph theory and related fields, and the structural
methods of category theory and categorical logic.

On the other hand, we exploit the framework of polyadic sets, combined with a
topological argument, to extend homomorphism counting results beyond
categories of finite structures. We thus obtain new general results that
apply, for example, to finitely branching trees and (topologically finitely
generated) profinite algebras. An application to finite-variable logics in
finite model theory, which relies on the notion of game comonad introduced by
Abramsky, Dawar _et al._ , is also presented.

The present paper is structured as follows. In Section 2 we recall some basic
categorical definitions and facts, and introduce the notion of (left- and
right-) combinatorial category, in which the isomorphism types of objects are
determined by homomorphism counts. In Section 3 we study polyadic (finite)
sets and prove some of their main properties. These results are used in
Section 4 to establish homomorphism counting results for locally finite
categories. In Section 5 we prove a general theorem characterising the
isomorphism type of certain objects in categories that are not necessarily
locally finite, and specialise it to the setting of locally finitely
presentable categories. Several applications of these results are discussed in
Section 6.

##  2\. Preliminaries and Basic Notions

Throughout the paper, we assume the reader is familiar with basic notions of
category theory; standard references include [3, 27].

Recall that a category $\operatorname{\mathscr{A}}$ is _well-powered_ if, for
each object $a\in\operatorname{\mathscr{A}}$, the collection of subobjects of
$a$ is a set (as opposed to a proper class), see e.g. [3, Definition 7.82].
Dually, $\operatorname{\mathscr{A}}$ is _well-copowered_ if the opposite
category $\operatorname{\mathscr{A}}^{\mathrm{op}}$ is well-powered.

######  Assumption 2.1.

All categories $\operatorname{\mathscr{A}}$ under consideration are assumed to
be locally small, well-powered and well-copowered.

Let $\operatorname{\mathbf{Set}}$ be the category of sets and functions. Given
a category $\operatorname{\mathscr{A}}$, denote by
$\widehat{\operatorname{\mathscr{A}}}$ the category of presheaves over
$\operatorname{\mathscr{A}}$, i.e. the functor category
$\operatorname{\mathbf{Set}}^{\operatorname{\mathscr{A}}^{\mathrm{op}}}$. The
Yoneda embedding

$\mathcal{y}^{\operatorname{\mathscr{A}}}\colon\operatorname{\mathscr{A}}\to\widehat{\operatorname{\mathscr{A}}}$

sends an object $a$ of $\operatorname{\mathscr{A}}$ to the presheaf

$\mathcal{y}^{\operatorname{\mathscr{A}}}_{a}\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}},\quad
b\mapsto\mathcal{y}^{\operatorname{\mathscr{A}}}_{a}(b)\coloneqq\hom_{\operatorname{\mathscr{A}}}(b,a).$

When the category $\operatorname{\mathscr{A}}$ is clear from the context, we
omit the superscript and simply write $\mathcal{y}$ and $\mathcal{y}_{a}$. A
well known consequence of the Yoneda Lemma (cf. e.g. [3, Theorem 6.20]) states
that, for all objects $a,b\in\operatorname{\mathscr{A}}$,

$a\cong
b\enspace\Longleftrightarrow\enspace\mathcal{y}_{a}\cong\mathcal{y}_{b}.$ (1)

That is, $a$ and $b$ are isomorphic (as objects of
$\operatorname{\mathscr{A}}$) precisely when the hom-functors
$\mathcal{y}_{a}$ and $\mathcal{y}_{b}$ are _naturally_ isomorphic.

In general, two functors $F,G\colon\operatorname{\mathscr{A}}\to\mathscr{B}$
can be pointwise isomorphic (i.e., $F(a)\cong G(a)$ for all
$a\in\operatorname{\mathscr{A}}$) without being naturally isomorphic; we
illustrate this point with an example due to Joyal [22, Exemple 6].

######  Example 2.2.

Let $\operatorname{\mathscr{A}}$ be the category of finite sets and
bijections. Consider the functor
$F\colon\operatorname{\mathscr{A}}\to\operatorname{\mathscr{A}}$ sending a
finite set $a$ to its set of permutations. Given a morphism $f\colon a\to b$
in $\operatorname{\mathscr{A}}$, $F(f)$ sends a permutation $\varphi$ of $a$
to the permutation $f\circ\varphi\circ f^{-1}$ of $b$. Further, let
$G\colon\operatorname{\mathscr{A}}\to\operatorname{\mathscr{A}}$ be the
functor which sends a finite set to the set of its linear orderings. If
$f\colon a\to b$ is a morphism in $\operatorname{\mathscr{A}}$, $G(f)$ sends a
linear order $R\subseteq a\times a$ on $a$ to the linear order
$\\{(f(x),f(y))\mid(x,y)\in R\\}$ on $b$.

The functors $F$ and $G$ are pointwise isomorphic because the number of
permutations of an $n$-element set $a$ is $n!$, which is also the number of
linear orders on $a$. However, they are not naturally isomorphic; just note
that there is no natural way of assigning a linear order to the identity
permutation.

Broadly speaking, a homomorphism counting result asserts that the existence of
a natural isomorphism $\mathcal{y}_{a}\cong\mathcal{y}_{b}$ in equation (1)
can be replaced by the weaker condition that $\mathcal{y}_{a}$ and
$\mathcal{y}_{b}$ are _pointwise_ isomorphic.

######  Definition 2.3.

A category $\operatorname{\mathscr{A}}$ is said to be _right-combinatorial_
if, for all objects $a,b\in\operatorname{\mathscr{A}}$,

$a\cong b\enspace\Longleftrightarrow\enspace\forall
c\in\operatorname{\mathscr{A}}\ (\mathcal{y}_{a}(c)\cong\mathcal{y}_{b}(c)).$

Note that the isomorphisms on the right-hand side above are nothing but
bijections between sets. Thus, the isomorphism type of an object $a$ of a
right-combinatorial category $\operatorname{\mathscr{A}}$ is completely
determined by the cardinalities $|\hom_{\operatorname{\mathscr{A}}}(c,a)|$ of
the hom-sets for $c$ which varies in $\operatorname{\mathscr{A}}$.

There is of course a dual notion of left-combinatorial category:

######  Definition 2.4.

A category $\operatorname{\mathscr{A}}$ is _left-combinatorial_ provided that
$\operatorname{\mathscr{A}}^{\mathrm{op}}$ is right-combinatorial. A category
that is both left- and right-combinatorial is called a _combinatorial
category_.

Let us hasten to point out that the term _combinatorial category_ was coined
by Pultr [36] (and used, e.g., in [9]) to refer to what we call a right-
combinatorial category. As both notions of left- and right-combinatorial
category are interesting and useful, we opted for a nomenclature that
distinguishes between these dual notions.

##  3\. Polyadic Sets

The aim of this section is to introduce the main tool of this paper: polyadic
sets. In Section 3.1 we introduce the amalgamation property for presheaves.
Polyadic sets, which are presheaves with the amalgamation property, are
studied in Section 3.2, where the construction of the Stirling kernel is
presented. In Section 3.3 we prove a result concerning Stirling kernels that
will be used to establish homomorphism counting results in the subsequent
sections.

###  3.1. The amalgamation property

Let us say that a category $\operatorname{\mathscr{A}}$ has the _amalgamation
property_ if any span of morphisms in $\operatorname{\mathscr{A}}$ can be
completed to a commutative square:

${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$

By extension, we say that a presheaf
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
has the amalgamation property if so does its _category of elements_ $\int F$.
Recall that objects of $\int F$ are pairs $(a,x)$ with
$a\in\operatorname{\mathscr{A}}$ and $x\in F(a)$, and a morphism
$(a,x)\to(a^{\prime},x^{\prime})$ is a morphism $f\colon a\to a^{\prime}$ in
$\operatorname{\mathscr{A}}$ such that $F(f)(x^{\prime})=x$ (see, e.g., [28,
§I.5]). Unravelling the definition above, we see that a presheaf
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
has the amalgamation property if, for all spans of morphisms

${b}$${{\cdot}}$${a}$$\scriptstyle{g}$$\scriptstyle{f}$

in $\operatorname{\mathscr{A}}$ and elements $x\in F(a)$ and $y\in F(b)$ such
that $F(f)(x)=F(g)(y)$, there exist a commutative square

${{\cdot}}$${a}$${b}$${c}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{g^{\prime}}$$\scriptstyle{f^{\prime}}$

in $\operatorname{\mathscr{A}}$ and $z\in F(c)$ such that $F(g^{\prime})(z)=x$
and $F(f^{\prime})(z)=y$.

######  Lemma 3.1.

Any representable functor
$\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$ has
the amalgamation property.

###### Proof.

It suffices to show that, for an arbitrary object
$a\in\operatorname{\mathscr{A}}$, the functor
$\mathcal{y}_{a}\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
has the amalgamation property. The statement then follows because the
amalgamation property for presheaves is preserved under natural isomorphisms.

Consider a span of morphisms

${b}$${{\cdot}}$${c}$$\scriptstyle{g}$$\scriptstyle{f}$

in $\operatorname{\mathscr{A}}$ and let $h\in\mathcal{y}_{a}(c)$ and
$k\in\mathcal{y}_{a}(b)$ satisfy
$\mathcal{y}_{a}(f)(h)=\mathcal{y}_{a}(g)(k)$. The latter equation amounts to
the commutativity of the following square:

${{\cdot}}$${c}$${b}$${a}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{h}$$\scriptstyle{k}$

Observe that the identity morphism $\mathrm{id}_{a}\in\mathcal{y}_{a}(a)$
satisfies $\mathcal{y}_{a}(h)(\mathrm{id}_{a})=h$ and
$\mathcal{y}_{a}(k)(\mathrm{id}_{a})=k$, and so $\mathcal{y}_{a}$ has the
amalgamation property. ∎

When the category $\operatorname{\mathscr{A}}$ admits pushouts, the
amalgamation property for presheaves
$\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$ can
be rephrased as follows. Recall that a commutative square

${u}$${s}$${t}$${{\cdot}}$$\scriptstyle{j^{\prime}}$$\scriptstyle{i^{\prime}}$$\scriptstyle{i}$$\scriptstyle{j}$

in $\operatorname{\mathbf{Set}}$ is a _quasi-pullback_ if the unique mediating
morphism $u\to p$, where $p$ is the pullback of $i$ along $j$, is a
surjection. In other words, whenever $x\in s$ and $y\in t$ satisfy
$i(x)=j(y)$, there is a (not necessarily unique) $z\in u$ such that
$j^{\prime}(z)=x$ and $i^{\prime}(z)=y$.

We have the following elementary result:

######  Lemma 3.2.

Let $\operatorname{\mathscr{A}}$ be a category with pushouts. The following
statements are equivalent for any functor
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$:

  1. (1)

$F$ has the amalgamation property.

  2. (2)

$F$ sends pushout squares in $\operatorname{\mathscr{A}}$ to quasi-pullbacks
in $\operatorname{\mathbf{Set}}$.

Note that, whenever $\operatorname{\mathscr{A}}$ has pushouts, Lemma 3.1 can
be deduced from Lemma 3.2 and the fact that representable functors preserve
limits. Further, in this case any presheaf
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
that is a filtered colimit of representable ones has the amalgamation
property. Just recall that filtered colimits in $\operatorname{\mathbf{Set}}$
commute with finite limits (see e.g. [27, Theorem 1 p. 215]).

###  3.2. Polyadic sets and Stirling kernels

######  Definition 3.3.

A _polyadic set_ on a category $\operatorname{\mathscr{A}}$ is a functor

$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$

with the amalgamation property. If, in addition, the sets $F(a)$ are finite
for all $a\in\operatorname{\mathscr{A}}$, then $F$ is called a _polyadic
finite set_.

Let $\operatorname{\mathbf{FinSet}}$ denote the full subcategory of
$\operatorname{\mathbf{Set}}$ defined by the finite sets. Throughout this
paper, we shall identify polyadic finite sets with functors
${\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{FinSet}}}$
satisfying the amalgamation property.

Note that, with this terminology, Lemma 3.1 states that all representable
presheaves are polyadic sets.

######  Remark 3.4.

Polyadic sets are a discrete variant of Joyal’s notion of polyadic space [21],
which we now recall. Let $\operatorname{\mathbf{Stone}}$ denote the category
of _Stone spaces_ (i.e., zero-dimensional compact Hausdorff spaces, also known
as _Boolean spaces_) and continuous maps. In [21], a _polyadic space_ (on
$\operatorname{\mathbf{FinSet}}$) is defined to be a functor

$F\colon\operatorname{\mathbf{FinSet}}^{\mathrm{op}}\to\operatorname{\mathbf{Stone}}$

satisfying the following conditions:

  1. (i)

$F$ sends pushout squares in $\operatorname{\mathbf{FinSet}}$ to quasi-
pullbacks222A commutative square in $\operatorname{\mathbf{Stone}}$ is a
quasi-pullback if its image under the underlying-set functor
$\operatorname{\mathbf{Stone}}\to\operatorname{\mathbf{Set}}$ is a quasi-
pullback in $\operatorname{\mathbf{Set}}$. in $\operatorname{\mathbf{Stone}}$.

  2. (ii)

$F(f)$ is an open map for any morphism $f$ in
$\operatorname{\mathbf{FinSet}}$.

The observation that condition (i) above can be generalised in terms of the
amalgamation property is due to Marquès [30].

By Stone duality between $\operatorname{\mathbf{Stone}}$ and the category
$\operatorname{\mathbf{Boole}}$ of Boolean algebras and their homomorphisms
[42], polyadic spaces can be identified with the pointwise duals of Boolean
hyperdoctrines
${\operatorname{\mathbf{FinSet}}\to\operatorname{\mathbf{Boole}}}$. For a
thorough account of this connection, we refer the interested reader to [30].

Polyadic sets are obtained by dispensing with condition (ii) above, which has
a topological nature. In particular, note that a polyadic finite set (on
$\operatorname{\mathbf{FinSet}}$) is the same as a polyadic space
$F\colon\operatorname{\mathbf{FinSet}}^{\mathrm{op}}\to\operatorname{\mathbf{Stone}}$
such that, for all $n\in\operatorname{\mathbf{FinSet}}$, $F(n)$ is a finite
(equivalently, discrete) space.

For the remainder of this section, we fix an arbitrary category
$\operatorname{\mathscr{A}}$ equipped with a _proper factorisation system_
$(\mathscr{Q},\mathscr{M})$. That is, a weak factorisation system such that
every $\mathscr{Q}$-morphism is an epimorphism and every
$\mathscr{M}$-morphism is a monomorphism. For more details and some basic
properties of these factorisation systems, see Appendix A. We refer to
$\mathscr{M}$-morphisms as _embeddings_ and denote them by $\rightarrowtail$.
$\mathscr{Q}$-morphisms will be referred to as _quotients_ and denoted by
$\twoheadrightarrow$. A _proper quotient_ is a quotient that is not an
isomorphism (in view of Lemma A.2(b) in the appendix, proper quotients can be
identified with arrows in $\mathscr{Q}\setminus\mathscr{M}$).

The following easy observation will come in handy in the following.

######  Lemma 3.5.

Any polyadic set
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
sends quotients in $\operatorname{\mathscr{A}}$ to injections.

###### Proof.

Let $f\colon n\twoheadrightarrow m$ be a quotient in
$\operatorname{\mathscr{A}}$ and let $s,t\in F(m)$ be arbitrary elements
satisfying $F(f)(s)=F(f)(t)$. By the amalgamation property for $F$ there are a
commutative diagram

${n}$${m}$${m}$${p}$$\scriptstyle{f}$$\scriptstyle{f}$$\scriptstyle{h}$$\scriptstyle{g}$

and an element $u\in F(p)$ such that $F(h)(u)=s$ and $F(g)(u)=t$. Since
$g\circ f=h\circ f$ and $f$ is an epimorphism, we get $g=h$. Thus,
$s=F(g)(u)=t$ and so $F(f)$ is injective. ∎

Next, we introduce the _Stirling kernel_ construction for polyadic sets. This
notion is due to Joyal in the more general context of polyadic
spaces333Private e-mail communication. (see Paré’s work [35] for a special
case) and has been further explored by Marquès in [30].

Before giving a formal definition, let us motivate the idea underlying
Stirling kernels with an example. Consider the polyadic set

$\operatorname{\mathbf{FinSet}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}},\quad
n\mapsto[0,1]^{n}$

obtained by restricting the representable functor
$\mathcal{y}_{[0,1]}\colon\operatorname{\mathbf{Set}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$,
where $[0,1]$ is the unit interval regarded as a set. Each (generalised) cube
$[0,1]^{n}$ can be decomposed into smaller ‘pieces’. Some of these pieces will
have maximal dimension, i.e. dimension $n$, while the others will have lower
dimension. The decomposition of $[0,1]$ is the trivial one consisting of a
single piece, namely $[0,1]$ itself (dimension $1$). Moving one dimension up,
the square $[0,1]^{2}$ can be decomposed into its diagonal (dimension $1$) and
two triangles (dimension $2$):

Similarly, $[0,1]^{3}$ can be decomposed into its diagonal, consisting of the
points $(x,y,z)$ such that $x=y=z$, the six triangles depicted below
consisting of the points where exactly two of the coordinates are equal,

(0,0,0)(1,1,1) (0,0,0)(1,1,1) (0,0,0)(1,1,1)

along with the remaining three-dimensional (convex) polyhedra. (All these
decompositions are determined by the polyadic set in a canonical way.) The
Stirling kernel of this polyadic set associates with a finite set $n$ the
subset of $[0,1]^{n}$ defined by the ‘generic’ points, i.e. those points that
belong to a piece of maximal dimension in the decomposition; equivalently, the
points whose coordinates are all distinct. The discussion above for $n\leq 3$
suggests that in the passage from the polyadic set to its Stirling kernel no
essential information is lost: a cube $[0,1]^{n}$ can be fully reconstructed
as long as we know the generic points of all cubes $[0,1]^{m}$ with $m\leq n$.

######  Definition 3.6.

Given a polyadic set
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
and an object $n\in\operatorname{\mathscr{A}}$, we say that an element $x\in
F(n)$ is _degenerate_ if there exist a proper quotient $f\colon
n\twoheadrightarrow m$ and an element $y\in F(m)$ such that $F(f)(y)=x$. The
elements of $F(n)$ that are not degenerate are called _generic_. The subset of
$F(n)$ consisting of the generic elements is denoted by $F^{\bullet}(n)$.

If $g$ is a morphism in $\operatorname{\mathscr{A}}$, then the function $F(g)$
need not preserve generic elements. However, this is the case when $g$ is an
embedding. This is the content of the following lemma, where we denote by
$\operatorname{\mathscr{A}}_{*}$ the category with the same objects as
$\operatorname{\mathscr{A}}$ and morphisms the embeddings in
$\operatorname{\mathscr{A}}$. (The dual of the category
$\operatorname{\mathscr{A}}_{*}$ is denoted by
$\operatorname{\mathscr{A}}_{*}^{\mathrm{op}}$, in place of the unwieldy
$(\operatorname{\mathscr{A}}_{*})^{\mathrm{op}}$.)

######  Lemma 3.7.

Let
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be a polyadic set. The assignment

${n\mapsto F^{\bullet}(n)}$

yields a functor
$F^{\bullet}\colon\operatorname{\mathscr{A}}_{*}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$.

###### Proof.

It suffices to show that, for all embeddings $g\colon n\rightarrowtail
n^{\prime}$ in $\operatorname{\mathscr{A}}$, the map $F(g)\colon
F(n^{\prime})\to F(n)$ preserves generic elements, for then it restricts to a
map $F^{\bullet}(n^{\prime})\to F^{\bullet}(n)$ (functoriality is clear).

Let $x\in F(n^{\prime})$ be an arbitrary generic element. Suppose that there
exist a quotient $f\colon n\twoheadrightarrow m$ and an element $y\in F(m)$
such that $F(f)(y)=F(g)(x)$. By Lemma A.5 in the appendix, the span formed by
$f$ and $g$ can be completed to a commutative square

${n}$${m}$${n^{\prime}}$${p}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{g^{\prime}}$$\scriptstyle{f^{\prime}}$

and there exists $z\in F(p)$ satisfying $F(f^{\prime})(z)=x$ (and
$F(g^{\prime})(z)=y$). As $f^{\prime}$ is a quotient and $x$ is generic,
$f^{\prime}$ must be an isomorphism. It follows easily by Lemma A.2(a),(b),(f)
that $f$ is an isomorphism. Therefore, $F(g)(x)$ is a generic element of
$F(n)$. ∎

######  Definition 3.8.

The _Stirling kernel_ of a polyadic set
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
is the functor
$F^{\bullet}\colon\operatorname{\mathscr{A}}_{*}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$.

In Corollary 3.13 below we shall see that, under mild assumptions on
$\operatorname{\mathscr{A}}$, the Stirling kernel of a polyadic set on
$\operatorname{\mathscr{A}}$ is a polyadic set on
$\operatorname{\mathscr{A}}_{*}$.

The next example will play a pivotal role in the study of homomorphism
counting results.

######  Example 3.9.

Let
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be any representable presheaf. Up to a natural isomorphism, we can assume that
$F=\mathcal{y}_{a}$ for some object $a\in\operatorname{\mathscr{A}}$. By Lemma
3.1, $F$ is a polyadic set. Its Stirling kernel
$F^{\bullet}\colon\operatorname{\mathscr{A}}_{*}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
sends an object $b\in\operatorname{\mathscr{A}}$ to the set $\mathscr{M}(b,a)$
of all embeddings $b\rightarrowtail a$. In other words, an element of
$F(b)=\mathcal{y}_{a}(b)$ is generic if, and only if, it is an embedding. This
was proved in [9, Lemma 11]; for the sake of completeness, we provide a proof
of this fact.

Let $f$ be an arbitrary element of $\mathcal{y}_{a}(b)$. Assume that $f$ is
generic, and take its $(\mathscr{Q},\mathscr{M})$ factorisation:

${b}$${c}$${a}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{h}$

Since $\mathcal{y}_{a}(g)(h)=f$ and the latter is generic, $g$ must be an
embedding. By Lemma A.2(a), $f=h\circ g$ is also an embedding.

Conversely, suppose that $f$ is an embedding and pick a quotient $g\colon
b\twoheadrightarrow c$ and an element $h\in\mathcal{y}_{a}(c)$ such that
$\mathcal{y}_{a}(g)(h)=f$, i.e. $h\circ g=f$. By Lemma A.2(f), $g$ is an
embedding, so it is not a proper quotient. It follows that $f$ is generic.

The next proposition shows that, under mild assumptions, a polyadic set can be
recovered from its Stirling kernel (as an appropriate left Kan
extension).444For applications to homomorphism counting in the next section,
we will only need the first part of Proposition 3.10. The reader unfamiliar
with the concept of Kan extension can safely ignore the second part of the
lemma. This observation is due to Joyal (for polyadic spaces), see also [30];
the proof offered below is a simple adaptation to the discrete case.

For all objects $a\in\operatorname{\mathscr{A}}$, we denote by
$\mathscr{Q}(a)$ and $\mathscr{M}(a)$, respectively, the poset of quotients of
$a$ and the poset of embeddings of $a$; for a definition, see Appendix A.
Loosely speaking, the elements of $\mathscr{Q}(a)$ are equivalence classes of
quotients from $a$, and the elements of $\mathscr{M}(a)$ are equivalence
classes of embeddings into $a$. The category $\operatorname{\mathscr{A}}$ is
said to be _$\mathscr{Q}$ -well-founded_ if, for all objects
$a\in\operatorname{\mathscr{A}}$, the poset $\mathscr{Q}(a)$ is well-founded.
That is, any non-empty subset of $\mathscr{Q}(a)$ has a minimal element.
Similarly, $\operatorname{\mathscr{A}}$ is _$\mathscr{M}$ -well-founded_ if,
for all objects $a\in\operatorname{\mathscr{A}}$, the poset $\mathscr{M}(a)$
is well-founded.

######  Proposition 3.10.

Let
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be a polyadic set and assume that $\operatorname{\mathscr{A}}$ is
$\mathscr{Q}$-well-founded. The following statements hold:

  1. (a)

For all $n\in\operatorname{\mathscr{A}}$,

$F(n)\cong\coprod_{n\twoheadrightarrow m}F^{\bullet}(m)$

where the coproduct is indexed by the set $\mathscr{Q}(n)$.

  2. (b)

$F\cong\operatorname{Lan}_{J}F^{\bullet}$, where
$\operatorname{Lan}_{J}F^{\bullet}$ is the left Kan extension of $F^{\bullet}$
along the inclusion functor
$J\colon\operatorname{\mathscr{A}}_{*}^{\mathrm{op}}\hookrightarrow\operatorname{\mathscr{A}}^{\mathrm{op}}$.

###### Proof.

(a) Let $\operatorname{\mathscr{A}}$ and
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be as in the statement. For each quotient $f\colon n\twoheadrightarrow m$ in
$\mathscr{Q}(n)$, the function $F(f)\colon F(m)\to F(n)$ is an injection by
Lemma 3.5. Let $\xi_{f}\colon F^{\bullet}(m)\rightarrowtail F(n)$ be the
obvious restriction of $F(f)$. By the universal property of the coproduct in
$\operatorname{\mathbf{Set}}$, the family of functions $\\{\xi_{f}\mid
f\in\mathscr{Q}(n)\\}$ induces a unique map

$\xi\colon\coprod_{n\twoheadrightarrow m}F^{\bullet}(m)\to F(n).$

We claim that $\xi$ is a bijection. For injectivity, suppose that there are
quotients $f_{1}\colon n\twoheadrightarrow m_{1}$, $f_{2}\colon
n\twoheadrightarrow m_{2}$ and elements $x_{1}\in F^{\bullet}(m_{1})$ and
$x_{2}\in F^{\bullet}(m_{2})$ such that $\xi(x_{1})=\xi(x_{2})$. That is,
$F(f_{1})(x_{1})=F(f_{2})(x_{2})$. By the amalgamation property for $F$ and
Lemma A.5, there are quotients $g_{1}\colon m_{1}\twoheadrightarrow p$ and
$g_{2}\colon m_{2}\twoheadrightarrow p$ making the square below commute,

${n}$${m_{1}}$${m_{2}}$${p}$$\scriptstyle{f_{1}}$$\scriptstyle{f_{2}}$$\scriptstyle{g_{1}}$$\scriptstyle{g_{2}}$

and $y\in F(p)$ such that $F(g_{1})(y)=x_{1}$ and $F(g_{2})(y)=x_{2}$. As
$x_{1}$ and $x_{2}$ are generic, $g_{1}$ and $g_{2}$ must be isomorphisms. In
particular, the isomorphism $g_{2}^{-1}\circ g_{1}\colon m_{1}\to m_{2}$
witnesses the fact that $f_{1}=f_{2}$ as elements of $\mathscr{Q}(n)$. Since
$\xi$ is injective on each summand, it follows that $x_{1}=x_{2}$.

For surjectivity of $\xi$, suppose that $x\in F(n)$ and consider the set

$S\coloneqq\\{f\in\mathscr{Q}(n)\mid F(f)^{-1}(x)\neq\emptyset\\}.$

If $S=\emptyset$, then $x\in F^{\bullet}(n)$ and thus it belongs to the image
of $\xi$. Therefore, assume that $S$ is non-empty. Because
$\operatorname{\mathscr{A}}$ is $\mathscr{Q}$-well-founded, $S$ has a minimal
element $g\colon n\twoheadrightarrow m$. Let $y\in F(m)$ be such that
$F(g)(y)=x$. As $g$ is minimal, $y$ must belong to $F^{\bullet}(m)$, and so
$x$ is in the image of $\xi$.

(b) Fix an arbitrary object $n\in\operatorname{\mathscr{A}}$. Consider the
composite functor

${G\colon
J{\downarrow}n}$${\operatorname{\mathscr{A}}_{*}^{\mathrm{op}}}$${\operatorname{\mathbf{Set}}}$$\scriptstyle{\pi}$$\scriptstyle{F^{\bullet}}$

where $J{\downarrow}n$ is the comma category and $\pi$ sends an object
$(m,J(m)\to n)$, where $J(m)\to n$ is an arrow in
$\operatorname{\mathscr{A}}^{\mathrm{op}}$, to its first component $m$. In
view of Lemma A.4(a), we can replace without loss of generality the category
$J{\downarrow}n$ with its full subcategory $\operatorname{\mathscr{D}}$
consisting of the pairs $(m,J(m)\to n)$ whose second components correspond to
quotients in $\operatorname{\mathscr{A}}$. Note that
$\operatorname{\mathscr{D}}$ is a groupoid, i.e. every arrow in
$\operatorname{\mathscr{D}}$ is an isomorphism. Just observe that a morphism

$(m^{\prime},J(m^{\prime})\to n)\to(m,J(m)\to n)$

in $\operatorname{\mathscr{D}}$ corresponds to a commutative triangle

${n}$${m}$${m^{\prime}}$

in $\operatorname{\mathscr{A}}$, and by Lemma A.2(e),(b) the horizontal arrow
in necessarily an isomorphism. Upon choosing representatives, this is
equivalent to considering the small diagram

${G^{\prime}\colon\mathscr{Q}(n)^{\mathrm{op}}}$${\operatorname{\mathscr{A}}_{*}^{\mathrm{op}}}$${\operatorname{\mathbf{Set}}}$$\scriptstyle{\pi^{\prime}}$$\scriptstyle{F^{\bullet}}$

where $\mathscr{Q}(n)$ is regarded as a set (i.e., a discrete category) and
$\pi^{\prime}$ sends (the equivalence class of) a quotient
$n\twoheadrightarrow m$ in $\operatorname{\mathscr{A}}$ to its codomain.

The colimit of $G$ thus coincides with the coproduct
$\coprod_{n\twoheadrightarrow m}F^{\bullet}(m)$ indexed by the set
$\mathscr{Q}(n)$. Moreover, any morphism $h\colon n\to n^{\prime}$ in
$\operatorname{\mathscr{A}}$ induces a unique function

$\coprod_{n\twoheadrightarrow m^{\prime}}F^{\bullet}(m^{\prime})\
\longleftarrow\ \coprod_{n^{\prime}\twoheadrightarrow m}F^{\bullet}(m)$

whose restriction to $F^{\bullet}(m)$, for all (representatives of equivalence
classes of) quotients ${f\colon n^{\prime}\twoheadrightarrow m}$, is the
function $F^{\bullet}(m)\to F^{\bullet}(m^{\prime})$ obtained by applying
$F^{\bullet}$ to the bottom horizontal arrow in the following commutative
diagram.

${n}$${n^{\prime}}$${m^{\prime}}$${m}$$\scriptstyle{h}$$\scriptstyle{f}$

By item (a), and the colimit formula for pointwise left Kan extensions (cf.
[27, Theorem 1 p. 237] for the dual statement), we see that
$F\cong\operatorname{Lan}_{J}F^{\bullet}$. ∎

We illustrate the previous proposition by means of an example, which also
justifies the terminology _Stirling kernel_ :

######  Example 3.11.

Let
$F\colon\operatorname{\mathbf{FinSet}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be any polyadic set on the category $\operatorname{\mathbf{FinSet}}$, and
equip the latter with the usual (surjective, injective) factorisation system.
We denote by $\uline{n}\in\operatorname{\mathbf{FinSet}}$ an $n$-element set.
For all non-negative integers $m\leq n$, the number of non-equivalent
surjections $\uline{n}\twoheadrightarrow\uline{m}$ in $\mathscr{Q}(\uline{n})$
coincides with the number of ways to partition an $n$-element set into $m$
non-empty subsets. This is commonly denoted by $S(n,m)$ and known as the
_Stirling number of the second kind_ associated with the pair $(n,m)$, see
e.g. [15, §1.5]. Therefore, denoting by $k\,\uline{n}$ the disjoint sum of $k$
copies of $\uline{n}$, Proposition 3.10 yields the formula

$F(\uline{n})\cong\coprod_{m\leq n}S(n,m)\,F^{\bullet}(\uline{m})$

for all finite sets $\uline{n}$. In particular, if $F$ is a polyadic finite
set, we get

$|F(\uline{n})|=\sum_{m\leq n}S(n,m)\cdot|F^{\bullet}(\uline{m})|.$

######  Remark 3.12.

The assumption in Proposition 3.10 that $\operatorname{\mathscr{A}}$ be
$\mathscr{Q}$-well-founded is necessary, even when $F$ is a polyadic _finite_
set. For instance, let $\operatorname{\mathscr{A}}$ be the set $\mathbb{N}$ of
natural numbers with the usual total order, regarded as a category. If
$\operatorname{\mathscr{A}}$ is equipped with the factorisation system
$(\mathscr{Q},\mathscr{M})$ where $\mathscr{Q}$ consists of all morphisms, and
$\mathscr{M}$ consists of the identity morphisms, then
$\operatorname{\mathscr{A}}_{*}$ is the category with set of objects
$\mathbb{N}$ and no arrows but identities. Note that
$\operatorname{\mathscr{A}}$ is not $\mathscr{Q}$-well-founded. Just observe
that, for all $n\in\operatorname{\mathscr{A}}$, the strictly increasing
sequence of natural numbers $n<n+1<n+2<\cdots$ induces the strictly decreasing
sequence

$n\twoheadrightarrow n+1\twoheadrightarrow n+2\twoheadrightarrow\cdots$

in $\mathscr{Q}(n)$. Thus, the latter is not well-founded. Now, let $a$ be any
non-empty finite set, and let
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{FinSet}}$
be the constant functor of value $a$. It is not difficult to see that $F$ is a
polyadic finite set, and
${F^{\bullet}\colon\operatorname{\mathscr{A}}_{*}^{\mathrm{op}}\to\operatorname{\mathbf{FinSet}}}$
is the constant functor of value $\emptyset$. Then
${\operatorname{Lan}_{J}F^{\bullet}\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{FinSet}}}$
is also the constant functor of value $\emptyset$ and so
$F\not\cong\operatorname{Lan}_{J}F^{\bullet}$.

######  Corollary 3.13.

Let $\operatorname{\mathscr{A}}$ be $\mathscr{Q}$-well-founded. The Stirling
kernel of a polyadic (finite) set on $\operatorname{\mathscr{A}}$ is a
polyadic (finite) set on $\operatorname{\mathscr{A}}_{*}$.

###### Proof.

Let $\operatorname{\mathscr{A}}$ be as in the statement and let
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be an arbitrary polyadic set. We claim that
$F^{\bullet}\colon\operatorname{\mathscr{A}}_{*}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
has the amalgamation property. Consider embeddings $f_{1}\colon
n\rightarrowtail m_{1}$, $f_{2}\colon n\rightarrowtail m_{2}$ and generic
elements $s\in F^{\bullet}(m_{1})$ and $t\in F^{\bullet}(m_{2})$ such that
$F(f_{1})(s)=F(f_{2})(t)$. By the amalgamation property for $F$, there exist a
commutative square

${n}$${m_{1}}$${m_{2}}$${p}$$\scriptstyle{f_{1}}$$\scriptstyle{f_{2}}$$\scriptstyle{g_{2}}$$\scriptstyle{g_{1}}$

in $\operatorname{\mathscr{A}}$ and an element $u\in F(p)$ such that
$F(g_{2})(u)=s$ and $F(g_{1})(u)=t$. By Proposition 3.10(a), there exist a
quotient $h\colon p\twoheadrightarrow q$ and a generic element $v\in
F^{\bullet}(q)$ such that $F(h)(v)=u$. Clearly, we have

$F(h\circ g_{2})(v)=s\ \text{ and }\ F(h\circ g_{1})(v)=t.$

It suffices to show that $h\circ g_{1}$ and $h\circ g_{2}$ are embeddings, for
then the following commutative square in $\operatorname{\mathscr{A}}_{*}$
shows that $F^{\bullet}$ has the amalgamation property.

${n}$${m_{1}}$${m_{2}}$${q}$$\scriptstyle{f_{1}}$$\scriptstyle{f_{2}}$$\scriptstyle{h\circ
g_{2}}$$\scriptstyle{h\circ g_{1}}$

To see that $h\circ g_{1}$ is an embedding, take its
$(\mathscr{Q},\mathscr{M})$ factorisation:

${m_{2}}$${q}$${{\cdot}}$$\scriptstyle{e}$$\scriptstyle{h\circ
g_{1}}$$\scriptstyle{l}$

Let $x\coloneqq F(l)(v)$. As $F(e)(x)=t$ and $t$ is generic, it follows that
$e$ is an isomorphism. Therefore, $h\circ g_{1}$ is an embedding by Lemma
A.2(a),(b). The same proof, mutatis mutandis, shows that $h\circ g_{2}$ is an
embedding.

Finally, note that if $F$ is a polyadic _finite_ set, then so is
$F^{\bullet}$. ∎

###  3.3. Pointwise isomorphisms

The main result of this section (Proposition 3.15 below) states that, under
appropriate assumptions, whenever two polyadic finite sets are pointwise
isomorphic, their Stirling kernels are also pointwise isomorphic. This
observation is at the core of the homomorphism counting results presented in
Sections 4 and 5.

Recall that two parallel functors
$F,G\colon\operatorname{\mathscr{C}}\to\operatorname{\mathscr{D}}$ are
_pointwise isomorphic_ if, for all $c\in\operatorname{\mathscr{C}}$, there is
an isomorphism $\eta_{c}\colon F(c)\to G(c)$ in $\operatorname{\mathscr{D}}$.
This contrasts with the concept of _natural isomorphism_ between $F$ and $G$,
whereby the isomorphisms $\eta_{c}$ are required to be natural in $c$.

In view of Proposition 3.10, if $F$ and $G$ are polyadic sets whose Stirling
kernels $F^{\bullet}$ and $G^{\bullet}$ are pointwise isomorphic, then $F$ and
$G$ are also pointwise isomorphic. The converse holds for polyadic _finite_
sets and follows from an application of the Möbius inversion formula, due to
Gian-Carlo Rota.

Recall that, given a finite555More generally, throughout this paragraph we
could consider a _locally finite_ poset, i.e. a poset $P$ such that, for all
$x,y\in P$, the interval $[x,y]\coloneqq\\{z\in P\mid x\leq z\leq y\\}$ is
finite. poset $P$, the _incidence algebra_ of $P$ has as elements the
functions $f\colon P\times P\to\mathbb{R}$ satisfying $f(x,y)=0$ whenever
${x\not\leq y}$. These functions form an associative algebra over the reals
with respect to pointwise sum, pointwise multiplication by scalars, and the
convolution product $h=fg$ defined as

$h(x,y)\coloneqq\sum_{x\leq z\leq y}f(x,z)g(z,y).$

The identity element of the incidence algebra is the Kronecker function
$\delta(x,y)$ satisfying $\delta(x,y)=1$ if $x=y$ and $\delta(x,y)=0$
otherwise. The _zeta function_ of $P$ is the element $\zeta(x,y)$ of the
incidence algebra such that $\zeta(x,y)=1$ if $x\leq y$ and $\zeta(x,y)=0$
otherwise. The function $\zeta$ is invertible in the incidence algebra, see
[39, Proposition 1], and its (two-sided) inverse $\mu$ is called the _Möbius
function of $P$_.

######  Lemma 3.14 (Möbius inversion formula [39]).

Let $P$ be a finite poset and let $f_{1},f_{2}\colon P\to\mathbb{R}$ be any
two functions. For all $y\in P$,

$f_{1}(y)=\sum_{x\leq y}{f_{2}(x)}\enspace\Longleftrightarrow\enspace
f_{2}(y)=\sum_{x\leq y}{f_{1}(x)\mu(x,y)},$

where $\mu$ is the Möbius function of $P$.

######  Proposition 3.15.

Suppose that $\operatorname{\mathscr{A}}$ is $\mathscr{Q}$-well-founded, and
let $F,G$ be polyadic finite sets on $\operatorname{\mathscr{A}}$. If $F$ and
$G$ are pointwise isomorphic, then so are their Stirling kernels $F^{\bullet}$
and $G^{\bullet}$.

###### Proof.

Let
$F,G\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{FinSet}}$
be any two polyadic finite sets, and suppose that they are pointwise
isomorphic. We must prove that $F^{\bullet}(n)\cong G^{\bullet}(n)$ for all
$n\in\operatorname{\mathscr{A}}$. Let us fix an arbitrary object
$n\in\operatorname{\mathscr{A}}$. By Proposition 3.10(a), we know that

$F(n)\cong\coprod_{n\twoheadrightarrow m}F^{\bullet}(m).$

As the left-hand side is a finite set, there exist finitely many quotients

$q_{1}\colon n\twoheadrightarrow m_{1},\ \ldots,\ q_{l}\colon
n\twoheadrightarrow m_{l}$

such that $F(n)\cong\coprod_{i=1}^{l}F^{\bullet}(m_{i})$. Similarly, there are
finitely many quotients

$q_{l+1}\colon n\twoheadrightarrow m_{l+1},\ \ldots,\ q_{u}\colon
n\twoheadrightarrow m_{u}$

such that $G(n)\cong\coprod_{i=l+1}^{u}G^{\bullet}(m_{i})$. Let $P$ be the
sub-poset of $\mathscr{Q}(n)$ defined by the elements $q_{1},\ldots,q_{u}$ and
the identity of $n$. For convenience of notation, we let $m_{0}\coloneqq n$
and let $q_{0}\colon n\twoheadrightarrow m_{0}$ be the identity. Note that
$q_{0}$ is the top element of $P$. Clearly,
$F(n)\cong\coprod_{i=0}^{u}F^{\bullet}(m_{i})$ and
$G(n)\cong\coprod_{i=0}^{u}G^{\bullet}(m_{i})$.

Consider the functions on $P$ determined, for all $i\in\\{0,\ldots,u\\}$, by
the cardinalities of $F(m_{i})$ and $F^{\bullet}(m_{i})$, respectively:

$f_{1}\colon P\to\mathbb{N},\ \ f_{1}(q_{i})\coloneqq|F(m_{i})|$

and

$f_{2}\colon P\to\mathbb{N},\ \ f_{2}(q_{i})\coloneqq|F^{\bullet}(m_{i})|.$

Then $f_{1}(q_{0})=\sum_{x\in P}f_{2}(x)$ and so, by the Möbius inversion
formula,

$f_{2}(q_{0})=\sum_{x\in P}f_{1}(x)\mu(x,q_{0})$

where $\mu$ is the Möbius function of the poset $P$. Reasoning in a similar
manner for the functions $g_{1},g_{2}\colon P\to\mathbb{N}$ defined by
$g_{1}(q_{i})\coloneqq|G(m_{i})|$ and
$g_{2}(q_{i})\coloneqq|G^{\bullet}(m_{i})|$, we get

$g_{2}(q_{0})=\sum_{x\in P}g_{1}(x)\mu(x,q_{0}).$

By assumption, for all $i\in\\{0,\ldots,u\\}$, we have $|F(m_{i})|=|G(m_{i})|$
and so $f_{1}(q_{i})=g_{1}(q_{i})$. We conclude that
$f_{2}(q_{0})=g_{2}(q_{0})$, i.e. $F^{\bullet}(n)\cong G^{\bullet}(n)$. ∎

If the category $\operatorname{\mathscr{A}}$ has pushouts, then Proposition
3.15 can be proved by exploiting the inclusion-exclusion principle (see e.g.
[41, §2.1]), rather than the Möbius inversion formula, in which case we can
dispense with the assumption that $\operatorname{\mathscr{A}}$ be
$\mathscr{Q}$-well-founded. This is an immediate consequence of a result in
[9], and will come in handy in Section 5.

######  Proposition 3.16.

Suppose that $\operatorname{\mathscr{A}}$ has pushouts, and let $F,G$ be
polyadic finite sets on $\operatorname{\mathscr{A}}$. If $F$ and $G$ are
pointwise isomorphic, then so are their Stirling kernels $F^{\bullet}$ and
$G^{\bullet}$.

###### Proof.

This was proved in [9, Lemma 12] whenever
$F,G\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{FinSet}}$
are functors sending pushout squares in $\operatorname{\mathscr{A}}$
consisting of quotients to pullback squares in
$\operatorname{\mathbf{FinSet}}$. (The proof of the aforementioned result
relies on the inclusion-exclusion principle.)

In turn, every polyadic (finite) set has this property. Just observe that, by
Lemmas 3.2 and 3.5, a polyadic set
$\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$ sends
pushout squares of quotients in $\operatorname{\mathscr{A}}$ to quasi-
pullbacks of injections. But a quasi-pullback in $\operatorname{\mathbf{Set}}$
consisting of injections is a pullback, because the unique mediating map into
the pullback is both injective and surjective. ∎

##  4\. Homomorphism Counting in Locally Finite Categories

We shall now exploit the framework of Section 3, and in particular Proposition
3.15, to establish a homomorphism counting result for so-called locally finite
categories (Theorem 4.3 below).

######  Definition 4.1.

A category $\operatorname{\mathscr{A}}$ is _locally finite_ if, for all
objects $a,b\in\operatorname{\mathscr{A}}$, the set
$\hom_{\operatorname{\mathscr{A}}}(a,b)$ is finite.

To start with, we record for future reference a well known and easily proved
fact about finite monoids. Recall that a monoid $(M,{\cdot},1)$ satisfies the
_left-cancellation law_ provided that, for all $x,y,z\in M$,

$x\cdot y=x\cdot z\enspace\Longrightarrow\quad y=z.$

######  Lemma 4.2.

A finite monoid satisfying the left-cancellation law is a group.

######  Theorem 4.3.

Let $\operatorname{\mathscr{A}}$ be a locally finite category admitting a
proper factorisation system $(\mathscr{Q},\mathscr{M})$ such that
$\operatorname{\mathscr{A}}$ is $\mathscr{Q}$-well-founded. Then
$\operatorname{\mathscr{A}}$ is right-combinatorial.

###### Proof.

Let $\operatorname{\mathscr{A}}$ be as in the statement. For any object
$a\in\operatorname{\mathscr{A}}$, the representable functor
$\mathcal{y}_{a}\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{FinSet}}$
is a polyadic finite set by Lemma 3.1, and its Stirling kernel sends an object
$c\in\operatorname{\mathscr{A}}$ to the finite set $\mathscr{M}(c,a)$
consisting of the embeddings $c\rightarrowtail a$ (see Example 3.9).

Now, if $a,b\in\operatorname{\mathscr{A}}$ are any two objects such that
$\mathcal{y}_{a}(c)\cong\mathcal{y}_{b}(c)$ for all
$c\in\operatorname{\mathscr{A}}$ then, by Proposition 3.15,
$\mathscr{M}(c,a)\cong\mathscr{M}(c,b)$ for all
$c\in\operatorname{\mathscr{A}}$. In particular, as $\mathscr{M}(a,a)$ is non-
empty (it contains the identity arrow), there exists an embedding
$i\in\mathscr{M}(a,b)$. Similarly, there exists an embedding
$j\in\mathscr{M}(b,a)$. Note that, by Lemma A.2(a), $j\circ
i\in\mathscr{M}(a,a)$. Lemma 4.2, combined with the fact that every embedding
is a monomorphism, entails that the set $\mathscr{M}(a,a)$ equipped with the
composition operation is a group. So, $j\circ i$ has an inverse. It follows by
Lemma A.2(b),(e) that $j$ is an isomorphism. ∎

######  Remark 4.4.

A variant of Theorem 4.3, where $\mathscr{Q}$ is the collection of extremal
epimorphisms and $\mathscr{M}$ is the collection of monomorphisms, and each
poset of embeddings $\mathscr{M}(a)$ is finite, was proved by Pultr [36,
Theorem 2.2] exploiting a direct generalisation of Lovász’ original counting
argument [25].

Furthermore, reasoning along the same lines as in the previous proof, we get
the following variant of Theorem 4.3 by applying Proposition 3.16 instead of
Proposition 3.15: _A locally finite category admitting pushouts and a proper
factorisation system is right-combinatorial_. This result was first proved in
[9, Theorem 5].

Theorem 4.3 admits a dual version (cf. Remark A.3 in the appendix):

######  Theorem 4.5.

Let $\operatorname{\mathscr{A}}$ be a locally finite category admitting a
proper factorisation system $(\mathscr{Q},\mathscr{M})$ such that
$\operatorname{\mathscr{A}}$ is $\mathscr{M}$-well-founded. Then
$\operatorname{\mathscr{A}}$ is left-combinatorial.

We conclude this section with several examples of applications of Theorems 4.3
and 4.5.

######  Example 4.6.

Let $\mathscr{V}$ be any variety of universal algebras (regarded as a
category, with morphisms the homomorphisms). By Theorems 4.3 and 4.5, the full
subcategory $\mathscr{V}_{\mathrm{fin}}$ of $\mathscr{V}$ consisting of the
finite members is combinatorial. Just observe that, if
$(\mathscr{Q},\mathscr{M})$ is the proper factorisation system consisting of
surjective and injective homomorphisms, respectively, then
$\mathscr{V}_{\mathrm{fin}}$ is both $\mathscr{Q}$-well-founded and
$\mathscr{M}$-well-founded. For instance, the following classes of algebras
are combinatorial: finite Boolean algebras, finite monoids, finite groups, and
finite Abelian groups.

######  Example 4.7.

Generalising the previous example, let $\operatorname{\mathscr{C}}$ be any
class of universal algebras closed under taking subalgebras. Then the usual
factorisation system in the category of all algebras for the given algebraic
signature, given by surjective and injective homomorphisms, respectively,
restricts to $\operatorname{\mathscr{C}}$. Thus, $\operatorname{\mathscr{C}}$
is combinatorial. A similar fact holds if $\operatorname{\mathscr{C}}$ is
closed under taking homomorphic images. For example, the following classes of
algebras are closed under homomorphic images and therefore combinatorial:
finite regular semigroups, finite inverse semigroups, and finite $p$-groups
(cf. [18, Lemma 2.4.4], [8, Lemma 7.35], and [40, Exercise 6(c) p. 32],
respectively).

######  Example 4.8.

Let $\sigma$ be a relational signature, i.e. a (possibly infinite) set of
relation symbols of finite arity, and let $\mathscr{R}(\sigma)$ be the
category of $\sigma$-structures with their homomorphisms. Then the full
subcategory $\mathscr{R}_{\mathrm{fin}}(\sigma)$ of $\mathscr{R}(\sigma)$
defined by the _finite_ $\sigma$-structures is combinatorial; for a finite
signature $\sigma$, this is precisely Lovász’ homomorphism counting theorem
[25].

First, recall that epimorphisms and monomorphisms in $\mathscr{R}(\sigma)$
coincide, respectively, with the surjective and injective homomorphisms.
Further, strong epimorphisms (respectively, strong monomorphisms) coincide
with the epimorphisms (respectively, monomorphisms) that reflect the relation
symbols. The same holds in $\mathscr{R}_{\mathrm{fin}}(\sigma)$.

Now, note that the factorisation system $(\mathscr{Q},\mathscr{M})$ in
$\mathscr{R}_{\mathrm{fin}}(\sigma)$, where $\mathscr{Q}$ consists of the
strong epimorphisms and $\mathscr{M}$ of the monomorphisms, is proper and
$\mathscr{R}_{\mathrm{fin}}(\sigma)$ is $\mathscr{Q}$-well-founded. Thus,
$\mathscr{R}_{\mathrm{fin}}(\sigma)$ is right-combinatorial by Theorem 4.3. On
the other hand, the factorisation system
$(\mathscr{Q}^{\prime},\mathscr{M}^{\prime})$ in
$\mathscr{R}_{\mathrm{fin}}(\sigma)$, where $\mathscr{Q}^{\prime}$ consists of
the epimorphisms and $\mathscr{M}^{\prime}$ of the strong monomorphisms, is
also proper and $\mathscr{R}_{\mathrm{fin}}(\sigma)$ is
$\mathscr{M}^{\prime}$-well-founded. So, $\mathscr{R}_{\mathrm{fin}}(\sigma)$
is left-combinatorial in view of Theorem 4.5.

Therefore, $\mathscr{R}_{\mathrm{fin}}(\sigma)$ is combinatorial. Observe
that, when $\sigma$ is infinite, the category
$\mathscr{R}_{\mathrm{fin}}(\sigma)$ need not be $\mathscr{Q}^{\prime}$-well-
founded nor $\mathscr{M}$-well-founded.

##  5\. Beyond Locally Finite Categories

In Theorem 4.3 we saw that a large class of locally finite categories is
right-combinatorial. The main result of this section (Theorem 5.10 below) is a
‘local’ extension of this fact to categories that need not be locally finite.
This result is then specialised to the case of locally finitely presentable
categories.

###  5.1. Nerves and hom-spaces

Throughout this section we fix a category $\operatorname{\mathscr{D}}$
admitting a proper factorisation system $(\mathscr{Q},\mathscr{M})$, and a
full subcategory $\operatorname{\mathscr{C}}$ of $\operatorname{\mathscr{D}}$
such that:

  1. (i)

$\operatorname{\mathscr{C}}$ is a _dense_ subcategory of
$\operatorname{\mathscr{D}}$, i.e. every $a\in\operatorname{\mathscr{D}}$ is
the colimit of the canonical diagram given by the forgetful functor
$\operatorname{\mathscr{C}}{\downarrow}a\to\operatorname{\mathscr{D}}$.

  2. (ii)

$\operatorname{\mathscr{C}}$ has all finite colimits and they are preserved by
the inclusion functor
$\operatorname{\mathscr{C}}\hookrightarrow\operatorname{\mathscr{D}}$.

  3. (iii)

For every composite $a\twoheadrightarrow b\rightarrowtail c$ in
$\operatorname{\mathscr{D}}$, if $a,c\in\operatorname{\mathscr{C}}$ then also
$b\in\operatorname{\mathscr{C}}$.

######  Remark 5.1.

Because $\operatorname{\mathscr{C}}$ is closed in $\operatorname{\mathscr{D}}$
under finite colimits by item (ii), the diagrams of the form
$\operatorname{\mathscr{C}}{\downarrow}a\to\operatorname{\mathscr{D}}$ in item
(i) are automatically directed.

Further, item (iii) amounts to saying that the proper factorisation system
$(\mathscr{Q},\mathscr{M})$ in $\operatorname{\mathscr{D}}$ restricts to a
(proper) factorisation system in $\operatorname{\mathscr{C}}$. This condition
is satisfied, e.g., if $\operatorname{\mathscr{C}}$ is closed in
$\operatorname{\mathscr{D}}$ under $\mathscr{Q}$-images (i.e., given a
quotient $a\twoheadrightarrow b$ in $\operatorname{\mathscr{D}}$, if
$a\in\operatorname{\mathscr{C}}$ then also $b\in\operatorname{\mathscr{C}}$)
or under $\mathscr{M}$-subobjects. Also, note that item (iii) implies that
$\operatorname{\mathscr{C}}$ is closed in $\operatorname{\mathscr{D}}$ under
isomorphisms.

Given an object $a\in\operatorname{\mathscr{D}}$, let
$N_{a}\colon\operatorname{\mathscr{C}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be the restriction of the presheaf
$\mathcal{y}_{a}\colon\operatorname{\mathscr{D}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
to $\operatorname{\mathscr{C}}^{\mathrm{op}}$. We consider the _nerve functor_

$N\colon\operatorname{\mathscr{D}}\to\widehat{\operatorname{\mathscr{C}}},\quad
a\mapsto N_{a}.$

In Theorem 5.10, we will identify a class of objects of
$\operatorname{\mathscr{D}}$ such that any two objects in this class are
isomorphic precisely when their images under the nerve functor are pointwise
isomorphic.

It is useful to observe that the nerve functor is full and faithful because
$\operatorname{\mathscr{C}}$ is a dense subcategory of
$\operatorname{\mathscr{D}}$ (see e.g. [3, p. 218]). Hence, $N$ is
conservative (that is, it reflects isomorphisms). Explicitly, this means that
a morphism $f\colon a\to b$ in $\operatorname{\mathscr{D}}$ is an isomorphism
if, and only if, the function

$f\circ-\colon N_{a}(c)\to N_{b}(c)$

is a bijection for every $c\in\operatorname{\mathscr{C}}$.

Since we want to be able to count morphisms from objects of
$\operatorname{\mathscr{C}}$, it makes sense to restrict our attention to
those objects of $\operatorname{\mathscr{D}}$ that look ‘finite’ from the
viewpoint of every object of $\operatorname{\mathscr{C}}$:

######  Definition 5.2.

An object $a\in\operatorname{\mathscr{D}}$ is of _finite
$\operatorname{\mathscr{C}}$-type_ provided that the set
$\hom_{\operatorname{\mathscr{D}}}(c,a)$ is finite for each
$c\in\operatorname{\mathscr{C}}$.

######  Example 5.3.

The previous definition makes sense for all categories
$\operatorname{\mathscr{D}}$ equipped with a (full) subcategory
$\operatorname{\mathscr{C}}$. For instance, let $\operatorname{\mathscr{D}}$
be the opposite of the category of groups and group homomorphisms, and let
$\operatorname{\mathscr{C}}$ be the full subcategory of
$\operatorname{\mathscr{D}}$ defined by the finite groups. Then any finitely
generated group is of finite $\operatorname{\mathscr{C}}$-type, because there
are finitely many homomorphisms from a finitely generated group to a finite
one.

######  Lemma 5.4.

Let $a\in\operatorname{\mathscr{D}}$ be an object of finite
$\operatorname{\mathscr{C}}$-type. The following statements hold:

  1. (a)

The nerve
$N_{a}\colon\operatorname{\mathscr{C}}^{\mathrm{op}}\to\operatorname{\mathbf{FinSet}}$
is a polyadic finite set.

  2. (b)

The Stirling kernel of $N_{a}$ sends an object
$c\in\operatorname{\mathscr{C}}$ to the set $\mathscr{M}(c,a)$ of embeddings
$c\rightarrowtail a$.

###### Proof.

First we show that, for any polyadic set
$F\colon\operatorname{\mathscr{D}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$,
its restriction to $\operatorname{\mathscr{C}}^{\mathrm{op}}$ is also a
polyadic set. Item (a) then follows at once from Lemma 3.1.

Let
$F\colon\operatorname{\mathscr{D}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be an arbitrary polyadic set. Since $\operatorname{\mathscr{C}}$ has pushouts,
by Lemma 3.2 it suffices to show that $F$ sends pushout squares in
$\operatorname{\mathscr{C}}$ to quasi-pullbacks in
$\operatorname{\mathbf{Set}}$. Consider a pushout square in
$\operatorname{\mathscr{C}}$ as on the left-hand side below and the
corresponding square in $\operatorname{\mathbf{Set}}$ as on the right-hand
side.

${{\cdot}}$${a}$${b}$${c}$$\scriptstyle{g}$$\scriptstyle{f}$
${F(\cdot)}$${F(a)}$${F(b)}$${F(c)}$$\scriptstyle{F(f)}$$\scriptstyle{F(g)}$

If $x\in F(a)$ and $y\in F(b)$ are such that $F(f)(x)=F(g)(y)$, by the
amalgamation property of $F$ there exist $d\in\operatorname{\mathscr{D}}$,
morphisms $f^{\prime}\colon b\to d$ and $g^{\prime}\colon a\to d$ such that
$f^{\prime}\circ g=g^{\prime}\circ f$, and an element $z\in F(d)$ such that
$F(g^{\prime})(z)=x$ and $F(f^{\prime})(z)=y$. Because the inclusion
$\operatorname{\mathscr{C}}\hookrightarrow\operatorname{\mathscr{D}}$
preserves pushouts, there exists a unique morphism $h\colon c\to d$ making the
ensuing diagram commute. The element $F(h)(z)\in F(c)$ then witnesses the fact
that the rightmost square above is a quasi-pullback.

Item (b) follows by reasoning as in Example 3.9, using the fact that the
factorisation system in $\operatorname{\mathscr{D}}$ restricts to a proper
factorisation system in $\operatorname{\mathscr{C}}$. ∎

Consider any two objects $a,b\in\operatorname{\mathscr{D}}$ and the canonical
colimit cocone

$\\{b_{i}\to b\mid i\in I\\}$

in $\operatorname{\mathscr{D}}$ where each $b_{i}$ belongs to
$\operatorname{\mathscr{C}}$. We have an isomorphism

$\mathcal{y}_{a}(b)\cong\lim_{i\in I}\mathcal{y}_{a}(b_{i})$

in the category of sets. Let us assume that $a$ is of finite
$\operatorname{\mathscr{C}}$-type, so that each
$\mathcal{y}_{a}(b_{i})=N_{a}(b_{i})$ is finite. Note that the diagram
consisting of the $b_{i}$’s is directed (see Remark 5.1). So, if we equip the
sets $\mathcal{y}_{a}(b_{i})$ with the discrete topologies, the hom-set
$\mathcal{y}_{a}(b)$ carries a natural Stone (i.e. compact, Hausdorff and
zero-dimensional) topology, namely the inverse limit topology. Explicitly,
this is the topology generated by the sets of the form

${\mathscr{U}_{\langle u,v\rangle}\coloneqq\\{h\in\mathcal{y}_{a}(b)\mid
h\circ u=v\\}}$
${c}$${b}$${a}$$\scriptstyle{u}$$\scriptstyle{v}$$\scriptstyle{h}$

for $c\in\operatorname{\mathscr{C}}$, $u\in N_{b}(c)$ and $v\in N_{a}(c)$.

Let us denote by $E_{a}(b)$ the ‘hom-space’ obtained by endowing the set
$\mathcal{y}_{a}(b)$ with the Stone topology just described.666Although we
shall not need this fact in the following, let us point out that the
assignment $b\mapsto E_{a}(b)$ yields a functor
$E_{a}\colon\operatorname{\mathscr{D}}^{\mathrm{op}}\to\operatorname{\mathbf{Stone}}$
which extends
$\mathcal{y}_{a}\colon\operatorname{\mathscr{D}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$.
Next, we prove some useful properties of the space of endomorphisms
$E_{a}(a)$:

######  Lemma 5.5.

The following statements hold for every $a\in\operatorname{\mathscr{D}}$ of
finite $\operatorname{\mathscr{C}}$-type:

  1. (a)

$E_{a}(a)$ is a topological monoid with respect to composition.

  2. (b)

$\mathscr{M}(a,a)$ is a closed submonoid of $E_{a}(a)$.

###### Proof.

For item (a), we must prove that the composition operation

$\circ\colon E_{a}(a)\times E_{a}(a)\to E_{a}(a),\enspace(f,g)\mapsto f\circ
g$

is continuous. Consider $(f,g)\in E_{a}(a)\times E_{a}(a)$ and an open
neighbourhood $\mathscr{U}_{\langle u,v\rangle}$ of $f\circ g$. Then the set
$\mathscr{U}_{\langle g\circ u,v\rangle}\times\mathscr{U}_{\langle u,g\circ
u\rangle}$ is an open neighbourhood of $(f,g)$ whose image is contained in
$\mathscr{U}_{\langle u,v\rangle}$. Just observe that, for all
$(f^{\prime},g^{\prime})\in\mathscr{U}_{\langle g\circ
u,v\rangle}\times\mathscr{U}_{\langle u,g\circ u\rangle}$, we have
$f^{\prime}\circ g^{\prime}\circ u=f^{\prime}\circ g\circ u=v$. Hence, the
composition operation is continuous.

For item (b), suppose that $f\in E_{a}(a)$ is not an embedding. We must find
an open neighbourhood $V$ of $f$ disjoint from $\mathscr{M}(a,a)$. Because $f$
is not an isomorphism and the nerve functor
$N\colon\operatorname{\mathscr{D}}\to\widehat{\operatorname{\mathscr{C}}}$ is
conservative, there exists $c\in\operatorname{\mathscr{C}}$ such that the map

$f\circ-\colon N_{a}(c)\to N_{a}(c)$

is not a bijection. Since $N_{a}(c)$ is a finite set, $f\circ-$ cannot be
injective. Hence, there exist distinct morphisms $u,v\in N_{a}(c)$ such that
$f\circ u=f\circ v$. The set $V\coloneqq\mathscr{U}_{\langle u,f\circ
u\rangle}\cap\mathscr{U}_{\langle v,f\circ v\rangle}$ is clearly an open
neighbourhood of $f$. We claim that $V$ is disjoint from $\mathscr{M}(a,a)$.
Assume, by way of contradiction, that $g\colon a\rightarrowtail a$ is an
embedding that belongs to $V$. Then $g\circ u=f\circ u=f\circ v=g\circ v$. As
$g$ is a monomorphism we get $u=v$, a contradiction. ∎

######  Remark 5.6.

Recall that a topological monoid is profinite if, and only if, its underlying
space is Stone [34]. Thus, it follows by Lemma 5.5 that $E_{a}(a)$ and
$\mathscr{M}(a,a)$ are profinite monoids.

Lemma 4.2 for finite monoids admits a non-trivial generalisation to
topological monoids, which we now recall. This result will be applied in (the
proof of) Theorem 5.10 to the topological monoids $\mathscr{M}(a,a)$ as in
Lemma 5.5.

######  Lemma 5.7 (Numakura’s Lemma [33, Lemma 2L]).

Let $S$ be a topological monoid whose topology is compact and Hausdorff. If
$S$ satisfies the left-cancellation law then it is a group.

We are interested in determining when two non-isomorphic objects
$a,b\in\operatorname{\mathscr{D}}$ of finite $\operatorname{\mathscr{C}}$-type
can be distinguished by counting the number of morphisms from objects of
$\operatorname{\mathscr{C}}$. To this end, we will assume that $a$ and $b$
satisfy an additional ‘separability’ property. (The latter is satisfied by any
object of a locally finitely presentable category
$\operatorname{\mathscr{D}}$, for an appropriate choice of the subcategory
$\operatorname{\mathscr{C}}$, cf. the proof of Theorem 5.12.)

######  Definition 5.8.

An object of $\operatorname{\mathscr{D}}$ is _$\operatorname{\mathscr{C}}$
-separable_ if it is the colimit of a directed diagram $J$ in
$\operatorname{\mathscr{C}}$ such that:

  1. (i)

The colimit cocone consists of embeddings.

  2. (ii)

For every compatible cocone of embeddings over $J$, the unique connecting
morphism is also an embedding.

Intuitively, an object $a$ is $\operatorname{\mathscr{C}}$-separable if there
exists a (directed) family $S$ of $\mathscr{M}$-subobjects of $a$ such that,
for all objects $d\in\operatorname{\mathscr{D}}$, $a$ can be embedded into $d$
precisely when all objects in $S$ can be embedded coherently into $d$ (and,
moreover, $a$ is the union of its subobjects in $S$).

######  Remark 5.9.

Note that, by Lemma A.2(f), item (i) in the previous definition implies that
the diagram $J$ consists entirely of embeddings.

We are now in a position to prove the main result of this section:

######  Theorem 5.10.

For any two $\operatorname{\mathscr{C}}$-separable objects
$a,b\in\operatorname{\mathscr{D}}$ of finite
$\operatorname{\mathscr{C}}$-type,

$a\cong
b\enspace\Longleftrightarrow\enspace\hom_{\operatorname{\mathscr{D}}}(c,a)\cong\hom_{\operatorname{\mathscr{D}}}(c,b)\
\text{ for all }c\in\operatorname{\mathscr{C}}.$

###### Proof.

Let $a,b\in\operatorname{\mathscr{D}}$ be as in the statement. For the non-
trivial direction, suppose that
$\hom_{\operatorname{\mathscr{D}}}(c,a)\cong\hom_{\operatorname{\mathscr{D}}}(c,b)$
for all $c\in\operatorname{\mathscr{C}}$. By assumption, $b$ is the colimit of
a directed diagram $\\{b_{i}\mid i\in I\\}$ in $\operatorname{\mathscr{C}}$
satisfying the conditions in Definition 5.8. Therefore,
$b\cong\operatornamewithlimits{colim}_{D}b_{i}$ entails

$\mathcal{y}_{a}(b)\cong\lim_{i\in I}N_{a}(b_{i}),$

i.e. the map associating with a compatible cocone $\\{b_{i}\to a\mid i\in
I\\}$ the unique connecting morphism $b\to a$ is a bijection. If each finite
set $N_{a}(b_{i})$ is equipped with the discrete topology, then the induced
inverse limit topology $\tau$ on $\mathcal{y}_{a}(b)$ coincides with the
topology of $E_{a}(b)$ and so we have a homeomorphism of Stone spaces

$E_{a}(b)\cong\lim_{i\in I}N_{a}(b_{i}).$ (2)

Just observe that the diagram of the $b_{i}$’s is a subdiagram of the
canonical diagram given by (the image of) the forgetful functor
$\operatorname{\mathscr{C}}{\downarrow}b\to\operatorname{\mathscr{D}}$, and so
the identity map $E_{a}(b)\to(\mathcal{y}_{a}(b),\tau)$ is continuous. In
turn, since any two comparable compact Hausdorff topologies on a set must
coincide, the two topologies are one and the same.

The space $\lim_{i\in I}\mathscr{M}(b_{i},a)$, endowed with the inverse limit
topology, can be identified with a subspace of $\lim_{i\in I}N_{a}(b_{i})$. We
claim that the homeomorphism in (2) restricts to a homeomorphism between
$\mathscr{M}(a,b)$ and $\lim_{i\in I}\mathscr{M}(b_{i},a)$. If a compatible
cocone $\\{b_{i}\to a\mid i\in I\\}$ induces a connecting morphism $b\to a$
that is an embedding then Lemma A.2(a), combined with item (i) in the
definition of a $\operatorname{\mathscr{C}}$-separable object and Remark 5.9,
entails that each $b_{i}\to a$ is an embedding. Conversely, if $\\{b_{i}\to
a\mid i\in I\\}$ is a compatible cocone consisting of embeddings then the
unique connecting morphism is an embedding by item (ii) in the definition of a
$\operatorname{\mathscr{C}}$-separable object. Hence, $\mathscr{M}(b,a)$ is
homeomorphic to $\lim_{i\in I}\mathscr{M}(b_{i},a)$.

By assumption, the nerves
$N_{a},N_{b}\colon\operatorname{\mathscr{C}}^{\mathrm{op}}\to\operatorname{\mathbf{FinSet}}$
are pointwise isomorphic. It follows by Proposition 3.16 and Lemma 5.4(a) that
their Stirling kernels are also pointwise isomorphic. So, by Lemma 5.4(b),

$\mathscr{M}(b_{i},a)\cong\mathscr{M}(b_{i},b)$

for every $i\in I$. As the sets $\mathscr{M}(b_{i},b)$ are non-empty (they
contain the colimit maps), we conclude that the space $\mathscr{M}(b,a)$ is
the inverse limit of non-empty finite discrete spaces and thus
$\mathscr{M}(b,a)\neq\emptyset$ (see e.g. [17, Theorem 2-85]). That is, there
exists an embedding $\alpha\colon b\rightarrowtail a$. By symmetry, there
exists also an embedding $\beta\colon a\rightarrowtail b$.

The composite $\alpha\circ\beta$ belongs to the monoid $\mathscr{M}(a,a)$,
which is a Stone topological monoid by Lemma 5.5. It follows by Numakura’s
Lemma that $\alpha\circ\beta$ has an inverse and so $\alpha$ is an isomorphism
by Lemma A.2(b),(e). ∎

###  5.2. Locally finitely presentable categories

In this section we specialise Theorem 5.10 to the case of locally finitely
presentable categories. To start with, we recall some basic definitions; for a
more thorough treatment, the reader can consult e.g. [5].

An object $a$ of a category $\operatorname{\mathscr{A}}$ is _finitely
presentable_ (respectively, _finitely generated_) if the associated covariant
hom-functor

$\hom_{\operatorname{\mathscr{A}}}(a,-)\colon\operatorname{\mathscr{A}}\to\operatorname{\mathbf{Set}}$

preserves directed colimits (respectively, directed colimits of
monomorphisms). A category $\operatorname{\mathscr{A}}$ is said to be _locally
finitely presentable_ if it is cocomplete, every object is a directed colimit
of finitely presentable objects, and there exists, up to isomorphism, only a
set of finitely presentable objects.

Let $\operatorname{\mathscr{A}}$ be a locally finitely presentable category.
Then $\operatorname{\mathscr{A}}$ admits a proper factorisation system
$(\mathscr{Q},\mathscr{M})$ where $\mathscr{Q}$ consists of the strong
epimorphisms and $\mathscr{M}$ of the monomorphisms. Further, an object
$a\in\operatorname{\mathscr{A}}$ is finitely generated if, and only if, there
exist a finitely presentable object $b\in\operatorname{\mathscr{A}}$ and a
quotient (i.e., a strong epimorphism) $b\twoheadrightarrow a$. For a proof of
these facts see, e.g., [5, Propositions 1.61 and 1.69(ii)]. Throughout, we
denote by $\operatorname{\mathscr{A}}_{\mathrm{fp}}$ and
$\operatorname{\mathscr{A}}_{\mathrm{fg}}$ the full subcategories of
$\operatorname{\mathscr{A}}$ consisting, respectively, of the finitely
presentable and finitely generated objects.

In this context, the role of the dense subcategory
$\operatorname{\mathscr{C}}$ in Theorem 5.10 is played by
$\operatorname{\mathscr{A}}_{\mathrm{fg}}$. However, it is an easy observation
that any object of finite $\operatorname{\mathscr{A}}_{\mathrm{fp}}$-type is
also of finite $\operatorname{\mathscr{A}}_{\mathrm{fg}}$-type:

######  Lemma 5.11.

Let $\operatorname{\mathscr{A}}$ be a locally finitely presentable category.
An object of $\operatorname{\mathscr{A}}$ is of finite
$\operatorname{\mathscr{A}}_{\mathrm{fp}}$-type if, and only if, it is of
finite $\operatorname{\mathscr{A}}_{\mathrm{fg}}$-type.

###### Proof.

For the non-trivial direction, suppose that $a$ is of finite
$\operatorname{\mathscr{A}}_{\mathrm{fp}}$-type and consider an arbitrary
$b\in\operatorname{\mathscr{A}}_{\mathrm{fg}}$. If $f\colon
c\twoheadrightarrow b$ is a quotient with $c$ finitely presentable, the map
$-\circ
f\colon\hom_{\operatorname{\mathscr{A}}}(b,a)\to\hom_{\operatorname{\mathscr{A}}}(c,a)$
is injective. Since the latter set is finite, so is the former. ∎

######  Theorem 5.12.

Let $\operatorname{\mathscr{A}}$ be a locally finitely presentable category.
For any two objects $a,b\in\operatorname{\mathscr{A}}$ of finite
$\operatorname{\mathscr{A}}_{\mathrm{fp}}$-type,

$a\cong
b\enspace\Longleftrightarrow\enspace\hom_{\operatorname{\mathscr{A}}}(c,a)\cong\hom_{\operatorname{\mathscr{A}}}(c,b)\
\text{ for all }c\in\operatorname{\mathscr{A}}_{\mathrm{fg}}.$

###### Proof.

Recall that $\operatorname{\mathscr{A}}_{\mathrm{fg}}$ is a dense subcategory
of $\operatorname{\mathscr{A}}$ because so is
$\operatorname{\mathscr{A}}_{\mathrm{fp}}$ (see e.g. [5, Proposition 1.22]),
and it is closed in $\operatorname{\mathscr{A}}$ under $\mathscr{Q}$-images
(see e.g. [5, Proposition 1.69(i)]). Further, it is a folklore result that
$\operatorname{\mathscr{A}}_{\mathrm{fg}}$ has all finite colimits and these
are preserved by the inclusion functor
$\operatorname{\mathscr{A}}_{\mathrm{fg}}\hookrightarrow\operatorname{\mathscr{A}}$.
Finally, every object of $\operatorname{\mathscr{A}}$ is
$\operatorname{\mathscr{A}}_{\mathrm{fg}}$-separable (cf. [5, Proposition 1.62
and Theorem 1.70]). Therefore, an application of Theorem 5.10 with
$\operatorname{\mathscr{D}}\coloneqq\operatorname{\mathscr{A}}$ and
$\operatorname{\mathscr{C}}\coloneqq\operatorname{\mathscr{A}}_{\mathrm{fg}}$,
combined with Lemma 5.11, yields the statement. ∎

We now specialise Theorem 5.12 to ind- and pro-categories. The ensuing results
are then applied in concrete cases in Section 6. A further application of
Theorem 5.12, this time to categories of coalgebras for certain comonads, is
presented in Section 5.3.

Given a (essentially small) category $\operatorname{\mathscr{C}}$, denote its
_ind-completion_ and _pro-completion_ by
$\operatorname{Ind}(\operatorname{\mathscr{C}})$ and
$\operatorname{Pro}(\operatorname{\mathscr{C}})$, respectively (see e.g. [20,
§VI.1]). These are, respectively, the free cocompletion of
$\operatorname{\mathscr{C}}$ under filtered colimits, and the free completion
of $\operatorname{\mathscr{C}}$ under cofiltered limits. Up to an equivalence
of categories, we can and will identify $\operatorname{\mathscr{C}}$ with a
full subcategory of $\operatorname{Ind}(\operatorname{\mathscr{C}})$ and
$\operatorname{Pro}(\operatorname{\mathscr{C}})$, respectively.

######  Corollary 5.13.

Let $\operatorname{\mathscr{C}}$ be an essentially small category with finite
colimits that is closed under strong epimorphic images in
$\operatorname{Ind}(\operatorname{\mathscr{C}})$. For all objects
$a,b\in\operatorname{Ind}(\operatorname{\mathscr{C}})$ of finite
$\operatorname{\mathscr{C}}$-type,

$a\cong
b\enspace\Longleftrightarrow\enspace\hom_{\operatorname{Ind}(\operatorname{\mathscr{C}})}(c,a)\cong\hom_{\operatorname{Ind}(\operatorname{\mathscr{C}})}(c,b)\
\text{ for all }c\in\operatorname{\mathscr{C}}.$

###### Proof.

If $\operatorname{\mathscr{C}}$ is essentially small and has finite colimits
then $\operatorname{Ind}(\operatorname{\mathscr{C}})$ is a locally finitely
presentable category; see e.g. [20, Corollary VI.1.3] and [5, Theorem 1.46].
Furthermore, every finitely presentable object of
$\operatorname{Ind}(\operatorname{\mathscr{C}})$ is isomorphic to an object of
$\operatorname{\mathscr{C}}$ (this follows from the fact that
$\operatorname{\mathscr{C}}$ has finite colimits, hence it is idempotent-
complete, combined with [23, Exercise 6.1(iii)]). The same is true of finitely
generated objects of $\operatorname{Ind}(\operatorname{\mathscr{C}})$, as
$\operatorname{\mathscr{C}}$ is closed under strong epimorphic images in
$\operatorname{Ind}(\operatorname{\mathscr{C}})$. Therefore, the statement
follows directly from Theorem 5.12. ∎

We record for future reference the dual version of Corollary 5.13.

######  Corollary 5.14.

Let $\operatorname{\mathscr{C}}$ be an essentially small category with finite
limits that is closed under strong subobjects in
$\operatorname{Pro}(\operatorname{\mathscr{C}})$. Let
$a,b\in\operatorname{Pro}(\operatorname{\mathscr{C}})$ be such that the sets
$\hom_{\operatorname{Pro}(\operatorname{\mathscr{C}})}(a,c)$ and
$\hom_{\operatorname{Pro}(\operatorname{\mathscr{C}})}(b,c)$ are finite for
all $c\in\operatorname{\mathscr{C}}$. Then

$a\cong
b\enspace\Longleftrightarrow\enspace\hom_{\operatorname{Pro}(\operatorname{\mathscr{C}})}(a,c)\cong\hom_{\operatorname{Pro}(\operatorname{\mathscr{C}})}(b,c)\
\text{ for all }c\in\operatorname{\mathscr{C}}.$

###  5.3. Coalgebras for comonads of finite rank

In this section we specialise Theorem 5.12 to categories of coalgebras for
comonads on locally finitely presentable categories.

Whenever $T$ is a comonad on a category $\operatorname{\mathscr{A}}$, we write
$\mathbf{EM}(T)$ for the category of Eilenberg-Moore coalgebras for $T$, and

${\operatorname{\mathscr{A}}}$$\bot$${\mathbf{EM}(T)}$$\scriptstyle{F}$$\scriptstyle{U}$

for the associated adjunction. For the latter notions, see Appendix B. In the
next result, we will assume that $\operatorname{\mathscr{A}}$ is locally
finitely presentable and $T$ is of _finite rank_ , and so the category
$\mathbf{EM}(T)$ is also locally finitely presentable. Comonads of finite rank
were defined by Diers in [10]; for a definition and some basic facts, we refer
the reader to Appendix B.

######  Corollary 5.15.

Let $\operatorname{\mathscr{A}}$ be a locally finitely presentable category
and let $T$ be a comonad of finite rank on $\operatorname{\mathscr{A}}$ with
associated adjunction $U\dashv F$. The following statements are equivalent for
all objects $a,b\in\operatorname{\mathscr{A}}$ of finite
$\operatorname{\mathscr{A}}_{\mathrm{fp}}$-type:

  1. (1)

$F(a)\cong F(b)$.

  2. (2)

For all $x\in\mathbf{EM}(T)_{\mathrm{fg}}$,

$\hom_{\operatorname{\mathscr{A}}}(U(x),a)\cong\hom_{\operatorname{\mathscr{A}}}(U(x),b).$

###### Proof.

Since $T$ is of finite rank, Theorem B.5 in the appendix entails that the
category $\mathbf{EM}(T)$ is locally finitely presentable and the forgetful
functor

$U\colon\mathbf{EM}(T)\to\operatorname{\mathscr{A}}$

preserves (and reflects) finitely presentable objects.

Note that the object $F(a)$ is of finite $\mathbf{EM}(T)_{\mathrm{fp}}$-type
whenever $a$ is of finite $\operatorname{\mathscr{A}}_{\mathrm{fp}}$-type.
Just observe that, for all $x\in\mathbf{EM}(T)_{\mathrm{fp}}$,

$\hom_{\mathbf{EM}(T)}(x,F(a))\cong\hom_{\operatorname{\mathscr{A}}}(U(x),a)$

which is a finite set because $U(x)$ is finitely presentable. Therefore, the
statement follows by an application of Theorem 5.12. ∎

######  Remark 5.16.

Suppose we are in the situation of the previous corollary. In view of
Corollary B.6 in the appendix, if the finitely presentable objects in
$\operatorname{\mathscr{A}}$ coincide with the finitely generated ones, then
the same holds in $\mathbf{EM}(T)$.

In this case, Corollary 5.15 states that, for all objects
$a,b\in\operatorname{\mathscr{A}}$ of finite
$\operatorname{\mathscr{A}}_{\mathrm{fp}}$-type, $F(a)\cong F(b)$ if, and only
if,

$\hom_{\operatorname{\mathscr{A}}}(U(x),a)\cong\hom_{\operatorname{\mathscr{A}}}(U(x),b)$

for all $x\in\mathbf{EM}(T)$ such that $U(x)$ is finitely presentable.

This occurs, for instance, when
$\operatorname{\mathscr{A}}=\operatorname{\mathbf{Set}}$ or
$\operatorname{\mathscr{A}}=\mathscr{R}(\sigma)$ is the category of
$\sigma$-structures for a finite relational signature $\sigma$. A similar
remark applies to Corollary 5.17 below.

We include a ‘relative’ version of Corollary 5.15 which will be needed in
Section 6.3 for applications to finite-variable logics. To this end, given a
functor $G\colon\operatorname{\mathscr{C}}\to\operatorname{\mathscr{D}}$ and a
full subcategory $\tilde{\operatorname{\mathscr{C}}}$ of
$\operatorname{\mathscr{C}}$, we write $G[\tilde{\operatorname{\mathscr{C}}}]$
for the full subcategory of $\operatorname{\mathscr{D}}$ defined by the
objects of the form $G(c)$ with $c\in\tilde{\operatorname{\mathscr{C}}}$.

######  Corollary 5.17.

Let $\operatorname{\mathscr{A}}^{\prime}$ be a locally finitely presentable
category and assume that there is a full and faithful functor
$J\colon\operatorname{\mathscr{A}}\hookrightarrow\operatorname{\mathscr{A}}^{\prime}$
with a left adjoint $H$. Let $T,T^{\prime}$ be comonads on
$\operatorname{\mathscr{A}}$ and $\operatorname{\mathscr{A}}^{\prime}$,
respectively, with associated adjunctions ${U\dashv F}$ and ${U^{\prime}\dashv
F^{\prime}}$. Suppose $T^{\prime}$ is of finite rank and the adjunction
$H\dashv J$ restricts to functors
$U[\mathbf{EM}_{\mathrm{fg}}(T)]\leftrightarrows
U^{\prime}[\mathbf{EM}_{\mathrm{fg}}(T^{\prime})]$:

${\operatorname{\mathscr{A}}}$$\bot$${\operatorname{\mathscr{A}}^{\prime}}$${U[\mathbf{EM}_{\mathrm{fg}}(T)]}$${U^{\prime}[\mathbf{EM}_{\mathrm{fg}}(T^{\prime})]}$$\scriptstyle{J}$$\scriptstyle{H}$

The following are equivalent for all objects
$a,b\in\operatorname{\mathscr{A}}$ of finite
$\operatorname{\mathscr{A}}_{\mathrm{fp}}$-type:

  1. (1)

$F^{\prime}J(a)\cong F^{\prime}J(b)$.

  2. (2)

For all $x\in\mathbf{EM}(T)_{\mathrm{fg}}$,

$\hom_{\operatorname{\mathscr{A}}}(U(x),a)\cong\hom_{\operatorname{\mathscr{A}}}(U(x),b).$

###### Proof.

In view of Corollary 5.15, item 1 in the statement is equivalent to saying
that, for all $x^{\prime}\in\mathbf{EM}(T^{\prime})_{\mathrm{fg}}$,

$\hom_{\operatorname{\mathscr{A}}^{\prime}}(U^{\prime}(x),J(a))\cong\hom_{\operatorname{\mathscr{A}}^{\prime}}(U^{\prime}(x),J(b)).$
(3)

In turn, it is an easy observation that the latter condition is equivalent to
item 2 in the statement. This is essentially the content of [9, Lemma 27]; for
the sake of completeness, we provide a proof. Suppose that equation (3) holds
for all $x^{\prime}\in\mathbf{EM}(T^{\prime})_{\mathrm{fg}}$, and fix an
arbitrary $x\in\mathbf{EM}(T)_{\mathrm{fg}}$. We have

$\displaystyle\hom_{\operatorname{\mathscr{A}}}(U(x),a)$
$\displaystyle\cong\hom_{\operatorname{\mathscr{A}}^{\prime}}(JU(x),J(a))$
($J$ full and faithful)
$\displaystyle\cong\hom_{\operatorname{\mathscr{A}}^{\prime}}(JU(x),J(b))$
($JU(x)\in U^{\prime}[\mathbf{EM}_{\mathrm{fg}}(T^{\prime})]$)
$\displaystyle\cong\hom_{\operatorname{\mathscr{A}}}(U(x),b).$ ($J$ full and
faithful)

Conversely, suppose item 2 in the statement holds. For all
$x^{\prime}\in\mathbf{EM}(T^{\prime})_{\mathrm{fg}}$,

$\displaystyle\hom_{\operatorname{\mathscr{A}}^{\prime}}(U^{\prime}(x),J(a))$
$\displaystyle\cong\hom_{\operatorname{\mathscr{A}}}(HU^{\prime}(x),a)$
($H\dashv J$)
$\displaystyle\cong\hom_{\operatorname{\mathscr{A}}}(HU^{\prime}(x),b)$
($HU^{\prime}(x)\in U[\mathbf{EM}_{\mathrm{fg}}(T)]$)
$\displaystyle\cong\hom_{\operatorname{\mathscr{A}}^{\prime}}(U^{\prime}(x),J(b))$
($H\dashv J$)

and so equation (3) holds. This concludes the proof. ∎

##  6\. Examples

###  6.1. Trees

If $(P,{\leq})$ is a poset, then $C\subseteq P$ is a _chain_ if it is linearly
ordered. A _forest_ is a poset $(P,\leq)$ such that, for all $u\in P$, the set

${\downarrow}u\coloneqq\\{v\in P\mid v\leq u\\}$

is a finite chain. The _covering relation_ $\prec$ associated with a partial
order $\leq$ is defined by $u\prec v$ if and only if $u<v$ and there is no $w$
such that $u<w<v$. The _roots_ of a forest are the minimal elements. A _tree_
is a forest with at most one root (note that a tree is either empty, or has a
unique root, the least element in the order). Morphisms of trees are maps
which preserve the root and the covering relation. The category of trees is
denoted by $\operatorname{\mathscr{T}}$. Monomorphisms and strong epimorphisms
in $\operatorname{\mathscr{T}}$ coincide, respectively, with the injective and
surjective tree morphisms.

It is well known that $\operatorname{\mathscr{T}}$ is a locally finitely
presentable category in which the finitely presentable objects, which coincide
with the finitely generated ones, are precisely the finite trees. Moreover, it
is not difficult to see that a tree $(P,\leq)$ has finite
$\operatorname{\mathscr{T}}_{\mathrm{fp}}$-type if, and only if, it is
_finitely branching_. That is, for every $u\in P$, the set $\\{v\in P\mid
u\prec v\\}$ is finite.

Thus, Theorem 5.12 entails at once the following result:

######  Theorem 6.1.

Let $P,Q$ be any two finitely branching trees. Then $P\cong Q$ if and only if,
for all finite trees $R$, the number of tree morphisms $R\to P$ is the same as
the number of tree morphisms $R\to Q$.

######  Remark 6.2.

In the last part of the proof of Theorem 5.10, we used the fact that

$\forall i\in I.\
\mathscr{M}(b_{i},a)\neq\emptyset\enspace\Longrightarrow\enspace\mathscr{M}(\operatornamewithlimits{colim}_{i\in
I}b_{i},a)\neq\emptyset$

where, using the notation of the aforementioned theorem, the objects $b_{i}$
sit in the category $\operatorname{\mathscr{C}}$ and $a$ is a
$\operatorname{\mathscr{C}}$-separable object of finite
$\operatorname{\mathscr{C}}$-type.

This can be regarded as a generalisation of König’s Lemma for trees, stating
that every finitely branching infinite tree contains an infinite simple path.
Just observe that a countably infinite simple path $P_{\omega}$ is a colimit
in $\operatorname{\mathscr{T}}$ of finite simple paths $P_{n}$ of (increasing)
length $n$. If $Q$ is an infinite tree, then for all $n$ there exists an
embedding $P_{n}\rightarrowtail Q$. If, in addition, $Q$ is finitely
branching, then it has finite $\operatorname{\mathscr{T}}_{\mathrm{fp}}$-type
(and is $\operatorname{\mathscr{T}}_{\mathrm{fp}}$-separable) and so there is
an embedding $P_{\omega}\rightarrowtail Q$.777In the specific case of trees,
embeddings could be replaced by arbitrary arrows. Just note that every
morphism in $\operatorname{\mathscr{T}}$ whose domain is linearly ordered is
automatically injective. In this sense, a version of König’s Lemma holds, in
particular, in every locally finitely presentable category.

###  6.2. Profinite algebras

In this section we focus on profinite universal algebras; a nice expository
paper on the subject is [6].

Let $\mathscr{V}$ be an arbitrary variety of universal algebras, regarded as a
category with morphisms the homomorphisms. The full subcategory
$\mathscr{V}_{\mathrm{fin}}$ of $\mathscr{V}$ defined by the finite algebras
is essentially small and has finite limits, which are computed in the category
of sets. The same holds for any full subcategory $\operatorname{\mathscr{C}}$
of $\mathscr{V}_{\mathrm{fin}}$ that is closed under subalgebras and finite
products.

Let us fix a full subcategory $\operatorname{\mathscr{C}}$ of
$\mathscr{V}_{\mathrm{fin}}$ closed under subalgebras and finite products. The
category $\operatorname{Pro}(\operatorname{\mathscr{C}})$ can be identified
with a full subcategory of the category $\mathscr{K}_{\mathscr{V}}$, whose
objects are the topological $\mathscr{V}$-algebras carrying a compact
Hausdorff topology and whose morphisms are the continuous
homomorphisms.888Under this identification, an algebra in
$\operatorname{\mathscr{C}}$ is regarded as a topological algebra with respect
to the discrete topology. Explicitly, a topological algebra
$A\in\mathscr{K}_{\mathscr{V}}$ belongs to
$\operatorname{Pro}(\operatorname{\mathscr{C}})$ if and only if, whenever
$f,g\colon B\to A$ are distinct morphisms in $\mathscr{K}_{\mathscr{V}}$,
there exists a morphism $h\colon A\to C$ with $C\in\operatorname{\mathscr{C}}$
such that $h\circ f\neq h\circ g$. We shall refer to the objects of
$\operatorname{Pro}(\operatorname{\mathscr{C}})$ as _pro-
$\operatorname{\mathscr{C}}$_ algebras. If
$\operatorname{\mathscr{C}}=\mathscr{V}_{\mathrm{fin}}$, these coincide with
the usual profinite $\mathscr{V}$-algebras.

The monomorphisms in $\mathscr{K}_{\mathscr{V}}$ are precisely the injective
maps, i.e. the maps that provide (topological and algebraic) isomorphisms with
the image. This holds in $\operatorname{Pro}(\operatorname{\mathscr{C}})$ as
well, because the latter is a reflective subcategory of
$\mathscr{K}_{\mathscr{V}}$. In particular, the subobjects in
$\operatorname{Pro}(\operatorname{\mathscr{C}})$ can be identified with the
closed subalgebras. For the previous assertions, cf. [6] and the references
therein. It follows that $\operatorname{\mathscr{C}}$ is closed under (strong)
subobjects in $\operatorname{Pro}(\operatorname{\mathscr{C}})$.

Finally, recall that a universal algebra $A$ is said to be _finitely
generated_ if there exists a finite subset $S\subseteq A$ such that the
inclusion-smallest subalgebra $\langle S\rangle$ of $A$ containing $S$ is $A$
itself. In the setting of topological algebras it is customary to relax the
previous condition and say that a topological algebra $A$ is _topologically
finitely generated_ if there exists a finite subset $S\subseteq A$ such that
$\langle S\rangle$ is dense in the topology of $A$. Now, if
$A\in\operatorname{Pro}(\operatorname{\mathscr{C}})$ is topologically finitely
generated and $C\in\operatorname{\mathscr{C}}$, the set
$\hom_{\operatorname{Pro}(\operatorname{\mathscr{C}})}(A,C)$ is finite. Just
observe that, if $S\subseteq A$ is a finite subset such that $\langle
S\rangle$ is dense in $A$, the obvious restriction function

$\hom_{\operatorname{Pro}(\operatorname{\mathscr{C}})}(A,C)\to C^{S}$

is injective because a continuous map into a Hausdorff space is completely
determined by its behaviour on any dense subset of its domain.

Hence, the following is an immediate consequence of Corollary 5.14:

######  Theorem 6.3.

Let $\mathscr{V}$ be a variety of universal algebras,
$\operatorname{\mathscr{C}}\subseteq\mathscr{V}_{\mathrm{fin}}$ a class of
finite algebras closed under subalgebras and finite products, and $A,B$ two
topologically finitely generated pro-$\operatorname{\mathscr{C}}$ algebras.
Then $A\cong B$ if and only if, for all (discrete) algebras
$C\in\operatorname{\mathscr{C}}$, the number of continuous homomorphisms $A\to
C$ is the same as the number of continuous homomorphisms $B\to C$.

The previous result applies, e.g., when $\operatorname{\mathscr{C}}$ is the
class of finite lattices, or finite Heyting algebras, or finite semigroups,
and provides a characterisation of the isomorphism relation for (topologically
finitely generated) profinite lattices, profinite Heyting algebras, and
profinite semigroups, respectively.

Next, we restrict our attention to topologically finitely generated profinite
groups, whose topological structure is determined by the algebraic one.

Instantiating Theorem 6.3 with $\operatorname{\mathscr{C}}$ the class of
finite groups, we obtain the following result: _Two topologically finitely
generated profinite groups $G,H$ are isomorphic (as topological groups) if and
only if, for all finite discrete groups $K$, the number of continuous group
homomorphisms $G\to K$ is the same as the number of continuous group
homomorphisms $H\to K$._999This fact was first conjectured by Mima
Stanojkovski (private e-mail communication).

In turn, a remarkable result of Nikolov and Segal [31, 32] states that the
topological structure of a topologically finitely generated profinite group is
completely determined by its algebraic structure. More precisely, the
subgroups of finite index of a topologically finitely generated profinite
group coincide with the open subgroups. (In the special case of
pro-$p$-groups, this was proved by Serre in the 1970s, cf. [40, Exercise 6 p.
32].) This implies that (i) any group homomorphism from a topologically
finitely generated profinite group to a finite discrete group is continuous,
and (ii) any two topologically finitely generated profinite groups are
isomorphic as topological groups if, and only if, they are isomorphic as
abstract groups. The homomorphism counting result in the previous paragraph
can then be restated as follows: _Two topologically finitely generated
profinite groups $G,H$ are isomorphic if and only if, for all finite groups
$K$, the number of group homomorphisms $G\to K$ is the same as the number of
group homomorphisms $H\to K$._

A similar result, whose statement we shall omit, holds for (topologically
finitely generated) Abelian profinite groups, also known as _proabelian
groups_ , by taking as $\operatorname{\mathscr{C}}$ the class of finite
Abelian groups.

For an example where $\operatorname{\mathscr{C}}$ is a proper subclass of
$\mathscr{V}_{\mathrm{fin}}$, let $\operatorname{\mathscr{C}}$ consist of the
finite $p$-groups. We deduce that: _Two topologically finitely generated pro-
$p$-groups $G,H$ are isomorphic if and only if, for all finite $p$-groups $K$,
the number of group homomorphisms $G\to K$ is the same as the number of group
homomorphisms $H\to K$._

A typical homomorphism counting result will count the number of morphisms
(into, or from a given object) in the monoid $\mathbb{N}$ of natural numbers.
Now, recall that the proof of Theorem 5.10 (and similarly, the proof of
Theorem 4.3 in the locally finite case) consists essentially of two steps.
First, using the Stirling kernel construction, we show that the functors
$\mathscr{M}(-,a)$ and $\mathscr{M}(-,b)$ are pointwise isomorphic whenever
the functors $\hom(-,a)$ and $\hom(-,b)$ are pointwise isomorphic. Second,
Numakura’s Lemma is invoked to show that $a\cong b$ if, for all $c$,

$\mathscr{M}(c,a)\neq\emptyset\enspace\Longleftrightarrow\enspace\mathscr{M}(c,b)\neq\emptyset.$

Dispensing with the first step, we obtain a (weaker) result whereby the
isomorphism type of an object is determined by counting the number of
embeddings (or, dually, quotients) in the two-element monoid
$(\\{0,1\\},\vee,0)$. We state a special case of this result, which
generalises a known fact in profinite group theory (cf. [37, Theorems 3.2.7
and 3.2.9]).

######  Proposition 6.4.

Let $\mathscr{V}$ be a variety of universal algebras,
$\operatorname{\mathscr{C}}\subseteq\mathscr{V}_{\mathrm{fin}}$ a class of
finite algebras closed under subalgebras and finite products, and $A,B$ two
topologically finitely generated pro-$\operatorname{\mathscr{C}}$ algebras.
Suppose that, for all (discrete) algebras $C\in\operatorname{\mathscr{C}}$,
there exists a quotient101010That is, a continuous surjective homomorphism.
$A\twoheadrightarrow C$ if and only if there exists a quotient
$B\twoheadrightarrow C$. Then $A\cong B$.

###  6.3. Finite-variable logics

In this section we assume familiarity with the basic notions of first-order
logic and finite model theory. We shall present an application of the results
in Section 5 to homomorphism counting in finite model theory; this is the
topic of the recent work [9]. Following [9], we apply the framework of _game
comonads_ in (finite) model theory introduced by Abramsky, Dawar _et al._ in
[1, 2].

Let us fix a finite relational signature $\sigma$ and a positive integer $k$.
We recall from [1] the _pebbling comonad_ $\mathbb{P}_{k}$ on the category
$\mathscr{R}(\sigma)$ of $\sigma$-structures, which models $k$-pebble games.

Set $\mathbf{k}\coloneqq\\{1,\dots,k\\}$. Given a $\sigma$-structure $A$, we
consider the set ${(\mathbf{k}\times A)^{+}}$ of _plays_ in $A$, i.e. all non-
empty finite sequences of elements of $\mathbf{k}\times A$. A pair
$(p,a)\in{\mathbf{k}\times A}$ is called a _move_. Intuitively, the move
$(p,a)$ corresponds to placing the pebble $p$ on the element $a$. Whenever
$[(p_{1},a_{1}),\dots,(p_{l},a_{l})]$ is a play, $p_{i}$ is called the _pebble
index_ of the move $(p_{i},a_{i})$. Define the map

$\varepsilon_{A}\colon(\mathbf{k}\times A)^{+}\to A,\ \
[(p_{1},a_{1}),\dots,(p_{l},a_{l})]\mapsto a_{l}$

sending a play to the element of $A$ in its last move. Let $\mathbb{P}_{k}(A)$
be the $\sigma$-structure with universe $(\mathbf{k}\times A)^{+}$ and such
that, for every $R\in\sigma$ of arity $j$, its interpretation
$R^{\mathbb{P}_{k}(A)}$ consists of the tuples of plays $(s_{1},\ldots,s_{j})$
such that:

  1. (i)

The $s_{i}$’s are pairwise comparable in the prefix order.

  2. (ii)

Whenever $s_{i}$ is a prefix of $s_{i^{\prime}}$, the pebble index of the last
move in $s_{i}$ does not appear in the suffix of $s_{i}$ in $s_{i^{\prime}}$.

  3. (iii)

${(\varepsilon_{A}(s_{1}),\dots,\varepsilon_{A}(s_{j}))\in R^{A}}$.

This assignment extends to a functor
$\mathscr{R}(\sigma)\to\mathscr{R}(\sigma)$ by setting, for all homomorphisms
of $\sigma$-structures $h\colon A\to B$,

$\mathbb{P}_{k}(h)\colon\mathbb{P}_{k}(A)\to\mathbb{P}_{k}(B),\ \
[(p_{1},a_{1}),\dots,(p_{l},a_{l})]\mapsto[(p_{1},h(a_{1})),\dots,(p_{l},h(a_{l}))].$

In fact, $\mathbb{P}_{k}$ is a comonad on $\mathscr{R}(\sigma)$ when equipped
with the counit $\varepsilon$ described above and the comultiplication
$\delta_{A}\colon\mathbb{P}_{k}(A)\to\mathbb{P}_{k}\mathbb{P}_{k}(A)$ given by

$[(p_{1},a_{1}),\dots,(p_{l},a_{l})]\mapsto[(p_{1},s_{1}),\ldots,(p_{l},s_{l})],$

where $s_{i}\coloneqq[(p_{1},a_{1}),\ldots,(p_{i},a_{i})]$ for
$i\in\\{1,\ldots,l\\}$. Moreover, it follows directly from [1, Proposition 22]
that a $\sigma$-structure $A$ admits a coalgebra structure for
$\mathbb{P}_{k}$ if, and only if, it has _tree-width_ less than $k$ (the
notion of tree-width for relational structures was introduced in [12] and
generalises the homonymous concept for graphs).

Denote by $\mathcal{L}$ (respectively,
$\mathcal{L}(\text{\small{$\overset{w.o.}{=}$}})$) the extension of first-
order logic (respectively, first-order logic _without equality_) obtained by
adding _counting quantifiers_ $\exists_{{\geq}i}$ for all natural numbers $i$.
The $k$-variable fragments of $\mathcal{L}$ and
$\mathcal{L}(\text{\small{$\overset{w.o.}{=}$}})$ are denoted by
$\mathcal{L}^{k}$ and $\mathcal{L}^{k}(\text{\small{$\overset{w.o.}{=}$}})$,
respectively. Further, consider the adjunction $U\dashv
F\colon\mathscr{R}(\sigma)\to\mathbf{EM}(\mathbb{P}_{k})$ associated with the
comonad $\mathbb{P}_{k}$. For any two finite $\sigma$-structures $A$ and $B$
we have

$F(A)\cong F(B)\enspace\Longleftrightarrow\enspace
A\equiv_{\mathcal{L}^{k}(\text{\scriptsize{$\overset{w.o.}{=}$}})}B,$

i.e. $F(A)\cong F(B)$ precisely when $A$ and $B$ satisfy the same sentences of
$\mathcal{L}^{k}(\text{\small{$\overset{w.o.}{=}$}})$. For the latter
assertion, cf. [1, Theorem 18] and [9, §VI].

It is well known that $\mathscr{R}(\sigma)$ is a locally finitely presentable
category, and every finitely presentable $\sigma$-structure is finite. Since
we assumed that the signature $\sigma$ is finite, the converse holds as well,
and so the finitely generated objects in $\mathscr{R}(\sigma)$ coincide with
the finitely presentable ones and are precisely the finite
$\sigma$-structures. See e.g. [5, pp. 200–201]. It follows easily from the
criterion in Lemma B.1 in the appendix that $\mathbb{P}_{k}$ is finitary, and
it can be verified that it satisfies the conditions in the definition of
comonad of finite rank (cf. also Remark B.4). As the forgetful functor
$U\colon\mathbf{EM}(\mathbb{P}_{k})\to\mathscr{R}(\sigma)$ preserves and
reflects finitely presentable objects by Lemma B.2, a coalgebra
$x\in\mathbf{EM}(\mathbb{P}_{k})$ is finitely presentable if and only if
$U(x)$ is a finite $\sigma$-structure.

Therefore, in view of Corollary 5.15 and Remark 5.16, the following statements
are equivalent for all finite $\sigma$-structures $A,B$:

  1. (1)

$A\equiv_{\mathcal{L}^{k}(\text{\scriptsize{$\overset{w.o.}{=}$}})}B$.

  2. (2)

For all finite $\sigma$-structures $C$ with tree-width less than $k$, the
number of homomorphisms $C\to A$ is the same as the number of homomorphisms
$C\to B$.

To characterise equivalence in the logic $\mathcal{L}^{k}$ _with equality_ ,
we proceed as follows. Let $\sigma^{\prime}$ be the relational signature
obtained by adding a binary relation symbol $I$ to $\sigma$. There is an
adjunction ${H\dashv
J\colon\mathscr{R}(\sigma)\to\mathscr{R}(\sigma^{\prime})}$, where:

  * •

$J$ sends a $\sigma$-structure $A$ to the $\sigma^{\prime}$-structure obtained
by interpreting $I$ as the identity relation on $A$;

  * •

$H$ sends a $\sigma^{\prime}$-structure $B$ to the quotient structure
$B^{-}/{\sim}$, where $B^{-}$ is the $\sigma$-reduct of $B$ and $\sim$ is the
equivalence relation generated by the interpretation of $I$ in $B$.

For a proof of this fact, see [9, Lemma 25].

Since the comonad $\mathbb{P}_{k}$ was defined for an arbitrary relational
signature $\sigma$, we have a corresponding comonad $\mathbb{P}_{k}^{\prime}$
on $\mathscr{R}(\sigma^{\prime})$ with associated adjunction $U^{\prime}\dashv
F^{\prime}$. It follows from [1, Theorem 18] that, for all finite
$\sigma$-structures $A,B$,

$F^{\prime}J(A)\cong F^{\prime}J(B)\enspace\Longleftrightarrow\enspace
A\equiv_{\mathcal{L}^{k}}B.$

Moreover, the adjunction $H\dashv J$ restricts to the full subcategories of
$\mathscr{R}(\sigma)$ and $\mathscr{R}(\sigma^{\prime})$ defined by the
structures with tree-width less than $k$ (this assertion is trivial for $J$;
for $H$, this follows directly from [9, Proposition 23]).

Thus, Corollary 5.17 and Remark 5.16 entail the following result, which was
first proved in [9, Theorem 21] for an arbitrary relational signature $\sigma$
(by means of an indirect argument) and generalises a result of Dvořák for
graphs [11]:

######  Theorem 6.5.

Let $\sigma$ be a finite relational signature and let $A,B$ be any two finite
$\sigma$-structures. Then $A\equiv_{\mathcal{L}^{k}}B$ if and only if, for all
finite $\sigma$-structures $C$ with tree-width less than $k$, the number of
homomorphisms $C\to A$ is the same as the number of homomorphisms $C\to B$.

##  Appendix A Proper Factorisation Systems

In this section we recall the notion of proper factorisation system in a
category $\operatorname{\mathscr{A}}$, and some of its main properties.

Given arrows $e$ and $m$ in $\operatorname{\mathscr{A}}$, we say that $e$ has
the _left lifting property_ with respect to $m$, or that $m$ has the _right
lifting property_ with respect to $e$, if for every commutative square as on
the left-hand side below

${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$$\scriptstyle{e}$$\scriptstyle{m}$
${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$$\scriptstyle{e}$$\scriptstyle{d}$$\scriptstyle{m}$

there exists a (not necessarily unique) _diagonal filler_ , i.e. an arrow $d$
such that the right-hand diagram above commutes. If this is the case, we write
$e{\,\pitchfork\,}m$. For any class $\mathscr{H}$ of morphisms in
$\operatorname{\mathscr{A}}$, let ${}^{\pitchfork}\mathscr{H}$ (respectively
$\mathscr{H}^{\pitchfork}$) be the class of morphisms having the left
(respectively right) lifting property with respect to every morphism in
$\mathscr{H}$.

######  Definition A.1.

A pair of classes of morphisms $(\mathscr{Q},\mathscr{M})$ in a category
$\operatorname{\mathscr{A}}$ is a _weak factorisation system_ provided it
satisfies the following conditions:

  1. (i)

Every arrow $f$ in $\operatorname{\mathscr{A}}$ decomposes as $f=m\circ e$
with $e\in\mathscr{Q}$ and $m\in\mathscr{M}$.

  2. (ii)

$\mathscr{Q}={}^{\pitchfork}\mathscr{M}$ and
$\mathscr{M}=\mathscr{Q}^{\pitchfork}$.

A _proper factorisation system_ is a weak factorisation system
$(\mathscr{Q},\mathscr{M})$ such that all arrows in $\mathscr{Q}$ are
epimorphisms and all arrows in $\mathscr{M}$ are monomorphisms.

We refer to $\mathscr{Q}$-morphisms and $\mathscr{M}$-morphisms, respectively,
as _quotients_ (denoted by $\twoheadrightarrow$) and _embeddings_ (denoted by
$\rightarrowtail$).

It is easy to see that any proper factorisation system is an _orthogonal_
factorisation system, meaning that the diagonal fillers are unique. In
particular, factorisations are unique up to (unique) isomorphism.

Furthermore, recall that a _strong epimorphism_ is an epimorphism that has the
left lifting property with respect to all monomorphisms, and a _strong
monomorphism_ is a monomorphism that has the right lifting property with
respect to all epimorphisms. Given any proper factorisation system
$(\mathscr{Q},\mathscr{M})$, the following inclusions are immediate:

$\displaystyle\\{\text{strong
monomorphisms}\\}\subseteq\mathscr{M}\subseteq\\{\text{monomorphisms}\\},$
$\displaystyle\\{\text{strong
epimorphisms}\\}\subseteq\mathscr{Q}\subseteq\\{\text{epimorphisms}\\}.$

Next, we state some well known properties of weak factorisation systems (cf.
[13] or [38]):

######  Lemma A.2.

Let $(\mathscr{Q},\mathscr{M})$ be a weak factorisation system in
$\operatorname{\mathscr{A}}$. The following statements hold:

  1. (a)

$\mathscr{Q}$ and $\mathscr{M}$ are closed under compositions.

  2. (b)

$\mathscr{Q}\cap\mathscr{M}=\\{\text{isomorphisms}\\}$.

  3. (c)

The pullback of an embedding along any morphism, if it exists, is again an
embedding.

  4. (d)

The pushout of a quotient along any morphism, if it exists, is again a
quotient.

Moreover, if $(\mathscr{Q},\mathscr{M})$ is proper, then the following hold:

  1. (e)

$g\circ f\in\mathscr{Q}$ implies $g\in\mathscr{Q}$.

  2. (f)

$g\circ f\in\mathscr{M}$ implies $f\in\mathscr{M}$.

Let $\operatorname{\mathscr{A}}$ be a category equipped with a proper
factorisation system $(\mathscr{Q},\mathscr{M})$. In the same way that one
usually defines the poset of subobjects of a given object
$a\in\operatorname{\mathscr{A}}$, we can define the poset of
$\mathscr{M}$-subobjects of $a$. Given embeddings $m\colon b\rightarrowtail a$
and $n\colon c\rightarrowtail a$, let us say that $m\trianglelefteq n$
provided there is a morphism $i\colon b\to c$ such that $m=n\circ i$ (note
that, if it exists, $i$ is necessarily an embedding). This yields a preorder
on the class of all embeddings with codomain $a$. The symmetrization $\sim$ of
$\trianglelefteq$ can be characterised as follows: $m\sim n$ if, and only if,
$m=n\circ i$ for some isomorphism $i\colon b\to c$.

Let $\mathscr{M}(a)$ be the class of $\sim$-equivalence classes of embeddings
with codomain $a$, equipped with the natural partial order $\leq$ induced by
$\trianglelefteq$. We systematically represent a $\sim$-equivalence class by
any of its representatives. As every embedding is a monomorphism, and we are
assuming that all categories under consideration are well-powered (cf.
Assumption 2.1), we see that $\mathscr{M}(a)$ is a set. We refer to
$\mathscr{M}(a)$ as the _poset of embeddings_ of $a$. Likewise, dualising the
construction outlined above, we consider the _poset of quotients_ of $a$,
denoted by $\mathscr{Q}(a)$. Hence, for any two (equivalence classes of)
quotients $f\colon a\twoheadrightarrow b$ and $g\colon a\twoheadrightarrow c$,
we have $f\leq g$ if and only if $f$ factors through $g$.

######  Remark A.3.

Let $(\mathscr{Q},\mathscr{M})$ be a proper factorisation system in
$\operatorname{\mathscr{A}}$. Recall from Section 3.2 that
$\operatorname{\mathscr{A}}$ is $\mathscr{Q}$-well-founded (respectively,
$\mathscr{M}$-well-founded) if, for all objects
$a\in\operatorname{\mathscr{A}}$, the poset $\mathscr{Q}(a)$ (respectively,
$\mathscr{M}(a)$) is well-founded.

Let $\mathscr{Q}^{\prime}$ be the class of morphisms in
$\operatorname{\mathscr{A}}^{\mathrm{op}}$ obtained by reversing the arrows in
$\mathscr{M}$, and $\mathscr{M}^{\prime}$ the class of morphisms in
$\operatorname{\mathscr{A}}^{\mathrm{op}}$ obtained by reversing the arrows in
$\mathscr{Q}$. Then $(\mathscr{Q}^{\prime},\mathscr{M}^{\prime})$ is a proper
factorisation system in $\operatorname{\mathscr{A}}^{\mathrm{op}}$, and
$\operatorname{\mathscr{A}}$ is $\mathscr{Q}$-well-founded if and only if
$\operatorname{\mathscr{A}}^{\mathrm{op}}$ is $\mathscr{M}^{\prime}$-well-
founded. Just observe that the posets $\mathscr{Q}(a)$ and
$\mathscr{M}^{\prime}(a)$ are isomorphic for all objects $a$ (because,
intuitively, the notion of ‘factoring through’ is self-dual).

######  Lemma A.4.

Let $\operatorname{\mathscr{A}}$ be a category equipped with a proper
factorisation system $(\mathscr{Q},\mathscr{M})$. The following statements
hold:

  1. (a)

Any commutative triangle in $\operatorname{\mathscr{A}}$ admits a commutative
subdivision as displayed below.

${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$

  2. (b)

If $\operatorname{\mathscr{A}}$ has the amalgamation property, then any span
of the form ${{\cdot}}$${{\cdot}}$${{\cdot}}$ can be completed to a
commutative square as follows:

${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$

In particular, any span of quotients in $\operatorname{\mathscr{A}}$ can be
completed to a commutative square of quotients.

###### Proof.

For item (a), consider morphisms $f_{1},f_{2},g$ in
$\operatorname{\mathscr{A}}$ such that ${g\circ f_{1}=f_{2}}$. Let
$(e_{1},m_{1})$ and $(e_{2},m_{2})$ be the $(\mathscr{Q},\mathscr{M})$
factorisations of $f_{1}$ and $f_{2}$, respectively. We obtain a commutative
diagram as follows.

${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$$\scriptstyle{f_{1}}$$\scriptstyle{f_{2}}$$\scriptstyle{e_{1}}$$\scriptstyle{e_{2}}$$\scriptstyle{m_{1}}$$\scriptstyle{m_{2}}$$\scriptstyle{g}$

Then the following square admits a diagonal filler,

${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$$\scriptstyle{e_{2}}$$\scriptstyle{e_{1}}$$\scriptstyle{m_{1}}$$\scriptstyle{g}$$\scriptstyle{m_{2}}$

which is a quotient by Lemma A.2(e). This settles the statement.

For item (b), suppose we have a span ${{\cdot}}$${{\cdot}}$${{\cdot}}$ in
$\operatorname{\mathscr{A}}$. As $\operatorname{\mathscr{A}}$ has the
amalgamation property, we can complete this span to a commutative square as on
the left-hand side below.

${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$

If we consider the $(\mathscr{Q},\mathscr{M})$ factorisation of the lower
horizontal morphism, then we obtain a diagonal filler as on the right-hand
side above. This yields the desired completion of the original span. For the
second part of the statement, note that in any commuting square of the form

${{\cdot}}$${{\cdot}}$${{\cdot}}$${{\cdot}}$

the right vertical morphism must be a quotient by Lemma A.2(a),(e). ∎

Let
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be a presheaf, and let $U\colon\int F\to\operatorname{\mathscr{A}}$ be the
natural forgetful functor defined on the category of elements of $F$. If
$\operatorname{\mathscr{A}}$ is equipped with a proper factorisation system
$(\mathscr{Q},\mathscr{M})$, then we can equip $\int F$ with a factorisation
system $(\mathscr{Q}^{\prime},\mathscr{M}^{\prime})$ by simply letting
$\mathscr{Q}^{\prime}$ be the class of morphisms $f$ in $\int F$ such that
$U(f)\in\mathscr{Q}$, and $\mathscr{M}^{\prime}$ the class of morphisms $g$ in
$\int F$ such that $U(g)\in\mathscr{M}$. It is not difficult to see that
$(\mathscr{Q}^{\prime},\mathscr{M}^{\prime})$ is a proper factorisation
system. In the proof of the next lemma, we will assume that $\int F$ is
equipped with this factorisation system.

######  Lemma A.5.

Let $\operatorname{\mathscr{A}}$ be a category equipped with a proper
factorisation system, and let
$F\colon\operatorname{\mathscr{A}}^{\mathrm{op}}\to\operatorname{\mathbf{Set}}$
be a polyadic set. For all spans

${b}$${{\cdot}}$${a}$$\scriptstyle{g}$$\scriptstyle{f}$

in $\operatorname{\mathscr{A}}$ and elements $x\in F(a)$ and $y\in F(b)$ such
that $F(f)(x)=F(g)(y)$, there exist a commutative square

${{\cdot}}$${a}$${b}$${c}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{g^{\prime}}$$\scriptstyle{f^{\prime}}$

in $\operatorname{\mathscr{A}}$ and $z\in F(c)$ such that $F(g^{\prime})(z)=x$
and $F(f^{\prime})(z)=y$. Moreover, if $g$ is a quotient, we can assume that
$g^{\prime}$ is also a quotient.

###### Proof.

This follows directly from Lemma A.4(b) by setting
$\operatorname{\mathscr{A}}\coloneqq\int F$. ∎

##  Appendix B Comonads of Finite Rank

Given a monad on a locally finitely presentable category, we may ask if the
associated category of Eilenberg-Moore algebras is locally finitely
presentable. The answer is positive, provided the monad is finitary (see e.g.
[5, p. 124]). The analogous question for _comonads_ requires more care and
leads to the notion of comonad of finite rank (Definition B.3 below). In this
section we shall collect some basic facts about comonads of finite rank; most
of the material presented here can be found in Diers’ monograph [10], albeit
in a more condensed form (detailed references are provided below).

Let $(T,\delta,\varepsilon)$ be a comonad on a category
$\operatorname{\mathscr{A}}$, with comultiplication $\delta$ and counit
$\varepsilon$. Recall that an _Eilenberg-Moore coalgebra_ for $T$ is a pair
$(a,g)$ where $a$ is an object of $\operatorname{\mathscr{A}}$ and $g\colon
a\to T(a)$ is a morphism in $\operatorname{\mathscr{A}}$ such that the
following diagrams commute.

${a}$${T(a)}$${T(a)}$${T^{2}(a)}$$\scriptstyle{g}$$\scriptstyle{g}$$\scriptstyle{\delta_{a}}$$\scriptstyle{T(g)}$
${a}$${T(a)}$${a}$$\scriptstyle{g}$$\scriptstyle{\mathrm{id}_{a}}$$\scriptstyle{\varepsilon_{a}}$

A morphism of coalgebras $(a,g)\to(b,h)$ is an arrow $f\colon a\to b$ in
$\operatorname{\mathscr{A}}$ satisfying $T(f)\circ g=h\circ f$. Eilenberg-
Moore coalgebras and their morphisms form a category, denoted by
$\mathbf{EM}(T)$. The forgetful functor
$U\colon\mathbf{EM}(T)\to\operatorname{\mathscr{A}}$, sending a coalgebra
morphism $(a,g)\to(b,h)$ to the corresponding arrow $a\to b$, has a right
adjoint $F\colon\operatorname{\mathscr{A}}\to\mathbf{EM}(T)$ which sends an
arrow $f\colon a\to b$ in $\operatorname{\mathscr{A}}$ to
$T(f)\colon(T(a),\delta_{a})\to(T(b),\delta_{b})$. We refer to $U\dashv F$ as
the adjunction canonically associated with $T$.

Recall that a functor is _finitary_ if it preserves directed colimits. By
extension, we say that a comonad is finitary if so is its underlying functor.

The next lemma, which provides sufficient conditions for a comonad to be
finitary, is an immediate consequence of a result of Adámek, Milius, Sousa and
Wissmann [4, Theorem 3.4]. Note that item (ii) below is a direct
generalisation of the ‘$\varepsilon$-$\delta$ characterisation’ of continuity
for Scott continuous maps between algebraic domains, see e.g. [14, Proposition
II-2.1] (we are grateful to Samson Abramsky for pointing this out to us).

######  Lemma B.1.

Let $\operatorname{\mathscr{A}}$ be a locally finitely presentable category in
which every finitely generated object is finitely presentable, and let $T$ be
a comonad on $\operatorname{\mathscr{A}}$ that preserves monomorphisms. The
following statements are equivalent:

  1. (i)

$T$ is finitary.

  2. (ii)

For all $a\in\operatorname{\mathscr{A}}$, every subobject $b\rightarrowtail
T(a)$ with $b$ finitely presentable factors through the $T$-image of a
finitely presentable subobject of $a$.

The following useful fact was proved by Diers in [10, p. 45], where some
details were omitted; for the sake of completeness, we offer a detailed proof.

######  Lemma B.2.

Let $T$ be a finitary comonad on a category $\operatorname{\mathscr{A}}$, with
canonically associated adjunction $U\dashv
F\colon\operatorname{\mathscr{A}}\to\mathbf{EM}(T)$. The following statements
hold:

  1. (a)

$F$ preserves directed colimits.

  2. (b)

$U$ preserves and reflects finitely presentable objects.

###### Proof.

For item (a), let $\\{c_{i}\mid i\in I\\}$ be an arbitrary directed diagram in
$\operatorname{\mathscr{A}}$. Since $T$ is finitary and $U$ preserves colimits
(as it is left adjoint),

$UF(\operatornamewithlimits{colim}_{i\in
I}a_{i})\cong\operatornamewithlimits{colim}_{i\in I}UF(a_{i})\cong
U(\operatornamewithlimits{colim}_{i\in I}F(a_{i})).$

That is, if $\varphi\colon\operatornamewithlimits{colim}_{i\in I}F(a_{i})\to
F(\operatornamewithlimits{colim}_{i\in I}a_{i})$ denotes the obvious mediating
morphism, then $U(\varphi)$ is an isomorphism. Using the fact that $U$
reflects isomorphisms (see e.g. [3, Proposition 20.12(5)] for a proof of the
dual fact), we deduce that $F(\operatornamewithlimits{colim}_{i\in
I}a_{i})\cong\operatornamewithlimits{colim}_{i\in I}F(a_{i})$.

For item (b), consider an arbitrary coalgebra $x=(b,h)\in\mathbf{EM}(T)$. If
$x$ is finitely presentable then, for any directed diagram $\\{a_{i}\mid i\in
I\\}$ in $\operatorname{\mathscr{A}}$,

$\displaystyle\hom_{\operatorname{\mathscr{A}}}(U(x),\operatornamewithlimits{colim}_{i\in
I}a_{i})$
$\displaystyle\cong\hom_{\mathbf{EM}(T)}(x,F(\operatornamewithlimits{colim}_{i\in
I}a_{i}))$
$\displaystyle\cong\hom_{\mathbf{EM}(T)}(x,\operatornamewithlimits{colim}_{i\in
I}F(a_{i}))$ by (a) $\displaystyle\cong\operatornamewithlimits{colim}_{i\in
I}\hom_{\mathbf{EM}(T)}(x,F(a_{i}))$
$\displaystyle\cong\operatornamewithlimits{colim}_{i\in
I}\hom_{\operatorname{\mathscr{A}}}(U(x),a_{i}).$

Thus, $U$ preserves finitely presentable objects.

To see that $U$ reflects finitely presentable objects, assume that $b=U(x)$ is
finitely presentable. Let $\\{(a_{i},g_{i})\mid i\in I\\}$ be a directed
diagram in $\mathbf{EM}(T)$ and $\alpha_{i}\colon(a_{i},g_{i})\to(a,g)$ a
colimit cocone. We claim that the function

$\operatornamewithlimits{colim}_{i\in
I}\hom_{\mathbf{EM}(T)}((b,h),(a_{i},g_{i}))\ \longrightarrow\
\hom_{\mathbf{EM}(T)}((b,h),(a,g))$ (4)

induced by the cocone

$\alpha_{i}\circ-\colon\hom_{\mathbf{EM}(T)}((b,h),(a_{i},g_{i}))\
\longrightarrow\ \hom_{\mathbf{EM}(T)}((b,h),(a,g))$

is bijective, thus showing that $x=(b,h)$ is finitely presentable.

Suppose that $f_{i}\colon(b,h)\to(a_{i},g_{i})$ and
$f_{j}\colon(b,h)\to(a_{j},g_{j})$ are morphisms in $\mathbf{EM}(T)$ such that
$\alpha_{i}\circ f_{i}=\alpha_{j}\circ f_{j}$. As the diagram $I$ is directed,
there are transition morphisms
$\varphi_{ik}\colon(a_{i},g_{i})\to(a_{k},g_{k})$ and
$\varphi_{jk}\colon(a_{j},g_{j})\to(a_{k},g_{k})$ such that

$\alpha_{k}\circ\varphi_{ik}=\alpha_{i}\ \text{ and }\
\alpha_{k}\circ\varphi_{jk}=\alpha_{j}.$

Hence $\alpha_{k}\circ\varphi_{ik}\circ f_{i}=\alpha_{k}\circ\varphi_{jk}\circ
f_{j}$. By the definition of finitely presentable object, there exists a
transition morphism $\varphi_{kk^{\prime}}$ such that
$\varphi_{ik^{\prime}}\circ f_{i}=\varphi_{jk^{\prime}}\circ f_{j}$. That is,
$f_{i}=f_{j}$ in $\operatornamewithlimits{colim}_{i\in
I}\hom_{\mathbf{EM}(T)}((b,h),(a_{i},g_{i}))$. Therefore, the map in (4) is
injective.

For surjectivity, consider an arbitrary morphism $f\colon(b,h)\to(a,g)$ in
$\mathbf{EM}(T)$. Because $U$ preserves colimits, $U(f)$ belongs to

$\hom_{\operatorname{\mathscr{A}}}(b,a)\cong\hom_{\operatorname{\mathscr{A}}}(b,\operatornamewithlimits{colim}_{i\in
I}a_{i})\cong\operatornamewithlimits{colim}_{i\in
I}\hom_{\operatorname{\mathscr{A}}}(b,a_{i}),$

so there exist $i\in I$ and $f_{i}\colon b\to a_{i}$ such that
$U(f)=U(\alpha_{i})\circ f_{i}$.

######  Claim.

$TU(\alpha_{i})\circ g_{i}\circ f_{i}=TU(\alpha_{i})\circ T(f_{i})\circ h$.

###### Proof of Claim.

The commutativity of the diagrams

${b}$${a_{i}}$${T(a_{i})}$${a}$${T(a)}$$\scriptstyle{f_{i}}$$\scriptstyle{U(f)}$$\scriptstyle{U(\alpha_{i})}$$\scriptstyle{g_{i}}$$\scriptstyle{TU(\alpha_{i})}$$\scriptstyle{g}$
${b}$${T(b)}$${a}$${T(a)}$$\scriptstyle{h}$$\scriptstyle{U(f)}$$\scriptstyle{TU(f)}$$\scriptstyle{g}$

entails that $TU(\alpha_{i})\circ g_{i}\circ f_{i}=TU(f)\circ h$. Since
$U(f)=U(\alpha_{i})\circ f_{i}$, we obtain

$TU(\alpha_{i})\circ g_{i}\circ f_{i}=T(U(\alpha_{i})\circ f_{i})\circ
h=TU(\alpha_{i})\circ T(f_{i})\circ h.\qed$

As $T$ preserves directed colimits, $T(a)$ is the colimit of the cocone given
by the morphisms $TU(\alpha_{i})\colon T(a_{i})\to T(a)$. By the Claim and the
definition of finitely presentable object, there is a transition morphism
$U(\varphi_{ij})\colon a_{i}\to a_{j}$ satisfying $TU(\varphi_{ij})\circ
g_{i}\circ f_{i}=TU(\varphi_{ij})\circ T(f_{i})\circ h$. Because
$TU(\varphi_{ij})\circ g_{i}=g_{j}\circ U(\varphi_{ij})$, we obtain

$g_{j}\circ U(\varphi_{ij})\circ f_{i}=T(U(\varphi_{ij})\circ f_{i})\circ h,$

showing that $U(\varphi_{ij})\circ f_{i}\colon(b,h)\to(a_{j},g_{j})$ is a
morphism in $\mathbf{EM}(T)$. Furthermore, note that the following diagram
commutes

${b}$${a}$${a_{j}}$$\scriptstyle{U(\varphi_{ij})\circ
f_{i}}$$\scriptstyle{U(f)}$$\scriptstyle{U(\alpha_{j})}$

and so the function in (4) is surjective. ∎

######  Definition B.3.

Let $T$ be a comonad on a category $\operatorname{\mathscr{A}}$, with
forgetful functor $U\colon\mathbf{EM}(T)\to\operatorname{\mathscr{A}}$. We say
that $T$ is of _finite rank_ provided that the following conditions are
satisfied:

  1. (i)

$T$ is finitary.

  2. (ii)

Every morphism $f\colon a\to U(x)$ in $\operatorname{\mathscr{A}}$, with $a$
finitely presentable, admits a factorisation

${a}$${U(y)}$${U(x)}$$\scriptstyle{f}$$\scriptstyle{\beta}$$\scriptstyle{U(\gamma)}$

where $U(y)$ is finitely presentable.

  3. (iii)

The factorisation in (ii) is essentially unique, i.e., if
$\beta^{\prime}\colon a\to U(y)$ satisfies $U(\gamma)\circ\beta^{\prime}=f$,
then there exist $y^{\prime}\in\mathbf{EM}(T)$ with $U(y^{\prime})$ finitely
presentable and morphisms

${y}$${y^{\prime}}$${x}$$\scriptstyle{\lambda}$$\scriptstyle{\gamma^{\prime}}$

in $\mathbf{EM}(T)$ such that
$U(\lambda)\circ\beta=U(\lambda)\circ\beta^{\prime}$ and
$\gamma=\gamma^{\prime}\circ\lambda$.

######  Remark B.4.

Note that, if the morphism $U(\gamma)$ in item (ii) is a monomorphism, then
item (iii) is automatically satisfied.

Comonads of finite rank were introduced by Diers in [10, Definition 1.12.0],
where item (iii) in Definition B.3 was omitted. This condition of essential
uniqueness is needed to prove Theorem B.5 below, which appears as Proposition
1.12.1 in _op. cit_. To remedy this omission, we offer a complete proof of the
following result:

######  Theorem B.5.

Let $T$ be a comonad on a locally finitely presentable category
$\operatorname{\mathscr{A}}$. If $T$ is of finite rank then the Eilenberg-
Moore category $\mathbf{EM}(T)$ is locally finitely presentable and the
forgetful functor $U\colon\mathbf{EM}(T)\to\operatorname{\mathscr{A}}$
preserves and reflects finitely presentable objects.

###### Proof.

Note that $\mathbf{EM}(T)$ is cocomplete because $\operatorname{\mathscr{A}}$
is cocomplete and $U$ creates colimits (cf. [3, Proposition 20.12(10)] for a
proof of the dual fact). Further, $U$ preserves and reflects finitely
presentable objects by Lemma B.2(b). Since in $\operatorname{\mathscr{A}}$
there is, up to isomorphism, only a set of finitely presentable objects, the
same holds in $\mathbf{EM}(T)$. It remains to prove that every object of
$\mathbf{EM}(T)$ is a directed colimit of finitely presentable objects.

We will show that each $(a,g)\in\mathbf{EM}(T)$ is the colimit of the
canonical (directed) diagram given by the forgetful functor

$D\colon\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)\to\mathbf{EM}(T),$

where $\mathbf{EM}(T)_{\mathrm{fp}}$ is the full subcategory of
$\mathbf{EM}(T)$ defined by the finitely presentable objects. Because $U$
reflects colimits, it is enough to show that $U(a,g)$ is the colimit of the
diagram $U\circ
D\colon\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)\to\operatorname{\mathscr{A}}$.
Further, since $U$ preserves finitely presentable objects, $U\circ D$ factors
as

${\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)}$${\operatorname{\mathscr{A}}_{\mathrm{fp}}{\downarrow}U(a,g)}$${\operatorname{\mathscr{A}}}$$\scriptstyle{U\circ
D}$$\scriptstyle{J}$$\scriptstyle{D^{\prime}}$

where $D^{\prime}$ is the canonical diagram associated with $U(a,g)$ and $J$
is the functor sending a morphism $(b_{1},h_{1})\to(b_{2},h_{2})$ in
$\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)$ to its image under $U$.
Because the colimit of $D^{\prime}$ is $U(a,g)$, it suffices to show that the
functor $J$ is cofinal. We prove that the following two properties hold, which
in turn imply that $J$ is cofinal (cf. [7, Proposition 2.11.2]):

  * •

For all $c\in\operatorname{\mathscr{A}}_{\mathrm{fp}}{\downarrow}U(a,g)$ there
is $c\to J(d)$ with $d\in\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)$.

  * •

For any two morphisms $\beta_{1}\colon c\to J(d_{1})$ and $\beta_{2}\colon
c\to J(d_{2})$ with
$c\in\operatorname{\mathscr{A}}_{\mathrm{fp}}{\downarrow}U(a,g)$ and
$d_{1},d_{2}\in\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)$, there are
$d\in\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)$ and morphisms
$\varphi_{1}\colon d_{1}\to d$, $\varphi_{2}\colon d_{2}\to d$ in
$\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)$ satisfying
$J(\varphi_{1})\circ\beta_{1}=J(\varphi_{2})\circ\beta_{2}$.

The first property is precisely item (ii) in the definition of a comonad of
finite rank. For the second one, consider any two objects
$\gamma_{1}\colon(b_{1},h_{1})\to(a,g)$ and
$\gamma_{2}\colon(b_{2},h_{2})\to(a,g)$ of
$\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)$, an object $\alpha\colon c\to
U(a,g)$ of $\operatorname{\mathscr{A}}_{\mathrm{fp}}{\downarrow}U(a,g)$, and
arrows $\beta_{1}\colon c\to U(b_{1},h_{1})$ and $\beta_{2}\colon c\to
U(b_{2},h_{2})$ such that

$U(\gamma_{1})\circ\beta_{1}=\alpha=U(\gamma_{2})\circ\beta_{2}.$

Since $D$ is directed, there exist an object $\gamma\colon(b,h)\to(a,g)$ in
$\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)$ and morphisms
$\psi_{1}\colon(b_{1},h_{1})\to(b,h)$ and
$\psi_{2}\colon(b_{2},h_{2})\to(b,h)$ in $\mathbf{EM}(T)$ such that
$\gamma\circ\psi_{1}=\gamma_{1}$ and $\gamma\circ\psi_{2}=\gamma_{2}$. It
follows that

$U(\gamma)\circ
U(\psi_{1})\circ\beta_{1}=U(\gamma_{1})\circ\beta_{1}=U(\gamma_{2})\circ\beta_{2}=U(\gamma)\circ
U(\psi_{2})\circ\beta_{2}.$

By item (iii) in the definition of a comonad of finite rank, and the fact that
$U$ reflects finitely presentable objects, there exist
$\gamma^{\prime}\colon(b^{\prime},h^{\prime})\to(a,g)$ in
$\mathbf{EM}(T)_{\mathrm{fp}}{\downarrow}(a,g)$ and
$\lambda\in\hom_{\mathbf{EM}(T)}((b,h),(b^{\prime},h^{\prime}))$ satisfying
$\gamma=\gamma^{\prime}\circ\lambda$ and

$U(\lambda)\circ U(\psi_{1})\circ\beta_{1}=U(\lambda)\circ
U(\psi_{2})\circ\beta_{2}.$

Therefore, the morphisms $\varphi_{1}\coloneqq\lambda\circ\psi_{1}$ and
$\varphi_{2}\coloneqq\lambda\circ\psi_{2}$ satisfy
$J(\varphi_{1})\circ\beta_{1}=J(\varphi_{2})\circ\beta_{2}$ as desired. ∎

######  Corollary B.6.

Let $T$ be a comonad of finite rank on a locally finitely presentable category
$\operatorname{\mathscr{A}}$. If every finitely generated object in
$\operatorname{\mathscr{A}}$ is finitely presentable, then the same holds in
$\mathbf{EM}(T)$.

###### Proof.

Suppose that every finitely generated object in $\operatorname{\mathscr{A}}$
is finitely presentable, and let $x$ be an arbitrary finitely generated object
of $\mathbf{EM}(T)$. By Theorem B.5, the category $\mathbf{EM}(T)$ is locally
finitely presentable and the forgetful functor
$U\colon\mathbf{EM}(T)\to\operatorname{\mathscr{A}}$ preserves and reflects
finitely presentable objects. Thus there is a strong epimorphism $f\colon
y\twoheadrightarrow x$ in $\mathbf{EM}(T)$ with $y$ finitely presentable. As
left adjoint functors preserve strong epimorphisms (see e.g. [7, Proposition
4.3.9]), $U(f)$ is a strong epimorphism in $\operatorname{\mathscr{A}}$. Since
$U$ preserves finitely presentable objects, it follows that $U(x)$ is finitely
generated in $\operatorname{\mathscr{A}}$ and thus finitely presentable. Using
the fact that $U$ reflects finitely presentable objects, we see that $x$ is
finitely presentable. ∎

### Acknowledgements

We are grateful to Samson Abramsky and Tomáš Jakl for several useful comments
on a preliminary version of this paper that helped us to improve the
presentation of our results.

## References

  * [1] S. Abramsky, A. Dawar, and P. Wang, _The pebbling comonad in finite model theory_ , Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, 2017, pp. 1–12.
  * [2] S. Abramsky and N. Shah, _Relating Structure and Power: Comonadic semantics for computational resources_ , Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, CSL, 2018, pp. 2:1–2:17.
  * [3] J. Adámek, H. Herrlich, and G. E. Strecker, _Abstract and concrete categories_ , John Wiley & Sons, Inc., New York, 1990.
  * [4] J. Adámek, S. Milius, L. Sousa, and T. Wissmann, _On finitary functors_ , Theory Appl. Categ. 34 (2019), Paper No. 35, 1134–1164.
  * [5] J. Adámek and J. Rosický, _Locally presentable and accessible categories_ , London Mathematical Society Lecture Note Series, vol. 189, Cambridge University Press, Cambridge, 1994.
  * [6] B. Banaschewski, _On profinite universal algebras_ , General topology and its relations to modern analysis and algebra, III (Proc. Third Prague Topological Sympos., 1971), 1972, pp. 51–62.
  * [7] F. Borceux, _Handbook of categorical algebra. 1_ , Encyclopedia of Mathematics and its Applications, vol. 50, Cambridge University Press, Cambridge, 1994.
  * [8] A. H. Clifford and G. B. Preston, _The algebraic theory of semigroups. Vol. II_ , Mathematical Surveys, No. 7, American Mathematical Society, Providence, R.I., 1967.
  * [9] A. Dawar, T. Jakl, and L. Reggio, _Lovász-type theorems and game comonads_ , Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, 2021.
  * [10] Y. Diers, _Categories of Boolean sheaves of simple algebras_ , Lecture Notes in Mathematics, vol. 1187, Springer-Verlag, Berlin, 1986.
  * [11] Z. Dvořák, _On recognizing graphs by numbers of homomorphisms_ , Journal of Graph Theory 64 (2010), no. 4, 330–342.
  * [12] T. Feder and M. Y. Vardi, _The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory_ , SIAM J. Comput. 28 (1999), no. 1, 57–104.
  * [13] P. J. Freyd and G. M. Kelly, _Categories of continuous functors, I_ , Journal of Pure and Applied Algebra 2 (1972), no. 3, 169–191.
  * [14] G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott, _Continuous lattices and domains_ , Encyclopedia of Mathematics and its Applications, vol. 93, Cambridge University Press, Cambridge, 2003.
  * [15] C. D. Godsil, _Algebraic combinatorics_ , Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993.
  * [16] M. Grohe, _Counting bounded tree depth homomorphisms_ , Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020, pp. 507–520.
  * [17] J. G. Hocking and G. S. Young, _Topology_ , second ed., Dover Publications, Inc., New York, 1988.
  * [18] J. M. Howie, _Fundamentals of semigroup theory_ , London Mathematical Society Monographs. New Series, vol. 12, The Clarendon Press, Oxford University Press, New York, 1995.
  * [19] J. Isbell, _Some inequalities in hom sets_ , Journal of Pure and Applied Algebra 76 (1991), no. 1, 87–110.
  * [20] P. T. Johnstone, _Stone spaces_ , Cambridge Studies in Advanced Mathematics, vol. 3, Cambridge University Press, 1986, Reprint of the 1982 edition.
  * [21] A. Joyal, _Polyadic spaces and elementary theories_ , Notices of the AMS 18 (1971), no. 3, 563, Preliminary report.
  * [22] A. Joyal, _Une théorie combinatoire des séries formelles_ , Adv. in Math. 42 (1981), no. 1, 1–82.