elementary set theory - If $X$ is infinite, then $X$ and $Xtimes X$ are equinumerous

If $X$ is infinite, then $X$ and $X\times X$ are equinumerous.

---

Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!

---

My attempt:

We denote $A$ and $B$ are equinumerous by $A\sim B$.

Let $Y=\{(A,f) \mid A \in\mathcal{P}(X) \text{ and } f:A \to A\times A\text{ is bijective }\}$. We define a partial order $<$ on $Y$ by $$(A_1,f_1) < (A_2,f_2) \iff A_1 \subseteq A_2 \text{ and } f_1\subseteq f_2$$

Since $X$ is infinite, there exists $A\subseteq X$ such that $A \sim \Bbb N$ (Here we assume Axiom of Countable Choice). Thus $A\sim \Bbb N\sim \Bbb N\times \Bbb N\sim A\times A$.

Hence there is a bijection $f:A\to A\times A$, and consequently $f\in Y$ and $Y\neq\emptyset$.

For any chain $Z$ in $Y$, let $F=\{f \mid \exists A \in\mathcal{P}(X),(A,f)\in Z\}$ and $f^\ast=\bigcup\limits_{f\in F}f$.

1. $f^\ast$ is a mapping

For $(a,x_1),(a,x_2)\in f^\ast$, there are $(A_1,f_1),(A_2,f_2) \in Z$ such that $(a,x_1)\in f_1$ and $(a,x_2)\in f_2$. Since $Z$ is a chain, we can safely assume $(A_1,f_1) < (A_2,f_2)$. It follows that $f_1 \subseteq f_2$. Thus $(a,x_1),(a,x_2)\in f_2$ and consequently $x_1=x_2$ by the fact that $f_2$ is a mapping.

Let $A^\ast=\operatorname{dom}f^\ast$, then $A^\ast=\bigcup\limits_{f\in F} \operatorname{dom}f$.

2. $f^\ast$ is surjective

For all $f\in F$, $f$ is a bijection from $\operatorname{dom}f$ to $\operatorname{dom}f\times\operatorname{dom}f$, and thus $\operatorname{ran}f = \operatorname{dom}f\times\operatorname{dom}f$.

$\operatorname{ran}f^\ast=\bigcup\limits_{f\in F} \operatorname{ran}f =\bigcup\limits_{f\in F} (\operatorname{dom}f \times \operatorname{dom}f) \subseteq (\bigcup\limits_{f\in F} \operatorname{dom}f) \times(\bigcup\limits_{f\in F} \operatorname{dom}f) =$ $\operatorname{dom}f^\ast \times \operatorname{dom}f^\ast$ $= A^\ast \times A^\ast$. Thus $\operatorname{ran}f^\ast\subseteq A^\ast\times A^\ast$.

For any $(a_1,a_2)\in A^\ast\times A^\ast$, since $A^\ast=\bigcup\limits_{f\in F} \operatorname{dom}f$, there exist $(A_1,f_1),(A_2,f_2)\in Z$ such that $a_1\in A_1$ and $a_2\in A_2$. Since $Z$ is a chain, we can safely assume that $(A_1,f_1)<(A_2,f_2)$, then $A_1 \subseteq A_2$, then $a_1,a_2\in A_2$, then $(a_1,a_2)\in A_2\times A_2$. Since $f_2$ is bijective, there exists $a\in A_2\subseteq A^\ast$ such that $f(a)=f^\ast(a)=(a_1,a_2)\in A_2\times A_2\subseteq A^\ast\times A^\ast$.

Hence there exists $a\in A^\ast$ such that $f^\ast(a)=(a_1,a_2)$ for any $(a_1,a_2)\in A^\ast\times A^\ast$. Thus $f^\ast$ is surjective.

3. $f^\ast$ is injective

Assume $(a_1,x),(a_2,x)\in f^\ast$. Then there exists $(A_1,f_1),(A_2,f_2) \in Z$ such that $(a_1,x) \in f_1$ and $(a_2,x) \in f_2$. Since $Z$ is a chain, we can safely assume $(A_1,f_1) < (A_2,f_2)$. It follows that $f_1 \subseteq f_2$. Thus $f_1(a_1)=f_2(a_1)$ and consequently $f_2(a_2)=x=f_1(a_1)=f_2(a_1)$. Hence $f_2(a_2)=f_2(a_1)$ and consequently $a_2=a_1$ by the fact that $f_2$ is injective. It follows that $f^\ast$ is injective.

