antor's Infinities - Professor Raymond Flood
3 Video Views·Dec 14, 2024
Although many people contributed to the study of infinity over the centuries it was Georg Cantor in the nineteenth century who established its modern development. Cantor created modern set theory and established the importance of one-to-one correspondence between sets. For example he showed that the set of all integers can be put into one-to-one correspondence with the set of all fractions and so these two sets have the same infinity. But he also proved the remarkable result that there are infinitely many infinities, all of different sizes.
Thank you all very much for coming to my lecture today. This is my last lecture of this academic
year and the title is Cantor's Infinities and I'm going to introduce you to some marvellous
ideas about infinity that were developed by Cantor. And it's sometimes said that because
Cantor asked and then answered questions that had never been asked before, that he created
the first truly original mathematics since the Greeks. So a good topic to end this year's
lectures. I wanted to end with something really exciting. The first truly original mathematics
since the Greeks. And I'm pleased to say that I've been asked by Gresham to serve a fourth
and final year. So I will give you the dates of my lectures next year at the end of this one.
So we have Cantor was born in St. Petersburg in 1845 and died towards the end of the First
World War in 1918. Let me give a little background to 19th century mathematics and how Cantor fitted
in. In the 19th century mathematics experienced a movement towards a more a progressively more
abstract style with an increased emphasis on putting itself on a sound and a rigorous basis
and on examining its foundations. And this movement happened in the calculus, in algebra
and in geometry. In the calculus in the 1820s the French mathematician Cauchy, the most prolific
mathematician of that century, made a major advance in making the calculus rigorous by clarifying the
concept of a limit. The idea of a limit is needed in the calculus. For example when we have the
ratio of two quantities and we want to see what happens to this ratio as both quantities move
simultaneously towards zero, so becoming infinitely small. And it was later in the century that the
German mathematician Weierstrass gave a mathematically and logical solid definition of a limit
and it's his definition of a limit that we use today and in which the calculus is founded.
However as often happens the resolution of one problem drew attention to another one. It turned
out that getting a sound definition of a limit needed a rigorous definition of the real numbers
and that in turn led to the study of infinite sets by Cantor. And this work by Cantor arose
from his various investigations into the convergence of Fourier series, which I gave a lecture on
this year, and in particular into whether a function could be represented by a trigonometric
series in only one way. And this caused Cantor to start thinking about collections of numbers
and the relationship between the different kinds of number. As a result Cantor created modern set
theory. He established the importance of one-to-one correspondence between sets and founded the theory
of transfinite numbers, the mathematics of the size of sets of different sizes. He showed in particular
that infinities can have different sizes. As I've mentioned Cantor was born in St Petersburg and
began his university studies at the Polytechnic in Zurich, moving after a year to the more
prestigious Berlin University where he took his doctorate. In 1869 he became a lecturer at the
University of Halle, being promoted to professor 10 years later. He had always hoped to obtain a
position in Berlin but he remained in Halle for the rest of his life, teaching there for many years
before succumbing to severe mental illness, and he died in 1918 in Germany. On the left of the slide
there's a monument to him in Halle. It's one side of a cube commemorating four distinguished
academics who worked there. At the right of Cantor's portrait the inscription reads
Georg Cantor, mathematician, founder of set theory, and gives his dates. The other two elements of the
are on the left one of his formulae from transfinite arithmetic and on the right a
graphical representation of a diagonal, his diagonal method, and I'm going to talk about
both of those. Finally at the bottom on the left, which is hard to see over here and of course in
German, is the famous statement from Cantor which in translation says the essence of mathematics
lies in its freedom. And let me now give you a brief overview of the lecture
and introduce Cantor's free and impressive thinking. Cantor introduced his theory of sets
in a number of papers dating from 1874. For him a set was any collection into a whole
of definite and separate objects of our intuition or of our thought. I will give you some examples
and introduce some notation. And then next we come to one of Cantor's core ideas which is hard
to define when two sets of the same size and two sets A and B are said to be equivalent. We can
think of this as meaning they have the same size if we can match them up exactly. That is there's
a one-to-one correspondence between the elements of A and those of B and an example is the one-to-one
correspondence between the digits of my left hand and the digits of my right hand. And because they
could be matched up exactly that tells me that I've got the same number of digits on my left
as on my right hand. And notice that I've done that without counting the number of digits on
each hand. I haven't said there are five on the left and there are five on the right. So there
is a sense in which one-to-one correspondence is a more basic concept than counting. You can use
one-to-one correspondence to tell when two sets have got the same size you don't have to know how
many elements there are in each of them. Turns out that if A and B are finite sets then they must have
the same number of elements. Their counts must be the same but if the sets are infinite then things
become a lot more interesting. And I'm going to use one-to-one correspondence to give a definition
as well of what it means for a set to be infinite. Another of Cantor's core ideas, just two of them I'm
really going to concentrate on or the consequences of those two I'm going to concentrate on during
the lecture, is the way that he viewed the infinite. Cantor accepted the actual infinite
by viewing an infinite set as a mathematical object which could be thought of as a totality
and could be studied rather than a process of tending towards a limit, tending towards the
infinite as you got in some earlier definitions for example of a limit. Next we'll come to our
first example of an infinite set, the natural or the counting numbers one, two, three, four, five,
six etc. And we will say following Cantor that any set which is equivalent to the natural numbers
that is can be put in one-to-one correspondence with it is countable. And I'll show you some
examples of countable sets and try to explain how I think of what a countable set is.
But next, are all infinite sets countable? The answer is no. The set of the real numbers is not
countable. It can't be put into one-to-one correspondence with the integers, it can't be
written out as a list which is the way I think of countable. Something is countable if you can
write it down as a list. And Cantor's proof that the real numbers are not countable I think is one
of the most beautiful ones in mathematics. And we can use the result to tell us about the size of
the irrational numbers, how many irrational numbers there are, and how many transcendental
numbers there are. And I'll define both of those terms when we come to it. Well anyway, when we
reach that point in the lecture we'll have met two different sizes of infinities corresponding
to the size of the set of natural numbers and the size of the set of real numbers. And what I want
to show you then is the tool or technique that Cantor developed to obtain sets of larger infinity.
If you hand me an infinite set I can use Cantor's technique to construct a new set
with size a larger infinity. And of course I can then use the technique on the new set to get
another set with a larger infinity and so on, getting a hierarchy of an infinite number of
infinite sets of increasing sizes. And then briefly at the end I'll mention the continuum
hypothesis, which is a hypothesis that Cantor worked on but could never prove as to whether
or not there's an infinite set whose size is greater than that of the natural numbers but
smaller than that of the real numbers. And the answer is truly amazing. And then just a few brief
words about the reception of Cantor's ideas and not surprisingly once you hear about them
they were very controversial and weren't unanimously accepted.
Okay well to start with just setting some framework I'll use Cantor's definition of a set
any collection into a whole M of definite and separate objects, small m, of our intuition and
of our thought. And broadly speaking a set is a collection of objects. And in mathematics these
objects are usually numbers or points in space or even other sets. And there are three usual ways of
denoting sets. You could just list all the members of the set out usually within curly brackets and
that's the first example there. One, three, four, six, eight, a set with five elements.
But however most sets are too large to do this so we use a dot notation. Some sets are infinite
so there's an example there one, two, three, dot, dot, dot, 66 represents the whole numbers from one to 66
or two, four, six, eight, dot, dot, dot is all the even positive whole numbers. But the third way
and it'll be crucial to us later on in one of the arguments I want to use is to represent a set in
probably the most important way and that's using a property. A set is going to consist of those
elements x that satisfy a certain property. And Cantor's main theorem that I'll speak about
does exactly that. It defines a set of those elements with a particular property. So I give
two examples there. Curly brackets x colon meaning the set of x such that x is an even positive
integer or the set of x such that x is a prime number less than a million. Okay to come to the
first main thing one-to-one correspondence and Cantor's investigations led him to define a means
of deciding of two sets of the same size and I've already outlined it. Two sets of the same size we
can set up a one-to-one correspondence a pairing of the elements of the two set so two sets so that
no element of either set is left unpaired. And he put it two sets m and n are equivalent if it
is possible to put them by some law in such a relation to one another that to every element
of each one of them corresponds one and only one element of the other. And when they're equivalent
we sometimes say that they've got the same cardinality or they've got the same power.
And I think the idea of one-to-one correspondence is more basic than counting because you can tell
whether or not sets of the same size if you can put them into one-to-one correspondence
and you don't need to know how many elements there are in each.
But when when the sets are infinite Cantor was moving into new unmapped and exciting territory.
So let's look now start the core of the lecture some of the consequences of Cantor's two key
premises one of which is we can think of infinite sets as a totality and that this is a valid
mathematical concept the idea of an infinite set and secondly that the equal cardinality
of sets can be established by using one-to-one correspondence. And they're the two premises
that everything is going to be built upon and as I've written here these two premises
give strange results. All right so countable we take n that is going to turn out to be our base
our reference set for infinite n 1 2 3 and so on is a set of natural numbers and e I'm denoting as
the set of even natural numbers 2 4 6. Now then by Cantor's definition n and e can be easily seen
to have the same cardinality and you can see there I've set up a one-to-one correspondence
between their members so the association is that with each element of the natural numbers n
I associate its double so with 1 I associate 2 with 2 I associate 4 3 6 and just to reinforce
the definition every natural number is paired off with an even number and every even number
arises from a natural number so it's a complete one-to-one correspondence. So according to Cantor
these two infinite sets are of the same size and of course this seems paradoxical since it seems
there should be half as many even numbers as there are whole numbers but it is consistent
with Cantor's premises that we can regard the set of natural numbers as a totality
and the beautifully simple definition of equal cardinality using a one-to-one correspondence
and indeed following Cantor we can in a sense turn this paradox on its head and we define
an infinite set as one that can be put into a one-to-one correspondence with a proper subset
of itself a proper subset of is a collection of the elements of the set but not the whole set
a proper subset doesn't contain all the elements of the set so he's defining infinity a set is
infinite if you can put it into one-to-one correspondence with a proper subset of itself
you can't do that with finite sets so let me show you another set that is countable
and this time it's the integers so here the integers denoting fairly standardly by z towards
the bottom of the slide and the z consists of all the positive and negative integers as well as zero
and the usual ordering for them is you know the negative ones first minus three minus two minus
one zero one two three and it's infinite off to the left and it's infinite off to the right
and you think how can I put them into a list a list starting one two three four and so on going
down well you can do it if you put them into a different order and at the bottom of the slide
I've shown a different order of putting them in I put them in order of magnitude whether they're
positive or negative so the first one I call zero the second one is one the third is minus one
they're the ones of magnitude one the fourth is two the fifth is minus two the sixth is three
the seventh is minus three so countable means that they can be put in a list excuse me for
sort of pushing at the point but I can remember my own first introduction to it and essentially
getting hold of that idea and here what we have is we've shown that all of the integers
are countable they can be written down as a list starting zero one minus one two minus two
three minus three and but it isn't the usual ordering that you have for the integers okay
now just another term any set that could be put into one-to-one correspondence with the
integers called countably infinite or denumerable you'll see all these terms I just tend to use the
word countable and then the symbol I'll be using just to shorten some of the slides is his symbol
that he chose to denote the size of a countable set and he used the symbol alpha naught or alpha
null after the first letter of the Hebrew alphabet so Cantor's study of infinite sets had
led him to a new number indeed a new kind of number called a transfinite cardinal so n is
like the benchmark for these new numbers and what I've shown is that the cardinality of the even
numbers the even integers is the same as the cardinality of the integers they're both equal
to the cardinality of the counting numbers the natural numbers n and we're denoting that size of
infinity by all of not okay now to start to do something with it so to explore the ideas we want
to use an idea reportedly introduced by the German mathematician David Hilbert in a lecture in 1924
and sometimes called Hilbert's Grand Hotel so here we have a drawing of Hilbert's Grand Hotel
on the right hand side and the thing about it is got an infinite number of rooms countably
infinite number of rooms one two three four five six seven and so on and as you can see on the
right hand side here it's full everybody's here waiting to get into the room but somebody arrives
looking for a room that's the person around here arriving looking for a room and after a moment's
thought the manager who as it happens is also called cantor comes up with a solution he moves
everybody up a room the person in room number one moves to room number two person room number two
move to room number three three moves to four four to five five to six and remember this is an infant
hotel so they're all able to move up a room that leaves one room free which is the first one into
which he puts the new arrival um so we have our first expression in transfinite arithmetic that
if you add one to aleph naught you still remain with aleph naught but next a bus arrives with 66
people looking for rooms that's a bus with 66 people you have to understand something in the
lecture with 66 people arriving for rooms and cantors not fears this guy's quick he says i can
all i do is i move everybody moves up 66 rooms so the person in room one moves to room number 67
person in room two moves to room 68 and if you do that then that will leave the first 66 rooms free
and you put the new arrivals on the bus into rooms one two three up to 66 and as you can see that's
going to work for any finite number of new arrivals so the expression in the transfinite
arithmetic is this one down here 66 plus aleph null is going to be aleph null and that's true for any
finite number that you care of so cantor think this is relatively straightforward and he's just
settling down for a well-earned coffee when another bus arrives um but in this time it has
on board a infinite number a countably infinite number of people and that's a very long bus
so that's got a countably infinite number of people too but fortunately cantor i just heard
this very good lecture this one here that's what i meant and early on and he remembers a slide
which showed the one-to-one correspondence between the room numbers the natural numbers and one two
three four and the even numbers and so he says to himself everybody move to the room with number
twice that of your current room that's what everybody has to do move so if you're in room 20
you move to room 40 if you're 23 you move to room 46 that leaves all the odd numbered room free
that's an infinite number and he puts the people off the bus into the odd number rooms so
symbolically we've got all of null people in the hotel when the bus arrives all of null people on
the bus and you can combine them together still and you get out of null done succeeded now cantor
is again sitting down and this time but he's not to know it he's decided to have an irish coffee
particularly since it's st patrick's day and this time what happens is that not only one bus with
an infinite number of people arrive but an infinite number of buses each with an infinite
number of people and that's a bit trickier you probably need more than one coffee to help you
with that but then he thinks i know what i could do i'll rebuild my hotel i'll rebuild it like that
in the shape of a triangle or a flat pyramid or whatever so the rooms are going to be one two
three four five six and the third level seven eight nine ten eleven twelve thirteen fourteen
fifteen and this keeps going on down and down it's an infinite triangular arrangement of the rooms in
the hotel but if you look at that look at all the rightmost rooms one three six ten fifteen twenty
one and so on down here there's going to be a countable number of them so what he does is he
everybody who's already into the hotel in the hotel i mean into the rightmost rooms into the
ones with that color there which is sort of yellowy color so that means that the hotel
the original occupants of the hotel are all catered for and now the core this is why i'm
doing it this way you see if you take that rightmost column away from this arrangement
what you're left with is something that's similar to what you just had you've got another triangular
arrangement of the rooms and all of the rightmost rooms in this remaining arrangement they're all
free so he puts the people in the first bus the infinite number of people in the first bus
into this rightmost free row like that but now you see that what you're left with again remember
this is an infinite thing going right down you've got the rightmost free rooms are again
a whole column going right down and you can fill them up with the people that are in the second bus
which is what i do here so you're able just repeating this here to put the infinite number
of people on the infinite number of buses into the hotel in this configuration and then cantor
of course realizes i don't have to build the hotel you know all i notice for example i just need to
make a note of what these numbers are and i get the people and i put them into that number you
may recognize the first set of numbers down here are just the triangular numbers so we can use this
sort of mental map in order to find out which of the rooms in the original hotel to put each of the
people in each of the buses so depending upon what bus you're in that will depend which column you're
going down and what your seat is will depend upon where you go so what we've shown there in terms of
transponder arithmetic is that all of null times all of null because you've got an infinite number
of an infinite number of buses okay so you see why i said it was somewhat strange but you might
be saying to yourself if you had a chance time to think about it i see what might be going on
we can do this because these infinite sets are discreet they've got gaps and that's what allows
the method to work because we can somehow interleave them you know you've got all these
rooms and you're moving people up doubling them and then you're putting other people in between
and somewhere what's allowing us to do it is that we've got discrete sets here with gaps in them
and the answer is afraid not because let's try to think of an infinite set that doesn't have gaps
between its elements the way the integers have and the first one you might care to think about
is the set of fractions or rationals now rational number or a fraction is any integer divided by any
other non-zero integer and there's some examples written down there but the thing about two
fractions is that there's always a fraction in between which is their average the average of
two fractions is a fraction and if you add two numbers of the form one number over another
number it added on to one number over another number you get a fraction and it's halfway between
the two of them and therefore you know any two that you get there's going to be one in between
so there are no discrete gaps with the rational numbers but the thing is it turns out that the
rational numbers are still countable and as i suggest to you the way you think about that is
that they can be put into a list so how can we put the rational numbers any fraction over any
other fraction non-zero fraction into a list and here's a way of doing it what i have here
along the top row i write down all the integers all the whole numbers in the second row i write
down all the halves in the third row i write down all the thirds and the fourth row all the quarters
and you're getting the idea the fifth row i'm writing down all the fifths now how do i turn
them into a list i turn them into a list by doing this snaking operation i snake around i start at
one to two to a half to a third and whenever i meet something that i've met before i just jump
over it or i delete it a third to three to four to one and a half to two thirds to a quarter to a
fifth now the thing about that that's a listing of the rational numbers we are keeping going that's
a listing of the rational numbers which is what we mean by something being countable and here i've
given it explicitly down here so this list will contain all the positive fractions so the positive
fractions are countable and this is um the kind of argument that was alluded to on the cantor
memorial that i showed you at the start where there was this snaking back and forth so we've
now found that every set we've looked at is countable can be put up can be written out as a
list or can be put in one-to-one correspondence with the integers which is what a list is just
tells you which is the first which is the second and so on so are all of them are all infinite
sets countable well the answer is no and this is this lovely proof i referred to there's an infinite
set which is uncountable the real numbers and we're going to use a proof by contradiction
it's what the main technique one has in this subject i think and you want to show that the
real numbers which we can think of as all infinitesimals in fact i'm just going to show
initially that the infinitesimals lying between zero and one so you think of a real number each
real number corresponds to an infinitesimal and i'm going to look at the infinitesimals between
zero and one and i'm going to show that they're not countable and the way i do that is i suppose
that they are and then i derive a contradiction showing that that assumption must be incorrect
so if they are countable that means that you can write them down in some list some association
so the first one is associated with the counting number one let's say is x1 equal to that the
second one x2 equal to that the third one x3 equal to that the fourth one equal to this
and the generic one i think that's n xn the nth one is equal to that there now the idea
is very simple once you've seen it but what it must have been like to have thought of it i don't
know it would have been very pleasing um what i'm going to do is to construct a number that is not
on the list so i'm going to construct a number that's not on this list and the first decimal
of the number that is not on the list i'm going to take the first decimal place of the number that
is not on the list i'm going to take different from two so let me see what my next yeah so i'm
going to construct this number calling it b and the first decimal place of b namely b1 i'm going
to take different from the first decimal place of x1 which is two so i'm going to take it say equal
to four of course there are lots of choices but the important thing is because i've done that b1
it's not equal to that that means that the number b cannot be x1 because it doesn't agree with it in
the first decimal place so the number b cannot be x1 now the second decimal place of b b2 i'm going
to choose to be different from the second decimal place of x2 the second decimal place of x2 is 5
so i'm going to choose the second decimal place of b to be say 7 something different from 5 so
that means the number b that i'm constructing cannot be equal to x2 because it's different
from it in that decimal place i think you're getting to get it the third decimal place of
number i'm constructing b is going to be different from the third decimal place of x3
which is 6 at the moment it's 6 so i'll choose it something different let's say 8 and that means
the important thing is that the number b i'm constructing cannot be equal to x3 and i keep
going down the list constructing a b every time i add another decimal place onto b that rules it
out from being equal to something in the list and in the generic you can see down here the nth
decimal place of b bn i take different from an so the number that i get here it is with the numbers
i've chosen there b the one example i was given would be 0.47837 it's not in the list because at
each stage you constructed it so that it was different from the corresponding x in it so what
we've got is a list it supposedly contains all of the real numbers and what i've done is i've
constructed a number that isn't on the list you know so that's immediately a contradiction and
one would clinch the argument by saying that that means that the original the decimals cannot be
written in a list like this here now if you were sceptical and it's good in this game to be
sceptical you would say well i could just add this new number to the list but if you did that then
you could just do the process again and you would find another number that doesn't belong to the
list and so on and so on so there's an uncountable number of real numbers they cannot be uncountable
i mean they cannot be put into one-to-one correspondence with the integers they're
sometimes called a diagonal argument because what we're doing is we're going down the diagonal
of these decimal places here two five six and so on and at each stage choosing a number and in fact
you can see there were lots of choices that you could have made to get a number that wasn't in
the list and i think one of the things that sort of helps me in thinking about that um let me just
skip over the next slide for a minute and then come back to it
um i've just put this into the notes it's something i've met i can't remember when it was
in school but it was one of the first things i thought that really excited me about mathematics
the the part i just want to draw your attention to is the top the the rationals the fractions
they can be thought of as precisely the collection of decimals which repeat
so we've given some examples there which actually takes quite a while to work out
you know especially 17 over 7 2.4 the block that's repeating is the 4 2 8 5 7 1 4 2 8 5 7 1
so rationals are those infinite decimals that repeat or repeat in blocks and when you think
of all the choices and we know that the fractions are countable they can be put into a list but when
you think of the infinite all the infinite decimals there can be there are many more than those that
terminate or start to repeat think of all the possible patterns or lack of patterns that you
could have amongst infinite decimals and that helps me to appreciate why it is the case that
you can't put the real numbers into a list that the real numbers are countable okay so but anyway
the argument pretty when you look at it on the left hand side it's uh gives you the fact that
it must repeat and on the right hand side it shows you that if it repeats you can show that it's a
decimal as any one of these amazing things i showed here that the numbers from zero up to one
the real numbers are uncountable but you take some sort of a curve such as this one here
and there are lots of them around that's an example of of one of them and this gives you
an association between any real number that any real number say up here you go across to the curve
and then down here and what you can do is you can associate any real number to a number between zero
and one and so therefore the real numbers are uncountable as well again not surprisingly so
what have we got to we've got to yeah we just got the rational stage here so let's just try and draw
some consequences out of the fact now that we've got two infinities so if you hold on we've got
two infinite sets archetypal typical one is the integers and the other typical one is the real
numbers both of different infinities so let me put that into a table and have a look at it
now that was the one that i jumped over into the table we've got repeating what i said natural
numbers integers rational numbers we showed all of them were out of null because the real numbers
are countable here now the definition of the irrationals are those real numbers which aren't
rational those real numbers such as root two that can't be written as one whole number over
another whole number and because of the fact that the rationals are countable that tells us that the
irrationals cannot be countable because if the irrationals were countable it's like Hilbert's
hotel again if the we know the rationals are countable so we could put a rational into every
room in the hotel if the irrationals were countable they would just be like one infinite
bus arriving and we know how to put them into rooms as well but we've just if you add together
the rationals and the irrationals you come up with the reals and we've just proved that the
reals are not countable so it must be the case that the irrationals and you can show have got
the same infinity the same cardinality as the real numbers so there's a very definite sense
in which there are many more irrational numbers than there are rational numbers and because we've
got a way or at least I've got a way of thinking of rationals in terms of these decimals that
repeat or don't repeat I can get a feeling for that but there was another important classification
in the 19th century and that was between what are called algebraic numbers and transcendental
numbers now from the diagram down below here at the bottom algebraic numbers are a bit more
more general than rational numbers in fact algebraic numbers are all solutions of a
of an equation with integer coefficients so for example all the rationals are a quarter lies in
there because it's a solution of the equation 4x is equal to 1 x equals a quarter is a solution of
that root 2 is in there because root 2 is the solution of the equation x squared is equal to 2
so root 2 is an algebraic number and you can show by a similar argument as the Hilbert Hotel one
and that the algebraic numbers are countable you can put all the algebraic numbers into a room
and you'll have enough rooms in order to be able to have one in each of them it's just like Hilbert
it's just like the buses arriving there's an infinite number of buses but this
time they only have a finite number of people on each of them you can set it up like that
so that means as a similar argument as I gave a moment ago about the rationals and irrationals
that the transcendental numbers those numbers which are not algebraic must be
uncountably infinite over here and these include numbers like pi
but when Cantor produced this result in 1874 what he's the result is saying is that most numbers
are transcendental but at that time people have been able to prove that very few numbers were
transcendental and here he was coming up with an approach that said most of them must be
transcendental by a counting argument in fact I think it was something like 1884, 1882 that pi
was shown to be transcendental whereas in 1874 he had shown that most of them were so really quite
an amazing sort of result to this technique completely non-constructive he didn't exhibit
a single transcendental number but by showing that the number of reals was a certain size of infinity
that the number of algebraic ones was a smaller size of infinity
then the transcendental ones which are the ones who aren't algebraic must be
infinite and in particular one can show it's got the same infinity as the set of real numbers
so this was truly astounding in its time okay so Cantor now has two types of infinity
and this is the last segment of the lecture he's got the natural numbers two kinds of infinities
and he's got the reals other other cardinalities well I think I can remember when I thought of it
myself first met it if you're looking to see where you can find more infinities bigger infinities it
would seem reasonable to look at the plane the set of all points in the plane but Cantor was
able to show that the points in the plane are no more abundant than the points of the real line
and as he wrote I see it but I do not believe it and I don't have time to show you that there
because it's uh because I want to show you this he had to look elsewhere what he's trying to do now
he's got two kinds of infinities he's trying to find if there are any more and not only does he
find out that there are more he finds out that there are lots more and I just need to introduce
I think it's probably my last concept to you and it's um if you're given a set we want to think
about another set which is the collection of all subsets of the set that we've been given
so given a set a the par set is the set of all subsets of a and I've written it out here
explicitly for the set consisting of the three elements a b c and then it's got eight subsets
and I've written them out there there's the set consisting of the empty set which is very
important in this game and the set consisting of a and the subset consisting of b subset consisting
of c the subset of a b and then of a c then b c and then the whole set itself a b c and if the
set has got n elements then it's got two to the n subsets the reason for that if you have a chance
to think about it is that when you're forming the subsets for each element you've got two choices
either to include it or not include it so you've got two choices for each of the n elements so the
number of different ways you can make those choices is two to the power of n so that's why
if you've got three elements in your set you will have two to the power of three namely eight subsets
now the crucial thing for Cantor's argument I'm going to show you is that the par set is itself
a set the result is Cantor's theorem that no set can be placed in one-to-one correspondence
with its par set no set can be placed in one-to-one correspondence with its par set
proof by contradiction seems to be the only way you can get a handle on it let's suppose it is
false let's suppose we can do that so we have an association between the set a these are the
elements of a down here I'm using letters to denote them a b c d e f g these are the elements
of a and on the right hand side I'm going to be listing all the sub all the subsets of a and I'm
supposing that there's a pairing between a sorry each element of set a and each and all the subsets
of a so I am associating little a here with the subset c d little b with a subset e little c this
just of course the grounds of them trying to help with the the exposition there is some small such
association so now we do the clever bit or the clever bit I suppose it's the bit after this
we define a subset of a now this is where that that's why I burdened you with the definition
of a set earlier on a set being defined by some property I'm going to consider a sub the following
subset called b of a b is a subset of a and it's the collection of all elements of a that don't
belong to the set the subset with which are matched now it's quite hard to absorb it even
it's quite hard to say um so let me go down here b is the collection the set of every element of
the original set that is not a member of the subset with which it is matched so a belongs to
it because a doesn't belong to the subset with which it is matched subset with which it is
matched cd and a is not in there so a belongs to b b doesn't belong to the subset with which it's
matched so b belongs to it but c c does belong to the subset with which it is matched so c doesn't
belong to B and thankfully I haven't got it in there. D doesn't belong to the
empty set nothing belongs to the empty set so D does go in there. E this is the
whole set E belongs to A so that means that E is not a member of B and so on
right down. So if you tell me an element belong to B I know that when I find it
in the list down here that it's when I go across to the subset with which it's
associated it's not going to be in that subset. It's tough I wish I could tell
you it's going to get better but it's not. Alright so we've got this subset
with a certain defining property you can think of it just like that for a moment
and then you can go back and remember what the defining property is. There's a
subset we're calling B with a certain defining property but remember our
original assumption that every elements of A could be associated with all of the
subsets of B so that means that B has to appear somewhere down this right-hand
side because this contains all the subsets of the original set A. So that
means it must be associated with some element and I think I've got that in the
next slide yes B had to be in the right-hand column because that was the
assumption so that means it has to be associated with some element which I'm
calling Z. So that arose from the fact that we said there was a one-to-one
correspondence between the set A and the set of all its subsets. Now wait for it.
This is the fatal question. Is Z an element of B? You'll be glad you're having a break of seven months.
Suppose it is. Case one. Suppose Z is an element of B so that means that Z here
is an element of B but what was the defining property of B? Yes Z satisfies
the defining property of B which is that it consists of elements which do not
belong to their matching subset. So Z does not belong to B. If Z belongs to B
that means it satisfies the criteria for belonging to the club but to belong to
the club of B it only consists of those elements that don't belong to their
matching subset. So you think oh good I'm glad that's out of the way. That means
that Z is not an element of B but if Z is not an element of B it's not an
element of the subset with which it is matched but that's the definition of
belonging to B. Z satisfies the defining property of B which is that it consists
of elements which do not belong to their matching subset. So Z does belong to B.
So you need a little time to look at that and to ponder. So the stages are you
had a one-to-one association with the elements of A and with every subset. You
defined a particular subset, the subset of elements that didn't belong to the
subset with which they were matched. That particular subset we're calling B had to
be matched up with some element and then you ask yourself whether or not the
element with which it is matched belongs to B and you see that whichever way you
take it because of the defining property of B you can come up with a
contradiction. So the original supposition cannot be correct. It means
that a set A cannot be put into one one correspondence with its power set. So
that means that the power set is going to be of a larger infinity. So
I've got it here just to say it. So the reals have therefore got a smaller
cardinality than the power set of the reals. So the set of all subsets of the
reals is a bigger cardinality than the reals. But you can do it again. I said
that at the very start. So therefore reals have a smaller cardinality than
the power set and that itself is smaller than the power set of the power set of
the reals and so on. And it doesn't matter what the tool is. All you know is
you've got a tool which if I hand you a set you can hand me back one of the
bigger infinity and we can keep playing that back and forth. So we keep getting a
hierarchy of infinities going up. Okay so that just brings me to the
conclusion and the conclusion was something that oh no let me just give you
a bit of notation because it explains what was on the Cantor monument. The
cardinality of the reals is usually written using this symbol C. C for
continuum and indeed what we can show is that the cardinality of the collection
of the subset of the integers, the subsets of the integers can be paired
off with the real numbers. That's the second thing that appeared in the Cantor
monument. Now the problem the Cantor couldn't satisfy, couldn't solve was the
continuum hypothesis and that's really saying that the two infinities that I've
spent most of the lecture talking about, the natural numbers and the real numbers,
Cantor wanted to try and establish whether or not there was an infinity
lying strictly between the two of those and he was unable to show it. And that is
not surprising. Some days he thought he proved it and then he would write to
friends saying so and then he would write subsequently saying he proved it
false and he just oscillated. And that's because it turns out that that
particular thing is independent of set theory, of the particularly standard
set of axioms for set theory and the work of Godel and Cohen
proved that there. Godel in 1940 showed that the continuum hypothesis cannot be
disproved using ordinary set theory and then 1963 Cohen showed it couldn't be
proved. So it's independent, you know, so a bunch of spending your life trying to
work on that. Okay so last few words then. So Cantor's work, very controversial,
raised really difficult questions and many powerful and established
mathematical figures were critical of what he'd achieved. But he had achieved
recognition by the end of his career but there were problems, just allude to them,
you know, he couldn't resolve for example Russell's paradox about the collection
of the set of all sets which are not members of themselves. Is it a member of
itself or not? These self-referential problems. Cantor's approach was just to
regard such collections as being too large and not really sets at
all or as he put it, I think a nice phrase, inconsistent aggregates. So other
mathematicians began to axiomate high set theory to try and exclude the
possibility of contradictions. But the new set of questions that arose
from Cantor's work shouldn't take away really from his magnificent, really
magnificent achievement of enabling us to deal with the concept of the infinite
careful, thoughtful and consistent manner. And Cantor was quite religious and you
can see that in the the penultimate statement in this clause leaving the
words to him. My theory stands as firm as a rock, every arrow directed against it
will return quickly to its archer. How do I know this? Because I've studied it from
all sides for many years, because I've examined all objections which has ever
been made against the infinite numbers and above all because I've followed its
roots, so to speak, to the first and fallible cause of all created things. So
thank you very much and I could just finish giving you some dates hopefully
for your diary for next year. So thank you.

