symmetric monoidal (∞,1)-category of spectra
A terminal coalgebra, also called final coalgebra, for an endofunctor on a category is a terminal object in the category of coalgebras of .
If has a terminal coalgebra , then is isomorphic to (see below); in this sense, is a fixed point of . Being terminal, is the largest fixed point of in that there is a map to from any other fixed point (indeed, any other coalgebra), and this map is an injection if 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.
Given two coalgebras , , a coalgebra map is a morphism which respects the coalgebra structures:
A terminal coalgebra (usually called a 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 are “fixed points” of their endofunctors, in that . This is the dual form of a theorem discovered long ago by Lambek:
If is a terminal object in the category of -coalgebras, then is an isomorphism.
Define a coalgebra structure on by . By terminality of , there is a unique coalgebra map . We claim this is inverse to . Indeed, by how we defined the coalgebra structure on , it is tautological that is a coalgebra map. By terminality of again, this gives an equation of coalgebra maps:
On the other hand,
where the first equation holds because is a coalgebra map. This completes the 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.
(Adámek) If has a terminal object and the limit of the diagram
exists in and preserves this limit, then the limit carries a structure of terminal coalgebra.
Let be the projection of the limiting cone. Then we have a cone from to the diagram (1) whose components are
and the induced map to the limit is invertible by hypothesis; let be the inverse. We claim the coalgebra is terminal.
Indeed, suppose is any coalgebra. We recursively define maps : let be the unique map, and
It is easily checked by induction that we have a commutative diagram
defining a cone from to the diagram (1), and inducing a map such that the following diagram commutes:
This diagram gives the fact that is a coalgebra map. Moreover, any coalgebra map leads to a sequence that satisfies , by gluing the second diagram to the commutative diagram
so that we were forced to define the by recursion as we did, and the coalgebra map is therefore uniquely determined.
As first observed by Peter Freyd, the unit interval 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 , i.e., linearly ordered sets with separate top and bottom elements and , and let
be the endofunctor which takes an interval to , the linear order obtained by taking two copies of and gluing the top element of the first copy to the bottom element of the second. The real interval becomes a coalgebra if we identify with and consider the multiplication-by-2 map as giving a coalgebra structure.
The interval is terminal in the category of coalgebras.
Given any coalgebra structure , any value lands either in the “lower” half (the first in ), the “upper” half (the second in ), 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 as giving an automaton where on input there is output of the form , where is either “upper”, “lower”, or “between”. By iteration, this generates a behavior stream . Interpreting upper as 1 and lower as 0, the form a binary expansion to give a number between 0 and 1, and therefore we have an interval map which sends to that number. Of course, should we ever hit , we have a choice to resolve it as either or and continue the stream, but these streams are identified, and this corresponds to the identification of binary expansions
as real numbers. In this way, we produce a unique well-defined interval map , so that is the terminal coalgebra.
(More material can be found at coalgebra of the real interval.)
The same proof shows that we could have considered instead the category of 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 , as the model which classifies the geometric realization functor, can be justified on the grounds of a universal property, as shown by this theorem.
Freyd, in his original post on this result, was inspired by a similar theorem due to Pavlovic and Pratt, that the half-open interval can be described as the terminal coalgebra for the endofunctor that sends a linearly ordered set to with the dictionary order.
The theorem holds in an arbitrary topos (with being the interval of Dedekind reals), provided that the word “separate” is interpreted correctly:
and provided that the process of gluing endpoints is given correctly. See Johnstone’s Elephant, section D.4.7, for an extended discussion.
The notion of terminal coalgebra may be categorified. For example, given a 2-category and a (pseudo) functor , one may speak of a 2-terminal (pseudo) coalgebra.
A theoretically important example is the category of trees, seen as a 2-terminal coalgebra for the endofunctor on which takes a locally small category to its small-coproduct cocompletion. Further discussion of this point is given at pure set.
The small-coproduct cocompletion of is given by a comma category construction: objects are pairs where is a set and is a functor whose domain is the discrete category on , denoted . A morphism from to is a pair where is a function and is a natural transformation. This category is denoted ; it is called a “categorical wreath product” (see also the discussion at club).
Adámek’s theorem may be adapted to this 2-categorical situation. The iterated wreath product may be identified with the category of -stage trees:
where is the linear order . Or, what is the same, the category of presheaves with the condition that is terminal; the element of is considered to be the root of the tree.
Indeed, we realize an explicit equivalence
by defining to be the functor that on the object level takes to , and to
On the morphism level, is the coproduct of morphisms
(and this makes sense for all under the convention ).
The morphism
used in Adámek’s theorem is identified with the restriction functor
which restricts presheaves along the inclusion .
The 2-limit of the diagram in Adámek’s theorem is then
aka the category of trees, where is the colimit of the finite ordinals . 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.
There is a category theoretic treatments of the self-similarity found in fractals in terms of terminal coalgebras, see Leinster 10, Bhattacharya-Moss-Ratnayake-Rose.
A list of notable endofunctors, and their initial algebras/terminal coalgebras.
Nonexistent (co)algebras are labelled with ‘/’, and unknown ones with ‘?’.
Base category | Endofunctor | Initial Algebra | Final Coalgebra | Note, reference |
---|---|---|---|---|
Set | Const | |||
Set | ||||
Set | Conatural numbers | extended natural number | ||
Set | , ie conatural numbers “terminated” (when they aren’t ) with | partial map classifier | ||
Set | or | (i.e. one definition of Stream ) | ||
Set | (i.e. one definition of Stream ) | sequence, writer monad, stream | ||
Set | or | 1 (the unique infinite unlabelled binary tree) | ||
Set | 1 | reader monad | ||
Set | List | another definition of Stream ; i.e. potentially infinite List | list, stream | |
Set | Finite binary tree with -labelled nodes | Potentially infinite binary tree with -labelled nodes | tree | |
Set | Finite -ary tree with -labelled nodes and -labelled leaves | Potentially infinite -ary tree with -labelled nodes with and -labelled leaves | ||
Set | Finite tree with -labelled nodes and -labelled leaves | Potentially infinite tree with -labelled nodes with and -labelled leaves | The number of subtrees is not fixed to a particular , it could be any number | |
Set | Potentially infinite Moore machine | |||
Set | Potentially infinite Mealy machine | |||
Set | / | / | ||
Set | Finite rooted forests | Potentially infinite finitely-branching rooted forests | ||
Set | polynomial endofunctor | W-type | M-type | |
Bipointed Sets | dyadic rational numbers in the interval | The closed interval | coalgebra of the real interval | |
linearly ordered sets | , where is the cartesian product of the natural numbers with the underlying set of , equipped with the lexicographic order. | The non-negative real numbers | real number | |
Archimedean ordered fields | the identity functor | The rational numbers | The real numbers | |
Archimedean ordered fields | where is the Archimedean ordered field of two-sided Dedekind cuts of | The real numbers | The real numbers | |
Archimedean ordered fields | where is the quotient of Cauchy sequences in the Archimedean ordered field | The HoTT book real numbers | The Dedekind real numbers | These are the same objects in the presence of excluded middle or countable choice. |
Any category | The constant functor given object | |||
Any category | The identity functor | initial object | terminal object | |
Any extensive category | given terminal object and coproduct | natural numbers object | ? | |
Any closed abelian category | given tensor unit , tensor product , coproduct , and object | tensor algebra of | cofree coalgebra over | tensor algebra, cofree coalgebra |
-Grpd | sphere spectrum | ? | suspension |
Terminal coalgebras are the categorical semantics of coinductive types, for instance M-types.
Peter Freyd, Real coalgebra Mailing to the categories list, Dec. 22, 1f999. (link)
Dusko Pavlovic, Vaughan Pratt, On coalgebra of real numbers, 1999. (web)
Cross-relations between algebraic and coalgebraic aspects of real numbers may be found in this article:
For category theoretic treatments of the self-similarity found in fractals in terms of terminal coalgebras, see
Tom Leinster, A general theory of self-similarity, (arXiv:1010.4474)
Prasit Bhattacharya, Lawrence S. Moss, Jayampathy Ratnayake, and Robert Rose, Fractal Sets as Final Coalgebras Obtained by Completing an Initial Algebra, (pdf)
Last revised on January 3, 2024 at 22:23:15. See the history of this page for a list of all contributions to it.