Thread: Proof involving enumeration of Q

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

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

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

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

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

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

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 $n_2$ such that $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 $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 $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 $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...

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