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

[tomkoolen]

Hello,

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!

 

[micromass]

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.

 

[tomkoolen]

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?

 

[micromass]

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.

 

[micromass]

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.