Audio · 2025-12-31 · 12 moments

#488 – Infinity, Paradoxes that Broke Mathematics, Gödel Incompleteness & the Multiverse – Joel David Hamkins

Joel David Hamkins is a mathematician and philosopher specializing in set theory, the foundations of mathematics, and the nature of infinity, and he’s the #1 highest-rated user on MathOverflow. He is also the author of several books, including Proof and the Art of Mathematics and Lectures on the Philosophy of Mathematics. And he has a great blog called Infinitely More. Thank you for listening ❤ Check out our sponsors: https://lexfridman.com/sponsors/ep488-sc See below for timestamps, transcrip ✦ AI generated

Apple Podcasts ↗

GUEST Joel David Hamkins

timeline · colored by role

Claim◆

The tension between the Cantor-Hume principle (one-to-one correspondence determines size) and Euclid's principle (the whole is greater than the part) was not fully resolved until Cantor, who showed that infinite sets can violate Euclid's principle and that there are different sizes of infinity.

Hamkins explains that the ancient tension between two principles of size—Cantor-Hume (equinumerosity via one-to-one correspondence) and Euclid's (whole greater than part)—was unresolved until Cantor showed infinite sets can be equinumerous with proper subsets, and then proved there are strictly larger infinities like the uncountable reals.

transcript

Joel David Hamkins: And the tension between the Cantor-Hume principle and what could be called Euclid's principle, which is that the whole is always greater than the part, which is a principle that Euclid appealed to in The Elements... And so what Galileo was troubled by was this tension between what we call the Cantor-Hume principle and Euclid's principle. And it really wasn't fully resolved, I think, until Cantor. He's the one who really explained so clearly about these different sizes of infinity and so on in a way that was so compelling. And so he exhibited two different infinite sets and proved that they're not equinumerous. They can't be put into one-to-one correspondence. And it's traditional to talk about the uncountability of the real numbers. So Cantor's big result was that the set of all real numbers is an uncountable set.

Context

The historical tension between the Cantor-Hume principle (sets are equinumerous when in one-to-one correspondence) and Euclid's principle (the whole is always greater than the part) was not fully resolved until Cantor.

For centuries, mathematicians were troubled by the conflict between two principles: that a one-to-one correspondence implies equal size, and that the whole must be greater than its part. Galileo observed this tension with perfect squares and line segments, but couldn't resolve it. Cantor's work finally provided a coherent framework.

transcript

Joel David Hamkins: Galileo observed that the perfect squares can be put into a one-to-one correspondence with all of the numbers. I mean, we just did it. I associated every number with its square. And so it seems like on the basis of this one-to-one correspondence, that there should be exactly the same number of squares, perfect squares, as there are numbers. And yet, there's all the gaps in between the perfect squares, right? And this suggests that there should be fewer perfect squares, more numbers than squares because the numbers include all the squares plus a lot more in between them, right? And Galileo was quite troubled by this observation because he took it to cause a kind of incoherence in the comparison of infinite quantities. [...] The tension between the Cantor-Hume principle and what could be called Euclid's principle, which is that the whole is always greater than the part, which is a principle that Euclid appealed to in The Elements. [...] And it really wasn't fully resolved, I think, until Cantor.

Example◆

Hilbert's Hotel demonstrates that a countably infinite set can accommodate additional infinities — adding one, finitely many, or even countably infinitely many new guests — without growing in cardinality, illustrating the counterintuitive nature of countable infinity.

Using the famous Hilbert's Hotel thought experiment — a fully occupied hotel with infinitely many rooms — Hamkins shows how the manager can always free up rooms by shifting guests, whether one new guest arrives, a bus with infinitely many passengers, or a train with infinitely many cars each holding infinitely many passengers.

transcript

Joel David Hamkins: Hilbert's Hotel is a hotel with infinitely many rooms. [...] It's completely full. There's a person occupying room N for every N. But meanwhile, a new guest comes up to the desk and wants a room. [...] The manager sent a message up to all the current occupants and told every person, hey, can you move up one room, please? So the person in room 5 would move to room 6, and the person in room 6 would move to room 7, and so on, and everyone moved at the same time. [...] the bottom room, room 0, becomes available, of course, and so he can put the new guest in that room. So even when you have infinitely many things, then the new guest can be accommodated. [...] On the following weekend, a giant bus pulled up, Hilbert's bus. And Hilbert's bus has, of course, infinitely many seats. [...] I'll ask you, can you tell me, what is your idea about how to fit them all in the hotel, everyone on the bus and also the current occupants? [Lex: You separate the hotel into even and odd rooms] That's exactly right. If you just tell all the current guests to double their room number, so in room N, you move to room 2 times N. [...] And so all the odd rooms become empty that way, and now we can put the bus occupants into the odd-numbered rooms.

