# $\left \{ 0,1 \right \}^{\mathbb{N}}\sim \left \{ 0,1,2,3 \right \}^{\mathbb{N}}$ bijection function

Prove that $\left \{ 0,1 \right \}^{\mathbb{N}}\sim \left \{ 0,1,2,3 \right \}^{\mathbb{N}}$ and find a direct bijection function.

I got the first part by showing that $\left \{ 0,1 \right \}^{\mathbb{N}} \subseteq \left \{ 0,1,2,3 \right \}^{\mathbb{N}} \subseteq {\mathbb{N}}^{\mathbb{N}}$, which implies that $|\left \{ 0,1 \right \}^{\mathbb{N}}| \leq |\left \{ 0,1,2,3 \right \}^{\mathbb{N}}| \leq |{\mathbb{N}}^{\mathbb{N}}|$ and since $|{\mathbb{N}}^{\mathbb{N}}| = |\left \{ 0,1 \right \}^{\mathbb{N}} | = 2^{\aleph_0}$ and Cantor-Bernstein you get that $\left \{ 0,1 \right \}^{\mathbb{N}}\sim \left \{ 0,1,2,3 \right \}^{\mathbb{N}}$.

But I'm stuck with formulating a bijection function. More generally, what approach do you use when you need a formulate an exact function?

-

There are at least two ways to proceed: Either you start as you did, and then you follow the argument of Cantor-Bernstein, which explicitly gives you how to build a bijection from the two given injections.

The other way is to directly argue in the case at hand. For example, identify the sequence $(a_0,a_1,a_2,a_3,...)$ in $\{0,1\}^{\mathbb N}$ with the sequence $(b_0,b_1,b_2,\dots)$ in $\{0,1,2,3\}^{\mathbb N}$ as follows: Replace $a_{2n},a_{2n+1}$ with $b_n$, where $0,0$ is replaced with $0$; $0,1$ is replaced with $1$; $1,0$ with $2$; and $1,1$ with $3$.

[Edit: I see Jonas wrote the same explicit bijection as I was typing this.]

As a slightly more challenging exercise, pick any two positive integers $n<m$, and build a "combinatorial" bijection between $\{0,1,\dots,n\}^{\mathbb N}$ and $\{0,1,\dots,m\}^{\mathbb N}$. Combinatorial meaning here something in the same spirit of the explicit bijection above.

-
So I actually define a mapping function between (0,0), (0,1), (1,0) and (1,1) to {0,1,2,3} and use it to define the function. Now, since the mapping function has an inverse function, so I can say it is a bijection function. Thanks. – Ma.H Dec 11 '10 at 23:20

Think in terms of how you convert between binary and base 4 representations of numbers. Break up a sequence of 0s and 1s into pairs, and to each pair (for which there are the 4 possibilities) assign one of 0, 1, 2, or 3.

-
I actually tried it, but I got to the conclusion that the function is not well-defined. How did you get the function is well-defined? – Ma.H Dec 11 '10 at 23:05
A function is well-defined if you can unambiguously write down where it sends each element of the domain. If you are given a sequence that starts say with 1001101010111000...., then the pairs will be 10,01,10,10,10,11,10,00.... As long as you stick with your rule for where each type of 0-1 pair gets sent, there is only one place to send the sequence to a sequence of 0s,1s,2s, and 3s, and therefore the function will be well defined. You should also convince yourself that it is bijective. – Jonas Meyer Dec 11 '10 at 23:07

$(b_1,b_2,b_3,b_4,\ldots)\mapsto(b_1+3^{b_2}-1,b_3+3^{b_4}-1,\ldots)$ answers the question.

@Andres: "As a slightly more challenging exercise, pick any two positive integers $n<m$, and build a "combinatorial" bijection between $\{0,1,…,n\}^{\mathbb N}$ and $\{0,1,…,m\}^{\mathbb N}$. Combinatorial meaning here something in the same spirit of the explicit bijection above."

Answer(partial). Assume that there exists two integers $p,q$ such that $l=(n+1)^p=(m+1)^q$. The bijection comes from a simple remark : there is a natural bijection between the words of length $p$ on the alphabet $\{0,1,…,n\}$ and the words of length $q$ on $\{0,1,…,m\}$. (one can think of two trees with the same leaves (with cardinalty $l$) to see this, look here). This yields an explicit bijection in the case $(n+1)^p=(m+1)^q$.

-