How to prove the power set of the rationals is uncountable?

Question

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?

Answer 1

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

Answer 2

@HennoBrandsma gave you a sketch of one formal proof. Here's another way: If we use the Cantor-Shreoder-Bernstien (CSB) theorem, a direct formal proof becomes easier. The CSB theorem states a bijection exists between 2 well defined nonempty sets A and B iff there exists injective functions f and g where $f: A \rightarrow B$ and $g:B \rightarrow A$.

Now let's proceed as follows: Define a map f : R → P(Q) from the reals to the power set of the rationals by sending $x\in\mathbb{R}$ to the set S= $\{q\in {\mathbb {Q}}\mid q\leq x\}$ of all rationals less than or equal to x. It can be easily proven for every real number, there is such a rational via the Archimedian property. (It's useful,although not necessary, to see that with the reals viewed as Dedekind cuts, this is nothing other than the inclusion map in the set of sets of rationals). Therefore,this map is injective since the rationals are dense in R and for each real number, the set of rationals in S is unique.

We now need an injective map from P(Q) into R. Let R = $$ \{r\in\mathbb{R}|r =\{x_n\}\}$$

where $\{x_n\}$ is the union of all the images of the Cauchy sequences in the equvilence class of rationals that define r. Then clearly $ \{x_n\}$ $\in$ P(Q)and since each real number corresponds to a unique equivalence class of rationals in the images of the convergent Cauchy sequences that correspond to r in $ \{x_n\}$ , $ \{x_n\}$ $\rightarrow$ r is an injective map from P(Q) into R and by the CSB theorem, we're done!