# An injection from $\mathcal{P} (\mathbb{Z^{+})}$ to $\mathcal{P} (\mathbb{ N \times N)}$

I am thinking about how to prove that $$\mathcal{P} (\mathbb{ N \times N)}$$ – the power set of $$\mathbb{N \times N}$$ – is not countable. My idea was to show the existence of an injection $$f: \mathcal{P} (\mathbb{Z^{+})}$$ $$\rightarrow$$ $$\mathcal{P} (\mathbb{ N \times N)}$$, and then, supposing $$\mathcal{P} (\mathbb{ N \times N)}$$ were countable, there would also exist an injection from it to $$\mathbb{Z^{+}}$$, and so, the composition $$f \circ g: f: \mathcal{P} (\mathbb{Z^{+})}$$ $$\rightarrow$$ $$\mathbb{Z^{+}}$$ would also be injective, contradicting Cantor's theorem. I thought this was pretty neat, but I've slowed down trying to think about whether there could be such an injection or not. I wonder if anyone can help me think about how to think about whether such an injection – from the power set of $$\mathbb{Z^{+}}$$ to the power set of $$\mathbb{N \times N}$$ – would be possible or not?

• If you know $\mathscr{P}({\mathbb{Z}^{+}})$ is not countable, then trivially $\mathscr{P}(\mathbb{N})$ and $\mathscr{P}(\mathbb{N}\times \mathbb{N})$ is not countable.
– Yos
Dec 14, 2022 at 17:27
• What's the difference between $\mathbb Z^+$ and $\mathbb N$ here? If $\mathbb Z^+ = \mathbb N$, then just use the injection $\{x\}_x \mapsto \{(x, 1)\}_x$. Dec 14, 2022 at 17:38
• I should have said. $\mathbb{N}$ includes $0$ in that way I'm setting things up, so $\mathbb{N} \neq \mathbb{Z^{+}}$ Dec 14, 2022 at 17:40
• @Nakayama you're using 'trivial' a bit loosely here. Dec 14, 2022 at 17:55
• If $A \subseteq B$, then $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ proves it trivially. As $\mathbb{N} \times \{0\} \subseteq \mathbb{N} \times \mathbb{N}$, and the first is in bijection with $\mathbb{Z}^+$, the result follows. I think that this is what @Nakayama meant. Dec 14, 2022 at 22:25