# A functor whose initial algebra is another's terminal coalgebra

Edit: the question was unclear, so prompted by the comments and answers I've tried to clarify things.

A colleague has asked me whether, or under what conditions, it is possible, given a sufficiently nice functor $F \colon \mathrm{Set} \to \mathrm{Set}$ with terminal coalgebra $\nu F$, to find another $F' \colon \mathrm{Set} \to \mathrm{Set}$ whose initial algebra $\mu F'$ is isomorphic to $\nu F$, with the two structure maps being inverses up to this isomorphism.

In the case m'colleague is considering, F is the structure functor of an algebraic signature and $\nu F$ is the set of possibly infinite terms coinductively generated from it. Apparently the same set of terms can be generated inductively from a strictly larger signature, whose structure functor would then have an initial algebra, and he would like to know if there is a more abstract category-theoretic perspective on this situation. (Note that F and F' will in general not be the same.)

It's an interesting question, and I'd like to help, but I'll be horribly busy for the next while and won't have time. Any ideas on where he could start looking?

-
what do you mean with "νF′ is isomorphic to μF", in what category ? In Set? –  Buschi Sergio Feb 21 '11 at 17:57
Yes, in Set, certainly, or in F-Alg or F'-Coalg if that's possible. –  Finn Lawler Feb 21 '11 at 18:37
No idea where to look, but maybe I'm not clear on the constraints of the problem. Suppose for example F is polynomial (the structure functor for a finitary algebraic signature). Then the initial algebra is countable. As an abstract set, it is isomorphic to the terminal coalgebra of say F' defined by F'(X) = 1 + X, since this is also countably infinite. But this is hardly an interesting solution; could your colleague say more precisely what is wanted? –  Todd Trimble Feb 21 '11 at 19:56
slaps forehead I got mixed up: he has the terminal coalgebra of one functor and wants it to be the initial algebra of another. The first is the set of infinite terms coinductively generated from a signature. He has reason to believe that the same terms can be generated inductively from an enlarged signature, and wants to know if there is a more abstract category-theoretic perspective on this. –  Finn Lawler Feb 21 '11 at 21:06
You comment about infinite terms makes sense. But your question does not, because trivially every object $A$ is the initial algebra of some functor, namely the constant functor $F(X) = A$. So you really have to ask something else. There has to be a connection between the structure maps of the terminal coalgebra and the initial algebra. –  Andrej Bauer Feb 22 '11 at 11:00

1. The set of streams of elements of $A$ can be thought of as the final coalgebra $\nu F$ of the functor $F(X) = A \times X$. It is also the initial algebra of the functor $G(X) = \mathbb{N} \to A$. (Note that $X$ does not occur in $G$ -- this is a constant functor.)

2. From a slightly less stupid perspective, thanks to the axiom of foundation, any coinductive set can be converted into an inductively generated one.

3. In a category of metric-valued metric spaces (ie, an enriched category with metric Hom-spaces), any locally contractive endofunctor (ie, sends maps to strictly smaller maps) will have a unique fixed point, basically via Banach's fixed point theorem. I think American and Rutten proved a general theorem along these lines.

4. Their theorem was a metric variant of Plotkin and Smyth (1982), "On the Category-Theoretic Solution of Recursive Domain Equations", where they make use of the fact that in pointed domains, you (a) have a distinguished least point to iterate a fixed point from, and (b) a least (initial) object to iterate the functor from.

I believe the general keyword to search for the phenomenon of functors whose initial and final algebras coincide is "bilimit compact".

I also seem to recall that in Abramsky and Jung's chapter on domain theory in the handbook of logic in computer science, they claim that the result still holds if you don't use embedding-projection pairs, but just have a Scott-continuous adjunction. I never did the proof of this claim myself, so I can't tell you how it goes.

-
Re 3: Kozen and Ruozzi recast fixed points of contractions as applications of metric coinduction golem.ph.utexas.edu/category/2009/05/metric_coinduction.html. –  David Corfield Feb 22 '11 at 9:11

The trivial answer is that every object $X$ in every category is the initial algebra for a functor, namely the constantly $X$ functor. I don't think you meant to ask that.

What we need is a connection between the structure maps of the final coalgebra and initial algebra. The best connection one can hope for is that the underlying objects coincide and the structure maps are inverses of each other. Let us investigate this possibility in the case of term algebras, as you mentioned that your friend is interested in this case.

The initial algebra $a : F(A) \to A$ for a given signature represented by a polynomial functor $F$ is the set of all finite trees (whose node types and branching correspond to the operations and their arities). The final coalgebra $c : C \to F(C)$ consists of all trees, finite and infinite ones, whose branching node types and branching correspond to the operations. (You stated above that the final coalgebra consists just of the infinite trees, but I do not think this is the case.)

We can try to make $A$ and $C$ coincide by moving over to a different category. Let us try, say, the category $\mathcal{C}$ of compact Hausdorff spaces. For concreteness, let us consider the functor $F(X) = 1 + X \times X$ (we have to think precisely how to make it work on compact Hausdorff spaces). unfortunately I do not have the time to prove things right now, so I will just make a claim. Perhaps someone else can prove or disprove it, or I will come back later.

Claim: The initial algebra and the final coalgebra for $F(X) = 1 + X \times X$ coincide in the category of compact Hausdorff spaces and continuous maps.

The idea is this: the initial algebra "wants" to be the discrete space on countably many points (the finite trees), but the category is "forcing" it to be a compact space. Thus, all the infinite trees appear in the initial algebra as the "missing" limit points. Am I right? I seem to remember a paper about this.

-
Yes, I meant possibly-infinite terms. The initial/terminal (co)algebras are those of distinct functors (see edits to question). I don't know about your example, but it reminds me of Barr's paper about terminal coalgebras as Cauchy completions of initial algebras. –  Finn Lawler Feb 22 '11 at 16:16