0

I am lookng at a suggested solution of the following:

For any alphabet $\Sigma$ give a $1-1$ mapping with $\mathbb{N}_0$ into $\Sigma^{\ast}$.

That's the suggested solution:

Let $\Sigma=\{0,1\}$.

Let $w \in \Sigma^{\ast}$, where $w=\alpha_0 \alpha_1 \alpha_2 \alpha_3 \dots \alpha_s, \ \ \ \alpha_i \in \{0,1\}$.

We map $w$ to $n \in \mathbb{N}_0$ such that

$$2^{s+1} \cdot 1+ 2^s \cdot \alpha_s+ 2^{s-1} \alpha_{s-1}+ \dots+ 2^{0} \alpha_0=n$$

First of all, why can we take $\Sigma=\{0,1\}$ given that we have to give a mapping for any alphabet $\Sigma$ ?

Also why does it hold that $2^{s+1} \cdot 1+ 2^s \cdot \alpha_s+ 2^{s-1} \alpha_{s-1}+ \dots+ 2^{0} \alpha_0=n$ and not $ 2^s \cdot \alpha_s+ 2^{s-1} \alpha_{s-1}+ \dots+ 2^{0} \alpha_0=n$ ?

Evinda
  • 1,460

1 Answers1

1

If we had chosen $w$ to be mapped to $n$ with $2^s \alpha_s + 2^{s-1} \cdot \alpha_{s-1} + \dots + 2^0 \alpha_0 = n$, then the empty word and the word $0$ both get mapped to $0$. The same is true for any word which consists only of $0$s.

From the way the question is formulated, it is definitely not ok to assume $\Sigma = \{0,1\}$.

However, the same proof works for $\Sigma = \{0,1, \dots, b-1\}$ where you map $w$ to the unique $n$ with $b^{s + 1} + b^s \alpha_s + \dots + b^0 \alpha_0 = n$ (Not true, but see the edit below). Note that if $\Sigma$ is any finite alphabet with $b$ elements, then by enumerating the elements of $\Sigma$ we obtain a bijection $\{0,1 , \dots, b-1\} \to \Sigma$ which also induces a bijection between the set of words with respect to these alphabets.

Note also that if we allow the alphabet $\Sigma$ to be infinite, then the statement becomes false. For $\Sigma = \mathbb{N}$ we still have a bijection between $\mathbb{N}_0$ and $\Sigma^*$ (because the latter is the countable union of the subsets of words with fixed lengths and these subsets are finite) but for $\Sigma = \mathbb{R}$ the statement is clearly false.

EDIT:

After some thought I noticed that for $\Sigma = \{0,1\}$ the map $$ \Sigma^* \to \mathbb{N}_0, w = \alpha_0\dots\alpha_s \mapsto 2^{s+1} \cdot 1+ 2^{s} \alpha_s + \dots + 2^0 \alpha_0$$ as described in the solution is not bijective as it misses the element $1 \in \mathbb{N_0}$. I wonder if there might be some sort of transcription error as replacing the $\cdot$ with a $-$ gives the map $$ \Sigma^* \to \mathbb{N}_0, w = \alpha_0\dots\alpha_s \mapsto 2^{s+1} - 1 + 2^{s} \alpha_s + \dots + 2^0 \alpha_0$$ which is a bijection of the desired form. Similarly, for $\Sigma = \{0,1, \dots b - 1\}$ the correct map is $$ \Sigma^* \to \mathbb{N}_0, w = \alpha_0\dots\alpha_s \mapsto b^{s+1} - 1 + b^{s} \alpha_s + \dots + b^0 \alpha_0.$$

Matthias Klupsch
  • 9,512
  • Why would the empty word get mapped to $0$ ? Which is the difference when we define $n=2^{s+1} \cdot 1+ 2^s \cdot \alpha_s+ 2^{s-1} \cdot \alpha_{s-1}+ \dots+ 2^0 \alpha_0=n$ ? $$$$ Also are all the finite alphabets equivalent with alphabets of the form ${0,1, \dots,b-1}$, where $b \in \mathbb{N}$ ? @MatthiasKlupsch – Evinda Aug 17 '16 at 10:15
  • @Evinda : The empty word gets mapped to the empty sum which is $0$. This is also true in the case where $w$ is mapped to $2^{s+1} + 2^s \alpha_s + 2^{s-1} \alpha_{s -1} + \dots + 2^0 \alpha_0$. In this case, however, the word consisting of $s$ zeroes is mapped to $2^{s+1}$. – Matthias Klupsch Aug 17 '16 at 10:30
  • @MatthisKlupsch Why does it have to hold that the elemet $1$ belongs to the mapping in order that the latter is $1-1$ ? – Evinda Aug 21 '16 at 16:56
  • @Evinda: You are right, this is not necessary if you want a map that is only 1-1 in the sense that it is just inective, if you want to have a one-to-one correspondence in the sense of a bijection, then you will need your map to be surjective. I was under the impression that what you really want to have is a bijection between $\mathbb{N}_0$ and $\Sigma^$, in particular because your question asked to find a 1-1 mapping "with $\mathbb{N}_0$ into $\Sigma^$" but the solution gives a 1-1 mapping from $\Sigma^*$ to $\mathbb{N}_0$. – Matthias Klupsch Aug 22 '16 at 09:33
  • A ok. In order to show that the mapping you suggested is injective, we say that for $(\alpha_0, \dots, \alpha_s) \neq (b_0, \dots,b_s)$ we have that $2^{s+1}-1+ 2^s \alpha_s+ \dots+ 2^0 \alpha_0 \neq 2^{s+1}-1+2^s b_s+ \dots+ 2^0 b_s$, right? $$$$ How can we show that the mapping is surjective? $$$$ Do we have to check if the element $1$ is in the mapping? If so, why? – Evinda Aug 23 '16 at 15:38