Proof by transfinite induction?

[oliphant]

Homework Statement

Show that if X is a subset of a well-ordered set (A, ≤ ) such that x₀ > x₁ > x₂... then X must be finite.

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 (x₀), 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.

 

[Dick]

I think you are overthinking this. If x0>x1>x2>... doesn't terminate then X doesn't have a least element, does it?

 

[oliphant]

After sleeping on it, I realize 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?

 

[Dick]

After sleeping on it, I realize 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?

Yes, looks to me like that's a contradiction, which proves that X must be finite.

 

[oliphant]

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?

 

[Dick]

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.

 

[oliphant]

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!

 

[Dick]

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!

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.

 

[oliphant]

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.

And showing X is order isomorphic to an initial subset of N doesn't say it can't be isomorphic to N itself.

I don't really understand this, could you expand?EDIT: Also, is [0,1] U Q not a well ordered dense set?

 

[Dick]

[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.

 

[oliphant]

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 x_i in X, we know that there is a set of elements that follows x_i that is a subset of X. According to our definition of a well ordered set, this subset will have a least element, say x_j. Now, x_i ≺ x_j, and by our definition of x_j there is no element between the two. Therefore X is not dense.

 

[Dick]

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 x_i in X, we know that there is a set of elements that follows x_i that is a subset of X. According to our definition of a well ordered set, this subset will have a least element, say x_j. Now, x_i ≺ x_j, and by our definition of x_j there is no element between the two. Therefore X is not dense.

Sure, ok. X isn't dense. Now can you solve the original problem?

 

[oliphant]

Well we know X has a first and last element by the earlier contradiction, and is not dense. So it's finite. Correct?

 

[Dick]

Well we know X has a first and last element by the earlier contradiction, and is not dense. So it's finite. Correct?

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.

 

[oliphant]

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.