Is the set of all strings with countably infinite length bijective to $[0,1]$?

Question

I heard that the set of all strings with countably infinite length in two-element alphabet (such as $ \{ a,b \} $ ) is bijective to $[0,1]$. I wonder why? What is the general conclusion? Thanks!

Answer 1

Without loss of generality, $\{a,b\}=\{0,1\}$. Now we have that an infinite binary string is a function $f\colon\mathbb N\to\{0,1\}$. We will denote this class of functions by $N$ for now.

Define the following injections:

1. For $f\in N$ define the real number: $$r_f = 2\cdot\sum_{n=0}^{\infty}\frac{f(n)}{3^{n+1}}$$ This is the Cantor set, if you happen to know it. The mapping $f\mapsto r_f$ while not surjective is indeed injective.

2. Fix an enumeration of $\mathbb Q$, that is $\{q_i\mid i\in\mathbb N\}$. Now map $r\in[0,1]$ to a set of natural numbers: $$L_r = \{n\in\mathbb N\mid q_n<r\}$$ This is a Dedekind cut, and of course this is an injective map. If $r\neq t$ then there is some rational number between them, thus $L_r\neq L_t$.

3. Lastly, we define a bijection between $N$ and $\mathcal P(\mathbb N)$ as follows: $$A_f = \{n\in\mathbb N\mid f(n)=1\}$$ This is indeed injective, since if $f\neq g$ there is some $n$ such that $f(n)\neq g(n)$. If $f(n)=1$ then $n\in A_f, n\notin A_g$ and vice versa if $g(n)=1$.
   To see that this is a bijection, consider $A\subseteq\mathbb N$, we define $$f_A(n) = \begin{cases}1 & n\in A\\ 0 & n\notin A\end{cases}$$ Now we have that $A_{f_A} = A$, as wanted.

Now consider the ordering $A \preceq B$ as "There is an injection from $A$ into $B$", we have:

$$\mathcal P(\mathbb N)\preceq N\preceq [0,1]\preceq\mathcal P(\mathbb N)$$

By Cantor-Bernstein we can now define a bijection between any of two sets mentioned here. The conclusion is nothing new in mathematics. The real numbers are bijectible with the power set of any countable set, and thus they form an uncountable set.

Answer 2

Let $B:=\{0,1\}^{\mathbb N}$ with ${\mathbb N}=\{1,2,\ldots\}$. A more or less explicit bijection $f:\>B\to[0,1]$ can be obtained as follows: The preliminary function $$g(x):=\sum_{k=1}^\infty x_k\>2^{-k}$$ interprets a string $x\in B$ as infinite binary fraction $0.x_1 x_2 x_3 \ldots\ $. The function $g$ maps $B$ almost bijectively onto $[0,1]$, but unfortunately the dyadic rationals in $\>]0,1[\>$ have two preimages, e.g., $g(1,0,0,0,\ldots)=g(0,1,1,1,\ldots)={1\over2}$. In order to fix this we let $$(q_n)_{n\geq1}:=\Bigl({1\over2},{1\over4},{3\over4},{1\over8},{3\over8},{5\over8},{7\over8},{1\over16},\ldots\Bigr)$$ be an enumeration of these dyadic rationals and define definitively $$f(x):=\cases{q_{2n-1} & \hbox{if $g(x)=q_n\>$, and $x_k=0$ for almost all $k$,} \cr q_{2n} & \hbox{if $g(x)=q_n\>$, and $x_k=1$ for almost all $k$,} \cr g(x) & \hbox{otherwise.} \cr}$$

Answer 3

$\Sigma^*$ is countably infinite. Recall,

\begin{equation} \Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n \end{equation}

for every value $n \in \mathbb{N}$, the set $\Sigma^n$ is countable, therefore, $\Sigma^*$ is a countable union of countable sets, thus it is countable.

Proof:

We must provide a bijection, a mapping of every element in $\Sigma^*$ to a unique element in $\mathbb{N}$, that is, a function which is one-to-one and onto.

Let $\Sigma = \{0, 1\}$ and $f:\Sigma^* \rightarrow \mathbb{N}$ be our bijection.

Now we start by writing down all the strings in $\Sigma^*$ in increasing order. First all strings of length $0$, then all strings of length $1$, all strings of length $2$, all strings of length $3$, so and and so forth.

\begin{equation} \Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 110, 101, 111, ...\}\\ \mathbb{N} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ... \} \end{equation}

Upon inspection of the above, we clearly have a bijection $f:\Sigma^* \rightarrow \mathbb{N}$, that is a function that maps every element of our alphabet to a unique element of the natural numbers. Therefore, $\Sigma^*$ is countably infinite. $\square$