1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of Well Ordering Property

  1. Jun 4, 2013 #1
    1. The problem statement, all variables and given/known data

    I am working through an introductory real analysis textbook and am having a little trouble with certain aspects of the proof of the well ordering property (I am new to proving).

    Theorem: Every nonempty subset of the natural numbers (N) has a smallest element.

    Proof:

    Let S[itex]\subset[/itex]N and S≠∅. Then inf(S) must exist and be a real number because N has lower bound. If inf(S) [itex]\in[/itex] S, we are done.

    If inf(S) [itex]\notin[/itex] S, then it is the greatest lower bound of S but is not min(S). There must be an element x [itex]\in[/itex] S that is smaller than inf(S)+1 since inf(S) is the greatest lower bound of S. Thus we have inf(S) < x < inf(S)+1.

    -This is the first part I had trouble with. What is the justification for the fact that inf(S)+1 is greater than some x[itex]\in[/itex]S? From which axiom(s)/definition(s) can we infer that inf(S) is a real number that is greater than the greatest integer not in S?

    Since x > inf(S), it is not a lower bound of S. This means there must be another element y[itex]\in[/itex]S such that inf(S) < y < x < inf(S)+1.

    -Perhaps due to the earlier misunderstanding,the existence of such a y does not seem readily apparent to me. These two points are my main stumbling blocks and the rest of the proof is clear to me (contingent upon the existence of y). Any elucidation would be greatly appreciated.
     
    Last edited: Jun 4, 2013
  2. jcsd
  3. Jun 4, 2013 #2

    CAF123

    User Avatar
    Gold Member

    I believe these both follow from the Approximation Property for Infima. If you haven't seen this before, then it can be proved using the equivalent statement for suprema by considering ##-S##. (and clearly ##\sup(-S)## exists by the Completness axiom)
     
  4. Jun 4, 2013 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    For any real number x, there exist at least one integer, N, such that [itex]x\le N\le x+ 1[/itex].

    "inf" means, of course "greatest lower bound". Since inf(S) is the "greatest lower bound" of S there cannot be a lower bound greater than inf(S). Since x> inf(S), x cannot be a lower bound for S. If there did not exist another integer, y, in S, less than x, x would be a lower bound for S.

     
  5. Jun 4, 2013 #4
    Thanks a lot for the responses. The approximation property for infima does indeed seem to close the gap. Funnily, it wasn't in the textbook.
     
  6. Jun 4, 2013 #5

    CAF123

    User Avatar
    Gold Member

    That's okay, it will be in the exercises :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted