# Does “induction” for a functor algebra imply it is initial?

I originally posted this question to MSE but there were no answers except for a partial one from me, so I'm trying again here. I'm an undergrad, not a researcher, so forgive me (and correct me!) if my terminology is nonstandard, or my ideas confused.

By "induction" I mean "no proper subalgebras". My thinking goes like this:

1. For natural numbers, recursion and induction are in some sense the same thing. In particular, given a recursive definition of $f$ you would prove its totality roughly by saying "if I can define $f$ on $1\dots n$, then I can define it on $n+1$", i.e. by induction.
2. The proper categorical notion of recursion is initial algebras – in particular, for $F(X) = 1\sqcup X$ an initial algebra is a natural number object, the property of being initial being precisely what you need to define functions by recursion.
3. An initial algebra automatically has a notion of induction: initial objects have no proper subobjects, so if you have some subobject that is closed under the algebra operations, this means precisely that the inclusion is an algebra homomorphism, and therefore an isomorphism.
4. I'd really like to go the other way, but in general the implication "$I$ is initial $\implies$ every mono into $I$ is an iso" cannot be reversed (its dual has a counterexample in $\mathbf{Set}$, in that every epi into $0$ is an iso but $0$ is not terminal).

Are there circumstances where an algebra having no proper subalgebra means it is initial?

Observations that have been made since posting the question:

• There is an algebra $1 \sqcup \mathbb Z/n\mathbb Z \to \mathbb Z/n\mathbb Z$ that has no proper subalgebras, so induction works for it. Nevertheless it is not initial. The problem is that the algebra satisfies equations, since $n$ successors give the identity, so there aren't morphisms to algebras that don't satisfy those equations. This suggests that the algebra needs to be "free" in some sense.
• In light of the above, I might decide I'm interested in quasi-initial objects, since it is at least true that any morphism from $\mathbb Z/n\mathbb Z$ that is an algebra homomorphism is unique. It turns out that in any category with equalisers, if an object has no proper subobjects then it is quasi-initial, and of course a category of algebras has equalisers if its underlying category does.

What's the "freeness" condition that I want? What can I do to show that any morphisms exist from an object with no proper subobjects?

-
@Bruce Westbury: no. –  Andrej Bauer Apr 14 '13 at 17:00
@Andrej Comment deleted –  Bruce Westbury Apr 14 '13 at 18:03

It looks as though you might have already observed this yourself, but suppose $F: C \to C$ is an endofunctor and $C$ has equalizers. Then if $F$ has a weakly initial algebra $X$ (meaning that for every $F$-algebra $Y$ there exists an $F$-algebra map $X \to Y$), then $X$ is initial if and only if every $F$-subalgebra of $X$ is all of $X$. For, if $f, g: X \to Y$ are two $F$-algebra maps, then their equalizer is an $F$-subalgebra of $X$, and its being equal to $X$ would force $f = g$.

This is not a completely idle observation however, because one sometimes has formal ways to construct weakly initial $F$-algebras. Suppose for instance that $C$ is finitely complete and cartesian closed and $F$ carries a structure of $C$-enriched functor. Then, if the end

$$\int_{c \in C} c^{c^{F(c)}}$$

exists (meaning an object universal with respect to dinatural maps to the functor $G: C^{op} \times C \to C$ defined by $G(d, c) = c^{d^{F(c)}}$), it is a weakly initial $F$-algebra. For instance, when $C = Set$ and $F(c) = 1 + c$, we have

$$\int_{c} c^{c^{1 + c}} \cong \int_c c^{c^c \times c} \cong \int_c (c^c)^{(c^c)}$$

which is the set of dinatural transformations $c^c \to c^c$. This is isomorphic to $\mathbb{N}$ conceived as the set of Church numbers $\lambda f: f^{(n)}$ where $f$ is of variable type $c^c$.

If you are interested specifically in natural numbers objects, then there is a remarkable theorem due to Peter Freyd:

Theorem: In a topos $E$, the following are equivalent for a structure $(N, o: 1 \to N, s: N \to N)$:

• $(N, o, s)$ is a natural numbers object;

• The maps $o: 1 \to N, s: N \to N$ are coproduct injections (that witness $N$ as a coproduct $1 + N$) and $N \to 1$ is the coequalizer of the pair $(1_N, s): N \to N$;

• $s$ is monic, the subobjects $s: N \to N$ and $o: 1 \to N$ are disjoint (have the initial object as their pullback), and any subalgebra of the algebra structure $(o, s): 1 + N \to N$ on $N$ is all of $N$.

The proof is not at all easy, but you can find it in Johnstone's Sketches of an Elephant, section D.5.

-