Results 1 to 12 of 12

Thread: 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 $\displaystyle (r_{n})$ be an enumeration of the set $\displaystyle \mathbb{Q}$. Show that there exists a subsequence $\displaystyle (r_{n_{k}})$ such that $\displaystyle \lim_{k \to \infty}\, r_{n_{k}}= +\infty$.

    Proof

    Choose $\displaystyle n_{1}\in \mathbb{N}$ such that $\displaystyle r_{n_{1}} > 1$. (This is possible by the use of the Archemedian property.) Choose $\displaystyle n_{2} > n_{1}$ such that $\displaystyle n_{2}$ is the smallest natural number that satisfies $\displaystyle r_{n_{2}} > 2r_{n_{1}}$. Then $\displaystyle r_{n_{2}} > 2$ and $\displaystyle r_{n_{2}} > r_{n_{1}}$. Now choose $\displaystyle n_{3} > n_{2}$ such that $\displaystyle n_{3}$ is the smallest natural number that satisfies $\displaystyle r_{n_{3}} > 3r_{n_{2}}$. Then $\displaystyle r_{n_{3}} > 6$ and $\displaystyle r_{n_{3}} > r_{n_{2}}$. Assume $\displaystyle n_{1}< n_{2}< ...< n_{k}$ have been selected such that $\displaystyle r_{n_{k}} > k!$ and $\displaystyle r_{n_{k}} > r_{n_{k-1}}$. Select $\displaystyle n_{k+1} > n_{k}$ such that $\displaystyle n_{k+1}$ is the smallest natural number that satisfies $\displaystyle r_{n_{k+1}} > (k+1)r_{n_{k}}$. This means $\displaystyle r_{n_{k+1}} > (k+1)!$ and $\displaystyle r_{n_{k+1}} > r_{n_{k}}$. By induction, $\displaystyle r_{n_{1}} < r_{n_{2}} < ... < r_{n_{k}}$ and $\displaystyle r_{n_{k}} > k!$ for all $\displaystyle k\in \mathbb{N}$. So given $\displaystyle M > 0$, choose $\displaystyle N=M$. And so $\displaystyle k > N$ implies $\displaystyle r_{n_{k}} > k! \ge k > M$. Hence, $\displaystyle \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; Feb 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
    22
    Quote Originally Posted by Pinkk View Post
    Let $\displaystyle (r_{n})$ be an enumeration of the set $\displaystyle \mathbb{Q}$. Show that there exists a subsequence $\displaystyle (r_{n_{k}})$ such that $\displaystyle \lim_{k \to \infty}\, r_{n_{k}}= +\infty$.

    Proof

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

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

    Or generally, take $\displaystyle x_n=f(e_n)$ where $\displaystyle 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 $\displaystyle \mathbb{Q}$ was defined in my class is simply that all the elements of $\displaystyle \mathbb{Q}$ are listed as any sequence of choice (since there are infinite ways to "count" $\displaystyle \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
    22
    Quote Originally Posted by Pinkk View Post
    The way enumeration of $\displaystyle \mathbb{Q}$ was defined in my class is simply that all the elements of $\displaystyle \mathbb{Q}$ are listed as any sequence of choice (since there are infinite ways to "count" $\displaystyle \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 $\displaystyle \left\{r_n\right\}_{n\in\mathbb{N}}$ is a sequence such that for each $\displaystyle q\in\mathbb{Q}$ we have that $\displaystyle q=r_k$ for some, and possibly many, $\displaystyle k\in\mathbb{N}$. So, for each $\displaystyle n\in\mathbb{N}$ we know (since $\displaystyle \mathbb{N}\subseteq\mathbb{Q}$) that there exists some $\displaystyle r_k=n$. But! There may be twenty gazillion of those $\displaystyle k$'s, so how do we pick one? We know that for eack $\displaystyle n\in\mathbb{N}$ there is a set of numbers $\displaystyle E_n$ such that $\displaystyle r_e=n$ for each $\displaystyle e\in E$. So define $\displaystyle x_n=r_{\varepsilon_n}$ where $\displaystyle \varepsilon_n=\min\text{ }E_n$. We can do this by the well-ordering principle. Thus, clearly $\displaystyle \{x_n\}$ is a subsequence of $\displaystyle \{r_n\}$ and $\displaystyle \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 $\displaystyle r_{n_{k}} > k$ for all $\displaystyle k\in \mathbb{N}$. I really don't understand how you know such a set $\displaystyle 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
    22
    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 $\displaystyle r_{n_{k}} > k$ for all $\displaystyle k\in \mathbb{N}$. I really don't understand how you know such a set $\displaystyle 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 $\displaystyle \left\{r_n\right\}_{n\in\mathbb{N}}$ is a list of $\displaystyle \mathbb{Q}$. To be listed means that one element is listed at least once (maybe more than once). So, we know that for each $\displaystyle q\in\mathbb{Q}$ that $\displaystyle q$ is listed at least once. Thus, $\displaystyle q=r_k$ for some $\displaystyle k$. But, since $\displaystyle \mathbb{N}\subseteq\mathbb{Q}$ we know (by what was just said) for each $\displaystyle n\in\mathbb{N}$ there exist some $\displaystyle r_k=n$.

    So, let's define $\displaystyle r_{e_1}=1$ where $\displaystyle e_1$ is the smallest number $\displaystyle k$ such that $\displaystyle r_k=1$. Now, since $\displaystyle e_1$ is finite we know that not all of $\displaystyle \mathbb{N}-\{1\}$ can be listed before $\displaystyle e_1$. Thus, define the set $\displaystyle E_2=\left\{n>1:n=r_k,\text{ for some }k>e_1\right\}$. By previous discussion we know that $\displaystyle E_2\ne\varnothing$ and so let $\displaystyle n_2=\min\text{ }E_2$, and so let $\displaystyle r_{e_2}=n_2$ where $\displaystyle e_2$ is the smallest number greater than $\displaystyle e_1$ such that $\displaystyle r_{e_2}=n_2$. Since for each $\displaystyle n\in\mathbb{N}$ we've exhausted only finitely many elements of $\displaystyle \mathbb{N}$ we can continue in this way. Thus, the sequence $\displaystyle \left\{r_{e_n}\right\}_{n\in\mathbb{N}}$ is a subsequence of $\displaystyle \{r_n\}$ and $\displaystyle r_{e_n}\geqslant n$. Thus $\displaystyle \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
    22
    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 $\displaystyle n_2$ such that $\displaystyle 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 $\displaystyle 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
    22
    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 $\displaystyle 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 $\displaystyle n_{1}$ is finite, we know that all rational numbers greater than $\displaystyle 2r_{n_{1}}$ cannot be listed before $\displaystyle n_{1}$, right? Could I use that in my proof as justification? And then that argument can be used for every $\displaystyle 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 $\displaystyle (r_{n})$ be an enumeration of $\displaystyle \mathbb{Q}$. Choose $\displaystyle n_{1} \in \mathbb{N}$ such that $\displaystyle n_{1}$ is the smallest natural number where $\displaystyle r_{n_{1}}=1$. Since $\displaystyle n_{1}$ is a finite number, all the elements of $\displaystyle \mathbb{N} -\{1\}$ cannot be listed before $\displaystyle n_{1}$, so choose $\displaystyle n_{2}>n_{1}$ such that $\displaystyle n_{2}$ is the smallest natural number where $\displaystyle r_{n_{2}}=2$. Assume $\displaystyle n_{1}<n_{2}<...<n_{k}$ have been chosen such that $\displaystyle r_{n_{k}}=k$. Since $\displaystyle n_{k}$ is finite, all the elements of $\displaystyle \mathbb{N}-\{1,2,...,k\}$ cannot be listed before $\displaystyle n_{k}$, so choose $\displaystyle n_{k+1}>n_{k}$ such that $\displaystyle n_{k+1}$ is the smallest natural number where $\displaystyle r_{n_{k}}=k+1$. By induction, $\displaystyle (r_{n_{k}})$ is a subsequence where $\displaystyle r_{n_{k}}=k$ for all $\displaystyle k\in \mathbb{N}$. And so $\displaystyle \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: Jan 14th 2011, 04:00 AM
  2. Enumeration question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 15th 2009, 07:21 PM
  3. Enumeration question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 14th 2009, 07:34 PM
  4. Enumeration problems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 12th 2009, 01:08 AM
  5. enumeration
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Oct 23rd 2005, 02:54 PM

Search Tags


/mathhelpforum @mathhelpforum