A Few "Simple" Proofs Concerning the Cardinality of Sets
This semester we're teaching a course on Real Analysis, and the first chapter of real analysis is on sets. Regarding the cardinality of infinite sets, there are many conclusions that run against intuition. The proof techniques behind these conclusions are exactly the core methods of set theory. Yet I've found that although many of these conclusions seem to contradict our intuition, on closer reflection they're actually not as "outrageous" as we might imagine. Meanwhile, the textbook we currently use, Theory of Real Variable Functions and Functional Analysis (by Cao Guangfu), doesn't use the seemingly simple proofs, but instead resorts to some relatively complicated theorems, which gives the impression of unnecessary mystification.
1. The set of all real numbers cannot be put in one-to-one correspondence with the set of all positive integers
This is one of the basic results in set theory. The proof is quite simple: if all real numbers could be put in one-to-one correspondence with all positive integers, then the real numbers on $(0,1)$ could also be put in one-to-one correspondence with all positive integers. Writing all the real numbers on $(0,1)$ as infinite decimals with no repeating block of 0's (for example, representing 0.1 as 0.0999...), suppose we have a correspondence of the form:
$$\begin{aligned}&a_1=0.a_{11} a_{12} a_{13} a_{14}\dots\\ &a_2=0.a_{21} a_{22} a_{23} a_{24}\dots\\ &a_3=0.a_{31} a_{32} a_{33} a_{34}\dots\\ &\dots\dots \end{aligned}$$
where $a_{ij}$ is any one of 0,1,2,...,9, representing the $j$-th decimal digit of $a_{i}$. Now construct a number
$$b=0.b_1 b_2 b_3 b_4\dots$$
where $b_i=1$ if $a_{ii}\neq 1$; and $b_{i}=0$ if $a_{ii} =1$. From the way $b$ is constructed, we see that $b$ does not appear among $\{a_n\}$, which contradicts our assumption.
This proof technique is known as the "diagonal argument," and it's an extremely elementary and easily understood technique — I recall being able to follow this proof back in middle school (even though I didn't have a clear concept of sets at that time). Yet somehow, our textbook uses the far more high-brow Nested Interval Theorem instead. Is it because once you've learned something hard to understand, you have to use a hard-to-understand proof for it? Only then does the math we're learning look sufficiently "advanced"? I simply don't believe I could have understood the Nested Interval Theorem back in middle school.
2. The union of countably many sets of the cardinality of the continuum is still of the cardinality of the continuum
A set with the cardinality of the continuum is a set whose cardinality equals that of the set of real numbers, usually denoted $C$. The proof of this proposition is very easy — in fact, essentially obvious — yet somehow our textbook piles on a whole bunch of tedious symbols to prove it.
We know that the set of real numbers on $[0,1)$ has cardinality $C$, the set of real numbers on $[1,2)$ has cardinality $C$, the set of real numbers on $[2,3)$ has cardinality $C$, and so on. Putting these together,
$$[0,1)\cup [1,2)\cup[2,3)\cup\dots=[0,\infty)$$
is exactly the set of all non-negative real numbers. Surely its cardinality is none other than $C$?
3. The union of countably many countable sets is still countable
This proof is analogous to the one above. We know that the set of rational numbers on $[0,1)$ is countable, the set of rational numbers on $[1,2)$ is countable, the set of rational numbers on $[2,3)$ is countable, and so on. Putting these together,
$$[0,1)\cup [1,2)\cup[2,3)\cup\dots=[0,\infty)$$
is exactly the set of all non-negative rational numbers, which is of course countable.
4. $\mathbb{R}^{\infty}$ is still of the cardinality of the continuum
Here $\infty$ denotes a countably infinite cardinal. This says that the set of real sequences $\{x_1 x_2 x_3 \dots\}$ is still in one-to-one correspondence with the real numbers themselves, where $x_i$ is any real number in $(0,1)$. The proof here isn't necessarily simple, but it's worth mentioning.
The proof isn't especially difficult — we just need to construct an injection
$$\{x_1 x_2 x_3 \dots\}\mapsto (0,1)$$
To do this, we simply map the element $x_1 x_2 x_3\dots$ to $y\in (0,1)$, where $y$ is constructed as follows (writing $S_i (x)$ for the $i$-th decimal digit of $x$):
$$S_{(2^i+2^{i+1} j)} (y)=S_{j+1} (x_{i+1}),\quad i,j=0,1,2,\dots$$
Looks mysterious, and you're not sure how anyone would come up with this construction? Just write out the first few terms by hand, and the reader will surely have a lightbulb moment~~ This too is quite a useful technique for proofs involving cardinality.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.