We advance the program of connections between final coalgebras as sources of circularity in mathematics
and fractal sets of real numbers.  In particular, we are interested in the
Sierpinski carpet, taking it as a fractal subset of the unit square.  We construct a
category of square metric spaces and an endofunctor on it which corresponds to the
operation of gluing copies of a square set along segments.   We show that the initial
algebra and final coalgebra exists for our functor, and that the final coalgebra is
bilipschitz equivalent to the Sierpinski carpet.  Along the way, we make connections
to topics such as the iterative construction of initial algebras as $\omega$-colimits,
corecursive algebras, and the classic treatment of fractal sets
due to Hutchinson [7].

§ INTRODUCTION

This paper continues work on fractal sets modeled as final coalgebras.
It  builds on a line of work that
began with Freyd's result [4] that the unit interval $[0,1]$
is the final coalgebra of a certain endofunctor on the category of bi-pointed sets.
Leinster's paper [8] is a far-reaching generalization of Freyd's result.
represents many of what would be intuitively
called self-similar spaces using (a) bimodules (also called profunctors or distributors);
(b) an examination of non-degeneracy conditions on functors of various sorts; (c) a construction of
final coalgebras for the types of functors of interest using a notion of resolution.    In addition to the
characterization of fractal sets as sets, his seminal paper also characterizes them as topological spaces.