Claim◆

Some infinities are larger than others, and Cantor's diagonal argument proves that the set of real numbers is strictly larger than the set of natural numbers.

Cantor's diagonal argument proves the real numbers are uncountably infinite — strictly larger than the countable infinity of the natural numbers — by constructing a real number that differs from every entry in any putative enumeration.

transcript

Joel David Hamkins: Cantor wants to prove that the infinity of the real numbers is different and strictly larger than the infinity of the natural numbers. [...] Suppose that the real numbers can be put into one-to-one correspondence with the natural numbers. So therefore, for every natural number n, we have a real number, let's call it R sub n. R sub n is the nth real number on the list. [...] I'm going to define the number z, and it's going to be the integer part is going to be a 0, and then I'm going to put a decimal place, and then I'm going to start specifying the digits of this number Z. D1, D2, D3, and so on. And what I'm going to make sure is that the nth digit after the decimal point of Z is different from the nth digit of the nth number on the list. [...] But now it follows that Z is not on the list because Z is different from R1 because, well, the first digit after the decimal point of Z is different from the first digit of R1 after the decimal point. That's exactly how we built it. And the 2nd digit of Z is different from the 2nd digit of R2 and so on. The nth digit of Z is different from the nth digit of R sub n for every n. So therefore, Z is not equal to any of these numbers R sub n.

explains mechanism · 1extends · 2gives example · 1provides context · 3

Mechanism

A set is countable if it fits into Hilbert's Hotel, and countably many countable sets put together still form only a countable infinity—a strong violation of Euclid's principle.

Using Hilbert's Hotel (bus, train), Hamkins shows that the union of countably many countable sets remains countable, demonstrating that adding infinitely many infinities together does not yield a larger infinity—a deep violation of the principle that the whole exceeds the part.

transcript

Joel David Hamkins: A set is countable if it fits into Hilbert's Hotel, because Hilbert's Hotel basically is the set of natural numbers in terms of the room numbers. So to be equinumerous with a set of natural numbers is just the same thing, is to fit into Hilbert's Hotel. And so what we've shown is that if you have two countably infinite sets, then their union is also countably infinite. If you put them together and form a new set with all of the elements of either of them, then that union set is still only countably infinite. It didn't get bigger. And that's a remarkable property for a notion of infinity to have, I suppose... We've proved that if you have countably many countable sets, then the union of those sets, putting all those sets together into one giant set, is still countable... which is a strong instance, a strong violation of Euclid's principle once again, right?

Mechanism

Cantor's power set theorem — that for any set, its power set is strictly larger — is the general form of the argument that there are infinitely many sizes of infinity, and it can be understood through the intuitive metaphor that there are more committees than people.

Cantor proved that the power set of any set is strictly larger than the original set. Hamkins anthropomorphizes this: for any collection of people, there are more possible committees (subsets) than there are people. The proof uses the same diagonal logic as the real numbers argument and Russell's paradox.

transcript

Joel David Hamkins: Cantor actually proved a much more general fact, namely that for any set whatsoever, the power set of that set is a strictly larger set. [...] Suppose that X and the power set of X have the same size. So that means we can associate to every individual of X a subset. And so now let me define a new set. Let's call it D. And D is the subset of X that contains all the individuals that are not in their set. [...] But that's a perfectly good subset. And so because of the equinumerosity, it would have to be attached to a particular individual. But let's call that person [...] Diana. And now we ask, is Diana an element of D or not? But if Diana is an element of D, then she is in her set. So she shouldn't be, because the set D was the set of individuals that are not in their set. So if Diana is in D, then she shouldn't be. But if she isn't in D, then she wouldn't be in her set, and so she should be in D. That's a contradiction. So therefore, the number of subsets is always greater than the number of elements for any set.

Anecdote

Russell's paradox — that the set of all sets not containing themselves leads to a contradiction — devastated Frege's logicist project just as his magnum opus was going to press, because it showed that his general comprehension principle (any property defines a set) is inconsistent.

Hamkins recounts the story of Russell's letter to Frege, which revealed that Frege's foundational principle — that for any property you can form the set of objects with that property — leads directly to a contradiction via the set of all sets not members of themselves. This arrived just as Frege's life's work was at the publisher.

transcript

