patternMinor
Decidability of Unary Languages / One-to-One Mapping
Viewed 0 times
languagesunaryonedecidabilitymapping
Problem
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)
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)
Solution
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.
Context
StackExchange Computer Science Q#65330, answer score: 5
Revisions (0)
No revisions yet.