A functor whose initial algebra is another's terminal coalgebra

Question

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?

Answer 1

Here's a sequence of answers.

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.

Answer 2

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.