ABSTRACT
Induction is the single most important method to prove elementary theorems about the integers. (More subtle theorems, such as many of the theorems of “number theory,” require more sophisticated methods.) Let P (x) be a formula in the language Lset of sets, with free variable x. For each such P (x) we have:
Proposition 18.1. (Induction Principle) Assume 1) P (1). 2) For all n ∈ N if n 6= 1 and P (n− 1) then P (n).
