Let S be the set of all real numbers in the interval (0; 1) whose decimal expansions contain only 0's, 4's and 8's. Prove that S is uncountable.

Question

I just prove $$S_1=\{0.4,0.8\}$$ $$S_2=\{0.04,0.08,0.44,0.48,0.84,0.88\}$$ ... So I can calculate the number of elements in $S_n = 2 \times 3^{n-1}$

I just prove it is countably infinite.

Answer 1

First of all, $\sum_{k=0}n #{S_n}$ is not $2\cdot 3^{n-1}, it is $3^n -1$.

But that sort of summing is moot. You can show the union of all $S_n$ to be uncountable as follows:

List all the entries in some order; if the set is countable you can do that. Let's call the $k$-th number in that list $L_k$. Now consider the number $X$ formed as a decimal containing only zeros, fours and eights according to the following rules for each digit:

• If the $n$-th digit of $L_n$ is 0, then set the $n$-th digit of $X$ to 4.

• If the $n$-th digit of $L_n$ is 4, then set the $n$-th digit of $X$ to 8.

• If the $n$-th digit of $L_n$ is 8, then set the $n$-th digit of $X$ to 0.

Then $X$ cannot be in the list $\{L_k | \k \in Bbb{N} \}$ since if $X$ is in that set, then $X = L_s$ for some integer $s$, and consider the $s$-th digit of $X$, which is by construction different than the $s$-th digit of $L_s$. So we have a contradiction: If the list is complete, there is a number that is not in the list. Therefore, such a counting order cannot exist, and the set is uncountable.

Answer 2

There's a crucial subtlety here: $S\not=\bigcup S_n$. For instance, the real $$0.0404040404040404 . . .$$ is not in $S_n$ for any $n$, but is clearly in $S$.

So there's two separate questions:

• How big is $\bigcup S_n$?

• How do you show $S$ is uncountable?

You've correctly answered the first - $\bigcup S_n$ is indeed countable. Now, as to $S$, suppose I gave you a list $\{x_i: i\in\mathbb{N}\}$ of elements of $S$. Each $x_i$ has a decimal expansion $x_i=0.a_1^ia_2^i . . .$ Do you see any way I can build a new number in $S$, using the $x_i$s, which is not equal to any of the $x_i$s themselves?

Answer 3

Let $f(x)$ be the number whose ternary representation has a zero wherever $x$ has a zero, a $1$ wherever $x$ has a $4$, and a $2$ wherever $x$ has an $8$. Then $f$ defines a bijection between $S$ and $(0,1)$; hence $S$ has the same cardinality as $(0,1)$.