Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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
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. –  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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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