# What is the problem with my “proof” that $\mathbb R$ is countable?

The problem I wanted to answer is

Determine whether or not the set of irrationals, $\mathbb R \backslash \mathbb Q$, is countable.

My attempt. For nicer notation, let $\mathcal I := \mathbb R \backslash \mathbb Q$.

Definition. An irrational number is a real number that can be expressed as an infinite simple continued fraction.

An infinite simple continued fraction is an expression of the form $$b_0+\frac{1}{b_1+\frac{1}{b_2+\frac{1}{b_3+\frac{1}{...}}}}$$ Hence a positive irrational number $\beta$ is uniquely determined by the $b_0, b_1, b_2, \ldots$. For each of these unique determinations of irrational numbers, we will construct a sequence $$s=[b_0, b_1, b_2, \ldots]$$

But a sequence is just a subset of $\mathbb{N} \times \mathbb Z$; for each $n \in \mathbb N$, take the point $(n,b_n)$ as the $n$th element of the sequence. And $\mathbb{N} \times \mathbb Z$ is countable, so the set of all such sequences is countable, so the set of all simple infinite fractions is countable, so the set of all irrationals is countable.

But since $\mathbb Q$ is countable as well, doesn't that mean that the union of $\mathbb R \backslash \mathbb Q$ and $\mathbb Q$, i.e. $\mathbb R$ is countable?

• A subset of $\mathbb{N}\times\mathbb{Z}$ is very different from an element of $\mathbb{N}\times\mathbb{Z}$... – Eric Wofsey Sep 20 '18 at 6:07
• @TiwaAina Your proposed argument is essentially the same as that "since every real has a decimal representation, then reals would be countable". – dxiv Sep 20 '18 at 6:11
• A countable set can have uncountably many different subsets. That's the crux of the problem. You could just as well say "Every real number is the limit of a sequence of rational numbers, these are countable, therefore $\Bbb R$ is countable", and the problem is the same: a countable set can have uncountably many sequences with different limits. – Asaf Karagila Sep 20 '18 at 6:21
• That's Cantor's theorem. $|X|<|\mathcal P(X)|$. If $X$ is countably infinite, then it has uncountably many subsets. – Asaf Karagila Sep 20 '18 at 6:26
• "Can a subset of a countable set be uncountable?" each subset (and each sequence) is countable. But the number of subsets (and the number of sequences) are not. Just because you have a countable number of ingredients, doesn't mean you are limited to only being able to make a countable number of combinations. Just like having 27 ingredients doesn't mean you are limited to 27 combinations. (Computer programming would be boring if their were only two possible programs that could be written!) – fleablood Sep 20 '18 at 15:59

But a sequence is just a subset of $\mathbb{N} \times \mathbb{Z}$; ... And $\mathbb{N} \times \mathbb{Z}$ is countable, so the set of all such sequences is countable.

By analogy, the power set of $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$ is all the subsets of $\mathbb{N}$. $\mathbb{N}$ is countable. Nevertheless, $\mathcal{P}(\mathbb{N})$ has strictly greater cardinality than $\mathbb{N}$ as the power set of any set is strictly greater than the cardinality of the original set.

Let for irrational $a$ define $s_a$ be the unique sequence that construct $a$. Then $\bigcup_{x\in\Bbb R\setminus \Bbb Q} \{s_x\}$ will be all the subsets of $\Bbb N\times \Bbb Z$ that have infinitely many non zero elements. That is subset of $\mathcal P(\Bbb N\times\Bbb Z)$.

What you defined is a single element $s$, and it is true that every irrational number can be represented by countable number of rationals/integers.

The error in your argument is in the step-

And N×ZN×Z is countable, so the set of all such sequences is countable

which basically assumes that-

"The set of all subsets of a countable set is automatically countable"

or,

"The power set of a countable set is automatically countable".

In the above, I have used 'is automatically' to colloquially mean "is always (by implication)".

In the above, your assumption was a logical fallacy, probably due to a subconscious analogy with the statement- "The power set of all finite sets is finite".

However, the assumption is false.

One way of seeing this is by noting that there are correct proofs (such as Cantor's famous diagonal argument) which prove that $\mathbb{R}$ is uncountable and therefore by reductio ad absurdum your assumption is false.

Of course, since this is based upon the incorrectness of the statement your argument attempts to prove, seeing this this way may not be very convincing.

A more direct ( and thus convincing ) argument may be to present a counter-example to your assumption. However, you can make the first way just as direct and thus just as convincing by noting that since the irrationals are indeed the power set of $\mathbb{N×Z}$, and can be proved to be uncountable by other methods, the reductio ad absurdum we used earlier is actually also a direct counter-example to your assumption.

As a side note, a more intuitive ( through non-rigorous ) way of picturing this may be to recall that for a set having $n$ elements, it's power set had $2^n$ elements. We can view this exponential relationship ad representing an 'order-of-magnitude plus' paradigm shift, and thus expect the power set of a countable yet infinite set to be uncountable.