Department of Mathematics and Department of Information and Computing
Sciences, Utrecht University, NetherlandsDepartment of Mathematics, University
of Pennsylvania, United States Paige Randall North and Maximilien Péroux
[500]Theory of computation Categorical semantics [500]Theory of computation
Algebraic semantics [500]Theory of computation Type structures X

# Coinductive control of inductive data types

Paige Randall North  Maximilien Péroux

###### Abstract

We combine the theory of inductive data types with the theory of universal
measurings. By doing so, we find that many categories of algebras of
endofunctors are actually enriched in the corresponding category of coalgebras
of the same endofunctor. The enrichment captures all possible partial algebra
homomorphisms, defined by measuring coalgebras. Thus this enriched category
carries more information than the usual category of algebras which captures
only total algebra homomorphisms. We specify new algebras besides the initial
one using a generalization of the notion of initial algebra.

###### keywords:

Inductive types, enriched category theory, algebraic data types, algebra,
coalgebra

##  1 Introduction

In both the tradition of functional programming and categorical logic, one
takes the perspective that most data types should be obtained as initial
algebras of certain endofunctors (to use categorical language). For instance,
the natural numbers are obtained as the initial algebra of the endofunctor
$X\mapsto X+1$, assuming that the category in question (often the category of
sets) has a terminal object $1$ and a coproduct $+$. Much theory has been
developed around this approach, which could be said to culminate in the notion
of W-types [5].

In another tradition, for $k$ a field, it has been long understood (going back
at least to Wraith, according to [3], and Sweedler [8]) that the category of
$k$-algebras is naturally enriched over the category of $k$-coalgebras, a fact
which has admitted generalization to several other settings (e.g. [3, 9, 6]).
Here, we generalize to the setting of an endofunctor on a category, and in
particular those that we consider in the theory of W-types.

This work is thus the beginning of a development of an analogue of the theory
of W-types – not based on the notion of initial objects in a _category_ of
algebras, but rather on generalized notions of initial objects in a _coalgebra
enriched category_ of algebras. Our main result (Theorem 3.17) states that the
categories of algebras of endofunctors considered in the theory of W-types are
often enriched in their corresponding categories of coalgebras. The hom-
coalgebras of our enriched category carry more information than the hom-sets
in the unenriched category that is usually considered in the theory of
W-types. We are then able to generalize the notion of _initial algebra_ ,
taking inspiration from the theory of enriched limits, which is more
expressive, and thus we are able to specify more objects than the usual notion
of initial algebra. Because of our passage to the enriched setting, we have
more precise control than in the unenriched setting, and we are able to
specify more data types than just those which are captured by the theory of
W-types. This general theory is presented in Section 3.

But first, in Section 2, we begin our paper with an enlightening example which
serves as an illustration of the relevance of our enriched theory and as a
motivation for the more general setting. Therein, we provide explicit
calculations for the case of algebras over the endofunctor $X\mapsto X+1$ on
${\mathsf{Set}}$.

##  2 Illustrative example: $\mathsf{id}+1$

In this section, we illustrate our results in the context of one example: the
endofunctor that sends $X\mapsto X+1$ (the coproduct of $X$ and a terminal set
$1$) in ${\mathsf{Set}}$, the category of sets. The initial algebra of this
endofunctor is $\mathbb{N}$, the natural numbers, and thus this endofunctor is
one of the most basic and important examples in the theory of W-types.

This section is one very long worked example of our general, categorical
theory which follows in Section 3.

We first review the classical story in Section 2.1, and afterwards our goal is
to explain how the category of algebras is naturally enriched in the category
of coalgebras of this functor and how we can use this extra structure to
generalize the notion of _initial algebra_ to capture more algebras than just
$\mathbb{N}$. So, in Section 2.2 we explore by hand a notion of partial
homomorphism between algebras that will be captured more formally later in the
enrichment. Next, in Section 2.3, we explore the structure that this
enrichment gives us. In Section 2.4, we introduce a computational tool and
compute explicitly some of the hom-objects of our enrichment. Finally, in
Section 2.5, we use this extra structure to generalize the notion of initial
object, and we describe some of the algebras that can be specified in this
way.

###  2.1 Preliminaries

Here, we review the the established theory regarding algebras and coalgebras
of $\mathsf{id}+1$ that we will use. See, for instance, [7, Ch. 3] for
details.

We let ${\mathsf{Alg}}$ denote the category of algebras of $\mathsf{id}$ \+ 1,
and we let ${\mathsf{CoAlg}}$ denote the category of coalgebras of
$\mathsf{id}$ \+ 1. Recall that an algebra is a pair $(A,\alpha)$ of a set $A$
together with a function $\alpha:A+1\to A$ (equivalently, a _successor_
endofunction $\alpha|_{A}:A\to A$ and a _zero_ $\alpha|_{1}:1\to A$), and a
coalgebra is a pair $(C,\chi)$ of a set $C$ together with a function
$\chi:C\to C+1$, i.e., a partial endofunction. The initial object of
${\mathsf{Alg}}$ is $(\mathbb{N},\alpha_{\mathbb{N}})$, where $\mathbb{N}$ is
the usual natural numbers, $\alpha_{\mathbb{N}}|_{\mathbb{N}}$ is the usual
successor function $x\mapsto x+1$ and $\alpha_{\mathbb{N}}|_{1}$ picks out
$0\in\mathbb{N}$. The terminal object of ${\mathsf{CoAlg}}$ is
$({\mathbb{N}^{\infty}},\chi_{\mathbb{N}^{\infty}})$ where
${\mathbb{N}^{\infty}}$ is the extended natural numbers
$\mathbb{N}+\\{\infty\\}$, and the map
$\chi_{\mathbb{N}^{\infty}}:{\mathbb{N}^{\infty}}\to{\mathbb{N}^{\infty}}+1$
takes $0\in{\mathbb{N}^{\infty}}$ to the element $t\in 1$ and all other
$x\in{\mathbb{N}^{\infty}}$ to $x-1\in{\mathbb{N}^{\infty}}$.

Note that because $\mathbb{N}$ is initial in ${\mathsf{Alg}}$, any algebra
$(A,\alpha_{A})$ gets a function $!_{A}:\mathbb{N}\to A$, and thus it will be
useful write $n_{A}$ for $!_{A}(n)$. That is, $0_{A}$ is the zero of $A$,
$1_{A}$ is the successor of $0_{A}$, etc. For $a\in A$, we will often also
write $a+1$ as shorthand for $\alpha_{A}(a)$ (especially when the algebra
structure morphism, here $\alpha_{A}$, does not have an explicit name).

Dually, because ${\mathbb{N}^{\infty}}$ is terminal in ${\mathsf{CoAlg}}$,
there is a function $\llbracket{-}\rrbracket:C\to{\mathbb{N}^{\infty}}$ for
any coalgebra $(C,\chi_{A})$, and we will say that the _index_ of a $c\in C$
is $\llbracket{c}\rrbracket$. Then the elements of $C$ that have index $0$ are
those $c$ such that $\chi_{C}(c)=t$, those that have index $1$ are all those
other $c$ such that $\chi_{C}^{2}(c)=t$, etc. For $c\in C$ where
$\llbracket{c}\rrbracket>0$, we will also often write $c-1$ to denote
$\chi_{C}(c)$ (especially when the coalgebra structure morphism does not have
an explicit name).

######  Notation .

Besides $\mathbb{N}$, we often consider algebras of the form
${\mathbb{n}}:=(\\{0,1,...,n\\},\alpha_{\mathbb{n}})$ for any
$n\in\mathbb{N}$. Here, $\alpha_{\mathbb{n}}$ is the algebra structure that
$\\{0,1,...,n\\}$ inherits as the quotient of $\mathbb{N}$ in ${\mathsf{Set}}$
that identifies all $m\geq n$. In fact, these are quotient algebras of
$\mathbb{N}$, in the sense that the algebra homomorphism
$\mathbb{N}\to{\mathbb{n}}$ is an epimorphism (see Example A.5 and preceding
Lemma A.3 in the appendix).

Dually, besides ${\mathbb{N}^{\infty}}$, we will also consider subcoalgebras
of ${\mathbb{N}^{\infty}}$, the _subterminal coalgebras_ :
${\mathbb{n}^{\circ}}$ with underlying subset $\\{0,1,...,n\\}$ of
${\mathbb{N}^{\infty}}$, $\mathbb{N}^{-}$ with underlying subset $\mathbb{N}$,
and $\mathbb{I}$ with underlying subset $\\{\infty\\}$. These all inherit
coalgebra structures from ${\mathbb{N}^{\infty}}$ (see Example A.10 and the
preceding Lemma A.8 in the appendix).

###  2.2 Partial homomorphisms

Consider algebras $A$ and $B$. We are, first of all, most interested in
algebra homomorphisms $f:A\rightarrow B$ (which we might call _total_ algebra
homomorphisms to distinguish them from the notion of _partial_ algebra
homomorphisms which we are about to introduce). This means that we have
$(\mathsf{H1})$ $f(0_{A})=0_{B}$ and $(\mathsf{H2})$ $f(a+1)=f(a)+1$ for all
$a\in A$. If $A$ is $\mathbb{N}$, we know that there is a total algebra
homomorphism $\mathbb{N}\to B$, and we can use $(\mathsf{H1})$ and
$(\mathsf{H2})$ to inductively construct this homomorphism.

But depending on the nature of $A$ and $B$, it might happen that we can only
guarantee $(\mathsf{H1})$ and $(\mathsf{H2})$ hold for some, but not all,
$a\in A$, and thus an attempt to construct a total algebra homomorphism $A\to
B$ inductively might fail at some point. Perhaps $A$ is ${\mathbb{n}}$ and $B$
is $\mathbb{N}$. We can try to construct a total homomorphism, so we set
$f(0_{\mathbb{n}}):=0_{\mathbb{N}}$ following $(\mathsf{H1})$,
$f(1_{\mathbb{n}}):=1_{\mathbb{N}}$ following $(\mathsf{H2})$, etc. This works
until we get to $n_{\mathbb{n}}$. Since $n_{\mathbb{n}}$ is the successor of
both ${(n-1)}_{\mathbb{n}}$ and ${n}_{\mathbb{n}}$, $(\mathsf{H2})$ tells us
to send $n_{\mathbb{n}}$ both to $n_{\mathbb{N}}$ and $(n+1)_{\mathbb{N}}$. We
might say that induction worked only up to the $n$th step, or that we can
define a _$n$ -partial homomorphism_. We formalize this idea in the following
way, in which we inductively construct partial homomorphisms in an attempt to
approximate a total homomorphism.

######  Construction  (Partial induction).

We seek to inductively approximate a homomorphism $A\rightarrow B$ when the
morphism $!_{A}:\mathbb{N}\to A$ is surjective. (We will drop the assumption
that $!_{A}$ is surjective in Definition 2.1.) We define a sequence of
functions $f_{c}:A\to B$ as follows.

_Initial step (P1)_

Define $f_{0}\colon A\rightarrow B$ by $f_{0}(a):=0_{B}$ for all $a\in A$.

_Inductive step_

Define $f_{c+1}\colon A\rightarrow B$ by:

_(P2)_

$f_{c+1}(0_{A}):=0_{B}$;

_(P3)_

$f_{c+1}(a+1):=f_{c}(a)+1$.

We stop when $f_{c+1}$ is not well-defined.

If $f_{c}$ is defined for all $c\in\mathbb{N}$, then there is a total
homomorphism $f_{\infty}:A\to B$ (the ‘diagonal’ $f_{\infty}(x):=f_{x}(x)$).
Otherwise, we will have defined $f_{c}$ only for all $c\in\\{0,...,n\\}$, and
in this case we will say that we have defined an _$n$ -partial homomorphism_.
We then also sometimes call a total homomorphism $f:A\to B$ an _$\infty$
-partial homomorphism_.

Notice that in the term “$n$-partial homomorphism” in the above Section 2.2,
$n$ takes values in ${\mathbb{N}^{\infty}}$, the terminal coalgebra of our
endofunctor. So now we make the following definition in which we encode the
coalgebra directly. This allows us to be much more general.

######  Definition 2.1 (Measuring, cf. Definition 3.3 and Proposition 3.8).

Consider algebras $A$ and $B$ and a coalgebra $C$. A _measuring from $A$ to
$B$ by $C$_ is a function $f\colon C\rightarrow A\rightarrow B$ such that:

_(M1)_

$f_{c}(0_{A})=0_{B}$ for all $c\in C$;

_(M2)_

