0
$\begingroup$

I need to prove the above equality without Cantor-Bernstein Theorem or cardinals arithmetic (i.e., a bijection must be found).

I know that for example $\;S\to 1_S=\;$ the indicator function, gives a bijection $\;P(\Bbb N)\to \{0,1\}^{\Bbb N}\;$ , so if I can find a bijection $\;P(\Bbb N)\to\{01,2,3\}^{\Bbb N}\;$ then I can compose these two and that's all. Yet this last one is making problems to me, so any help will be appreciated.

$\endgroup$
  • 1
    $\begingroup$ $\{0,1\} \times \{0,1\}$ is equipotent to $\{0,1,2,3\}$. Use even and odd coordinates. $\endgroup$ – Henno Brandsma Feb 1 '16 at 21:41
  • $\begingroup$ Thank you Henno, yet I still can't see your point as the left set is $\;\{0,1\}^{\Bbb N}\;$ and not the cartesian product. $\endgroup$ – DonAntonio Feb 1 '16 at 21:44
7
$\begingroup$

HINT: You can interpret a binary sequence as a sequence base four by grouping it into pairs of digits.

$\endgroup$
  • $\begingroup$ Thank you very much Brian. Let me see if I get your point: every pair in the sequence will be translated to basis four say by a law like $$(0,0)\to 0\;,\;\;(0,1)\to 1\;,\;\;(1,0)\to 2\;,\;\;(1,1)\to3\;?$$ Thus, we'd get for instance $$(0,1,1,1,1,1,0,0,1,0,1,0,0,0,1,0,...)\to (1,3,3,0,2,2,0,2,...)\;\;?$$ $\endgroup$ – DonAntonio Feb 1 '16 at 22:03
  • $\begingroup$ Yes, it looks so beautiful that it's hard for me to convince me it works. Thanks a lot! $\endgroup$ – DonAntonio Feb 1 '16 at 22:04
  • 1
    $\begingroup$ @Joanpemo: You’re very welcome. Yes, that’s exactly what I was suggesting. $\endgroup$ – Brian M. Scott Feb 1 '16 at 22:05

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.