# Thread: Proof involving enumeration of Q

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

2. Originally Posted by Pinkk
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.

3. 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).

4. Originally Posted by Pinkk
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$

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

6. Originally Posted by Pinkk
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.

7. Okay, I think I understand it for the most part now. Was my proof also legitimate or no?

8. Originally Posted by Pinkk
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}$

9. 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?

10. Originally Posted by Pinkk
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.

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

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