# Bijective Function between Uncountable Set of Real numbers and a set of all functions

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

-
I've added LaTeX formatting to your question. Apologies if I changed your intended meaning in any way. – Zev Chonoles Nov 22 '11 at 4:01
In general, if you want to refer to a function $f:X\to Y$, I would highly recommend not using the subset of $X\times Y$ consisting of elements of the form $(x,f(x))$. That might be the definition of "function", but it's not going to help you get an intuitive handle on what's going on for this problem. – Zev Chonoles Nov 22 '11 at 4:05
Also, in your definition of $T$, you never specified what it would mean for a function to correspond to $c\in S$, so there would be no way to prove anything about it. – Zev Chonoles Nov 22 '11 at 4:08
What is theorem 10.8? – Tyler Nov 22 '11 at 5:01
Why the vote to close? – Asaf Karagila Nov 22 '11 at 7:06

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.

-
For (b), what function could we use from $\mathbb{N}$ to ${1,2}$? The only thing I can think of is $f(i)= \begin{cases}1\text{ if }a_{i}=0\\ 2\text{ if }a_{i}=1\end{cases}$. I'm not sure how looking at the number whose n-th digit after the decimal point is $f(n)-1$ helps... – Samuel Reid Nov 22 '11 at 5:36
It gives you a one-to-one correspondence between the functions from $\mathbb{N}$ to $\{1,2\}$ and the numbers in the interval $[0,1)$ whose decimal expansion has only $0$'s and/or $1$'s. Note the unfortunate square bracket in $[0,1)$. But observe that there is a one-to one correspondence between the numbers of the right shape in $[0,1)$ and those in $(0,1)$. Send $0$ to $1/10$, $1/10$ to $1/100$, and so on. For any $x$ in $[0,1)$ (which uses $1$'s and or $0$'s), except $0$, $1/10$, $1/100$, and so on, send $x$ to $x$. I can add the details to my answer tomorrow if you still have trouble. – André Nicolas Nov 22 '11 at 6:26

Hints: For b, the usual solution involves writing numbers in binary notation. For c, notice that there is a simple bijection to ordered pairs of natural numbers.

-
I'm trying to think of a simple bijection to ordered pairs of natural numbers, good thing I have noticed that already. I have only been able to come up with non-function that sends {1,2} to $\mathbb{N}$. For example, if we say $$f(x): \{1,2\} \rightarrow \mathbb{N} = \begin{cases}2k+1\text{ if } x=1\\ 2l\text{ if }x=2\end{cases}$$ for $k,l \in \mathbb{Z}$. Would this work? – Samuel Reid Nov 22 '11 at 5:38
It doesn't work. I gave a link in my answer to a polynomial that works. Or else you can use my $2^a3^b$ idea. There is a simple bijection from the numbers of this shape to $\mathbb{N}$. List the numbers of this shape in the usual order. Call them $a_1$, $a_2$, $a_3$, and so on. Note that $a_1=6$, $a_2=12$, $a_3=18$, $a_4=24$. No nice formula for $a_n$, but definitely bijection. – André Nicolas Nov 22 '11 at 6:32

Thank you everyone for the feedback and suggestions. Andre, your suggestions for question 2(b) were very helpful, but not so much for 2(c) and we did something completely different.

Our solutions for 2(b) and 2(c) were:

2(b) Prove that: $T=\{1,2\}^{\mathbb{N}}$ is uncountable.

For $c \in S$, we know $c=0.a_{1}a_{2}a_{3}...$, where for the digit $a_{i}$ of $c$, $i \in \mathbb{N}$. Then for $T =\{1,2\}^{\mathbb{N}}$, we map $c$ to a subset $\mathbb{B}=T-\{(1,1),(2,1),(3,1),...\}$, of $T$ to ensure that $0.000...$, does not have an image in $\mathbb{B}$, since $0.000... \notin S$. Define the elements $f \in \mathbb{B}$ as, $f=\{(i,b_{i})|i \in \mathbb{N}, b_{i} \in \{1,2\}\}$, where $b_{i}=a_{i}+1$. By Result 2, we know $S$ is uncountable, so if we can show that there exists a bijective function $g:S \rightarrow \mathbb{B}$, then $\mathbb{B}$ must be uncountable. We now show this for $g=\{(c,f)|c \in S, f \in \mathbb{B}\}$, and since $B \subseteq T$, then by Theorem 10.9, $T$ would be uncountable. For $g$ to be onto we take an arbitrary element $f \in \mathbb{B}$, where $f=\{(1,b_{1}),(2,b_{2}),(3,b_{3}),...\}$, which can also be written as $\{b_{1},b_{2},b_{3},...\}$ or $f=\{b_{i}\}_{i=1}^{\infty}$, where $b_{i} \in \{1,2\}$. Then, for $c=0.a_{1}a_{2}a_{3}...$, the $i^{th}$ digit $a_{i}$ is given by $a_{i}=b_{i}-1$. So, $c=0.b_{1}-1\text{ }b_{2}-1\text{ }b_{3}-1...$, therefore, since all $c \in S$ have unique decimal representations, for any arbitrary $f \in \mathbb{B}$, there exists a $c \in S$, $g:S \rightarrow \mathbb{B}$ is onto. For $g$ to be one-to-one, we assume for $c_{1},c_{2} \in S$, that $g(c_{1})=g(c_{2})$, where $c_{1}=0.x_{1}x_{2}x_{3}...$, and $c_{2}=0.y_{1}y_{2}y_{3}...$, with $x_{i},y_{i} \in \{0,1\}$. So, $g(0.x_{1}x_{2}x_{3}...)=g(0.y_{1}y_{2}y_{3}...)$, then, $\{x_{1}+1,x_{2}+1,x_{3}+1,...\}=\{y_{1}+1,y_{2}+1,y_{3}+1,...\}$. Since for every digit $x_{i}$ of $c_{1}$ and every digit $y_{2}$ of $c_{2}$, $x_{i}+1=y_{i}+1$, then $x_{i}=y_{i}$. So, any arbitrary digit of $c$, is equal to any arbitrary digit of $c_{2}$, and all $c \in S$ have unique decimal representations, so $c_{1}=c_{2}$. Thus, $g$ is one-to-one. So, since $g: S \rightarrow \mathbb{B}$ is one-to-one and onto it is bijective and so $|S|=|\mathbb{B}|$. Since $\mathbb{B} \subseteq T$, and $\mathbb{B}$ is uncountable, by Theorem 10.9, $T$ is uncountable.

2(c) There is a table and figure included in our proof, but I'll list out some of what we had:

Let $f$ be an arbitrary function $f \in \mathbb{N}^{\{1,2\}}$ so that $f$ is of the form $f=\{(1,a),(2,b)|a,b \in \mathbb{N}\}$. We list the entries for $a$ and $b$ as their own ordered pair in the following table: If we traverse this table as shown, we hit the ordered pair that gives the values for $a$ and $b$ for every possible function $f=\{(1,a),(2,b)\}$. So, the set of all functions $f:\{1,2\} \rightarrow \mathbb{N}$ can be listed in a sequence as: $$\mathbb{N}^{\{1,2\}} = \{\{(1,1),(2,1)\},\{(1,1),(2,2)\},\{(1,2),(2,1)\}, \{(1,1),(2,3)\},\{(1,2),(2,2)\},\{(1,3),(2,1)\},\{(1,1),(2,4)\},...\}$$ Therefore, $\mathbb{N}^{\{1,2\}}$ is denumerable.

-