Originally Posted by

**mrproper** Greetings,

I'm reading Introduction to Set Theory, Third Edition by K.Hrbacek and T.Jech and I have some questions on the proof of the induction principle in that specific book. I'm interested in knowing if the proof of the strong or the weak form is somehow depends on implicit assumption that N is well-ordered.

Yes. Under ZF, the Principle of Math. Induction is equivalent with $\displaystyle \mathbb{N}$ being well ordered,

and from here we also get inductions (perhaps transfinite) for any well ordered set.

The difference between the weak and the strong formof the PMI is not that deep and each can be proved, I think,

from the other one.

Tonio

I cite the proofs below.

**Weak form:** Let P(x) be a property (possibly with parameters). Assume that

(a) P(0) holds

(b) For all n $\displaystyle \in$ N P(n) implies P(n+1)

Then P holds for all natural numbers n.

**Proof of the weak form:** This is immediate sequence of our definition of N. The assumptions (a) and (b) simply say that the set A={n $\displaystyle \in$ N | P(n)} is inductive. N $\displaystyle \subset$ A follows.

(N is defined as the smallest inductive set, whose elements are elements of all inductive sets. Inductive set is defined as a set that contains 0 and for every element it contains, it contains also his successor).

Strong form: Let P(x) be a property (possibly with parameters). Assume that for all n $\displaystyle \in$ N:

(*) If P(k) holds for all k<n then P(n)

Then P holds for all natural numbers n.

**Proof of the strong form:** Assume that (*) is true. Consider the property Q(n): P(k) holds for all k<n. Clearly Q(0) is true (there is no k<0). If Q(n) holds, then Q(n+1) also holds: If Q(n) holds then P(k) holds for all k<n and consequently also for k=n [By (*)]. Lemma 2.1(II) enables us to conclude that P(k) holds for all k<n+1 and therefore Q(n+1) holds. By the weak form of the induction principle, Q(n) is true for all n $\displaystyle \in$ N. Since for k $\displaystyle \in$ N there is some n>k (e.g. n=k+1) we have P(k) true for all n $\displaystyle \in$ N as desired.

**Lemma 2.1(ii):** For all k,n $\displaystyle \in$ N, k<n+1 if and only if k<n or k=n.

Proof: It suffices to observe that k $\displaystyle \in$ n U {n} if and only if k $\displaystyle \in$ n or k=n.

I think that this book is probably very unpopular with the professional mathematicians because it tries to avoid too much mathematical logic, but for a layman as me is a discovery and I hope someone here will be able to help me on this one...