Joel David Hamkins: Before that time, Frege was working on his monumental work, undertaking, implementing the philosophy of logicism, which is the attempt to reduce all of mathematics to logic. [...] Those principles happened to imply that for any property whatsoever, you could form the set of objects with that property. This is known as the general comprehension principle. And Russell wrote him a letter when he observed the work in progress. that there was this problem, because if you accept the principle that for any property whatsoever, you can make the set of objects with that property, then you could form the set of all sets that are not members of themselves. That's just an instance of the general comprehension principle. But the set of all sets that aren't elements of themselves can't be a set, because if it were, then it would be an element of itself if and only if it's not a member of itself, and that's a contradiction. [...] It's completely devastating. I mean, it must have been such a horrible situation for Frege to be placed in because he's finished this monumental work, years of his life dedicated to this. And Russell finds this one line proof of a contradiction in the fundamental principles of the thesis that completely destroys the whole system.

Claim

The ZFC axioms serve as the foundational framework for modern mathematics, and when understood as fundamentally logical principles of abstract set formation, they can be seen as a successful fulfillment of the logicist program.

Hamkins argues that ZFC — Zermelo-Fraenkel set theory with the axiom of choice — succeeds as a foundation for mathematics. He takes the controversial view that its axioms, including the axiom of infinity and the axiom of choice, are fundamentally logical in character, making ZFC a completion of Frege's logicist dream.

transcript

Joel David Hamkins: The project of logicism did not die with Frege, and it was continued. [...] My view of the matter is that really we should view the main goals of logicism are basically completely fulfilled in the rise of set theoretic foundationalism. I mean, when you view ZFC as the foundation of mathematics, and in my view, the principles of ZFC are fundamentally logical in character, including the axiom of choice, as I mentioned, as a principle of logic. This is a highly disputed point of view, though, because a lot of people take even the axiom of infinity as mathematical, inherently mathematical and not logical and so on. But I think if you adopt the view that the principles of ZFC have to do with the principles of abstract set formation, which is fundamentally logical in character, then it's complete success for logicism.

Mechanism◆

Cantor's diagonal argument proves the real numbers are uncountable: given any list of reals, you can construct a new real not on the list by making its nth digit differ from the nth digit of the nth number.

Hamkins walks through Cantor's diagonal argument: assuming a one-to-one correspondence between naturals and reals, construct a new real whose nth decimal digit differs from the nth digit of the nth real on the list, producing a contradiction because the new real is omitted.

transcript

Joel David Hamkins: So suppose that the real numbers can be put into one-to-one correspondence with the natural numbers. So therefore, for every natural number n, we have a real number, let's call it R sub n. R sub n is the nth real number on the list... And now I'm going to define the number z... D1, D2, D3, and so on. And what I'm going to make sure is that the nth digit after the decimal point of Z is different from the nth digit of the nth number on the list... I'm going to make it different in a way that I'm never using the digits 0 or 9... But now it follows that Z is not on the list because Z is different from R1 because the first digit after the decimal point of Z is different from the first digit of R1 after the decimal point... So therefore, Z is not equal to any of these numbers R sub n. But that's a contradiction because we had assumed that we had every real number on the list, but yet here is a real number Z that's not on the list.

Context

The axiom of choice is a natural, almost logical principle—that for any collection of non-empty sets there exists a choice function—but its non-constructive character makes it controversial, especially when contrasted with the well-ordering theorem it implies.

Hamkins describes the axiom of choice as an obviously desirable principle that does not require a constructive rule—the mathematical ontology is rich enough to contain choice functions even when we cannot specify them. However, the well-ordering theorem it proved was so controversial it forced Zermelo to axiomatize set theory.

transcript

Joel David Hamkins: On the one hand, I mean, the axiom choice principle is completely obvious that we want this to be true, that it is true. I mean, a lot of people take it as a law of logic. If you have a bunch of sets, then there's a way of picking an element from each of them. There's a function. If I have a bunch of sets, then there's a function that when you apply it to any one of those sets, gives you an element of that set. It's a completely natural principle... The difficulty is that when you can't specify a rule or a procedure by which you're making choices, then it's difficult to say what the function is that you're asserting exists... But if you have a constructive attitude about the nature of mathematics, and you think that mathematical claims maybe are only warranted when you can provide an explicit procedure for producing the mathematical objects that you're dealing with, then you're probably going to want to deny the axiom of choice and maybe much more.

Claim

The diagonalization idea—abstracted from Cantor's proof that the power set of any set is strictly larger than the set itself—is the core of Russell's paradox, the halting problem, the recursion theorem, and almost every major result in mathematical logic.

