4
$\begingroup$

This question already has an answer here:

As I study the first part of abstract algebra, I have a question: why $\left\vert{\mathbb R}\right\vert = \left\vert{\mathbb R^2}\right\vert$?

And moreover, I knew the fact that $\left\vert{\mathbb R}\right\vert = \left\vert{\mathbb R^n}\right\vert$.

Does the equality apply to any infinite set? How can I prove them?

|cite|improve this question
$\endgroup$

marked as duplicate by Alex Mathers, skyking, Asaf Karagila♦ cardinals Jan 10 '17 at 13:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ @AlexMathers Not fully duplicate. The question is also whether $|X^n|=|X|$ if $X$ is an infinite set. $\endgroup$ – skyking Jan 10 '17 at 9:35
  • 2
    $\begingroup$ There you can see that if you accept the axiom of choice (which many do) then if $X$ and $Y$ are infinite and $|X|=|Y|$ then $|X\times Y| = |X|=|Y|$. Otherwise (if you don't accept AC) you can't tell in general if $|X^n|=|X|$. $\endgroup$ – skyking Jan 10 '17 at 9:45
  • $\begingroup$ @skyking: But if $X$ is some iterated power-set of $\mathbb{N}$, then ZF (without AC) is more than enough and the proof is simple too, which is relevant for $\mathbb{R} \approx \mathcal{P}(\mathbb{N})$. $\endgroup$ – user21820 Jan 19 '17 at 16:15
  • $\begingroup$ @user21820 But all infinite sets need not be iterated power-sets of $\mathbb N$. The question also was about if this is true for any infinite set. $\endgroup$ – skyking Jan 20 '17 at 8:08
  • $\begingroup$ @skyking: Of course, which is why I said my comment is relevant for the real numbers. A lot of people think that one needs AC to prove such results but in applied mathematics very little (perhaps none) needs AC. $\endgroup$ – user21820 Jan 20 '17 at 9:25
5
$\begingroup$

You can think of a real number in decimal notation: an infinite sequence of digits with a decimal point somewhere in there. Now you can take $n$ (e.g. $n=3$) such numbers and interleave their digits like this:

      1  2.  3  5  6…
  1  3  7 . 2  7  3 …
    9  3  .1  5  8  …
⇒ 10931372.123575836…

So this way you have turned a triple of real numbers into a single real number in a reversible fashion. To make this rigorous you'd have to consider special cases like $0.999… = 1$, but the above should convey the general idea in an intuitive way.

For $n=\infty$ this argument no longer holds in this fashion. And it's not that trivial there, either, since it depends on the kind of infinity. Most likely you have contable infinity in mind there, I guess, so you are asking about $\mathfrak c^{\aleph_0}$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ And $\mathfrak c^{\aleph_0}=\mathfrak c$ of course. But I think he's asking whether $|X|=|X^2|$ holds for every infinite $X.$ $\endgroup$ – bof Jan 10 '17 at 9:40
  • $\begingroup$ @bof: Right now I'm not sure how to intuitively show that $\mathfrak c^{\aleph_0}=\mathfrak c$, so I'm not sure I agree with “of course”. But you are right, now that I read the question again, infinite base sets are more likely what this question is about. $\endgroup$ – MvG Jan 10 '17 at 9:54
  • 1
    $\begingroup$ Well, if you think of a real number (loosely) as an infinite sequence of digits, then you can think of an infinite sequence of real numbers as an infinite two-dimensional array of digits, so it boils down to $\aleph_0\cdot\aleph_0=\aleph_0.$ $\endgroup$ – bof Jan 10 '17 at 10:02
3
$\begingroup$

The existence of space-filling curves shows that the cardinality of $\mathbb{R}^n$ can be at most that of $\mathbb{R}$. A space-filling curve in a curve parametrized by a surjective mapping $s: \mathbb{R} \rightarrow \mathbb{R}^n$. Since $s$ is surjective, we must conclude that $|\mathbb{R}^n| \leq |\mathbb{R}|$.

More generally, to show that we have $|A^n| = |A|$ for any infinite set $A$ and finite $n \geq 1$, it is enough to show that $|A \times A| = |A|$, since the general case then follows by a trivial inductive argument.

To prove the result, consider the family $\mathcal{F}$ of those functions $f$ such that $f: X \times X \rightarrow X$, where $X$ is a subset of $A$. $\mathcal{F}$ is non-empty, for if $X$ is a countable subset of $A$, then the usual dovetailing argument tells us that such an $f$ exist. It is also easy to see that $\mathcal{F}$ can be equipped with a partial order $\sqsubseteq$, namely that of extension: $f_1 \sqsubseteq f_2$ if $\mathrm{dom}(f_1) \subseteq \mathrm{dom}(f_2)$ and whenever $f_1(x) = y$, then also $f_1(x) = y$. Because $\mathcal{F}$ is partially ordered, we know from Zorn's lemma that it has a maximal element $f_{max}$. So let $\mathrm{dom}(f_{max}) = X$. All that is left is then to show that $|X| = |A|$.

Suppose $X$ had strictly smaller cardinality than $A$. But then, since $|A| = \max(|X|,|A \setminus X|)$ we must have that $|A| = |A \setminus X|$ and therefore that $|X| < |A \setminus X|$. This then means that we can find a $Y \subset A \setminus X$ of the same cardinality as $X$. But now consider the sets $X \times Y$, $Y \times X$ and $Y \times Y$. Each of these sets is infinite and has the same cardinality as $X \times X$ and therefore also the same cardinality as $X$ and as $Y$. Therefore we have

$$ |X \times Y \cup Y \times X \cup Y \times Y| = |Y|$$

But $X \times Y \cup Y \times X \cup Y \times Y = (X \cup Y) \times (X \cup Y)$, so this means that we can extend $f_{max}$ such that its domain is $(X \cup Y) \times (X \cup Y)$, and that is a contradiction, since $f_{max}$ was assumed to be maximal.

|cite|improve this answer
$\endgroup$

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