In a somewhat different direction, work related to Freyd's
Theorem continues with development of tri-pointed sets [3, 2] and the proof  that the
Sierpinski gasket $\mathbb{SG}$ is related to the final coalgebra of a functor modeled on that of Freyd [4].
Although it might seem that this result is but a special case of the much better results in  Leinster [8],
the work on tri-pointed sets was carried out in the setting of metric spaces rather than topological spaces
(and so it re-proved Freyd's result in that setting, too).   Work in the metric setting is unfortunately more
complicated.   It originates  in Hasuo, Jacobs, and Niqui [6], a paper which
emphasized algebras in addition to coalgebras, and proposed
endofunctors defined using quotient metrics.
Following this [3, 2] show
that for the unit interval,
the initial algebra of Freyd's functor is also interesting, being the metric space of dyadic rationals,
and thus the unit interval itself is its Cauchy completion.  For the  Sierpinski gasket, the initial algebra
of the functor on tripointed sets is
connected to the finite addresses used in building the gasket as a fractal; its completion again
turns out to be the final coalgebra;
and while the gasket itself is not the final coalgebra, the two metric spaces are bilipschitz isomorphic.

In this paper, we take the next step in this area by considering the Sierpinski carpet $\SC$.
The difference between this and the gasket (or the unit interval) is that the gluing of spaces needed to define the functor
involves gluing along line segments, not just along points.
This turns out to complicate matters at every step.   The main results of the paper are analogs of what we saw for the
gasket:  we have a category of metric spaces that we call square metric spaces, an endofunctor $M\otimes -$ which
takes a space to 8 scaled copies of itself glued along segments
(the notation recalls Leinster's paper, and again we are in the metric setting), a proof that the initial algebra and final coalgebra
exist, and that the latter is the completion of the former, and a verification that the actual Sierpinski carpet $\SC$
is bilipschitz isomorphic to the final coalgebra.   Along the way, we need to consider a different functor
$N\otimes -$
which is like $M\otimes-$ but involves 9 copies (no “hole”).
coalgebra $N\otimes-$
turns out to be the unit square with the taxicab metric.   Moreover, in much of this work we have found it convenient to
work with corecursive algebras as a stepping stone to the final coalgebra; the unit square
with the taxicab metric
turns out to be a corecursive
algebra for $N\otimes -$ on square metric spaces.
The Sierpinski carpet  $\SC$ turns out to be a
corecursive algebra
for the endofunctor $M\otimes -$, but it is not a final coalgebra itself.

§.§ Outline

The paper begins with a discussion of the
Sierpinski carpet $\SC$ in classical terms, reviewing the
results from Hutchinson [7] that we need.
What we need most is that $\SC$ is the fixed point of certain
contractive map $\sigma$ on the space of non-empty subsets of the unit square.
The first leading idea in the paper is that the action of $\sigma$ can
be generalized to give an endofunctor
on a category $\C$.  But it is not
immediate what that $\C$ and $F$ are.
The category $\C$ is defined in
Section <ref>; we call it the category
$\SquaMS$ of square metric spaces,
and the functor $F$ in
Section <ref> is  written $X\mapsto M\otimes X$.
The second leading idea is that $\SC$  should be related to the
final coalgebra of $M\otimes-$. We have the intuition that this should
be so from previous work on the unit interval [5]
and the Sierpinski triangle [3], and from the general
treatment of self-similar sets [8].  However,
as we remarked above, this paper
involves a
great deal more work than in those earlier works; we are not giving
a straightforward generalization of them.
For example, Section <ref> constructs the initial
algebra of $M\otimes-$, and this already is more difficult than in
previous work because the morphisms of the inital chain of $M\otimes-$ are not
isometric embeddings.  Still, $M\otimes-$ does have an initial algebra, and its
completion is the final coalgebra of this functor.
This and other results are
proved in Section <ref>.
We find it useful to bring in the concept of a corecursive algebra in
this discussion, and so the results of that section should be of independent
The paper ends in Section <ref> with
a proof that $\SC$ is bilipschitz equivalent to the final coalgebra of
the functor.
It would have been nice if $\SC$ turned out to be exactly the
final coalgebra.   An analogous result holds for the unit interval
(it is the completion of the unit interval)
but not for the Sierpinski triangle (again, we have bilipschitz equivalence).

The paper as a whole contains a mixture of geometric ideas that crop up
in the study of square metric spaces and our functor $M\otimes-$,
and also very general facts about colimits of chains in various categories
and facts about corecursive algebras.  We hope that readers interested in
one or the other of these kinds of work will come away from our paper with
interest in the other kind, and that the mixture of ideas here will be useful
in the category-theoretic treatment of other fractal sets.

§ THE SIERPINSKI CARPET

The main object of interest in this paper is the Sierpinski Carpet.

\[	\includegraphics[scale=0.12]{Sierpinski_carpet.png}
\]

We will begin by recalling the definition of the Sierpinski carpet $\SC$ (shown above) in terms of contractions of the unit square $U_0$, as in Hutchinson's work [7].

§.§ Review of  Hutchinson's Theorem

Let $(X,d)$ be a complete metric space, and let $\CC$ be the set of non-empty closed subsets of $X$,
with the Hausdorff metric $d_H$.   Let
be a finite index set and suppose for each $m\in M$, we have $\sigma_m \colon X \to X$, a contracting map.   Then the setwise extension of $\sigma_m$ is
defined by taking images: for $A\subseteq X$, $\sigma_m(A) = \set{\sigma_m(x) : x\in A}$.  This $\sigma_m$ is a contraction of $(\CC, d_{H})$.
Moreover, we define $\sigma \colon \CC\to\CC$ by

\[ \sigma(A) = \displaystyle{\bigcup_{m\in M}} \sigma_m(A)\]

Again $\sigma$ is a contracting map, and we let $K$ be its unique fixed point.
$K$ is called the invariant set determined by $\sigma_m$ for $m\in M$.

For each finite sequence $\vec{m} = m_1 m_2 \cdots m _k$ of elements of $M$, and each $A\in\CC$, $A_{\vec{m}}$ is
defined by recursion on $k$, starting with $k = 0$ and the empty sequence $\eps$:

\[
\begin{array}{lcl}
A_{\eps} & = & A \\
A_{m_1 m_2 \cdots m _k m_{k+1}} & = &   \sigma_{m_{1}}( A_{m_2 m_3 \cdots m _{k+1} })\end{array}
\]

We have the following facts about the invariant set $K$:

* For every infinite sequence $\overline{m} = m_1,m_2,\ldots, m_p, \ldots$ in $M$,

\begin{equation}\label{decrease}
K_{\eps} \supseteq K_{m_1} \supseteq K_{m_1 m_2} \supseteq \cdots \supseteq K_{m_1 m_2\cdots m_p} \supseteq \cdots
\end{equation}

and $\displaystyle{\bigcap_{p=1}^\infty}K_{m_1\ldots m_p}$ is a singleton whose member is denoted $k_{\overline{m}}$.  $K$ is the union of these singletons.

* If $A$ is a non-empty bounded set, then $diam(A_{m_1\ldots m_P})\rightarrow 0$ as $p\rightarrow\infty$.

*  If $A$ is a non-empty bounded set, then $d(A_{m_1\ldots m_p},k_{\overline{m}} )\rightarrow 0$ as $p\rightarrow\infty$.  In particular, $\sigma^p(A)\rightarrow K$ as $p\rightarrow\infty$ in the Hausdorff metric.

* Since $K$ is invariant, for any $p\geq 0$ we get

\[
\begin{array}{rcl}
K & = & \sigma(K) \\
& = & \displaystyle{\bigcup_{m_p\in M}} \sigma_{m_p}(K)\\
& = & \displaystyle{\bigcup_{m_p\in M}} K_{m_p}\\
& = & \sigma(\displaystyle{\bigcup_{m_p\in M}} K_{m_p})\\
& = & \displaystyle{\bigcup_{m_{p-1},m_p\in M}} \sigma_{m_{p-1}} (K_{m_p})\\
& = & \displaystyle{\bigcup_{m_{p-1},m_p\in M}} K_{m_{p-1}m_p}\\
& \vdots & \\
& = & \displaystyle{\bigcup_{m_1,\ldots,m_p\in M}} K_{m_1\ldots m_p}\\
\end{array}
\]

\[
\begin{array}{rcl}
K_{m_1\ldots m_p} & = & \sigma_{m_1}\circ\ldots \circ \sigma_{m_p}(K) \\
& = & \sigma_{m_1}\circ \ldots\circ \sigma_{m_p}\circ \sigma(K)\\
& = & \sigma_{m_1}\circ \ldots \circ \sigma_{m_p}(\displaystyle{\bigcup_{m_{p+1}\in M}} \sigma_{m_{p+1}}(K))\\
& = & \displaystyle{\bigcup_{m_{p+1}\in M}}\sigma_{m_1}\circ \ldots\circ  \sigma_{m_p}\circ \sigma_{m_{p+1}}(K)\\
& = & \displaystyle{\bigcup_{m_{p+1}\in M}} K_{m_1\ldots m_pm_{p+1}}\\
\end{array}
\]

So $K_{m_1\ldots m_p}\supset K_{m_1\ldots m_pm_{p+1}}$ and for any $x\in K$, we can find $\overline{m} = m_1,m_2,\ldots \in M$ such that $x\in K_{\overline{m}}$.

Since each $\sigma_m$ is a contraction and there are finitely many of them, $diam(K_{m_1\ldots m_p})\rightarrow 0$ as $p\rightarrow\infty$, and since $X$ is complete, the intersection is non-empty, so it must be a singleton.

* Let $A$ be a non-empty bounded set.  Then for $m\in M$, let $r_m<1$ be such that $d(x,y) \geq r_m d(\sigma_m(x),\sigma_m(y))$ and let $r = \displaystyle{\max_{m\in M}}\ r_m$.
$\mbox{diam}(A_{m_1\ldots m_p}) \leq r^p\ \mbox{diam}(A)$, which approaches $0$ as $p\rightarrow\infty$.

* Suppose $A$ is non-empty and bounded.
Let $m_1,\ldots,m_p\in M$.  For $m\in M$, let $r_m<1$ be such that $d(\sigma_{m}(x),\sigma_{m}(y)) \leq r_m d(x,y)$ for $x,y\in X$.

\[
\begin{array}{rcl}
d(A_{m_1\ldots m_p},k_{\overline{m}}) & = & d(\sigma_{m_1}\circ \ldots\circ \sigma_{m_p}(A),\sigma_{m_1}\circ\ldots\circ \sigma_{m_p}(k_{m_{p+1\ldots}})\\
& \leq & r_{m_1}\cdot \ldots \cdot r_{m_p}d(A, k_{m_{p+1}\ldots}) \\
& \leq & r_{m_1}\cdot\ldots\cdot r_{m_p} \sup \{d(a,b): a\in A,b\in K\} \\

& \leq & C(\displaystyle{\max_{m\in M}}\ r_m)^p\\
\end{array}
\]

where $C = \sup \{d(a,b): a\in A,b\in K\}$, which is constant with respect to $p$.
Since $r_m <1$ for all $m\in M$  and $M$ is finite, this goes to $0$ as $p\rightarrow\infty$, as required.

§.§ The Sierpinski Carpet

Now we apply the general results in the last section to define the Sierpinski Carpet $\mathbb{S}$ as a subset of $U_0 = [0,1]^2$.  Throughout this paper, we will be working with $(U_0,d_{\Taxicab})$, where
\[d_{\Taxicab}((x,y),(x_1,y_1)) = |x-x_1|+|y-y_1|\]
is the taxicab metric.

Most typically, we would view $\SC$ as a subset of $U_0$ with the Euclidean metric, $d_{\Euc}$. However, we will see that we can use the taxicab metric in our characterization of $\SC$.

Two metric spaces $A$ and $B$ are bilipschitz equivalent if there
is a bijection $f: A\to B$ and a number $K\geq 1$ such that

\[  \frac{1}{K}d_A(x,y) \leq d_B(f(x),f(y)) \leq K d_A(x,y) \]

for all $x,y\in A$.

$(U_0,d_{\Taxicab})$ is bilipschitz equivalent to $(U_0, d_{\Euc})$.

Our bijection will be the identity map.  Let $K = 2$ and let $(x,y),(x_1,y_1)\in U_0$.  Then

\[\begin{array}{rclc}
\frac{1}{2}d_{\Euc}((x,y),(x_1,y_1))& \leq &
\frac{1}{2}(d_{\Euc}((x,y),(x_1,y)) + d_{\Euc}((x_1,y),(x_1,y_1)) \\
& = & \frac{1}{2}(|x-x_1|+|y-y_1|)  \\
& \leq & d_{\Taxicab}((x,y),(x_1,y_1))  \\
& = & |x-x_1| + |y-y_1|  \\
& = & \sqrt{(x-x_1)^2} + \sqrt{(y-y_1)^2}  \\
&\leq & \sqrt{(x-x_1)^2+(y-y_1)^2} + \sqrt{(x-x_1)^2+(y-y_1)^2}  \\
& = & 2d_{\Euc}((x,y),(x_1,y_1))  \\
\end{array}
\]

$C\subset U_0$ is a closed set with respect to $d_{\Taxicab}$ if and only if it is a closed set with respect to $d_{\Euc}$.

Let $\mathcal{C}$ denote the collection of non-empty closed subsets of $U_0$ (with respect to either metric).
In order to apply Hutchinson's work to define $\SC$, we need to understand the Hausdorff metric on closed sets:

\[d_{He} = \max(\displaystyle{\sup_{a\in A}}\  d_{\Euc}(a,B),\displaystyle{\sup_{b\in B}}\  d_{\Euc}(A,b))\]

\[d_{Ht} = \max(\displaystyle{\sup_{a\in A}} \ d_{\Taxicab}(a,B),\displaystyle{\sup_{b\in B}} \ d_{\Taxicab}(A,b)).\]

$(\mathcal{C},d_{He})$ is bilipschitz equivalent to $(\mathcal{C}, d_{Ht})$.

This follows from Proposition <ref>

\[
\begin{array}{rcl}
\frac{1}{2} d_{He}(A,B) & = &   \frac{1}{2} \max(\displaystyle{\sup_{a\in A}}\  d_{\Euc}(a,B),\displaystyle{\sup_{b\in B}}\ d_{\Euc}(A,b)) \\
& = & \max(\displaystyle{\sup_{a\in A}}\  \frac{1}{2} d_{\Euc}(a,B),\displaystyle{\sup_{b\in B}}\  \frac{1}{2} d_{\Euc}(A,b))\\
& \leq & \max(\displaystyle{\sup_{a\in A}}\  d_{\Taxicab}(a,B),\displaystyle{\sup_{b\in B}}\  d_{\Taxicab}(A,b))\\
& = & d_{Ht}(A,B)\\
\end{array}
\]

and similarly, $d_{Ht}(A,B) \leq 2d_{He}(A,B)$.

So from here on, we will consider $(U_0,d_{\Taxicab})$ and define $\mathbb{S}$ as a subset of $U_0$ with respect to the taxicab metric.

For the remainder of the section, we may write $d_{U_0}$ or simply $d$ to denote $d_{\Taxicab}$.

$M$ is $\set{0,1,2}^2\setminus\set{(1,1)}$.
For each $m\in M$, let $\sigma_m\colon \CC\to \CC$ be

\[
A \subseteq U_0  \mapsto \shrink(m) + \frac{1}{3}(A)
\]

Following what we have done,
let $\sigma\colon\CC \to \CC$ be $\sigma(A) = \displaystyle{\bigcup_{m\in M}} \sigma_m(A)$.

Since we are scaling by a factor of $\frac{1}{3}$, it is routine to verify that $\sigma$ is a contraction on $\CC$ with respect to $d_{Ht}$.  Indeed, it easy to verify that it is also a contracting map with respect to $d_{He}$.

The Sierpinski carpet $\SC$ is the unique fixed point of $\sigma\colon\CC \to \CC$.
That is, it is the unique non-empty compact (with respect to $d_{\Taxicab}$) subset of $U_0$  fixed by $\sigma$.

When we consider $\SC$ as a metric space, we primarily take the metric to be
the one inherited from $(U_0,d_{\Taxicab})$.  For example, the distance between
$(0,0)$ and $(1,1)$ is $2$.
But because they are bilipschitz equivalent, if we had defined $\SC$ with respect to the Euclidean metric, we
would get the exact same set.

Indeed, $\SC$ the unique non-empty compact (with respect to either metric) subset of $\mathbb{R}^2$ fixed by $\sigma$.
But this is not relevant for us, and we prefer to work with subsets of
the unit square $U_0$.

§ THE CATEGORY OF SQUARE METRIC SPACES

We start by defining $\SquaMS$, the category of Square Metric spaces.  Though some of the arguments in the following sections will apply to a broader class of categories, our work will primarily focus on this category.  Our goal is to find a functor $F$ on this category and an $F$-coalgebra which is bilipschitz equivalent to the Sierpinski Carpet.

\[M_0=\{(r,s): r\in \{0,1\}, s\in [0,1]\}\cup\{(r,s):r\in [0,1], s\in \{0,1\}\}\]

be the boundary of the unit square.

A square set is a set $X$ with with an injective map $S_X:M_0\rightarrow X$.  The idea is that $S_X$ designates the $4$ sides of the square.

Examples of Square Sets:

* $M_0$ with $S_{M_0} = id$.

* $X=[0,1]^2$ where $S_X$ is the inclusion map.

* Sierpinski Carpet where $S_X$ is the inclusion map.

We are interested in square sets which are metric spaces.  $(X,S_X)$ is a square metric space if $X$ is a metric space bounded by $2$, and the boundary indicated by $S_X$ satisfies the following:

($\sqone$) For $i\in \{0,1\}$ and $r,s\in [0,1]$,
$$d_X(S_X((i,r)),S_X((i,s))) = |s-r|$$
$$d_X(S_X((r,i)),S_X((s,i))) = |s-r|.$$
That is, along each side of the square, distances coincide with distances on the unit interval.

($\sqtwo$) For $(r,s),(t,u)\in M_0$, $d_X(S_X((r,s)),S_X((t,u)))\geq |r-t|+|s-u|$.  This is a non-degeneracy requirement, which prevents our squares from “collapsing”.

Note that we do not require that the metric on the
boundary of the square coincides with the Euclidean metric (we are not requiring that opposite corners have distance $\sqrt{2}$).  In fact, we will be interested in a path metric around the square. That is, we will determine the distance between points by the shortest path around the square (described in more detail below).

Examples of Square Metric Spaces:

* $(M_0, id)$ with the path metric: for $x,y\in M_0$, if they are on the same side, their distance coincides with the unit interval, if they are on adjacent sides which share a corner $C$, $d(x,y) = d(x,C)+d(C,y)$, and if they are on opposite sides, $d(x,y)$ is the minimum (between the two sides) of $d(x,C_1)+1+d(C_2,y)$ where $C_1,C_2$ are endpoints of a side not containing either $x$ or $y$, with $C_1$ on the side containing $x$ and $C_2$ on the side containing $y$.  Note that these distances are all bounded by $2$ (the distance between opposite corners is $2$).

* $(M_0, id)$ with the taxicab metric.

* $([0,1]^2, S)$ where $S$ is the inclusion map, with the taxicab metric.

Let $\SquaMS$ be the category whose objects are square metric spaces (bounded by $2$) whose morphisms are short maps which preserve $S$.  That is, $f:(X,S_X)\rightarrow (Y,S_Y)$ which are maps such that for $x,y\in X$, $d_X(x,y)\geq d_Y(f(x),f(y))$ and for $(r,s)\in M_0$, $f(S_X((r,s))) = S_Y((r,s))$.

$(M_0,id)$ with the path metric is an initial object in $\SquaMS$.

Let $(X,S_X)$ be an object in $\SquaMS$.  Define $f:M_0\rightarrow X$ by $S_X$.  To see that $f$ is a morphism, since it clearly preserves $S_{M_0}$, we just need to check $f$ is a short map.  Let $x,y\in M_0$.  So $f(x) = S_X(x)$ and $f(y)= S_X(y)$.  If $x$ and $y$ are on the same side of $M_0$, then $d_X(f(x),f(y)) = d_X(S_X(x),S_X(y)) = d_{M_0}(x,y)$, since the distance coincides with the distance on the unit interval.

If $x$ and $y$ are on adjacent sides, let $C$ be the corner between them.  Then $d_X(f(x),f(y)) = d_X(S_X(x),S_X(y)) \leq d_X(S_X(x),S_X(C))+d_X(S_X(C),S_X(y)) = d_{M_0}(x,C)+d_{M_0}(C,y) = d_{M_0}(x,y)$.
We used the triangle inequality in  $(X,S_X)$.

Finally, suppose $x$ and $y$ are on opposite sides and let $C_1,C_2$ be the endpoints of the side which provides the shortest path from $x$ to $y$ in $M_0$.  Then

\[\begin{array}{lcl}
& = & d_X(S_X(x),S_X(y))\\
& \leq & d_X(S_X(x),S_X(C_1))+
d_X(S_X(C_1),S_X(C_2)) + d_X(S_X(C_2),S_X(y))\\
& = &  d_{M_0}(x,C_1) + 1 + d_{M_0}(C_2,y)  \\
&= & d_{M_0}(x,y)
\end{array}
\]

So, since $f$ is a short map and it is the unique map which preserves $S_{M_0}$, $(M_0,id)$ with the path metric is an initial object in $\SquaMS$.

We will find that the concrete description of the requirements on objects in $\SquaMS$ (($\sqone$) and ($\sqtwo$)) is useful for our purposes, but alternatively we can view the relationship between $X$ and $M_0$ as follows:

For every square metric space $(X, S_X)$ and every $(r,s),(t,u)\in M_0$,

\[ d_X(S_X((r,s)),S_X((t,u))) \leq d_{M_0}((r,s),(t,u)),\]
where $d_{M_0}$ is the path metric.

Follows from the fact that there is a (unique) short map $f:M_0\rightarrow X$ such that $f((r,s)) = S_X((r,s))$.

Monomorphisms in $\SquaMS$ are
the morphisms which are one-to-one.

Let $f:X\rightarrow Y$ be a monomorphism.  Let $Z = M_0\cup\{z\}$ be the boundary of the unit square with the path metric and one extra point $z$ such that $d_Z(z,(r,s)) = 2$ for all $(r,s)\in M_0$.  This is an object in $\SquaMS$.  Let $x_0,x_1\in X$ and suppose $f(x_0) = f(x_1)$.  Define $g_i:Z\rightarrow X$ by $(r,s)\mapsto S_X((r,s))$ for $(r,s)\in M_0$ and $z\mapsto x_i$ for $i=0,1$.  These clearly preserve $S_Z$, and are short maps since $d_X(g_i((r,s)),g_i((t,u)))\leq d_Z((S_Z((r,s)),S_Z((t,u)))$ for $(r,s),(t,u)\in M_0$ by the same argument as the previous proposition, and $d_X(g_i(z),g_i((r,s))) \leq 2 = d_Z(z,(r,s))$ for $(r,s)\in M_0$.  $f\circ g_0 = f\circ g_1$, since $f(g_i((r,s))) = S_Y((r,s))$, and $f(g_0(z)) = f(x_0)=f(x_1) = f(g_1(z))$.  So since $f$ is a monomorphism, $g_1 = g_2$, which means that $x_0 = g_0(z) = g_1(z)= x_1$.

For the other direction, suppose $f$ is an injective morphism and $g_0,g_1:Z\rightarrow X$ are morphisms from and arbitrary object $Z$  such that $f\circ g_0 = f\circ g_1$.  Then for $z\in Z$, $f(g_0(z)) = f(g_1(z))$, so since $f$ is injective, $g_0(z) =g_1(z)$.  Hence, $g_0=g_1$.

$\SquaMS$ has no final object.

As in the previous proposition, let $Z$ be the boundary of the unit square, $M_0$, with the path metric and a single point $z$ defined to be distance $2$ from every point in $M_0$.  This is an object in $\SquaMS$, via the inclusion $M_0 \rightarrow Z$.

Let $Y$ be an object in the category.
Then consider $f_0: Z\rightarrow Y$ defined by $(r,s)\mapsto S_Y((r,s))$ for $(r,s)\in M_0$ and $z\mapsto S_Y((0,0))$, and $f_1:Z\rightarrow Y$ defined by $(r,s)\mapsto S_Y((r,s))$ for $(r,s)\in M_0$ and $z\mapsto S_Y((1,1))$.
As in the previous proposition, these maps are both morphisms.
So since there are two distinct morphims from $Z$ to $Y$, $Y$ cannot be a final object in $\SquaMS$.

§ DEFINING THE FUNCTOR $M\OTIMES -$

In this section we will define a functor

\[ M\otimes- : \SquaMS\to \SquaMS
\]
which, when applied to the initial square metric space $M_0$,
will give us objects which correspond to iterations of the Sierpinski Carpet.  The idea is that $M$ will be a set of indices indicating positions to place scaled copies of $X$, and by showing that $M\otimes -$ is a functor, we will be able to apply it repeatedly in order to form a chain whose colimit will be an object whose completion is bilipschitz equivalent to the Sierpinski Carpet.
We will also define $N\otimes-$, an analogous map in which the center “hole” is filled in.  This will behave similarly to $M\otimes-$ and be useful later on to obtain the desired results about $M\otimes-$.

§.§ A General Discussion of The Quotient Metric on $M\otimes -$

In the first section, we work at a level of generality such that we can apply these results to functors $M\otimes-$ and $N\otimes -$, defined in the subsequent sections.

We will discuss the behavior of the quotient metric, which is how we will view $M\otimes X$ and $N\otimes X$, where $X$ is an object in $\SquaMS$, as metric spaces. We will give requirements on $M$ which will guarantee that $M\otimes X$ is a metric space, among other things.

We will do this work for the category $\SquaMS$, though it should be noted that the results of this section can be adapted to apply to a broad collection of categories, such as the  bipointed or tripointed metric spaces in [4, 3], where $S_X:\{\top,\perp\}\rightarrow X$ and $S_X:\{T,L,R\}\rightarrow X$ respectively.

Let $M$ be a finite collection of
indices.  The idea is that these will indicate positions in which we will place scaled copies of $X$.

Let $E$ be an equivalence relation on $M\times M_0$. Given an
object $X$, the pairs in $E$ will identify places where we glue copies of   $X$ by a procedure which we will specify
shortly.    Of course, the set $E$ is independent of $X$.

For a fixed object $X$ in $\SquaMS$, define a relation $\approx$ on $M\times X$ as follows: For $m,n\in M$ and $(r,s), (t,u)\in M_0$,

\begin{equation}\label{extendE}
\mbox{$(m,S_X((r,s))) \approx (n,S_X((t,u)))$ if and only if $((m,(r,s)),(n,(t,u)))\in E$.}
\end{equation}

Let $\sim$ be the symmetric, reflexive, and transitive closure of
$\approx$ on $M\times X$.  Note that if $(m,x)\neq (n,y)$ and $(m,x)\sim (n,y)$, then it must be the case that $x$ and $y$ are in the image of $M_0$ under $S_X$.

An equivalence relation $E$ on $M\times M_0$ is quotient suitable if for every object $X$ in $\SquaMS$

* If $((m,(r,s)),(n,(r',s'))),((m,(t,u)),(n,(t',u')))\in E$ then
$d_X(S_X((r,s)), S_X((t,u))) = d_X(S_X((r',s')),S_X((t',u')))$.
That is, that $E$ relates points in an isometric way.

* The graph of $\sim$ in (<ref>) is a closed
subsubset of $M\times X$:
If $x_p\rightarrow x$ and $y_p\rightarrow y$ for some $x,y\in X$ and $(i,x_p)\sim (j,y_p)$ for all $p$, then $(i,x)\sim (j,y)$.

Let $M\otimes X = M\times X/\sim$ and let $m\otimes x$ denote the equivalence class of $(m,x)$ in $M\otimes X$.

Suppose for every object $X$ in $\SquaMS$ we have an injective map $S_{M\otimes X}:M_0\rightarrow M\otimes X$ such that for all $(r,s)\in M_0$, $S_{M\otimes X}((r,s)) = m\otimes S_X((r',s'))$ for some $m\in M$ and $(r',s')\in M_0$, where $m$ and $(r',s')$ do not depend on $X$, just on $(r,s)\in M_0$.

Viewing $M\otimes X$ as a Metric Space  Recall that every object in $\SquaMS$ has distances bounded by $2$.
To view $M\otimes X$ as a metric space, we will use the quotient metric.

Define a metric $d$ on $M\times X$ (not $M\otimes X$) by

\begin{equation}\label{nottensor}
d_{M\times X}((m,x),(n,y)) =
\begin{cases}
\frac{1}{3}d(x,y) & m=n \\
2 & otherwise\\
\end{cases}
\end{equation}

So the distance is scaled by $\frac{1}{3}$ inside of
each copy of $X$, and otherwise, it is $2$ (the maximum distance).  The idea is that $\frac{1}{3}$ is determined by the number of copies of $X$, according to $M$ or $N$.

We see right away that $d_{M\times X}$ is bounded by $2$, since points in the same copy of $X$ will be at most $\frac{2}{3} < 2$ from each other, and points in different copies will be $2$ away from each other.

Consider $m\otimes x$ and $n\otimes y$ in $M\otimes X$. The distance between them will be defined as the infimum over all finite paths in $M\times X$ of the score, where the score is the sum of the distances (in $M\times X$) along the path, but where we count $0$ for pairs in the relation $\sim$.  By the first condition in the definition of quotient suitable, we know that the score of a given path is well defined.

First note that this is a pseudometric:  clearly this is symmetric, the distance between any point and itself is $0$, and it will satisfy the triangle inequality since the concatenation of two paths is a path.  We will show that this is in fact a metric: distinct points will have positive distance. To achieve this, we will show that the distance is actually witnessed by the score of
some particular finite path; it is not just an infimum of the scores of
an infinite set of paths.

An $\sim$-alternating path in $M\times X$
is a sequence of elements of $M\times X$ such that every other entry is related by $\sim$,
starting with either the first or the second entry, and where either the last pair is related by $\sim$
or the pair just before the last.
In other words, it is a sequence
of the form

\begin{equation}\label{L9}
(m,x)=(m_0,x_0),(m_0,x_0')\sim (m_1,x_1),(m_1,x_1')\sim \ldots, (m_p,x_p), (m_p,x_p')
\end{equation}

$(m_0,x_0)$ and $(m_p,x_p')$ might be omitted.
(If the first is omitted, then $x$  belongs to  $S_X[M_0]$, and similarly with the last and $y$.)
Also, in case $p =1$, an $\sim$-alternating path
could be a pair related by $\sim$, or it could be a pair not related by $\sim$.

For any finite path from
$(m,x)$ to $(n,y)$ in $M\times X$,
there is a $\sim$-alternating path
from $(m,x)$ to $(n,y)$
with smaller or equal score.

Take a path from $(m,x)$ to $(n,y)$, say

\begin{equation}\label{distancelemmapath}
(m,x) = (m_0,x_0) \quad (m_1, x_1) \quad (m_2, x_2) \quad \cdots \quad (m_p, x_p) = (n,y)
\end{equation}

If any adjacent pair on the path, say   $(m_k, x_k)$ and $(m_{k+1},x_{k+1})$ has
$m_k \neq m_{k+1}$ and the pair of points is not related by $\sim$, then this pair
contributes $2$ to the score.  So in this case we can just take the two-point path
$(m,x), (n,y)$ to satisfy our lemma.  We thus assume that this case does not arise in what follows.

We may take our path (<ref>) and shorten any chain of $\sim$ relations.
This is because $\sim$ is transitive.  Thus, we can assume that no three adjacent pairs are related by $\sim$.
In other words, we never have  $(m_k, x_k) \sim (m_{k+1},x_{k+1}) \sim (m_{k+2},x_{k+2})$.

At this point, we argue by induction on $p$ that for  every path (<ref>)
which meets all of the
assumptions so far has a a $\sim$-alternating path with smaller or equal score.
If $p =2$, the path automatically is $\sim$-alternating.

Assume our result for paths of length $<p$, and consider a path as in (<ref>)
of length $p$.  If this path is not alternating, then there must be
$(m_k, x_k) \not\sim (m_{k+1},x_{k+1}) \not\sim (m_{k+2},x_{k+2})$.
In this case, what we said at the end of the first paragraph implies that $m_k = m_{k+1} = m_{k+2}$.
So we may shorten our path by deleting $(m_{k+1},x_{k+1})$.
By the triangle inequality and the definition of the metric on $M\times X$
in (<ref>), the score does not increase with this deletion.
And then applying our induction hypothesis
to the shortened path proves our result.

For $m\otimes x,n\otimes y\in M\otimes X$,
for any finite path between
$(m,x)$ and $(n,y)$ in $M\otimes X$,
by (possibly) deleting entries we can find a $\sim$-alternating path with smaller or equal score.

First consider $m\otimes x$ and $n\otimes y$ whose distance according to $d_{M\times X}$ is $2$.  Then since $\frac{1}{3}<1$, we know that $m\neq n$ and $m\otimes x\neq n\otimes y$.  Thus, the path $(m,x),(n,y)$ witnesses the distance, in the sense that $d_{M\otimes X}(m\otimes x,n\otimes y) = 2=d_{M\times X}((m,x),(n,y))$, and
the path is already of the required form.

Suppose $d_{M\otimes X}(m\otimes x,n\otimes y)<2$.  Then there must be a sequence
(possibly an infinite sequence)
of finite paths such that the infimum of their scores is $d_{M\otimes X}(m\otimes x,n\otimes y)$.  Consider a path $(m,x)=(m_0,x_0),(m_1,x_1),\ldots,(m_p,x_p)=(n,y)$ whose score is strictly less than $2$.

Note that if there is $0\leq k<p$ such that $(m_k,x_k)$ and $(m_{k+1},x_{k+1})$ are not identified by $\sim$ and $m_k\neq m_{k+1}$, then the distance between these entries is $2$, making the score at least $2$ and contradicting our assumption.

Next, if we have more than two successive entries
which are all equivalent under $\sim$, we can remove all but the first and last and the score remains the same.

And finally, suppose that
we have three adjacent entries $(m_k,x_k),(m_{k+1},x_{k+1}),(m_{k+2},x_{k+2})$ such that $m_k=m_{k+1}=m_{k+2}$.  Then
we could
delete $(m_{k+1},x_{k+1})$ from the path,
by the triangle inequality, the score
would not increase.

Now we are ready to prove that the quotient metric can be calculated as the score of a particular finite path, not just an infimum.
We do this in Theorem <ref> just below.
This results has two assumptions, and  they look technical.
It might help to look
ahead to Section <ref> for
the definitions of $M\otimes X$ for the particular
$M$ that we want most in the paper.  It turns out that the first
assumption is very mild; any reasonable way to define $M\otimes X$
should satisfy this assumption.  On the other hand, the second assumption
is much more substantial.  It plays a key role in our connection of
the Sierpinski carpet with iterations of a functor on square sets.

Suppose $M$ is a finite index set and $E$ is a quotient suitable equivalence relation on $M\times M_0$.  Further, assume
that for any $x,y\in X$ and $m\in M$, for any path $(m,x)=(m_0,x_0), \ldots, (m_p,x_p) = (m,y)$,

\[ \frac{1}{3} d_X(x,y) \leq \displaystyle{\sum_{k=0}^{p-1}}d_{M\times X}((m_k,x_k),(m_{k+1},x_{k+1}))\]
That is, between two points
$(m,x)$ and $(m,y)$
in the same scaled copy
$\set{m}\times X$
of $X$, their distance
is $\frac{1}{3}d_X(x,y)$;
there is no   path
in $M\otimes X$ from $m\otimes x$ to $m\otimes y$
with a score smaller than $\frac{1}{3}d_X(x,y)$.

Then for $m\otimes x$ and $n\otimes y$,

\[d_{M\otimes X}(m\otimes x,n\otimes y) = \displaystyle{\sum_{k=0}^p} d_{M\times X}((m_k,x_k),(m_k,x_k')),\]

for some $\sim$-alternating path from $(m,x)$ to $(n,y)$.

Let $m\otimes x,n\otimes y\in M\otimes X$ be given and consider a $\sim$-alternating path  from one to the next.
Lemma <ref> shows that the distance from $m\otimes x$ to $n\otimes y$ is the
infimum of the scores of $\sim$-alternating paths.
The point is that any path which is not $\sim$-alternating gives rise to a
$\sim$-alternating path with score that is at most the score of the original.
We next give a similar argument for why our distance of interest is the
infimum of the scores of
paths as in (<ref>)
with $p\leq 2|M|$.
(Here $|M|$ is the number of elements in $M$.) The point is that every $\sim$-alternating
path of length  $p > 2 |M|$ must have three different $m_i$ which are
That is, we have $0\leq j<k<l\leq p$ with $m_j = m_k = m_l$.
But in this case we could delete all of the entries in our path strictly between $(m_j,x_j)$ and $(m_l,x_l')$,
and the assumption in our result tells us that we have
a (shorter) path with a smaller or equal score.

The upshot is that we need only to consider paths as in (<ref>) with $p\leq 2|M|$.
Since there are only finitely many tuples from $M$ of length $\leq 2|M|$,
we need only show that for each $p$ and each fixed tuple
$m = m_0, m_1, \ldots, m_p = n$, the infimum of the scores of paths
involving this tuple (allowing the $x$'s to vary) is attained.

For $0<i<p-1$, let

\[ C_i = (\set{m_i}\times S_{X}[M_0]) \times (\set{m_{i+1}} \times  S_{X}[M_0]).\]

Each $C_i$ is a compact set:
$M_0$ is compact, and $S_X$ is continuous, so the image $S_{X}[M_0]$ is compact.
And thus so is each set $\set{m_i}\times S_{X}[M_0]$.
So the following set $C^*$ is also compact:

\[
C^* = (C_1 \times C_1) \times  (C_2 \times C_2)
\times  (C_{p-1} \times C_{p-1}).
\]

Each element of $C^*$ is a tuple, and each gives us a path as in
In more detail, we can write an element of $C^*$ as

\begin{equation}\label{tuple}
(((m_0, x_0'),(m_1 , x_1)), \ldots,
((m_{p-1} ,  x_{p-1}),(m_p , x_p)))
\end{equation}

Again, the $m$'s are the ones
which we fixed above, and the $x$'s belong to $X$.
The first entry of this $p$-tuple,
$((m_0, x_0'),(m_1 , x_1))$ belongs to
$(m_0\times X) \times (m_{1} \times X)$, since
these two are related by $\sim$.
Analogous statements hold for all the other entries
in our tuple (<ref>)
The path corresponding to this is the one with the same notation as in (<ref>).
Moreover, every path as in (<ref>) comes from
an element of our set $C^*$.

Taking the score is a continuous function, and so we have
a continuous function $C^* \to \reals$.  Since $C^*$ is compact, this function
indeed attains its minimum value at some point, just as we want.

We next argue that there is a fixed number $p$ such that the distance in question
is the
infimum over $\sim$-alternating paths of length $p$ the score of the path.
For this, we first claim that for
$0\leq j<k<l\leq p$,
$ A_j\cap A_k\cap A_l =\emptyset$.
For suppose not.
there is some $m\in M$ and
also $m_j, m_l\in M$ and
$\widehat{x}_j,\widehat{x}_j', \widehat{x}_l,\widehat{x}_l'\in X$ such that $m_j\otimes x_j = m\otimes \widehat{x_j}$, $m_j\otimes x_j' = m\otimes\widehat{x}_j'$, $m_l\otimes x_l = m\otimes \widehat{x}_l$ and $m_l\otimes x_l' = m\otimes \widehat{x}_l'$.  By assumption, the shortest path from $m\otimes \widehat{x}_j$ to $m\otimes \widehat{x}_l'$ is the path inside of the $m$ copy of $x$.  That is, we can delete all of the entries in our path strictly between $(m_j,x_j)$ and $(m_l,x_l')$ to get a shorter path (with a smaller or equal score) of the form

\[(m,x) = (m_0,x_0),(m_0,x_0'),\ldots,(m\otimes \widehat{x}_j),(m,\widehat{x}_l'),\ldots,(m_p,x_p')=(n,y)\]

Our goal is to find a path which witnesses the exact distance
in $M\otimes X$. To achieve this, for $0\leq k\leq p$, define $A_k\subset M$ as follows: $m\in A_k$ if and only if there exists $x'$ such that  $(m,x')\sim (m_k,x_k)$.  The idea is that $A_k$ is the set of copies of $X$ which $m_k\otimes x_k$ lives in, and we will show that we can find the distance with the infimum of paths with a particular configuration of $A_k$'s.
Note that since $(m_k,x_k')\sim (m_{k+1},x_{k+1})$, $m_k\in A_{k+1}$, so $A_k\cap A_{k+1} \neq\emptyset$.

Suppose there are $0\leq j<k<l\leq p$ such that
$ A_j\cap A_k\cap A_l \neq \emptyset$.

Thus, we can always find a path with smaller or equal score such that each index in $M$ appears in at most two elements of each $A_k$.
Going back to our original $m\otimes x$ and $n\otimes y$, we know that the distance is the infimum over
paths of a fixed finite length, say $p$,
of their score.

So, since $M$ is finite, and each $m\in M$ can only appear in at most two $A_k$'s, there are only finitely many possible sequences of $A_0,\ldots, A_p$ for shortest paths (otherwise we could delete sections to find a path with a shorter score).
More specifically, since $A_k\subset M$,  there are only finitely many possible sequences $m_0,\ldots, m_p$ of indices for paths of this form.

Now suppose
$(m_0,x_0)_j,\ldots, (m_{n_j},x_{n_j}')_{j}$ are a sequence of paths whose scores converge to the distance between $m\otimes x$ and $n\otimes y$, such that each index in $M$ appears in at most two $A_k$'s in each path, and they are of the form described in Lemma <ref>.
Then since there are only finitely many possible sequences of $A_k$'s, choose some infinite subsequence of these paths such every path in the subsequence is of the same length $p$ and the sequence of $A_k$'s is the same for every path, and such that the score of path $p$ is at most $\frac{1}{p}$ greater than $d$.

That is, we have a
fixed sequence $m_1, \ldots, m_p\in M$
and a sequence of paths of the form

\[
\begin{array}{l}
(m,x)=(m_0,(x_0)_j),(m_0,(x_0')_j)\sim (m_1,(x_1)_j),(m_1,(x_1')_j),\ldots,\\
(m_{p-1},(m_{p-1}')_j)\sim (m_p,(x_p)_j),(m_p,(x_p')_j) = (n,y)
\end{array}
\]

such that the score of path $p$ is at most $\frac{1}{j}$ more than $d_{M\otimes X}(m\otimes x,n\otimes y)$.

Now let $I_0=\omega$ and $(m_0,x_0^*) = (m,x)$, which is equal to $(m_0,(x_0)_j)$ for all $j$.  Then suppose we have defined $(n_0,x_0^*),(n_0,x_0'^*),\ldots, (n_k,x_k^*)$ and infinite index sets
$I_k\subset I_{(k-1)'}\subset I_{k-1}\subset\ldots I_0\subset \omega$.

Then consider $((x_k')_j:j\in I_k)$.  This is a subset of the image of $S_X$ in $X$, which is compact, so it must have some accumulation point $x_k'^*$.  Let $I_{k'}\subset I_k$ be an infinite subset such that for $j\in I_{k'}$, $d((m_k,(x_k')_p),(m_k,x_k'^*))<\frac{1}{j}$. Then let $x^*_{k+1}$ be an accumulation point of $((x_{k+1})_j:j\in I_{k'})$ (again, this exists because this set is a subset of the image of $S_X$ in $X$, which is compact) and choose an infinite $I_{k+1}\subset I_{k'}$ such that for $j\in I_{k+1}$, $d((m_{k+1},(x_{k+1})_j),(m_k,x_{k+1}^*))<\frac{1}{j}$.  Note that $(m_k,(x_k')_j)\sim (m_{k+1},(x_{k+1})_j)$ for all $j$, so by assumption, $(m_k,x_k'^*)\sim (m_{k+1},x_{k+1}^*)$.

Then at the end of this, $(m_p,x_p'^*)$ will be $(n,y)$.  So we have a path (of the required form) from $(m,x)$ to $(n,y)$.  Notice that in these paths, the non-zero parts of the score are determined by $d_{M\times X}((m_k,x_k^*),(m_k,x_k'^*))$.

Let $\epsilon>0$ be given and choose $j$ sufficiently large so that $\frac{1}{j}<\frac{\epsilon}{2}$ and so that for each $k$, $d((m_k,(x_k)_j),(m_k,x_k^*))<\frac{\epsilon}{4(p+1)}$ and $d((m_k,(x_k')_j),(m_k,x_k'^*))<\frac{\epsilon}{4(p+1)}$.

\[
\begin{array}{cl}
& d((m_k,x_k^*),(m_k,x_k'^*))
\\
\leq &  d((m_k,x_k^*),(m_k,(x_k)_j)) + d((m_k,(x_k)_j),(m_k,(x_k')_j)) + d((m_k,(x_k')_j),(m_k,x_k'^*))
\\
\leq &
d((m_k,(x_k)_j),(m_k,(x_k')_j)) + \frac{\epsilon}{2(p+1)}\\
\end{array}
\]

and similarly,

\[
\begin{array}{cl}
& d((m_k,(x_k)_j),(m_k,(x_k')_j))\\
\leq  & d((m_k,x_k^*),(m_k,x_k'^*)) + \frac{\epsilon}{2(p+1)}\\
\end{array}
\]

And so

\[|d((m_k,x_k^*),(m_k,x_k'^*)) - d((m_k,(x_k)_j),(m_k,(x_k')_j))|\leq \frac{\epsilon}{2(p+1)}.
\]

\[
\begin{array}{lcl}
|\displaystyle{\sum_{k=0}^{p}} d((m_k,(x_k)_j),(m_k,(x_k')_j)) - \displaystyle{\sum_{k=0}^{p}} d((m_k,x_k^*),(m_k,x_k'^*))|
& \leq &  \frac{\epsilon}{2}
\end{array}
\]

So by assumption,

\[
\begin{array}{lcl}
|\displaystyle{\sum_{k=0}^{p}} d((m_k,(x_k)_j),(m_k,(x_k')_j)) -  d_{M\otimes X}(m\otimes x,n\otimes y)|
& \leq  & \frac{1}{j}<\frac{\epsilon}{2}
\end{array}
\]

Hence, $|\displaystyle{\sum_{k=0}^{p}} d((m_k,x_k^*),(m_k,x_k'^*)) - d_{M\otimes X}(m\otimes x,n\otimes y)| <\epsilon$.

So since $\epsilon>0$ was arbitrary,

\[
d_{M\otimes X}(m\otimes x,n\otimes y)=\displaystyle{\sum_{k=0}^{p}} d((m_k,x_k^*),(m_k,x_k'^*)).
\]

This shows us that the distances in $M\otimes X$ are witnessed by an actual finite path, not just an infimum of paths.  This gives us the following:

Under the same assumption as in Theorem <ref>,

* $M\otimes X$ is a metric space.

* For $n\in M$, $\phi_i:X\rightarrow M\otimes X$ given by $x\mapsto m\otimes x$ is an embedding such that for $x,y\in X$, $d_{M\otimes X}(m\otimes x,m\otimes y) = \frac{1}{3} d_X(x,y)$.

For the first assertion, assume that  $d_{M\otimes X}(m\otimes x,n\otimes y) =0$.  Then there exists an
$\sim$-alternating path  whose score is equal to $0$.
The adjacent entries $(m_k,x_k), (m_{k+1}, x_{k+1})$  not related by
$\sim$ must then contribute $0$ to the score.  This only happens when $m_k = m_{k+1}$ and $x_k = x_{k+1}$.
In this case, the entire path is a sequence completely related by $\sim$.
So we have $(m,x)\sim(n,y)$.  Thus,
$m\otimes x=n\otimes y$.

The second point is immediate from the assumption which we made in in
Theorem <ref>.

Ultimately, our goal is to define functors $M\otimes-$ and $N\otimes-$, which means we will have to examine how these functors behave on morphisms in $\SquaMS$.  This will be handled in detail in the following sections, but for now, with the assumptions of this section, we have the following result.

If $f:X\rightarrow Y$ is an injective morphism of square sets, then the $\Set$-map
$M\otimes f:M\otimes X\rightarrow M\otimes Y$ given by $m\otimes x\mapsto m\otimes f(x)$ is an injective map.

Let $f:X\rightarrow Y$ be an injective morphism.  Then if $(M\otimes f)(m\otimes x) = (M\otimes f)
(n\otimes y)$, $m\otimes f(x) = n\otimes f(y)$.  So if $m=n$, then $f(x)=f(y)$, and since $f$ is injective, $x=y$.  Otherwise, $m\otimes f(x)\sim n\otimes f(y)$, so we must have $x = S_X((r,s))$ and $y=S_X((t,u))$ for some $(r,s),(t,u)\in M_0$.
Since $f$ is a morphism, it preserves $S_X$, so $m\otimes f(S_X((r,s))) = m\otimes S_Y((r,s))$ and $n\otimes f(S_X((t,u))) = n\otimes S_Y((t,u))$. That is, $(m,S_Y((r,s)))\sim (n,S_Y((t,u)))$.  Thus,
since $E$ does not depend on $X$ or $Y$,
we must also have $m\otimes S_X((r,s)) = n\otimes S_X((t,u))$.
So $m\otimes x = n\otimes y$.

§.§ Defining $M\otimes -$ for Square Metric Spaces

The last section dealt
with properties of the operation
$X\mapsto M\otimes X$ which were presented in an abstract fashion.  Now it is time to be more concrete.   We will fix a particular set $M$
in this section, and also define a relation $E$
on $M\times M_0$ and show that it
is quotient suitable.  Then we will verify
the other hypotheses used in the results of the last section for this $M$ and $E$.
In the next section, we do the same thing for a different set $N$ and a different relation $E$.

Let $M = \{0,1,2\}^2\setminus \{(1,1)\}$.  $m=(i,j)\in M$ will indicate a (column, row) in the $3\times 3$ grid.

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=1.2]
\draw [help lines] (0,0) grid (3,3);
\draw (.5,.5)  node {$(0,0)$};
\draw (1.5,.5)  node {$(1,0)$};
\draw (2.5,.5)  node {$(2,0)$};
\draw (.5,1.5)  node {$(0,1)$};
%% \draw (1.5,1.5)  node {$(1,1)$};
\draw (2.5,1.5)  node {$(2,1)$};
\draw (.5,2.5)  node {$(0,2)$};
\draw (1.5,2.5)  node {$(1,2)$};
\draw (2.5,2.5)  node {$(2,2)$};
% \draw (2,2) -- (1,-1cm);
\end{tikzpicture}
\]

The idea is that $m\in M$ will tell us where a scaled copy of an object $X$ in $\SquaMS$ will go.

Our goal is to show that $X\mapsto M\otimes X$ is a functor on $\SquaMS$.  We will use the results of the previous section to establish that $M\otimes X$ is a metric space.

Let $E$ be the following relation on $M\times M_0$ for  $r\in [0,1]$:

\begin{equation} \label{eq-E}
\begin{array}{l}
((0,0), (r,1))\approx((0,1),(r,0))\\
((0,1), (r,1) )\approx((0,2),(r,0))\\
((0,2),(1,r))\approx( (1,2),(0,r))\\
((1,2),(1,r))\approx ((2,2),(0,r))\\
\end{array}
\qquad
\begin{array}{l}
((2,2), (r,0))\approx((2,1), (r,1))\\
((2,1), (r,0))\approx( (2,0),(r,1))\\
((2,0), (0,r))\approx((1,0), (1,r))\\
((1,0), (0,r))\approx((0,0), (1,r))\\
\end{array}
\end{equation}

For any $X$ in $\SquaMS$ we can extend this to an equivalence relation
(also denoted $\approx$)
on $M\times X$ by taking the symmetric, reflexive, and transitive closure of
the relation $\sim$ given by

\[
m\otimes S_X((r,s)) \sim n\otimes S_X((t,u)) \Leftrightarrow (m,(r,s))\approx (n,(t,u)).
\]

For $(m, (r,s))\approx (n,(r',s'))$ and $(m,(t,u))\approx (n,(t',u'))$ in $E$, it is routine to verify that in any object $X$, $d_X(S_X((r,s)),S_X((t,u))) = d_X(S_X((r',s')),S_X((t',u')))$.

If $x_p$ and $y_p$ are sequences in $X$ such that  $x_p\rightarrow x$ and $y_p\rightarrow y$ for some $x,y\in X$ and $(m,x_p)\sim (n,y_p)$ for all $p$ for some $m,n\in M$, then $(m,x)\sim (n,y)$.

If $m=n$, then $x_p=y_p$, so $x=y$.  Otherwise,  $x_p = S_X((r_p,s_p))$ and $y_p = S_X((t_p,u_p))$ for some $(r_p,s_p),(t_p,u_p)\in M_0$.  And since $S_X$ is continuous, the image of $M_0$ is compact, so it is closed, which means that $x = S_X((r^*,s^*))$ and $y = S_X((t^*,u^*))$ for some $(r^*,s^*),(t^*,u^*)\in M_0$.  It is routine to verify that for some infinite subsequence of $p$, all of the $x_p$'s are on one of the four sides of $M_0$, and similarly for $y_p$, so their limits will coincide according to the definition of $E$.  That is, $(m,S_X((r^*,s^*)))\sim (n,S_X((t^*,u^*)))$.

$E$ is quotient suitable.

Define $S_{M\otimes X}$ by

\[ S_{M\otimes X}((0,r)) =
\begin{cases}
(0,0)\otimes S_X((0,3r)) & 0\leq r\leq \frac{1}{3} \\
(0,1)\otimes S_X((0,3r-1)) & \frac{1}{3}\leq r\leq \frac{2}{3}\\
(0,2)\otimes S_X((0,3r-2)) & \frac{2}{3}\leq r\leq 1\\
\end{cases}
\]

\[ S_{M\otimes X}((r,1)) =
\begin{cases}
(0,2)\otimes S_X((3r,1)) & 0\leq r\leq \frac{1}{3} \\
(1,2)\otimes S_X((3r-1,1)) & \frac{1}{3}\leq r\leq \frac{2}{3}\\
(2,2)\otimes S_X((3r-2,1)) & \frac{2}{3}\leq r\leq 1\\
\end{cases}
\]

\[ S_{M\otimes X}((1,r)) =
\begin{cases}
(2,0)\otimes S_X((1,3r)) & 0\leq r\leq \frac{1}{3} \\
(2,1)\otimes S_X((1,3r-1)) & \frac{1}{3}\leq r\leq \frac{2}{3}\\
(2,2)\otimes S_X((1,3r-2)) & \frac{2}{3}\leq r\leq 1\\
\end{cases}
\]

\[ S_{M\otimes X}((r,0)) =
\begin{cases}
(0,0)\otimes S_X((3r,0)) & 0\leq r\leq \frac{1}{3} \\
(1,0)\otimes S_X((3r-1,0)) & \frac{1}{3}\leq r\leq \frac{2}{3}\\
(2,0)\otimes S_X((3r-2,0)) & \frac{2}{3}\leq r\leq 1\\
\end{cases}
\]

The idea is that each new side consists of $3$ copies of the corresponding side from $X$.  So far, $(M\otimes X, S_{M\otimes X})$ is a square set (we know $S_{M\otimes X}$ is well-defined because of the identified segments in $\sim$ on $M\times X$).

As before, the metric $d_{M\times X}$ is

\[ d((m,x),(n,y)) =
\begin{cases}
\frac{1}{3}d(x,y) & m = n \\
2 & otherwise\\
\end{cases}
\]

So the distance is scaled by $\frac{1}{3}$ in the same copy of $X$, and otherwise, it is $2$ (the maximum distance).
To apply Theorem <ref> and Corollary <ref> to see that $M\otimes X$ is a metric space, we will need the following lemmas.

Let $X$ be any object in $\SquaMS$.
Let $m\in M$ and let $x,y\in X$.
The score of every path in $M\times X$ from $(m,x)$ to $(m,y)$ is at least
$\frac{1}{3} d_X(x,y)$.

Let $(m_0,x_0),\ldots,(m_p,x_p)$ be a path, where $(m_0,x_0) = (m,x)$ and $(m_p,x_p) = (m,y)$. (Notice that the same $m$ is used in both the start and end of the path.)

\begin{equation}\label{dioc}
\frac{1}{3} d_X(x,y) \leq \displaystyle{\sum_{k=0}^{p-1}} d_{M\times X}((m_k,x_k),(m_{k+1},x_{k+1})).
\end{equation}

Fix $m$, $x$, and $y$.
Since we are establishing a lower bound on the scores of paths from $(m,x)$ to $(m,y)$,
we need only consider $\sim$-alternating paths.
This is by Lemma <ref>.

Paths must be of length $\geq 2$, and the case of $p = 2$  is trivial.
Without loss of generality, we may consider a path of the form in
Lemma <ref>, say

\[ (m,x)=(m_0,x_0),(m_0,x_0')\sim (m_1,x_1), (m_1,x_1')\sim (m_2,x_2)\ldots \]

\[\ldots (m_{p-1},x_{p-1}),
(m_{p-1},x_{p-1}')\sim (m_p,x_p), (m_p,x_p') = (m,y)\]

(where we may have $(m_0,x_0) = (m_0,x_0')$ or $(m_p,x_p) = (m_p,x_p')$ if $x$ or $y$ are in the image of $S_X$, respectively), since we can always find a path of this form witnessing the distance.  In particular, we may assume that we do not have $k$ such that $m_k=m_{k+1}$, otherwise by the triangle inequality we would be able to delete $(m_i,x_i')$ and $(m_{i+1},x_{i+1})$ to get a $\sim$-alternating path of length $2p$ with a score which is at most that of our original path, whose score is strictly less than $\frac{1}{3}d_X(x,y)$.  But this contradicts our induction hypothesis.

Suppose that for
paths of length at most $2p$,
the score is at least $\frac{1}{3}d_X(x, y)$.  Suppose also that, towards a contradiction,
we have a
path of length $2p + 2$ whose score is strictly less than $\frac{1}{3}d_X(x,y)$.

Now consider the sequence $m_0,\ldots,m_p$ in $M$. This corresponds to a path in the
region contact graph of $M$, shown below:

<EMAIL_ADDRESS>(0,2)\ar@{-}[d] \ar@{-}[r]  & \ar@{-}[dl] (1,2)\ar@{-}[dr]  \ar@{-}[r] & (2,2)\ar@{-}[d] \\
(0,1) \ar@{-}[d]\ar@{-}[dr]  & & (2,1) \ar@{-}[d]\ar@{-}[dl]\\
(0,0) \ar@{-}[r]  & (1,0) & \ar@{-}[l]  (2,0) \\
\]

Recall  that the path under discussion starts and ends in the same
copy $\set{m}\times X$ of $X$.
So it corresponds to a cycle in the graph above.  In particular, since the score of our path is bounded by $\frac{2}{3}$ (the maximum possible value of $\frac{1}{3}d_X(x,y)$), we known that adjacent entries must be
in the same copy of $X$ or identified by $\sim$
(or else the score would exceed $2$).

The only
simple cycles in this
graph are the triangles, the squares,  the overall outside rectangle,
and versions of that outside rectangle that cut one to four of the corners.

Notice that the “diamond” in the middle in which all four corners are cut corresponds to the
$\sim$-alternating path

\[
\begin{array}{ll}
(1,0),S_X((0,1))\sim ((0,1)\otimes S_X((1,0)),
((0,1), S_X((1,1))) \sim ((1,2),S_X((0,0)),
\\
((1,2), S_X((1,0)))\sim ((2,1),S_X((0,1))),
((2,1),S_X((0,0)))\sim ((1,0),S_X((1,1))),
\\
((1,0), S_X((0,1)))
\end{array}
\]

This path has score $\frac{4}{3}$, exceeding $\frac{2}{3}$. Then any version of this where we replace an edge of the diamond with the corner of the square will have longer score, so none of these paths will have sufficiently small score.

This takes care of all of the simple cycles in the region contact graph except for the triangles.
So suppose we have a triangle such as

<EMAIL_ADDRESS>((0,0),x)\ar@{-}[r] & ((0,0), x_0') \ar@{-}[r]^-{\sim} &
((1,0),x_1)\ar@{-}[r] &   ((1,0), x_1') \ar@{-}[r]^-{\sim} &
((0,1),x_2)\ar@{-}[r] &
\\
\ar@{-}[r]  &((0,1),x_2') \ar@{-}[r]^-{\sim} &
((0,0), x_3)\ar@{-}[r] & ((0,0),y)
\]

But in this case, we must have $x_1' = S_X((0,1))$ and $x_2 = S_X((1,0))$ since this is the only shared point by $(1,0)$ and $(0,1)$.  But

\[((1,0),S_X((0,1)) \sim ((0,1),S_X((1,0))) \sim ((0,0),S_X((1,1)),\]

so we get a smaller or equal score replacing this with

\[\xymatrix{
((0,0),x)\ar@{-}[r] & ((0,0), S_X((1,1)))
\ar@{-}[r] &
\]

By now the triangle inequality, we can just get a smaller or equal score just using the path $((0,0),x),((0,0),y)$, which has score $\frac{1}{3} d_X(x,y)$.
This shows that the path that we started with could not have had a score less than
the original distance in $X$.

Let us return to our discussion of $M\otimes -$ as a functor on $\SquaMS$.
Corollary <ref> tell us that
for every object $X$,
$M\otimes X$ is a metric space.
We next  check that $S_{M\otimes X}$ satisfies the non-degeneracy requirements.

$M\otimes X$ with $S_{M\otimes X}$ satisfies ($\sqone$) and ($\sqtwo$).

To show ($\sqone$), without loss of generality, we will examine $S_{M\otimes X}((r,0))$ for $r\in [0,1]$ (since all of the sides will behave the same way).
We show
\begin{equation}\label{rs}
d_{M\otimes X}(S_{M\otimes X}((r,0)),S_{M\otimes X}((s,0))) = |s-r|.\end{equation}

First, if $S_{M\otimes X}((r,0))$ and $S_{M\otimes X}((s,0))$ are in the same copy of $X$, this follows immediately from Lemma <ref>.

Next, suppose $S_{M\otimes X}((r,0))$ and $S_{M\otimes X}((s,0))$ are in adjacent copies of $X$.  Without loss of generality, suppose $0\leq r\leq \frac{1}{3}$ and $\frac{1}{3}<s\leq \frac{2}{3}$.  That is, $S_{M\otimes X}((r,0)) = (0,0)\otimes S_X((3r,0))$ and $S_{M\otimes X}((s,0)) = (1,0)\otimes S_X((3s-1,0))$.
Then there is a path

\[ ((0,0),S_X((3r,0))), ((0,0),S_X((1,0)))\sim ((1,0),S_X((0,0))),((1,0),S_X((3s-1,0)))\]

through the bottom right corner of the $(0,0)$ copy of $X$.  This path has length

\[\frac{1}{3}|1-3r| + \frac{1}{3} |3s-1 - 0| = \frac{1}{3} ( |1-3r| + |3s-1|) = \frac{1}{3}|1-3r + 3s -1|=|s-r|,\]

since $0\leq r\leq \frac{1}{3} < s\leq \frac{2}{3}$.  To see that this is the shortest path, first note that going the other way around the square will yield a path which is greater than $1$ by the non-degenerate requirements (as in Lemma <ref>).  So we just need to check that the score of a path of the form

\[((0,0),S_X((3r,0))), ((0,0),S_X((1,k))), ((1,0),S_X((0,k))),((1,0),S_X((3s-1,0)))
\]
has minimal score when $k=0$.

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=3]
\draw [help lines] (0,0) grid (2,1);
\draw (0,0) node {$\bullet$};
\draw (.5,0) node {$\bullet$};
\draw (1,0) node {$\bullet$};
\draw (1.5,0) node {$\bullet$};
\draw (2,0) node {$\bullet$};
\draw (1,.5) node {$\bullet$};
\draw (.25,-.15)  node {$c$};
\draw (.75,-.15)  node {$x$};
\draw (1.25,-.15)  node {$y$};
\draw (1.75,-.15)  node {};
\draw (.25,.25)  node {$d$};
\draw (.75,.15)  node {$a$};
\draw (1.25,.15)  node {$b$};
\draw (1.75,.25)  node {};
\draw (0,0) -- (1,.5);
\draw (2,0) -- (1,.5);
\draw (.5,0) -- (1,.5);
\draw (1.5,0) -- (1,.5);
% \draw (2,2) -- (1,-1cm);
\end{tikzpicture}
\]

This amounts to showing that $x\leq a$ and $y\leq b$.  By the non-degeneracy requirement for $X$ (that points on opposite sides are at least distance $1$ apart since the distance is bounded below by the taxicab metric) we know that $d\geq \frac{1}{3}$ and $c+x = \frac{1}{3}$.  So $c+x = \frac{1}{3} \leq d \leq a+c$ $\Rightarrow$ $x\leq a$.  Similarly, $y\leq b$.  So indeed the shortest possible path is when $k=0$.
Hence,  in this case
$d(S_{M\otimes X}((r,0)),S_{M\otimes X}((s,0)) = |s-r|$, as required.

It remains to check this holds for $S_{M\otimes X}((r,0))$ and $S_{M\otimes X}((s,0))$ in non-adjacent copies of $X$ (that is, $0\leq r\leq \frac{1}{3}$ and $\frac{2}{3}\leq s\leq 1$).
We note again that we have a path with length $|s-r|$ via the bottom corners of the $(1,0)$ copy of $X$.  If we go the other way around $M\otimes X$, our path will have score greater than $1$ because of the non-degenerate requirement, and using a triangle inequality argument similar to the adjacent copies case, we see that this is minimized by going through the corners.

Now to check ($\sqtwo$), let $(r,s)$ and $(t,u)$ in $M_0$ be given, and consider a shortest path between $S_{M\otimes X}((r,s))$ and $S_{M\otimes X}((t,u))$.  First note that each pair of entries in the path contributing positively to the score will be on the sides of a copy of $X$, so we can take advantage of ($\sqtwo$) in $X$.  We will show that the sum of horizontal and vertical components of each entry of our path will be at least the sum of the horizontal and vertical components of the distance between $(r,s)$ and $(t,u)$, and thus, our distance will be bounded below by the taxicab metric.

The different cases for relative placement of $(r,s)$ and $(t,u)$ are similar, so we will examine $S_{M\otimes X}((0,s))$ and $S_{M\otimes X}((r,0))$ with $\frac{1}{3}<r, s< \frac{2}{3}$ in detail.

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=1.5]
\draw [help lines]  grid (3,3);
\draw (1.5,0)  node (a)  {$\bullet$};
\draw (1,.5)  node {$\bullet$};
\draw (.5,1)  node {$\bullet$};
\draw (0,1.5)  node  (b) {$\bullet$};
\draw (-1,1.5)  node {$S_{M\otimes X}((0,s))$};
\draw (1.5,-.5)  node {$S_{M\otimes X}((r,0))$};
\draw (0.75, 1.2) node {$A$};
\draw (1.3, 0.5) node {$B$};
%% \draw (1.5,1.5)  node {$(1,1)$};
%  \draw (2.5,1.5)  node {$(2,1)$};
% \draw (.5,2.5)  node {$(0,2)$};
% \draw (1.5,2.5)  node {$(1,2)$};
%   \draw (2.5,2.5)  node {$(2,2)$};
\draw (1.5,0) -- (0,1.5);
\end{tikzpicture}
\]

By examining cases, we can show that a shortest path will be of the form pictured (though we may have $A =B = (0,0)\otimes S_X((1,1))$).  Then by ($\sqtwo$) in $X$, we see that
its length is

\[d_{M\otimes X}(S_{M\otimes X}((0,s)), A) + d_{M\otimes X}(A,B) + d_{M\otimes X}(B,S_{M\otimes X}((r,0))).\]

Note that $S_{M\otimes X}((0,s)) = (0,1)\otimes S_X((0,3s-1))$ and $S_{M\otimes X}((r,s)) = (1,0)\otimes S_X((3r-1,0))$.  Let $A = (0,1)\otimes S_X((t,0)) = (0,0)\otimes S_X((t,1))$ and $B = (0,0)\otimes S_X((1,u)) = (1,0)\otimes S_X((0,u))$.

Then the distance is

\[
\begin{array}{cll}
& \frac{1}{3}d_X(S_X((0,3s-1)), S_X((t,0))) + \frac{1}{3}  d_X(S_X((t,1)),S_X((1,u)))\\
& \qquad + \frac{1}{3} d_X(S_X((t,1)),S_X((1,u))) + \frac{1}{3}d_X(S_X((0,u)),S_X((3r-1,0)))\\
= &  \frac{1}{3}(|3s-1-0| + |t-0| + |1-t| + |1-u| + |u-0| + |3r-1-0|)
\\
= & \frac{1}{3}(3|s-0| + 3|r-0|)\\
= & |s-0| + |r-0|,
\end{array}
\]

as required.
In the first equality, we used
the fact that $X$ is an object in $\SquaMS$.

At this point we know that $M\otimes X$ is an object in $\SquaMS$.
That is, we know how the functor $M\otimes -$ works on objects
of $\SquaMS$.
Now let $f:X\rightarrow Y$ be a morphism  in
To check that $M\otimes f:M\otimes X\rightarrow M\otimes Y$ is a morphism, first note that for $(r,s)$ on the boundary of the unit square,

\[ (M\otimes f)(S_{M\otimes X}((r,s))) =
(M\otimes f)(m\otimes S_X((r',s')))\]

for some $m\in M$ and $(r',s')\in M_0$ (by the definition of $S_{M\otimes X}$), and this equals

\[
\begin{array}{cll}
&  m\otimes f(S_X((r',s')))\\
= & m\otimes S_Y((r',s'))&
\mbox{since $f$ preserves $S_X$}\\
= & S_{M\otimes Y}((r,s))\\
\end{array}
\]

The last equality holds since $S_{M\otimes Y}$ is defined using the same scheme as $S_{M\otimes X}$.
So $M\otimes f$ preserves $S_{M\otimes X}$.

To see that $M\otimes f$ is a short map, let
$m\otimes x, n\otimes y\in M\otimes X$ and let

\[m\otimes x = m_0\otimes x_0,\ldots,m_p\otimes x_p = n\otimes y\]

be a shortest path between them of the form in Theorem  <ref>.

Then if $d_{M\times X}((m_k,x_k),(m_k,x_{k+1})) \neq 0$, it is because $m_k=m_{k+1}$.

\[
\begin{array}{cll}
& d_{M\otimes X}(m_k\otimes x_k,m_{k+1}\otimes x_{k+1}) \\
= & d_{M\times X}((m_k,x_k),(m_{k+1},x_{k+1}))\\
= & \frac{1}{3}d_X(x_k,x_{k+1})\\
\geq &  \frac{1}{3} d_Y(f(x_k),f(x_{k+1})) &
\mbox{since $f$ is a short map}\\
= & d_{M\times Y}((m_k,f(x_k)),(m_{k+1},f(x_{k+1})))\\
=  & d_{M\otimes Y}((M\otimes f)(m_k\otimes x_k),(M\otimes f)(m_{k+1}\otimes x_{k+1}))
\end{array}
\]

Thus, since there is a path in $M\otimes Y$ from $(M\otimes f)(m\otimes x)$ to $(M\otimes f)(m\otimes y)$ whose score is bounded above by the score of a shortest path in $M\otimes X$, $M\otimes f$ is a short map.

Finally, note that $M\otimes -$ preserves compositions and identity maps, as required.

$M\otimes -$ is a functor on $\SquaMS$.

Finally, we want to take advantage of the following lower bound on paths.  Recall that $d_{U_0}((x,y),(x_1,y_1)) = |x-x_1|+|y-y_1|$ is the taxicab metric on the unit square.

Let $B$ be an object in $\SquaMS$ and consider $m\otimes S_B((r,s))$ and $n\otimes S_B((t,u))$ in $M\otimes B$.  Then

$$d_{M\otimes B}(m\otimes S_B((r,s)),n\otimes S_B((t,u)))\geq d_{M\otimes U_0}(m\otimes S_{U_0}((r,s)),n\otimes S_{U_0}((t,u)))$$

By Theorem  <ref> there is a shortest path in $M\otimes B$ of the form

\[
\begin{array}{l}m\otimes S_B((r,s)) = n_0\otimes S_B((r_0,s_0)), n_0\otimes S_B((r_0',s_0'))\sim n_1\otimes S_B((r_1,s_1)),\\
\ldots, m_{p-1}\otimes S_B((r_{p-1},s_{p-1})), m_{p-1}\otimes S_B((r_{p-1}',s_{p-1}'))\sim m_p\otimes S_B((r_p,s_p)) = n\otimes S_B((t,u))
\end{array}
\]

Then note that

\[
\begin{array}{cl}
& d_{M\otimes B}(m_k\otimes S_B((r_k,s_k)), m_k\otimes S_B((r_k',s_k')))
\\
= & \frac{1}{3} d_B(S_B((r_k,s_k)),S_B((r_k',s_k')))
\\
\geq & \frac{1}{3} d_{U_0}(S_{U_0}((r_k,s_k)),S_{U_0}((r_k',s_k')))
\\
= &  d_{U_0}(m_k\otimes S_{U_0}((r_k,s_k)), m_k\otimes S_{U_0}((r_k',s_k')))
\end{array}
\]

where the inequality follows from $(\sqtwo)$.  So the score of the shortest path in $M\otimes B$ is bounded below by the score of the corresponding path in $M\otimes U_0$, which is an upper bound of the distance between the correspond points in $M\otimes U_0$ (since there may be a shorter path).

§.§ Defining $N\otimes-$ in $\SquaMS$

It will be useful for us to augment $M$ in the following way.  Let $N = \{0,1,2\}^2 = M\cup \{(1,1)\}$, which will correspond to the full $3\times 3$ grid.  We aim to expand the work from the previous section to show that $N\otimes -$ is also a functor.  We will use this in later sections.

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=1.2]
\draw [help lines] (0,0) grid (3,3);
\draw (.5,.5)  node {$(0,0)$};
\draw (1.5,.5)  node {$(1,0)$};
\draw (2.5,.5)  node {$(2,0)$};
\draw (.5,1.5)  node {$(0,1)$};
\draw (1.5,1.5)  node {$(1,1)$};
\draw (2.5,1.5)  node {$(2,1)$};
\draw (.5,2.5)  node {$(0,2)$};
\draw (1.5,2.5)  node {$(1,2)$};
\draw (2.5,2.5)  node {$(2,2)$};
% \draw (2,2) -- (1,-1cm);
\end{tikzpicture}
\]

First we want to apply Corollary <ref> to see that $N\otimes X$ is in fact a metric space with the quotient metric.  The majority of the work for us is done.  The definition of $S_{N\otimes X}$ will coincide with $S_{M\otimes X}$, and we will need to expand $E$ to include

\[
\begin{array}{l}
((0,1),(1,r))\approx ((1,1),(0,r))\\
((1,2),(r,0))\approx ((1,1),(r,1))\\
((2,1),(0,r))\approx ((1,1),(1,r))\\
((1,0),(r,1))\approx ((1,1),(r,0))\\
\end{array}
\]

for $r\in [0,1]$.  Call this relation $\widehat{E}$.

The proof of Lemma <ref> holds for $N$.

For Lemma <ref>, we need to show that the claim holds for paths starting and ending in the $(1,1)$ copy of $X$.

Let $X$ be any object in $\SquaMS$.
Let $n\in N$ and let $x,y\in X$.
Let $(n_0,x_0),\ldots,(n_p,x_p)$ be a path, where $(n_0,x_0) = (n,x)$ and $(n_p,x_p) = (n,y)$. (Notice that the same $n$ is used in both the start and end of the path.)

\[\frac{1}{3} d_X(x,y) \leq \displaystyle{\sum_{k=0}^{p-1}} d_{N\times X}((j_k,x_k),(j_{k+1},x_{k+1})).\]

We extend the proof of Lemma <ref> to consider cycles in the region contact graph of $N$ which start and end at $(1,1)$.

\[\xymatrix@-1pc{ (0,2)\ar@{-}[d] \ar@{-}[r]  &
(1,2)  \ar@{-}[r] & (2,2)\ar@{-}[d] \\
(0,1) \ar@{-}[d] \ar@{-}[ur]  &
(1,1) \ar@{-}[u] \ar@{-}[d] \ar@{-}[r] \ar@{-}[l]
\ar@{-}[ur]  \ar@{-}[ul]  \ar@{-}[dr]  \ar@{-}[dl]
& (2,1) \ar@{-}[d] \ar@{-}[ul] \\
(0,0) \ar@{-}[r]  &  (1,0) \ar@{-}[ur] \ar@{-}[ul] & \ar@{-}[l]  (2,0) \\
\]

Note that the region contact graph of $M$ is a subgraph of this, and that the only new edges are those from $(1,1)$ to every other vertex.

For any cycle of $3$ vertices, by the same argument as in Lemma <ref>, this is not a shortest path.

Then it remains to check cycles with more than $3$ distinct entries.  The second entry is either a middle square or a corner, so we will examine two representative cases: cycles of length $4$ or more which begin with $(1,1), (0,1)$, and ones which begin with $(1,1),(0,2)$.

Consider a cycle starting with $(1,1), (0,1)$.  Then the next entry must be from $(0,2)$ or $(0,1)$, without loss of generality suppose it is $(0,2)$.  Then the next entry must be in $(1,2)$, so we get the
diagram on the left:

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=1.5]
\draw [help lines]  grid (3,3);
\draw (1.5,1.5)  node (a) {$\bullet$};
\draw (1,1.5)  node (b)  {$\bullet$};
\draw (.5,2)  node (c)  {$\bullet$};
\draw (1,2.5)  node  (d) {$\bullet$};
\draw (1.5,1.5)  -- (1,1.5) ;
\draw (1,1.5)  -- (.5,2);
\draw (.5,2) -- (1,2.5);
\draw (1,2.5) -- (1.5,2.7);
\end{tikzpicture}
\qquad \qquad
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=1.5]
\draw [help lines]  grid (3,3);
\draw (1.5,1.5)  node (a) {$\bullet$};
\draw (1,1.5)  node (b)  {$\bullet$};
\draw (1,2)  node (c)  {$\bullet$};
\draw (1,2.5)  node  (d) {$\bullet$};
%  \draw (1.5,2.5)  node  (e) {$\bullet$};
\draw (1.5,1.5)  -- (1,1.5) ;
\draw (1,1.5)  -- (1,2);
\draw (1,2) -- (1,2.5);
\draw (1,2.5) -- (1.5,2.7);
\end{tikzpicture}
\]

But this path can be made shorter by moving the second entry to $(0,1)\otimes S_X((1,1)) = (1,1)\otimes S_X((0,1))$, by the non-degeneracy requirements in $X$.  This is shown on the right above.
By the triangle inequality in $X$, we can shorten this by removing the second and fourth points in this path, which will remove two entries in our cycle.  But then this will reduce to one of the previous cases.

Next consider a cycle which starts with $(1,1),(0,2)$, and without loss of generality, suppose the next entry is $(1,2)$.  Then the second entry must be of the form $(0,2)\otimes S_X((1,0))$, and then the next entry is of the form $(1,2)\otimes S_X((0,s)) = (0,2)\otimes S_X((0,1))$.

The following entry is either $(2,2)$, or $(2,1)$, but in either case, the next entry in the path is of the form $(1,2)\otimes S_X((1,t))$ (where $t=0$ in the latter case).

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=1.5]
\draw [help lines]  grid (3,3);
\draw (1.5,1.5)  node (a) {$\bullet$};
\draw (1,2)  node (b)  {$\bullet$};
\draw (1,2.5)  node (c)  {$\bullet$};
\draw (2,2.5)  node  (d) {$\bullet$};
%  \draw (1.5,2.5)  node  (e) {$\bullet$};
\draw (1.5,1.5)  --  (1,2) ;
\draw (1,2)  -- (1,2.5);
\draw (1,2.5) -- (2,2.5);
\end{tikzpicture}
\]

So by the triangle inequality we can delete the third entry for a shorter path, so our cycle now starts with $(1,1), (1,2)$.  But then this reduces to either the cycle of length $3$ case or the previous case.

So by Corollary <ref>, $N\otimes X$ is a metric space.  The proof that $N\otimes X$ satisfies ($\sqone$) is the same as that for $M\otimes X$, and ($\sqtwo$) follows for $N\otimes X$ from ($\sqtwo$) in $X$, in the same way as it does for $M\otimes X$ in Lemma <ref>.

Morphisms will be preserved by $N\otimes -$ just as they are by $M\otimes -$.  Hence, we have the following:

$N\otimes -$ is a functor on $\SquaMS$.

In fact, we can calculate the distance between certain points in images of iterations $N\otimes-$ using horizontal and vertical components.   Later on we will see that by taking the colimit of an $\omega$-chain of applications of $N\otimes-$, and then the Cauchy completion of this space,
we get the unit square with the taxicab metric.

Let $B$ be an object in $\SquaMS$.  Consider $N^p\otimes B$.  This is $3^{2p}$ copies of $B$ arranged in a $3^p\times 3^p$ grid.  Consider two points which correspond to corners of copies of $B$.  That is, points of the form $n_0\otimes\ldots\otimes n_{p-1}\otimes S_B((r,s))$ where $r,s\in \{0,1\}$.  We can view these points as occurring on a grid with $3^{2p}$ squares.  Let $h$ be the number of horizontal squares between the two and $v$ be the number of vertical squares.

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=.5]
\draw [help lines] (0,0) grid (8,8);
\draw (2,2)  node {$\bullet$};
\draw (7,6)  node {$\bullet$};
%  \draw (1.5,.5)  node {$(1,0)$};
%   \draw (2.5,.5)  node {$(2,0)$};
% \draw (2,2) -- (1,-1cm);
\end{tikzpicture}
\]

For example, if this is $N^2\otimes B$ and we consider points $(0,0)\otimes (2,2)\otimes S_B((0,0))$, and $(2,2)\otimes (0,0)\otimes S_B((1,0))$, then $h = 5$ and $v=4$.

Then consider any path between two such points.  For each pair of non-equivalent adjacent points in the path, these correspond to edges of one these squares.  So the distance between them will be $\frac{1}{3^p}$ times the distance between these points, which by ($\sqtwo$) is bounded below by the taxicab metric on $M_0$.  That is, for each of the squares occurring in the path, it will contribute (at least) a horizontal component or a vertical component to the score of the path, and in some cases, both.

Any path between these two points will have at least $h$ many squares contributing at least $1$ each to the score, and at least $v$ many squares contributing at least $1$ each to the score, so the distance in the quotient metric will be bounded below by $\frac{h+v}{3^n}$.  And in fact, we can witness this distance with the $L$-shaped path from one point to the other along the grid lines formed by the boundaries of copies of $B$.

For $(i_0,j_0)\otimes\ldots\otimes (i_{p-1},j_{p-1})\otimes S_B((r,s))$ and $(k_0,l_0)\otimes\ldots\otimes (k_{p-1},l_{p-1})\otimes S_B((t,u))$ where $r,s,t,u\in \{0,1\}$ in $N^p\otimes B$, their distance is exactly $\frac{h+v}{3^p}$.
In particular, for $(i_0,j_0),\ldots,(i_{p-1},j_{p-1}), (k_0,l_0),\ldots (k_{p-1},l_{p-1})\in N$,
$$d_{N^p\otimes B}((i_0,j_0)\otimes\ldots\otimes (i_{p-1},j_{p-1})\otimes S_B((0,0)), (k_0,l_0)\otimes\ldots\otimes (k_{p-1},l_{p-1})\otimes S_B((0,0)))$$

$$= |\displaystyle{\sum_{m=0}^{p-1}}\frac{i_m-k_m}{3^{m+1}}| + |\displaystyle{\sum_{m=0}^{p-1}}\frac{j_m-l_m}{3^{m+1}}|$$

It is clear that
the distances are precisely $\frac{h+v}{3^p}$, so we will just show the formula holds for the case when $(r,s)=(t,u)=(0,0)$ (the other cases are similar).  So we need to show  that $|\displaystyle{\sum_{m=0}^{p-1}}\frac{i_m-k_m}{3^{m+1}}| =  \frac{h}{3^p}$, then the same argument will show that $|\displaystyle{\sum_{m=0}^{p-1}}\frac{j_m-l_m}{3^{m+1}}| = \frac{v}{3^p}$.
We will do this by induction on $p$.

When $p=0$, this holds automatically since the distance will be $0$.

Suppose this is true for $(i_0,j_0)\otimes\ldots\otimes (i_{p-1},j_{p-1})\otimes S_B((0,0))$ and $(k_0,l_0)\otimes \ldots\otimes (k_{p-1},l_{p-1})\otimes S_B((0,0))$.  Let $h$ be the number of horizontal units between them (as described above).

Without loss of generality, suppose for the first index $m$ such that $i_m\neq k_m$, that $i_m< k_m$.  That is, if we visualize this on a grid, $(i_0,j_0)\otimes\ldots\otimes (i_{p-1},j_{p-1})\otimes S_B((0,0))$ is to the left of $(k_0,l_0)\otimes \ldots\otimes (k_{p-1},l_{p-1})\otimes S_B((0,0))$.  So $|\displaystyle{\sum_{m=0}^{p-1}}\frac{i_m-k_m}{3^{m+1}}|  = \displaystyle{\sum_{m=0}^{p-1}}\frac{k_m-i_m}{3^{m+1}}$.

Then let $(i_p,j_p)$ and $(k_p,l_p)$ be given.

$(i_0,j_0)\otimes\ldots\otimes (i_{p-1},j_{p-1}) \otimes (i_p,j_p)\otimes S_B((0,0)$ is $\frac{i_p}{3^{p+1}}$ units to the right of $(i_0,j_0)\otimes\ldots\otimes (i_{p-1},j_{p-1})\otimes S_B((0,0)$, and $(k_0,l_0)\otimes \ldots\otimes (k_{p-1},l_{p-1})\otimes (k_p,l_p)\otimes S_B((0,0))$ is $\frac{k_p}{3^{p+1}}$ units to the right of $(k_0,l_0)\otimes \ldots\otimes (k_{p-1},l_{p-1})\otimes S_B((0,0))$.

So if $h'$ is the number of horizontal units between $(i_0,j_0)\otimes\ldots\otimes (i_{p-1},j_{p-1}) \otimes (i_p,j_p)\otimes S_B((0,0)$ and $(k_0,l_0)\otimes \ldots\otimes (k_{p-1},l_{p-1})\otimes (k_p,l_p)\otimes S_B((0,0))$, $h' = 3h +k_p - i_p$.

Thus, the horizontal distance is

\[
\displaystyle{\frac{3h-k_p-i_p}{3^{p+1}}} = \displaystyle{\sum_{m=0}^{p-1}}\frac{k_m-i_m}{3^{m+1}} + \frac{k_p-i_p}{3^{n+1}} = \displaystyle{\sum_{m=0}^{p}}\frac{k_m-i_m}{3^{m+1}}.
\]

as required.

We also have an analogous lower bound on distances between boundary points to Proposition <ref>. The proof is the same.

Let $B$ be an object in $\SquaMS$ and consider $m\otimes S_B((r,s))$ and $n\otimes S_B((t,u))$ in $N\otimes B$.  Then

\[ d_{N\otimes B}(m\otimes S_B((r,s)),n\otimes S_B((t,u)))\geq d_{N\otimes U_0}(m\otimes S_{U_0}((r,s)),n\otimes S_{U_0}((t,u))).\]

We close this section with a result to be used later.

There is a natural transformation
$\iota\colon M\otimes - \to N \otimes -$.

For a space $X$, $\iota_X$ is the inclusion
of spaces $M\otimes X \to N \otimes X$.
This is a short map because every geodesic in $M\otimes X$ between
points is a path between the same points in $N\otimes X$.

§.§ The Cauchy Completion Functor

To obtain the final $M\otimes-$ and $N\otimes-$ coalgebras, we will use the technique in [2] of using the completion of the initial algebra.  Here we recall some facts about $C$, the Cauchy completion functor.

Consider a category $\mathcal{C}$ of metric spaces whose morphisms are short maps,  and for $X$ an object in $\mathcal{C}$, let $C(X)$ be its Cauchy completion, where we identify equivalent Cauchy sequences (that is, $(x_i)_i$ and $(y_i)_i$ such that $d_X(x_i,y_i)$ tends to $0$).
For Cauchy sequences $(x_i)_i$ and $(y_i)_i$ from an object $X$ in $\mathcal{C}$, $d_{C(X)} ((x_i)_i,(y_i)_i) = \displaystyle{\lim_{i\rightarrow\infty}}d_X(x_i,y_i)$, which is well defined (as it will be $0$ for equivalent Cauchy sequences).  If $(x_i)_i$ and $(y_i)_i$ are not equivalent, then $d_{C(X)}((x_i)_i,(y_i)_i)>0$.     For $f:X\rightarrow Y$ a morphism in $\mathcal{C}$, let $C(f):C(X)\rightarrow C(Y)$ be defined by $(x_i)_i\mapsto (f(x_i))_i$.  Since $(x_i)_i$ is a Cauchy sequence in $X$ and $f$ is a short map, $(f(x_i))_i$ is a Cauchy sequence in $Y$.  This is well defined.

Let $\mathcal{C}$ be $\SquaMS$, and let $C$ be a map which takes objects in $\mathcal{C}$ to their Cauchy completions.

$C$ may be considered as an endofunctor on $\SquaMS$.

Let $X$ be an object in SquaMS and consider $C(X)$.  $S_{C(X)}((r,s))$ will be the class of Cauchy sequences whose limits are $S_X((r,s))$ (for example, the constant sequence $(S_X((r,s)))$).  So

\[ d_{C(X)}(S_{C(X)}((r,s)),S_{C(X)}((t,u))) = d_X(S_X((r,s)),S_X((t,u))\]
for $(r,s),(t,u)\in M_0$.  Thus, ($\sqone$) and ($\sqtwo$) hold, and clearly distances in $C(X)$ are also bounded by $2$.  So $C(X)$ is an object in SquaMS.

Now we need to check that $C(f)$ is a morphism in $\SquaMS$.  First note that $C(f):C(X)\rightarrow C(Y)$ is a short map. To see that $C(f)$ preserves $S_{C(X)}$, let $(x_i)_i\in C(X)$ be a Cauchy sequence whose limit is $S_X((r,s))$ (so $(x_i)_i$ is $S_{C(X)}((r,s))$).

For $i$ sufficiently large so that $d_X(x_i, S_X((r,s)))<\epsilon$, we have

\[
d_Y(f(x_i),S_Y((r,s)))=d_Y(f(x_i), f(S_X((r,s))))<d_X(x_i,S_X((r,s))) < \epsilon,\]

So $(f(x_i))_i$ converges to $S_Y((r,s))$, as required.

We aim to show that $M\otimes -$ and $N\otimes -$ commute with $C$.  We will show the result for $M\otimes-$, but the proof for $N\otimes-$ is the same.
For any object $X$ in $\mathcal{C}$, consider

\[ M\otimes C(X)\xrightarrow[]{\delta_X} C(M\otimes X)\xrightarrow[]{\rho_X} M\otimes C(X).\]

given by

\[\begin{array}{lcl}
\delta_X(m\otimes (x_0,x_1,\ldots))
& =  & (m\otimes x_0,m\otimes x_1,\ldots) \\
\rho_X((m_k\otimes x_k)_k)
& =  &  m^*\otimes (x_{k_0},x_{k_1},\ldots),
\end{array}
\]

where $m^*$ is the first index in $M$ (via some order of the finite set $M$) which occurs infinitely many times in $(m_k\otimes x_k)_k$ and $x_{k_0},x_{k_1},\ldots$ are the corresponding elements of $X$.

$\delta$ and $\rho$ are natural isomorphisms.

It is routine to check that for all $X$ in $\mathcal{C}$, $\delta_X$ and $\rho_X$ are well-defined,
that they are inverse functions (modulo equivalence of Cauchy sequences), that they are short maps, and thus, isometries.

We need to check that $\delta_X$ and $\rho_X$ preserve $S_X$.
For $\delta_X$, let $(r,s)\in M_0$ and consider $S_{M\otimes C(X)}((r,s))$.  Then for some $m$ and $(r',s')$ which do not depend on $C(X)$, $S_{M\otimes C(X)}((r,s)) = m\otimes S_{C(X)}((r',s'))$.  $S_{C(X)}((r',s'))$ can be viewed as the limit of the constant sequence $(S_X((r',s')))$.    So $\delta_X(S_{M\otimes C(X)}((r,s)))= \delta_X(m\otimes (S_X((r',s')))) = (m\otimes S_X((r',s')))$, which is equal to the constant sequence $(S_{M\otimes X}((r,s)))$, whose limit is $S_{C(M\otimes X)}((r,s))$, as required.

For $\rho_X$, if $(r,s)\in M_0$, we can view $S_{C(M\otimes X)}((r,s))$ as the limit of the constant sequence $(S_{M\otimes X}((r,s)))$, which is equal to the constant sequence $(m\otimes S_X((r',s')))$ for some $m\in M$ and $(r',s')\in M_0$ only depending on $(r,s)$.  Then $\rho_X(S_{C(M\otimes X)}((r,s))) = m\otimes (S_X((r',s'))) = m\otimes S_{C(X)}((r',s')) = S_{M\otimes C(X)}((r,s))$.

We get analogous natural isomorphisms for $N\otimes-$ defined in the same way.  Thus, we have the following.

For $X$ in $\SquaMS$, $M\otimes C(X) \cong C(M\otimes X)$ and $N\otimes C(X) \cong C(N\otimes X)$.

§ THE INITIAL ALGEBRA OF $M\OTIMES -$ OBTAINED AS THE COLIMIT OF
ITS INITIAL $\OMEGA$-CHAIN

The overall message of this paper is that the Sierpinski carpet as a metric space
is bilipschitz equivalent to
a final coalgebra of the endofunctor $M\otimes -$ on the category of square metric spaces.
However, to show this, we need a lot of material on a dual concept, initial algebras.
It turns out that in our setting the final coalgebra is the Cauchy completion of the initial algebra.

Let $\A$ be a category and $F\colon\A\to \A$
an endofunctor.
An algebra for $F$ is a pair $(A,f)$, where
$A$ is an object, and $f: FA\to A$ is a morphism.
We call $A$ the carrier and $f$ the
structure (morphism).
A pre-fixed point of $F$ is an
algebra whose structure is a monomorphism.

Let $(A,f)$ and $(B,g)$ be algebras for $F$.  An algebra morphism
from $(A,f)$ to $(B,g)$
is a morphism $\phi:A\to B$ in $\AA$ such that $\phi\o f = g \o F\phi$:

\[
\xymatrix@C+1pc{FA \ar[r]^-{f} \ar[d]_-{F\phi}
& A \ar[d]^-{\phi}\\
FB   \ar[r]_-{g}  &  B
\]

This gives a category $\AlgF$ of $F$-algebras, and an initial algebra is an initial object in  $\AlgF$.
As expected, if such an algebra exists at all, it is unique up to isomorphism
in  $\AlgF$ (which is equivalent to being isomorphic in the base category $\A$).

We recall a standard result in category theory, Lambek's Lemma:
if $(A,f)$ is an initial algebra, then $f$ is an isomorphism in the base category $\A$.

§.§ An injective $M\otimes -$ algebra

The main result of this section is the existence of an
initial algebra $M\otimes G \rightarrow G$ in $\SquaMS$.
Before we start in on that,
we exhibit an injective algebra related to the topic of this paper.
Let $U_0=[0,1]^2$, equipped with the taxicab metric $d_{U_0}$, where

\[d_{U_0}((x,y),(x_1,y_1)) = |x-x_1|+|y-y_1|.\]

Define $\alpha_M: M\otimes U_0\rightarrow U_0$ by $(i,j)\otimes (r,s)\mapsto (\frac{1}{3}(i+r),\frac{1}{3}(j+s))$.
The following result is not immediate because the metrics are different in
$U_0$ and $M\otimes U_0$.

$\alpha_M:M\otimes U_0\rightarrow U_0$ is an injective morphism
of $\SquaMS$.   Thus, $(U_0,\alpha_M:M\otimes U_0\rightarrow U_0)$ is an injective $M\otimes-$ algebra.

First, it is easy to verify using the equivalences in $E$ that $\alpha_M$ preserves $S_{M\otimes U_0}$.  To see that $\alpha_M$ is injective, note that if $\alpha_M((i,j)\otimes (r,s)) = \alpha_M((k,l)\otimes (t,u))$, when $(i,j)=(k,l)$, we must have $(r,s) = (t,u)$.  Otherwise, by examining cases we check that for any possible combination of $(i,j)$ and $(k,l)$, this equality forces $(r,s)$ and $(t,u)$ to be such that $(i,j)\otimes (r,s)$ and $(k,l)\otimes (t,u)$ are equal under the equivalence relation $E$.

Now we need to check that $\alpha_M$ is a short map.  Let $x=(i,j)\otimes (r,s)$ and $y=(k,l)\otimes (t,u)$ in $M\otimes U_0$.
$x$ and $y$ fall into one of the following cases (up to possible rotation and reflection).

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=1.2]
\draw [help lines] (0,4) grid (1,5);
\draw (.3,4.6)  node   {$\cdot\, x$};
\draw (.7,4.2)  node   {$\cdot\, y$};
\draw [help lines] (2,3) grid (3,5);
\draw (2.5,4.5)  node   {$\cdot\, x$};
\draw (2.5,3.5)  node   {$\cdot\, y$};
\draw [help lines] (4,2) grid (5,5);
\draw (4.5,4.5)  node    {$\cdot\, x$};
\draw (4.5,2.5)  node   {$\cdot\, y$};
\draw [help lines] (6,2) grid (7,5);
\draw [help lines] (7,2) grid (8,3);
\draw (6.5,4.5)  node    {$\cdot\, x$};
\draw (7.5,2.5)  node   {$\cdot\, y$};
\end{tikzpicture}
\]

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=1.2]
\draw [help lines] (0,0) grid (1,3);
\draw [help lines] (1,0) grid (3,1);
\draw (0.5,2.5)  node    {$\cdot\, x$};
\draw (2.5,0.5)  node    {$\cdot\, y$};
\draw [help lines] (4,1) grid (5,3);
\draw [help lines] (5,2) grid (6,3);
\draw (4.5,1.5)  node    {$\cdot\, y$};
\draw (5.5,2.5)  node    {$\cdot\, x$};
\draw [help lines] (7,0) grid (10,3);
\draw (8.5,2.5)  node    {$\cdot\, x$};
\draw (8.5,0.5)  node    {$\cdot\, y$};
\end{tikzpicture}
\]

In each case it is reasonably routine to verify that $d_{M\otimes U_0}(x,y)\geq d_{U_0}(\alpha_M(x),\alpha_M(y))$, but we will examine one of these cases carefully, the one indicated in
the lower-left corner.
Suppose $(i,j) = (0,2)$ and $(k,l) = (2,0)$ (so $x$ and $y$ are in opposite corners).
Note that

\[ d_{U_0}(\alpha_M(x),\alpha_M(y)) = \frac{1}{3}|(i+r)-(k+t)|+\frac{1}{3}|(j+s)-(l+u)|.
\]

Then, without loss of generality, the shortest path
in $M\otimes U_0$
between $x$ and $y$ is of the following form:

\[
\begin{array}{l}
x=(0,2)\otimes (r,s), (0,2)\otimes (r_1,0)=(0,1)\otimes (r_2,1), \\
(0,1)\otimes (r_3,0)= (0,0)\otimes (r_4,1), (0,0)\otimes (1, s_1) = (1,0)\otimes (0,s_2),\\
(1,0)\otimes (1,s_3)=(2,0)\otimes (0,s_4), (2,0)\otimes (t,u)=y\\
\end{array}
\]

\[
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2cm,semithick,scale=1.2]
\draw [help lines] (0,0) grid (1,3);
\draw [help lines] (1,0) grid (3,1);
\draw (0.5,2.5)  node     {$\bullet$};
\draw (0.2,2.5)  node     {$x$};
\draw (2.5,0.5)  node   {$\bullet$};
\draw (2.8,0.5)  node   {$y$};
\draw (0.6,2)  node  (a)  {$\bullet$};
\draw (0.6,1)  node   (b)   {$\bullet$};
\draw (1,.8)  node    {$\bullet$};
\draw (2,.8)  node    {$\bullet$};
\draw (0.5, 2.5) -- (0.6,2);
\draw (0.6,2)  -- (0.6,1);
\draw (0.6,1) -- (1,.8);
\draw (1,.8) --(2,.8);
\draw(2,.8) --(2.5,0.5) ;
\end{tikzpicture}
\]

We estimate the score of this path.  First, we consider the horizontal components from each scaled copy of $U_0$.
Their contribution to the score is

\[
\begin{array}{cl}

\geq & \frac{1}{3}|r_1-r| + \frac{1}{3} |r_2-r_1| + \frac{1}{3} |1-r_2| + \frac{1}{3}|1-0| + \frac{1}{3} |t-0|\\
\geq & \frac{1}{3} |2 + (t-r)|\\
%%%%%and since $i=0$ and $k=2$,
= & \frac{1}{3} |(i+r)-(k+t)|
\end{array}
\]

(The last equality holds because  $i=0$ and $k=2$.)
Similarly for the vertical components.  Thus, $d_{M\otimes U_0}(x,y)\geq d_{U_0}(\alpha_M(x),\alpha_M(y))$.

The other cases are similar.

In the next section we will revisit $\alpha_M$ and a similarly defined morphism $\alpha_N:N\otimes U_0\rightarrow U_0$.

§.§ Colimits of $\omega$-chains

We apply Theorem <ref>,
a well-known result in category theory,
to construct an initial algebra by taking
the colimit of a certain $\omega$-chain and verifying that the functor
preserves this colimit.
We thus begin with a review of the definitions.  Even though we are mainly interested
in square metric spaces, we find it convenient to work somewhat more generally and
also to study the situation in several related categories.

Let $\A$ be a category.
$\omega$-chain in $\A$
is a functor from $(\omega, \leq)$ as a category into $\A$.
It is determined by an infinite sequence of objects and morphisms of $\A$ indexed by $\omega$:

\begin{equation}\label{chain}
\xymatrix{
A_0 \ar[r]^{a_{0}} & A_1 \ar[r]^{a_{1}} & \cdots & A_k \ar[r]^{a_k} & A_{k+1} & \cdots
\end{equation}

To turn this into a functor from $(\omega, \leq)$, we must specify
connecting morphisms $a_{k,\ell}$ for $k \leq \ell$.
We obviously take
$a_{k,k} = \id_{A_k}$, and
then for $k < \ell$ we take $a_{k,\ell}$ to be the composition
$a_{\ell-1} \o a_{\ell-2} \o \cdots \o a_{k}$.

A cocone of (<ref>) is
a pair $(B, (b_k)_k)$ consisting of
an object $B$ together with morphisms $b_k\colon A_k \to B$ so that that $b_k = b_\ell \o a_{k,\ell}$
when $k\leq \ell$.
Sometimes we abuse notation slightly and write a cocone as $b_k\colon A_k\to B$, but technically
a cocone is an object together with a family of morphisms.
A colimit of the chain

is a cocone $(C,(c_k)_k)$ with the property that
for every cocone  $(B, (b_k)_k)$ there is a unique morphism $f\colon C \to B$ so that $b_k = f \o c_k$ for all $k\in\omega$.

Consider an $\omega$-chain (<ref>) with connecting morphisms $a_{k,\ell}$.  Let $(C,(c_k)_k)$ be a colimit.
We say that $F$ preserves this colimit
the chain $FA_k$ with connecting morphisms $Fa_{k,\ell}$ has $(FC,(Fc_k)_k)$ as a colimit.

Here is the reason that this is of interest in this paper.

Let $\mathcal{A}$ be a category with initial object $0$.  Let $F:\mathcal{A}\rightarrow\mathcal{A}$ be an endofunctor.  Consider the initial chain

\[
0\xrightarrow[]{!} F0\xrightarrow[]{F!} F^20\xrightarrow[]{F^2!} \cdots F^k0\xrightarrow[]{F^k !}  F^{k+1}0\cdots\]

Suppose the colimit $G=colim_{k<\omega}F^k0$ exists, and write $g_k:F^k0\rightarrow  G$ for the cocone morphism.
Suppose that $F$ preserves this colimit.
Let $a:FG\rightarrow G$ be the unique moprhism so that $a\circ Fg_k=g_{k+1}$ for all $k$.  Then $(G,a)$ is an initial algebra.

We are especially concerned with the case
$0= M_0$, and  $! =S_{M\otimes M_0}: M_0 \to M\otimes M_0$.
We shall show that with those choices, the colimit of the initial $\omega$-chain exists,
calling on much more general results.
Then we shall prove that the functor $M\otimes -$ preserves this colimit.

In addition,
we are going to need  colimits of other $\omega$-chains in $\SquaMS$.
For every $M\otimes -$ coalgebra $(B,\beta)$, we need the chain below and its colimit.

\begin{equation}
B\xrightarrow[]{\beta} M\otimes B\xrightarrow[]{M\otimes \beta} M^2\otimes B\xrightarrow[]{M^2\otimes \beta}
\cdots M^k\otimes B\xrightarrow[]{M^k\otimes \beta}  M^{k+1}\otimes B\cdots,
\label{eq-B-chain}
\end{equation}

We need the same colimit with $N$ replacing $M$, too.
We shall prove that the colimit of (<ref>) exists
and that it is preserved by the functor.
For this, we combine general facts about
colimits in  pseudo-metric spaces
with facts about the functors $M\otimes -$ and $N\otimes -$
which we have already seen.

We thus make a digression to study colimits of $\omega$-chains in further generality.
We want to explore the colimits in sets,
pseudo-metric spaces, metric spaces,
square sets, and square metric spaces.
In each case, we aim for a characterization
of colimits of $\omega$-chains.

§.§ Colimits of $\omega$-chains in $\Set$

Suppose we have an $\omega$-chain  in $\Set$

\begin{equation}\label{Achain}
A_0 \to A_1 \to \cdots \end{equation}

with connecting maps $a_{k,\ell}\colon A_k \to A_\ell$.
Suppose that we have a set $C$ and a cocone
$(c_k)_{k\in\omega}$, where
A_k \to C$.  Assume the following two properties:

($\Set$1) $C = \bigcup_{k} c_k[A_k]$, and

($\Set$2) Given $k\in\omega$ and elements
$x,y\in A_k$ with $c_k(x) = c_k(y)$, there exists $\ell \geq k$ in
$\omega$ such that $a_{k,\ell}(x) = a_{k,\ell}(y)$.

Note that ($\Set$2) implies a stronger form of the same result:
if $x\in A_k$ and $y\in A_\ell$ with $k\leq \ell$ and $c_{k}(x)=c_\ell(y)$,
then there is $p\geq \max(\ell,k)$ such that $a_{k,p}(x) = a_{\ell,p}(y)$.
Here is how we see this.  Notice that $a_{k,\ell}(x)\in A_\ell$.   Apply ($\Set$2) to $a_{k,\ell}(x)$ and $y$ as elements
of $A_\ell$ to get some $p\geq \ell$ so that $a_{\ell,p}(a_{k,\ell}(x)) = a_{\ell,p}(y)$.   But $a_{\ell,p}(a_{k,\ell}(x)) = a_{k,p}(x)$.

We claim that $C$ with these morphisms is a colimit.
Indeed, suppose we are given a cocone $b_k\colon A_k\to B$.
We need to define a cocone morphism $f\colon C\to B'$ and to prove that it is unique.
We define $f(c_k(x)) = b_k(x)$ for all $k\in \omega$ and $x\in A_k$.
This is a well-defined function due to  ($\Set$1) and ($\Set$2).
It is a cocone morphism $f\o c_k = b_k$.   And it is unique,  since
the condition   $f\o c_k = b_k$ gives the definition of $f$.

To prove the existence of a colimit of  (<ref>), we only need to find a set with
($\Set$1) and ($\Set$2).
Take the disjoint union $\sum_k A_k$, then take the  relation $\equiv$
given by

\[
(x,k) \equiv (y,\ell)\quad\mbox{iff}\quad \mbox{ $a_{k,p}(x) = a_{\ell,p}(y)$ for some $p\geq k,\ell$}
\]

In fact, this relation is an equivalence relation.
The quotient $C = (\sum_k A_k)/\!\!\equiv$ is then the colimit, with maps $c_k = A_k \to \sum_k A_k \to C$.

The second fact is a result which we state now:
If each $a_k$ is injective, so is each $c_k$.

Suppose that $[(x,k)] = [(y,k)]$.  Then there is some $p\geq k$ so that $a_{k,p}(x) = a_{k,p}(y)$.
Since $a_{k,p}$ is injective, $x = y$.

§.§ Colimits of $\omega$-chains in $\PS$

Let us consider the category $\PS$ of $2$-bounded
pseudo-metric spaces.
(A pseudo-metric on a set $X$ is a distance function
$d: X\times X \to [0,\infty]$
with the following properties:
$d(x,x) = 0$, $d(x,y) = d(y,x)$, and $d(x,z) \leq d(x,y) + d(y,z)$.
However, $d(x,y) = 0$ need not imply $x = y$.
A $2$-bounded space has all distances bounded by $2$.)
As with the metric space categories in this paper,
we take the morphisms in $\PS$ to be  the non-expanding functions (short maps).
Let $\UU\colon \PS \to \Set$ be the forgetful functor.
As mentioned in [1] for the case of $1$-bounded spaces,
$\PS$ is also
cocomplete. That is, it has all colimits, not just colimits of $\omega$-chains.
We only need a special case of this, the result for colimits of $\omega$-chains.

Characterization of colimits of $\omega$-chains in $\PS$.
Suppose we have a chain

\begin{equation}\label{AchainPS}
(A_0,d_0) \to (A_1,d_1) \to \cdots \end{equation}

with connecting short maps $a_{k,\ell}\colon A_k \to A_\ell$.
Suppose that we have a $\PS$-object $(C,d_C)$ with
short maps $c_k\colon
A_k \to C$.  Assume the following three

($\PS$1)  $C = \bigcup_{k} c_k[A_k]$, and

($\PS$2) Given $n\in\omega$ and elements
$x,y\in A_k$ with $c_k(x) = c_k(y)$, there exists $\ell \geq k$ in
$\omega$ such that $a_{k,\ell}(x) = a_{k,\ell}(y)$.

($\PS$3)  For all $k$ and all $x,y\in A_k$,
$d_C(c_k(x), c_k(y)) = \inf_{p\geq k} d_p(a_{k,p}(x), a_{k,p}(y))$.

We claim that $(C,d_C)$ is the   colimit of (<ref>) in
Due to ($\PS$1) and ($\PS$2), the underlying set $C$
is a colimit of the $\omega$-chain in $\Set$ obtained by forgetting the pseudometric.
So, given a cocone $b_k\colon A_k\to B$
in $\PS$,
we have a $\Set$ map $f\colon C\to B$
(from above)
given by $f(c_k(x)) = b_k(x)$.  We need only check that this map is
short.  First take a fixed $k$ and elements $x,y\in A_k$.   We want to show that

\[ d_{B}(f(c_k(x)), f(c_k(y))) \leq d_C(c_k(x), c_k(y))\]

This means that we want

\[ d_{B}(b_k(x), b_k(y))) \leq
\inf_{p\geq k} d_p(a_{k,p}(x), a_{k,p}(y)) \]

For this, we can show that for all $p\geq k$,

\[ d_{B}(b_k(x), b_k(y))) \leq
d_p(a_{k,p}(x), a_{k,p}(y)) \]

Now $b_p\colon A_p\to B$ is short, and $b_p\o a_{k,p} = b_k$ due to the cocone property.

\[ d_p(a_{k,p}(x), a_{k,p}(y)) \geq
d_{B}(b_p (a_{k,p}(x)), b_p (a_{k,p}(y))   ) = d_{B}(b_k(x), bk(y)) \]

More generally, we need to consider $\ell\leq k$ and elements $x\in A_k$ and $y\in A_\ell$.
In this case, $a_{\ell,k}(y) \in A_k$.
So by what we just did,

\[ d_{B}(f(c_k(x)), f(c_k(a_{\ell,k}(y)))) \leq d_C(c_k(x), c_k(a_{\ell,k}(y)))\]

But $c_k\o a_{\ell,k} = c_\ell$.
So we have

\[ d_{B}(f(c_k(x)), f(c_\ell(y))) \leq d_C(c_k(x), c_\ell(y)).\]

To prove the existence of a colimit of  (<ref>), we
need only find a space with properties ($\PS$1) –($\PS$3) above.
Take the colimit $C$ in $\Set$.  This ensures ($\PS$1) and ($\PS$2).
Endow this set with the pseudometric

\[
d^*(x,y) = \inf \set{d_k(x',y') : k< \omega,  x',y'\in A_k,
c_k(x') = x,  \mbox{ and } c_k(y') = y }.
\]

This ensures ($\PS$3).

§.§ Colimits of $\omega$-chains in $\MS$

Now suppose we have a chain of
of $2$-bounded
metric spaces:

\begin{equation}\label{AchainMS}
(A_0,d_0) \to (A_1,d_1) \to \cdots \end{equation}

with connecting short maps $a_{k,\ell}\colon A_k \to A_\ell$.
Suppose that we have a metric space $(C,d_C)$ with
short maps $c_k\colon
A_k \to C$.  Assume the following

($\MS$1)  $C = \bigcup_{k} c_k[A_k]$, and

($\MS$2)  For all $k$ and all $x,y\in A_k$,
$d_C(c_k(x), c_k(y)) = \inf_{p\geq k} d_p(a_{k,p}(x), a_{k,p}(y))$.

We claim that $(C,d_C)$ is the   colimit of (<ref>) in
Suppose we have a     cocone $b_k\colon A_k\to B$
in $\MS$.
We want to define $f\colon C\to B$
as before,
by $f(c_k(x)) = b_k(x)$.
To prove that $f$ is well-defined in $\Set$ or $\PS$, we had used a condition that we do not assume here,
so the argument is different.
Suppose that we have $n$ and     $x,y\in A_k$ with $c_k(x) = c_k(y)$.

We want to show that $b_k(x) = b_k(y)$.   (The more general case of having $\ell,k$ and
$x\in A_k$, $y\in A_\ell$ with $c_k(x) = c_\ell(y)$ is treated similarly.)
Since $B$ is a metric space, it is sufficient to show that
$d_B(b_k(x), b_k(y)) \leq \eps$ for every $\eps >0$.
Then, by condition ($\MS$2),

\[ \inf_{p\geq k} d_p(a_{k,p}(x), a_{k,p}(y)) = 0 = d_C(c_k(x), c_k(y)).\]

Fix $p$ so that $ d_p(a_{k,p}(x), a_{k,p}(y)) \leq \eps$.
Since $b_p \colon A_p \to B$ is short,

\[
d_B(b_k(x), b_k(y)) =
d_B(b_p(a_{k,p}(x)),  b_p(a_{k,p}(y)) ) \leq  d_p(a_{k,p}(x), a_{k,p}(y)) \leq \eps.
\]

This proves that $f$ is well-defined.
The same argument which we gave for $\PS$ shows that it is the colimit map in $\MS$.

To prove the existence of a colimit of  (<ref>), we
need only find a metric space with properties ($\MS$1) –($\MS$2) above.
Take the colimit $C$ in $\Set$,
and endow it with the same pseudometric from before

\[
d^*(x,y) = \inf \set{d_k(x',y') : k<\omega, x',y'\in A_k,
i_k(x') = x,  \mbox{ and } i_k(y') = y }.
\]

Then let $x \sim y$ iff $d^*(x,y) = 0$.   This is an equivalence relation,
and so we can take the quotient $C/\!\!\sim$.  This quotient is a metric space,
and in fact the natural map $C\to C/\!\!\sim$ does not change any non-zero distances.
The quotient has properties ($\PS$1) –($\PS$3).
For ($\PS$2),   if two points in $A_k$
are identified by some map $a_{k,p}$, then their images in $C$ will have distance $0$
in $C$ and hence in $C/\!\!\sim$.  Thus our metric space is a colimit in $\PS$ and
hence also in $\MS$.

§.§ Colimits of $\omega$-sequences in $\SquaSet$

Suppose we have a chain

\[
A_0 \to A_1 \to \cdots
\]

in $\SquaSet$.
Suppose that we have a cocone $a_k\colon A_k \to C$ in $\SquaSet$, and assume ($\Set$1) – ($\Set$2).
Then we claim that our cocone is the colimit in $\SquaSet$.   To see this,  we need only endow
$C$  with a square set structure
$S_{C}\colon M_0 \to C$ and also show that given a cocone
$b_k\colon A_k\to B$ in $\SquaSet$,
the colimit map $f\colon C\to B$ preserves this structure.

We define $S_C$ by $c_0 \o S_{A_0} : M_0 \to A_0 \to C$.
To see that this works, note that since $b_0 \colon A_0 \to B$ is a square space map, $b_0\o S_{A_0} = S_B$.

\[ f \o S_C = f\o  c_0 \o S_{A_0} =  b_0 \o S_{A_0} = S_B
\]

§.§ Colimits of $\omega$-sequences in $\SquaMS$

Suppose we have a chain

\[
(A_0, d_0) \to (A_1, d_1) \to \cdots
\]

in $\SquaMS$.
Suppose that we have a cocone $a_k\colon A_k \to C$ in $\SquaMS$, and assume ($\MS$1) – ($\MS$2).
Then we claim that our cocone is the colimit in $\SquaMS$.

We know how to take the colimit $C$ in $\SquaSet$, endowing $C$ with a $\SquaSet$ structure.
We also know how to take the colimit in $\MS$.
So the only remaining point is to check the non-degeneracy requirements
($\sqone$) and ($\sqtwo$).
To check $(\sqone)$, let $r,s\in [0,1]$ and consider $S_{C}((r,0))$ and $S_{C}((s,0))$.  Then

\[d_{C}(S_{C}((r,0)),S_{C}((s,0))) =
\displaystyle{\inf_{k<\omega}} d_k(S_{A_k}((r,0)),S_{A_k}((r,0))) = |r-s|,\]

since each $A_k$ is an object in $\SquaMS$.
Similarly, to check $(\sqtwo)$, let $(r,s),(t,u)\in M_0$.  Then

\[ d_{C}(S_{C}((r,s)),S_{C}((t,u))) =
\displaystyle{\inf_{k<\omega}}\ d_k(S_{A_k}((r,s)),S_{A_k}((t,u)))\geq |r-t| +  |s-u|,\]

§.§ Preservation Theorems

Consider a chain

\[
(A_0, d_0) \to (A_1, d_1) \to \cdots
\]

in $\SquaMS$, and let its colimit be $(C, (c_k)_k)$.
Write $M\otimes d_k$ for the metric on $M\otimes A_k$.
Then the colimit of

\[
(M\otimes A_0,  M\otimes d_0) \to (M\otimes  A_1, M\otimes d_1) \to \cdots
\]

is $(M\otimes C, (M\otimes c_k)_k)$.

We know that the cocone
$(C, (c_k)_k)$
has properties ($\MS$1) and ($\MS$2) for the original chain.
We need only check that
$(M\otimes C, (M\otimes c_k)_k)$ has these same properties ($\MS$1) and ($\MS$2)   for the second chain.

For ($\MS$1), it is clear that

\[ M\otimes C = M \otimes \bigcup_k c_k[A_k] =
\bigcup_k \biggl( M \otimes  c_k[A_k]\biggr)  = \bigcup_k (M\otimes c_k)[A_k].
\]

For ($\MS$2), we want to show that
for all $k\in\omega$ and all $x,y\in A_k$, and all $m, n\in M$,

\begin{equation}
\label{want}
d_{M\otimes C}(m\otimes c_k(x), n\otimes c_k(y)) = \inf_{p\geq k} d_{M\otimes A_p}(m \otimes a_{k,p}(x), n\otimes a_{k,p}(y))
\end{equation}

We first consider the case when $n = m$.
In this case,

\[
\begin{array}{lcll}
d_{M\otimes C}(m\otimes c_k(x), m\otimes c_k(y))
& = & \frac{1}{3} d_{C}(c_k(x), c_k(y)) \\ \\
& = & \frac{1}{3} \inf_{p\geq k} d_p(a_{k,p}(x), a_{k,p}(y)) \\ \\
& = &  \inf_{p\geq k} \frac{1}{3} d_p(a_{k,p}(x), a_{k,p}(y))\\ \\
& = &  \inf_{p\geq k} d_{M\otimes A_p} (m\otimes a_{k,p}(x),m \otimes a_{k,p}(y))
\end{array}
\]

With this special case done, we consider the general case.    We use the fact from Theorem  <ref>
that in $M\otimes C$, there is a fixed path that attains the distance between our points $m\otimes c_k(x)$ and $n\otimes c_k(y)$.
This path has finitely many sub-paths (at most $5$ in fact), and each subpath is in one and the same copy of $C$.
It follows from our first observation that  (<ref>) holds.

We also have a result
exactly like Theorem <ref>
but for the functor $N\otimes -$.
The details are basically the same.

§.§ Using Colimits to Obtain the Initial $M\otimes-$ Algebra

At this point, we recall Adamék's Theorem (Theorem <ref>),
and apply this to $\SquaMS$, with $F$ either $M\otimes -$ or $N\otimes -$.
As we know, the colimit exists, since colimits of all $\omega$-chains exist in our category.
And the functor preserves this colimit, since it preserves all colimits of $\omega$-chains.
Thus, there is an initial algebra for $M\otimes -$, and also an initial algebra for $N\otimes -$.
We write these as

\begin{equation}\label{GW}
\begin{array}{l}
(G,\eta: M\otimes G\to G) \\
(W,\lambda\colon N\otimes W \to W) \\
\end{array}
\end{equation}

In both cases, the algebra structures  are isometries, by Lambek's Lemma.
We also need an important detail about both of these coalgebras.  We state a fact about this for $M$, but the same reasoning works for $N$.

Further, the colimit morphisms are given by the natural equivalence relations.
For example, consider $M$ (the functor where we need this remark).
We have

\begin{equation}\label{ikmaps}
g_k\colon M^k\otimes M_0\rightarrow G
\end{equation}

given by $g_k(x) = [x]$, where the equivalence relation involved here
relates, for $l\leq m$,  $y\in M^\ell\otimes M_0$ with $z\in M^m\otimes M_0$
iff $a_{\ell,m}(y) = z$,
where $a_{\ell,m}\colon  M^\ell\otimes M_0 \to  M^m\otimes M_0$ is the
evident map.

$G$ is in fact equal to the colimit in $\PS$, and thus, the colimit in $\Set$.

$G$ is the colimit of the $\omega$-chain in $\SquaMS$, and indeed, in $\MS$.  To see that it is the colimit of the chain in $\PS$, and thus, in $\Set$, we need to know that there is no “quotienting” as we pass from $\PS$ to $\MS$.
This is a due to the short injective map of each $M^k\otimes M_0$ into the unit square $U_0$:  by Corollary <ref>, we know that $M\otimes-$ preserves injective morphisms, and from Lemma <ref>, we know that $\alpha_M:M\otimes U_0\rightarrow U_0$ is injective.  So for each $k$ we have an injective morphism $\alpha_M\circ\ldots\circ M^k\otimes \alpha_M\circ M^k\otimes i:M^k\otimes M_0\rightarrow U_0$, where $i:M_0\rightarrow U_0$ is the inclusion map.    That is, distinct points in $M^k\otimes M_0$
map to points in $U_0$ which are distinct, and thus, whose distance is positive.  In particular, the images of the points along the $\omega$-chain will still map to the same points in $U_0$, so their distance will be bounded below by the same positive distance.  Thus, the infimum of the distances is bounded below by a positive number.

The canonical maps $g_k \colon M^k \otimes M_0 \to G$ are injective.

Along the chain

\[
M_0 \to M\otimes M_0 \to M^2 \otimes M_0 \cdots
\]

each morphism is injective.   This is an easy induction using our general result that $M\otimes - $ preserves injective maps.
Then the colimit in $\Set$ is injective, by Proposition <ref>.  And so the colimit in $\PS$ is injective as well, since the maps are the same.  So since $G$ is the colimit in $\PS$, the maps $g_k: M^k\otimes M_0\rightarrow G$ are injective.

§ FINAL COALGEBRAS FOR $N\OTIMES-$ AND $M\OTIMES -$

This section discusses final coalgebras for the two main functors of interest in this paper,
$N\otimes -\colon \SquaMS\to \SquaMS$, and $M\otimes -\colon \SquaMS\to \SquaMS$.
The main results are that the unit square $U_0$ with the taxicab metric is a final coalgebra for
$N\otimes -\colon \SquaMS\to \SquaMS$, and that this coalgebra is the Cauchy completion
of the initial algebra.   Turning to $M$, we show that again the
Cauchy completion
of the initial algebra is the final coalgebra.
It would have been pleasing if the Sierpinski carpet $\SC$ were exactly this final coalgebra.
But this is not to be: $\SC\to M\otimes\SC$ is not a short map.
Nevertheless, we shall prove later than $\SC$ is bilipschitz equivalent to the carrier of
final coalgebra
of $M\otimes -$.
In a different direction, forgetting the metric, $\SC$ is the final coalgebra of our functor on $\SquaSet$.

Let $H\colon \A\to \A$ be an endofunctor on any category.
A coalgebra for $H$ is a pair $(A,a)$, where  $a \colon A \to HA$.
Given two colagebras $(A,a)$ and $(B,b)$ for this functor,
a coalgebra morphism is a
morphism $h\colon A \to B$ in $\A$ such that $b\o h  = Hh\o a$:

\[
\xymatrix@C+1pc{A \ar[r]^-{a} \ar[d]_-{h}
& HA \ar[d]^-{Hh}\\
B   \ar[r]_-{b}  &  HB
\]

$(C,\gamma)$ is a final coalgebra if for every $(A,a)$, there is a unique
coalgebra morphism $h\colon A \to C$.

As with initial algebras, a final coalgebra is a final object in the category of coalgebras.

Final coalgebras need not exist, but when they do, they are unique.  Moreover,
if $(C,\gamma)$ is a final coalgebra, then by Lambek's Lemma (the dual of the form that we stated earlier),
$\gamma$ is an isomorphism in the base category $\A$.

§.§ Corecursive algebras

Our work on final coalgebras involves a secondary notion: corecursive algebras.
We bring corecursive algebras into the paper because they generalize final coalgebras
and because the Sierpinski Carpet turns out to be a corecursive algebra in $\SquaMS$.

Let $H\colon \A\to \A$ be an endofunctor on any category.
An algebra $a\colon HA \to A$ is corecursive if for every
coalgebra $e\colon X\to HX$ there is a unique
morphism $e^\dag\colon X \to A$. This means that
$e^\dag = a\o He^\dag \o e$:

\[
\xymatrix@C+1pc{X \ar[r]^-{e} \ar[d]_-{e^\dag}
& HX \ar[d]^-{He^\dag}\\
A  & \ar[l]^-{a}   HA
\]

The map $e^\dag$ is also called the solution to $e$
in the algebra $(A,a)$.

This section contains a number of examples of
corecursive algebras for various functors on categories,
beginning with the following one
on $\Set$.
First fix a real number $0\leq \delta < 1$. The rest of this example
depends on this parameter,
and in later sections we are going to take $\delta = \frac{1}{3}$.
Let  $K = [0,1-\delta]\subset \mathbb{R}$.

For the functor, we take
$H\colon \Set\to \Set$ to be given by
$HX = K\times X$.
For a function $f\colon X\to Y$, $Hf\colon HX \to HY$ is
given by $Hf(\xi,x) = (\xi, f(x))$.
We have an algebra $(I,i)$, where $I$
is the unit interval $[0,1]$, and

\[ i\colon H[0,1] = K \times [0,1] \to [0,1]\]
is given by
$i(\xi, x) = \xi + \delta x$,
for $\xi\in K$ and $x\in I$.

$i\colon HI \to I$ is a corecursive algebra for $H$.

Let  $X$ be a set, and
consider a  coalgebra $(X,e\colon X\to K\times X$).
The function set $I^X = [0,1]^X$ is a complete metric space
under the metric $d(f,g) = \displaystyle{\sup_{x\in X}}\ d_{I}(f(x),g(x))$.
This space is non-empty due to the constant functions.
We have an endofunction $\Phi\colon I^X \to I^X$ given by
$\Phi(f)=  i \o Hf  \o e$.  (To check that $\Phi$ maps into $I^X$,
take any $x\in X$.  For this $x$, write $e(x)$
as $(\xi, y)$. So $\xi\in [0,1-\delta]$.
Then $\Phi(f)(x) = \xi + \delta f(y) \leq (1-\delta) + (\delta \cdot 1) = 1$.)
And $\Phi$ is a contracting map, since $\delta < 1$.
(See Theorem <ref> for a parallel result done in full on this point.)   The fixed points of $\Phi$
are exactly the coalgebra-to-algebra morphisms $X\to I$.
So the Contracting Mapping Theorem
implies our result.

We used that $I$ and $HI$ come with metrics
such that  $I$ is complete, $i$ is short, and $\Phi$ is
a contraction.
We also needed to know that the space $I^X$ is not empty.
(The Contracting Mapping Theorem does not hold for the empty space,
since the empty map has no fixed point.)
This gives many more examples of corecursive algebras.
Also, the method of proof in Proposition <ref>
is one which we shall see again.

Here is a way to think about what is going on.
To discuss a concrete example, let $X = \set{x_0, x_1, \ldots, }$.
A coalgebra structure $e\colon X \to HX$
might be thought of as a system of equations in the real
of the form

\begin{equation}
\label{eq-sys}
\begin{array}{lcl}
x_0 & = & \xi_0 + \delta x_1 \\
x_1 & = & \xi_1 + \delta x_2 \\
& \vdots & \\
\end{array}
\end{equation}

We require that the $x$'s are pairwise distinct.
For each $x\in X$, $e(x)$ belongs to $K\times X$, and rather than write
$e(x_0) = (\xi_0,x_1)$, we adopt a notation suggested by the algebra $(I,\iota)$
and instead write $x_0 = \xi_0 + \delta x_1$.  The abstract notation $(X,e)$
translates to a system as we have exhibited it.
Incidentally, it is not required of a coalgebra that the variable on the right-hand side for $x_i$
be $x_{i+1}$; that variable on the right-hand side could be any of the $x$'s.

Again, $\delta$ is fixed at the outset, and each $\xi_i$ is a number in
$[0,1-\delta]$.  Then a function $e^\dag\colon X \to  I = [0,1]$
satisfying the equation $e^\dag = \iota\o He^\dag \o e$
would correspond to a
solution to the system: a sequence $(r_k)_{k\in \omega}$,
of numbers in $[0,1]$.  We require that $r_k = \xi_k + \delta r_{k+1}$.
The fact that $(I,i)$ is a corecursive algebra is just another way of saying that
every system of equations as in (<ref>)
has a unique solution in $[0,1]$.  We proved this in
Proposition <ref> using the Contracting Mapping Theorem.
Another way to do it is
to explicitly define for each $k\in \omega$ the solution

\[ r_k =
\xi_k + \delta \xi_{k+1}  + \delta^2 \xi_{k+2} + \cdots + \delta^{\ell} \xi_{k+\ell} +\cdots
=\sum_{\ell = 0}^{\infty} \delta^{\ell}\xi_{k+\ell}
\]

(Note that the infinite sum is $\leq (1-\delta ) \sum_{\ell = 0}^{\infty} \delta^{\ell}
That is, if we set $e^\dag(x_k) =\sum_{\ell = 0}^{\infty} \delta^{\ell}\xi_{k+\ell} $,
we have a solution to our system, because

\[%\arraycolsep=1.4pt
\def\arraystretch{1.5}
\begin{array}{lcl}
e^\dag(x_k) & = & \sum_{\ell = 0}^{\infty} \delta^{\ell}\xi_{k+\ell}  \\
& = & \xi_k + \sum_{\ell = 1}^{\infty} \delta^{\ell}\xi_{k+\ell}\\
& = & \xi_k + \sum_{\ell = 0}^{\infty} \delta^{\ell_+1}\xi_{k+\ell+1}\\
& =  & \xi_k + \delta\cdot \sum_{\ell = 0}^{\infty} \delta^{\ell}\xi_{(k+1)+\ell}\\
& =  & \xi_k  + \delta \cdot e^{\dag}(x_{k+1})\\
\end{array}
\]

In our development of this section,
we have adopted the style of trying to use the fixed point equations as much
as possible and the summation idea
as little as possible.

Let us remark that the corecursive algebra structure
can be used to give new proofs of well-known facts.
Here is an example.

Every $x\in [0,1]$ has a
ternary representation: there is a sequence
$m_0, m_1, \ldots, m_k,\ldots$ from $M = \set{0,1,2}$ such that
$x = \sum_k m_k 3^{-(k+1)}$.

We use the same functor $H X = K\times X$ with $K = [0,\frac{2}{3}]$,
and the corecursive algebra of
Proposition <ref>.
Let $X$ be the set of all such sequences.
Let $e\colon X \to HX$ be

\[
(m_0, m_1, \ldots) \quad \mapsto \quad(\frac{1}{3}m_0, (m_1,m_2,\ldots))\in K\times X
\]

That is, we map every sequence to its “head” (an
element of $\frac{1}{3}M$) and tail (a sequence).
Thus, we have a unique $e^\dag \colon X \to I$ so that

\begin{equation}
\label{eq-ternary}
e^\dag(m_0, m_1, \ldots) \quad = \quad
\frac{1}{3} m_0 + \frac{1}{3} e^\dag(m_1, m_2, \ldots )
\end{equation}

Let us verify that $e^\dag$ is surjective.
(It is not injective: the images of
$(0, 2,2,2, \ldots)$ and $(1,0,0,\ldots)$ are both $1/3$.)
The set $X$ carries a natural metric: the distance between
two different sequences
$\vec{m}$ and $\vec{n}$
is $2^{-(K+1)}$, where $K$ is least so that $m_K \neq n_K$.
It is straight forward to verify that with this metric $X$ is compact and $e^\dag$ is continuous.
Thus, its image set $J = e^\dag[X]$
is a non-empty compact subset of $I$. It is easy to check
that $J$ satisfies the following equation

\[
J = \frac{1}{3}J \cup (\frac{1}{3}J  + \frac{1}{3}) +
(\frac{1}{3}J  + \frac{2}{3}).
\]

Indeed, this follows from (<ref>).
But by Hutchinson's Theorem, there is a unique $J\subseteq \mathbb{R}$
satisfying this equation.   Since $I$ itself satisfies it,
we have $J = I$.

With this digression completed, we return to our development.

If a corecursive $H$-algebra $(A,a)$ has an invertible structure map $a$,
then $(A,a^{-1})$ is a final coalgebra for the same functor.
If $(A, a)$ is a final coalgebra, then  $(A,a^{-1})$ is a corecursive algebra.

In the first assertion, a coalgebra-to-algebra morphism $e^\dag\colon (X,e)\to (A,a)$
is the same as a coalgebra-to-coalgebra morphism $e^\dag\colon(X,e)\to (A,a^{-1})$.
In the second assertion, we recall Lambek's Lemma to see that the structure of a final coalgebra is invertible.

Let $e\colon X \to HX$ and $f\colon Y \to HY$
be coalgebras, and let $h\colon X\to Y$ be
a coalgebra morphism.
Let $a\colon HA \to A$ be corecursive algebra.
Then $e^\dag = f^\dag\o h$.

\[
\begin{tikzcd}[column sep=.5in]
X   \arrow[swap]{d}{h}
\arrow[swap,bend right =40]{dd}{e^\dag}
\arrow{r}{e}
& HX  \arrow[swap]{d}{Hh}
\arrow[bend left =40]{dd}{He^\dag}
\\
Y   \arrow[swap]{d}{f^\dag} \arrow{r}{f}
& HY  \arrow[swap]{d}{Hf^\dag}  \\
& HA   \arrow{l}{a}   \\
\end{tikzcd}
\]

The squares commute, and this easily shows that
$f^\dag \o h$ satisfies the equation which defines
$e^\dag$ uniquely.  That is, $f^\dag\circ h = a\circ Hf^\dag \circ Hh \circ e = a\circ H(f^\dag \circ h) \circ e$.
Thus $e^\dag = f^\dag \o h$.

A corecursive algebra $\alpha_0\colon N\times U_0 \to U_0$ on $\Set$

Recall that $N = \set{0,1,2}^2$, and that $U_0 = [0,1]^2$.
We are going to consider the functor $H_0 X = N\times X$ on $\Set$.  We will see shortly how this is related to $H$ from Proposition <ref> above.

Recall from the previous section
our definition of $\alpha_M:M\otimes U_0\rightarrow U_0$, which we proved was an injective morphism in Lemma <ref>.  Here we will introduce some notation towards defining an analogous morphism $\alpha_N:N\otimes U_0\rightarrow U_0$

Let $\shrink\colon N \to U_0$ be given by

\[\shrink(i,j) = (i/3, j/3).
\]

We have an $H_0$-algebra structure $\alpha_0\colon N\times U_0 \to U_0$ given by

\[\alpha_0((i,j),(x,y)) =  \shrink(i,j)+ (1/3)(x,y).\]

$(U_0,\alpha_0\colon N\times U_0 \to U_0)$ is a corecursive algebra for $H_0$ on $\Set$.

Rather than sketching
a proof, let us provide an example that illustrates all of the ideas without the thick notation which
would be necessary in the complete proof.

Let $Z = \set{z_1,z_2}$ and let $e\colon Z \to N\times Z$ be as on the left below:

\[
\begin{array}{lcl}
e(z_1) = ((1,2),z_2)\\
\\
e(z_2) = ((0,2),z_1)\\
\\
\end{array}
\qquad
\begin{array}{lcl}
f(x_1) = (1/3,x_2)\\
f(y_1) = (2/3,y_2)\\
f(x_2) = (0/3,x_1)\\
f(y_2) = (2/3,y_1)\\
\end{array}
\]

We turn $(Z,e)$ into
$(Z_0,f)$, where $Z_0 = \set{x_1,x_2, y_1, y_2}$,
and $f$ is shown on the right above.
The basic idea is that $x_i$ and $y_i$ represent the $x$- and $y$-coordinates of $z_i$.
Please note that $(Z_0,f)$ is a coalgebra for the functor $HX = K\times X$
from the previous section.
(We are taking $\delta = 1/3$. Further note that $\shrink(i,j)$ is always
a pair of numbers in $K = [0,1-\delta]$.)
We apply Proposition <ref>.
That result tells us that there is a
unique coalgebra-to-algebra map $f^\dag\colon Z_0 \to [0,1]$
such that  $f^\dag = \iota \circ Hf^\dag \circ f$.
we have the equations on the left below:

\[
\begin{array}{lcl}
f^\dag(x_1) & = & (1/3) + (1/3)f^\dag(x_2)\\
f^\dag(y_1) & = & (2/3) + (1/3)f^\dag(y_2)\\
f^\dag(x_2) & = & (0/3) + (1/3)f^\dag(x_1)\\
f^\dag(y_2) & = & (2/3) + (1/3)f^\dag(y_1)\\
\end{array}
\qquad
\begin{array}{lcl}
e^\dag(z_1)  & = & \shrink(1,2) + (1/3) e^\dag(z_2)
\\ \\
e^\dag(z_2)  & = & \shrink(0,2) + (1/3) e^\dag(z_1)
\\ \\
\end{array}
\]

We then define $e^\dag\colon Z\to U_0$ by
$e^\dag(z_1) = (f^\dag (x_1), f^\dag (y_1))$,
$e^\dag(z_2) = (f^\dag (x_2), f^\dag (y_2))$.
These imply the equations on the right above.
Moving to the more general and abstract formulation, what we have
here is that $e^\dag = \alpha_0 \o (H_0 e^\dag) \o e$.
This now says that $e^\dag$ is a coalgebra-to-algebra map
for $H_0$.
This shows the existence of $e^\dag$.
For the uniqueness, we would go the other way,
defining an $H$-coalgebra-to-algebra morphism for $f$
from an $H_0$-coalgebra-to-algebra morphism for $e$.

A corecursive algebra $\alpha_N\colon N\otimes U_0 \to U_0$ on $\SquaSet$

Proposition <ref> was a preliminary
result; the main point is
Lemma <ref>,
adaptation  for
the category $\SquaSet$ of square sets.

We have already seen the algebra structure $\alpha_N\colon N \otimes U_0 \to U_0$.
To repeat the definition in different notation:

\[
\begin{array}{lcl}
\alpha_N(n\otimes z) & = & \shrink(n) + \frac{1}{3}(z)
\end{array}
\]

Notice that $n\in N$ here is a pair; earlier we
had written it as $(i,j)$.  Similarly, $z\in U_0$;
earlier we wrote it as $(r,s)$.  It takes quite a few
routine elementary calculations to be sure that $\alpha_N$
is well-defined.  That is, we must check that
if $(n,z) \approx (n',z')$, then $ \shrink(n) + \frac{1}{3}(z) =
\shrink(n') + \frac{1}{3}(z')$.
For example, we  have
$((0,0), (r,1))\approx((0,1),(r,0))$.

\[
\shrink(0,0) + \frac{1}{3}(r,1) =
(\frac{r}{3}, \frac{1}{3}) =
\shrink(0,1) + \frac{1}{3}(r,0)
\]

In $\SquaSet$, this map is an isomorphism: by a few routine calculations, we can easily verify that $\alpha_N(S_{N\otimes U_0}((r,s)))  = (r,s) = S_{U_0}((r,s))$.
(This contrasts with $\alpha_0\colon N\times U_0 \to U_0$.
That map is surjective but not injective.)

$(U_0,\alpha_N\colon N\otimes U_0 \to U_0)$ is a corecursive algebra for $N\otimes X$ on $\SquaSet$.

We are given $e\colon B \to N\otimes B$,
and it is our task to show that there
is a unique $e^\dag$ in  $\SquaSet$
such that $e^\dag = \alpha_N\o (N\otimes e^\dag) \o e$.
We first make a diagram in $\Set$:

\[
\begin{tikzcd}
M_0   \arrow[swap]{d}{S_B} \arrow{r}{\widehat{S_{N\otimes M_0}}}
& N\times M_0  \arrow[swap]{d}{N\times S_B} & \\
B \arrow{r}{\widehat e}
%   \arrow[bend left=30]{rr}{e}
%\arrow[shiftarr = {yshift=20}]{rr}{e^\dag}
\arrow{d}[swap]{e^\dag}
N\times B
\arrow[d,swap, "N\times e^\dag"]
\arrow{r}{i}
N\otimes B
\arrow{d}{h}%{N\otimes e^\dag}
\\
%\arrow[shiftarr = {yshift=-20}]{rr}{F e^\dag}
N\times U_0       \arrow{l}{\alpha_0}
% \arrow[u,swap,shift right = .75ex, "\tau"]
\arrow{r}{\nu}
N\otimes U_0
\arrow[bend left=30]{ll}{\alpha_N}
\end{tikzcd}
\]

$S_B$ and $\alpha_N$ are $\SquaSet$ morphisms, and so what we mean above
is the same maps in $\Set$.
The maps $i$ and $\nu$ are the evident quotient maps.

The morphisms $\widehat{e}$ and $\widehat{S_{N\otimes M_0}}$ are defined in a canonical way,
as follows.
Fix an ordering $<$ on $N$, say the lexicographic order.
First, consider $\widehat{e}$.
Let $\widehat{e}(b)$ be any pair $(n,b') \in N\times B$ such that $e(b) = [\widehat{e}(b)]$
and  $n$ is $<$-least in $N$ such that some $b'$ exists with this property.   This defines $n$ uniquely,
and it is easy to see that $b'$ is also unique.  This is because if $(n,b) \approx (n,b')$,
then $b = b'$.  We see easily that $e = i\o \widehat{e}$.
The morphism $\widehat{S_{N\otimes M_0}}$ is similar.
As an example, $\widehat{S_{N\otimes M_0}}(1/3,0) = ((0,0),(1,0))$.
By the way, despite the notation,
$\widehat{S_{N\otimes M_0}}$ is a morphism in $\Set$ here.

By Proposition <ref>
applied to $\widehat{e}$,  we get $e^\dag$ making the square in the corner commute.
The definitions of
$\widehat{e}$ and $\widehat{S_{N\otimes M_0}}$
imply that the square in the upper-left commutes.  For example, consider $(\frac{1}{3},0)\in M_0$.  $N\times S_B\circ \widehat{S_{N\otimes M_0}}((\frac{1}{3},0)) = N\times S_B((0,0)\times (1,0)) = (0,0)\times S_B((1,0))$  because $(0,0)\times S_B((1,0))$ is the first representative of the class $S_{N\otimes B}((\frac{1}{3},0))$ according to the lexicographic order on $N$.  Similarly, $\widehat{e}\circ S_B((\frac{1}{3},0)) = \widehat{e}(S_B((\frac{1}{3},0))) = (0,0)\times S_B((1,0))$ since $(0,0)\otimes S_B((1,0))$ is the first representation of $S_{N\otimes B}((\frac{1}{3},0))$ according to the lexicographic ordering on $N$ (as opposed to $(1,0)\otimes S_B((0,0))$).
So we get a coalgebra
morphism for the functor $N\times-$.
By Lemma <ref>,
$\widehat{S_{N\otimes M_0}}^\dag = e^\dag\o S_B$.

We claim that  $\widehat{S_{N\otimes M_0}}^\dag = S_{U_0}$.
That is,
we claim that
$S_{U_0}$ satisfies the corecursive algebra condition which defines
$\widehat{S_{N\otimes M_0}}^\dag$:

\[S_{U_0} = \alpha_0 \circ (N\times S_{U_0})
\circ    \widehat{S_{N\otimes M_0} }
\]

We show this with an example.   For example, for
$1/3 < r \leq 2/3$,

\[\begin{array}{lcl}
(\alpha_0 \circ (N\times S_{U_0})
\circ \widehat{S_{N\times M_0}})(r,0)
&  =  & \alpha_0 \circ (N\times S_{U_0})((1,0),(3r-1 ,0))\\
& = & \alpha_0((1,0), S_{U_0}(3r-1,0)) \\
& = & \alpha_0((1,0),  (3r-1,0))\\
& = &  (r,0) \\
& = & S_{U_0}((r,0))\\
\end{array}
\]

All of the other cases are similar.
By uniqueness of
solutions, $S_{U_0}$ is the solution.
The upshot is that at this point we know that
$e^\dag\o S_B =
\widehat{S_{N\otimes M_0}}^\dag =
S_{U_0}$, and hence that
$e^\dag$ is a $\SquaSet$ morphism.

The morphism $h\colon N\otimes B \to N\otimes U_0$ is defined by
$h(n\otimes b) = n\otimes e^\dag(b)$.
To know that this definition is sensible,
we need to know that if $(n,b)\approx (n',b')$ then
$(n,e^\dag(b))\approx (n',e^\dag(b'))$.
However, if $(n,b)\approx (n',b')$, then there are
$z, z'\in M_0$ such that
$(n,z)\approx (n',z')$;  and also $S_B(z) = b$ and $S_B(z') = b'$.
But then $e^\dag(b) = e^\dag(S_B(z)) = S_{U_0}(z)$,
and similarly
$e^\dag(b') =  S_{U_0}(z')$.
And then we indeed to have $(n,e^\dag(b))\approx (n',e^\dag(b'))$.
This checks that $h$ is well-defined,
and that the square in the bottom-right commutes.
In fact the definition of $h$ implies that $h = N\otimes e^\dag$.

We return to our figure above.
The region on the bottom commutes: $ \alpha_N \o \nu = \alpha_0$.
Recalling that $e = i\o \widehat{e}$
and also
$h = N\otimes e^\dag$, a diagram chase shows that we have the
desired equality  $e^\dag = \alpha_N\o (N\otimes e^\dag) \o e$.

We also check that  $e^\dag$ is the  unique solution of $e$ in $\SquaSet$.
Suppose we have a $\SquaSet$ morphism $e^*$ so that
$e^* = \alpha_N\o (N\otimes e^*) \o e$.  We show that $e^* = e^\dag$.
Consider the diagram below:

\[
\begin{tikzcd}
B \arrow{r}{\widehat e}
\arrow[bend left=30]{rr}{e}
%\arrow[shiftarr = {yshift=20}]{rr}{e^\dag}
\arrow{d}[swap]{e^*}
N\times B
\arrow[d,swap, "N\times e^*"]
\arrow{r}{i}
N\otimes B
\arrow{d}{N\otimes e^*}%{N\otimes e^\dag}
\\
%\arrow[shiftarr = {yshift=-20}]{rr}{F e^\dag}
N\times U_0       \arrow{l}{\alpha_0}
% \arrow[u,swap,shift right = .75ex, "\tau"]
\arrow{r}{\nu}
N\otimes U_0
\arrow[bend left=30]{ll}{\alpha_N}
\end{tikzcd}
\]

Since $e^*$ is a morphism in $\SquaSet$, we
have $N\otimes e^*$, as shown.  But the diagram
above is in $\Set$.
The top and bottom commute, as we have seen.
The square on the right commutes, easily.
The verification here is similar to what we saw in the first part of the proof.
And now a diagram chase shows that the square on the left commutes as well:

\[
\begin{array}{lcl}
\alpha_0 \o (N\times e^*) \o \widehat{e} & = & \alpha_N\o \nu \o (N\times e^*) \o \widehat{e}  \\
& = & \alpha_N\o  (N\otimes e^*) \o i \o \widehat{e}  \\
& = & \alpha_N\o  (N\otimes  e^*)  \o e \\
& = & e^*
\end{array}
\]

But this means that $e^*$ is a solution to the $N\times-$ coalgebra $(B,\widehat{e})$.
And so by uniqueness of solutions in $(U_0,\alpha_0)$, $e^* = e^\dag$.

A corecursive algebra $\alpha_N\colon N\otimes U_0 \to U_0$ on Square Metric Spaces

The main result next is that $(U_0,\alpha_N^{-1})$ is a final
$N\otimes-$coalgebra on square metric spaces.
Here the metric on $U_0$ is the taxicab metric.
We need a few prelminary lemmas.
In these, we fix an $N\otimes-$coalgebra on $\SquaMS$,
$(B,\beta:B\rightarrow N\otimes B)$.
We already know that there is a unique $\SquaSet$ morphism $\beta^\dag\colon B\to U_0$.
Also, $\alpha_N$ is an isometry, hence $\alpha_N^{-1}$ is short.
Our main work in this section shows that $\beta^\dag$ is short (on all of $B$),
of course using that $\beta$ is a short map.
The surprising feature of our proof is that we must consider other coalgebras in order to prove the shortness of $\beta^\dag$.
Notice that $(N\otimes B, N\otimes\beta)$

is also an $N\otimes-   $coalgebra.  Furthermore, $\beta\colon B\to N\otimes B$ is a coalgebra morphism.

$(N\otimes \beta)^\dag  =  \alpha_N \o (N\otimes \beta^\dag)$.

Consider the diagram below.  It makes sense because $\alpha_N$ is invertible.

\[
\xymatrix@C+1pc{
N\otimes B \ar[d]_-{N\otimes\beta} \ar[r]^-{N\otimes \beta^\dag}  &
N\otimes U_0 \ar[d]_-{N\otimes \alpha_N^{-1}} \ar[r]^-{\alpha_N} \ar@{=}[dr] &
U_0 \\
N \otimes N\otimes B \ar[r]_-{N\otimes N\otimes\beta^\dag} &
N\otimes (N\otimes U_0) \ar[r]_-{N\otimes\alpha_N} &
N\otimes U_0 \ar[u]_-{\alpha_N}
\]

The triangles commute.  The square on the right
(rotated $90^{o}$ and reflected) then
shows that  $(N\otimes \alpha_N^{-1})^\dag = \alpha_N$.
The square on the left  commutes because when we remove $N$ and turn the arrow
on the right around (from $\alpha_N^{-1}$ to $\alpha_N$), we have the definition of $\beta^\dag$.
That square thus
shows that $N\otimes \beta^\dag$ is a coalgebra morphism.
Applying  Lemma <ref> to it, we see that

\[ (N\otimes \beta)^\dag = (N\otimes \alpha_N^{-1})^\dag  \o (N\otimes \beta^\dag) = \alpha_N \o (N\otimes \beta^\dag).
\]

Let $Z\subseteq B$.  We say that $\beta^\dag$ is short on $Z$ if for all $b,c\in Z$,
$d_{U_0}(\beta^\dag (b), \beta^\dag (c)) \leq d_B(b,c)$.

Also, we write $N\otimes Z$ for  $\set{n\otimes b : n\in N \mbox{ and } b \in Z}$.

Let $Z\subseteq B$ be any set that includes the image $S_{B}[M_0]$.
If $\beta^\dag$ is short on $Z$, then $(N\otimes \beta)^\dag$ is short on $N\otimes Z$.

Let $b,c\in Z$ and $n_1,n_2\in N$.
We may assume that $n_1 \neq n_2$, since if $n_1 = n_2$
this follows easily from the fact that $\alpha_N$ is a short map and $\beta^\dag$ is short on $Z$.
There are $(r_1,s_1), (r_2,s_2)\in M_0$ such that
a geodesic in $N\otimes B$ from $n_1\otimes b$  to $n_2\otimes c$ goes through
$n_1\otimes S_{B}(r_1,s_1)$ and $n_2 \otimes S_{B}(r_2,s_2)$.
We are going to write $S$ for $S_B$ to save on some notation.
We have

\[
\begin{array}{cll}
& d_{N\otimes B}(n_1\otimes b, n_2\otimes c)  \\ \\
= &
d(n_1\otimes b, n_1\otimes S((r_1,s_1)) + d(n_1 \otimes S((r_1,s_1)), n_2 \otimes S((r_2,s_2)) + d(n_2 \otimes S((r_2,s_2)), n_2\otimes c)
&(1) \\ \\
= & \frac{1}{3} d_B(b, S((r_1,s_1))) + d_{N\otimes B}(n_1 \otimes S((r_1,s_1))), n_2 \otimes S((r_2,s_2)) + \frac{1}{3} d_B(S((r_2,s_2)), c)
&(2)  \\ \\
\geq &
\frac{1}{3} d_{U_0}(\beta^\dag(b), (r_1,s_1))  + d_{N\otimes U_0}(n_1 \otimes (r_1,s_1),  n_2 \otimes (r_2,s_2)) +
\frac{1}{3} d_{U_0}((r_2,s_2), \beta^\dag(c))
\\ \\
= &  d_{U_0}( \shrink(n_1) + \frac{1}{3}\beta^\dag(b),  \shrink(n_1) +\frac{1}{3}(r_1,s_1))  \\
&  + d_{U_0}(\shrink(n_1) + \frac{1}{3}(r_1,s_1),  \shrink(n_2)  +  \frac{1}{3}(r_2,s_2))  \\
& +
d_{U_0}( \shrink(n_2) +\frac{1}{3} (r_2,s_2), \shrink(n_2) + \frac{1}{3} \beta^\dag(c))
\\ \\
\geq &  d_{U_0}(\shrink(n_1) +\frac{1}{3} \beta^\dag (b), \shrink(n_2) + \frac{1}{3}\beta^\dag (c))
&(5)  \\ \\
= & d_{U_0}(\alpha_N((N\otimes\beta^\dag)(n_1,b)), \alpha_N((N\otimes\beta^\dag)(n_2,c)))
& (6) \\ \\
=  & d_{U_0}((N\otimes \beta)^\dag(n_1\otimes b), (N\otimes \beta)^\dag(n_2\otimes c))
\end{array}
\]

In (1), the distances are in $N\otimes B$.  (1) holds by the choice of $(r_1,s_1)$ and $(r_2,s_2)$.
In (2), we are using Corollary <ref>, the result on distances in a single copy of  $X$ inside of $N\otimes X$.
(3) uses
the assumption that $\beta^\dag$ is short on $Z$,  and the fact that $\beta^\dag \o S_B$ is the inclusion.
It also uses Proposition <ref> in the middle.

(4) uses two facts about distances in $U_0$.  Let $x,y,z\in U_0$.
First, $c \cdot d(x,y) = d(c\cdot x,c\cdot y)$ when $0\leq c \leq 1$.
Second, $d(x,y) = d(x+z,y+z)$, provided $x +z$ and $y+z$ belong to $U_0$.
And in the middle summand of (4), we used the fact that $\alpha_N\colon N\otimes U_0 \to U_0$ is
a short map, and the definition of $\alpha_N$.

(5) uses the triangle inequality in $U_0$.
(6) uses the definition of $\alpha_N$.
(7) is by Lemma <ref>.

This completes the proof.

Let $(B,\beta\colon B\to N\otimes B)$, and let $k\in \omega$.
There is a coalgebra $(C,\gamma\colon C\to N\otimes C)$,
a coalgebra morphism $h\colon B\to C$, and
a set $Z\subseteq C$ so that

* $S_C[M_0] \subseteq Z$.

* $\gamma^\dag$ is short on $Z$.

* For every $c_1\in C$ there is some $c_2\in Z$ such that
$d_C(c_1,c_2) \leq \frac{2}{3^k}$, and also

$d_{U_0}(\gamma^{\dag}(c_1),\gamma^\dag(c_2)) \leq \frac{2}{3^k}$.

By induction on $k$.
For $k = 0$, we take $(C,\gamma) = (B,\beta)$,   $h = \id_B$, and $Z = S_B[M_0]$.
Every point in $B$ is at a distance $\leq 2$ from $S_B((0,0))$, and every point in $U_0$ is
at distance at most $2$ from every other point. $\gamma^\dag = \beta^\dag$ is
short on $Z=M_0$ because of ($\sqtwo$), which requires that distances on the boundary are bounded below by the distances determined by the taxicab metric.

Assume our result for $k$, and fix $(C,\gamma)$, $h$, and $Z$ with the required properties.
The map $\gamma$ is a coalgebra morphism $\gamma\colon C\to N\otimes C$.
Consider $(N\otimes C,N\otimes \gamma)$, $\gamma\o h$ and $N\otimes Z$.

We check that $S_{N\otimes C}[M_0] \subseteq N\otimes Z$.
Let $(r,s)\in M_0$.
Recall the $\SquaSet$ structure
$S_{N\otimes M_0}\colon M_0\to N\otimes M_0$.
It is a general feature of the how