# Homework Help: Proof by transfinite induction?

1. Oct 31, 2009

### oliphant

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.

1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Oct 31, 2009

### Dick

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

3. Nov 1, 2009

### oliphant

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?

4. Nov 1, 2009

### Dick

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

5. Nov 1, 2009

### 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?

6. Nov 1, 2009

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

7. Nov 2, 2009

### 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!

8. Nov 2, 2009

### Dick

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.

9. Nov 3, 2009

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

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
10. Nov 3, 2009

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

11. Nov 3, 2009

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

12. Nov 3, 2009

### Dick

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

13. Nov 3, 2009

### oliphant

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

14. Nov 3, 2009

### Dick

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.

15. Nov 3, 2009

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