6
$\begingroup$

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?

  • 0
    $f : \{0, 1\}^\mathbb{N} \rightarrow \{0, 1, 2, 3\}^\mathbb{N}$ where $f(x)(n) = x(2n) + 2 x(2n + 1)$.2017-05-22

3 Answers 3

3

$(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

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

10

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.

  • 0
    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?2010-12-11
  • 2
    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.2010-12-11
8

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 $nCombinatorial meaning here something in the same spirit of the explicit bijection above.

  • 0
    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.2010-12-11