## Proof by transfinite induction?

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
 PhysOrg.com science news on PhysOrg.com >> A robot that runs like a cat (w/ Video)>> Global cooling as significant as global warming, research shows>> 'Chase and run' cell movement mechanism explains process of metastasis
 Recognitions: Homework Help Science Advisor I think you are overthinking this. If x0>x1>x2>... doesn't terminate then X doesn't have a least element, does it?
 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?

Recognitions:
Homework Help

## Proof by transfinite induction?

 Quote by 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?
Yes, looks to me like that's a contradiction, which proves that X must be finite.
 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?
 Recognitions: Homework Help Science Advisor 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.
 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!

Recognitions:
Homework Help
 Quote by 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!
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.

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?
 Recognitions: Homework Help Science Advisor [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.
 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.

Recognitions:
Homework Help
 Quote by 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.
Sure, ok. X isn't dense. Now can you solve the original problem?
 Well we know X has a first and last element by the earlier contradiction, and is not dense. So it's finite. Correct?

Recognitions:
Homework Help