3
$\begingroup$

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)

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

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The question already talks about unary notation, which the asker already tried to use. They had a problem, which is exactly what they're asking about, which your answer doesn't address. $\endgroup$ – David Richerby Oct 31 '16 at 21:02
  • 1
    $\begingroup$ 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})$. $\endgroup$ – Hans Hüttel Oct 31 '16 at 21:08
  • $\begingroup$ Oh, you're saying "Don't prove it via $\{0,1\}^*; prove it this other way, instead." Fair enough. $\endgroup$ – David Richerby Oct 31 '16 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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