[Math] How to prove the power set of the rationals is uncountable

elementary-set-theoryproof-verificationproof-writingrational numbersreal numbers

Recently a professor of mine remarked that the rational numbers make an "incomplete" field, because not every subsequence of rational numbers tends to another rational number – the easiest example being
$$\lim_{N\to \infty} \sum_{n=1}^N {1 \over n^2} = { \pi ^2 \over 6}$$
He then said that the "completion" of the rational numbers is, then, the real numbers $\Bbb{R}$.

This led me to think that every real number could be identified with an infinite sequence of rational numbers. And clearly this must be so – the rationals are dense in the reals, so given any arbitrary real number $r$ and rational number $a_0$, there always exists another rational number $a_1$ between $a_0$ and $r$. Infinitely repeated iterations of this process would produce a sequence of rationals $a_n$ which tends to $r$.
This implies then that the set of all possible subsequences of rational numbers (necessarily, the power set of the rationals) must be at least as large as $\Bbb{R}$, thus uncountable.

Is this proof valid, or rigorous enough? Or one that is commonly used to show uncountability?

Best Answer

The idea is indeed correct, but needs a little work to formalise. You note that for every real $r$ there is a sequence $(a_n(r))_n$ of points that are all distinct and say (strictlty) increasing, so that $a(r)_n \rightarrow r$ as $n \rightarrow \infty$. You could choose the finite decimal approximations of $r$ (when we write $r$ as an infinite decimal expansion, which we can always do), if you want to be concrete.

Then the sets $A(r) = \{a_n(r): n \in \mathbb{N} \}$ would be almost disjoint for every pair of distinct $r_1 \neq r_2$; their intersection can be at most finite, or we would have a common subsequence tending to 2 limits, which cannot be. In particilar $r \rightarrow A(r)$ is an injection of $\mathbb{R}$ into $\mathscr{P}(\mathbb{Q})$.

Related Question