Results 1 to 5 of 5

Math Help - Well-Ordering Proof Skeleton

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    27

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    oh well, guess I'll have to BS it on this one
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by Th3sandm4n View Post
    Just for illustrative purposes, let P(x) = x^2 >= 2x.

    Prove P(x) for all positive x in Z.
    1^2\ \not\geqslant\ 2\cdot1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    All right, I think I see the problem you are trying to describe.

    Suppose you want to show that a statement P(n) is true for all positive integers n. If you are using the method of contradiction method, this means assuming that the set T of all positive integers for which P(n) is false is nonempty. What you want to do now is to show that 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    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
    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?
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: January 14th 2010, 06:31 PM

Search Tags


/mathhelpforum @mathhelpforum