\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{terminal coalgebra for an endofunctor}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{algebra}{}\paragraph*{{Algebra}}\label{algebra}

[[!include higher algebra - contents]]

\hypertarget{induction}{}\paragraph*{{Induction}}\label{induction}

[[!include induction - contents]]

\hypertarget{terminal_coalgebras}{}\section*{{Terminal coalgebras}}\label{terminal_coalgebras}

\noindent\hyperlink{introduction}{Introduction}\dotfill \pageref*{introduction} \linebreak
\noindent\hyperlink{details}{Details}\dotfill \pageref*{details} \linebreak
\noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak
\noindent\hyperlink{UnitInterval}{Unit interval in the real line}\dotfill \pageref*{UnitInterval} \linebreak
\noindent\hyperlink{categorified_example_trees}{Categorified example: Trees}\dotfill \pageref*{categorified_example_trees} \linebreak
\noindent\hyperlink{fractals}{Fractals}\dotfill \pageref*{fractals} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{introduction}{}\subsection*{{Introduction}}\label{introduction}

A \textbf{terminal coalgebra}, also called \textbf{final coalgebra}, for an [[endofunctor]] $F$ on a category $C$ is a [[terminal object]] in the category of [[coalgebra for an endofunctor|coalgebras]] of $F$.

If $F$ has a terminal coalgebra $\alpha\colon X \to F(X)$, then $X$ is isomorphic to $F(X)$ (see below); in this sense, $X$ is a fixed point of $F$. Being terminal, $X$ is the largest fixed point of $F$ in that there is a map to $X$ to any other fixed point (indeed, any other coalgebra), and this map is an [[injection]] if $C$ is [[Set]].

The dual concept is [[initial algebra]]. Just as initial algebras allow for [[induction]] and [[recursion]], so terminal coalgebras allow for [[coinduction]] and [[corecursion]].

\hypertarget{details}{}\subsection*{{Details}}\label{details}

Given two coalgebras $(x, \eta: x \to F x)$, $(y, \theta: y \to F y)$, a coalgebra map is a morphism $f: x \to y$ which respects the coalgebra structures:

\begin{displaymath}
\theta \circ f = F(f) \circ \eta
\end{displaymath}
A \textbf{terminal coalgebra} (usually called a \emph{final coalgebra} in the literature) is of course a terminal object in the category of coalgebras. Many data structures can be expressed as terminal coalgebras of suitable endofunctors; a simple but useful theorem says that terminal coalgebras $x$ are ``fixed points'' of their endofunctors, in that $F x \cong x$. This is the dual form of a theorem discovered long ago by Lambek:

\begin{theorem}
\label{}\hypertarget{}{}
If $(x, \theta: x \to F x)$ is a terminal object in the category of $F$-coalgebras, then $\theta$ is an isomorphism.

\end{theorem}
\begin{proof}
Define a coalgebra structure on $F x$ by $F\theta: F x \to F F x$. By terminality of $x$, there is a unique coalgebra map $f: F x \to x$. We claim this is inverse to $\theta$. Indeed, by how we defined the coalgebra structure on $F x$, it is tautological that $\theta$ is a coalgebra map. By terminality of $x$ again, this gives an equation of coalgebra maps:

\begin{displaymath}
f \circ \theta = 1_x.
\end{displaymath}
On the other hand,

\begin{displaymath}
\theta \circ f = F(f) \circ F(\theta) = F(f \circ \theta) = F(1_x) = 1_{F x}
\end{displaymath}
where the first equation holds because $f$ is a coalgebra map. This completes the proof.

