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. 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.
 A: 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)$.
A: 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?
A: 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.