$f_{c}(a+1)=0_{B}$ for all $\llbracket c\rrbracket=0$ and for all $a\in A$;

_(M3)_

$f_{c}(a+1)=f_{c-1}(a)+1$ for $\llbracket c\rrbracket\geq 1$ and for all $a\in
A$.

We write $\mu_{C}(A,B)$ for the set of measurings from $A$ to $B$. This
defines a functor
$\mu:{\mathsf{CoAlg}}^{\mathsf{op}}\times{\mathsf{Alg}}^{\mathsf{op}}\times{\mathsf{Alg}}\to{\mathsf{Set}}$.

For a measuring $f$ and an element $c\in C$, we call $f_{c}$ a _$C$ -partial
homomorphism_.

######  Example 2.2.

Suppose that $!_{A}:\mathbb{N}\to A$ is surjective, so that in particular,
every element of $A$ is of the form $0_{A}$ or $a+1$.

Then there is a measuring from $A$ to $B$ by ${\mathbb{n}^{\circ}}$ if the
induction of Section 2.2 creates an $n$-partial homomorphism, and in this case
the functions of the form $f_{c}$ constructed in Section 2.2 are the same as
those specified in Definition 2.1.

There is a measuring by $\mathbb{N}^{-}$ if the induction never fails, and
again the functions $f_{c}$ from Section 2.2 and Definition 2.1 coincide. Now,
note that exhibiting a measuring by ${\mathbb{N}^{\infty}}$ amounts to
exhibiting a measuring by $\mathbb{N}^{-}$ together with a total algebra
homomorphism $f_{\infty}$. For such an $A$, then, exhibiting a measuring by
$\mathbb{N}$ is equivalent to exhibiting one by ${\mathbb{N}^{\infty}}$.

The reader might wonder why Definition 2.1 does not require
$\mathsf{(M2^{\prime})}$ $f_{c}(x)=0_{B}$ for any $\llbracket{c}\rrbracket=0$
and any $x$, but rather only requires $f_{c}(x)=0_{B}$ when
$\llbracket{c}\rrbracket=0$ and $x$ is either the zero or a successor. In the
previous example, when $!_{A}:\mathbb{N}\to A$ is surjective, every $x\in A$
is either the zero or a successor, so there is no difference between these two
requirements. In the following example, we consider an algebra $A$ where this
is not the case, and illustrate why we only stipulate $\mathsf{(M2)}$ and not
$\mathsf{(M2^{\prime})}$.

######  Example 2.3.

Consider the algebra $A$ with underlying set $\mathbb{N}+\mathbb{N}$, where we
will notate the elements of the first copy of $\mathbb{N}$ as $n_{A}$, and the
elements of the second copy as $n^{\prime}$. The zero of $A$ is then $0_{A}$
and the successors are given by $n_{A}+1:=(n+1)_{A}$ and
$n^{\prime}+1:=(n+1)^{\prime}$. Total homomorphisms $A\to\mathbb{N}$ are
determined by the image of $0^{\prime}$ in $\mathbb{N}$.

If we require $\mathsf{(M2^{\prime})}$ instead of $\mathsf{(M2)}$ in
Definition 2.1, then in a measuring by ${\mathbb{N}^{\infty}}$,
$f_{0}(0^{\prime})=0_{\mathbb{N}}$ by $\mathsf{(M2^{\prime})}$, and in general
$f_{n}(n^{\prime})=n_{\mathbb{N}}$ by $\mathsf{(M3)}$.

However, following Definition 2.1 as written, in a measuring by
${\mathbb{N}^{\infty}}$, $f_{0}(0^{\prime})$ may be anything, say
$z\in\mathbb{N}$ and then general $f_{n}(n^{\prime})=(z+n)_{\mathbb{N}}$.

Thus, Definition 2.1 does generalize the idea of inductively approximating a
total homomorphism $A\to\mathbb{N}$ from Section 2.2.

Now notice another difference between Section 2.2 and Definition 2.1. In
Section 2.2 we continue the induction as far as we can, but there is nothing
of this flavor in Definition 2.1. For instance, if there is a total algebra
homomorphism $A\to B$, then in the process described by Section 2.2, we will
inductively construct $f_{c}$ for all $c\in\mathbb{N}$. However, following
Definition 2.1, we could say that $A$ to $B$ is measured by ${\mathbb{0}}$
(which only amounts to exhibiting $f_{0}$), without making any claim about it
being measured by other coalgebras – it does not ask us to find any kind of
maximum coalgebra $C$ that measures $A$ to $B$. To remedy this, we make the
following definition.

######  Definition 2.4 (Universal measuring, cf. Definition 3.5).

Let $A$ and $B$ be algebras.

We define the category of measurings from $A$ to $B$ to be the category whose
objects are pairs $(C;f)$ of a coalgebra $C$ and a measuring $f:C\to A\to B$,
and whose morphisms $(C;f)\to(D;g)$ are coalgebra homomorphisms $d:C\to D$
such that $f=gd$.

The _universal measuring from $A$ to $B$_, denoted
$({\underline{\mathsf{Alg}}}(A,B);u)$, is the terminal object in the category
of measurings from $A$ to $B$. That is, if $(C;f)$ is a measuring from $A$ to
$B$, then there is a unique morphism $!:C\to{\underline{\mathsf{Alg}}}(A,B)$
that makes the following diagram commute.

${C}$${A\to
B}$${{\underline{\mathsf{Alg}}}(A,B)}$$\scriptstyle{f}$$\scriptstyle{!}$$\scriptstyle{u}$

######  Example 2.5.

Again, suppose that $!_{A}:\mathbb{N}\to A$ is surjective. We show in the
appendix (Lemma A.1) that in this case, the universal measuring is a
subcoalgebra of ${\mathbb{N}^{\infty}}$. The subcoalgebras of
${\mathbb{N}^{\infty}}$ are of the form
$\emptyset,{\mathbb{n}^{\circ}},\mathbb{N}^{-},\mathbb{I},$ and
${\mathbb{N}^{\infty}}$. We have shown that if the induction of Section 2.2
creates an $n$-partial homomorphism, then the maximum subcoalgebra of
${\mathbb{N}^{\infty}}$ that measures $A$ to $B$ is ${\mathbb{n}^{\circ}}$, so
this is the universal measuring. And if the induction of Section 2.2 creates
an total homomorphism, then the maximum subcoalgebra of
${\mathbb{N}^{\infty}}$ that measures $A$ to $B$ is ${\mathbb{N}^{\infty}}$
itself, so this is the universal measuring. We will also show this fact more
directly in Section 2.4 below.

Since composing an arbitrary coalgebra homomorphism
$C\to{\underline{\mathsf{Alg}}}(A,B)$ with $u$ produces a measuring $C\to A\to
B$, we obtain a bijection, natural in $C,A,B$,

$\mu_{C}(A,B)\cong{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,B))$

showing that $\mu_{-}(A,B)$ is represented by
${\underline{\mathsf{Alg}}}(A,B)$. By Theorem 3.10, we will see that
${\underline{\mathsf{Alg}}}(A,B)$ always exists (for this and other
endofunctors of interest). The coalgebra ${\underline{\mathsf{Alg}}}(A,B)$
will constitute the hom-coalgebra from $A$ to $B$ of our enriched category of
algebras (Theorem 3.17).

Now, note that a measuring by the coalgebra $\mathbb{I}$ is a total algebra
homomorphism. Thus,

${\mathsf{Alg}}(A,B)\cong\mu_{\mathbb{I}}(A,B)\cong{\mathsf{CoAlg}}(\mathbb{I},{\underline{\mathsf{Alg}}}(A,B))$

and so we find the hom-sets of the category of algebras can be easily
extracted from ${\underline{\mathsf{Alg}}}(A,B)$ – a statement that aligns
with our intuition that ${\mathsf{Alg}}(A,B)$ is the set of total algebra
homomorphisms and ${\underline{\mathsf{Alg}}}(A,B)$ is the coalgebra of
partial algebra homomorphisms.

###  2.3 Composing partial homomorphisms

We will only prove that the universal measuring coalgebras form the hom-
objects of our enriched category in Theorem 3.17, but we can already work out
how this enrichment behaves. Thus, in this section, we describe the
composition and identities of this enriched category.

Given algebras $A,B$ and $T$, we can always compose total homomorphisms
$f:A\rightarrow B$ and $g:B\rightarrow T$ to form a total homomorphism $g\circ
f:A\rightarrow T$. We wish to do the same for our partial homomorphisms.
Consider coalgebras $C$ and $D$, a $C$-partial homomorphism
$f_{c}:A\rightarrow B$, and a $D$-partial homomorphism $g_{d}:B\rightarrow T$.
We can compose $g_{d}$ and $f_{c}$ as functions to obtain $g_{d}\circ
f_{c}:A\to T$, and we claim that this is a $(D\times C)$-partial homomorphism.
Indeed $D\times C$ has a coalgebra structure where
$\llbracket{(d,c)}\rrbracket=\min(\llbracket{d}\rrbracket,\llbracket{c}\rrbracket)$
for $(d,c)\in D\times C$ and

$(d,c)-1=\begin{cases}(d-1,c-1)&\text{if }\llbracket{(d,c)}\rrbracket>0;\\\
t&\text{if }\llbracket{(d,c)}\rrbracket=0.\end{cases}$

This induces a symmetric monoidal structure on ${\mathsf{CoAlg}}$ for which
$\mathbb{I}$ is the unit (Proposition 3.15), and one can verify that
$g_{d}\circ f_{c}$ is a $(D\times C)$-partial homomorphism.

Now we have constructed a function

$\displaystyle\mu_{D}(B,T)\times\mu_{C}(A,B)$
$\displaystyle\longrightarrow\mu_{D\times C}(A,T)$ $\displaystyle(g,f)$
$\displaystyle\longmapsto g\circ f$

where $g\circ f:(D\times C)\rightarrow A\to T$ is defined by $(g\circ
f)_{(d,c)}=g_{d}\circ f_{c}$. Thus, by the universal property of
${\underline{\mathsf{Alg}}}$, we obtain a function

$\displaystyle{\mathsf{CoAlg}}(D,{\underline{\mathsf{Alg}}}(B,T))\times{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,B))$
$\displaystyle\longrightarrow{\mathsf{CoAlg}}(D\times
C,{\underline{\mathsf{Alg}}}(A,T)).$

Applying this function to
$(\mathsf{id}_{{\underline{\mathsf{Alg}}}(B,T)},\mathsf{id}_{{\underline{\mathsf{Alg}}}(A,B)})$,
we obtain a composition morphism
$\circ:{\underline{\mathsf{Alg}}}(B,T)\times{\underline{\mathsf{Alg}}}(A,B)\to{\underline{\mathsf{Alg}}}(A,T)$
such that for
$(d,c)\in{\underline{\mathsf{Alg}}}(B,T)\times{\underline{\mathsf{Alg}}}(A,B)$,
we have $u_{d}\circ u_{c}=u_{d\circ c}$ (where $u$ is as in Definition 3.5).

Similarly, for any algebra $A$ we might ask if there is an identity
$\mathsf{id}_{A}:\mathbb{I}\to{\underline{\mathsf{Alg}}}(A,A)$. We showed
above that
${\mathsf{Alg}}(A,A)\cong{\mathsf{CoAlg}}(\mathbb{I},{\underline{\mathsf{Alg}}}(A,A))$.
Thus, we take the image of $\mathsf{id}_{A}\in{\mathsf{Alg}}(A,A)$ under this
bijection.

We will show in full generality in Theorem 3.17 that this constitutes an
enrichment of ${\mathsf{Alg}}$ in $({\mathsf{CoAlg}},\otimes,\mathbb{I})$,
i.e., that all the axioms for an enriched category are satisfied by this
choice of composition and identities.

###  2.4 The convolution algebra

We now give an alternative representation of $\mu_{C}(A,B)$ that can be
directly defined and computed. In this section, we will be able to use it to
compute ${\underline{\mathsf{Alg}}}(A,B)$ without appealing to Lemma A.1.

In Definition 2.1, we defined $\mu_{C}(A,B)$ to be a certain subset of
${\mathsf{Set}}(C,{\mathsf{Set}}(A,B))\cong{\mathsf{Set}}(A,{\mathsf{Set}}(C,B))$.
We now identify that subset as the subset of (total) algebra homomorphisms
$A\to{\mathsf{Set}}(C,B)$ with a particular _convolution_ algebra structure on
${\mathsf{Set}}(C,B)$.