To sum up, $f^\ast:A^\ast\to A^\ast\times A^\ast$ is bijective and hence $A^\ast\sim A^\ast\times A^\ast$ and $f^\ast \in Y$. Furthermore, $f^\ast$ is an upper bound of $Z$ by definition. Thus $Y$ satisfies the requirement of Zorn's Lemma and hence has a maximal element $(\bar{A},\bar{f})$.

4. $X\sim X\times X$

First, we prove $X\sim \bar{A}$. If not, then $X\setminus \bar{A}$ is infinite and consequently there exists $C\subseteq X\setminus \bar{A}$ such that $C\sim \Bbb N\sim \Bbb N \times\Bbb N \sim C\times C$. Thus there is a bijection $\underline f:C \to C\times C$. Hence $g=\bar{f} \cup \underline f$ is a bijection from $\bar{A}\cup C$ to $(\bar{A}\times\bar{A})\cup (C\times C)$. Hence $\bar{A}\cup C \sim (\bar{A}\times\bar{A})\cup (C\times C)$.

Since $C\sim \Bbb N$, $(\bar{A}\times\bar{A})\cup (C\times C) \sim \bar{A}\times\bar{A} \sim (\bar{A}\cup C)\times(\bar{A}\cup C)$ by Lemma. It follows that $\bar{A}\cup C\sim (\bar{A}\cup C)\times(\bar{A}\cup C)$ and consequently there exists a bijection $G:\bar{A}\cup C\to (\bar{A}\cup C)\times(\bar{A}\cup C)$. Thus $(\bar{A}\cup C,G)\in Y$ and $\bar{f}\subsetneq G$. This contradicts the maximality of $(\bar{A},\bar{f})$. Hence $X\sim\bar{A}\sim \bar{A}\times \bar{A}\sim X\times X$. This completes the proof.

---

Update: I fixed Part 4 as follows:

We denote:

1. $X\sim Y \iff$ $X$ and $Y$ are equinumerous.




2. $|X|+|Y|:=|A\cup B|$ for $X\sim A$, $Y\sim B$, and $A\cap B=\emptyset$.




3. $|X|.|Y|:=|X\times Y|$.

Lemma 1: If $\aleph_0\le |Z|$, $|X|+|Y|=|Z|$, and $|X|<|Z|$. Then $|Y|=|Z|$. (I presented a proof here)

Lemma 2: If $\aleph_0\le |X|=|Y|$. Then $|X|+|Y|=|X|$. (I presented a proof here)

4. $X\sim X\times X$

We first prove $\bar{A}\sim X$. Assume the contrary that $|\bar{A}|\neq |X|$, then $|\bar{A}|< |X|$.

We have $\bar{A} \cup (X\setminus \bar{A})=X$, $\bar{A} \cap (X\setminus \bar{A})=\emptyset$, and $|\bar{A}|<|X|$. Then $|X\setminus \bar{A}|=|X|$ by Lemma 1. It follows that there exists $C\subseteq X\setminus \bar{A}$ such that $|C|=|\bar{A}|<|X\setminus \bar{A}|=|X|$. Consider $$D=(C\times \bar{A})\cup(\bar{A}\times C)\cup(C\times C)$$ We have the following claims:

a. $(\bar{A}\times \bar{A})\cup D=(\bar{A}\times \bar{A})\cup(C\times \bar{A})\cup(\bar{A}\times C)\cup(C\times C)=(\bar A\cup C)\times(\bar A\cup C)$ by the definition of Cartesian product.

b. Since $|C|=|\bar{A}|$, $|C\times \bar{A}|=|\bar{A}\times C|=|C\times C|=|\bar{A}\times \bar{A}|=|\bar{A}|$ [since $\bar{f}:\bar{A}\to\bar{A}\times \bar{A}$ is bijective].

c. Since $|C\times \bar{A}|=|\bar{A}\times C|=|C\times C|=|\bar{A}\times \bar{A}|=|\bar{A}|\ge\aleph_0$ and they are pairwise-disjoint [Since $\bar A\cap C=\emptyset$], $|D|=|\bar{A}|$ by Lemma 2.

d. Since $|C|=|\bar{A}|=|D|$, $|C|=|D|$. Thus there exists a bijection $\underline f: C\to D$.

Let $G=\bar f\cup \underline f$, then $G:\bar A\cup C\to (\bar A\times\bar A)\cup D$ is bijective since $\bar f, \underline f$ are bijective, or equivalently $G:\bar A\cup C\to(\bar A\cup C)\times(\bar A\cup C)$ is bijective. It follows that $\bar f\subsetneq G$ and $(\bar A\cup C,G)\in Y$. This contradicts the maximality of $(\bar f,\bar A)$. Hence $X\sim\bar A\sim \bar A\times\bar A\sim A\times X$.$$\tag*{$\blacksquare$}$$