Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
Related question: 61926. See the answers of William and leo, as well as my answer. –  Srivatsan Sep 20 '11 at 4:22
    
@Srivatsan: The other question isn't really a duplicate of this one though. It may be worth reposting your answer here. –  Zhen Lin Sep 20 '11 at 6:43

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
Thanks! I wish I could accepted more than one answers. –  Tim Sep 20 '11 at 22:30

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

share|improve this answer
2  
This matches the finite length strings, not the countably infinite length strings. This changes the answer. –  Ross Millikan Oct 23 '12 at 14:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.