######  Definition 2.6 (Convolution algebra, cf. Definition 3.12).

Given a coalgebra $(C,\chi_{C})$ and an algebra $(B,\alpha_{B})$, define the
_convolution algebra_ $[C,B]$ to be the algebra whose underlying set is
${\mathsf{Set}}(C,B)$, whose zero is the constant function $C\to B$ at
$0_{B}$, and where $f+1$ is defined by

$(f+1)(c)=\begin{cases}0_{B}&\text{if }\llbracket{c}\rrbracket=0;\\\
f(c-1)+1&\text{if }\llbracket{c}\rrbracket>0.\end{cases}$

This defines a functor
$[-,-]:{\mathsf{CoAlg}}^{\mathsf{op}}\times{\mathsf{Alg}}\to{\mathsf{Alg}}$.

Given a coalgebra $(C,\chi_{C})$ and an algebra $(B,\alpha_{B})$, a function
$m:C\rightarrow A\rightarrow B$ is a measuring if and only if the associated
$\widetilde{m}:A\rightarrow C\rightarrow B$ (under the bijection
$\widetilde{-}:{\mathsf{Set}}(C,{\mathsf{Set}}(A,B))\to{\mathsf{Set}}(A,{\mathsf{Set}}(C,B))$)
underlies a homomorphism $A\to[C,B]$ of algebras. Indeed, $\mathsf{(M1)}$ of
Definition 2.1 for $m$ is equivalent to $\mathsf{(H1)}$
$\widetilde{m}(0_{A})=0_{[C,B]}$ and criteria $\mathsf{(M2)}$ and
$\mathsf{(M3)}$ for $f$ are equivalent to $\mathsf{(H2)}$
$\widetilde{m}(a+1)=\widetilde{m}(a)+1$.

Therefore, we find the following string of bijections

$\displaystyle\mu_{C}(A,B)\cong{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,B))\cong{\mathsf{Alg}}(A,[C,B])$
(1)

so that we see that $\mu_{C}(-,B)$ is represented by $[C,B]$. We can even find
a representation for $\mu_{C}(-,B)$, but we will leave this for later (Theorem
3.7).

In practice, when we want to compute ${\underline{\mathsf{Alg}}}(A,B)$, we
will compute $[C,B]$ and then apply the universal property above. We do that
now, computing some of the results of Example 2.5 without appealing to Lemma
A.1.

######  Example 2.7.

We will now compute ${\underline{\mathsf{Alg}}}({\mathbb{n}},B)$ using the
right-hand bijection in Equation 1.

We first observe the following for any coalgebra $Z$.

${\mathsf{Alg}}({\mathbb{n}},Z)\cong\begin{cases}*&\text{if
}n_{Z}=(n+1)_{Z}\\\ \emptyset&\text{otherwise}\end{cases}$

Since we are considering $Z:=[C,B]$, we need to understand when
$n_{[C,B]}=(n+1)_{[C,B]}$. By definition, $0_{[C,A]}$ is the constant function
at $0_{A}$. Then the successor of $0_{[C,A]}$, i.e. $1_{[C,A]}$, is the
function that takes every $c\in C$ of index $0$ to $0_{B}$, and every other
$c\in C$ to $1_{B}$, so this is $1_{[C,B]}$. Inductively, we can show that
$n_{[C,B]}(c)=\min(\llbracket c\rrbracket,n)_{B}$. Thus,
$n_{[C,B]}=(n+1)_{[C,B]}$ means that $\min(\llbracket
c\rrbracket,n)_{B}=\min(\llbracket c\rrbracket,n+1)_{B}$ for all $c\in C$, and
this holds if and only if $\llbracket c\rrbracket\leq n$ for all $c\in C$ or
$n_{B}=(n+1)_{B}$. Now we have the following.

$\displaystyle{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}({\mathbb{n}},B))\cong{\mathsf{Alg}}({\mathbb{n}},[C,B])\cong\begin{cases}*&\text{if
}\llbracket c\rrbracket\leq n\text{ for all }c\in C\\\ *&\text{if
}n_{B}=(n+1)_{B}\\\ \emptyset&\text{otherwise}\end{cases}$ (2)

In the case that $n_{B}=(n+1)_{B}$, we find that
${\underline{\mathsf{Alg}}}({\mathbb{n}},B)$ has the universal property of the
terminal object, ${\mathbb{N}^{\infty}}$.

Now suppose that $n_{B}\neq(n+1)_{B}$. Since
${\mathsf{CoAlg}}(C,{\mathbb{n}^{\circ}})=*$ if and only if $\llbracket
c\rrbracket\leq n$ for all $c\in C$,
${\underline{\mathsf{Alg}}}({\mathbb{n}},B)$ has the universal property of
${\mathbb{n}^{\circ}}$.

Now we have calculated the following

${\underline{\mathsf{Alg}}}({\mathbb{n}},B)=\begin{cases}{\mathbb{N}^{\infty}}\text{
if }n_{B}=(n+1)_{B}\\\ {\mathbb{n}^{\circ}}\text{ otherwise}\end{cases}$

This aligns with our expectations, since there is a total homomorphism
${\mathbb{n}}\to B$ if $n_{B}=(n+1)_{B}$ but there is only an $n$-partial
homomorphism ${\mathbb{n}}\to B$ otherwise.

Finally, note that taking $B:=\mathbb{N}$, we have calculated
${\underline{\mathsf{Alg}}}({\mathbb{n}},\mathbb{N})$, the _dual_ (Definition
3.14) of ${\mathbb{n}}$, to be ${\mathbb{n}^{\circ}}$.

###  2.5 Generalizing initial objects

Now we turn to the question of specifying algebras other than $\mathbb{N}$ via
a generalization of the notion of initial algebra.

The fact that $\mathbb{N}$ is the initial object in ${\mathsf{Alg}}$ means
that the algebra structure on an algebra $A$ specifies exactly one total
algebra homomorphism $\mathbb{N}\to A$, and this can be constructed
inductively. Now we have introduced the notion of partial homomorphism which
can be constructed by partial induction (Section 2.2). Thus, we might ask if
we can formalize a notion of being initial with respect to partial
homomorphisms and partial induction.

Our calculations in this section so far have perhaps given us the intuition
that the algebra ${\mathbb{n}}$ represents $n$-partial homomorphisms in the
way that $\mathbb{N}$ represents total homomorphisms. Indeed, from Equation 2,
there is a unique measuring $f:{\mathbb{n}^{\circ}}\to{\mathbb{n}}\to B$ for
any algebra $B$. Now we try to capture and elucidate this fact by rephrasing
it to say that ${\mathbb{n}}$ is a certain kind of initial object with respect
to such partial homomorphisms.

There are multiple equivalent definitions of initial object, and we choose the
one that is amenable to generalization. We choose to define an initial object
in a category $\mathcal{C}$ as an object $I\in\mathcal{C}$ such that there is
a unique function $1\to\mathcal{C}(I,X)$ for all $X\in\mathcal{C}$. Now we
have brought to the surface a parameter, here $1$, that we can vary.

######  Definition 2.8 ($C$-initial algebra, cf. Definition 3.21).

For a coalgebra $C$, we define a _$C$ -initial algebra_ to be an algebra $A$
such that there is a unique coalgebra morphism
$C\to{\underline{\mathsf{Alg}}}(A,X)$ for all algebras $X$.

######  Remark 2.9.

One may wonder what would happen if for a _set_ $S$, we defined an $S$-initial
algebra to be an algebra $A$ such that there is a unique _function_
$S\to{\mathsf{Alg}}(A,X)$ for all $X\in{\mathsf{Alg}}$. But every algebra is
an $\emptyset$-initial algebra, and an $S$-initial algebra is an initial
algebra for any $S\neq\emptyset$ (because functions $S\to T$ are unique only
when $S=\emptyset$ or $T\cong 1$). Thus, we need to consider
${\underline{\mathsf{Alg}}}(A,X)$ and not just ${\mathsf{Alg}}(A,X)$ to obtain
interesting $C$-initial algebras.

######  Example 2.10.

We have shown in Example 2.7 that ${\mathbb{n}}$ is an
${\mathbb{n}^{\circ}}$-initial algebra.

Since
${\mathsf{Alg}}(A,X)\cong{\mathsf{CoAlg}}(\mathbb{I},{\underline{\mathsf{Alg}}}(A,X))$,
the initial algebra $\mathbb{N}$ is the (only) $\mathbb{I}$-initial algebra.
In fact, since
${\underline{\mathsf{Alg}}}(\mathbb{N},X)={\mathbb{N}^{\infty}}$ for all $X$
by Lemma A.1, we find that $\mathbb{N}$ is a $C$-initial algebra for any
subterminal coalgebra (i.e.,
$\emptyset,{\mathbb{n}^{\circ}},\mathbb{N}^{-},{\mathbb{N}^{\infty}}$).

Now we see that for instance, both ${\mathbb{n}}$ and $\mathbb{N}$ are
${\mathbb{n}^{\circ}}$-initial algebras. Thus, ${\mathbb{n}^{\circ}}$-initial
algebras are not determined up to isomorphism as initial algebras are. This
captures the fact that for an algebra $B$, we can construct $n$-partial
homomorphisms from both ${\mathbb{n}}$ and $\mathbb{N}$ to $B$.

######  Definition 2.11 (Terminal $C$-initial algebra, cf. Definition 3.21).

Consider the category whose objects are $C$-initial algebras, and whose
morphisms $A\to B$ are total algebra homomorphisms $A\to B$. Then we call the
terminal object of this category the _terminal $C$-initial algebra_.

######  Example 2.12.

Since the only $\mathbb{I}$-initial algebra is $\mathbb{N}$, it is also the
terminal $C$-initial algebra.

We want to show that ${\mathbb{n}}$ is the terminal
${\mathbb{n}^{\circ}}$-initial algebra. However, we need another computational
tool. This is in fact an alternate generalization of the notion of initial
algebra.

Above, we might have observed that an initial object can be characterized as
the limit of the identity functor and then, following the theory of weighted
limits, considered objects
$\mathsf{lim}^{C}\mathsf{id}_{\underline{\mathsf{Alg}}}$ with the following
universal property.

${\mathsf{Alg}}(A,\mathsf{lim}^{C}\mathsf{id}_{\underline{\mathsf{Alg}}})\cong\mathsf{lim}_{X\in{\mathsf{Alg}}}\
{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,X))$

We can immediately calculate (Proposition 3.22) that
$\mathsf{lim}^{C}\mathsf{id}_{\underline{\mathsf{Alg}}}$ is $C^{*}$, the dual
of $C$ (Definition 3.14). By the bijection above, there is a unique total
algebra homomorphism from each $C$-initial object to
$\mathsf{lim}^{C}\mathsf{id}_{\underline{\mathsf{Alg}}}$. This will help us
understand the possible structure that a $C$-initial object can have. But
first, we must understand the structure of $C^{*}:=[C,\mathbb{N}]$.

######  Example 2.13.

Let $C:={\mathbb{n}^{\circ}}$. Then elements of
$[{\mathbb{n}^{\circ}},\mathbb{N}]$ are sequences of $n+1$ natural numbers.

The successor of a sequence $(a_{i})_{i=0}^{n}$ is $(b_{i})_{i=0}^{n}$ where
$b_{0}=0$ and $b_{i+1}=a_{i}+1$. Notice that the successor of
$(b_{i})_{i=0}^{n}$ is $(c_{i})_{i=0}^{n}$ where $c_{0}=0$, $c_{1}=1$ and
otherwise $c_{i+2}=a_{i}+2$. Thus, we can inductively show that the $(n+1)$-st
successor of any element of $[{\mathbb{n}^{\circ}},\mathbb{N}]$ is the
sequence $(i)_{i=0}^{n}$, and the successor of this sequence is itself.

We claim that the unique morphism
$!_{[{\mathbb{n}^{\circ}},\mathbb{N}]}:\mathbb{N}\to[{\mathbb{n}^{\circ}},\mathbb{N}]$
factors through ${\mathbb{n}}$. We have
$m_{[{\mathbb{n}^{\circ}},\mathbb{N}]}=(\min(i,m))_{i=0}^{n}$. Thus, the
restriction of the map $!_{[{\mathbb{n}^{\circ}},\mathbb{N}]}$ to
$\\{0,...,n\\}\subset\mathbb{N}$ is injective, and
$n_{[{\mathbb{n}^{\circ}},\mathbb{N}]}=m_{[{\mathbb{n}^{\circ}},\mathbb{N}]}$
for all $m\geq n$.

######  Example 2.14.

