Kind: captions
Language: en
The following is a conversation with
Joel David Hamkins, a mathematician and
philosopher specializing in set theory,
the foundation of mathematics, and the
nature of infinity. He is the number one
highest rated user on math overflow,
which I think is a legendary
accomplishment. Math overflow, by the
way, is like Stack Overflow, but for
research mathematicians.
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 infinitely more.xyz.
This is a super technical and super fun
conversation about the foundation of
modern mathematics and some mindbending
ideas about infinity, nature of reality,
truth, and the mathematical paradoxes
that challenged some of the greatest
minds of the 20th century.
I have been hiding from the world a bit,
reading, thinking, writing,
soulsearching, as we all do every once
in a while, but mostly just deeply
focused on work and preparing mentally
for some challenging travel I plan to uh
take on in the new year. Through all of
it, a recurring thought comes to me. how
damn lucky I am to be alive and to get
to experience so much love from folks
across the world.
I want to take this moment to say thank
you from the bottom of my heart for
everything, for your support, for the
many amazing conversations I've had with
people across the world. I got uh a
little bit of hate and a whole lot of
love, and I wouldn't have it uh any
other way. I'm grateful for all of it.
This is the Lex Freedman podcast. To
support it, please check out our
sponsors in the description where you
can also find ways to contact me, ask
questions,
give feedback, and so on. And now, dear
friends, here's Joe David Hamkins.
Some infinities are bigger than others.
This idea from Caner at the end of the
19th century I think it's fair to say
broke mathematics before rebuilding it
and uh I also read that this was a
devastating and transformative discovery
for several reasons. So one it created a
theological crisis because infinity is
associated with God. How could there be
multiple infinities and also Caner was
deeply religious himself. Second there
was a kind of mathematical civil war.
The leading German mathematician
chronicer called Caner a corruptor of
youth and uh tried to block his career.
Third, many fascinating paradoxes
emerged from this uh like Russell's
paradox about the set of all sets that
don't contain themselves and uh those
threatened to make all of mathematics
inconsistent. And finally on the
psychological side, on the personal
side, Caner's own breakdown. He
literally went mad spending his final
years in and out of uh sanatoriums
obsessed with proving the continuum
hypothesis. So laying that all out on
the table uh can you explain the idea of
infinity that uh some infinities are
larger than others and why was this so
transformative to mathematics?
>> Well, that's a really great question.
I would want to start talking about
infinity and telling the story much
earlier than caner actually because I
mean you can go all the way back to
ancient Greek times when Aristotle
emphasized the potential aspect of
infinity as opposed to the impossibility
according to him of achieving an actual
infinity and Archimedes method of
exhaustion where he is trying to
understand the the area of a region by
carving it into more and more triangles
say and sort of exhausting the area and
thereby understanding the total area in
terms of the sum of the areas of the
pieces that he put into it and it
proceeded on this kind of potential
under this potentialist understanding of
infinity for for hundreds of years
thousands of years. Uh almost all
mathematicians were potentialists only
and thought that it was incoherent to
speak of an actual infinity at all. Um,
Galileo is an extremely
prominent exception to this though he
argued against this sort of potentialist
orthodoxy in the dialogue of tunu
sciences. Really lovely account there
that he gave. Um, and that the in many
ways Galileo was anticipating Kandra's
developments except he couldn't quite
push it all the way through and uh ended
up throwing up his hands in confusion
in in a sense. I mean, the Galileo
paradox is the idea or the observation
that if you think about the natural
numbers, I would start with zero, but I
think maybe he would start with one. The
numbers 1 2 3 4 and so on. And you think
about which of those numbers are perfect
squares. So 0 squar is zero and one
square is one and two squar is 4, 3
squar is 9, 16, 25 and so on. And
Galileo observed that the the perfect
squares can be put into a onetoone
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 and this
suggests that uh you know 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. Right? And another
example is if you take two line segments
of different lengths and you can imagine
drawing a kind of foliation a fan of
lines that connect them. So the end
points are matched from the shorter to
the longer segment and the midpoints are
matched and so on. So spreading out the
lines as you go and so every point on
the shorter line would be associated
with a a unique distinct point on the
longer line in a onetoone way. And so it
seems like the two line segments have
the same number of points on them
because of that even though the longer
one is longer. And so it makes again a
kind of confusion of our ideas about
infinity. And also with two circles, if
you just place them concentrically and
draw the rays from the center, then
every point on the smaller circle is
associated with a corresponding point on
the larger circle, you know, in a one to
one way. and and again that seems to
show that the smaller circle has the
same number of points on it as the
larger one precisely because they can be
put into this one to one correspondence.
Now of course the contemporary attitude
about this situation is that those two
infinities are are exactly the same and
that Galileo was right in those
observations about the equinosity and
the way we would talk about it now is
appeal to what uh what I call the caner
Hume principle or some people just call
it Hume's principle which is the idea
that if you have two collections whether
they're finite or infinite then we want
to say that those two collections have
the same size they're equinumerous
if and only if there's a onetoone
correspondence between those
collections. And so Galileo was
observing that line segments of
different lengths are equinumerous and
the perfect squares are equinumerous
with the whole all of the natural
numbers and and two any two circles are
equinumerous and so on and that the
tension between the kander Hume
principle and what could be called
Uklid's principle which is that the
whole is always greater than the part
which is a principle that Uklid appealed
to in in the elements. I mean many times
when he's calculating area and so on he
wants it's a kind of basic idea that if
something is just a part of another
thing then the the whole is greater than
the part and so what Galileo was
troubled by was this tension between
what we call the canerhume principle and
Uklid's principle
and it really wasn't fully resolved I
think until Caner 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 onetoone
correspondence
and it's traditional to talk about the
uncountability of the real numbers so
Kanto's big result was that the set of
all real numbers is an uncountable set
so maybe if we're going to talk about
countable sets then I would suggest that
We talk about Hilbert's hotel which
really makes that idea perfectly clear.
>> Yeah, let's talk about the Hilbert's
hotel.
>> Hilbert's hotel is a hotel with
infinitely many rooms. You know, each
room is a full floor suite. So there's
floor zero. I always start with zero
because for me the natural numbers start
with zero. Although that's maybe a point
of contention for some mathematicians.
The the other mathematicians are wrong.
>> Like a bunch of geo programmers. So
starting at zero is a wonderful place to
start.
>> Exactly. So there's floor 0, floor 1,
floor two or room 0 1 2 3 and so on just
like the natural numbers. So Hilbert's
hotel has a room for every natural
number
and 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. Can I have a
room, please? And the manager says,
"Hang on a second. Just give me a
moment." And you see, when the other
guests had checked in, they had to sign
an agreement with uh with the hotel that
maybe there would be some changing of
the rooms, you know, during the stay.
And so 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 five
would move to room six and the person in
room six would move to room seven and so
on. And everyone moved at the same time.
And of course, we never want to be
placing two different guests in the same
room and we want everyone to have their
own private room and but when you move
everyone up one room then the bottom
room room zero 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 and that's a
way of showing how the particular
infinity of the occupants of Hilbert's
hotel it violates Uklid's principle. I
mean, it exactly illustrates this idea
because adding one more element to a set
didn't make it larger because we can
still have a 1:1 correspondence between
the total new guests and the old guests
by the room number. Right?
>> So, to just uh say one more time, the
hotel is full. the hotel is full
>> and then you could still squeeze in one
more and that breaks the uh traditional
notion of mathematics and and breaks
people's brains about when they try to
uh think about infinity. I suppose this
is a property of infinity.
>> It's a property of infinity that
sometimes when you add an element to a
set it doesn't get larger. That's what
this example shows.
But one can go on with Hilbert for
example. Uh, I mean maybe the next day,
you know, 20 people show up all at once,
but we can easily do the same trick
again. Just move everybody up 20 rooms
and then we would have 20 empty rooms at
the bottom and those new 20 guests could
go in. But on the following weekend, a
giant bus pulled up Hilbert's bus. And
Hilbert's bus has, of course, infinitely
many seats. There's seat zero, seat one,
seat two, seat three, and so on. And so
one wants to uh you know all the people
on the bus want to check into the hotel
but the hotel is completely full. And so
what is the manager going to do? And
when I talk about Hbert's hotel in when
I teach Hilbert's hotel in in class I
always demand that the students provide
you know the explanation of of how to do
it.
>> So maybe I'll ask you can you tell me
yeah what is your idea about how to fit
them all in the hotel everyone on the
bus and also the current occupants. uh
you uh you separate the hotel into even
and odd rooms and you squeeze in the new
Hilbert bus people into the odd rooms
and uh the [clears throat] previous
occupants go into the even rooms.
>> That's exactly right. So I mean that's
the a very uh easy way to do it if you
just tell all the current guests to
double their room number. So in room n
you move to room 2 * n. So they're all
going to get their own private room, the
new room, and it will always be an even
number because 2 * n is always an even
number. And so all the odd rooms become
empty that way. And now we can put the
bus occupants into the oddnumbered
rooms.
>> And by doing so, you have now shoved in
an infinity into another infinity.
>> That's right. So what it really shows I
mean another way of thinking about it is
that well we can define that a set is
countable if it is equinumerous with a
set of natural numbers and and a kind of
easy way to understand what that's
saying in terms of Hilbert's hotel is
that a set is countable if it fits into
Hbert'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 as 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 uh a notion of
infinity to have, I suppose. But if you
thought that there was only one kind of
infinity, then it wouldn't be surprising
at all because if you take two infinite
sets and put them together, then it's
still infinite. And so if there were
only one kind of infinity, then it
shouldn't be surprising that the union
of two countable sets is countable.
>> So there's another way to push this a
bit harder. And that is when uh when
Hilbert's train arrives and Hilbert's
train has infinitely many train cars.
>> Mhm. And each train car has infinitely
many seats.
>> And so we have an infinity of infinities
of the train passengers together with
the current occupants of the hotel. And
everybody on the train wants to check
into Hilbert's hotel.
So the manager can again of course send
a message up to all the rooms uh telling
every person to double their room number
again. And so that will occupy all the
even-umbered rooms again and but free up
again the oddnumbered rooms. So somehow
we want to put the train passengers into
the oddnumbered rooms. And so well every
train passenger is on some car let's say
car C and seat S. So somehow we have to
take these two coordinates you know C
comma S the car number and the seat
number and produce from it an odd number
in a one to one way you know and that's
that's actually not very difficult. In
fact uh one can just use say an easy way
to do it is to just use the number 3 to
the C * 5 to the S
3 to the C 3 to the car number. So 3 * 3
* 3 you know the number of the car you
multiply three by itself the number of
the train car and then you multiply five
by itself the seat number times and then
you multiply those two numbers together
so 3 to the c * 5 to the s
that's always an odd number because the
prime factorization has only threes and
fives in it there's no two there so
therefore it's definitely an odd number
and it's always different because of the
uniqueness a prime factoriization. So
every number can be factored uniquely
into prime. So if you have a number of
that form, then you can just factor it
and that tells you the exponent on three
and the exponent on five. And so you
know exactly which person it was, which
car they came from and which seat they
came from.
>> And prime factorization is every single
number can be uh uh decomposed into the
atoms of mathematics which is the prime
numbers. You can multiply them together
to achieve that number. And that's prime
factorization. You're showing three and
five are both prime numbers odd. So
through this magical formula, you can uh
deal with this
train infinite number of cars with each
car having infinite number of seats.
>> Exactly. Right. 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. Yeah, cuz the the
train cars are each countable. Plus, the
current hotel, it's sort of like another
train car if you want to think about it
that way. The current occupants of the
hotel could, you know, have the same
number as as any of the train cars. So
putting countably many countable sets
together to make one big union set is
still countable. It's quite remarkable I
think. Um I mean when I first learned
this many many years ago I was
completely shocked by it and transfixed
by it. It was quite amazing to me that
this notion of countable infinity could
be closed under this process of
infinitely many infinities adding up
still to the very same infinity which is
a strong instance a strong violation of
Uklid's principle once again right so
the new set that we built is has many
more elements than the old set in the
sense that there's additional elements
but it doesn't have many more elements
in terms of its size because it's still
just to countable infinity and it fits
into Hbert's hotel.
>> Uh, have you been able to sort of
internalize a good intuition about
countable infinity? Cuz that is a pretty
weird thing that you can have a
countably infinite set of countably
infinite sets. You can shove it all in
and it still is countable infinite set.
>> Yeah, that's that's exactly right.
Right. I mean, I guess
of course when you when you work with
these notions that the the argument of
of Hilbert Sortell becomes kind of
clear. There's many many other ways to
talk about it too. For example,
let's think about say the the integer
lattice the grid of points that you get
by taking pairs of natural numbers say
so the the upper right quadrant of the
integer lattice. Yeah. So there's the,
you know, row 0, row one, row two, and
so on, column 0, column 1, column 2, and
so on. And each each row and column has
an countable infinity of points on it,
right?
So those dots, if you think about them
as dots, are really the same as the
train cars. If you think about each
column of in the in that integer
lattice, it's a countable infinity. It's
like one train car and then there's the
next train car next to it and then the
next column next to that the next train
car and so but if we think about it in
this grid manner then I can imagine a
kind of winding path winding through
these grid points like up and down the
diagonals winding back and forth. So I
start at the corner point and then I go
down up and to the left and then down
and to the right up and to the left down
and to the right and so on in such a way
that I'm going to hit every grid point
in on this path. So this gives me a way
of assigning room numbers to the points
because every every grid point is going
to be the nth point on that path for
some n
>> and that that gives a correspondence
between the grid points and the natural
numbers themselves. So it's a kind of
different picture. I mean before we used
this 3 to the C 5 * 5 to the S which is
a kind of you know overly arithmetic way
to think about it but there's a kind of
direct you know way to understand that
it's still a countable infinity when you
have countably many countable sets
because you can just start putting them
on this list and as long as you give
each of the infinite collections a
chance to add one more person to the
list then you're going to accommodate
everyone in any of the sets in one list.
Yeah, it's a really nice visual way to
think about it. You just zigzag your way
across the grid to make sure everybody's
included that gives you kind of an
algorithm for including everybody. So,
can you speak to the uncountable
infinities? So, what are the integers
and the real numbers and what is the
line that Caner was able to find?
>> So, maybe there's there's one more step
I want to insert before doing that which
is
>> the rational numbers. So, we did we did
pairs of natural numbers,
>> right? that that's the train car
basically. But maybe it's a little bit
informative to think about the rational
the fractions the set of fractions or
rational numbers because a lot of people
maybe have an expectation that maybe
this is a bigger infinity because the
rational numbers are are densely ordered
between any two fractions you can find
another fraction. Right? The average of
two fractions is another fraction.
[gasps]
And so so sometimes people it seems to
be a different character than um than
the integers which are discreetly
ordered right from every any integer
there's a next one and a previous one
and so on. But that's not true in the
rational numbers
and yet the rational numbers are also
still only accountable infinity. And the
the way to see that is actually it's
just exactly the same as Hilbert's train
again because every fraction consists of
two integers the numerator and the
denominator and so if I tell you two
natural numbers then you know what
fraction I'm talking about I mean plus
the sign issue I mean if it's positive
or negative but if you just think about
the positive fractions then you know you
have the numbers of the form p over q
where q is not zero. So you can still do
3 to the P * 5 to the Q. The same idea
works with the rational numbers. So this
is still a countable set. And you might
think, well, every every set is going to
be countable because there's only one
infinity. I mean, if that's a kind of
perspective maybe that you're um uh
adopting, but it's not true. And that's
the profound achievement that Caner made
is proving that the set of real numbers
is not a countable infinity. It's a
strictly larger infinity and therefore
there are uh there's more than one
concept of infinity more than one size
of infinity. So let's talk about the
real numbers. What are the real numbers?
Why do they break infinity? The
countable infinity
>> right?
>> Looking it up on perplexity.
Uh real numbers include all the numbers
that can be represented on the number
line encompassing both rational and
irrational numbers. We've spoken about
the rational numbers and the rational
numbers by the way are by definition the
numbers that can be represented as a
fraction of two integers. That's right.
So with the real numbers we have the
algebraic numbers. We have of course all
the rational numbers. The integers and
the rationals are all part of the real
number system. But then also we have the
algebraic numbers like the square root
of two or the cube root of five and so
on. Numbers that solve an algebraic
equation over the integers. Those are
known as algebraic numbers.
It was an open question for a long time
whether that was all of the um real
numbers or whether there would exist
numbers that are the transcendental
numbers. The transcendental numbers are
real numbers that are not algebraic
>> and we won't even go to the surreal
numbers about which you have a wonderful
blog post. We'll talk about that a
little bit later.
>> Oh great. So it was Louisville who first
proved that uh there are transcendental
numbers and he exhibited a very specific
number that's now known as the
Louisville constant which is a
transcendental number. Caner also
famously proved that there are many many
transcendental numbers. In fact it
follows from his argument on the
uncountability of the real numbers that
there are uncountably many
transcendental numbers. So most real
numbers are transcendental
>> and again going to perplexity
transcendental numbers are real or
complex numbers that are not the root of
any nonzero polomial with integer or
rational coefficients. This means they
cannot be expressed as solutions to
algebraic equations with integer
coefficients setting them apart from
algebraic numbers. That's right. So some
of the famous transcendental numbers
would include the number pi you know the
the uh 3.14159265
and so on. Uh so that's a transcendental
number also oilers's constant the e like
e to the x the exponential function.
>> So you could say that some of the
sexiest numbers in mathematics are all
transcendental numbers.
>> Absolutely. That's true. [laughter]
Yeah. Although you know I don't know
square of two is pretty
>> square. All right. So it depends. Let's
not beauty can be found in in all the
different kinds of sets. But yeah,
>> and if you have a kind of simplicity
attitude, then you know zero and one are
looking pretty good, too. So, and
they're definitely not.
>> Sorry to take that tangent, but what is
your favorite number? Do you have one?
>> Oh, gosh. You know,
>> is it zero?
>> Did you know there's a proof that every
number is interesting? [laughter]
You can prove it because
>> Yeah. What's that proof look like? How
do you even begin? I'm going to prove to
you that every natural number is
interesting.
>> Okay?
>> Yeah. I mean zero is interesting because
you know it's the additive identity,
right? That's pretty interesting. And
one is the multiplicative identity. So
when you multiply it by any other
number, you just get that number back,
right? And two is, you know, the the
first prime number that's super
interesting, right? And
>> okay so one can go on this way and and
give specific reasons but I want to
prove as a general principle that every
number is interesting and and this is
the proof.
>> Um suppose toward contradiction that
there were some boring numbers.
>> Okay.
>> Uh
>> but if if there was an uninteresting
number
>> Yes.
>> then there would have to be a smallest
uninteresting number.
>> Mhm. Yes. But that's a contradiction
because the smallest uninteresting
number is a super interesting graphology
to have. [laughter]
>> So therefore there cannot be good there
cannot be any boring numbers. I'm going
to have to try to find a hole in that
proof [laughter]
>> cuz there's a lot of big tin in the word
interesting. But yeah that's a be that's
beautiful. That doesn't say anything
about the transcendental numbers about
the real numbers. You just prove from
just for natural numbers.
>> Okay. Should we get back to Caner's
argument or
>> Sure. You you've masterfully avoided the
question. You basically said I love all
numbers.
>> Yeah, basically. Okay, that's what I my
>> back to Caner's argument. Let's go.
>> Okay. So, Caner wants to prove that the
infinity of the real numbers is
different and strictly larger than the
infinity of the natural numbers. So, the
natural numbers are the numbers that
start with zero and and add one
successively. So, 0 1 2 3 and so on. And
the real numbers as we said are the the
numbers that come from the number line
including all the integers and the
rationals and the algebraic numbers and
the transcendental numbers and all of
those numbers altogether. Now obviously
since the natural numbers are included
in the real numbers we know that the
real numbers are at least as large as
the natural numbers and so the claim
that we want to prove is that it's
strictly larger. So suppose that it
wasn't strictly larger. So that then
they would have the same size. But to
have the same size remember means by
definition that there's a 1 to1
correspondence between them. So we
suppose that the real numbers can be put
into one toone correspondence with the
natural numbers. So therefore for every
natural number n we have a real number.
Let's call it r subn.
R subn is the nth real number on the
list. Basically, our assumption allows
us to think of the real numbers as
having been placed on a list. R1, R2,
and so on. Okay. And now, now I'm going
to define the number Z and it's going to
be the integer part is going to be a
zero. And then I'm going to have put a
decimal place. And then I'm going to
start specifying the digits of this
number Z. [snorts] D1, D2, D3, and so.
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.
>> Okay. So, so to specify the nth digit of
Z, I go to the nth number on the list, R
subn, and I look at its nth digit after
the decimal point. And whatever that
digit is, I make sure that my digit is
different from it. Okay?
And then I want to do something a little
bit more and that is uh I'm going to
make it different in a way that I I'm
never using the digits zero or nine. I'm
just always using the the other digits
and not zero. There's a certain
technical reason to do that.
[sighs and gasps]
But the main thing is that I make the
digits of Z different in the nth place
from the nth digit of the nth number.
If you had ma if you had drawn out the
numbers uh on the original list R1, R2,
R3 and so on and you made it you know
and they were each filling a whole row
and you thought about the nth digit of
the nth number it would form a kind of
diagonal going down and to the right and
that for that reason this argument is
called the diagonal argument because
we're looking at the nth digit of the
nth number and those exist on a kind of
diagonal going down and we've made our
number D so that the nth digit of Z is
different from the nth digit of the nth
number.
But now it follows that Z is not on the
list because Z is different from R1
because
well the 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 second digit of Z is different
from the second digit of R2 and so on.
The nth digit of Z is different from the
nth digit of R subn for every N. So
therefore Z is not equal to any of these
numbers R subn and 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. Okay. And so
that's the main contradiction.
>> And so it's a kind of proof by
construction. Exactly. So given a list
of numbers Caner is proving it's
interesting that you say that actually
because there's a kind of philosophical
controversy that occurs as a uh uh in
connection with this observation about
whether Caner's construction is
constructive or not. Um given a list of
numbers, Caner gives us a specific means
of constructing a real number that's not
on the list is a way of thinking about
it.
There's this one aspect which I alluded
to earlier but some real numbers have
more than one decimal representation and
it causes this slight problem in the
argument. Um for example the number one
you can write it as 1.0000
forever but you can also write it as
0.999
forever. Those two those are two
different decimal representations of
exactly the same number. And then you
beautifully got rid of the zeros and the
nines. Therefore, we don't need to even
consider that. And the proof still
works.
>> Exactly. Because the only kind of case
where that phenomenon occurs is when the
number is eventually zero or eventually
nine. And so since our number Z never
had any zeros or nines in it, it wasn't
one of those numbers. And so actually in
those cases, we didn't need to do
anything special to diagonalize. Just
the mere fact that our number has a
unique representation already means that
it's not equal to those numbers. So
maybe it was controversial in Caner's
day more than 100 years ago, but I think
it's most commonly looked at today as
you know one of the initial main results
in set theory and it's profound and
amazing and insightful and the beginning
point of so many later arguments. And
this diagonalization idea has proved to
be an extremely fruitful proof method.
And almost every major result in
mathematical logic is using in an
abstract way the idea of
diagonalization. It was really um the
start of so many other observations that
uh were made including Russell's paradox
and the halting problem and the
recursion uh theorem and so many other
principles are using diagonalization uh
at their core. So
>> can we uh can we just step back a little
bit? This infinity crisis led to a kind
of uh rebuilding of mathematics. So uh
it would be nice if you lay out the
things it resulted in. So one is set
theory became the foundation of
mathematics. All mathematics could now
be built from sets giving math its first
truly rigorous foundation. The
exiomatization
of mathematics. The paradoxes forced
mathematicians to develop ZFC and other
aimatic systems and uh mathematical
logic emerged. Uh Geredo Touring and
others created entire new fields. So can
you uh explain what set theory is and uh
how does it serve as a foundation of
modern mathematics and maybe even the
foundation of truth?
>> That's a great question. Set theory
really has two roles that it's serving.
this kind of two ways that set theory
emerges. On the one hand, set theory is
the is its own subject of mathematics
which with its own problems and
questions and answers and proof methods.
And so really from this point of view,
set theory is about the transfinite
recursive constructions or wellfounded
definitions and constructions.
And those ideas have been enormously
fruitful and set theorists have looked
into them and developed uh so many ideas
coming out of that. But set theory has
also happened to serve in this other
foundational role. It's very common to
hear things said about set theory that
really aren't taking account of this
distinction between the two roles that
it's serving. It's its own subject, but
it's also serving as a foundation of
mathematics. So in its foundational
role, set theory provides a way to think
of a collection of things as one thing.
That's the the central idea of set
theory. A set is a collection of things,
but you think of the set itself as one
abstract thing. So when you form the set
of real numbers, then that is a set.
It's one thing. It's a set and it has
elements inside of it. So it's sort of
like a bag of objects. A set is kind of
like a bag of objects. And so we have a
lot of different axioms that uh describe
the nature of this idea of thinking of a
collection of things as as one thing
itself, one abstract thing. And axioms
are, I guess, facts that we assume are
true based on which we then build the
ideas of mathematics. So there's a bunch
of facts, axioms about sets that we can
put together and if they're sufficiently
powerful, we can then build on top of
that a lot of really interesting
mathematics.
>> Yeah, I think that's right. So I mean
the history of how of the current set
theory aims known as the Zera Franco
axioms came out in the early 20th
century with with Zermelo's idea. I mean
the history is quite fascinating because
um Zerlo in 1904 offered a proof that
the what's called the axim of choice
implies the well-order principle. So he
described his proof and that was
extremely controversial at the time and
there was no theory there weren't any
axioms there. Caner was not working in
an aimatic framework. He didn't have a
list of axioms in the way that we have
for set theory now and Zerlo didn't
either. Um and his ideas were challenged
so much with regard to the well-order
theorem
>> uh that he was pressed to produce the
theory that in which his argument could
be formalized and that was the origin of
what's known as their melo set theory.
Uh and going to perplexity the axiom of
choice is a fundamental principle in set
theory which states that for any
collection of non-mpty sets it is
possible to select exactly one element
from each set even if no explicit rule
to make the choices given. This axiom
allows the construction of a new set
containing one element from each
original set even in cases where the
collection is infinite or where there is
no natural way to specify a selection
rule. So this was controversial and uh
this was described before there was even
a language for exiomatic systems.
>> That's right. So on the one hand I mean
the exo 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. And if I have a
bunch of sets, then there's a function
that uh when you apply it to any one of
those sets gives you an element of that
set. It's it's a completely natural
principle. I mean, it's called the
eximma choice, which is a way of sort of
anthropomorphizing the mathematical
idea. It's not like the function is
choosing something. I mean, it's just
that if you were to make such choices,
there would be a function that consisted
of the choices that you made. And the
difficulty is that when you 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. You know, you want to have the
view that well there is a way of
choosing. I don't have an easy way to
say what the function is, but there
definitely is one. Yeah, this is the way
of thinking about the XMA choice. So
we're going to say the the the three
letters of ZFC maybe a lot in this
conversation. You already mentioned Zela
Frankle set theory. That's the Z and the
F. And the C in that is this comes from
this axum of choice.
>> That's right.
>> So ZFC sounds like a super technical
thing but it is the set of axioms that's
the foundation of modern mathematics.
>> Yeah. Absolutely. So one should be aware
also that there's huge parts of
mathematics that don't that pay
attention to whether the exo choice is
being used and they don't want to use
the eximma choice or they work out the
consequences that's that are possible
without the exma choice or with weakened
forms of of smela franle set theory and
so on and that's quite a there's quite a
vibrant amount of work in that area I
mean but going back to the exo choice
for a bit it's maybe uh interesting to
to give Russell's
description of how to think about the
axim of choice. So Russell describes um
this uh rich person who has a an
infinite closet and in that closet he
has infinitely many pairs of shoes
and he tells his butler uh to uh please
go and give me one shoe from each pair.
And and the butler can do this easily
because he can for any pair of shoes he
can just always pick the left shoe. I
mean there's a way of picking that we
can describe
we always take the left one or always
take the right one or take the left one
if it's a red shoe and the right one if
it's a brown shoe or you know we can
invent rules that would result in these
kind of choice functions. We can
describe explicit choice functions. And
for those cases, you don't need the axim
of choice to know that there's a choice
function. When you can describe a
specific way of choosing, then you don't
need to appeal to the axiom to know that
there's a choice function.
But the problematic case occurs
when you think about the infinite
collection of socks that the person has
in their closet. And if we assume that
socks are sort of indistinguishable
within each pair, you know, they match
each other, but they're sort of, you
know, incisible,
then the the butler wouldn't have any
kind of rule for which sock in each pair
to pick. And so it's not so clear that
he has a way of of producing one sock
from each pair because right so that's
what's at stake is the question of
whether you can specify a rule by which
the choice function you know a rule that
it obeys uh that defines the choice
function or whether there's sort of this
arbitrary choosing aspect to it that's
when you need the axim of choice to know
that there is such a function but of Of
course, as a matter of mathematical
ontology, we might find attractive the
idea that well, look, I mean, I don't I
don't not every way of choosing this
socks has to be defined by a rule. Why
should everything that exists in
mathematical reality follow a rule or a
procedure of that sort? If I have the
idea that my mathematical ontology is
rich with objects, then I think that
that there are all kinds of functions
and ways of choosing. Those are all part
of the mathematical reality that I want
to be talking about. And so I don't have
any problem asserting the actual choice.
Yes, there is a way of choosing um but I
can't tell necessarily tell you what it
is. But in a mathematical argument, I
can assume that I fix the choice
function because I know that there is
one. So it's a the philosophical
difference between working when you have
the exim of choice and when you don't is
the question of this constructive nature
of the argument. So if you make an
argument and you appeal to the axim
choice, then maybe you're admitting that
the objects that you're producing in the
proof are not going to be constructive.
you're not going to be able to
necessarily say specific things about
them. But if you're just claiming to
make an existence claim, that's totally
fine. Whereas, 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, uh, then you're probably going to
want to deny the axim choice and maybe
much more.
Can we maybe speak to the axioms that uh
underly CSC? So going to perplexity ZFC
or is a Mela frankl set theory with the
axiom of choice as we mentioned is the
standard foundation from most modern
mathematics. It consists of the
following main axioms. Axiom of
extensionality, axiom of empty set,
axiom of pairing, axiom of union, axom
of power set, axiom of infinity, axiom
of separation, aim of replacement, axum
of regularity, and axiom of choice. Uh,
some of these are quite basic. Um but it
would be nice to kind of give people a
sense
>> of what it means to be an axiom like
what kind of basic facts we can lay on
the table on which we can build some
beautiful mathematics.
>> Yeah. So the history of it is really
quite fascinating. So Zerlo introduced
most of these axioms I mean as part of
what's now called Zurlo set theory to
formalize his proof from the axim choice
to the well-order principle which was an
extremely controversial result. So in
1904 he gave the proof without the
theory and then it was challenged to
provide the theory and so in 1908 he
produced the Zumelo set theory and gave
the proof that in that theory you can
prove that every set admits a well
orderering. Um and so the acts on the
list these things like extensionality
express the the most fundamental
principles of the understanding of sets
that he wanted to be talking about. So
for example, extensionality says if two
sets have the same members, then they're
equal. So it's this idea that the sets
consist of the collection of their
members and that's it. There's nothing
else that's going on in the set. So it's
just if if two sets have the same
members, then they are the same set. So
it's maybe the most primitive uh axiom
in some respect. Well, there's also just
to give a flavor,
uh there exists a set with no elements
called the empty set. Uh for any two
sets, there's a set that contains
exactly those two sets as elements. For
any set, there's a set that contains
exactly the elements of the elements of
that set. So the union set and then
there's the power set. For any set,
there's a set whose elements are exactly
the subsets of the original set, the
power set. And the axum of infinity,
there exists an infinite set. typically
a set that contains the empty set and is
closed under the operation of adding one
more element. Back to our hotel example.
>> That's right.
>> And there's there's more. But this it's
kind of fascinating. Um I used to put
yourself in the mindset of people at the
beginning of this of trying to formalize
set theory.
It's it's fascinating that humans can do
that. I read some historical accounts by
historians about that time period,
specifically about Zerla's axioms and
his proof of the well-order theorem. And
the historians were saying, um, never
before in the history of mathematics has
a mathematical theorem been argued about
so publicly and so viciferously
uh as that theorem of Smela's. Um and
it's fascinating also because the axim
of choice was widely regarded as a kind
of you know basic principle at first but
then when but people were very
suspicious of the well order theorem
because no one could imagine a well
orderering say of the real numbers and
so this was a case when Zumelo seemed to
be from principles that seemed quite
reasonable proving this obvious untruth
and so people were mathematicians were
objecting um but then Zermelo and others
actually looked into the mathematical
papers and so on of some of the people
who had been objecting so viciferously
and found in many cases that they were
implicitly using the axim choice in
their own arguments even though they
would argue publicly against it because
it's so natural to use it because it's
such an obvious principle in a way I
mean it's easy to just use it by
accident with if you're not critical
enough and you don't even realize that
you're using the axim choice. That
that's true now even people like to pay
attention to when the axim choice is
used or not used in mathematical
arguments. I mean up until this day it
used to be more important in the early
20th century it was very important
because people didn't know if it was a
consistent theory or not and there were
these antitomies arising and so there
was a worry about consistency of the
axioms. Um but then of course eventually
with the result of of Gerel and Cohen
and so on this consistency question
specifically about the eximma choice
sort of falls away. We know that it the
aim of choice itself will never be the
source of inconsistency and set theory.
If there's inconsistency with the axim
choice then it's it's already
inconsistent without the axim of choice.
So it's not the cause of inconsistency.
And so in that from that point of view
the need to pay attention to whether
you're using it or not from a
consistency point of view is somehow
less important but still there's this uh
reason to pay attention to it on the
grounds of these uh constructivist ideas
that I had mentioned earlier
>> and we should say in set theory
consistency means that it is impossible
to derive a contradiction from the
axioms of the theory.
means that there's no contradictions.
That's that's a a consistent aimatic
system that there's no contradictions.
>> A consistent theory is one for which you
cannot prove a contradiction from that
theory.
>> Maybe a quick pause, quick break, quick
bathroom break.
You mentioned to me offline uh we were
talking about Russell's paradox and that
there's a nice another kind of
anthropomorphizable
proof of uncountability. Uh I was
wondering if you can lay that out. Oh
yeah, sure. Absolutely.
>> Both Russell's paradox and the proof,
>> right? So let's So we we talked about
Cander's proof that the real numbers,
the set of real numbers is an
uncountable infinity. It's a strictly
larger infinity than the natural
numbers. But Kander actually proved a 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 Caner proves that this is
this is a bigger set. They're not
equinumerous. Of course, there's always
at least as many subsets as elements
because for any element, you can make
the the singleton subset that has only
that guy as a member, right? So there's
always at least as many subsets as
elements. But the question is whether
they whether it's strictly more or not.
And so Caner reasoned like this. It's
very simple. It's a kind of distilling
the abstract diagonalization idea
without encumbered by the complexity of
the real numbers. So we have a set X and
we're looking at all of its subsets.
That's the power set of X. Suppose that
X and the power set of X have the same
size. Suppose there's contradiction.
they 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 I
mean another set. I'm going to define
it. Let's call it D. And D is the subset
of X that contains all the individuals
that are not in their set.
Every individual
was associated with a subset of X. And
I'm looking at the individuals that are
not in that their set. Maybe nobody's
like that. Maybe there's no element of X
that's like that. Or maybe they're all
like that. Or maybe some of them are and
some of them aren't. I don't it doesn't
really matter for the argument. I
defined a subset D consisting of the
individuals that are not in the set
that's attached to them. But that's a
perfectly good subset. And so because of
the equinosity it would have to be
attached to a to a particular individual
you know and but that let let's call
that person uh it should be a name
starting with D so 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 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 [clears throat] that's a
contradiction. So therefore, the number
of subsets is always greater than the
number of elements for any set.
And the anthropomorphizing idea is the
following. I like to talk about it this
way. uh for any collection of people you
can you can form more committees from
them than there are people
even if you have infinitely many people.
>> Mhm.
>> Suppose you have an infinite set of
people. And what's a committee? Well, a
committee is just a list of who's on the
committee basically the members of the
committee. So