# When is a fold monomorphic/epimorphic

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

• 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? – Mike Shulman Mar 10 at 14:13
• 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. – 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$$.

• 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. – Mike Shulman Mar 10 at 4:33
• 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. – Mike Shulman Mar 10 at 4:35
• @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. – Valery Isaev Mar 10 at 11:45
• Well of course you would have to put conditions on $X$ too. – Mike Shulman Mar 10 at 14:11