Given a functor $F : \mathcal C \to \mathcal C$ with initial algebra $\alpha : FA \to A$, and another algebra $\xi : FX \to X$, we obtain a unique morphism $\mathsf{fold}~\xi : A \to X$ such that $\mathsf{fold}~\xi \circ \alpha = \xi \circ F(\mathsf{fold}~\xi)$.

I am looking for a sufficient condition - ideally phrasable as $P(F) \wedge Q(\xi)$ rather than $R(F, \xi)$ - which guarantees that:

  1. $\mathsf{fold}~\xi$ is monomorphic,
  2. $\mathsf{fold}~\xi$ is epimorphic.

(I'm looking for separate conditions for 1 and for 2.)

I would expect:

  1. $F$ preserves monomorphism and $\xi$ is monomorphic
  2. $F$ preserves epimorphism and $\xi$ is epimorphic

but I can't seem to prove this.

EDIT: I'm also interested in the dual question (which, mathematically, of course just has dual answers). I mention this anyway, because Valery Isaev's answer uses local finite presentability, which is something that might not have been answered had I asked the dual question. So feel free to use concepts that are only dually familiar. In particular, I'm willing to assume that $F^{op}$ is polynomial (or similar in a less powerful category, e.g. $FX$ is a coproduct of powers of $X$ in $\mathcal C^{op}$).

  • $\begingroup$ By "$Q(\xi)$" do you mean a property of the morphism $\xi$ purely as a morphism in $C$ without any reference to the fact that its domain happens to be of the form $FX$? Or would you include properties of $\xi$ as an $F$-algebra? $\endgroup$ – Mike Shulman Mar 10 at 14:13
  • $\begingroup$ Yes, I've realized the separation of concerns is a bit ill-typed. I'm willing to consider $\xi$ as an $F$-algebra. Anything is better than requiring that $0 \to X$ be epimorphic. $\endgroup$ – dremodaris Mar 11 at 11:43

Suppose $({\cal E,M})$ is a factorization system on $\cal C$ such that $\cal M$ consists of monomorphisms and $F$ preserves $\cal E$-morphisms. If $X$ is an $F$-algebra, define an $\cal M$-subalgebra of $X$ to be a morphism $Y\to X$ of $F$-algebras that is an $\cal M$-morphism. Then if $A$ is the initial $F$-algebra, the map $A\to X$ lies in $\cal E$ if and only if $X$ has no proper $\cal M$-subalgebras.

In the "if" direction, note that the assumption that $F$ preserves $\cal E$-morphisms implies that $({\cal E,M})$-factorizations lift to $F$-algebras. In particular, if we factor the unique $F$-algebra morphism $A\to X$ as $A\to Z \to X$, then the unique lifting property of $F A \to F Z$ (which is in $\cal E$) against $Z\to X$ (which is in $\cal M$) makes $Z$ an $F$-algebra and the two maps $F$-algebra maps. In particular, $Z$ is an $\cal M$-subalgebra of $X$. Thus, if $X$ has no proper $\cal M$-subalgebras, then $Z\cong X$ and hence $A\to X$ is in $\cal E$.

Conversely, if $A\to X$ is in $\cal E$, suppose $Z\to X$ is an $\cal M$-subalgebra. Then $A\to X$ factors through $Z$ (since $A$ is the initial $F$-algebra), but then $Z\to X$ must be an isomorphism since it is an $\cal M$-morphism that is factored through by some $\cal E$-morphism.

In particular, if $\cal C$ admits (epi, strong mono) factorizations, then $A\to X$ is epi if and only if $X$ has no proper strong-subalgebras.

EDIT: Note that if $X$ has no proper $\cal M$-subalgebras, then $\xi : F X \to X$ is in $\cal E$. For we can $({\cal E,M})$-factor it as $F X \to Z\to X$ and show that $Z$ becomes an $\cal M$-subalgebra. The assumption on $X$ then implies $Z\cong X$, hence $\xi\in\cal E$.

On the other hand, as Valery pointed out, taking $F=\rm Id$ shows that the converse can't hold. Any endo-epimorphism $X\to X$ (e.g. $(+1) : \mathbb{Z}\to\mathbb{Z}$) gives an $F$-algebra $\xi$ that is an epimorphism, but $0 = A \to X$ will rarely be epi.


If $\mathcal{C}$ has an initial object and the unique map $0 \to X$ is an epimorphism, then $\mathrm{fold}\ \xi : A \to X$ is an epimorphism. This follows from the fact that the composite $0 \to A \to X$ is an epimorphism. This condition seems too restrictive, but it is "almost necessary". Indeed, if $F(0) \simeq 0$ (for example, if $F$ is the identity functor), then $A \simeq 0$, so $\mathrm{fold}\ \xi : A \to X$ is an epimorphism if and only if $0 \to X$ is. It is hard to imagine some nice sufficient properties of $F$ which are not true for the identity functor.

Now, let's discuss when $\mathrm{fold}\ \xi$ is a monomorphism. Suppose that the following conditions hold:

  • $\mathcal{C}$ is locally finitely presentable.
  • $F$ preserves sufficiently long sequential colimits.
  • The unique map $0 \to X$ is a monomorphism.
  • The map $\xi : F(X) \to X$ is a monomorphism.
  • $F$ preserves monomorphisms.

Then $\mathrm{fold}\ \xi : A \to X$ is a monomorphism. Indeed, if the second condition holds, then $A$ can be constructed as a colimit of a transfinite sequence $$ 0 \to F(0) \to F^2(0) \to F^3(0) \to \ldots$$ This colimit exists since $\mathcal{C}$ is locally presentable. The map $f^n : F^n(0) \to X$ is constructed as the composite $F^n(0) \xrightarrow{F(f^{n-1})} F(X) \xrightarrow{\xi} X$. Since $0 \to X$ and $\xi$ are monomorphisms and $F$ preserves monomorphisms, we can prove that $f^n$ is a monomorphism by induction. At a limit stage, we need to use the fact that $\mathcal{C}$ is locally finitely presentable. Such a category has a generator consisting of finitely presentable objects. Thus, to prove that a map $f^\alpha : F^\alpha(0) \to X$ is a monomorphism, we just need to show that for every pair of maps $g,h : S \to F^\alpha(0)$, where $S$ is finitely presentable, if $f^\alpha \circ g = f^\alpha \circ h$, then $g = h$. Since $S$ is finitely presentable, maps $g$ and $h$ factor through $F^\beta(0)$ for some $\beta < \alpha$. Now, it follows that $g = h$ by induction hypothesis. This shows that $\mathrm{fold}\ \xi$ is a monomorphism since it equals $f^\lambda : F^\lambda(0) \to X$ for some $\lambda$.

  • 1
    $\begingroup$ I think in place of local finite presentability, it also suffices to assume $C$ is a Grothendieck topos, or more generally an exhaustive category (ncatlab.org/nlab/show/exhaustive+category), since then $F^\alpha(0)\to X$ is a union of a chain of subobjects of $X$ and hence also a subobject. $\endgroup$ – Mike Shulman Mar 10 at 4:33
  • $\begingroup$ However I'm not sure what you mean by "It is hard to imagine some nice sufficient properties of $F$ which are not true for the identity functor." There are plenty of endofunctors for which we want to consider initial algebras that don't preserve the initial object; indeed as you note, if $F0=0$ then $A=0$, so any functor with an interesting initial algebra must not preserve the initial object. For instance, $F(X) = X+1$, whose initial algebra is the natural numbers. $\endgroup$ – Mike Shulman Mar 10 at 4:35
  • 1
    $\begingroup$ @MikeShulman I mean a sufficient condition on $F$ cannot be of the form "$F$ preserves something", or "$F$ is a polynomial functor", or anything like that since the identity functor satisfies these conditions. Of course, we can consider conditions such as "$F$ does not preserve the initial object", but it seems less natural to me. $\endgroup$ – Valery Isaev Mar 10 at 11:45
  • $\begingroup$ Well of course you would have to put conditions on $X$ too. $\endgroup$ – Mike Shulman Mar 10 at 14:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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