2
$\begingroup$

I have devised the following proof for the countability of $\mathbb Q$.

Define countable number of bijections in this way:

$f_1(n)=\frac {1}{n}, n\in\mathbb N$

$f_2(n)=\frac {2}{n}, n\in\mathbb N$

...

$f_k(n)=\frac {k}{n}, n\in\mathbb N$

...

And also for negative subscripts

$f_{-k}(n)=-f_k(n)$

Now denote with $R_k$ the range of $f_k$.

Then we have $\lim_{m\to\infty}\bigcup_{k=-m}^{m}R_k=\mathbb Q\setminus\{0\}$ so the set $\mathbb Q \setminus \{0\}$ is countable as countable union of countable sets.

Now we add $0$ to $\mathbb Q\setminus\{0\}$ to obtain $\mathbb Q$ so $\mathbb Q$ is countable because adding one element does not change the cardinality.

Is the proof good?

$\endgroup$
  • 4
    $\begingroup$ If you already know "... is countable as countable union of countable sets" then why do you need all these things? $\endgroup$ – njguliyev Aug 20 '13 at 15:17
  • $\begingroup$ Limits don't really make sense in this context. If you're taking a countable union then you should just write it as such: $\bigcup_{k \in \mathbb Z}R_k$. $\endgroup$ – Jim Aug 20 '13 at 15:25
  • $\begingroup$ @Jim They do. $\endgroup$ – Andrés E. Caicedo Aug 20 '13 at 15:39
  • $\begingroup$ Your proof is fine. Although you should note that countable union of countable sets are countable require some weak form of choice. However, if you want to remove this fact, you can (with some work) find a bijective coding of $\langle i, j, k \rangle$ by natural numbers such that $i \in \{-1, 1\}$, $j, k \in \mathbb{N}$ and find define a function $g(\langle i, j, k \rangle) = f_{i \cdot j}(k)$, where the $f$'s are the one you defined above. $\endgroup$ – William Aug 20 '13 at 16:40
  • 1
    $\begingroup$ @Jim Sure. Adding the mention of limits, etc, is completely unnecessary in this case, and distracts from the goal. $\endgroup$ – Andrés E. Caicedo Aug 20 '13 at 19:22
1
$\begingroup$

Here is a more concrete argument: given a rational $p/q$ (expressed in lowest terms), write $p$ in base 9 as $n_1\ldots n_k$ and also $q$ in base 9 as $m_1\ldots m_\ell$, and then send $p/q\in\mathbb{Q}$ to the base 10 natural number $n_1\ldots n_k 9 m_1\ldots m_\ell$. This is clearly injective and therefore the rationals are countable.

$\endgroup$

Your Answer

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