Now we can show that ${\mathbb{n}}$ is the terminal
${\mathbb{n}^{\circ}}$-initial algebra. In this calculation, we make liberal
use of the law of excluded middle.

Consider a ${\mathbb{n}^{\circ}}$-initial algebra $A$.

First, we show that every $a\in A$ is either the basepoint or a successor. So
suppose that there is an element $a\in A$ that is not a basepoint or
successor, and consider an algebra $B$ with more than one element. Then for
any $b\in B$ and any measure $f:{\mathbb{n}^{\circ}}\to A\to B$, we can form a
measure $\tilde{f}:{\mathbb{n}^{\circ}}\to A\to B$ such that
$\tilde{f}(n)(a)=b$ and $\tilde{f}$ agrees with $f$ everywhere else, since
Definition 2.1 imposes no requirements $\tilde{f}(n)(a)$. Thus, there are
multiple measures ${\mathbb{n}^{\circ}}\to A\to B$, equivalently total algebra
homomorphisms ${\mathbb{n}^{\circ}}\to{\underline{\mathsf{Alg}}}(A,B)$.

Now, we consider the unique map $A\to[{\mathbb{n}^{\circ}},\mathbb{N}]$ and
claim that this factors through
${\mathbb{n}}\to[{\mathbb{n}^{\circ}},\mathbb{N}]$, so that there is a unique
$A\to{\mathbb{n}}$. Since every element of $A$ is either a basepoint or a
successor, every element of $A$ is either of the form $n_{A}$ or has
infinitely many predecessors. The elements of the form $n_{A}$ are mapped
those to of the form $n_{[{\mathbb{n}^{\circ}},\mathbb{N}]}$, and the elements
who have infinitely many predecessors can only be mapped to the ‘top element’
$n_{[{\mathbb{n}^{\circ}},\mathbb{N}]}=(i)_{i=0}^{n}$, since this is the only
element which has an $m$-th predecessor for any $m\in\mathbb{N}$. Thus, the
unique $A\to[{\mathbb{n}^{\circ}},\mathbb{N}]$ indeed factors through
${\mathbb{n}}$.

Thus we have shown how to specify algebras of the form ${\mathbb{n}}$ in a way
analogous to the specification of $\mathbb{N}$ as an initial algebra. After
determining an algebra structure on a set $A$, we obtain a unique $n$-partial
algebra homomorphism ${\mathbb{n}}\to A$.

##  3 General theory

In this section, we now generalize the results of the previous section. So fix
a symmetric monoidal category $(\mathcal{C},\otimes,\mathbb{I})$ and a lax
symmetric monoidal endofunctor $(F,\nabla,\eta)$ (defined below in Definition
3.1) on $\mathcal{C}$.

###  3.1 Measuring coalgebras

In this section, we define the general notion of _measuring_ for $F$. Note
that in Section 2.2 above, it was convenient to define a measuring to be a
certain kind of function $C\to A\to B$, but here we first define the notion of
measuring without requiring the monoidal structure to be closed. That is, we
define a measuring to be a certain kind of function $C\otimes A\to B$.

######  Definition 3.1.

That $(F,\nabla,\eta)$ is a _lax symmetric monoidal endofunctor_ means that
$F$ is an endofunctor on $\mathcal{C}$ with

_(L1)_

a natural transformation $\nabla_{X,Y}\colon F(X)\otimes F(Y)\longrightarrow
F(X\otimes Y)$, for all $X,Y\in\mathcal{C}$; and

_(L2)_

a morphism $\eta:\mathbb{I}\rightarrow F(\mathbb{I})$ in $\mathcal{C}$;

such that $(F,\nabla,\eta)$ is associative, unital and commutative, as
described in Section A.2.

######  Example 3.2.

In Section 2, we considered the (cartesian closed) symmetric monoidal category
$({\mathsf{Set}},\times,1)$. For the endofunctor $\mathsf{id}+1$, we define
$\nabla_{X,Y}:(X+1)\times(Y\times 1)\to(X\times Y)+1$ to take
$(x,y)\mapsto(x,y)$, $(t,y)\mapsto t$, and $(x,t)\mapsto t$ for $x\in X,y\in
Y,t\in 1$. We define $\eta:1\to 1+1$ to be the inclusion into the first
summand.

######  Definition 3.3 (Measuring, cf. Definition 2.1).

Consider algebras $(A,\alpha)$ and $(B,\beta)$, and a coalgebra $(C,\chi)$. We
call a map $\phi:C\otimes A\rightarrow B$ a _measuring from $A$ to $B$_ if it
makes the following diagram commute.

${F(C)\otimes F(A)}$${F(C\otimes A)}$${F(B)}$${C\otimes F(A)}$${C\otimes
A}$${B}$$\scriptstyle{\nabla_{C,A}}$$\scriptstyle{F(\phi)}$$\scriptstyle{\beta}$$\scriptstyle{\chi\otimes\mathsf{id}}$$\scriptstyle{\mathsf{id}\otimes\alpha}$$\scriptstyle{\phi}$

We denote by $\mu_{C}(A,B)$ the set of all measurings $C\otimes A\rightarrow
B$.

If $\phi\colon C\otimes A\rightarrow B$ is a measuring,
$a\colon(A^{\prime},\alpha_{A^{\prime}})\rightarrow(A,\alpha_{A})$ and
$b\colon(B,\alpha_{B})\rightarrow(B^{\prime},\alpha_{B^{\prime}})$ are algebra
homomorphisms, and
$c\colon(C^{\prime},\chi_{C^{\prime}})\rightarrow(C,\chi_{C})$ is a coalgebra
homomorphism, then one can check that the composition

${C^{\prime}\otimes A^{\prime}}$${C\otimes
A}$${B}$${B^{\prime}}$$\scriptstyle{c\otimes
a}$$\scriptstyle{\phi}$$\scriptstyle{b}$

is a measuring. Therefore, the assignment $C,A,B\mapsto\mu_{C}(A,B)$ underlies
a functor

$\mu\colon{\mathsf{CoAlg}}^{\mathsf{op}}\times{\mathsf{Alg}}^{\mathsf{op}}\times{\mathsf{Alg}}\longrightarrow{\mathsf{Set}}.$

We shall see that this functor is representable in each of its variables.

######  Example 3.4.

The monoidal unit $\mathbb{I}$ of $\mathcal{C}$ is a coalgebra via the lax
symmetric monoidal structure $\eta:\mathbb{I}\rightarrow F(\mathbb{I})$. Thus
morphisms $A\to B$ in $\mathcal{C}$ are in bijection with morphisms
$\mathbb{I}\otimes A\to B$ in $\mathcal{C}$, and one can check that a morphism
$A\to B$ in $\mathcal{C}$ is an algebra homomorphism if and only if
$\mathbb{I}\otimes A\to B$ is a measure. Thus,
$\mu_{\mathbb{I}}(A,B)\cong{\mathsf{Alg}}(A,B)$.

######  Definition 3.5 (Universal measuring, cf. Definition 2.4).

Let $A$ and $B$ be algebras.

We define the category of measurings from $A$ to $B$ to be the category whose
objects are pairs $(C;f)$ of a coalgebra $C$ and a measuring $f:C\otimes A\to
B$, and whose morphisms $(C;f)\to(D;g)$ are coalgebra homomorphisms $d:C\to D$
such that $f=g(d\otimes A)$.

The _universal measuring from $A$ to $B$_, denoted
$({\underline{\mathsf{Alg}}}(A,B),\mathsf{ev})$, is the terminal object (if it
exists) in the category of measurings from $A$ to $B$. That is, if $(C;f)$ is
a measuring from $A$ to $B$, then there is a unique morphism
$!:C\to{\underline{\mathsf{Alg}}}(A,B)$ that makes the following diagram
commute.

${C\otimes A}$${B}$${{{\underline{\mathsf{Alg}}}(A,B)\otimes
A}}$$\scriptstyle{f}$$\scriptstyle{!\otimes A}$$\scriptstyle{\mathsf{ev}}$

If a universal measuring $({\underline{\mathsf{Alg}}}(A,B),\mathsf{ev})$
exists, then we obtain a representation ${\underline{\mathsf{Alg}}}(A,B)$ for
$\mu_{-}(A,B):{\mathsf{CoAlg}}^{\mathsf{op}}\to{\mathsf{Set}}$. That is, we
have the following bijection, natural in $C,A,B$.

$\mu_{C}(A,B)\cong{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,B)).$

In the following sections, we will show that if $\mathcal{C}$ is closed and
locally presentable and $F$ is accessible, then the universal measuring always
exists.

###  3.2 Local presentability, accessibility, and the measuring tensor

We will now usually require that $\mathcal{C}$ be _locally presentable_ and
$F$ is _accessible_ [2, Def. 1.17 & 2.17]. Then ${\mathsf{Alg}}$ and
${\mathsf{CoAlg}}$ are also locally presentable, the forgetful functor
${\mathsf{Alg}}\to\mathcal{C}$ has a left adjoint $\mathsf{Fr}$, and the
forgetful functor ${\mathsf{CoAlg}}\to\mathcal{C}$ has a right adjoint
$\mathsf{Cof}$ [2, Cor. 2.75 & Ex. 2.j]. We will also use that these
categories, as locally presentable categories, are complete and cocomplete.

######  Example 3.6.

${\mathsf{Set}}$ is locally presentable and $\mathsf{id}+1$ is accessible.

If $\mathcal{C}$ is locally presentable and $F$ is accessible, then for a
coalgebra $(C,\chi)$, and algebras $(A,\alpha)$ and $(B,\beta)$, a map
$\phi\colon C\otimes A\rightarrow B$ uniquely determines an algebra
homomorphism $\phi^{\prime}\colon\mathsf{Fr}(C\otimes A)\rightarrow(B,\beta)$.
Notice then that a map $\phi\colon C\otimes A\rightarrow B$ is a measuring if
and only if both composites from $\mathsf{Fr}(C\otimes FA)$ to $(B,\beta)$
coincide in the following diagram.

${\mathsf{Fr}(C\otimes FA)}$${\mathsf{Fr}(C\otimes
A)}$${(B,\beta)}$$\scriptstyle{\mathsf{Fr}(\mathsf{id}_{C}\otimes\alpha)}$$\scriptstyle{f}$$\scriptstyle{\phi^{\prime}}$

In the above, $f$ is obtained as adjunct under the free-forgetful adjunction
of the composition

${C\otimes FA}$${FC\otimes FA}$${F(C\otimes A)}$${F(\mathsf{Fr}(C\otimes
A))}$${\mathsf{Fr}(C\otimes
A),}$$\scriptstyle{\chi\otimes\mathsf{id}}$$\scriptstyle{\nabla_{C,A}}$$\scriptstyle{F(i)}$$\scriptstyle{\alpha_{\mathsf{Fr}}}$

in which $i$ is the unit of the free-forgetful adjunction and
$\alpha_{\mathsf{Fr}}$ is the algebra structure on the free algebra
$\mathsf{Fr}(C\otimes A)$. We have now shown the following.

######  Theorem 3.7.

Suppose that $\mathcal{C}$ is locally presentable and $F$ is accessible.
Consider a coalgebra $C$ and an algebra $A$. Then the coequalizer of the
following diagram in ${\mathsf{Alg}}$ exists, and we denote it by
$C\triangleright A$ and call it the _measuring tensor of $C$ and $A$._

${\mathsf{Fr}(C\otimes F(A))}$${\mathsf{Fr}(C\otimes A)}$${C\triangleright
A.}$$\scriptstyle{\mathsf{coeq}}$

Given any algebra $B$, a measuring $\phi:C\otimes A\rightarrow B$ uniquely
corresponds to an algebra homomorphism $C\triangleright A\rightarrow B$. In
other words, we obtain a natural identification

$\mu_{C}(A,B)\cong{\mathsf{Alg}}(C\triangleright A,B).$

That is, the functor $\mu_{C}(A,-):{\mathsf{Alg}}\to{\mathsf{Set}}$ is
represented by $C\triangleright A$.

In the following sections, we will also construct representing objects for
$\mu_{C}(-,B)$ and $\mu_{-}(A,B)$.

###  3.3 Measurings as partial homomorphisms

Now we will often assume that the symmetric monoidal structure of
$\mathcal{C}$ is closed. Whenever we do, we will denote the internal hom by
$\underline{\mathcal{C}}(-,-)$. In this section, we provide a dual description
of measurings when $\mathcal{C}$ is closed, generalizing Definition 2.1.

