Results 1 to 4 of 4

Math Help - Can't seem to understand Well Ordering Principle

  1. #1
    Junior Member
    Joined
    Nov 2011
    From
    Karachi
    Posts
    36

    Can't seem to understand Well Ordering Principle

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

    Can't seem to understand Well Ordering Principle-capture.png

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,237
    Thanks
    1795

    Re: Can't seem to understand Well Ordering Principle

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Can't seem to understand Well Ordering Principle

    Quote Originally Posted by HallsofIvy View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Can't seem to understand Well Ordering Principle

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Well ordering principle and the maximum principle
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 3rd 2010, 09:31 AM
  2. Well-Ordering Principle
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2009, 11:59 AM
  3. Well Ordering Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 10th 2008, 09:16 AM
  4. well-ordering principle
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 10th 2007, 09:09 PM
  5. Well ordering principle
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 14th 2007, 08:37 AM

Search Tags


/mathhelpforum @mathhelpforum