Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 from $0$ is an iso but $0$ is not terminal).

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

share|improve this question
    
Please feel free to add more tags, I wasn't sure if e.g. universal-algebra was appropriate. –  Ben Millwood Mar 9 '13 at 16:09
1  
You also have to know that the algebra is "free" in a suitable sense, if you want induction to imply recursion. For example, every simple abelian group has "induction" in the sense of having only the trivial subgroup as a proper subgroup, but "recursion" is only possible for $\mathbb{Z}$ and not, say, $\mathbb{Z} / p \mathbb{Z}$. –  Zhen Lin Mar 9 '13 at 16:18
    
Makes sense. Is there a characterisation of "free" that is not "induction implies recursion"? Or any nice sufficient condition for it? –  Ben Millwood Mar 9 '13 at 16:25
    
(A thought: recursion might fail for $\mathbb Z/p\mathbb Z$, but if it works it will be unique... maybe I am looking for a quasi-initial object? Especially since in my counterexample, $0$ is indeed *sub*terminal...) –  Ben Millwood Mar 9 '13 at 16:34

2 Answers 2

In general, it is possible for an object to have every mono into it an iso, but not be initial, weakly initial, or quasi-initial. The pre-condition is too easily satisfied just by not having very many morphisms into a given object, so to give it some traction, I'll need an existence-of-morphisms condition.

Theorem: In a category with equalisers, if $I$ is an object such that any mono $A \rightarrowtail I$ is an iso, then $I$ is quasi-initial.

Proof: Let $f, g : I \rightrightarrows X$, and take $A \xrightarrow{e} I$ the equaliser of $f$ and $g$. An equaliser is a (regular) mono, so by hypothesis on $I$ it is an iso, but if the equaliser of two morphisms is an iso then they are equal. So $f = g$, so there is at most one morphism from $I$ to any other object.

In the particular case of categories of functor algebras and homomorphisms, the forgetful functor to the underlying category creates limits, so in particular it is enough for the underlying category to have equalisers (thanks Zhen Lin for reminding me of this).

I've not yet come up with any interesting word on when there is at least one morphism, so that $I$ really is initial instead of quasi-so.

share|improve this answer
    
And, of course, the category of algebras for an endofunctor has equalisers if the base category does. –  Zhen Lin Mar 25 '13 at 23:52
    
Yes, I thought that, but forgot to mention it. Might edit it in. –  Ben Millwood Mar 25 '13 at 23:53
up vote 1 down vote accepted

After receiving no answers here, I reposted this question on MathOverflow, and got an answer from Todd Trimble.

http://mathoverflow.net/questions/127540/does-induction-for-a-functor-algebra-imply-it-is-initial

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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