# Layman question about proving mathematical induction from axioms of set theory

• April 9th 2011, 01:14 PM
mrproper
Layman question about proving mathematical induction from axioms of set theory
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. 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 $\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 $\in$ N | P(n)} is inductive. N $\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 $\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 $\in$ N. Since for k $\in$ N there is some n>k (e.g. n=k+1) we have P(k) true for all n $\in$ N as desired.

Lemma 2.1(ii): For all k,n $\in$ N, k<n+1 if and only if k<n or k=n.
Proof: It suffices to observe that k $\in$ n U {n} if and only if k $\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...
• April 9th 2011, 07:38 PM
tonio
Quote:

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 $\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 $\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 $\in$ N | P(n)} is inductive. N $\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 $\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 $\in$ N. Since for k $\in$ N there is some n>k (e.g. n=k+1) we have P(k) true for all n $\in$ N as desired.

Lemma 2.1(ii): For all k,n $\in$ N, k<n+1 if and only if k<n or k=n.
Proof: It suffices to observe that k $\in$ n U {n} if and only if k $\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...

.
• April 10th 2011, 12:15 AM
mrproper
Thanks very much. After looking into the reply, PlanetMath and Wikipedia, I think the things are becoming more clear for me now. But I'm still at loss about the original problem I had in mind.
Exercise in the same book asked for devising a proof of double induction:

Let P(k,l) be a property. If the statement (**) holds, then P holds for all pairs of natural numbers.
(**) If P(k,l) holds for all k,l $\in$ N such that k<m or (k=m and l<n), then P(m,n) holds.

The book seems to suggest is to do the proof by induction on one of the parameters then proceed by induction on the other. Things with this approach seem not enough precise to me. I'm not sure it's fair play and I could not write the arguments the way that seem convincing and in the style of the book. It may be my lack of imagination or maybe the lack of precision in the way reasoning is described in the book.

So I looked around for other proofs and noticed very nice proof of induction that proves induction, assuming that we have already proven that (N,<) is well ordered.
Mathematical induction - Wikipedia, the free encyclopedia
It cannot be adapted for ordered pairs unless there is non-inductive way of proving that that set of all ordered pairs of natural numbers is well ordered by relation (k,l)<(m,n) if (k<m or k=m and l<n). My book does this for N by induction, and I suspect that's the only way it is. I have to prove induction to be able to prove "well-orderednes"?
• April 10th 2011, 01:16 AM
Deveno
the "well-orderedness" and "inductiveness" of the natural numbers are equivalent properties. what this means is that each can be proved from the other. to some, this seems like circular logic.

on a more basic level, the natural numbers pose a certain problem: it is well-nigh impossible to define the natural numbers without self-referentiality. for example, if one defines the natural numbers as the smallest inductive set, then when one defines induction one shouldn't refer to the natural numbers, because induction defines them. at some point, most foundational systems of math (set theory, category theory, etc.) just give up, and stipulate the natural numbers' existence as an axiom (some of these are fairly well-disguised, it may not be obvious that this is what is being done. for example, you can have the axiom of infinity. but positing the existence of an infinite set, rests on (at some level) a notion of counting, i.e., the natural numbers).

often, induction is stated as an axiomatic property of the natural numbers, because there is not universal acceptance of the well-ordering property (equivalent to the axiom of choice). naively, the situation is this: we can prove (given suitable definitions) a lot of things about any given natural number. 2+2 = 4 is the "standard" example. but proving something is true for ALL (or ANY) natural number involves, essentially, a "leap of faith". these are, at their core, questions of infinity. things get...counter-intuitive... "at" or "beyond" infinity (a difficulty most likely engendered by the fact that infinity is a "concept" not something we have direct apprehension of).

it is two different things to say: P is true for any (particular) natural number we choose (we can, given the time, supply a demonstration), and P is true for ALL natural numbers. some mathematicians (constructivists, in particular) accept the former, and reject the latter. for some of these, none of the "proofs" you discuss, are logically defensible.

but, by and large, induction proves so useful a tool, that it's possible logical short-comings are dismissed. my personal theory is that there is a natural inductive structure hard-wired into our synapses, and that much of mathematics is an attempt to express symbolically what we are "born knowing".

P.S: the book you are reading sounds like it ought to be popular with "professional mathematicians", the language used and the style of proof are consistent with much of mathematical literature.
• April 10th 2011, 07:43 AM
mrproper
Thank You very much! I guess when I finish the book, hopefully I'll know more about why these particular axioms are chosen as basis and more about their relation to other mathematical phenomena. For now, as happened more times before, the rabbit hole just grew bigger again (Happy).
I'm finishing by stating what "proof" i devised of double induction. I'd be thankful for someone reviewing it and pointing out the potential weaknesses. Try not to laugh that hard...

So: Let P(x,y) be a property. Assume that (**) holds then P holds for all m,n $\in$ N
(**) If P(k,l) holds for all k,l $\in$ N, such that k<m or (k=m and l<n), then P(m,n) holds.

I'll try to introduce new property Q(m,n): P(k,l) holds for all k,l $\in$ N, such that k<m or (k=m and l<n). And try to prove some facts about it, under assumption (**) is true.

FACT1: If Q(m,0) holds for some fixed m, then Q(m,n) holds for any n. By induction on n. Q(0,0) states that P(k,l) holds for all k<0 or (k=0 and l<0). Vacuous truth.
If Q(0,n) holds, then by (**) P(k,l) holds for l=n too, which means Q(0,n+1) also holds.

FACT2: If Q(m,n) holds for some fixed m and n, Q(m,n) holds for any n. If n=0 that's FACT1, if not - Q(m,n) implies Q(m,0) is true, by the way Q is defined. Then by FACT1 Q(m,n) must be true for any n.

I'll try to prove that Q(m,n) is true for any m and fixed arbitrary n by induction.
- Q(0,0) is vacuously true, so by FACT1, Q(0,n) must be true for any n.
- Assuming Q(m,n) is true, I must show that Q(m+1, n) is true. By FACT 2, Q(m,n) is true for any n. By (**) then Q(m+1,0) must be true. And by FACT 2 Q(m+1,n) must be true, no matter what n we have chosen.

So the conclusion is Q(m,n) must be true for all m and fixed arbitrary n. But since we have established FACT 2 it must mean that Q(m,n) is true for all natural numbers m and n. (First conclusion that looks little unprecise). Then since for all m,n $\in$ N there are always p, q such that m<p and n<q (for example p=m+1 and q=n+1) then P(m,n) must be true for all natural numbers m and n. (Does proving that require using induction again?).
• April 11th 2011, 12:26 PM
Deveno
i think you're making it harder than it needs to be. define a new property Qm(n) = P(m,n). then define a second property R(m) = Qm(n). you can prove Qm by induction on n (here m is fixed). then you prove R by induction on m (here n is no longer fixed, but we have already proved for a fixed m, Qm(n) is true for all n).

but R(m) = Qm(n) = P(m,n), so proving R proves P (if R is true for all m, and Qm is true for all n, then P is true for all m and all n).

the idea is, you want to take double-induction "one variable at a time". requiring simulateneous requirements on both m, and n, defeats that purpose.