Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of |2^N x 2^N| = |2^N| with N the natural numbers

  1. Nov 10, 2015 #1

    At my exam I had to proof the title of this topic. I now know that it can easily be done by making a bijection between the two, but I still want to know why I didn't receive any points for my answer, or better stated, if there is still a way to proof the statement from my work.

    My work:
    2^N > N (Cantor)
    2^N x 2^N > N x N
    Knowing that |N x N| = |N| it follows that |2^N x 2^N| = |2^N|.

    I know that I didn't really give an explanation in that last step, but I still want to know if and how it's correct.
    Thanks in advance!
  2. jcsd
  3. Nov 10, 2015 #2
    I don't see how this resembles a proof at all. You start by using Cantor ##|2^\mathbb{N}| > |\mathbb{N}|##, which is not relevant at all here. Then you give another irrelevant inequality, and finally you just state the result. You would not get any points for that if I were the grader.
  4. Nov 10, 2015 #3
    I understand Cantor is not the way to go here but we were allowed to regard |N x N| = |N| as proven. I just want to know if there is any way to link the two?
  5. Nov 10, 2015 #4
    For any infinite set ##X##, we have ##|X\times X| = |X|##. In particular, this is true for ##X= 2^{\mathbb{N}}##. I don't see how ##|\mathbb{N}\times \mathbb{N}| = |\mathbb{N}|## is really relevant here.
  6. Nov 10, 2015 #5
    However, you can work with the disjoint union ##\mathbb{N} + \mathbb{N} := (\mathbb{N}\times \{0\})\cup (\mathbb{N}\times \{1\})##. We have ##|\mathbb{N}+\mathbb{N}| = |\mathbb{N}|## (this requires a proof). We can then say:
    [tex]|2^\mathbb{N}\times 2^\mathbb{N} | = |2^{\mathbb{N}+\mathbb{N}}| = |2^{\mathbb{N}}|[/tex]
    But both of the two equalities also require a proof.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook