Let $S$ be the set of all real numbers in $(0, 1)$ having a decimal representation which only uses the digits $0$ and $1$. So for example, the number $1/9$ is in $S$ because $1/9 = 0.1111\ldots$, the number $1/100$ is in $S$ because we could write $1/100 = 0.010000\ldots$, but $1/2$ is not in $S$ because $1/2 = 0.5$ which contains the digit $5$ (or $1/2 = 0.49999\ldots$ which contains $4$ and $9$).
(a) Prove that $S$ is uncountable. [Hint: use a proof similar to the proof of Theorem 10.8.]
(b)Let $T =\{1,2\}^{\mathbb{N}}$ be the set of all functions $f :\mathbb{N}\to\{1,2\}$,where $\mathbb{N}$ is the set of all positive integers. Find a bijection between the sets $S$ and $T$, and thus conclude that $T$ is uncountable.
(c) Prove that the set $\mathbb{N}^{\{1,2\}}$ of all functions $f : \{1, 2\} → \mathbb{N}$ is denumerable.
We solved question (a) and know $S$ is uncountable, we are looking to do (b) and if anyone wants to give a hint for (c) that would be great.
I'm having trouble with notation, but we think:
$$T=\{\{(i,a_{i}+1):i \in \mathbb{N}\}: n\text{ corresponds to some real number }c \in S\}$$
$g: S \rightarrow T = \{(c_{m},\{(i,a_{i}+1):i \in \mathbb{N}\}\}$, where $c_{m}$ is an arbitrary element of $S$.
Then we tried to show $g$ is one-to-one and onto and didn't make much progress.
Alternatively, we thought of defining:
$$g = \{(c,f(i))\},$$ where $c \in S$ and $$f(i) = \begin{cases}2\text{ if }a_{i}=0\\ 1\text{ if }a_{i}=1\end{cases}$$
Best Answer
Hint for (c): There is a nice one-to-one correspondence between the functions from $\{1,2\}$ to $\mathbb{N}$ and the set of ordered pairs $(a,b)$ where $a$ and $b$ roam over $\mathbb{N}$. We can now find a pleasant injective mapping from the ordered pairs $(a,b)$ to $\mathbb{N}$ by for example mapping the ordered pair $(a,b)$ to $2^a3^b$. There is even a simple bijective mapping, but (depending on the tools you have) an injective mapping may let you finish things.
Added for (c): We give some details if we choose to map the ordered pair $(a,b)$ to $2^a3^b$. The details are simpler if we use the bijection described in the link.
Let $F$ be the set of all functions from $\{1,2\}$ to $\mathbb{N}$. For any such function $f$, let $\phi(f)=(f(1),f(2))$. Then $\phi$ is a bijection from $F$ to the set of ordered pairs $(a,b)$, where $a$ and $b$ range over $\mathbb{N}$.
Look at the collection $K$ of numbers of the form $2^a3^b$, where $a$ and $b$ range over $\mathbb{N}$. There is an immediate bijection $\psi$ from the ordered pairs $(a,b)$ to $K$. List the numbers in $K$ in their natural order. Let the list be $k_1, k_2, k_3, \dots$. Note for example that $k_1=2^13^1=6$; $k_2=2^23^1=12$; $k_3=2^13^2=18$. The listing gives a bijection $\chi$ from $K$ to $\mathbb{N}$. For example, $\chi(6)=1$, $\chi(12)=2$, $\chi(18)=3$. So now we have $3$ bijections, (1) $\phi$, from $F$ to ordered pairs; (2) $\psi$, from ordered pairs to $K$; and (3) $\chi$, from $K$ to $\mathbb{N}$. Put them together: the function $\chi(\psi(\phi))$ is a bijection from $F$ to $\mathbb{N}$. We conclude that $F$ is denumerable.
For (b), there is a natural thing to try. Take a function $f$ from $\mathbb{N}$ to $\{1,2\}$. Look at the number whose $n$-th digit after the decimal point is $f(n)-1$. There is a problem, however, in that there is no number for the function which is identically $1$ to go to, since our set of numbers is $(0,1)$, and therefore excludes the number $0.000\dots.$. So we need to fix things, and the fix is slightly tricky.
Let $A$ be the set of all numbers in the interval $[0,1)$ whose decimal expansion has only $0$'s and/or $1$'s. Let $B$ be the set of such numbers in $(0,1)$. We exhibit a bijection from $A$ to $B$. Map $0$ to $1/10$, $1/10$ to $1/100$, $1/100$ to $1/1000$, and so on. For any other number $x$ in $A$, map $x$ to $x$. This gives a bijection from $A$ to $B$. It is a quite standard trick, related to Hilbert's infinite hotel. If the hotel is full, and a new guest comes, you put the person in Room $1$ into Room $2$, the person in Room $2$ into Room $3$, and so on forever. Now Room $1$ is free for the new guest. In our case, the number $0$ was the new guest.