Note that since $F$ is lax monoidal, it is also lax closed: that is, there is
a map

$\widetilde{\nabla}_{X,Y}:F\left(\underline{\mathcal{C}}(X,Y)\right)\stackrel{{\scriptstyle}}{{\longrightarrow}}\underline{\mathcal{C}}(FX,FY)$

natural in $X,Y\in\mathcal{C}$. Indeed, this is the adjunct under the
adjunction $-\otimes FX\dashv\underline{\mathcal{C}}(FX,-)$ of the composition

${F(\underline{\mathcal{C}}(X,Y))\otimes
F(X)}$${F(\underline{\mathcal{C}}(X,Y)\otimes
X)\xrightarrow{F(\mathsf{ev}_{X})}F(Y),}$$\scriptstyle{\nabla_{\underline{\mathcal{C}}(X,Y),X}}$

in which $\mathsf{ev}_{X}$ is the counit of the adjunction $-\otimes
X\dashv\underline{\mathcal{C}}(X,-)$.

Given a closed monoidal structure, we can connect the notion of measuring with
our notion of partial homomorphism from Section 2.

######  Proposition 3.8 (cf. Definition 2.1).

Suppose that $\mathcal{C}$ is closed. Given algebras $(A,\alpha)$ and
$(B,\beta)$ and a coalgebra $(C,\chi)$, a map $\phi:C\otimes A\rightarrow B$
is a measuring if and only if its adjunct
$\widetilde{\phi}:C\rightarrow\underline{\mathcal{C}}(A,B)$ fits in the
following commutative diagram.

${F(C)}$${F(\underline{\mathcal{C}}(A,B))}$${\underline{\mathcal{C}}(F(A),F(B))}$${C}$${\underline{\mathcal{C}}(A,B)}$${\underline{\mathcal{C}}(F(A),B)}$$\scriptstyle{F(\widetilde{\phi})}$$\scriptstyle{\widetilde{\nabla}_{A,B}}$$\scriptstyle{\beta_{*}}$$\scriptstyle{\chi}$$\scriptstyle{\widetilde{\phi}}$$\scriptstyle{\alpha^{*}}$

We shall also refer to the pair $(C;\widetilde{\phi})$ as a measuring.

######  Example 3.9.

Note that the cartesian monoidal structure on ${\mathsf{Set}}$ is closed, and
that the above recovers Definition 2.1.

This approach allows us to reformulate the notion of measuring as certain
coalgebra homomorphisms which we now describe. If $\mathcal{C}$ is locally
presentable and $F$ is accessible, then given a coalgebra $(C,\chi)$ and
algebras $(A,\alpha)$ and $(B,\beta)$, a map
$\phi:C\rightarrow\underline{\mathcal{C}}(A,B)$ in $\mathcal{C}$ uniquely
determines a coalgebra homomorphism
$\phi^{\prime}:(C,\chi_{C})\rightarrow\mathsf{Cof}(\underline{\mathcal{C}}(A,B))$.
A map $\phi:C\rightarrow\underline{\mathcal{C}}(A,B)$ is a measuring if and
only if both composites from $(C,\chi_{C})$ to
$\mathsf{Cof}\big{(}\underline{\mathcal{C}}(FA,B)\big{)}$ in the following
diagram coincide.

${(C,\chi_{C})}$${\mathsf{Cof}\big{(}\underline{\mathcal{C}}(A,B)\big{)}}$${\mathsf{Cof}\big{(}\underline{\mathcal{C}}(FA,B)\big{)}}$$\scriptstyle{\phi^{\prime}}$$\scriptstyle{\mathsf{Cof}(\underline{\mathcal{C}}(\alpha,B))}$$\scriptstyle{f}$

In the above, $f$ is the adjunct under the cofree-forgetful adjunction of the
following composite.

${\mathsf{Cof}(\underline{\mathcal{C}}(A,B))}$${F\big{(}\mathsf{Cof}(\underline{\mathcal{C}}(A,B))\big{)}}$${F\big{(}\underline{\mathcal{C}}(A,B)\big{)}}$${\underline{\mathcal{C}}(F(A),F(B))}$${\underline{\mathcal{C}}(F(A),B).}$$\scriptstyle{\chi_{\mathsf{Cof}}}$$\scriptstyle{F(\varepsilon)}$$\scriptstyle{\widetilde{\nabla}_{A,B}}$$\scriptstyle{\beta_{*}}$

Here $\chi_{\mathsf{Cof}}$ is the coalgebraic structure on the cofree
coalgebra, and $\varepsilon$ is the counit of the cofree-forgetful adjunction.

Now we can use this to guarantee the existence of a universal measuring.

######  Theorem 3.10 (Proof in Section A.3).

Suppose that $\mathcal{C}$ is locally presentable and closed and that $F$ is
accessible. Given algebras $A$ and $B$, then the universal measuring coalgebra
${\underline{\mathsf{Alg}}}(A,B)$ exists and is obtained as the following
equalizer diagram in ${\mathsf{CoAlg}}$

${{\underline{\mathsf{Alg}}}(A,B)}$${\mathsf{Cof}\big{(}\underline{\mathcal{C}}(A,B)\big{)}}$${\mathsf{Cof}\big{(}\underline{\mathcal{C}}(F(A),B)\big{)},}$$\scriptstyle{\mathsf{eq}}$

with
$\widetilde{\mathsf{ev}}\colon{\underline{\mathsf{Alg}}}(A,B)\rightarrow\underline{\mathcal{C}}(A,B)$
obtained as the composition of the equalizer map $\mathsf{eq}$ together with
the counit
$\mathsf{Cof}\big{(}\underline{\mathcal{C}}(A,B)\big{)}\rightarrow\underline{\mathcal{C}}(A,B)$
of the cofree-forgetful adjunction.

######  Corollary 3.11.

Suppose that $\mathcal{C}$ is locally presentable and closed and that $F$ is
accessible. Given algebras $A$ and $B$, the functor
$\mu_{-}(A,B):{\mathsf{CoAlg}}^{\mathsf{op}}\to{\mathsf{Set}}$ is represented
by ${\underline{\mathsf{Alg}}}(A,B)$.

###  3.4 Measuring via the convolution algebra

We will now describe the last representable object for the measuring functor.

######  Definition 3.12 (Convolution algebra, cf. Definition 2.6).

Suppose that $\mathcal{C}$ is closed. Given a coalgebra $(C,\chi_{C})$ and an
algebra $(A,\alpha_{A})$ in $\mathcal{C}$, we define an algebra structure on
$\underline{\mathcal{C}}(C,A)$, called the _convolution algebra_ , which is
denoted $[(C,\chi_{C}),(A,\alpha_{A})]$ or simply $[C,A]$, as follows. The
algebra structure $F[C,A]\rightarrow[C,A]$ is the composition

${F(\underline{\mathcal{C}}(C,A))}$${{\underline{\mathcal{C}}(FC,FA)}}$${{\underline{\mathcal{C}}(C,A)},}$$\scriptstyle{\widetilde{\nabla}_{C,A}}$$\scriptstyle{\alpha_{A}^{*}{\chi_{C}}_{*}}$

where $\alpha_{A}^{*}{\chi_{C}}_{*}(f)=\alpha_{A}\circ f\circ\chi_{C}$, for
any $f:FC\rightarrow FA$. The convolution algebra construction lifts the
internal hom to a functor

$[-,-]\colon{\mathsf{CoAlg}}^{\mathsf{op}}\times{\mathsf{Alg}}\longrightarrow{\mathsf{Alg}}.$

The convolution algebra provides a representing object for
$\mu_{C}(-,B):{\mathsf{Alg}}^{\mathsf{op}}\to{\mathsf{Set}}$. Indeed, we have
the following bijection natural in $C,A,B$.

$\mu_{C}(A,B)\cong{\mathsf{Alg}}(A,[C,B]).$

In other words, a measuring $\phi\colon C\otimes A\rightarrow B$ corresponds
to an algebra homomorphism $\phi^{\prime}:A\rightarrow[C,B]$ under the
identification $\mathcal{C}(C\otimes
A,B)\cong\mathcal{C}(A,\underline{\mathcal{C}}(C,B))$. Indeed, notice that
$\phi^{\prime}$ is a homomorphism if and only if the following diagram,
adjunct to the one appearing in Definition 3.3, commutes.

${F([C,B])}$${{[F(C),F(B)]}}$${F(A)}$${A}$${{[C,B]}}$$\scriptstyle{\widetilde{\nabla}_{C,B}}$$\scriptstyle{\alpha_{A}^{*}{\chi_{C}}_{*}}$$\scriptstyle{F(\phi^{\prime})}$$\scriptstyle{\alpha_{A}}$$\scriptstyle{\phi^{\prime}}$

######  Remark 3.13.

The convolution algebra also provides an alternative characterization of the
algebra $C\triangleright A$ and coalgebra ${\underline{\mathsf{Alg}}}(A,B)$.
As limits in ${\mathsf{Alg}}$ and colimits in ${\mathsf{CoAlg}}$ are
determined in $\mathcal{C}$ [1] and the internal hom
$\underline{\mathcal{C}}(-,-):\mathcal{C}^{\mathsf{op}}\times\mathcal{C}\rightarrow\mathcal{C}$
preserves limits, the functor
$[-,-]:{\mathsf{CoAlg}}^{\mathsf{op}}\times{\mathsf{Alg}}\rightarrow{\mathsf{Alg}}$
also preserves limits. Moreover, fixing a coalgebra $C$, the induced functor
$[C,-]:{\mathsf{Alg}}\rightarrow{\mathsf{Alg}}$ is accessible since filtered
colimits in ${\mathsf{Alg}}$ are computed in $\mathcal{C}$ (see [1, 5.6]).
Therefore, by the adjoint functor theorem [2, 1.66], the functor $[C,-]$ is a
right adjoint. Its left adjoint is precisely
$C\triangleright-:{\mathsf{Alg}}\rightarrow{\mathsf{Alg}}$. Indeed, for any
algebras $A$ and $B$, we obtain the following bijection, natural in $C,A,B$.

${\mathsf{Alg}}\big{(}C\triangleright
A,B\big{)}\cong{\mathsf{Alg}}\big{(}A,[C,B]\big{)}.$

Notice we can also determine the universal measuring by using the adjoint
functors. Fixing now an algebra $B$, the opposite functor
$[-,B]^{\mathsf{op}}:{\mathsf{CoAlg}}\rightarrow{\mathsf{Alg}}^{\mathsf{op}}$
preserves colimits, where the domain is locally presentable and the codomain
is essentially locally small. By the adjoint functor theorem [2, 1.66] and [4,
5.5.2.10], this functor is a left adjoint. Its right adjoint is precisely the
functor
${\underline{\mathsf{Alg}}}(-,B):{\mathsf{Alg}}^{\mathsf{op}}\rightarrow{\mathsf{CoAlg}}$.
Indeed, for any algebra $A$ and $B$ and any coalgebra $C$, we have the
following bijection, natural in $C,A,B$.

${\mathsf{CoAlg}}\big{(}C,{\underline{\mathsf{Alg}}}(A,B)\big{)}\cong{\mathsf{Alg}}\big{(}A,[C,B]\big{)}.$

Combining the identifications, we see that the measuring functor is
representable in each factor:

$\mu_{C}(A,B)\cong{\mathsf{CoAlg}}\big{(}C,{\underline{\mathsf{Alg}}}(A,B)\big{)}\cong{\mathsf{Alg}}\big{(}A,[C,B]\big{)}\cong{\mathsf{Alg}}\big{(}C\triangleright
A,B\big{)}.$

In other words, for any algebra $A$ and $B$ and any coalgebra $C$, the
following data are equivalent.

$C\otimes A\rightarrow B$ | $C\rightarrow\underline{\mathcal{C}}(A,B)$ | $C\rightarrow{\underline{\mathsf{Alg}}}(A,B)$ | $A\rightarrow[C,B]$ | $C\triangleright A\rightarrow B$
---|---|---|---|---
measuring | measuring | coalgebra | algebra | algebra
|  | homomorphism | homomorphism | homomorphism

######  Definition 3.14.

Assuming that $\mathcal{C}$ is locally presentable and $F$ is accessible,
${\mathsf{Alg}}$ has an initial object $N$.

Let $(-)^{*}:{\mathsf{CoAlg}}^{\mathsf{op}}\rightarrow{\mathsf{Alg}}$ denote
the functor $[-,N]$, and call $C^{*}$ the _dual algebra of $C$_ for any
coalgebra $C$.

