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)

Improve this question
$\endgroup$
2
  • $\begingroup$ Try lexicographic order. $\endgroup$
    – Louis
    Commented Oct 31, 2016 at 9:21
  • $\begingroup$ Could you explain a little more what you mean by that — putting what in lexicographic order? $\endgroup$
    – user60640
    Commented Oct 31, 2016 at 9:31

2 Answers 2

Reset to default
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.

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Oct 31, 2016 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
    Commented Oct 31, 2016 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
    Commented Oct 31, 2016 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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