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.

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.

  • $\begingroup$ I realize my phrasing in the last paragraph is ambiguous. It is not the case that "there is no amorphous set" is equivalent to the axiom of choice; the equivalence is between AC and "$\forall$ infinite $X(\vert X^2\vert=\vert X\vert)$." $\endgroup$ Aug 4 '15 at 6:41
  • $\begingroup$ Actually we don't need AC to obtain the cardinality of any set that can be obtained from $\mathbb{N}$ by iterating cartesian product and power-set. At least this covers almost all sets in 'ordinary' mathematics. $\endgroup$
    – user21820
    Aug 4 '15 at 6:58
  • $\begingroup$ @user21820 Sure, but that in no way contradicts anything I wrote. $\endgroup$ Aug 4 '15 at 15:44
  • $\begingroup$ Yup it's just an interesting fact that I proved but haven't seen before. If you have any reference for it I'd be glad to know. $\endgroup$
    – user21820
    Aug 4 '15 at 17:02
  • 1
    $\begingroup$ Yes to the first. For the second, the $\beth$ numbers are basically iterates of the powerset: $\beth_0=\omega$, $\beth_{\alpha+1}=2^{\beth_\alpha}$, and $\beth_\lambda=\sup\{\beth_\alpha: \alpha<\lambda\}$ for $\lambda$ a limit ordinal. See en.wikipedia.org/wiki/Beth_number. $\endgroup$ Aug 5 '15 at 5:38

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|$

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.

  • $\begingroup$ Can you please explain why ...union of four pieces all having a cardinality of $|B|$? $\endgroup$
    – Akira
    Sep 14 '18 at 9:13
  • $\begingroup$ @LeAnhDung We have $|B \times B| = |B|$ and $|U| = |B|.\,$ So $|B \times B| = |B| \text{ and } |B \times U| = |B \times B| = |B| \text{ and } |U \times B| = |B \times B| = |B| \text{ and } |U \times U| = |B \times B| = |B|.$ $\endgroup$ Sep 14 '18 at 10:25
  • $\begingroup$ How do you know $|B \times B| = |B|$? Is this what we are proving? $\endgroup$
    – Akira
    Sep 14 '18 at 10:27
  • 1
    $\begingroup$ Oh is it because there is a bijective from $B$ to $B\times B$? $\endgroup$
    – Akira
    Sep 14 '18 at 10:30
  • $\begingroup$ The hypothesis of the lemma (the surjection $f$) means that we do have it true on this 'starter set' $B$. And we know we can 'start' with any $B$ that is countable. $\endgroup$ Sep 14 '18 at 10:31

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)$.

  • $\begingroup$ Just to confirm, $\#(.)$ is another notation of the more common $|.|$ cardinality function, right? $\endgroup$
    – FreshAir
    Aug 5 '15 at 5:26
  • $\begingroup$ @FreshAir: Yes. I prefer it to avoid overloading $|$. $\endgroup$
    – user21820
    Aug 5 '15 at 5:44
  • $\begingroup$ Because |.| is also used for absolute value in arithmetic? $\endgroup$
    – FreshAir
    Aug 6 '15 at 9:23
  • 1
    $\begingroup$ @FreshAir: That's hardly the tip of the overloaded iceberg. $|$ is also used for divisibility and some people use it for set notation (I use colon instead). Then in geometry we have $||$ for parallel lines... $\endgroup$
    – user21820
    Aug 6 '15 at 14:33
  • $\begingroup$ @user21820:how to prove: If #(SxS)=#(S) then #(P(S)xP(S)=P(S)? $\endgroup$
    – KCK
    May 22 '19 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.