How We Got From There To Here: A Story of Real Analysis

The following theorem follows directly from our previous work with the NIP and will be very handy later. It basically says that a sequence of nested closed intervals will still have a non-empty intersection even if their lengths do not converge to zero as in the NIP.

Our next theorem says that in a certain, very technical sense there are more real numbers than there are counting numbers [3]. This probably does not seem terribly significant. After all, there are real numbers which are not counting numbers. What will make this so startling is that the same cannot be said about all sets which strictly contain the counting numbers. We will get into the details of this after the theorem is proved.

So how does this theorem show that there are “more” real numbers than counting numbers? Before we address that question we need to be very careful about the meaning of the word ’more’ when we’re talking about infinite sets.

First let’s consider two finite sets, say \(A=\left\{\alpha,\beta,\gamma,\delta\right\}\) and \(B=\left\{a,b,c,d,e\right\}\text{.}\) How do we know that \(B\) is the bigger set? (It obviously is.) Clearly we can just count the number of elements in both \(A\) and \(B\text{.}\) Since \(\abs{A}=4\) and \(\abs{B}=5\) and \(4\lt 5\) \(B\) is clearly bigger. But we’re looking for a way to determine the relative size of two sets without counting them because we have no way of counting the number of elements of an infinite set. Indeed, it isn’t even clear what the phrase “the number of elements” might mean when applied to the elements of an infinite set.

Such a match-up is called a one-to-one correspondence. In general, if two sets can be put in one-to-one correspondence then they are the same “size.” Of course the word “size” has lots of connotations that will begin to get in the way when we talk about infinite sets, so instead we will say that the two sets have the same cardinality. Speaking loosely, this just means that they are the same size.

More precisely, if a given set \(S\) can be put in one-to-one correspondence with a finite set of consecutive integers, say \(\left\{1,2,3,\ldots, N\right\}\text{,}\) then we say that the cardinality of the set is \(N\text{.}\) But this just means that both sets have the same cardinality. It is this notion of one-to-one correspondence, along with the next two definitions, which will allow us to compare the sizes (cardinalities) of infinite sets.

Since \(\NN\) is an infinite set, we have no symbol to designate its cardinality so we have to invent one. The symbol used by Cantor and adopted by mathematicians ever since is \(\aleph_0\text{.}\) Thus the cardinality of any countably infinite set is \(\aleph_0\text{.}\)

We have already given the following definition informally. We include it formally here for later reference.

With these two definitions in place we can see that Theorem 11.1.3 is nothing less than the statement that the real numbers are not countably infinite. Since it is certainly not finite, then we say that the set of real numbers is uncountable and therefore “bigger” than the natural numbers!

If some real numbers are repeated in our sequence then all of the real numbers are a subset of our sequence and will therefore also be countable (see Problem 11.1.7, part a).

In either case, every sequence is countable. But our theorem says that no sequence in \(\RR\) includes all of \(\RR\text{.}\) Therefore \(\RR\) is uncountable.

Most of the sets you have encountered so far in your life have been countable.

In fact, if we start with a countable set it is rather difficult to use it to build anything but another countable set.

It seems that no matter what we do the only example of an uncountably infinite set is \(\RR\text{.}\) But wait! Remember the rational numbers? They were similar to the real numbers in many ways. Perhaps they are uncountably infinite too?

Alas, no. The rational numbers turn out to be countable too.

The following corollary says that the cardinality of the real numbers is much larger than the cardinality of the rational numbers, despite the fact that both are infinite.

That is, as a subset of the reals, the rationals can be contained in a sequence of intervals, the sum of whose lengths can be arbitrarily small. In a sense this says that a countably infinite set is so small (on the transfinite scale) that it is “almost” finite.

Usually we express this idea with the statement, “\(\QQ\) is a set of measure zero in \(\RR\)”. The term “measure” has a precise meaning which we will not pursue. The following corollary contains the essence of the idea.

Notice how this idea hearkens back to the discussion of Leibniz’s approach to the Product Rule (equation (9)). He simply tossed aside the expression \(\dx{ x}\dx{ y}\) because it was infinitely small compared to either \(x\dx{ y}\) or \(y\dx{ x}\text{.}\) Although this isn’t quite the same thing we are discussing here it is similar and it is clear that Leibniz’s insight and intuition were extremely acute. They were moving him in the right direction, at least.

All of our efforts to build an uncountable set from a countable one have come to nothing. In fact many sets that at first “feel” like they should be uncountable are in fact countable. This makes the uncountability of \(\RR\) all the more remarkable.

However if we start with an uncountable set it is relatively easy to build others from it.