3
$\begingroup$

I'm trying to prove the following:

Let $\Bbb Q$ be the countable set of rational numbers and $\{x_n\}_{n=1}^\infty$ be a sequence such that for every q $\in$ $\Bbb Q$ there is a $n \in \Bbb N$ with $x_n = q$. Prove that there is such a sequence $\{x_n\}$.

My initial thoughts for an attempt at a solution:

We know that $|\Bbb Q| = |\Bbb N|$ by the Cantor Theorem. Further, I can show that there is a bijection between $\Bbb Q$ and $\Bbb N$.

If I define $\{x_n\}_{n=1}^\infty$ as some relation between $(p,q) \in \Bbb Z \times \Bbb Z$, will ths properly prove that such a sequence exists?

$\endgroup$
  • $\begingroup$ For an explicit bijection, see -math.stackexchange.com/questions/7643/… $\endgroup$ – Thomas Shelby Dec 9 '18 at 17:15
  • 1
    $\begingroup$ Thanks Thomas! This is wonderful to see! $\endgroup$ – user624612 Dec 9 '18 at 17:20
  • $\begingroup$ What is the definition of an infinite sequence $\{x_n\}_{n\in \Bbb N} $? It's a function $ f$ with domain $\Bbb N,$ except we write $x_n$ for $f(n)$..... And $|\Bbb Q|=|\Bbb N$| is an abbreviation for, or an equivalent to, the statement that there exists a bijection $f:\Bbb N\to \Bbb Q.$ And that's all there is to it. $\endgroup$ – DanielWainfleet Dec 9 '18 at 20:19
  • $\begingroup$ You may enjoy the small book Stories About Sets, by Vilenkin. $\endgroup$ – DanielWainfleet Dec 9 '18 at 20:22
0
$\begingroup$

It is actually quit easy once you know that $|\mathbb{Q}|=|\mathbb{N}|$ as this implies that there exists a bijection $f:\mathbb{N}\rightarrow \mathbb{Q}$. Now simply let $x_n = f(n)$.

$\endgroup$
  • $\begingroup$ Thank you! This makes sense! I didn't know if much more was needed other than defining the bijective mapping, but it seems that this is about it. $\endgroup$ – user624612 Dec 9 '18 at 17:23
0
$\begingroup$

The answer to this question is going to depend upon what you have available as definitions. Where I come from, a sequence of elements from a set $S$ is just a function $f:\mathbb{N}\rightarrow S$; if that is the case for you, since you already know there is a bijection from $\mathbb{N}$ to $\mathbb{Q}$ you are done!

If you wanted to explicitly write down such a sequence, then yes, you will probably want to start with a surjection from $\mathbb{N}$ to $\mathbb{Z}\times \mathbb{Z}$, and then a surjection from $\mathbb{Z}\times \mathbb{Z}$ to $\mathbb{Q}$. The composition of these functions will be a sequence that hits every rational number.

How to build such surjections? You could define $f:\mathbb{N}\rightarrow \mathbb{Z}\times \mathbb{Z}$ in pieces, say by sending numbers of the form $2^i3^j$ to $(i,j)$, numbers of the form $5^i7^j$ to $(-i,-j)$, numbers of the form $11^i13^j$ to $(i,-j)$, and numbers of the form $17^i19^j$ to $(-i,j)$, with everything else sent to $(0,0)$. You could define $g:\mathbb{Z}\times \mathbb{Z} \rightarrow \mathbb{Q}$ by sending $(0,q)$ and $(p,0)$ to $0$, and all other $(p,q)$ to $p/q$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy