Well Ordering Proof?

Printable View

January 13th 2010, 08:31 PM
mathgirl13

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!!!
January 13th 2010, 08:32 PM
mathgirl13

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.
January 13th 2010, 09:06 PM
Drexel28

Quote:

Originally Posted by mathgirl13

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?
January 13th 2010, 11:56 PM
Laurent

Quote:

Originally Posted by mathgirl13

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$ .
January 14th 2010, 10:08 AM
mathgirl13

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!
January 14th 2010, 10:10 AM
mathgirl13

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.
January 14th 2010, 10:52 AM
Laurent

Quote:

Originally Posted by mathgirl13

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.
January 14th 2010, 06:29 PM
Drexel28

Quote:

Originally Posted by mathgirl13

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.
January 14th 2010, 06:31 PM
mathgirl13

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.