2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for your answer. Is it possible to get a more explicit bijection? $\endgroup$ – Priya Apr 21 at 4:28

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.