Can't seem to understand Well Ordering Principle

Been wondering on it since hours. If I may quote from Kenneth Rosen's book:

Attachment 23998

The two underlined parts are saying totally the opposite, no? What exactly is the author trying to visualize in the first highlighted part?

I guess its a set S = { 1, 2, 3, ......, n, n+1 }

hmm? I may be wrong, I often am.

Yes, they say the opposite. That's why they give a contradiction. The "hypothesis" that the set S does not include all positive integers must be false.

Quote:

---

Originally Posted by HallsofIvy

Yes, they say the opposite. That's why they give a contradiction.

---

I agree.

To remind, the well-ordering property for positive integers says that every nonempty subset of positive integers has the least element. Note that the proof would go through with a weaker property:

For every nonempty subset S of positive integers we have 1 ∈ S or there exists a number n such that n ∉ S and n + 1 ∈ S (*)

It is clear that the well-ordering property implies (*). Now, (*) is in fact the contrapositive of induction. Indeed, considering the complement S' of S in (*) we have

∀S'. S' ≠ Z⁺ ⇒ 1 ∉ S' ∨ ∃n. n ∈ S' ∧ n + 1 ∉ S'.

The contrapositive of this is

∀S'. 1 ∈ S' ∧ (∀n. n ∈ S' ⇒ n + 1 ∈ S') ⇒ S' = Z⁺,

which is the induction principle. Thus, the outline of the proof is the same as the proof by contradiction of the contrapositive ¬B ⇒ ¬A from A ⇒ B: assume ¬B and suppose A; then B, a contradiction.

Similarly, the contrapositive of the whole well-ordering property is strong induction.

lol, using the well-ordering principle to justify induction is like becoming an american citizen in order to get a permanent visa. and what i mean by this is: the principle of induction is equivalent to the well-ordering principle: given one, you can prove the other.

such "proofs" amuse me, it's like defining existence to be a state of being. you haven't really accomplished anything.

the principle of induction is something we would like to BELIEVE is true. this belief is founded on the notion that the successor map is injective. i'll admit it seems plausible, but it's only so because we say it's so. at some point, we should be honest and admit: "well, if the natural numbers DID exist, we'd like them to behave like THIS".

look, i get it, we've built the "inductive" character of the natural numbers into our set theory. it's axiomatic. the desire for natural numbers to be included in the scope of ZF set theory is the raison d'etre of the axiom of infinity.

@ the original poster: i sympathize with your confusion. all Mr. Rosen has done is to shift the proof of the principle of induction onto another principle: the well-ordering principle. and the well-ordering principle is typically proved....by induction! but it's still worth-while to understand the "form" of the proof.

one way we often prove something is true, is to show that there are no counter-examples. and often this is paired with a proof by contradiction, like so:

Pigs never fly

Proof: If pigs fly, there must be some pig that flies. But as proved in Theorem A.B(1a), if any pig flies, then everything is true. But some things are not true, contradiction.

a less tongue-in-cheek example of what i mean can be found here:

http://courses.csail.mit.edu/6.042/s...l_ordering.pdf