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?

  • $\begingroup$ +1 I retagged just in case there already similar results in the fixpoint theory. $\endgroup$ – Ilya Jan 28 '13 at 18:40
  • $\begingroup$ Perhaps Kelly's 1980 paper, A unified treatment of transfinite constructions, is relevant here. $\endgroup$ – Zhen Lin Jan 28 '13 at 18:51
  • 2
    $\begingroup$ See math.stackexchange.com/questions/282556/… $\endgroup$ – Martin Brandenburg Jan 28 '13 at 23:47
  • 2
    $\begingroup$ @Martin +1, it is amusing to see that you wrote a wrong answer to a question, and the right question for you answer came the very next day. Perhaps one should set up math.jeopardy.com site, where people could write their answers in the hope that they finally find the right questions :-) $\endgroup$ – Michal R. Przybylek Jan 29 '13 at 1:06
  • $\begingroup$ What, a wrong answer? $\endgroup$ – Martin Brandenburg Jan 29 '13 at 23:17

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).

  • $\begingroup$ You mean "initial algebra" (not free algebra), and "terminal coalgebra". $\endgroup$ – Martin Brandenburg Jan 28 '13 at 23:47
  • $\begingroup$ Could you clarify which of my strategies corresponds to which of your descriptions, or is that an exercise for the reader? :) $\endgroup$ – Ben Millwood Jan 28 '13 at 23:51
  • $\begingroup$ Other details I'm missing: whether to take the limit or the colimit, and whether or not it matters which object I start from in my chain. $\endgroup$ – Ben Millwood Jan 28 '13 at 23:56
  • $\begingroup$ @Martin, I meant "free" and "cofree" --- a (co)free (co)algebra is an initial (terminal) (co)algebra on some (possibly empty) "generators". I think in these contexts terms (co)free an initial (termianl) are used interchangeably. However I do agree with you that initial/termianl would suit better. $\endgroup$ – Michal R. Przybylek Jan 29 '13 at 0:43
  • $\begingroup$ @Ben, your first example construct the initial algebra, and the second example construct the terminal coalgebra. $\endgroup$ – Michal R. Przybylek Jan 29 '13 at 0:49

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.