Prove that the map $f: \{0,1\}^{\Bbb N}\to \{0,1\}^{\Bbb N}\times \{0,1\}^{\Bbb N}$ given by ($a_1,a_2,a_3,a_4...$) $\mapsto$ ($a_1,a_3,a_5...$) $\times$ ($a_2,a_4,a_6...$)is bijective, where $\{0,1\}^{\Bbb N}$ denotes the infinite product of $\{0,1\}$

I guess the map could be interpreted as the sequence $a_1,a_2,a_3,a_4...$ mapping to the pair of sequences ($a_1,a_3,a_5...$;$a_2,a_4,a_6...$ ) but how do I show this is bijective, especially the case of surjection?

  • $\begingroup$ You have two sequences $(b_n)_{n \in \mathbb{N}}$ and $(c_n)_{n \in \mathbb{N}}$ now suppose that $f((a_n)_{n\in \mathbb{N}}= ((b_n)_{n\in\mathbb{N}},(c_n)_{n\in\mathbb{N}})$ what can you conclude? $\endgroup$ – Nex Nov 8 '15 at 5:52
  • 1
    $\begingroup$ Define a function $((x_1, x_2, \ldots), (y_1, y_2, \ldots)) \mapsto (x_1, y_1, x_2, y_2, \ldots)$ in the other direction and show that they're inverses of each other. $\endgroup$ – BrianO Nov 8 '15 at 5:58


Let $\{b_k\} \times \{c_j\}$ be an element. Let {$a_i$} be such that $a_{2k+1} = b_k$ and $a_{2k} = c_k$. Then $f(\{a_i\}) = \{b_k\} \times \{c_j\}$.


Let $f(\{a_i\}) = \{b_k\} \times \{c_j\}$. And let $f(\{d_i\}) = \{b_k\} \times \{c_j\}$ Then for each $b_k = a_{2k + 1} = d_{2k + 1}$ and for each $c_j = a_{2j} = d_{2k}$ so $a_i = d_i$ for all $i$ so $\{a_i\} = \{d_i\}$.

  • $\begingroup$ Isn't this a proof of injectiveness? Since I read on other post that to prove a function is surjective, take an arbitrary element y $\in$ Y and show that there is an element x $\in$ X so that f ( x ) = y. $\endgroup$ – jio Nov 8 '15 at 17:40
  • $\begingroup$ You're right. I was going to do just one but somehow I thought the OP would.... well... $\endgroup$ – fleablood Nov 8 '15 at 18:39
  • $\begingroup$ Seriously, I was going for b x c => a but I got muddle with b x c => a,d => a =d and ... well, it was late and I got careless. $\endgroup$ – fleablood Nov 8 '15 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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