7
$\begingroup$

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.

I found a question here, but it is with regard to finite sets only.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\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$ – Noah Schweber 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$ – Noah Schweber 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$ – Noah Schweber Aug 5 '15 at 5:38
4
$\begingroup$

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

$\endgroup$
  • $\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 at 20:35
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you please explain why ...union of four pieces all having a cardinality of $|B|$? $\endgroup$ – MadnessFor MATH 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$ – CopyPasteIt Sep 14 '18 at 10:25
  • $\begingroup$ How do you know $|B \times B| = |B|$? Is this what we are proving? $\endgroup$ – MadnessFor MATH Sep 14 '18 at 10:27
  • 1
    $\begingroup$ Oh is it because there is a bijective from $B$ to $B\times B$? $\endgroup$ – MadnessFor MATH 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$ – CopyPasteIt Sep 14 '18 at 10:31
0
$\begingroup$

The cardinality of the Cartesian product corresponds to multiplying cardinalities.

$\endgroup$
  • $\begingroup$ I know this holds for finite sets...but it holds for infinite sets too, correct? $\endgroup$ – FreshAir Aug 4 '15 at 4:42

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.