Results 1 to 12 of 12

Math Help - Proof involving enumeration of Q

  1. #1
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419

    Proof involving enumeration of Q

    Let (r_{n}) be an enumeration of the set \mathbb{Q}. Show that there exists a subsequence (r_{n_{k}}) such that \lim_{k \to \infty}\, r_{n_{k}}= +\infty.

    Proof

    Choose n_{1}\in \mathbb{N} such that r_{n_{1}} > 1. (This is possible by the use of the Archemedian property.) Choose n_{2} > n_{1} such that n_{2} is the smallest natural number that satisfies r_{n_{2}} > 2r_{n_{1}}. Then r_{n_{2}} > 2 and r_{n_{2}} > r_{n_{1}}. Now choose n_{3} > n_{2} such that n_{3} is the smallest natural number that satisfies r_{n_{3}} > 3r_{n_{2}}. Then r_{n_{3}} > 6 and r_{n_{3}} > r_{n_{2}}. Assume n_{1}< n_{2}< ...< n_{k} have been selected such that r_{n_{k}} > k! and r_{n_{k}} > r_{n_{k-1}}. Select n_{k+1} > n_{k} such that n_{k+1} is the smallest natural number that satisfies r_{n_{k+1}} > (k+1)r_{n_{k}}. This means r_{n_{k+1}} > (k+1)! and r_{n_{k+1}} > r_{n_{k}}. By induction, r_{n_{1}} < r_{n_{2}} < ... < r_{n_{k}} and r_{n_{k}} > k! for all k\in \mathbb{N}. So given M > 0, choose N=M. And so k > N implies r_{n_{k}} > k! \ge k > M. Hence, \lim_{k\to \infty}\, r_{n_{k}} = +\infty. 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.
    Last edited by Pinkk; February 22nd 2010 at 05:23 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Pinkk View Post
    Let (r_{n}) be an enumeration of the set \mathbb{Q}. Show that there exists a subsequence (r_{n_{k}}) such that \lim_{k \to \infty}\, r_{n_{k}}= +\infty.

    Proof

    Choose n_{1}\in \mathbb{N} such that r_{n_{1}} > 1. (This is possible by the use of the Archemedian property.) Choose n_{2} > n_{1} such that n_{2} is the smallest natural number that satisfies r_{n_{2}} > 2r_{n_{1}}. Then r_{n_{2}} > 2 and r_{n_{2}} > r_{n_{2}}. Now choose n_{3} > n_{2} such that n_{3} is the smallest natural number that satisfies r_{n_{3}} > 3r_{n_{2}}. Then r_{n_{3}} > 6 and r_{n_{3}} > r_{n_{2}}. Assume n_{1}< n_{2}< ...< n_{k} have been selected such that r_{n_{k}} > k! and r_{n_{k}} > r_{n_{k-1}}. Select n_{k+1} > n_{k} such that n_{k+1} is the smallest natural number that satisfies r_{n_{k+1}} > (k+1)r_{n_{k}}. This means r_{n_{k+1}} > (k+1)! and r_{n_{k+1}} > r_{n_{k}}. By induction, r_{n_{1}} < r_{n_{2}} < ... < r_{n_{k}} and r_{n_{k}} > k! for all k\in \mathbb{N}. So given M > 0, choose N=M. And so k > N implies r_{n_{k}} > k! \ge k > M. Hence, \lim_{k\to \infty}\, r_{n_{k}} = +\infty. 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.
    If my memory serves f is an enumeration of \mathbb{Q} if f:\mathbb{N}\mapsto\mathbb{Q} is surjective?

    If so, what about this: think about \mathbb{N} as being embedded in the codomain \mathbb{Q} so for each n\in\mathbb{N} there exists some E\subseteq\mathbb{N} such that f(E)=\{n\}. Take x_1=f\left(e\right) where e=\min\left\{E\right\}.

    Or generally, take x_n=f(e_n) where e_n=\min\text{ }f^{-1}\left(n\right). Note that we can take the min by the well-ordering principle.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419
    The way enumeration of \mathbb{Q} was defined in my class is simply that all the elements of \mathbb{Q} are listed as any sequence of choice (since there are infinite ways to "count" \mathbb{Q}). I have not learned what you have suggested in my class (at least as of yet).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Pinkk View Post
    The way enumeration of \mathbb{Q} was defined in my class is simply that all the elements of \mathbb{Q} are listed as any sequence of choice (since there are infinite ways to "count" \mathbb{Q}. I have not learned what you have suggested in my class (at least as of yet).
    Yes you have! You're just not looking hard enough.

    You know that this \left\{r_n\right\}_{n\in\mathbb{N}} is a sequence such that for each q\in\mathbb{Q} we have that q=r_k for some, and possibly many, k\in\mathbb{N}. So, for each n\in\mathbb{N} we know (since \mathbb{N}\subseteq\mathbb{Q}) that there exists some r_k=n. But! There may be twenty gazillion of those k's, so how do we pick one? We know that for eack n\in\mathbb{N} there is a set of numbers E_n such that r_e=n for each e\in E. So define x_n=r_{\varepsilon_n} where \varepsilon_n=\min\text{ }E_n. We can do this by the well-ordering principle. Thus, clearly \{x_n\} is a subsequence of \{r_n\} and \lim\text{ }x_n=\lim\text{ }n
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419
    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 r_{n_{k}} > k for all k\in \mathbb{N}. I really don't understand how you know such a set E_{n} exists and how the logic follows after that point.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Pinkk View Post
    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 r_{n_{k}} > k for all k\in \mathbb{N}. I really don't understand how you know such a set E_{n} 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 \left\{r_n\right\}_{n\in\mathbb{N}} is a list of \mathbb{Q}. To be listed means that one element is listed at least once (maybe more than once). So, we know that for each q\in\mathbb{Q} that q is listed at least once. Thus, q=r_k for some k. But, since \mathbb{N}\subseteq\mathbb{Q} we know (by what was just said) for each n\in\mathbb{N} there exist some r_k=n.

    So, let's define r_{e_1}=1 where e_1 is the smallest number k such that r_k=1. Now, since e_1 is finite we know that not all of \mathbb{N}-\{1\} can be listed before e_1. Thus, define the set E_2=\left\{n>1:n=r_k,\text{ for some }k>e_1\right\}. By previous discussion we know that E_2\ne\varnothing and so let n_2=\min\text{ }E_2, and so let r_{e_2}=n_2 where e_2 is the smallest number greater than e_1 such that r_{e_2}=n_2. Since for each n\in\mathbb{N} we've exhausted only finitely many elements of \mathbb{N} we can continue in this way. Thus, the sequence \left\{r_{e_n}\right\}_{n\in\mathbb{N}} is a subsequence of \{r_n\} and r_{e_n}\geqslant n. Thus \lim\text{ }r_{e_n}=\infty.

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419
    Okay, I think I understand it for the most part now. Was my proof also legitimate or no?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Pinkk View Post
    Okay, I think I understand it for the most part now. Was my proof also legitimate or no?
    It looks fairly correct, except I feel as though you would need to give justification for why there exists n_2 such that r_{n_2}>2r_{n_1}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419
    I don't know how to put it formally, but wouldn't that mean that all rational numbers twice as large would be before the term s_{n_{1}}, and I don't believe that is possible. Is there a way to formally show this?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Pinkk View Post
    I don't know how to put it formally, but wouldn't that mean that all rational numbers twice as large would be before the term s_{n_{1}}, and I don't believe that is possible. Is there a way to formally show this?
    If I am understanding your intent in the proof, try mimicking what I did with the indices.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419
    Hmm, okay. I was just thinking though, borrowing from the argument you gave in that proof, since n_{1} is finite, we know that all rational numbers greater than 2r_{n_{1}} cannot be listed before n_{1}, right? Could I use that in my proof as justification? And then that argument can be used for every n_{k} since if the opposite were true, an infinite number of rational numbers are listed using a finite number of terms, which is impossible...
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419
    Let (r_{n}) be an enumeration of \mathbb{Q}. Choose n_{1} \in \mathbb{N} such that n_{1} is the smallest natural number where r_{n_{1}}=1. Since n_{1} is a finite number, all the elements of \mathbb{N} -\{1\} cannot be listed before n_{1}, so choose n_{2}>n_{1} such that n_{2} is the smallest natural number where r_{n_{2}}=2. Assume n_{1}<n_{2}<...<n_{k} have been chosen such that r_{n_{k}}=k. Since n_{k} is finite, all the elements of \mathbb{N}-\{1,2,...,k\} cannot be listed before n_{k}, so choose n_{k+1}>n_{k} such that n_{k+1} is the smallest natural number where r_{n_{k}}=k+1. By induction, (r_{n_{k}}) is a subsequence where r_{n_{k}}=k for all k\in \mathbb{N}. And so \lim_{k\to \infty}\,r_{n_{k}}=\lim_{k\to \infty}\,k= +\infty. Q.E.D.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Two Enumeration Questions
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: January 14th 2011, 04:00 AM
  2. Enumeration question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2009, 07:21 PM
  3. Enumeration question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 14th 2009, 07:34 PM
  4. Enumeration problems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2009, 01:08 AM
  5. enumeration
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 23rd 2005, 02:54 PM

Search Tags


/mathhelpforum @mathhelpforum