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?

  • $\begingroup$ 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. $\endgroup$
    – Yos
    Dec 14, 2022 at 17:27
  • $\begingroup$ 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$. $\endgroup$ Dec 14, 2022 at 17:38
  • $\begingroup$ I should have said. $\mathbb{N}$ includes $0$ in that way I'm setting things up, so $\mathbb{N} \neq \mathbb{Z^{+}}$ $\endgroup$
    – Dan Öz
    Dec 14, 2022 at 17:40
  • $\begingroup$ @Nakayama you're using 'trivial' a bit loosely here. $\endgroup$
    – Dan Öz
    Dec 14, 2022 at 17:55
  • $\begingroup$ 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. $\endgroup$
    – user480840
    Dec 14, 2022 at 22:25


You must log in to answer this question.