Let $(-)^{\circ}:{\mathsf{Alg}}^{\mathsf{op}}\rightarrow{\mathsf{CoAlg}}$
denote the functor ${\underline{\mathsf{Alg}}}(A,N)$, and call $A^{\circ}$ the
_dual coalgebra of $A$_ for any algebra $A$.

These functors form a dual adjunction since we have the following bijection,
natural in $C,A$:

${\mathsf{Alg}}(A,C^{*})\cong{\mathsf{CoAlg}}(C,A^{\circ}).$

###  3.5 Measuring as an enrichment

We now come to the main punchline of the general theory presented in this
paper: that ${\underline{\mathsf{Alg}}}(-,-)$ gives the category of algebras
an enrichment in coalgebras. First, we describe how to compose measurings.

######  Proposition 3.15.

The category ${\mathsf{CoAlg}}$ has a symmetric monoidal structure for which
the forgetful functor ${\mathsf{CoAlg}}\rightarrow\mathcal{C}$ is strong
symmetric monoidal.

######  Proof 3.16.

Suppose $(C,\chi_{C})$ and $(D,\chi_{D})$ are coalgebras. Then $C\otimes D$
has the following coalgebra structure.

${{C\otimes D}}$${{F(C)\otimes F(D)}}$${{F(C\otimes
D)}}$$\scriptstyle{\chi_{C}\otimes\chi_{D}}$$\scriptstyle{\nabla_{C,D}}$

The morphism $\eta:\mathbb{I}\rightarrow F(\mathbb{I})$ provides the
coalgebraic structure on $\mathbb{I}$. One can verify that
$({\mathsf{CoAlg}},\otimes,(\mathbb{I},\eta))$ is a symmetric monoidal
category, see details in Section A.4.

Now we can prove our main theorem.

######  Theorem 3.17 (Proof in Section A.5).

Suppose that $\mathcal{C}$ is locally presentable and closed and that $F$ is
accessible. Then the category ${\mathsf{Alg}}$ is enriched, tensored, and
powered over the symmetric monoidal category ${\mathsf{CoAlg}}$ respectively
via

${\mathsf{Alg}}^{\mathsf{op}}\times{\mathsf{Alg}}\xrightarrow{{\underline{\mathsf{Alg}}}(-,-)}{\mathsf{CoAlg}},\quad{\mathsf{CoAlg}}\times{\mathsf{Alg}}\xrightarrow{-\triangleright-}{\mathsf{Alg}},\quad{\mathsf{CoAlg}}^{\mathsf{op}}\times{\mathsf{Alg}}\xrightarrow{[-,-]}{\mathsf{Alg}}.$

######  Example 3.18 (Details in Section A.7).

Suppose that $\mathcal{C}$ is locally presentable and closed. The following
endofunctors on $\mathcal{C}$ are accessible and lax symmetric monoidal.

$(\mathsf{id})$

The identity endofunctor $\mathsf{id}_{\mathcal{C}}$.

$(A)$

The constant endofunctor that sends each object to a fixed commutative monoid
$A$ in $\mathcal{C}$.

$(GF)$

The composition $GF$ of accessible, lax symmetric monoidal endofunctors $F$
and $G$.

$(F\otimes G)$

The pointwise tensor product $F\otimes G$ of accessible, lax symmetric
monoidal endofunctors $F$ and $G$, assuming $\mathcal{C}$ is closed.

$(F+G)$

The pointwise coproduct $F+G$ of an accessible, lax symmetric monoidal
endofunctor $F$ and an accessible endofunctor $G$ equipped with natural
transformations $GX\otimes GY\to G(X\otimes Y)$, $\lambda:FX\otimes GY\to
G(X\otimes Y)$, $\rho:GX\otimes FY\to G(X\otimes Y)$ satisfying the axioms
described in Section A.7, assuming $\mathcal{C}$ is closed.

$(\mathsf{id}^{A})$

The exponential $\mathsf{id}^{A}$ for any object $A$ of $\mathcal{C}$,
assuming the monoidal product on $\mathcal{C}$ is cartesian closed

($W$-types)

A polynomial endofunctor of a morphism $f:X\to Y$, given a point $y:*\to Y$ in
$\mathcal{C}$ and assuming that the monoidal structure on $\mathcal{C}$ is
locally cartesian closed

(d.e.s.)

A discrete equational system, assuming that the monoidal structure on
$\mathcal{C}$ is cocartesian and that $\mathcal{C}$ has binary products that
preserve filtered colimits.

On some occasions, the category of coalgebras of $F$ can be interesting while
its category of algebras is vacuous. For instance, given an alphabet $\Sigma$,
coalgebras over the endofunctor $F(X)=2\times X^{\Sigma}$ in ${\mathsf{Set}}$
are automata but the initial algebra remains $\emptyset$. To remedy this, we
can extend our main result into the following theorem.

######  Theorem 3.19 (Proof in Section A.6).

Suppose that $\mathcal{C}$ is locally presentable and closed and that $F$ is
also accessible. Let $G\colon\mathcal{C}\rightarrow\mathcal{C}$ be a
$\mathcal{C}$-enriched functor that is accessible. Then ${\mathsf{Alg}}_{GF}$
is enriched, tensored and powered over ${\mathsf{CoAlg}}_{F}$.

######  Example 3.20.

If $F(X)=2\times X^{\Sigma}$, we could consider $G=\mathsf{id}+1$, and thus
${\mathsf{Alg}}_{GF}$ has $\mathbb{N}$ as an initial object and remains
enriched in automata.

The enrichment of algebras in coalgebras specify a pairing of coalgebras

${\underline{\mathsf{Alg}}}(B,T)\otimes{\underline{\mathsf{Alg}}}(A,B)\longrightarrow{\underline{\mathsf{Alg}}}(A,T),$

regarded as a enriched composition, for any algebras $A$, $B$ and $T$. In more
details, the above coalgebra homomorphism is induced by the measuring of

${\big{(}{\underline{\mathsf{Alg}}}(B,T)\otimes{\underline{\mathsf{Alg}}}(A,B)\big{)}\otimes
A}$${{\underline{\mathsf{Alg}}}(B,T)\otimes
B}$${T.}$$\scriptstyle{\mathsf{id}\otimes\mathsf{ev}_{A,B}}$$\scriptstyle{\mathsf{ev}_{B,T}}$

In other words, the enrichment is recording precisely that we can compose a
measuring $C\otimes A\rightarrow B$ with $D\otimes B\rightarrow T$ to obtain a
measuring $(D\otimes C)\otimes A\rightarrow T$. In particular, our above
discussion shows that ${\underline{\mathsf{Alg}}}(A,A)$ is always a monoid
object in the symmetric monoidal category
$({\mathsf{CoAlg}},\otimes,\mathbb{I})$.

###  3.6 General $C$-initial objects

Now we follow Section 2.5. We can use the extra structure in the enriched
category of algebras to specify more algebras than we could in the unenriched
category of algebras.

######  Definition 3.21 ($C$-initial algebra, cf. Definition 2.8 and
Definition 2.11).

Suppose that $\mathcal{C}$ is locally presentable and closed and that $F$ is
accessible.

Given a coalgebra $C$, we say an algebra $A$ is a $C$-initial algebra if there
exists a unique map $C\rightarrow{\underline{\mathsf{Alg}}}(C,X)$, for all
algebras $X$.

The _terminal_ $C$-initial algebra is the terminal object, if it exists, in
the subcategory of ${\mathsf{Alg}}$ spanned by the $C$-initial algebras.

We end with a result that helped us calculate some terminal $C$-initial
algebras in Section 2.5.

######  Proposition 3.22 (Proof in Section A.8).

Suppose that $\mathcal{C}$ is locally presentable and closed and that $F$ is
accessible. There is a unique map from any $C$-initial algebra to $C^{*}$.

##  4 Conclusions & Vista

In this paper, we have shown that given a closed symmetric monoidal category
$\mathcal{C}$ and an accessible lax symmetric monoidal endofunctor $F$ on
$\mathcal{C}$, the category of algebras of $F$ is enriched, tensored, and
cotensored in the category of coalgebras of $F$. The algebras of such a
functor are of central importance in theoretical computer science, and we hope
that identifying such extra structure can shed light on these studies. Indeed,
we have demonstrated one use case: we can now specify $C$-initial algebras in
an analogous way to initial algebras. We identified a large class of examples
of endofunctors that are encompassed by our theory. Thus, we have established
the beginning of an _enriched_ analogue of the theory of $W$-types. We have
also worked out concretely the results for the endofunctor $\mathsf{id}+1$ on
${\mathsf{Set}}$, which suggested a meaningful interpretation of the
enrichment as partial algebra homomorphisms.

In future work, we will present similar meaningful interpretations for other
endofunctors of our theory. Our future plans involve incorporating features,
such as $C$-initial algebras, of this new enriched theory into concrete
programming languages like Haskell or Agda.

We also seek to extend the results of Example 2.14 into more general settings
and provide conditions for the existence of the terminal $C$-initial algebras.
We will also develop more robust theory from Theorem 3.19. Our partial algebra
homomorphisms remain total functions: it would be interesting to develop a
theory that encodes maps that are partial both as a function and as algebra
homomorphisms. Lastly in Example 3.18, when we considered the constant functor
at an object $A$, we must choose a commutative monoid structure on $A$. What
if we had two different monoidal structures on $A$? There are other such
choices that are needed in Example 3.18. We seek to understand how these
choices interact with one another.

## References

  * [1] Jiří Adámek and Hans-E. Porst.  On varieties and covarieties in a category.  volume 13, pages 201–232. 2003.  Coalgebraic methods in computer science (Genova, 2001).  doi:10.1017/S0960129502003882.
  * [2] Jiří Adámek and Jiří Rosický.  Locally presentable and accessible categories, volume 189 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 1994.  doi:10.1017/CBO9780511600579.
  * [3] Martin Hyland, Ignacio López Franco, and Christina Vasilakopoulou.  Hopf measuring comonoids and enrichment.  Proc. Lond. Math. Soc. (3), 115(5):1118–1148, 2017.  doi:10.1112/plms.12064.
  * [4] Jacob Lurie.  Higher topos theory, volume 170 of Annals of Mathematics Studies.  Princeton University Press, Princeton, NJ, 2009.  doi:10.1515/9781400830558.
  * [5] Per Martin-Löf.  Intuitionistic type theory.  Naples: Bibliopolis, 1984.
  * [6] Maximilien Péroux.  The coalgebraic enrichment of algebras in higher categories.  Journal of Pure and Applied Algebra, 226(3):106849, 2022.  doi:https://doi.org/10.1016/j.jpaa.2021.106849.
  * [7] Jan Rutten.  The Method of Coalgebra: exercises in coinduction.  C, 2019.  URL: https://ir.cwi.nl/pub/28550/.
  * [8] Moss E. Sweedler.  Hopf algebras.  Mathematics Lecture Note Series. W. A. Benjamin, Inc., New York, 1969\.
  * [9] Christina Vasilakopoulou.  Enriched duality in double categories: $\mathcal{V}$-categories and $\mathcal{V}$-cocategories.  J. Pure Appl. Algebra, 223(7):2889–2947, 2019.  doi:10.1016/j.jpaa.2018.10.003.
  * [10] D.N. Yetter.  Abelian categories of modules over a (lax) monoidal functor.  Advances in Mathematics, 174(2):266–309, 2003.  URL: https://www.sciencedirect.com/science/article/pii/S0001870802000415, doi:https://doi.org/10.1016/S0001-8708(02)00041-5.

##  Appendix A Appendix

###  A.1 Details for Section 2

######  Lemma A.1.

Consider two algebras $A,B$, and suppose that the canonical map $\mathbb{N}\to
A$ is an epimorphism. Then ${\underline{\mathsf{Alg}}}(A,B)$ is a subterminal
coalgebra, and it is the maximum subterminal coalgebra $C$ such that
${\mathsf{Alg}}(A,[C,B])$ is nonempty.

######  Proof A.2.

We first claim that ${\mathsf{Alg}}(A,[C,B])$ is empty or a singleton for any
coalgebra $C$. Since $!_{A}:\mathbb{N}\to A$ is an epimorphism, the function

${\mathsf{Alg}}(A,[C,B])\xrightarrow{!^{*}_{A}}{\mathsf{Alg}}(\mathbb{N},[C,B])$

is an injection, and since $\mathbb{N}$ is initial,
${\mathsf{Alg}}(\mathbb{N},[C,B])\cong*$. Thus, ${\mathsf{Alg}}(A,[C,B])$ is a
singleton, in the case where the only map $\mathbb{N}\to[C,B]$ factors through
$A$, and otherwise is empty.

