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.
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!!!
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 is introduced works the same way as the step where is introduced: is the highest lower bound, and it is not in , therefore each interval (for ) contains an element of , and we apply this to and then to .
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 is a natural number, that's why we need x and y, not just x.