How do you map $\{0,1\}^* \times \{0,1\}^$ to $\{0,1\}^$ with a 1-1 function?

Question

I know how to map $\{0,1\}^*$ to integers but I can not figure this one out.

@Nichlos The question's body and title's body are not supposed to be used as one. Please write up the question completly on the question's body. — Git Gud, Aug 28 '13 at 15:49
http://en.wikipedia.org/wiki/Kleene_star all possible strings using 0 and 1 — Nichlos, Aug 28 '13 at 15:50
Is this your question too: http://math.stackexchange.com/questions/476677/find-1-1-and-onto-mapping-from-0-1-to-the-integers/476720#476720? If yes, you can flag for moderators' attention and merge your two accounts. — M Turgeon, Aug 29 '13 at 18:51

score 2 · Answer 1 · edited Aug 29 '13 at 13:58

2

One easy way is, starting with binary words $u,v$, to interpret $2u2v$ as a ternary number representing $~n\in\Bbb N$, and map it to the binary representation of$~n$ (without leading digit $0$).

edited Aug 29 '13 at 13:58

Did

279,727

answered Aug 29 '13 at 13:12

Marc van Leeuwen

115,048

user87690 · Answer 2 · 2013-08-28T15:57:50.307

1

Since $\{0, 1\}^*$ is countably infinite and product of countably infinite sets is countably infinite, the claim follows. You can get the function explicitly by composing bijection between $\{0, 1\}^*$ and $\mathbb{N}$ with bijection between $\mathbb{N}$ and $\mathbb{N} × \mathbb{N}$. There are standard candidates for those bijections. Ask if you need more explanation.

edited Aug 28 '13 at 15:57

answered Aug 28 '13 at 15:52

user87690

9,133

1

but how would I describe such a function? – Nichlos Aug 28 '13 at 15:53
@Nichlos: You said you knew how to map ${0, 1}^*\to\Bbb N$; is your problem that you don't know how to do that bijectively (which is what this method requires)? Or is your difficulty with an explicit bijection $\Bbb N\times\Bbb N\to\Bbb N$ (actually injection would suffice here)? – Marc van Leeuwen Aug 29 '13 at 13:17
For a bijection ${0, 1}^*\to\Bbb N$, prefix a digit $1$ to you string, interpret as a binary number, and subtract$~1$. – Marc van Leeuwen Aug 29 '13 at 13:19

score 1 · Answer 3 · answered Aug 28 '13 at 15:55

1

You have a bijection $$f:\{0,1\}^*\to \mathbb Z.$$ Therefore, you can consider the composition $$\{0,1\}^*\times\{0,1\}^*\to\mathbb Z\times\mathbb Z\to\mathbb Z\to \{0,1\}^*,$$ where the first map is the product $f\times f$, the last map is $f^{-1}$, and the middle map is any bijection $\mathbb Z\times\mathbb Z\to\mathbb Z$.

answered Aug 28 '13 at 15:55

M Turgeon

10,419

I think $\Bbb Z$ should probably better be $\Bbb N$ througout, but of course it doesn't really matter (as the two are in bijction). – Marc van Leeuwen Aug 29 '13 at 13:09
@MarcvanLeeuwen I used $\mathbb Z$ because the OP mentioned he already had the map $f$ (whatever it is), but you're right, it could just as well have been $\mathbb N$ – M Turgeon Aug 29 '13 at 18:48

score 1 · Answer 4 · answered Aug 28 '13 at 16:13

1

Given $w \in \{ 0, 1\}^*$, define $w_0$ as the string obtained from $w$ by adding a $0$ after each symbol in $w$. Similarly define $w_1$.

Then $(u, v) \mapsto u_0v_1$ is an injection.

answered Aug 28 '13 at 16:13

1

Shorter but less symmetric is $(u,v)\mapsto u_011v$. – Andreas Blass Aug 28 '13 at 17:47

score 0 · Answer 5 · answered Oct 10 '13 at 12:18

It should be the same with the proof of the theore "rational numbers are countable". If you're able to map your set to the integers 1-1, then you should be able to prove its Cartesian product with itself can be mapped on itself just like the mapping between rational numbers and natural numbers.

Here is the proof of the countability of the rational numbers:

http://www.proofwiki.org/wiki/Rational_Numbers_are_Countably_Infinite

How do you map $\{0,1\}^* \times \{0,1\}^*$ to $\{0,1\}^*$ with a 1-1 function?

5 Answers5

How do you map $\{0,1\}^* \times \{0,1\}^$ to $\{0,1\}^$ with a 1-1 function?