Results 1 to 5 of 5

Math Help - Well-Ordering Property

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    34

    Well-Ordering Property

    I'm getting a little confused about the logic behind a proof in a book. It is proving the well-ordering property using induction; it proves the contrapositive:
    If T is a subset of the natural numbers which has no smallest element, then T is empty

    Suppose T has no smallest element and let S be the complement of T. (*) Let n be a natural number such that for all m<n, m is in S. Then n is in S and so S is the set of natural numbers and T is empty.

    (*) This is the step I don't understand. What if 1 is in T? Then no such n exists and S is empty? Where is the step that uses the fact T has no smallest element?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    I think that you must post the complete proof in that text.
    Along with some background from the textbook on W.O.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2009
    Posts
    34
    This is from Peter Cameron's Introduction to Algebra. It's just the introduction chapter going through basic number systems in a relaxed way (ie no formal construction from some explicit set of axioms).
    Also, that is the entire proof. I know it's not the best book to be contemplating about the well-ordering property, but some of the other books I have on set theory all assume the well-ordering property and use it to prove induction, so that doesn't help.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I think everything just has to be written carefully.

    Suppose T has no least element. We prove some statement by (strong) induction that will entail that T is empty. Let S be the complement of T.

    Induction statement P[n]: for all m < n, m is in S.

    P[0]: vacuously true.

    Fix some n and suppose P[n]: for all m < n, m is in S.
    Need to prove P[n+1]: for all m < n + 1, m is in S.

    Since (m < n + 1) iff (m < n or m = n), we need to show that n is in S. Note that at this points we reached the stage "Let n be a natural number such that for all m<n, m is in S" in your proof. Then if n is not in S, n is in T (as T is the complement of S). However, n is the least element in T because for all m<n, m is in S. Contradiction. Therefore, n is in S and P[n+1] is proved.

    Thus, we proved "for all n, P[n]". Therefore, T is empty because if n is in T, then n < n + 1 and P[n+1] says n is in S, i.e., not in T.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2009
    Posts
    34
    Oh, wow, thanks! I realise now that I was getting confused because I didn't put together the fact that both induction AND contradiction were being used (I have only seen that kind of proof method a handful of times). I kept seeing them separate
    Thanks a lot!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. ordering property of Z
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: January 16th 2012, 04:22 PM
  2. Mean Value Property Implies "Volume" Mean Value Property
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 16th 2011, 09:13 PM
  3. Replies: 1
    Last Post: November 16th 2010, 02:36 AM
  4. Well Ordering
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: September 8th 2010, 05:04 AM
  5. Well ordering property and induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 30th 2009, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum