1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by transfinite induction?

  1. Oct 31, 2009 #1
    1. The problem statement, all variables and given/known data

    Show that if X is a subset of a well-ordered set (A, ≤ ) such that x0 > x1 > x2... then X must be finite.

    3. The attempt at a solution

    It seems like there's an obvious solution in that we know X must be well ordered, so has a least element. But by the question, X has a maximum element (x0), so X must be finite. I don't know what's wrong with this argument, but I don't think it's right.

    Moving on to what I think must be the real solution, I think transfinite induction might be involved. I think I need to prove something similar to above, like if I define P(x) to be the property that x > x* for all x in X, then there would be a minimum element. So if P(y) is true for all y < x, then P(x) is true for all x.

    If this is totally wrong, please suggest another avenue of investigation as I'm really not sure about this question.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Oct 31, 2009 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I think you are overthinking this. If x0>x1>x2>... doesn't terminate then X doesn't have a least element, does it?
     
  4. Nov 1, 2009 #3
    After sleeping on it, I realise I was thinking of X as an interval, not a set.

    Hang on, if x0>x1>x2>... doesn't terminate it doesn't have a least element. But we know X is a subset of a well ordered set (A,≤), so is well ordered by ≤. So ... x2 ≤ x1 ≤ x0 WILL have a least element. Is that right?
     
  5. Nov 1, 2009 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, looks to me like that's a contradiction, which proves that X must be finite.
     
  6. Nov 1, 2009 #5
    Wow, that was much simpler than I thought it would be. Teach me to judge a question by how many marks it's worth.

    There's a follow on question "Deduce that any strictly descending chain of ordinals has finite length."

    Assume the chain is infinite α > β > ..

    But we know α > β > .. > 1 > 0. Contradiction. Set has finite length.

    Would that suffice?
     
  7. Nov 1, 2009 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It suffices for me. It's the same proof as the first question, right? But why are you bringing 1 and 0 into this? The contradiction is not having a minimum member of the chain.
     
  8. Nov 2, 2009 #7
    Hm, well backtracking from the follow on question for a second, it seems that if we know the set has a minimum and a maximum element we can't necessarily say it is finite. Surely we have to consider the case where X is dense?

    We'd need to prove that there exists a bijection from X to {1,...,n}. We have a theorem that (A, ≤) and (B, ≤') are well ordered then either (B,≤') ⊲ (is order isomorphic to an initial subset of) (A, ≤) or vice versa. So replacing A by X and B by N and showing X ⊲ N will complete the proof. Which I think means the stuff we've done so far has been made slightly redundant!
     
  9. Nov 2, 2009 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You are going to have a hard time finding a set that is dense AND well ordered. And showing X is order isomorphic to an initial subset of N doesn't say it can't be isomorphic to N itself. It doesn't show it's finite.
     
  10. Nov 3, 2009 #9
    So should I try and prove that X is not dense?

    OR, is there a way I could adapt the isomorphism method? I found a lemma that states if X is well ordered, each element of X except the first is a successor of some other element of X and X has no greatest element then (X, <) is isomorphic to (N, <). Clearly the first two statements are true, but could I not try and change the third condition to "DOES have a greatest element" and change the conclusion to something suitable.

    I don't really understand this, could you expand?


    EDIT: Also, is [0,1] U Q not a well ordered dense set?
     
    Last edited: Nov 3, 2009
  11. Nov 3, 2009 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    [0,1] is not a well ordered set. Q is not a well ordered set. [0,1] U Q is not a well ordered set. I suggest you go back a few posts and try to prove a set X such that x0>x1>x2>... is finite directly, just from the definition of well ordering. Don't try and change lemmas, and don't think hard about sets that aren't well ordered.
     
  12. Nov 3, 2009 #11
    Ok, hammer is approaching the head of the nail.

    We haven't been explicitly told that well ordered sets cannot be dense. But, I think from the proposition "every element in X except the last one has an immediate successor" we can prove that X is not dense.

    Starting with an xi in X, we know that there is a set of elements that follows xi that is a subset of X. According to our definition of a well ordered set, this subset will have a least element, say xj. Now, xi ≺ xj, and by our definition of xj there is no element between the two. Therefore X is not dense.
     
  13. Nov 3, 2009 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Sure, ok. X isn't dense. Now can you solve the original problem?
     
  14. Nov 3, 2009 #13
    Well we know X has a first and last element by the earlier contradiction, and is not dense. So it's finite. Correct?
     
  15. Nov 3, 2009 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Sort of. But you don't need to say anything about 'dense' at all. If x0>x1>x2>... doesn't terminate, then for every x_k in X, x_k>x_k+1. So x_k isn't a least element for any k. So there is no least element. Same idea for the chain. If every element of X is greater than some other element of X, then there is no minimum.
     
  16. Nov 3, 2009 #15
    I see, I think I just needed the argument about density before to get it straight in my head. I should be able to form a coherent proof from all this.

    Thank you very much for your help, it's greatly appreciated.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by transfinite induction?
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...