Let be an enumeration of the set . Show that there exists a subsequence such that .
Proof
Choose such that . (This is possible by the use of the Archemedian property.) Choose such that is the smallest natural number that satisfies . Then and . Now choose such that is the smallest natural number that satisfies . Then and . Assume have been selected such that and . Select such that is the smallest natural number that satisfies . This means and . By induction, and for all . So given , choose . And so implies . Hence, . Q.E.D.
Is this proof correct; can I construct the subsequence in such a way? And if not, how should I go about this proof? Thanks.
Yes you have! You're just not looking hard enough.
You know that this is a sequence such that for each we have that for some, and possibly many, . So, for each we know (since ) that there exists some . But! There may be twenty gazillion of those 's, so how do we pick one? We know that for eack there is a set of numbers such that for each . So define where . We can do this by the well-ordering principle. Thus, clearly is a subsequence of and
I kinda get it but not really. What I meant to say is that we have never used this type of method, or anything related to that type of method in my class, to prove limits. In fact, the back of the book gives the hint to construct it so that for all . I really don't understand how you know such a set exists and how the logic follows after that point.
I will try one more time, especially because I misread the question. Ok, so we know that is a list of . To be listed means that one element is listed at least once (maybe more than once). So, we know that for each that is listed at least once. Thus, for some . But, since we know (by what was just said) for each there exist some .
So, let's define where is the smallest number such that . Now, since is finite we know that not all of can be listed before . Thus, define the set . By previous discussion we know that and so let , and so let where is the smallest number greater than such that . Since for each we've exhausted only finitely many elements of we can continue in this way. Thus, the sequence is a subsequence of and . Thus .
The problem with my previous answer was the the set of indices in your subsequence MUST be increasing. There was no guarantee in my last post they they were.
Note: I relied heavily on the well-ordering principle for this.
Hmm, okay. I was just thinking though, borrowing from the argument you gave in that proof, since is finite, we know that all rational numbers greater than cannot be listed before , right? Could I use that in my proof as justification? And then that argument can be used for every since if the opposite were true, an infinite number of rational numbers are listed using a finite number of terms, which is impossible...
Let be an enumeration of . Choose such that is the smallest natural number where . Since is a finite number, all the elements of cannot be listed before , so choose such that is the smallest natural number where . Assume have been chosen such that . Since is finite, all the elements of cannot be listed before , so choose such that is the smallest natural number where . By induction, is a subsequence where for all . And so . Q.E.D.