Injection from $\mathcal{P}(\{0,1\}^*)$ to $[0,1]$

Question

I'd like to find an injection $\mathcal{P}(\{0,1\}^*)\to[0,1]$.

By $\mathcal{P}(\{0,1\}^*)$ I mean the powerset of the set of finite sequences over the numbers $0$ and $1$ and by $[0,1]$ I mean the interval of real numbers.

In theoretical computer science $\mathcal{P}(\{0,1\}^*)$ is also known as the set of languages over the alphabet $\{0,1\}$. Proving this injection is one part of proving that $|\mathcal{P}(\{0,1\}^*)|=|[0,1]|$.

Here's what I have done so far:

I build an infinite table $[a_{ij}]_{i,j=1,\ldots,\infty}$. The column labels of the table are the elements of $\{0,1\}^*$ (words) in their canonical order and the row labels are specific subsets (languages) in $\mathcal{P}(\{0,1\}^*)$.

Note: I'm not sure if I'm allowed to use the elements of $\mathcal{P}(\{0,1\}^*)$ as row labels, since I know that they are not enumerable - I'm not sure if this is a problem or not. Assuming not, lets continue:

Now for every row $i$ (language), we let $a_{ij}=1$ if the $j$-th word $w_j\in \{0,1\}^*$ (in canonical order) is in that set (language) and $a_{ij}=0$ otherwise.

So every row is just an infinite bit-string indicating which words are in the language. And we know that for different languages the bit-string will be different. Then for every language we take that bit string $s$ (row) and map it as follows:

$s\mapsto Number(0.s)\in[0,1]$, where $0.s$ is the binary representation of a real number.

The problem with this solution is that it's not an injection. For example the languages specified by the infinite bit-strings $1\overline{0}=10000000000\ldots$ and $0\overline{1}=011111111111111\ldots$ are clearly different, but they will map to the same real number $\frac{1}{2}$, since in binary $0.1\overline{0} = 0.0\overline{1}$.

Is there a solution to fix this? Or do you have another idea for the construction of an injection?

Answer 1

Very simply, instead of using the binary expansion, use the ternary expansion (or the decimal expansion if you want, or really anything but the binary expansion). Then $0.111... = 0.2$ is not the image of any other sequence (because you only use 0's and 1's), and the function you have built becomes an injection.

Answer 2

Hint If you want to fix your solution, you can show that the set $$\{ (x,y) \in \mathcal{P}(\{0,1\}^*) \times \mathcal{P}(\{0,1\}^*) | x \neq y, f(x) =f(x) \}$$ is countable.

To do this, show that whenever $f(x)=f(y)$ and $x \neq y$ one of $x$ or $y$ has a finite binary expansion. Show that the words of lenght $n$ are countable, thus this is a countable union of countable sets.

Then, if you denote this set as $\{ (x_n,y_n)\}$ and you have $f(x_n)=f(y_n)=z_n$ you can redefine $$ f(x_n)=z_{2n} \\ f(y_n)=z_{2n+1} $$

This function actually becomes a bijection.