Results 1 to 9 of 9

Math Help - Well Ordering Proof?

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    16

    Unhappy Well Ordering Proof?

    Can someone explain this well ordering proof? Or explain where it's wrong since my dog jumped on my keyboard and messed up part of my notes from class (lol).

    Theorem: Well Ordering Principle (W.O.P.)
    Every non-empty subset of the ℕ (natural numbers) has a smallest element

    Proof: Let S be a subset of ℕ, S ≠ ∅ (empty set)
    Since S is bounded below, the infemum of S exists and is a real number.
    Let ∝ = inf S = glb S.
    If ∝ ɛ S then we are done.
    Suppose ∝ is not ɛ S.
    There must be an element of S smaller than ∝+1
    Since ∝ is the greatest lower bound of S & x is not in S this element cannot be ∝ since ∝ is not in S
    Ǝ x ɛ S ⋺ ∝<x<∝+1
    NOTE: that x is not a lower bound for S since x>∝ and ∝ is the greatest lower bound of S
    Therefore, Ǝ y ɛ S ⋺ ∝ <x<y<∝+1
    Therefore, 0<x-y<1 #
    This is a contradiction since x and y ɛ ℕ

    I really think it is messed up a bit somewhere but just started the class and did not get a good chance to look at it before it got messed up...

    Any help is greatly greatly appreciated!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2009
    Posts
    16
    And sorry for the random spaces, I copied and pasted from Word and that's how it turned out after I posted the thread, didn't look like that originally.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mathgirl13 View Post
    Can someone explain this well ordering proof? Or explain where it's wrong since my dog jumped on my keyboard and messed up part of my notes from class (lol).

    Theorem: Well Ordering Principle (W.O.P.)
    Every non-empty subset of the ℕ (natural numbers) has a smallest element

    Proof: Let S be a subset of ℕ, S ≠ ∅ (empty set)
    Since S is bounded below, the infemum of S exists and is a real number.
    Let ∝ = inf S = glb S.
    If ∝ ɛ S then we are done.
    Suppose ∝ is not ɛ S.
    There must be an element of S smaller than ∝+1
    Since ∝ is the greatest lower bound of S & x is not in S this element cannot be ∝ since ∝ is not in S
    Ǝ x ɛ S ⋺ ∝<x<∝+1
    NOTE: that x is not a lower bound for S since x>∝ and ∝ is the greatest lower bound of S
    Therefore, Ǝ y ɛ S ⋺ ∝ <x<y<∝+1
    Therefore, 0<x-y<1 #
    This is a contradiction since x and y ɛ ℕ

    I really think it is messed up a bit somewhere but just started the class and did not get a good chance to look at it before it got messed up...

    Any help is greatly greatly appreciated!!!
    Do you want a new proof?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by mathgirl13 View Post
    Can someone explain this well ordering proof? Or explain where it's wrong since my dog jumped on my keyboard and messed up part of my notes from class (lol).

    Theorem: Well Ordering Principle (W.O.P.)
    Every non-empty subset of the ℕ (natural numbers) has a smallest element

    Proof: Let S be a subset of ℕ, S ≠ ∅ (empty set)
    Since S is bounded below, the infemum of S exists and is a real number.
    Let ∝ = inf S = glb S.
    If ∝ ɛ S then we are done.
    Suppose ∝ is not ɛ S.
    There must be an element of S smaller than ∝+1
    Since ∝ is the greatest lower bound of S & x is not in S this element cannot be ∝ since ∝ is not in S
    Ǝ x ɛ S ⋺ ∝<x<∝+1
    NOTE: that x is not a lower bound for S since x>∝ and ∝ is the greatest lower bound of S
    Therefore, Ǝ y ɛ S ⋺ ∝ <y<x<∝+1
    Therefore, 0<x-y<1 #
    This is a contradiction since x and y ɛ ℕ

    I really think it is messed up a bit somewhere but just started the class and did not get a good chance to look at it before it got messed up...

    Any help is greatly greatly appreciated!!!
    Looks like your dog didn't mess it up too much: there was only one mistake, it is corrected in red above. Is there something in the proof you don't understand?
    The step where y is introduced works the same way as the step where x is introduced: \alpha is the highest lower bound, and it is not in S, therefore each interval (\alpha,\beta) (for \beta>\alpha) contains an element of S, and we apply this to \beta=\alpha+1 and then to \beta=x.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    16
    The "since" sentence before there exists an x screws me up a bit, and these are all natural numbers, meaning 1,2,3, etc. so the greatest lower bound plus one will have an element lower than it, but it is all whole numbers so I keep coming back to it's must be alpha..I don't know, I understand it and yet at the same time I don't. Maybe I'm just over thinking it? Thanks for fixing the proof also, and the help!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2009
    Posts
    16
    And drexel, I don't know, maybe a new proof would help. I tried searching for some online and couldn't really find anything. I wish my book for the class would come.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by mathgirl13 View Post
    The "since" sentence before there exists an x screws me up a bit, and these are all natural numbers, meaning 1,2,3, etc. so the greatest lower bound plus one will have an element lower than it, but it is all whole numbers so I keep coming back to it's must be alpha..I don't know, I understand it and yet at the same time I don't. Maybe I'm just over thinking it? Thanks for fixing the proof also, and the help!
    Yes, this is this kind of idea, but you don't say it properly; the difficulty maybe is that we are doing a proof by contradiction, hence something "weird" (a contradiction) must happen at some time. We don't know a priori whether \alpha is a natural number, that's why we need x and y, not just x.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mathgirl13 View Post
    And drexel, I don't know, maybe a new proof would help. I tried searching for some online and couldn't really find anything. I wish my book for the class would come.
    Do it by induction.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2009
    Posts
    16
    Oooooooo!!! Wow that all makes perfect sense now!!! Thank you so much!!!!! I can't believe I thought alpha had to be natural number too.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Well-Ordering Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 18th 2011, 01:06 AM
  2. Replies: 5
    Last Post: November 25th 2010, 11:11 AM
  3. Ordering proof?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 25th 2010, 02:10 AM
  4. Proof using Well Ordering
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 27th 2010, 10:17 PM
  5. Well-Ordering Proof Skeleton
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 31st 2009, 10:31 AM

Search Tags


/mathhelpforum @mathhelpforum