The principle of induction says that if a property of the natural numbers
is true for ;
if it is true for then it is true for ;
then it is true for every . The intuitive notion of a property is in practical mathematics identified with (belonging to) a subset . Thus the mathematical induction says that if and if then . This is the way in the formal Dedekind-Peano arithmetics. Usually in logic one however uses a weaker form of induction which can be stated in a first order language (or in a type theory), namely where one limits to properties given by the predicates depending on natural numbers. The corresponding conclusion is the proposition . The latter version of the principle of induction is weaker because there are only predicates but subsets of .
When formulated in one of the formalizations below, one finds that the principle of induction for propositions depending on natural numbers is the simplest special case of a very general notion of induction over inductive types. Other examples are induction over lists, trees, terms in a logic, and so on.
The induction principle my neatly be formalized in terms of the notion of initial algebras of an endofunctor.
In terms of this the principle of induction is equivalent to saying that there is no proper subalgebra of ; that is, the only subalgebra is itself. This follows from the general property of initial objects that monomorphisms to them are isomorphisms.
Bart Jacobs, Jan Rutten, A tutorial on (co)algebras and (co)induction, pdf EATCS Bulletin (1997); extended and updated version: An introduction to (co)algebras and (co)induction, In: D. Sangiorgi and J. Rutten (eds), Advanced topics in bisimulation and coinduction, p.38-99, 2011, pdf 62 pp.
Ch. 3, Formal arithmetics, in: Elliott Mendelson, Introduction to mathematical logic, D. Van Nostrad 1964