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.

oh well, guess I'll have to BS it on this one

Quote:

---

Originally Posted by Th3sandm4n

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

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

---

All right, I think I see the problem you are trying to describe.

Suppose you want to show that a statement is true for all positive integers . If you are using the method of contradiction method, this means assuming that the set of all positive integers for which is false is nonempty. What you want to do now is to show that 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.

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 :)