We have been discussing the countably infinite. A set is countable if it can be placed into one-to-one correspondence with a set of natural numbers. One way to understand this is that a set is countable when it fits in Hilbert's Hotel, because the room assignment number gives you the one-to-one correspondence with the natural numbers. Every finite set is of course countable, but there are also the countably infinite sets, which can be placed into one-to-one correspondence with the entirety of the natural numbers.
In a previous lecture, we saw many instances of countable sets. The natural numbers themselves are countable, but so too are the integers and the rational numbers. We saw how the union of two countably infinite sets is still countable, and in fact the union of countably many countable sets is still countable. This is analogous to the situation in which Hilbert's bus pulls up to Hilbert's Hotel: we can accommodate all of the previous hotel occupants together with the bus passengers, and everyone still has their own room. Likewise, when Hilbert's train arrives with infinitely many cars, each holding infinitely many passengers, we can fit them all into the hotel.
From this we saw that the set of all finite words over a countable alphabet, that is, the set of all finite sequences of symbols from that alphabet, still forms a countable set. At this point one might wonder whether every set is countable. It is perhaps not unreasonable to expect that there is only one size of infinity, the countable infinity, and that the word "countable" simply means infinite.
Cantor discovered that this is not true. What he proved is that the set of real numbers, the set of points on the number line, is an uncountable infinity. When Cantor's cruise ship pulls up to Hilbert's Hotel, carrying one passenger for every real number with a ticket bearing a real-numbered serial number, we cannot accommodate all of those passengers. The set of real numbers is simply too large.
This is a profound achievement, because it demonstrates for the first time that there are different sizes of infinity. The infinity of the natural numbers is a strictly smaller infinity than the infinity of the real numbers. Cantor's argument establishes this rigorously, and that is precisely what I would like to show you today.
Cantor's ideas were controversial in his day, meeting with stubborn rejection from some quarters, but they were eventually accepted completely by the mathematical community. Hilbert famously declared, "Let no one cast us from the paradise that Cantor has created for us." Cantor's framework was so robust and so foundationally fulfilling that Hilbert recognized it as one of the great achievements of mathematics.
The central claim is that the real numbers form an uncountable infinity, meaning that it is impossible to establish a one-to-one correspondence between the real numbers and the natural numbers. To prove this, we proceed by contradiction. Suppose, toward contradiction, that the real numbers are a countable set. Then we could place them all in Hilbert's Hotel; in other words, we could arrange them in a list: R1, R2, R3, R4, and so on, indexed by the positive integers. Under this assumption, every real number appears somewhere on that list.
Now, given this list, we define a new number Z. The number Z takes the form zero-point-D1D2D3D4…, where each Dn is a decimal digit chosen by reference to the list. Specifically, we require that the nth digit of Z differ from the nth digit of the nth number on the list. To make this fully definite, we can use the digit 1 whenever the corresponding digit of the listed number is not 1, and the digit 7 whenever it is. There are many ways to implement this rule; what matters is only that the nth digit of Z disagrees with the nth digit of Rn.
This is the key insight, the idea that Cantor recognized as so powerful. Because D1 differs from the first digit of R1, the number Z cannot equal R1, regardless of what its remaining digits are. Because D2 differs from the second digit of R2, the number Z cannot equal R2. By the same reasoning, Z differs from R3 in the third digit, from R4 in the fourth digit, and so on down the list.
We conclude that Z is not equal to R1, not equal to R2, not equal to R3, not equal to any number on the list. But this is a contradiction, since we assumed that every real number appears on the list. Therefore our assumption was false: the real numbers cannot be countable. The reals are an uncountable infinity.
There are a few subtle points worth addressing about this argument, because a couple of issues do come up. In the argument, I was referring to the nth digit of rn, but there is an annoying complication: real numbers do not always have a unique decimal representation. We are not simply entitled to refer to, say, the third digit of a real number, because it might have two different representations, and that digit could differ depending on which one we use.
Consider what I call the most controversial equation in middle school: 1.000… and 0.999… are the same real number. These two decimal representations both represent the number one. So if someone asks, "What is the third digit after the decimal point of the number one?", you might say it is zero, or you might equally say it is nine. Real numbers can therefore have more than one representation, and this creates a slight problem for the diagonal argument as described. It is conceivable that the digit we chose differs from one representation of a given real number on the list but not from the other, meaning we have not actually guaranteed that our constructed number is distinct.
This phenomenon arises precisely in the eventually nines and eventually zeros cases. For example, 2.352999… is the same real number as 2.353000…. In fact, this is the only situation in which a real number has more than one decimal representation, so every real number has either one or two representations, and two representations are possible only when one ends in repeating nines and the other in repeating zeros.
There are at least two clean ways to handle this in the diagonal argument. One approach is to ensure, when constructing the diagonal number z, that each chosen digit dn differs from the corresponding digit in both representations of rn, whenever rn happens to have two. In that way, z will contain a digit that does not appear in any representation of any rn, guaranteeing it is genuinely distinct from every number on the list.
Alternatively, if we restrict the digits of z to ones and sevens exclusively, producing something like 0.11771771…, then z itself will never fall into the eventually-nines or eventually-zeros pattern, and so it will have a unique decimal representation. Because z has only one representation, it cannot equal any rn that has two representations, since two distinct representations correspond to a single number and z simply is not that number. This subtle issue is therefore easily handled in a variety of ways.
I want to give a concrete example of how we construct the number z, making the argument as explicit as possible. Suppose we are given a very specific list of real numbers: r1 is π, r2 is e, r3 is √2, and r4 is log 2. Writing out their decimal expansions, we have 3.14159265…, then 2.71828182…, then 1.41421356…, and finally 0.69314718…. Of course, when we assume towards a contradiction that the real numbers are countable and can therefore be placed on a list, we cannot assume the list begins with these particular numbers. This is simply an illustration of how the argument works.
Now let us build the number z from this list. Recall that we specify the digits of z one by one, choosing each digit to differ from the corresponding diagonal digit. We use the following rule: always write a 1, unless the relevant digit of rn is already a 1, in which case we write a 7. The first digit of r1 after the decimal point is 1, so we write 7. The second digit of r2 is also 1, so we write another 7. The third digit of r3 is 4, so we write 1. The fourth digit of r4 is 3, so we write 1. Thus z begins 0.7711…
By this construction, the nth digit of z differs from the nth digit of rn for every n. This guarantees that z ≠ rn for any n on the list. In our example, z is clearly different from π already because π begins with 3 while z begins with 0, but the diagonal construction ensures the difference regardless of what r1 happens to be, by directly targeting the first digit.
This is where the contradiction arises. We assumed towards contradiction that the real numbers are countable, meaning our list was supposed to contain every real number. But the number z we have constructed is a real number that differs from every entry on the list, so it cannot appear anywhere on the list. A list that was supposed to contain all real numbers has failed to contain z, and that is a contradiction.
We therefore conclude that our original assumption was false: the real numbers are not countable. They are uncountable. And this means there is more than one size of infinity.
I want to call attention to a particular aspect of this argument: the nature of the digits we examine all occur on a diagonal. The nth digit of the nth number on the list lies on this diagonal, and for precisely this reason Cantor's argument is known as the diagonal argument. It is a diagonal construction because at stage n of the construction we look at the nth digit of the nth real number on the list, and those digits trace out a diagonal. The resulting number is sometimes called the diagonal real, and we are proving Cantor's theorem by the method of diagonalization.
There is one further point about this argument worth emphasizing. When people present it, they sometimes say: "Suppose the reals were countable, so we can list all of them; now we define a new real number z by the diagonal method." I take issue with the word new, because we are not defining a new real number. We are simply defining a particular real number by reference to the list. That number already existed before any list was given; we are not creating it.
What the argument actually shows is that if someone hands us a list of real numbers, we can describe a real number, by reference to that list, which is not on it. We are not bringing this number into existence; we are merely identifying it. The diagonal real was already there. We are just pointing to it.
The diagonal argument just presented, consulting the digits of real numbers on a list, is not actually Cantor's original argument. In 1874, he published his result that the reals constitute an uncountable infinity, and he used a slightly different method.
The argument begins the same way: we suppose towards contradiction that the set of real numbers is countable, which means we can place all real numbers on a list, R1, R2, R3, and so on, and we assume that every real number appears somewhere on this list. What Cantor then does is construct a certain nested sequence of closed intervals.
To obtain the first interval, we locate R1 on the number line and choose a non-trivial closed interval [A1, B1] that excludes R1. We then look at R2. If it is already outside the interval, nothing further needs to be done at this stage; but if R2 lies inside [A1, B1], we shrink to a smaller subinterval [A2, B2] that excludes R2. We continue in this fashion: at stage n, we ensure that Rn is not contained in the interval [An, Bn].
The result is a nested sequence in which the left endpoints are increasing, A1 ≤ A2 ≤ A3 ≤ …, and the right endpoints are decreasing, B1 ≥ B2 ≥ B3 ≥ …. It is a basic theorem, well known to Cantor, that any nested sequence of closed bounded intervals must contain at least one common point. In fact, we can identify such a point explicitly: the supremum of the left endpoints, Z = supn An, is a real number that lies inside every one of the intervals.
This is where the contradiction arises. The number Z was never excluded from any interval, yet every number on the list was excluded. R1 was excluded by the first interval, R2 by the second, and so on. Therefore Z cannot equal any Rn, which means Z does not appear on the list. This contradicts our assumption that the list contained all real numbers. The overall logical structure of this argument is the same as that of the diagonal digit argument: in both cases we construct a real number that differs from every entry on the supposed complete list.
Sometimes one finds people arguing online that when Cantor's argument is presented using digit diagonalization, it is not how Cantor first did it, since he used a nested interval argument instead. But disputes about these two forms of the argument are not very important, because there is a way of looking at the nested interval argument that makes it appear exactly the same as the digit diagonalization argument. They are simply two superficially different presentations of the same underlying idea. Specifying successive digits of a real number is the same thing as defining a nested sequence of intervals, and by recognizing this we can see that the two presentations share a common foundation.
Consider what it looks like when we specify the digits of a real number. Take the closed interval from 3 to 4 on the number line. Every real number in that interval has a decimal representation beginning with 3, numbers such as 3.1, 3.5, and 3.9, as well as 3.000… itself. One might object that the endpoint 4 does not begin with a 3, but in fact 4 has the representation 3.999… repeating, so the closed interval from 3 to 4 consists precisely of those real numbers whose decimal expansion begins with the digit 3.
Now look inside this interval at the numbers whose first decimal digit is 1. These are exactly the numbers in the closed interval from 3.1 to 3.2, numbers such as 3.12, 3.15, and 3.19. The right endpoint 3.2 is included because it equals 3.1999… repeating, so it too begins with the digits 3.1. Specifying this next digit is therefore equivalent to selecting a closed subinterval nested inside the first.
We can continue one step further. The closed interval from 3.14 to 3.15 consists precisely of those numbers whose decimal representation begins with the digits 3.14, for instance, 3.141, 3.145, and 3.147. Again, the right endpoint 3.15 equals 3.1499… repeating and so belongs to the interval. Each time we specify another digit, we obtain another closed interval nested inside the previous one.
What this shows is that specifying successive digits of a real number, exactly as one does in Cantor's diagonal argument, is the same as specifying a nested sequence of closed intervals. The real number determined by all those digits is precisely the unique point lying inside every one of those intervals. By this observation, we see that the digit diagonalization argument and the nested interval argument embody the same underlying idea: at stage n, one ensures that the number being constructed differs from the nth number on the list, and consequently one produces a real number that cannot appear anywhere on the list. This is the contradiction that shows the real numbers form a strictly larger infinity.
There is a certain sociological situation surrounding Cantor's theorem. Because the result is so profound — that there are different sizes of infinity — many people are unwilling to accept it, and this has given rise to a phenomenon of crank mathematicians who write endless articles rejecting Cantor's argument. The phenomenon itself has an extremely long history. Bolzano wrote an entire treatise mocking the crank mathematicians of his own day, well before Cantor's results, targeting the circle-squarers and angle-trisectors — people who attempted, without hope, to solve classical problems that are now known to be impossible by the methods of classical geometry.
I receive emails regularly from people claiming that Cantor's proof is wrong, that all of mathematics is wrong, and that the authors of these messages are unrecognized geniuses. They send me various arguments purporting to refute Cantor's diagonal argument. In every case I have checked — and I do not always have the patience to check all of them, since it is simply too much work — there are invariably mistakes, errors, and misunderstandings. Let me share a few of the ideas that people typically offer.
One common objection runs as follows: there is no problem with the diagonal real not appearing on the list, because we can simply add it to the list, producing a new list that does contain the number z. To reconstruct the argument: in Cantor's diagonal construction, we have a supposed enumeration r1, r2, r3, … of all the real numbers, and we produce a diagonal real number z whose nth digit differs from the nth digit of rn. The contradiction arises because z is not equal to any number on the list, even though the list was assumed to contain all real numbers. The proposal in these objections is simply to take z and prepend it to the list — make it r0, for instance.
This proposal is completely without merit. The claim is not that there exists no possible list on which z could appear — of course one can construct a new list that includes z. The claim, rather, is that it is impossible to have a countable list of real numbers that already includes all real numbers. The argument establishes that for any given list, one can produce a real number that is not on that list. The fact that one can make a different list containing z is entirely beside the point. Once z is added, that is a new list, and Cantor's diagonalization applied to this new list will produce yet another real number not on it. Add that number, and there will be another missing one, and so on indefinitely. The task can never be completed. It is simply impossible to have a list of real numbers that includes every real number, because for any list whatsoever, Cantor's diagonalization method produces a real number that is not on it.
Let me mention how Cantor's result relates to the topic of potential infinity and actual infinity that we discussed in a previous lecture. It is my view that Cantor's achievement — his theorem that there are uncountable infinities — is part of the cause of the sea change that occurred in mathematics, by which mathematicians generally switched from the potentialist philosophy of infinity to the actualist philosophy of infinity.
It is perhaps not immediately clear how to frame the distinction between countable and uncountable within a potentialist framework. One might attempt a potentialist account along the following lines: the natural numbers already represent a countable infinity, but the real numbers cannot be achieved through any enumeration process. Even if one acquires real numbers in countably many steps — always possessing finitely many at a time, with more always available — it cannot be the case that all real numbers are eventually reached. Cantor's ideas explain precisely what is happening in that process: there is no countable sequence of finite sets of real numbers that encompasses every real number, and this is the sense in which the uncountable infinity of the real numbers resists a straightforward potentialist account.
There are, however, other approaches to potentialism that can make sense of the real numbers. For example, if one takes as the potentialist system all finite sets of real numbers, that constitutes a directed potentialist system, and it will validate S4.2 — to use the technical modal logic we discussed in that previous lecture. So there are ways of speaking about the infinity of the real numbers from a potentialist point of view.
Nevertheless, the most straightforward way of understanding Cantor's result is as a result about actual infinity: it is not possible to put the set of real numbers into one-to-one correspondence with the natural numbers, and that is the sense in which the real numbers constitute an uncountable infinity.
We can view developments in mathematics in part as a gradual and continual enlargement of our number concept. One might begin with the whole numbers — the numbers one, two, three, four, and so on, but without zero. The introduction of zero was actually a profound development in mathematics, arriving much later than one might expect, and its acceptance as a legitimate number was a very important step. From there, one moves to the natural numbers, which include zero.
The next step is the introduction of negative numbers, giving us the integers: zero, one, two, three, and so on, together with −1, −2, −3, and so on. This forms a mathematical structure known as a ring — we can add and multiply, and we have additive inverses. But one also wants to divide arbitrary numbers, and that is precisely the move to the rational numbers, where fractions allow us to divide by any non-zero quantity.
The rational numbers form a very rich number system, one that was central to the philosophy of the Pythagoreans in ancient times. They sought to understand so much of reality through the concept of ratio, and the robustness of the rational number system was built into their quasi-religious number mysticism. The discovery, then, that the square root of two is irrational came as a profound shock. The diagonal of a unit square has length √2, and this quantity is not rational — it lies outside that number system entirely, and one must expand the number system to accommodate it.
Numbers such as √2 are called algebraic numbers, because they satisfy polynomial equations over the integers. The number √2, for instance, is a solution of x² − 2 = 0. More generally, a number is algebraic when it is a solution of some non-trivial polynomial equation with integer coefficients. The cube root of five, for example, is algebraic because it satisfies x³ − 5 = 0.
Any number built up from roots and powers can be shown to be algebraic by tracing through the operations it involves. Consider, for example, the square root of the quantity (∛5 + 6). If we square this number, we obtain ∛5 + 6; subtracting 6 gives ∛5; cubing that gives 5; and subtracting 5 gives 0. The number therefore satisfies a specific polynomial equation and is thus algebraic. This trick works for any expression built from roots and powers, though it is in fact a deep result that not every algebraic number can be represented by radicals in that manner.
Perhaps it seems mysterious whether every real number is algebraic — whether every real number satisfies a polynomial equation over the integers. The answer is no, and this was proved by Liouville in 1844. He introduced a specific real number, now called the Liouville constant, and proved that it is not algebraic. It is, in other words, a transcendental real number.
The Liouville constant is 0.11000100000000000000000100…, where a 1 appears in the n-factorial decimal place for each positive integer n. So there is a 1 in the first place (1 factorial), the second place (2 factorial), the sixth place (3 factorial), the twenty-fourth place (4 factorial), and so on, with vast stretches of zeros in between. This kind of number is called lacunary, because it has these lakes of zeros separating the isolated 1s.
One can begin to see why the Liouville constant is not algebraic by considering what happens when you square it. If we call the number x and compute x², each isolated 1, surrounded by enormous gaps of zeros on either side, gets multiplied by other digits of x. Those isolated 1s are moved around by the multiplication, but they remain isolated. Similarly, multiplying x or any power of x by an integer constant merely shifts the isolated digits around while preserving their isolation. Consequently, there is no way to combine powers of x with integer coefficients so that everything cancels — you can never obtain zero — and that is the essential reason the Liouville constant is transcendental.
This was the first known example of a transcendental number, and I regard it as a discovery of the same profound character as the Pythagorean proof of the irrationality of the square root of two. Just as the Pythagoreans were compelled to expand their conception of number from the rationals to include the irrationals, Liouville's result compels us to expand our conception further still, from the algebraic numbers to include the transcendentals. It is equally important, and equally philosophically troubling for our capacity to comprehend these numbers. We form an idea of what numbers are, and mathematics keeps proving that something lies beyond it, demanding a larger concept in order to grasp those new realms.
Cantor offered an alternative proof for the existence of transcendental numbers. His argument runs as follows. Every algebraic number is a solution of a polynomial over the integers, and every such polynomial can be specified by a finite list of integers — namely, its coefficients. For example, the polynomial x³ − 5x² + 6x − 7 is completely determined by the list 1, −5, 6, −7, with a zero inserted wherever a term is missing.
Of course, a single polynomial may have more than one root: a polynomial of degree N has at most N real solutions. We can therefore specify any particular algebraic number by giving the polynomial together with one additional integer indicating which root — ordered by position among the real roots — we wish to designate. In this way, every algebraic number is encoded by a finite list of integers.
A finite list of integers is simply a word in the alphabet of the integers. Since the integers form a countable set, and since we proved in the previous lecture that the collection of all finite sequences over a countable set is itself countable, it follows that there are only countably many such polynomials. Each polynomial contributes only finitely many algebraic numbers, so altogether there are only countably many algebraic numbers.
From this, the existence of transcendental numbers follows immediately. The real numbers form an uncountable set, as Cantor proved, yet the algebraic numbers form only a countable subset. Therefore some real numbers must be non-algebraic — that is, they must be transcendental. In fact, the argument shows far more: there must be uncountably many transcendental numbers. If there were only countably many, then the real numbers would be the union of two countable sets — the algebraic numbers and the transcendental numbers — and hence countable, contradicting Cantor's theorem.
Cantor's argument therefore establishes not merely that some transcendental numbers exist, but that almost every real number is transcendental: only countably many reals are algebraic, while the transcendental numbers constitute an uncountable infinity.
It is worth comparing this argument with Liouville's. Liouville produced a specific number — the Liouville constant — and proved directly that it is transcendental. A natural question is whether Cantor's argument is merely a pure existence proof, one that guarantees transcendental numbers exist without identifying any particular one. Many people conclude that it is, and that Cantor's proof is therefore non-constructive in this sense. This conclusion is, in my view, mistaken. If we examine the argument carefully, we find that Cantor's proof is in fact constructive: when its details are fully unwound, it yields specific real numbers that are provably transcendental.
Recall that Cantor proves that the set of finite sequences over a countable alphabet — the set of words in a countable set of letters, or equivalently the set of finite sequences from a countable set — is itself countable, and that proof is constructive. It gives us a specific way of enumerating all finite sequences of integers. Using this, we can produce a concrete, constructive list of all the algebraic numbers, because every algebraic number is determined by the polynomial of which it is a root and its position among that polynomial's finitely many roots.
Now combine that fact with the observation that Cantor's diagonalization construction is itself constructive: the digit-diagonalization method yields a specific real number not on the given list. Therefore, if we apply Cantor diagonalization to the specific list of algebraic numbers, we obtain a specific real number that is not algebraic — that is, a specific transcendental number. This is a different way of appreciating what Cantor actually achieved.
One can read the diagonal argument as a proof by contradiction that the reals are uncountable: if they were countable, we could produce a number that is simultaneously on the list and not on the list. But another, more constructive reading of the argument — which is, in fact, how Cantor presented it in his 1874 paper — is that for every countable list of real numbers, there exists a real number not on that list, and furthermore we can specify that number exactly via the diagonalization procedure. Applying this constructive formulation to the algebraic numbers, which we can enumerate in a concrete way, we thereby produce a specific transcendental number.
Some years ago I came across an article in one of the mathematical monthly journals — I have unfortunately lost the citation over the decades — whose title was something like "0.11717… is transcendental." The point of that essay, which I found fantastic, was to dive into the details of the specific enumeration provided by Cantor's listing of the algebraic numbers and to carry out the diagonalization procedure explicitly. The first few digits of the resulting number appeared in the article's title. What it demonstrates is that there is an analog of Liouville's constant arising from Cantor's construction — one might call it the Cantor constant.
Perhaps Dedekind's name should be attached to that constant as well, because it has recently come to light that in the correspondence between Dedekind and Cantor leading up to the 1874 paper, many of the key ideas — including the specific insight that the algebraic numbers are countable — were anticipated by Dedekind. Historians are now examining those letters and assessing how credit should be apportioned between the two mathematicians. It appears clear that Dedekind had important insights into that part of the argument, which Cantor incorporated into his 1874 article without acknowledgment — an omission that, in light of these letters, he obviously should have avoided.
With that context established, I would like to turn next to some variations of Cantor's argument and certain special cases, as we continue exploring the further aspects of Cantor's remarkable achievement concerning the uncountable infinite.
Consider what is now called Cantor space, the space of infinite binary sequences — sequences consisting entirely of zeros and ones. For example, there is the all-ones sequence, which is simply ones forever, and the all-zeros sequence, which is a different element. There is the alternating sequence one, zero, one, zero, one, zero, and so on, or its complement, or sequences with more complicated patterns. All of these are elements of Cantor space.
It is important to note that we are not interpreting such a sequence as a real number; this is a different kind of space, consisting purely of sequences. This space is commonly denoted 2ℕ, where the two indicates that each position takes a value of zero or one, and the ℕ indicates that the sequences are infinite. The claim is that Cantor space is uncountable — it is an uncountable infinity.
The structure of the argument is identical to that of Cantor's original diagonalization argument for the real numbers, but it is actually slightly easier to prove uncountability here, because binary sequences have unique representations. There is no subtle issue of non-unique representations as there is in the real number case.
We proceed by supposing towards a contradiction that Cantor space is countable. That would mean it is in one-to-one correspondence with the natural numbers, and therefore we could make a list s1, s2, s3, and so on, of all infinite binary sequences, such that every binary sequence appears somewhere on the list.
Given that list, we define a new binary sequence z by the following rule: the nth bit of z is the opposite of the nth bit of sn. Since each bit is either zero or one, taking the opposite simply means flipping it. This is a perfectly well-defined infinite binary sequence.
Now, z differs from s1 in the first bit, differs from s2 in the second bit, differs from s3 in the third bit, and so forth. Therefore z does not appear anywhere on the list — but z is a binary sequence, and we assumed every binary sequence appears on the list. This is a contradiction. The assumption that Cantor space was countable must therefore be false, and we conclude that Cantor space is an uncountable set.
Let me explain how the result on Cantor space relates to another uncountability result: the uncountability of the power set of the natural numbers. Recall that the power set of a set is the collection of all its subsets, so the power set of the natural numbers is the set of all A such that A is a subset of the natural numbers. This includes the full set of natural numbers, the empty set, the set of even numbers, the set of odd numbers, the primes, the composites, and so on — all such sets belong to the power set.
The key observation is that there is a natural one-to-one correspondence between Cantor space — the space of infinite binary sequences — and the power set of the natural numbers. Given any subset A of the natural numbers, we can form its characteristic sequence sA, a sequence of zeros and ones in which the nth bit is one if and only if n belongs to A. For example, a zero in position zero indicates that zero is not in A, a one in position one indicates that one is in A, and so forth. This encodes the complete membership pattern of A as a binary sequence.
Conversely, given any infinite binary sequence, we can recover a subset of the natural numbers by taking the set of indices at which ones occur. These two operations are inverses of each other, establishing a genuine one-to-one correspondence between Cantor space and the power set of the natural numbers. Since we have already proved that Cantor space is uncountable, it follows immediately that the power set of the natural numbers is uncountable as well, the two sets being of exactly the same size.
In fact, we can go further and show that Cantor space, the power set of the natural numbers, and the set of real numbers are all equinumerous — they all have exactly the same cardinality. To see that Cantor space is no larger than the reals, observe that any infinite binary sequence can be interpreted as a real number by placing a decimal point before the sequence of bits and reading them as a decimal expansion. This gives a one-to-one map from Cantor space into the reals, showing that the reals are at least as large as Cantor space.
For the other direction, given any real number we can associate to it its Dedekind cut: the set of all rational numbers smaller than it. This association is one-to-one, embedding the real numbers into the power set of the rationals. Since the set of rational numbers is equinumerous with the natural numbers, the power set of the rationals is equinumerous with the power set of the natural numbers. We therefore have injections in both directions: Cantor space injects into the reals, and the reals inject into something equinumerous with Cantor space.
To conclude that all these sets are equinumerous, we appeal to the Cantor–Schroeder–Bernstein theorem, discussed in another lecture. That theorem states that if each of two sets injects into the other — that is, each is at least as large as the other in the sense of one-to-one correspondences — then the two sets are in fact equinumerous. Applying this here, we conclude that Cantor space, the power set of the natural numbers, and the set of real numbers all have exactly the same cardinality.
What I would like to do now is generalize this result. We proved that the power set of the natural numbers is an uncountable set. Cantor also proved a vast generalization of this idea: for any set X, the set X is strictly smaller than its power set. The power set of X is the set of all subsets of X. The claim is that if you have any set whatsoever and you want a bigger set, a bigger infinity, you simply take the power set, and that will be a strictly larger infinity.
Let us give the proof. It is very similar to the argument we just gave for Cantor space, though a little more abstract. First, we observe that there are always at least as many subsets of X as there are elements of X. This is because for each element a in X, we can form the singleton {a}, the subset whose only member is a. Different elements yield different singletons, so this gives a one-to-one correspondence between elements and a collection of subsets. The theorem asserts something stronger: the power set is a strictly larger infinity.
One might be tempted to argue that the power set is strictly larger simply because, beyond the singletons, there are additional subsets — doubletons, the whole set, the empty set, and so on. But that reasoning is fallacious, and it is precisely the fallacy involved in Galileo's paradox. To say one set is strictly larger than another means there is no one-to-one correspondence between them — not merely that one set is equinumerous with a proper subset of the other.
To prove the theorem, we suppose towards a contradiction that X is equinumerous with its power set. That is, we suppose there exists a one-to-one correspondence between the elements of X and the subsets of X, so that every subset is named after some element. Concretely, for each element a in X, we have an associated subset Xa, and every subset of X arises as Xa for some a.
Given this naming scheme, we define the diagonal set D to be the set of all elements a in X such that a is not a member of Xa. This is a perfectly well-defined subset of X. Notice that some elements may belong to their associated subset — for instance, the element paired with the full set X is certainly a member of that set — while others do not, such as any element paired with the empty set. The diagonal set D collects precisely those elements that fall into the latter category.
The key observation is this: for any element a, we have a ∈ D if and only if a ∉ Xa. It follows immediately that D cannot equal Xa for any a, because D and Xa give opposite answers to the question of whether a is a member. This is a single point of disagreement, which is enough to make them different sets. We call D the diagonal set because this construction — asking whether the set associated with a disagrees with D at the position a — is an abstraction of the same diagonal idea Cantor used with the real numbers, where one examines the n-th digit of the n-th real number.
To summarize the argument: we supposed towards a contradiction that there are exactly as many subsets of X as elements of X, meaning we have a one-to-one correspondence — a naming scheme — in which every subset is attached to some element. From that naming scheme we constructed the diagonal subset D, consisting of all elements not belonging to their own associated set. We then observed that D cannot be attached to any element, contradicting the assumption that every subset is named. Therefore, no such one-to-one correspondence can exist, and the power set of X is strictly larger than X.
We can make some deductions from this general fact. Starting with the natural numbers, we can produce a bigger infinity by taking the power set of the natural numbers, which is equinumerous with the collection of binary sequences and also equinumerous with the set of real numbers. But this is itself a perfectly good set, and it has a power set — the set of sets of natural numbers — which is strictly smaller than the power set of the power set of the natural numbers. For any set, its power set is a strictly bigger infinity, so now we have three distinct infinities: the countable infinity, the size of the continuum, and an even larger uncountable infinity.
Of course, we can iterate this process. Taking the power set again, and again, and again, we obtain more and more infinities, and we see that there are infinitely many different uncountable infinities, each strictly larger than the last. One might then ask: how many different infinities are there altogether? A natural first answer is that there are infinitely many, but the question is which infinity — because, as it turns out, the list produced by iterating the power set operation only countably many times yields only countably many different infinities, which is not very impressive.
We can do better. To produce an infinite set larger than all of those infinities, we simply take the union, over every natural number n, of the n-fold iteration of the power set of the natural numbers. This union is at least as large as each set in the sequence, and since each successive set is strictly larger than the previous one, the union is strictly larger than any single member of the sequence. We can therefore continue the list transfinitely: beyond this union, its power set is strictly bigger, the power set of that is strictly bigger still, and so on.
Crucially, this process can be iterated through all the ordinals. Whenever we reach a limit stage, we take the union of all the sets produced so far, obtaining a set larger than anything in the sequence up to that point, and then continue. The conclusion is that the number of different infinities is larger than any one of them.
There is an interesting foundational point lurking in this argument. In the Zermelo axiomatization of set theory — first proposed in 1904 and refined in 1908 — one cannot actually prove the claim just made. Zermelo set theory is not strong enough to establish that there are uncountably many different infinities; indeed, it is known to be consistent with Zermelo set theory that there are only countably many infinities altogether. However, the slightly stronger system known as Zermelo–Fraenkel set theory adds the Replacement Axiom, and that is precisely what the argument above requires. The ability to collect the entire sequence of iterated power sets and form their union depends essentially on Replacement. In ZFC, we can prove that the number of infinities exceeds any given infinity, whereas Zermelo set theory alone is too weak to establish this, and it remains consistent there that only countably many infinities exist.
Let me offer some allegorical accounts of Cantorian logic on countable infinity. This is an anthropomorphic way of understanding the argument that I find helpful. As general advice to students, I often recommend imagining that the mathematical objects you are trying to understand are people — perhaps people in tension, cooperating, or playing a game. When you anthropomorphize your mathematical arguments, you can often gain genuine insight into their nature.
The first claim is this: for any set of people, however large — even infinitely large — there are more committees than people. What is a committee? A committee is simply a set of people. There is the universal committee, on which everyone sits (arguably the worst committee), and there is the empty committee, on which no one sits (arguably the best). There are also one-person committees, two-person committees, three-person committees, and so on. The claim is that the collection of all logically possible committees cannot be placed in one-to-one correspondence with the people themselves.
There are at least as many committees as people, since for every person there is the one-person committee consisting of that person alone, giving a one-to-one correspondence between people and some of the committees. But the mere existence of additional committees — such as the empty committee — does not by itself prove there are more committees than people; that would be committing the kind of error Galileo's paradox warns us about. Instead, we must show that no one-to-one correspondence between committees and people is possible.
Suppose, toward contradiction, that we could assign every committee to a distinct person in a way that constitutes a one-to-one correspondence. In effect, we are naming every committee after a person. Note that the person a committee is named after may or may not be a member of that committee. The person named by the universal committee must be on it, since everyone is. The person named by the empty committee cannot be on it, since no one is. So sometimes a person is on the committee named after them, and sometimes they are not.
Now consider the collection of all people who are not on the committee named after them. Call this the diagonal committee. It is a perfectly legitimate committee, so it must be named after someone; call that person Danielle. We now ask: is Danielle on the diagonal committee? She is on the diagonal committee if and only if she is not on the committee named after her — but the committee named after her is the diagonal committee. Therefore, she is on it if and only if she is not on it. This is a contradiction.
That argument is identical in logical structure to the proof that the power set of any set is strictly larger than the set itself. There can be no one-to-one correspondence between the subsets of a set and the elements of that set — or, in our allegory, between committees and people.
Let me give another version of this argument, suggested by one of my Oxford students. The claim is that there are more fruit salads than fruits. Suppose you have a collection of fruits — perhaps infinitely many distinct fruits. A fruit salad is simply a specification of which fruits it contains. There is the salad consisting only of strawberries, the salad of apples, grapes, and pears, and so forth. There is also the empty salad — excellent for dieting — and the universal salad containing every fruit. We are considering all logically possible fruit salads that can be formed from the available fruits, and the claim is that there are strictly more such salads than there are fruits.
Suppose toward contradiction that the number of possible fruit salads equals the number of fruits, so that there exists a one-to-one correspondence between them. This correspondence would give us a naming scheme: every fruit salad is named after a fruit. As before, the fruit a salad is named after may or may not be an ingredient in it. The universal salad must contain the fruit it is named after, since it contains every fruit. The empty salad cannot contain the fruit it is named after, since it contains nothing. So the naming is inconsistent in this respect across different salads.
Now form the diagonal fruit salad, consisting of all fruits that are not in the fruit salad named after them. This is a perfectly good fruit salad, so it must be named after some fruit; suppose it is named after durian. We ask: is durian in the diagonal salad? If durian is in the diagonal salad, then it is in the salad named after it, and so by the definition of the diagonal salad it should not be in it — a contradiction. If durian is not in the diagonal salad, then it is not in the salad named after it, and so by the definition of the diagonal salad it should be in it — again a contradiction. Either way we reach a contradiction, so no such one-to-one correspondence can exist.
Therefore, there are always more fruit salads than fruits, more committees than people, more subsets than elements. These are all the same argument, expressed in different allegorical terms, each illuminating the same underlying logic.
Let me discuss a certain issue that Bertrand Russell arrived at in the beginning of the twentieth century: the Russell Paradox. It concerns a principle in set theory known as the general comprehension principle. The general comprehension principle states that for any property φ, we can form the set consisting of all objects that have that property. If you have a property, you can make the set of all things that instantiate it. For example, the set of all elephants is a set, because being an elephant is a property; the set of all even numbers is a set; the set of all prime numbers is a set; the set of all functions from the reals to the integers is a set. For any property whatsoever, you can collect all things with that property into a set — that is what the general comprehension principle asserts.
The historically fascinating situation is that, at the end of the nineteenth century, Gottlob Frege was working on a monumental treatise advancing his program of logicism, which aimed to reduce all of mathematics to logic. He wanted to identify the most fundamental logical principles sufficient to develop all of mathematics, reducing every mathematical claim, at bottom, to logic. Built into his system was the assumption that the general comprehension principle is correct. He did not state it explicitly as a separate axiom, but it was woven throughout: for any property, Frege could form a term representing the set of all instances of that property.
Bertrand Russell, examining this work, noticed a serious problem. His observation was simple and devastating: the general comprehension principle is false. It is not merely imprecise or in need of refinement — it is logically contradictory, and Russell found a very easy refutation of it. Suppose the general comprehension principle is correct. Then we may form the following set: let R be the set of all sets X such that X is not a member of itself. Being non-self-membered is a perfectly ordinary property. The set of all elephants is not itself an elephant, so it is not a member of itself; the set of people in this room is not a person, so it is not a member of itself. Most sets have this property — it is quite a banal one.
Russell's point is that being non-self-membered is a perfectly good property, so by general comprehension we may form R, the set of all X such that X is not a member of X. Now simply ask: is R a member of itself? Since R is a set, it falls under the membership condition precisely when it satisfies that condition — that is, R is a member of R if and only if R is not a member of R. That is a contradiction. The argument shows, in essentially one line, that the general comprehension principle is contradictory: if it were correct, R would be a set, but R cannot be a set without contradiction.
If you reflect on Russell's argument, you may recognize it as a diagonal argument — the condition "X is not a member of X" is exactly the kind of self-referential diagonal move that Cantor used, both in his diagonal proof about real numbers and in his power-set argument. Russell himself mentions Cantor in the letter he wrote to Frege announcing the problem. He wrote to Frege and pointed out that there appeared to be a difficulty with his system, and gave what we now call the Russell argument.
Frege had poured years of work into this monumental treatise, and Russell's argument completely undercut the system he had developed. It was not a minor flaw, because Frege was using general comprehension throughout — it was woven into everything he did — and so the refutation was utterly devastating. To his credit, Frege was able to add an epilogue to the volume, in which he wrote: "Hardly anything more unwelcome can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished. This was the position into which I was put by a letter from Mr. Bertrand Russell, as the printing of this volume was nearing completion." Frege acknowledged the full seriousness of Russell's objection, and it is now widely regarded as a definitive refutation of the general comprehension principle.
To my way of thinking, the general comprehension principle is simply a logical fallacy — comparable to denying the antecedent or any of the other logical fallacies one might encounter. It has a one-line refutation, and we should regard it as a naive mistake, set it aside, and move on to the modified forms that are acceptable. One such modification is the axiom of separation, which appears among the axioms of the Zermelo–Fraenkel axiomatization of set theory. The axiom of separation is similar to general comprehension, but with a crucial restriction: given an already-existing set and a property, the collection of elements of that set satisfying the property is itself a set. You must start with a set and use the property to carve out a subset of it. With that modification the principle seems entirely acceptable, and Russell's argument no longer applies.
Let me continue with a few more allegorical accounts of Cantor's argument, or rather versions of Russell's argument. One should think of the Russell argument and the various Cantor arguments we have discussed as all using the same underlying logic.
Imagine a town with a barber who lives in that town. The barber shaves all and only the men in town who do not shave themselves. Some men shave themselves, and the barber has no need to shave them; he shaves precisely those who do not shave themselves. The question to ask is: does the barber shave himself? If he does not shave himself, then he should, because he shaves all and only those who do not shave themselves. But if he does shave himself, then he should not, because he shaves all and only those who do not. Either way, we reach a contradiction.
There cannot be such a town with such a barber, because the situation is contradictory — in exactly the same way that the Russell set is contradictory. One cannot have a set of all sets that are not members of themselves, because that set would be a member of itself if and only if it were not. The barber who shaves all and only those who do not shave themselves can neither shave himself nor refrain from doing so without contradiction.
There is also a related example: the barista paradox. Consider a barista who makes coffee for all and only those who do not make coffee for themselves. Some people do not make their own coffee and so receive it from the barista; others make their own coffee and therefore do not. But then the question is, of course, whether the barista makes coffee for herself. If she does, then she should not, because she serves all and only those who do not make coffee for themselves. But if she does not, then she should. It is exactly the same logic.
I hope you have enjoyed these examples and this exploration of uncountable infinity. It has been a great pleasure. Thank you.