# Decidability of Unary Languages / One-to-One Mapping

I'm trying to prove that there exists an undecidable subset of {1}* by showing a one-to-one correspondence between it and {0, 1}* (which would imply a one-to-one correspondence between their power sets), but I'm struggling with how to do the one-to-one mapping. Isn't it just surjective? That is, there's one unary representation of potentially many binary strings (e.g., 1 = 01 = 0000000000001).

What am I misunderstanding here? Or am I just taking the wrong overall strategy?

(This isn't homework; I'm reviewing for a midterm, and it's a little concerning I'm getting tripped up here)

• Try lexicographic order. – Louis Oct 31 '16 at 9:21
• Could you explain a little more what you mean by that — putting what in lexicographic order? – user60640 Oct 31 '16 at 9:31

Instead of mapping the string $x\in\{0,1\}^*$ to $1^{\mathrm{bin}(x)}$ (where $\mathrm{bin}(x)$ is the number denoted by interpreting $x$ as a string in binary, map it to $1^{\mathrm{bin}(1x)}$. Now every string in $\{0,1\}^*$ maps to a unique number of $1$s.
The easiest approach is probably to use unary notation. The string $1^k$ can be thought of the natural number $k$; $\varepsilon$ is then $0$.
We then have that every unary language corresponds to a unique subset of $\mathbb{N}$ – and vice versa, for every subset of $\mathbb{N}$ we can find a unique language over the alphabet $\{ 1 \}$.
There are uncountably many subsets of $\mathbb{N}$, so there are uncountably many languages over the alphabet $\{ 1 \}$.
• We do not need to involve $\{ 0,1 \}^*$. Unary notation uses a singleton alphabet. The mapping $1^k \mapsto k$ is a bijection between $\mathcal{P}(\{ 1 \}^*)$ and $\mathcal{P}(\mathbb{N})$. – Hans Hüttel Oct 31 '16 at 21:08