Finding a functor satisfying a recursive equation

326 Views Asked by At

Say I want to find a functor satisfying something like: \[FA = 1 \sqcup (A \times FA).\] Equivalently, I want to find for each $A$ a fixed point of: \[GB = 1 \sqcup (A \times B)\] (I'll worry about what $F$ does on morphisms later).

What I want to do is roughly speaking apply $G$ infinitely many times, and hope $G$ is in some sense "continuous" so that the result is a fixed point of it. But I see at least two possible approaches: if I have an initial object, then I can form the diagram (of shape $\mathbb N$, considered as a poset category) \[0 \to G0 \to GG0 \to \dots\] and take the colimit, or if I have a terminal object then the limit of \[\dots \to GG1 \to G1 \to 1\] (of shape $\mathbb N^\mathrm{op}$) might do the trick (as a commenter pointed out, the limit of the former and the colimit of the latter are uninteresting). Presumably I want to choose the limit or colimit according to whichever of the two $G$ preserves, so that I can argue that the result really is a fixed point.

The initial and terminal objects are the most obvious "ends" of the above chains, but any object on which I can get started (i.e. which has a morphism $A \to GA$ or $GA \to A$) might conceivably be helpful.

Which of these strategies (if any) is sensible? Do they give the same result? Are there other strategies?

2

There are 2 best solutions below

0
On BEST ANSWER

A good strategy for finding fixed points for functors is to find initial algebras, or terminal coalgebras.

An initial algebra for a functor $F$ is an object $A$ paired with a morphism $\alpha : FA \to A$, such that for any other such pair $(B,\beta)$ there is a unique morphism $f : A \to B$ such that $f \circ \alpha = \beta \circ Ff$.

They're interesting in this context because:

Theorem: If $(A,\alpha)$ is an initial $F$-algebra, then $\alpha$ is an isomorphism (so $A$ is a fixed point of $F$).

Proof: If $(A,\alpha)$ is an algebra then so is $(FA,F\alpha)$, and $\alpha$ is (somewhat trivially) an algebra homomorphism $(FA, F\alpha) \to (A, \alpha)$. Then since $(A,\alpha)$ is initial, there is a unique algebra homomorphism $f : (A,\alpha) \to (FA,F\alpha)$, and so $\alpha\circ f$ is an algebra homomorphism from $(A,\alpha)$ to itself. But by uniqueness, this is the identity. Now, $f$ an algebra homomorphism means $$f \circ \alpha = F\alpha \circ Ff = F(\alpha \circ f) = F\operatorname{id}_A = \operatorname{id}_{FA}$$. So $f \circ \alpha$ is the identity too.

A dual result holds for terminal coalgebras, of course.

The next question is, when do initial algebras exist, and how do you construct them? Introduction to coalgebra has a wealth of theorems with references on this and related subjects. In particular, the following:

3.17. Theorem. Let $\mathcal A$ have and $H$ preserve $\omega$-colimits. If $0$ is the initial object of $\mathcal A$ and $! : 0 \to H0$ the unique morphism, then an initial algebra $I$ is a colimit of the $\omega$-chain $$0 \xrightarrow{!} H0 \xrightarrow{H!} HH0 \xrightarrow{HH!} \dots$$

There are further results for more general settings, in particular colimits indexed by larger ordinals. The reference given for the above result is:

J. Adámek, Free algebras and automata realization in the language of categories, Comment. Math. Univ. Carolinae 15(1974), 589–602.

On another note, following the advice of Mockup in the other answer, I went through the construction of lists in $\mathbf{Set}$ by the sequential colimit method, but starting from a non-initial object. What you get depends on what exactly you pick for your morphism $A \to GA$: you may get exactly the same as you would otherwise, or you may get a few "extra" elements, e.g. sequences that satisfy $x = a:x$ for some $a \in A$.

9
On

Both of your strategies are sensible for suitably well-behaved functors and categories: one corresponds to taking the "smallest" fixed-point (the free algebra), and the other corresponds to taking the "largest" fixed point (the cofree coalgebra). They are almost never equivalent --- in your example, the first construction gives the type of finite sequences over $A$, whereas the second construction gives the type of countable sequences over $A$.

Categorically, what you have described is a very special case of constructing the free monad and the cofree comonad of an endofunctor. From the top of my head I cannot tell you of any good textbook about the subject (I hardly recall there is a chapter in "Toposes Triples and Theories" by Michael Barr, also there is a lot of stuff on (co)algebras written by Bard Jacobs). However you should find a lot of information by searching terms "free (co)monad" and "free (co)triple" (triple is an old name for monad).