Proving well ordering principle from Peano Axioms

[issacnewton]

Homework Statement

Let ## G \subseteq \mathbb{N} ## be a non empty set. Then there is some ## m \in G ## such that ## m \leq g ## for all ## g \in G##

Relevant Equations

Peano Axioms where lowest element is taken to be 1.

I am trying to understand the proof given in Ethan Bloch's book "The real numbers and real analysis". I am posting snapshot of the proof in the book.

I am also posting theorem 1.2.9 given in the book.

Here author is trying proof by contradiction. First, I don't understand why specific choice of the set ##H## was done. Is there any hint in the statement of the theorem 1.2.10 that this set needs to be considered. Next, the author is using contradiction at 3 different places in the proof. Though I am following what he says, but is this usual in math proofs to use contradiction at several places ? When I studied the method of proof by contradiction, there is only one contradiction at the end. So, this was new way to do proofs to me. Finally, when author states at the end that ##H = \mathbb{N}##, how does theorem's statement follow ?

 

[FactChecker]

Here author is trying proof by contradiction. First, I don't understand why specific choice of the set ##H## was done.

##H \subseteq \mathbb{N}## is the set of all possible lower limits for the set ##G##. For a proof by contradiction, it was assumed that ##H \cap G = \phi##.

Is there any hint in the statement of the theorem 1.2.10 that this set needs to be considered.

Yes. The theorem implies that ##H \cap G \ne \phi##.

Next, the author is using contradiction at 3 different places in the proof. Though I am following what he says, but is this usual in math proofs to use contradiction at several places ?
When I studied the method of proof by contradiction, there is only one contradiction at the end. So, this was new way to do proofs to me.

I think he is just stating things that the assumption for a contradiction implies about ##H##. It implies several things that take some thought to establish.

Finally, when author states at the end that ##H = \mathbb{N}##, how does theorem's statement follow ?

Because if ##H = \mathbb{N}## and ##H \cap G = \phi## and ##G \subseteq \mathbb{N}##, then ##G = \phi##, which contradicts an assumption of the theorem.

 

[issacnewton]

Thanks.

 

[mathwonk]

If it makes you feel any better, I am a retired professional mathematician, and although I can follow that proof, I think it is one of the most complicated proofs I have seen in a supposedly elementary book. With apologies to Ethan, I myself would possibly toss this book on the strength of that one example of its marginal usefulness.

Out of fairness, this is probably an example of why it is not always helpful for understanding, to try to deduce everything from a minimal set of axioms, and perhaps not Prof. Bloch's fault. However Factchecker's nice enhancement shows it could have been made much more clear.

In fact I would have defined H (without negations) as all a such that if n is in N and in G, then n ≥ a. Then H really is the set of all lower bounds for G, and all we have to do is show that G does meet H. So assume G is non empty but disjoint from H, and derive a contradiction. This time the fact that 1 is in H is immediate from Theorem 1.2.9(2), no argument needed. Now if G is non empty but disjoint from H, then H is not everything, so by Peano (negated) there is some a in H (and in N) with a+1 not in H. Then (as in Bloch's argument) there is some p in G with a ≤ p < a+1), hence p = a is in both G and H; we are done by contradiction since then G is in fact not disjoint from H.

A good exercise might be to write up the proof for yourself with as few negations as possible.