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}$$
Answer
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.
No comments:
Post a Comment