Cardinality of the Cartesian Product of Two Equinumerous Infinite Sets

Is the cardinality of the Cartesian product of two equinumerous infinite sets the same as the cardinality of any one of the sets? I couldn't find this explicitly stated in any handout or text.

This certainly seems to be true from the examples I have seen:

• The Cartesian product of two infinitely countable sets is again infinitely countable.
• The Cartesian product of two sets with cardinality of continuum again has cardinality of continuum.

Solution 1:

This depends on whether we assume the axiom of choice.

In the presence of choice, then yes, $\vert X^2\vert=\vert X\vert$ for all infinite $X$. This was proved by Zermelo.

If choice fails, however, this may no longer be the case: e.g. it is consistent with ZF that there is a set $X$ which is infinite but cannot be partitioned into two infinite sets. Since (exercise) if $X$ is infinite then $X^2$ can be partitioned into two infinite sets, this means that such an $X$ (called amorphous) is a counterexample to the rule.

In fact, this will happen whenever choice fails: the principle "$\vert X^2\vert=\vert X\vert$ for all infinite $X$" is exactly equivalent to the axiom of choice! See For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice.

Solution 2:

One way to prove this is to first show that $\kappa +\mu =\max\{\kappa ,\mu \}$ when either $κ$ or $μ$ are infinite cardinals. This is assumed in the proof below.

I searched the web for this approach and found it here - theorem B3 in the appendix combines both, showing first that $\kappa +\mu =\max\{\kappa ,\mu \}$ and then that $\kappa \times \mu =\max\{\kappa ,\mu \}$.

We begin with a lemma.

Lemma 1: Let $B$ be a subset of an infinite set $A$ and $f: B \to B \times B$ a surjective function. Then $|B| \le |B \times B| \le |B| \le |A|$. Moreover, if $|B|$ is indeed less that $|A|$, then $f$ can be extended to a surjective function $D \to D \times D$, with $B$ a proper subset of $D$.
Proof: For the first part, apply elementary cardinality theory. For the second part, the we can find an infinite set $U$ that is disjoint from $B$, so that $|U| = |B|$; we also have the identity

$\tag 1 (B \cup U) \times (B \cup U) = (B \times B) \cup (B \times U) \cup (U \times B) \cup (U \times U)$

a disjoint union of four pieces all having a cardinality of $|B|$.

The function $f$ takes care of the first piece, and a cardinality argument allows us to surjectively cover the remaining three pieces with a function operating on the set $U$ as a domain. So we can extend $f$ to $D = B \cup U$. $\quad \blacksquare$

We are now ready to prove the main result:

Proposition 2: For any infinite set $A$,

$\tag 2 | A \times A | = |A|$

Proof
We only have to show that $|A| \ge |A \times A|$.

Consider the collection of all $(B,\phi)$ where $B \subseteq A$ and $\phi : B \to B \times B$ is a surjection. This collection is nonempty since there is a surjection $ \mathbb N \to \mathbb N \times \mathbb N$.

This collection can be partially ordered by $(B,\phi) < (C,\psi)$ if $B \subseteq C$ and $\psi|_B = \phi$. Every chain has an upper bound; simply take the union of the graphs of the functions in the chain, defining a surjective function $D \to D \times D$.

By Zorn's lemma there is a maximal element $(\hat B,\hat \phi)$. By lemma 1, we can proceed under the assumption that $|B| \lt |A|$, since otherwise we can use $\hat \phi$ to establish (2). But then lemma 1 also provides a surjective extension of $\hat \phi$, contradicting that $(\hat B,\hat \phi)$ was a maximum element, i.e. no such extension can be found. $\quad \blacksquare$

This proof was arrived at by 'lifting' the proof that $|A \times \mathbb N| = |A|$, found here.

Solution 3:

In general, you need almost the full power of ZFC (including the axiom of choice) to prove that $\#( S \times S ) = \#(S)$ for infinite $S$.$\def\pow{\mathcal{P}}$ However, one can prove without the axiom of choice that for any $S$ such that $\#( S \times S ) = \#(S)$, we also have$\def\pow{\mathcal{P}}$ $\#( \pow(S) \times \pow(S) ) = \#(\pow(S))$. This means that we do not even need AC for cardinality of all ordinary sets that you would ever encounter in situations relevant to the real world, since one can easily prove that$\def\nn{\mathbb{N}}$ $\#( \nn \times \nn ) = \#(\nn)$.