# Bijection between SxS and S where S is an infinite string of 1's and 0's

Denote $S = \{(a_1, a_2, a_3, \dots)| a_i \text{is 0 or 1}\}$.

So I know if I think of one S as $\{(a_1,a_2,a_3,\dots)\}$ and another S as $\{(b_1,b_2,b_3,\dots)\}$, I can create a function that spits out something like $\{(a_1,b_1, a_2,b_2, a_3, b_3, \dots)\}$. I've seen this sort of thing before when showing that (0,1)x(0,1) bijects to (0,1), but I'm having trouble proving that such a function is injective and surjective. Thanks.

• As a follow up, I've defined a piecewise function f(Sa,Sb)={(c1,c2,c3,...) if n even,cn=b(n/2) and if n odd, cn=a((n+1)/2)) Commented Mar 14, 2017 at 3:31
• In your question is $S \times S$ the cross product of the two strings or a zipper of both strings? Commented Mar 14, 2017 at 3:32
• Its the cross product Commented Mar 14, 2017 at 3:38
• Then that doesn't work, clearly!
– Pedro
Commented Mar 14, 2017 at 3:43
• Thinking about this, I wonder: Is S a subset of SxS? Commented Mar 14, 2017 at 4:37

The function that you imagined is exactly the one you want. Now given $a \in S, b \in S$ you have $f(a,b)=c: S \times S \to S$ Clearly if you change either $a$ or $b$ you change $f(a,b)$ so the function is injective. $f$ is clearly invertible as well. Changing $c$ changes $f^{-1}(c)$ so the inverse is injective as well.