# Well-Ordering Proof Skeleton

• Jan 29th 2009, 07:50 PM
Th3sandm4n
Well-Ordering Proof Skeleton
Hello, I am recently trying to learn the whole concept of Well-Ordering, and my teacher isn't one to show us how to do things, instead for us to figure it out.
I believe I get the concept, I just want to make sure I have my proof skeleton down and would welcome any input. Thanks.

Just for illustrative purposes, let P(x) = x^2 >= 2x.

Prove P(x) for all positive x in Z.

Let T be a non-empty set of positive integers such that P(x) is not true. By the Well-Ordering Principle T contains a smallest element k.

(This is my first trouble, I don't really understand how T can have a smallest element k, since P(x) holds for k. But I KNOW you are supposed to somehow show that k-1 also holds, and this contradicts that k is the smallest element. But it seems that you just have to show that T is empty, that is k isn't even in T, so T is empty, and therefore all positive integers hold for P(x))

plug in k in P(k) and show that it is true. Therefore , T is empty. Contradiction and P(x) must hold for all positive integers.

Thanks for any input, this is reeaaaaally killing me. After having mathematical induction drilled into me, I understand that, and Well-Ordering doesn't seem to make any sense other than that "duh" kind of way. I don't really know how to implement it in proofs.
• Jan 30th 2009, 05:39 AM
Th3sandm4n
oh well, guess I'll have to BS it on this one
• Jan 30th 2009, 05:06 PM
JaneBennet
Quote:

Originally Posted by Th3sandm4n
Just for illustrative purposes, let P(x) = x^2 >= 2x.

Prove P(x) for all positive x in Z.

$\displaystyle 1^2\ \not\geqslant\ 2\cdot1$
• Jan 30th 2009, 05:18 PM
JaneBennet
All right, I think I see the problem you are trying to describe.

Suppose you want to show that a statement $\displaystyle P(n)$ is true for all positive integers $\displaystyle n$. If you are using the method of contradiction method, this means assuming that the set $\displaystyle T$ of all positive integers for which $\displaystyle P(n)$ is false is nonempty. What you want to do now is to show that $\displaystyle T$ has no least element. This would contradict the well-ordering principle, hence proving that the assumption that T is nonempty is false. The is the whole idea of the proof.
• Jan 31st 2009, 10:31 AM
Th3sandm4n
Ah it was 2^x >= 2x, my bad lol.

Yeah I was trying to do something like that. I ended up with something bordering like this (I turned in my work already so I don't have the exact reference):

assume that T does have a smallest element k.
Then showed that k wasn't in T,

Then showed that k-1 wasn't in T.

So then T must be empty and contradicting, so all positive integers satisfy P(x).

Like I said, I just turned this in. I don't really see a systematic way to use Well Ordering (like I can in induction). To me it seems like if I assume that it has a smallest element, then show it's not in T, that is the end. But I KNOW you have to use k-1 in some way (this is how it relates to induction, no?)

Point being, I probably missed this one but I still would really like to understand, because I can't conceptualize it at all. I have a feeling it is something REALLY simple that I just can't grasp and/or see.

Thanks for the input though. Any references online(I could find no practice problems with solutions to check and we don't have a book) or maybe some small samples would be GREATLY appreciated :)