We now claim that the canonical map
$\llbracket{-}\rrbracket:{\underline{\mathsf{Alg}}}(A,B)\to{\mathbb{N}^{\infty}}$
is a monomorphism. Suppose there are maps
$a,b:C\to{\underline{\mathsf{Alg}}}(A,B)$ from a coalgebra $C$ such that
$\llbracket{a}\rrbracket=\llbracket{b}\rrbracket$. Recall that the coalgebra
${\underline{\mathsf{Alg}}}(A,B)$ is defined by the following universal
property for any coalgebra $C$

${\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,B))\cong{\mathsf{Alg}}(A,[C,B]).$

Thus, ${\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,B))$ is a singleton, so
$a=b$, and $\llbracket{-}\rrbracket$ is monic.

######  Lemma A.3.

Consider a category $\mathcal{C}$, an endofunctor
$F:\mathcal{C}\to\mathcal{C}$, and an algebra $(A,\alpha)$ of $F$.

  1. 1.

Given a quotient object $Q$ of $A$ for which $\alpha$ restricts to a morphism
$\alpha_{Q}:FQ\to F$, the pair $(Q,\alpha_{Q})$ is a quotient object of
$(A,\alpha)$.

  2. 2.

If the forgetful functor $\mathsf{Alg}\to\mathcal{C}$ preserves epimorphisms,
then for every quotient object $(Q,\alpha_{Q})$ of $(A,\alpha)$, $Q$ is a
quotient object of $A$.

Thus, if the forgetful functor preserves epimorphisms, it underlies an
isomorphism between the poset of quotient algebras of $(A,\alpha_{A})$ and the
poset of quotient objects $Q$ of $A$ for which $\alpha$ restricts to a
morphism $\alpha_{Q}:FQ\to Q$.

######  Proof A.4.

Consider a a quotient object $Q$ of $A$ for which $\alpha$ restricts to a
morphism $\alpha_{Q}:FQ\to F$. Then $(Q,\alpha_{Q})$ is an algebra of $F$. The
quotient map $A\to Q$ underlies a total algebra homomorphism
$q:(A,\alpha)\to(Q,\alpha_{Q})$. Consider another algebra $(B,\beta)$ and two
maps $f,g:(Q,\alpha_{Q})\to(B,\beta)$ such that $fq=gq$. Then we find that the
underlying maps of $f$ and $g$ in $\mathcal{C}$ coincide, and thus $f=g$.

Suppose that the forgetful functor $\mathsf{Alg}\to\mathcal{C}$ preserves
pushouts. Then it preserves epimorphisms

######  Example A.5.

Consider the endofunctor $\mathsf{id}+1$ on ${\mathsf{Set}}$. This preserves
surjections, so there is an isomorphism between the poset of quotient algebras
of an algebra $(A,\alpha)$ and the poset of quotient sets $Q$ of $A$ for which
$\alpha$ restricts to a morphism $\alpha_{Q}:FQ\to Q$.

######  Definition A.6.

Consider a category $\mathcal{C}$ with a terminal object $*$, an endofunctor
$F:\mathcal{C}\to\mathcal{C}$, and suppose that the category of coalgebras of
$F$ has a terminal coalgebra ${\mathbb{N}^{\infty}}$.

Call a point $*\to{\mathbb{N}^{\infty}}$ an _index_. For any index $n$, let
${\mathsf{CoAlg}}^{n}$ denote the category whose objects are pairs
$((X,\chi_{X}),x)$ where $(X,\chi_{X})$ is a coalgebra and $x\in X$ such that
$\llbracket{x}\rrbracket=n$.

Say that a coalgebra is _freely generated by a point of index $n$_ if it is an
initial object in ${\mathsf{CoAlg}}^{n}$. Say that a coalgebra is _generated
by a point of index $n$_ if it is the vertex of a cone on the identity
endofunctor on ${\mathsf{CoAlg}}^{n}$.

######  Definition A.7.

Say that $F:\mathcal{C}\to\mathcal{C}$ is _well-equipped_ if $\mathcal{C}$ is
well-pointed and for every index $n$, there is a coalgebra generated by a
point of index $n$.

######  Lemma A.8.

Consider a category $\mathcal{C}$, an endofunctor $F$, and a coalgebra
$(C,\chi)$.

  1. 1.

Given a subobject $S$ of $C$ for which $\chi$ restricts to a morphism
$\chi_{S}:S\to FS$, the pair $(S,\chi_{S})$ is a subobject of $(C,\chi)$.

  2. 2.

If $F$ is well-equipped, for every subcoalgebra $(S,\chi_{S})$ of $c$, we have
that $S$ is a subobject of $C$.

Thus, if $F$ is well-equipped, there is an isomorphism between the poset of
subobjects of $(C,\chi_{C})$ and the poset of subobjects of $C$ for which
$\chi_{C}$ restricts to a morphism $\chi_{S}:FS\to S$.

######  Proof A.9.

Consider a subobject $S$ of $C$ for which $\chi_{C}$ restricts to a morphism
$\chi_{S}:S\to FS$. Then $(S,\chi_{S})$ is a coalgebra, and there is a total
algebra homomorphism $s:(S,\chi_{C})\to(C,\chi)$. Consider another coalgebra
$(D,\chi_{D})$ and two morphisms $f,g:(C,\chi)\to(D,\chi_{D})$ such that
$sf=sg$. Then the underlying morphisms of $f$ and $g$ coincide, so $f=g$.

Now suppose that $F$ is well-equipped. Consider a subcoalgebra
$\iota:(S,\chi_{S})\rightarrowtail(C,\chi)$, and two points $x,y:*\to S$ in
$\mathcal{C}$ such that $\iota x=\iota y$. Thus
$\llbracket{x}\rrbracket=\llbracket{\iota x}\rrbracket=\llbracket{\iota
y}\rrbracket=\llbracket{y}\rrbracket$, and let $((I,\chi_{I}),\top_{n})$
denote a coalgebra generated by a point of this index. Then we get two maps
$\overline{x},\overline{y}:(I,\chi_{I})\to(S,\chi_{S})$ and a map
$\overline{\iota x}=\overline{\iota y}:(I,\chi_{I})\to(C,\chi)$ such that
$\iota\overline{x}=\overline{\iota x}=\overline{\iota y}=\iota\overline{y}$.
Since $\iota$ is a monomorphism, $\overline{x}=\overline{y}$, but then
$x=\overline{x}\top_{n}=\overline{y}\top_{n}=y:*\to\mathcal{C}$.

######  Example A.10.

Consider the endofunctor $\mathsf{id}+1$ on ${\mathsf{Set}}$. The indices are
the elements of ${\mathbb{N}^{\infty}}$. The coalgebra ${\mathbb{n}^{\circ}}$
is freely generated by a point of index $n$ for finite $n$, and $\mathbb{I}$
is freely generated by a point of index $\infty$.

Thus there is an isomorphism between the poset of subcoalgebras of any
coalgebra $(C,\chi)$ and the poset of subsets $S$ of $C$ for which $\chi$
restricts to a morphism $\chi_{S}:FS\to S$.

###  A.2 Axioms for Definition 3.1

The triplet $(F,\nabla,\eta)$ must satisfy the following commutative diagrams.

Associative

For all objects $X,Y,Z\in\mathcal{C}$, we have

${F(X)\otimes F(Y)\otimes F(Z)}$${F(X\otimes Y)\otimes F(Z)}$${F(X)\otimes
F(Y\otimes Z)}$${F(X\otimes Y\otimes
Z).}$$\scriptstyle{\nabla_{X,Y}\otimes\mathsf{id}}$$\scriptstyle{\mathsf{id}\otimes\nabla_{Y,Z}}$$\scriptstyle{\nabla_{X\otimes
Y,Z}}$$\scriptstyle{\nabla_{X,Y\otimes Z}}$

Unital

For all objects $X\in\mathcal{C}$

${F(X)}$${\mathbb{I}\otimes F(X)}$${F(\mathbb{I})\otimes
F(X)}$${F(X)}$${F(X)\otimes\mathbb{I}}$${F(X)\otimes
F(\mathbb{I})}$${F(\mathbb{I}\otimes
X)}$${F(X\otimes\mathbb{I})}$${F(X)}$${F(X).}$$\scriptstyle{\cong}$$\scriptstyle{\eta\otimes\mathsf{id}}$$\scriptstyle{\nabla_{\mathbb{I},X}}$$\scriptstyle{\cong}$$\scriptstyle{\mathsf{id}\otimes\eta}$$\scriptstyle{\nabla_{X,\mathbb{I}}}$$\scriptstyle{\cong}$$\scriptstyle{\cong}$

Commutative

For all objects $X,Y\in\mathcal{C}$

${F(X)\otimes F(Y)}$${F(X\otimes Y)}$${F(Y)\otimes F(X)}$${F(Y\otimes
X),}$$\scriptstyle{\nabla_{X,Y}}$$\scriptstyle{\cong}$$\scriptstyle{\tau_{F(X),F(Y)}}$$\scriptstyle{F(\tau_{X,Y})}$$\scriptstyle{\cong}$$\scriptstyle{\nabla_{Y,X}}$

where $\tau_{X,Y}:X\otimes Y\rightarrow Y\otimes X$ is the symmetry natural
isomorphism in $\mathcal{C}$.

###  A.3 Proof of Theorem 3.10

######  Proof A.11.

By the cofree-forgetful adjunction, the coalgebra homomorphism
$\mathsf{eq}:{\underline{\mathsf{Alg}}}(A,B)\to\mathsf{Cof}\big{(}\underline{\mathcal{C}}(A,B)\big{)}$
determines a map
$\widetilde{\mathsf{ev}}:{\underline{\mathsf{Alg}}}(A,B)\rightarrow\underline{\mathcal{C}}(A,B)$
which must be a measuring. We verify it is the universal one. If
$\psi:C\rightarrow\underline{\mathcal{C}}(A,B)$ is a $C$-partial homomorphism,
then we obtain by the cofree-forgetful adjunction a coalgebra homomorphism
$C\rightarrow\mathsf{Cof}\big{(}\underline{\mathcal{C}}(A,B)\big{)}$ which
must equalize the two parallel homomorphisms. Thus by universal property of
equalizers there must exists a unique coalgebra homomorphism
$u_{\psi}:C\rightarrow{\underline{\mathsf{Alg}}}(A,B)$ such that the following
diagram commutes:

${C}$${{\underline{\mathsf{Alg}}}(A,B)}$${\underline{\mathcal{C}}(A,B).}$$\scriptstyle{u_{\psi}}$$\scriptstyle{\psi}$$\scriptstyle{\widetilde{\mathsf{ev}}}$

In other words, we have just shown that the universal property of the
equalizer $({\underline{\mathsf{Alg}}}(A,B),\mathsf{eq})$ is equivalent to the
universal measuring
$({\underline{\mathsf{Alg}}}(A,B);\widetilde{\mathsf{ev}})$ which corresponds
to the universal measuring $({\underline{\mathsf{Alg}}}(A,B);\mathsf{ev})$.

###  A.4 Proof of Proposition 3.15

We first need to check
$(C,\chi_{C})\otimes(\mathbb{I},\eta)\cong(C,\chi_{C})$. On objects, we have
$C\otimes\mathbb{I}\cong C$ as $\mathbb{I}$ is a monoidal unit. The
coalgebraic structures correspond as we have the following commutative diagram
by unitality of $(F,\nabla,\eta)$:

${C}$${C\otimes\mathbb{I}}$${F(C)}$${F(C)\otimes\mathbb{I}}$${F(C)\otimes
F(\mathbb{I})}$${F(C\otimes\mathbb{I})}$${F(C).}$$\scriptstyle{\cong}$$\scriptstyle{\chi}$$\scriptstyle{\chi\otimes\eta}$$\scriptstyle{\cong}$$\scriptstyle{\mathsf{id}\otimes\eta}$$\scriptstyle{\nabla}$$\scriptstyle{\cong}$

Similarly, we have a natural identification
$(\mathbb{I},\eta)\otimes(C,\chi_{C})\cong(C,\chi_{C})$ from the
identification $\mathbb{I}\otimes C\cong C$. Moreover, we also have natural
identifications:

$((C,\chi)\otimes(C^{\prime},\chi^{\prime}))\otimes(C^{\prime\prime},\chi^{\prime\prime})\cong(C,\chi)\otimes((C^{\prime},\chi^{\prime})\otimes(C^{\prime\prime},\chi^{\prime\prime})),$