Hamkins explains that Cantor proved a more general result: for any set X, the power set of X is strictly larger than X. This same diagonal logic—applied to committees, fruit salads, or sets that are not members of themselves—underlies Russell's paradox, the halting problem, and the recursion theorem.

transcript

Joel David Hamkins: Cantor actually proved a much more general fact, namely that for any set whatsoever, the power set of that set is a strictly larger set. So the power set is the set containing all the subsets of the original set. So if you have a set, and you look at the collection of all of its subsets, then Cantor proves that this is a bigger set... Suppose that X and the power set of X have the same size. So that means we can associate to every individual of X a subset. And so now let me define a new set... D is the subset of X that contains all the individuals that are not in their set... But that's a perfectly good subset. And so because of the equinumerosity, it would have to be attached to a particular individual. But let's call that person... Diana. And now we ask, is Diana an element of D or not? But if Diana is an element of D, then she is in her set. So she shouldn't be... But if she isn't in D, then she wouldn't be in her set, and so she should be in D. That's a contradiction. So therefore, the number of subsets is always greater than the number of elements for any set.

extends · 1

Context

Russell's paradox devastated Frege's logicist project—the principle that for any property you can form the set of objects with that property leads to a contradiction—and Hilbert's program responded by proposing to prove the consistency of strong set-theoretic mathematics using weak finitistic reasoning.

Hamkins recounts how Russell's one-line contradiction—the set of all sets not members of themselves—destroyed Frege's monumental logicist work at the moment of publication, and how Hilbert responded by proposing to keep strong set theory but prove its consistency from weak, finitistic principles.

transcript

Joel David Hamkins: Before that time, Frege was working on his monumental work... implementing the philosophy of logicism, which is the attempt to reduce all of mathematics to logic. And those principles happened to imply that for any property whatsoever, you could form the set of objects with that property... And Russell wrote him a letter when he observed the work in progress that there was this problem... It's basically one line proof of a contradiction in the fundamental principles of the thesis that completely destroys the whole system. And Frege had put in the appendix of his work a response to Russell's letter in which he explained what happened. And he wrote very gracefully, '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.'... Hilbert said, well, look, we have to fix this problem. We want to use the set theory foundations, but we want to do it in a way that is trustworthy and reliable... We're going to have this strong theory, this set theory that we want to be proving our theorems in. But I mean, on the one hand, we want it to be as strong as possible. We would like it to answer all the questions... But secondly, we want to combine that with, in a very weak, arithmetic, purely finitistic theory, we want to prove that the reasoning process of the strong theory is safe.

Highlight slides

Two Clashing Principles of Size✦ from: The tension between the Cantor-Hume principle (one-to-one correspondence determines size) and Euclid's principle (the whole is greater than the part) was not fully resolved until Cantor, who showed that infinite sets can violate Euclid's principle and that there are different sizes of infinity.Cantor's Resolution✦ from: The tension between the Cantor-Hume principle (one-to-one correspondence determines size) and Euclid's principle (the whole is greater than the part) was not fully resolved until Cantor, who showed that infinite sets can violate Euclid's principle and that there are different sizes of infinity.Hilbert's Hotel: Infinity Fits More Infinity✦ from: Hilbert's Hotel demonstrates that a countably infinite set can accommodate additional infinities — adding one, finitely many, or even countably infinitely many new guests — without growing in cardinality, illustrating the counterintuitive nature of countable infinity.Bus of Infinity: Doubling Makes Room✦ from: Hilbert's Hotel demonstrates that a countably infinite set can accommodate additional infinities — adding one, finitely many, or even countably infinitely many new guests — without growing in cardinality, illustrating the counterintuitive nature of countable infinity.The Claim: Unequal Infinities✦ from: Some infinities are larger than others, and Cantor's diagonal argument proves that the set of real numbers is strictly larger than the set of natural numbers.Cantor's Diagonal Argument — The Setup✦ from: Some infinities are larger than others, and Cantor's diagonal argument proves that the set of real numbers is strictly larger than the set of natural numbers.Why Z Is Not on the List✦ from: Some infinities are larger than others, and Cantor's diagonal argument proves that the set of real numbers is strictly larger than the set of natural numbers.Cantor's Diagonal Argument✦ from: Cantor's diagonal argument proves the real numbers are uncountable: given any list of reals, you can construct a new real not on the list by making its nth digit differ from the nth digit of the nth number.Contradiction Proves Uncountability✦ from: Cantor's diagonal argument proves the real numbers are uncountable: given any list of reals, you can construct a new real not on the list by making its nth digit differ from the nth digit of the nth number.