How can I prove (without cardinal numbers) that $P(P(\mathbb{N}))$ is equipollent to $P(P(\mathbb{N})) \times P(P(\mathbb{N}))$

Question

I am stuck trying to prove that $P(P(\mathbb{N}))$ is equipollent to $P(P(\mathbb{N})) \times P(P(\mathbb{N}))$. I was thinking that it is enough to prove $P(\mathbb{R}) \sim P(\mathbb{R}) \times P(\mathbb{R})$, or even $2^{\mathbb{R}} \sim 2^{\mathbb{R}} \times 2^{\mathbb{R}}$ , but I still don't know how to finish this. It would be even better if you can prove that in general for any infinite set $X$ it's true that $X \times X \sim X$.

Answer 1

The statement that $|X|=|X\times X|$ is equivalent to the axiom of choice. You can prove it as follows. Let: $$\mathcal{H}:=\{f:B \longrightarrow B\times B : B\subset X \text{ and } f \text{ is a bijection}\}$$ with the relation order given by $g<h \Longleftrightarrow \operatorname{Dom}g\subset\operatorname{Dom} h \text{ and } h|_{\operatorname{Dom} g}=g$. It's easy to proof that for every chain $\mathcal{C}\subset\mathcal{H}$, the function defined as $f_\mathcal{C}(c):=f(c)$ if $c\in S\subset\mathcal{C}$ is well defined, is a element of $\mathcal{H}$ and is an upper bound for $\mathcal{C}$.

Hence there is a maximal $f_0\in\mathcal{H}$ (Zorn's Lemma). It can be proved (it's not an trivial proof, but I can write it down here if you want), that $\operatorname{Dom} f_0=X$, so $f_0$ is a bijection between $X$ and $X\times X$.

Let $A_0:=\operatorname{Dom} f_0$ and lets prove that there is a bijective map between $A_0$ and $X$.

For this purpose, assume that there exists a surjective aplication $g:X\setminus A_0\longrightarrow A_0$. Then, you can easily prove using axiom of choice that there exists $S\subset X\setminus A_0$ such that $\phi:=g|_{S}$ is bijective. Now note that: $$(A_0\cup S)\times(A_0\cup S)=(A_0\times A_0)\cup(A_0\times S)\cup(S\times A_0)\cup(S\times S)$$
And also note that the function $\theta:=\phi\circ f_0\circ(\phi^{-1},\phi^{-1})$ is a bijection between $S$ and $S\times S$.

There exists a bijective map $j:S\longrightarrow(A_0\times S)\cup(S\times A_0)\cup(S\times S)$ (the existence of this map is given by the fact that $|S|=|S\times S|=|(A_0\times S)\cup(S\times A_0)\cup(S\times S)|$, because the union of disjoint sets of same cardinality has the same cardinality as any of the sets or without using cardinals at all, there is a bijection between $T$ and $T\cup P$ whenever there exists one between $T$ and $P$; again, if you want a proof of this I can write it down). Then, the map defined as: \begin{align*} h_0:A_0\cup S &\longrightarrow(A_0\cup S)\times(A_0\cup S) \\ x &\longmapsto h_0(x):=\begin{cases}f_0(x) &\text{ if } x\in A_0 \\ j(x) &\text{ if } x\in S\setminus A_0\end{cases} \end{align*} is a bijection, and $h_0|_{A_0}=f_0$. Hence $f_0<h_0$, which is a contradiction. Then there doesn't exists a surjective map $g:X\setminus A_0\longrightarrow A_0$, which implies that there actually is a bijection $k:X\longrightarrow A_0$ (this is also a consecuence of the cardinality of union of disjoint sets). Finally, the map: $$k\circ f_0 \circ (k^{-1},k^{-1}): X\longrightarrow X\times X$$ is bijective, which concludes the proof.

Answer 2

You can see that for any sets $A$ and $B$, there is a bijection from $\mathcal{P}(A)\times \mathcal{P}(B)$ to $\mathcal{P}(A\sqcup B)$, where $A\sqcup B:=\{0\}\times A\cup \{1\}\times B$ is the disjoint union of $A$ and $B$: Just consider the map that sends $(X,Y)$ to $\{0\}\times X\cup \{1\}\times Y$.

(Note: Constructing the bijection does not require any knowledge about cardinals, but is directly related to showing equalities on cardinal arithmetic.)

Hence it suffices to construct a bijection between $\mathcal{P}(\mathbb{N})\sqcup \mathcal{P}(\mathbb{N})$ and $\mathcal{P}(\mathbb{N})$. Here is a way to constructing it: for each $(i,X)$, consider $f(i,X)=\{0\mid i=1\}\cup \{n+1\mid n\in X\}$.

Answer 3

You don’t need the axiom of choice for this specific case of $|X|=|X\times X|$.

Let $f:\Bbb N\to 2\Bbb N:n\mapsto 2n$ and $g:\Bbb N\to 2\Bbb N+1:n\mapsto 2n+1$. Define

$$\begin{align*} \varphi&:\wp(\wp(\Bbb N))\times\wp(\wp(\Bbb N))\to\wp(\wp(\Bbb N))\\ &:\langle\mathscr{A},\mathscr{B}\rangle\mapsto\{f[A]\cup g[B]:\langle A,B\rangle\in\mathscr{A}\times\mathscr{B}\}\,. \end{align*}$$

The map $\varphi$ actually recoverably encodes each member of $\mathscr{A}\times\mathscr{B}$ as a subset of $\Bbb N$.

Suppose that $\mathscr{C}\in\operatorname{ran}\varphi$. For each $C\in\mathscr{C}$ let

$$A_C=\left\{\frac{n}2:n\in C\cap 2\Bbb N\right\}$$

and

$$B_C=\left\{\frac{n-1}2:n\in C\cap(2\Bbb N+1)\right\}\,;$$

then $C=f[A_C]\cup g[B_C]$. Let $\mathscr{A}=\{A_C:C\in\mathscr{C}\}$ and $\mathscr{B}=\{B_C:C\in\mathscr{C}\}$; then $\mathscr{C}=\varphi(\langle\mathscr{A},\mathscr{B}\rangle)$. Thus, $\varphi$ is an injection. Since there is an obvious injection in the other direction, the result follows from the Cantor-Schröder-Bernstein theorem.

In the original version of this answer I thought that I had avoided having to use the Cantor-Schröder-Bernstein theorem and incorrectly said that $\varphi$ was a bijection, but of course it is not: the range of $\varphi$ is the family of $\mathscr{C}\in\wp(\wp(\Bbb N))$ such that if $\mathscr{A}$ and $\mathscr{B}$ are defined as in the previous paragraph, then $\mathscr{C}=\{f[A]\cup g[B]:\langle A,B\rangle\in\mathscr{A}\times\mathscr{B}\}$, so that $\mathscr{C}$ encodes all of $\mathscr{A}\times\mathscr{B}$, not just an arbitrary set $\mathscr{D}\subseteq\mathscr{A}\times\mathscr{B}$ big enough so that $\pi_0[\mathscr{D}]=\mathscr{A}$ and $\pi_1[\mathscr{D}]=\mathscr{B}$.