lifted from $(C\otimes C^{\prime})\otimes C^{\prime\prime}\cong
C\otimes(C^{\prime}\otimes C^{\prime\prime})$. Lastly, the symmetry $C\otimes
C^{\prime}\cong C^{\prime}\otimes C$ lifts to ${\mathsf{CoAlg}}$. Therefore as
$\mathcal{C}$ is symmetric monoidal, the above natural identifications
assemble to a symmetric monoidal structure on ${\mathsf{CoAlg}}$ as the
pentagon, triangle, hexagon and symmetric identities remain valid in
${\mathsf{CoAlg}}$.

###  A.5 Proof of Theorem 3.17

######  Proof A.12.

The convolution algebra functor
$[-,-]:{\mathsf{CoAlg}}^{\mathsf{op}}\times{\mathsf{Alg}}\rightarrow{\mathsf{Alg}}$
presents ${\mathsf{Alg}}$ as a right module over
${\mathsf{CoAlg}}^{\mathsf{op}}$. Thus ${\mathsf{Alg}}^{\mathsf{op}}$ is a
left module over ${\mathsf{CoAlg}}$ via

$[-,-]^{\mathsf{op}}\colon{\mathsf{CoAlg}}\times{\mathsf{Alg}}^{\mathsf{op}}\rightarrow{\mathsf{Alg}}^{\mathsf{op}}.$

Moreover, for any $A\in{\mathsf{Alg}}$, the functor
$[-,B]^{\mathsf{op}}\colon{\mathsf{CoAlg}}\rightarrow{\mathsf{Alg}}^{\mathsf{op}}$
has a right adjoint
${\underline{\mathsf{Alg}}}(-,B):{\mathsf{Alg}}^{\mathsf{op}}\rightarrow{\mathsf{CoAlg}}$
as shown in Remark 3.13. Thus, by [3, 3.1], the category
${\mathsf{Alg}}^{\mathsf{op}}$ is enriched over ${\mathsf{CoAlg}}$ with tensor
$[-,-]^{\mathsf{op}}$. Therefore ${\mathsf{Alg}}$ is enriched over
${\mathsf{CoAlg}}$ with power $[-,-]$.

###  A.6 Details for Theorem 3.19

If $A$ is a $GF$-algebra, and $C$ is an $F$-coalgebra, then we obtain a
$GF$-algebra structure on $[C,A]=\underline{\mathcal{C}}(C,A)$ as follows.
Define
$GF\big{(}\underline{\mathcal{C}}(C,A)\big{)}\rightarrow\underline{\mathcal{C}}(C,A)$
as the adjunct of:

$GF\big{(}\underline{\mathcal{C}}(C,A)\big{)}\otimes C\rightarrow
GF\big{(}\underline{\mathcal{C}}(C,A)\big{)}\otimes F(C)\rightarrow
G\big{(}F(\underline{\mathcal{C}}(C,A))\otimes F(C)\big{)}\rightarrow
G(F(A))\rightarrow A.$

The first map is induced by the $F$-coalgebra structure $C\rightarrow F(C)$,
the last map is induced by the $GF$-structure $GFA\rightarrow A$. The
penultimate map is applying $G$ to the map
$F(\underline{\mathcal{C}}(C,A))\otimes F(C)\rightarrow F(A)$ induced by the
lax symmetric monoidal structure on $F$ and evaluation. The second map is
induced by the $\mathcal{C}$-enrichment of $G$ that produces a map
$G(X)\otimes Y\rightarrow G(X\otimes Y)$ for any objects $X$ and $Y$ in
$\mathcal{C}$. Indeed, this is the adjunct of:

$Y\rightarrow\underline{\mathcal{C}}(X,X\otimes
Y)\rightarrow\underline{\mathcal{C}}(G(X),G(X\otimes Y)),$

where the first map is the coevaluation of the internal hom, and the second
map is induced by the $\mathcal{C}$-enrichment.

###  A.7 Details for Example 3.18

######  Example A.13.

The following endofunctors on a locally presentable, symmetric monoidal
category $\mathcal{C}$ are always accessible and lax symmetric monoidal.

$(\mathsf{id})$

The identity endofunctor $\mathsf{id}_{\mathcal{C}}$ has a trivial lax
symmetric monoidal structure, and preserves filtered colimits.

$(A)$

Given a commutative monoid $(A,\eta,\nabla)\in\mathcal{C}$, the endofunctor
that sends each object to $A$ has a lax symmetric monoidal structure. Indeed,
$\iota$ and $\nabla$ are exactly the structure required for this functor to be
lax symmetric monoidal. This preserves filtered colimits.

$(GF)$

Suppose that $(F,\eta_{F},\nabla_{F})$ and $(G,\eta_{G},\nabla_{G})$ are lax
symmetric monoidal endofunctors on $\mathcal{C}$. Then so is the composition
$GF$. The map $\eta$ is the composition
$\mathbb{I}\xrightarrow{\eta_{G}}G(\mathbb{I})\xrightarrow{G\eta_{F}}GF(\mathbb{I})$.
The map $\nabla$ is the composition $GF(X)\otimes
GF(Y)\xrightarrow{\nabla_{G}}G(F(X)\otimes
F(Y))\xrightarrow{G\nabla_{F}}GF(X\otimes Y)$. If $F$ and $G$ both preserved
filtered colimits, then so does $GF$.

$(F\otimes G)$

Suppose that $\mathcal{C}$ is closed and that $(F,\eta_{F},\nabla_{F})$ and
$(G,\eta_{G},\nabla_{G})$ are lax symmetric monoidal endofunctors on
$\mathcal{C}$. Then so is $F\otimes G$. The map $\eta$ is the composition
$\mathbb{I}\to\mathbb{I}\otimes\mathbb{I}\xrightarrow{\eta_{F}\otimes\eta_{G}}(F\otimes
G)(\mathbb{I})$. The map $\nabla$ is the composition $(F\otimes
G)(X)\otimes(F\otimes G)(Y)\cong(FX\otimes FY)\otimes(GX\otimes
GY)\xrightarrow{\nabla_{F}\otimes\nabla_{G}}(F\otimes G)(X\otimes Y)$. If $F$
and $G$ are accessible, then so is $F\otimes G$ (because $\otimes$ preserves
colimits in each variable, as $\mathcal{C}$ is closed).

$(F+G)$

Suppose $\mathcal{C}$ is closed and that $(F,\eta_{F},\nabla_{F})$ is a lax
symmetric monoidal endofunctor, and consider a pair $(G,\nabla_{G})$ of an
endofunctor $G:\mathcal{C}\to\mathcal{C}$ and transformation $GX\otimes GY\to
G(X\otimes Y)$ which is associative and symmetric (i.e. a lax symmetric
monoidal endofunctor but without $\eta$), and suppose that $G$ is both a left
and right module over $F$, meaning that there are natural transformations
$\lambda:FX\otimes GY\to G(X\otimes Y)$ and $\rho:GX\otimes FY\to G(X\otimes
Y)$ satisfying the diagrams of [10, Def. 39], where the concept of module over
a monoidal functor is defined. Then $F+G$ is a lax symmetric monoidal functor.
We set $\eta$ to be the composition
$\mathbb{I}\xrightarrow{\eta_{F}}F(\mathbb{I})\rightarrow
F(\mathbb{I})+G(\mathbb{I})\cong(F+G)(\mathbb{I})$. The map $\nabla$ is given
by the following composition.

$\displaystyle(F+G)(X)\otimes(F+G)(Y)$ $\displaystyle\cong(FX\otimes
FY)+(FX\otimes GY)+(GX\otimes FY)+(GX\otimes GY)$
$\displaystyle\xrightarrow{\langle\nabla_{F},\lambda,\rho,\nabla_{G}\rangle}F(X\otimes
Y)+G(X\otimes Y)$ $\displaystyle\cong(F+G)(X\otimes Y)$

If $F$ and $G$ preserve filtered colimits, then so does $F+G$.

$(\mathsf{id}^{A})$

Suppose that $\mathcal{C}$ is cartesian (so we denote it
$(\mathcal{C},*,\times)$). Consider an exponentiable object $A$ of
$\mathcal{C}$, meaning that the functor $\mathsf{id}\times A$ has a right
adjoint, denoted $\mathsf{id}^{A}$. This has a lax symmetric monoidal
structure. We let $*\to*^{A}$ and $X^{A}\times Y^{A}\to(X\times Y)^{A}$ be the
isomorphisms we get from the fact that $-^{A}$, as a right adjoint, preserves
limits. It is accessible as a right adjoint.

($W$-types)

Suppose that the monoidal structure on $\mathcal{C}$ is not only cartesian (so
that we write it as $(\mathcal{C},*,\times)$) but also locally cartesian
closed. Consider a morphism $f:A\to C$ in $\mathcal{C}$ and a point $c:*\to
C$. We consider the symmetric, cartesian monoidal categories
$(\mathcal{C}/A,A,\times_{A})$ and $(\mathcal{C}/C,C,\times_{C})$ where
$\mathcal{C}/A$ and $\mathcal{C}/C$ denote the slice categories. The universal
properties of the product, pullback, and local exponentiation give
$A^{*}:=A\times-:\mathcal{C}\to\mathcal{C}/A$ and
$\Pi_{f}:\mathcal{C}/A\to\mathcal{C}/C$ (where $\Pi_{f}$ denotes the local
exponential along $f$) the structure of a lax symmetric monoidal functor. To
see $\Sigma_{C}:=\mathsf{dom}:\mathcal{C}/C\to\mathcal{C}$ as lax symmetric
monoidal, we use the point $c:*\to C$ as $\eta$ and $\nabla$ is given by the
universal property of the pullback and product. Then the composition
$\Sigma_{C}\Pi_{f}A^{*}:\mathcal{C}\to\mathcal{C}$ is lax symmetric monoidal,
and it is accessible since it is the composition of left and right adjoints.

(d.e.s.)

Suppose that the monoidal structure on $\mathcal{C}$ is cocartesian, so we
denote it by $(\mathcal{C},0,+)$, and suppose also that $\mathcal{C}$ also has
binary products that preserve filtered colimits in each variable. Consider a
discrete equational system on $\mathcal{C}$, that is, a pair $(A,M)$ where $A$
is a set and $M$ is an object of $\mathcal{C}^{A\times A}$. The functor
category $\mathcal{C}^{A}$ inherits a cocartesian monoidal structure
$(\mathcal{C}^{A},0,+)$ pointwise. Define an endofunctor
$M\otimes-:\mathcal{C}^{A}\to\mathcal{C}^{A}$ by setting

$(M\otimes X)_{a}:=\sum_{b\in A}M_{b,a}\times X_{b}.$

This is lax symmetric monoidal. The morphisms $\eta:0\to M\otimes 0$ and
$\nabla:M\otimes(X+Y)\to M\otimes X+M\otimes Y$ are induced by the universal
properties of $0$ and $+$. It is also accessible since the coproducts and
binary products preserve filtered colimits.

###  A.8 Details for Proposition 3.22

We consider an object $\mathsf{lim}^{C}\mathsf{id}_{\underline{\mathsf{Alg}}}$
with the following universal property (if it exists).

${\mathsf{Alg}}(A,\mathsf{lim}^{C}\mathsf{id}_{\underline{\mathsf{Alg}}})\cong\mathsf{lim}_{X\in{\mathsf{Alg}}}\
{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,X))$

Since ${\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,-))$ preserves limits
and $\mathsf{lim}_{X\in{\mathsf{Alg}}}X\cong\mathbb{N}$, we have

$\displaystyle\mathsf{lim}_{X\in{\mathsf{Alg}}}\
{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,X))$
$\displaystyle\cong{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,\mathsf{lim}_{X\in{\mathsf{Alg}}}X))$
$\displaystyle\cong{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,\mathbb{N}))$
$\displaystyle\cong{\mathsf{Alg}}(A,[C,\mathbb{N}])$
$\displaystyle={\mathsf{Alg}}(A,C^{*})$

Thus, $C^{*}$ has the universal property of
$\mathsf{lim}^{C}\mathsf{id}_{\underline{\mathsf{Alg}}}$.

Now note that for a $C$-initial algebra $A$, we have
$\mathsf{lim}_{X\in{\mathsf{Alg}}}\
{\mathsf{CoAlg}}(C,{\underline{\mathsf{Alg}}}(A,X))\cong 1$. Thus, by this
universal property of $C^{*}$, there is a unique map $A\to C^{*}$.