\end{proof}
To construct terminal coalgebras, the following result is useful and practical. See [[Adámek's theorem on terminal coalgebras]] for an extension of this result.

\begin{theorem}
\label{Adam}\hypertarget{Adam}{}
\textbf{(Ad\'a{}mek)} If $C$ has a terminal object $1$ and the limit $L$ of the diagram

\begin{displaymath}
\ldots F^3 1 \stackrel{F^2 !}{\to} F^2 1 \stackrel{F !}{\to} F 1 \stackrel{!}{\to} 1 \qquad (1)
\end{displaymath}
exists in $C$ and $F$ preserves this limit, then the limit carries a structure of terminal coalgebra.

\end{theorem}
\begin{proof}
Let $\pi_n: L \to F^n 1$ be the $n^{th}$ projection of the limiting cone. Then we have a cone from $F L$ to the diagram (1) whose components are

\begin{displaymath}
F L \stackrel{F\pi_n}{\to} F^{n+1} 1 \stackrel{F^n !}{\to} F^n 1
\end{displaymath}
and the induced map $F L \to L$ to the limit is invertible by hypothesis; let $\theta: L \to F L$ be the inverse. We claim the coalgebra $(L, \theta)$ is terminal.

Indeed, suppose $(x, \eta: x \to F x)$ is any coalgebra. We recursively define maps $f_n: x \to F^n 1$: let $f_0: x \to 1$ be the unique map, and

\begin{displaymath}
f_{n+1} = F(f_n) \circ \eta
\end{displaymath}
It is easily checked by induction that we have a commutative diagram

\begin{displaymath}
\itexarray{
F^{n+1}1 & \stackrel{F^n !}{\to} & F^n 1 \\
 ^\mathllap{F f_n} \uparrow & \nwarrow  ^\mathrlap{f_{n+1}} & \uparrow ^\mathrlap{f_n} \\
F x & \underset{\eta}{\leftarrow} & x
}
\end{displaymath}
defining a cone from $x$ to the diagram (1), and inducing a map $f: x \to L$ such that the following diagram commutes:

\begin{displaymath}
\itexarray{
F L & \stackrel{\theta^{-1}}{\to} & L \\
 ^\mathllap{F f} \uparrow & & \uparrow  ^\mathrlap{f} \\
F x & \underset{\eta}{\leftarrow} & x
}
\end{displaymath}
This diagram gives the fact that $f$ is a coalgebra map. Moreover, any coalgebra map $f: x \to L$ leads to a sequence $f_n = \pi_n \circ f$ that satisfies $f_{n+1} = F(f_n) \circ \eta$, by gluing the second diagram to the commutative diagram

\begin{displaymath}
\itexarray{
F^{n+1}1 & \stackrel{F^n!}{\to} & F^n 1 \\
 ^\mathllap{F \pi_n} \uparrow & \nwarrow  ^\mathrlap{\pi_{n+1}} & \uparrow  ^\mathrlap{\pi_n} \\
F L & \underset{\theta^{-1}}{\to} & L
}
\end{displaymath}
so that we were forced to define the $f_n$ by recursion as we did, and the coalgebra map $f: x \to L$ is therefore uniquely determined.

\end{proof}
\hypertarget{examples}{}\subsection*{{Examples}}\label{examples}

\hypertarget{UnitInterval}{}\subsubsection*{{Unit interval in the real line}}\label{UnitInterval}

As first observed by [[Peter Freyd]], the [[unit interval]] $[0, 1] \hookrightarrow \mathbb{R}$ inside the [[real line]] can be characterized as a suitable terminal coalgebra. There are various ways of realizing this; we give one (but see remarks below).

Consider the [[category]] of [[intervals]] $Int$, i.e., linearly ordered sets with separate [[top]] and [[bottom]] elements $1$ and $0$, and let

\begin{displaymath}
F: Int \to Int
\end{displaymath}
be the endofunctor which takes an interval $X$ to $X \vee X$, the linear order obtained by taking two copies of $X$ and gluing the top element of the first copy to the bottom element of the second. The real interval $[0, 1]$ becomes a coalgebra if we identify $[0, 1] \vee [0, 1]$ with $[0, 2]$ and consider the multiplication-by-2 map $[0, 1] \to [0, 2]$ as giving a coalgebra structure.

\begin{theorem}
\label{}\hypertarget{}{}
The interval $[0, 1]$ is terminal in the category of coalgebras.

\end{theorem}
\begin{proof}
Given any coalgebra structure $f: X \to X \vee X$, any value $f(x)$ lands either in the ``lower'' half (the first $X$ in $X \vee X$), the ``upper'' half (the second $X$ in $X \vee X$), or at the precise spot between them, where the top element in the first copy is glued to the bottom element of the second. Intuitively, one could think of a coalgebra structure $\theta: X \to X \vee X$ as giving an automaton where on input $x_0$ there is output of the form $(x_1, h_1)$, where $h_1$ is either ``upper'', ``lower'', or ``between''. By iteration, this generates a behavior stream $(x_n, h_n)$. Interpreting upper as 1 and lower as 0, the $h_n$ form a binary expansion to give a number between 0 and 1, and therefore we have an interval map $X \to [0, 1]$ which sends $x_0$ to that number. Of course, should we ever hit $(x_n, between)$, we have a choice to resolve it as either $(bottom_X, upper)$ or $(top_X, lower)$ and continue the stream, but these streams are identified, and this corresponds to the identification of binary expansions

\begin{displaymath}
.h_1... h_{n-1} 100000... = .h_1... h_{n-1}011111...
\end{displaymath}
as real numbers. In this way, we produce a unique well-defined interval map $X \to [0, 1]$, so that $[0, 1]$ is the terminal coalgebra.

\end{proof}
\begin{remark}
\label{}\hypertarget{}{}
(More material can be found at [[coalgebra of the real interval]].)

\begin{enumerate}%
\item The same proof shows that we could have considered instead the category of [[poset|posets]] with separate top and bottom, or even the category of sets with separate top and bottom, with an analogous endofunctor. The reason we chose the category of intervals is (besides the availability of the succinct term `interval') to indicate that choice of interval $[0, 1]$, as the model which classifies the [[geometric realization]] functor, can be justified on the grounds of a universal property, as shown by this theorem.


\item Freyd, in his original \hyperlink{Freyd}{post} on this result, was inspired by a similar theorem due to \hyperlink{PP}{Pavlovic and Pratt}, that the half-open interval $[0, \infty)$ can be described as the terminal coalgebra for the endofunctor that sends a linearly ordered set $X$ to $\omega \times X$ with the dictionary order.


\item The theorem holds in an arbitrary topos (with $[0, 1]$ being the interval of [[real number object|Dedekind reals]]), provided that the word ``separate'' is interpreted correctly:

\begin{displaymath}
\forall p\colon P\; (\neg(0 = p) \vee \neg(1 = p))
\end{displaymath}
and provided that the process of gluing endpoints is given correctly. See Johnstone's [[Elephant]], section D.4.7, for an extended discussion.



\end{enumerate}
\end{remark}
\hypertarget{categorified_example_trees}{}\subsubsection*{{Categorified example: Trees}}\label{categorified_example_trees}

The notion of terminal coalgebra may be categorified. For example, given a 2-category $C$ and a (pseudo) functor $F: C \to C$, one may speak of a 2-terminal (pseudo) coalgebra.

A theoretically important example is the [[tree|category of trees]], seen as a 2-terminal coalgebra for the endofunctor on $Cat$ which takes a locally small category $C$ to its small-coproduct cocompletion. Further discussion of this point is given at [[pure set]].

The small-coproduct cocompletion of $C$ is given by a comma category construction: objects are pairs $(X, F: X_d \to C)$ where $X$ is a set and $F$ is a functor whose domain is the discrete category on $X$, denoted $X_d$. A morphism from $(X, F)$ to $(Y, G)$ is a pair $(f, \Phi)$ where $f: X \to Y$ is a function and $\Phi: F \to G \circ f_d$ is a natural transformation. This category is denoted $Set \wr C$; it is called a ``[[categorical wreath product]]'' (see also the discussion at [[club]]).

Ad\'a{}mek's theorem may be adapted to this 2-categorical situation. The iterated [[categorical wreath product|wreath product]] $(Set \wr)^n 1$ may be identified with the category of $n$-stage trees:

\begin{displaymath}
(Set \wr)^n 1 = Set^{[n]^{op}}
\end{displaymath}
where $[n]$ is the linear order $1 \leq 2 \leq \ldots \leq n$. Or, what is the same, the category of presheaves $T: [n+1]^{op} \to Set$ with the condition that $T(0) = 1$ is terminal; the element of $T(0)$ is considered to be the root of the tree.

Indeed, we realize an explicit equivalence

\begin{displaymath}
\Sigma: Set \wr Set^{[n]^{op}} \simeq Set^{[n+1]^{op}}
\end{displaymath}
by defining $\Sigma(X, F: X \to Set^{[n]^{op}})$ to be the functor $T: [n+1]^{op} \to Set$ that on the object level takes $1$ to $X$, and $i+1$ to

\begin{displaymath}
\sum_{x \in X} F(x)(i).
\end{displaymath}
On the morphism level, $T(i+1 \to i)$ is the coproduct of morphisms

\begin{displaymath}
\sum_{x \in X} F(x)(i \to i-1)
\end{displaymath}
(and this makes sense for all $1 \leq i \leq n$ under the convention $F(x)(0) = 1$).

The morphism

\begin{displaymath}
(Set \wr)^n !: (Set \wr)^n Set \to (Set \wr)^n 1
\end{displaymath}
used in Ad\'a{}mek's theorem is identified with the restriction functor

\begin{displaymath}
Set^{[n+1]^{op}} \to Set^{[n]^{op}}
\end{displaymath}
which restricts presheaves along the inclusion $[n] \hookrightarrow [n+1]$.

The 2-limit of the diagram in Ad\'a{}mek's theorem is then

\begin{displaymath}
Set^{\omega^{op}},
\end{displaymath}
aka the [[tree|category of trees]], where $\omega$ is the colimit of the finite ordinals $[n]$. The statement that the category of trees is equivalent to its small-coproduct cocompletion says that the category of trees is equivalent to the category of forests.

\hypertarget{fractals}{}\subsubsection*{{Fractals}}\label{fractals}

There is a [[category theory|category theoretic]] treatments of the self-similarity found in [[fractals]] in terms of terminal coalgebras, see \hyperlink{Leinster10}{Leinster 10}, \hyperlink{BhattacharyaMossRatnayakeRose}{Bhattacharya-Moss-Ratnayake-Rose}.

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

Terminal coalgebras are the [[categorical semantics]] of [[coinductive types]], for instance [[M-types]].

\hypertarget{references}{}\subsection*{{References}}\label{references}

\begin{itemize}%
\item [[Peter Freyd]], \emph{Real coalgebra} Mailing to the categories list, Dec. 22, 1f999. (\href{http://www.mta.ca/~cat-dist/catlist/1999/realcoalg}{link})


\item [[Dusko Pavlovic]], [[Vaughan Pratt]], \emph{On coalgebra of real numbers}, 1999. (\href{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.5204}{web})



\end{itemize}
Cross-relations between algebraic and coalgebraic aspects of real numbers may be found in this article:

\begin{itemize}%
\item [[Peter Freyd]], \emph{Algebraic Real Analysis, Theor.} Appl. Cat., vol. 20, no. 10 (2008), 215-308. (\href{http://www.tac.mta.ca/tac/volumes/20/10/20-10abs.html}{link})

\end{itemize}
For [[category theory|category theoretic]] treatments of the self-similarity found in [[fractals]] in terms of terminal coalgebras, see

\begin{itemize}%
\item [[Tom Leinster]], \emph{A general theory of self-similarity}, (\href{https://arxiv.org/abs/1010.4474}{arXiv:1010.4474})


\item Prasit Bhattacharya, Lawrence S. Moss, Jayampathy Ratnayake, and Robert Rose, \emph{Fractal Sets as Final Coalgebras Obtained by Completing an Initial Algebra}, (\href{http://www3.nd.edu/~pbhattac/papers/Sierpinski.pdf}{pdf})



\end{itemize}
[[!redirects terminal coalgebra]] [[!redirects terminal coalgebras]] [[!redirects final coalgebra]] [[!redirects final coalgebras]]

[[!redirects terminal coalgebra of an endofunctor]] [[!redirects terminal coalgebras of an endofunctor]]

[[!redirects terminal coalgebra of the endofunctor]] [[!redirects terminal coalgebras of the endofunctor]]

[[!redirects terminal coalgebra]]

[[!redirects terminal coalgebra of an endofunctor]] [[!redirects terminal coalgebras of an endofunctor]] [[!redirects terminal coalgebras of an endofunctors]]



\end{document}