# A bijection between the set of all sequences whose terms are either 0 or 1, and the set of all sequences whose terms are 0, 1 or - 1.

Let X be the set of all sequences whose terms are either 0 or 1. Let Y be the set of all sequences whose terms are 0, 1 or - 1. We know that both are uncountable sets, by Cantor's diagonal technique. Give a bijection between X and Y explicitly. As X and Y are uncountable, there exists bijections to R, the set of real numbers, a composition of these, will give a bijection between X and Y. But, how to get an explicit bijection between X and Y?

Let $$X$$ be the set of $$\{0,1\}$$-sequences $$x=(x_1,x_2,\dots)$$ and $$Y$$ be the set of $$\{0,1,2\}$$-sequences $$y=(y_1,y_2,\ldots)$$. Denote by $$X_0$$ and $$Y_0$$ the subsets of sequences with only finitely many terms $$\ne0$$, and by $$X_\infty$$ and $$Y_\infty$$ the subsets of sequences with infinitely many terms $$\ne0$$. Furthermore we need the auxiliary set $$Z:=\>]0,1]\>\sqcup\>{\mathbb N}_{\geq0}$$ ($$\>\sqcup\>$$ denotes the disjoint union). We now produce explicit bijective maps $$f:\>X\to Z,\qquad g:\>Y\to Z\ ,$$ so that $$\psi:=g^{-1}\circ f$$ maps $$X$$ bijectively onto $$Y$$. Namely: f(x):=\left\{\eqalign{\sum_{k=1}^\infty x_k 2^{-k}\qquad&(x\in X_\infty) \cr \sum_{k=1}^\infty x_k2^{k-1}\quad&(x\in X_0)\cr}\right.\quad,\qquad g(y):=\left\{\eqalign{\sum_{k=1}^\infty y_k 3^{-k}\quad&(y\in Y_\infty) \cr \sum_{k=1}^\infty y_k3^{k-1}\quad&(y\in Y_0)\cr}\right.\quad. It is well known that $$\tilde f:\>x\mapsto\sum_{k=1}x_k2^{-k}$$ maps $$X$$ almost bijectively onto the real interval $$[0,1]$$, the exemption being that the two sequences $$(x_1,\ldots, x_r,1,0,0,0,\ldots)$$ and $$(x_1,\ldots, x_r,0,1,1,1,\ldots)$$ are mapped on the same number $$\xi\in[0,1]$$. The partition $$X=X_0\cup X_\infty$$ collects all zero-ending sequences in $$X_0$$, and $$\tilde f$$ maps $$X_\infty$$ bijectively onto $$\>]0,1]$$. The sequences in $$X_0$$ are then used to produce finite natural numbers $$n\in{\mathbb N}_{\geq0}$$ via binary representation. – Similarly for $$g$$.