nLab list of notable initial algebras and terminal coalgebras


A list of notable endofunctors, and their initial algebras/terminal coalgebras.

Nonexistent (co)algebras are labelled with ‘/’, and unknown ones with ‘?’.

Base categoryEndofunctorInitial AlgebraFinal CoalgebraNote, reference
SetXXX \mapsto X\varnothing11
SetX1+XX \mapsto 1 + X\mathbb{N}Conatural numbers \mathbb{N}^\inftyextended natural number
SetXA+XX \mapsto A + XA×A \times \mathbb{N}A×+1A \times \mathbb{N} + 1, ie conatural numbers “terminated” (when they aren’t \infty) with AApartial map classifier
SetXX+XX \mapsto X + X or X2×XX \mapsto 2 \times X\emptyset2 2^\mathbb{N} (i.e. one definition of Stream 22)
SetXA×XX \mapsto A \times X\emptysetA A^\mathbb{N} (i.e. one definition of Stream AA)sequence, writer monad, stream
SetXX×XX \mapsto X \times X or X[2,X]X \mapsto [2, X][2,]\emptyset \simeq [2, \emptyset]1 (the unique infinite unlabelled binary tree)
SetX[A,X]X \mapsto [A, X][A,][A, \emptyset]1reader monad
SetX1+A×XX \mapsto 1 + A \times XList AAanother definition of Stream AA; i.e. potentially infinite List AAlist, stream
SetX1+A×X 2X \mapsto 1 + A \times X^2Finite binary tree with AA-labelled nodesPotentially infinite binary tree with AA-labelled nodestree
SetXB+A×X nX \mapsto B + A \times X^nFinite nn-ary tree with AA-labelled nodes and BB-labelled leavesPotentially infinite nn-ary tree with AA-labelled nodes with and BB-labelled leaves
SetXB+A×List(X)X \mapsto B + A \times \text{List}(X)Finite tree with AA-labelled nodes and BB-labelled leavesPotentially infinite tree with AA-labelled nodes with and BB-labelled leavesThe number of subtrees is not fixed to a particular nn, it could be any number
SetXO×[I,X]X \mapsto O \times [I, X]O×[I,]O \times [I, \emptyset]Potentially infinite Moore machine
SetX[I,O×X]X \mapsto [I, O \times X][I,][I, \emptyset]Potentially infinite Mealy machine
SetX𝒫(X)X \mapsto \mathcal{P}(X)//
SetX𝒫 fin(X)X \mapsto \mathcal{P}_{\text{fin}}(X)Finite rooted forestsPotentially infinite finitely-branching rooted forests
Setpolynomial endofunctorW-typeM-type
Bipointed SetsXXXX \mapsto X \vee Xdyadic rational numbers in the interval [0,1][0,1]The closed interval [0,1][0,1] \subseteq \mathbb{R}coalgebra of the real interval
linearly ordered setsXωXX \mapsto \omega \cdot X, where ωX\omega \cdot X is the cartesian product of the natural numbers with the underlying set of XX, equipped with the lexicographic order.\emptysetThe non-negative real numbers 0\mathbb{R}_{\geq 0}real number
Archimedean ordered fieldsXXX \mapsto X the identity functorThe rational numbers \mathbb{Q}The real numbers \mathbb{R}
Archimedean ordered fieldsX𝒟(X)X \mapsto \mathcal{D}(X) where 𝒟(X)\mathcal{D}(X) is the Archimedean ordered field of two-sided Dedekind cuts of XXThe real numbers \mathbb{R}The real numbers \mathbb{R}
Archimedean ordered fieldsX𝒞(X)X \mapsto \mathcal{C}(X) where 𝒞(X)\mathcal{C}(X) is the quotient of Cauchy sequences in the Archimedean ordered field XXThe HoTT book real numbers H\mathbb{R}_HThe Dedekind real numbers \mathbb{R}These are the same objects in the presence of excluded middle or countable choice.
Any categoryThe constant functor XAX \mapsto A given object AAAAAA
Any categoryThe identity functor XXX \mapsto Xinitial objectterminal object
Any extensive categoryX1+XX \mapsto 1 + X given terminal object 11 and coproduct ++natural numbers object?
Any closed abelian categoryXI(AX)X \mapsto I \sqcup (A \otimes X) given tensor unit II, tensor product \otimes, coproduct \sqcup, and object AAtensor algebra of AAcofree coalgebra over AAtensor algebra, cofree coalgebra
\infty -GrpdXΣXX \mapsto \Sigma Xsphere spectrum 𝕊\mathbb{S}?suspension

Last revised on March 24, 2024 at 22:50:46. See the history of this page for a list of all contributions to it.