Well, welcome everybody to the first lecture on Alan Turing on computer ability and intelligence.
I'm Peter Milliken. As you see at Harvard College and as most of you probably know, I'm quite keen on computer science and philosophy,
which is the degree programme towards which these lectures around.
Anyone here who's not doing computer science philosophy? You're very welcome to.
It's a very interesting topic, and I hope you enjoy the lectures.
As you'll be aware, they're being recorded this year. That's so that they're available in the future.
So for that reason, I'm not going to be taking any questions during the lectures.
But if any problems arise, I will be organising classes during the term for anyone who needs them.
Okay, those doing computer science philosophy later in the term will be having tutorials on the stuff to do with philosophy of mind.
And so when you'll be writing essays and I'll give you details about that later.
The role of the course is part of the introduction to philosophy for the prelims course in computer science and philosophy.
And just to get this out of the way, you have a three hour examination and it contains six either all questions on general
philosophy and six questions on curing from which you are expected to choose for.
And you have to do at least one from each section, so you could end up doing one question on curing.
You could end up doing three. In practise, I have to say computer science philosophy students tend to do more Turing papers than gentle questions,
so you'll probably find that the course is quite fruitful from that point of view.
Here's the overall plan of the lectures. Today we'll be talking about types of number about cantor infinities diagonal argument.
Next lecture We're going to be talking about Hilbert programme and girdles theorem.
We won't be going through Girdles Theorem in all detail, but we will be seeing how it works.
The ingenious method by which girdle proved his result, and by then, you'll understand why it's important.
Lecture three to five Focus on the the really main core of the lectures,
which is Alan Turing's 1936 paper on computable numbers with an application to the incidence problem.
Now that was the paper that introduced the Turing machine and hence virtually invented the computer.
We have a set text for that, which makes it feasible to do this.
It's a fiercely difficult paper, but with the help of this book by Charles Petzold, you should, I hope, find it entirely manageable.
Those doing computer science and philosophy, it's probably a good idea to buy this book.
The reason is that you might very well find as you go through it, that you want to make notes and highlights and so forth on it.
And of course, you shouldn't be doing that with library books. Okay, so that's lecture three to five.
And then in the last three lectures, we'll be looking at Alan Turing's other very famous paper,
the 1950 paper computing machinery and intelligence, and that's the paper that introduced the Turing test.
So that's where we get into stuff from philosophy of mind and so on.
Okay, so I've mentioned the textbook. Here are the details about it.
It really does contain everything you need to know on the background of the 1936 paper that it contains the
actual text of the paper if you see highlighted here in grey so that you can see exactly what Turing wrote.
But it's surrounded by a lot of commentary, which makes it all comprehensible, explains difficulties, explains corrections and so forth.
What I'll be doing in these lectures is giving you, I hope, enough material that will make that paper much more comprehensible.
Even with petzold help, you might find it difficult sometimes to see the wood for the trees in the lectures.
I'm going to be focussing on bits that are particularly difficult and setting the background for that.
OK? Highly recommended reading a couple of books by Andrew Hodges, which are biographical books about Turing,
but obviously also contain quite a lot of stuff that's relevant to what we're going to be talking about.
His mammoth biography from 1983 and very well known.
If you want to read something during the long vacation, maybe that's a good idea.
A much shorter book, just 58 pages is very well worth reading to get a feel for what Turing was about,
and I'll be mentioning this book, which is a huge collection on Turing remarkable value.
It's actually surprisingly cheap for a book of over 900 pages.
So if you're a real enthusiast and you want an absolute doorstop of a book, that's worth considering that you should.
Most of you have it in college libraries. And if you don't get them to order it and this small book, it's a classic book on girdles proof.
I'll be mentioning next lecture. Okay, so who was Alan Turing?
Well, he was born in 1912, educated at Hazelhurst and Sherburne schools.
His parents were in India, so he was at boarding school.
He formed a close relationship with another lad at the school called Christopher Malcolm.
And both of them applied to read maths at Trinity Cambridge.
Malcolm was accepted. Turing wasn't. But the next year, Malcolm died of tuberculosis.
And it seems they had a very intimate affair. Alan Turing was gay,
losing his intimate friend had a profound effect on him and got him thinking a lot seems about the nature of mind where the mind can survive death,
the relation between mind and body and so forth.
I mean, so some of this is speculative, but it seems very plausible later in his life, as is well known.
He played a huge role in the war in the Second World War.
He was largely responsible for the techniques by which the Nazi Enigma codes were decrypted,
thus enabling allied shipping to escape the U-boats in the Atlantic without cheering.
It's entirely possible that the war would have gone on a lot longer and been a lot more
difficult to win because without being able to divert the ships around the U-boat packs,
Britain's position would really have been quite perilous in the early 1940s.
This was completely unknown until relatively recently because it was all official secrets,
and Turing was prosecuted for homosexuality in the early 1950s.
And again, nobody knew what a hero he was.
He was forced to take hormone treatment, which had very bad effects on him, and he ended up probably committing suicide in 1954.
He seems to have set it up in such a way that there was a little bit of ambiguity.
He he apparently took a bite out of an apple on which he'd committed suicide cyanide.
But it is possible that he killed himself by mistake.
So a plausible suggestion is that he deliberately set it up that way so that his
mother would be able to believe that he hadn't actually killed himself deliberately.
Anyway, back to his early life, he reapplied to Cambridge.
In 1930, he was accepted for King's College, went up in 1931.
He took his part to try pass exams in 1934, passed with distinction and got a research student ship.
Then the next year, he was elected to a three year fellowship, so he obviously did extremely well in maths at Cambridge.
By 1935, he was a fellow and he attended a Part three course given by Max Neumann on the foundations of mathematics.
And this, again, is something that seems to have had quite a profound effect on him to understand why we
need to look a bit at one of the greatest mathematicians of the early 20th century.
David Hilbert Hilbert was born in Konigsberg, the city with which Immanuel Kant is greatly associated.
He was perhaps the most influential mathematician of the early 20th century, partly because he set the agenda.
He made a point of saying, Here are big problems on which we should focus.
He also developed the formalised approach to philosophy of maths. So those of you who study philosophy of maths you will come across, you know,
the the politeness, the approach, the intuition is the approach, the formalist approach.
And Hilbert is very much a founder of the last of these, the formalised approach CS mathematics as involving manipulations of symbols.
So we discuss proofs and things in terms of their syntactic properties, and we'll see that playing a role later,
especially next time at the 19:00 Paris International Conference of Congress of Mathematicians.
He famously listed prominent unsolved problems of mathematics, including this one,
the tenth problem determination of the solve ability of a Die-Off and time equation.
Now I put this in, partly because Petzold, in his book,
discusses these at some length and very interestingly, so I recommend that you go and look at his book.
The question is, suppose you have an equation which has a number of unknowns and with integer coefficients, can there be a solution to that equation?
And trying to devise a process by which you can tell whether there is a solution or not is a major problem.
The the equations were named after an Alexandrian mathematician, Dave Fanta.
The most famous example of a die Fantine equation is associated with them as last Theorem X to the end, plus Y to the end.
And does this have any integer solutions when N is greater than two?
I mean, it clearly does when any equals one.
It clearly does. When any calls to, for example, three squared plus four squared equals five squared.
Does it have any when an equal three or four or more than that?
And for many years, this was a huge puzzle.
The great French mathematician Thelma famously wrote in the margin of one of his notebooks that he had discovered a wonderful proof of this theorem,
but I don't have room to write it down in the margin. And this intrigued future generations of mathematicians.
They all tried to discover or rediscover this proof that Thelma had supposedly discovered.
It actually took a huge amount of work by lots of mathematicians and eventually was proved by Andrew Wiles in 1995.
I think most people think that Sam probably found an ingenious proof that applied to certain cases,
but not to all because proving it as a general theorem is actually extraordinarily difficult requires very sophisticated mathematics.
OK, let's have a quick look at some of Gilbert's other problems, apart from the one concerning Di Fantine equations.
We've got the continuum hypothesis that's a very important problem in philosophy of mathematics.
Again, here on, I'm not going to discuss it, but I'm just going to refer you to Petzold.
That's something he discusses and is well worth knowing about proving the
consistency of the axioms of arithmetic that something will be coming back to,
particularly next time. The Riemann hypothesis and Goldmark conjecture gold, but conjecture is a favourite of philosophers.
It's the claim that any even number greater than two can be expressed as the sum of two prime numbers.
Philosophers love it because it hasn't yet been proved.
So when I started out studying maths at Oxford quite a long time ago, there were three of these very famous unsolved problems,
and one of them was the full-color theorem, which got proved the subsequent year.
One of them was Fermat's Last Theorem, which, as I say, was proved in 1995.
I'm hoping that Girlboss conjecture will last a bit longer so that we philosophers can continue to give.
It is a nice example. OK.
Let's come to here. But the challenge is that Hilbert set, he set out a programme in philosophy of mathematics.
He wanted to establish foundations for mathematics, which were provably consistent.
So starting from axioms which were ideally self-evident, clearly true and manifestly consistent.
So even if you can't necessarily see immediately that they're all true, you want to be able to prove that they all hang together.
There's no inconsistency there and a set of axioms from which in principle,
all mathematical truths can be deduced by the standard rules of First Order predicate logic.
So I assume you've all learnt, first of all, the predicate logic, standard logic that we inherited from Fraga.
Is it possible to get a set of basic axioms from which by those rules, you can deduce all of mathematics or at least all of arithmetic?
A related problem, the incidents problem,
the problem that Alan Turing was going to be concerned with the decision problem, can an effective procedure be devised,
which would demonstrate in a finite time with any given mathematical proposition is or is not provable from a given set of axioms?
OK, so we want these axioms. We want them to be provably consistent and complete, such that all of mathematics can be deduced from them.
We also want to have a procedure which in a finite time is going to tell us as it were,
mechanically simply by applying this procedure in a mechanical way to tell us
whether any given proposition is or is not provable from the set of axioms.
Okay. Some of the relations between those will become much clearer next time when we talk about girdle.
The 1936 paper, which is said, the sort of central topic of these lectures.
Second, the decision problem, the entitlements problem.
It showed, in fact, that there could be no such procedure.
But the paper starts, as the title suggests, from the concept of a computable number.
So then the paper the ultimate aim of Turing's paper is to settle the incidence problem.
It gets there by talking about a certain kind of number, a computable number.
Now, in order to understand what those are and how they fit in with everything else, we're going to need to talk first about types of number.
So that's actually going to be the main focus of the rest of this lecture. In the next lecture, as I've said, we'll move on to girdle.
We'll talk about completeness and consistency.
And then by the third lecture, we'll have a good framework for understanding where Turing's paper comes in and and why it takes the form it does.
Okay, so what we we're going to look at various types of number and find interesting results about some of these sets of numbers.
So here are some set standards used in mathematics the set of natural numbers one two three four You're studying computer science.
You've probably been told the first natural number zero. I'm going to take the first natural number to be one because zero.
Isn't that natural? Is it real? OK? It's actually pretty harmless for most contexts.
Whether you take the natural numbers are starting from zero or one.
We're going to go with one the set of integers from Xylem and German of the symbol Zaidi's commonly used for that.
The set of integers obviously is both positive and negative, and zero the set of rational numbers.
A rational number is simply a fraction of integers, so you've got an integer on the top, you've got an integer on the bottom.
Obviously not zero on the bottom. And that set is commonly denominated Q, probably for quotient.
And then there are real numbers, say R, and real numbers essentially correspond to to all the non complex numbers,
all the numbers that we normally handle when we're doing things like calculus or trigonometry and so forth.
Those are all real numbers now. Real numbers include irrational numbers, numbers that cannot be written as a fraction of integers,
algebraic numbers which are roots of algebraic equations and transmittal numbers, which on either of those?
OK, I'll be coming to those a little bit later in the lecture. We're not going to be talking here about the set of complex numbers.
Some of what we do could apply equally to complex numbers, but they're not really relevant to the business here.
OK. Now, these are obviously all infinite sets.
There's an infinite number of natural numbers. There's an infinite number of rational numbers and so forth.
But what Georg Cantor did was show that not all of these infinities are the same.
We're going to end up with more than one type of infinity.
So that's the theory of Tehran's finite cardinal numbers.
And the key to understanding how this works is a principle that's to my mind, somewhat ironically known as Hume's principle.
As you probably know, I'm rather a fan of David Hume, but it has to be said that philosophy of mathematics wasn't exactly Hume's strongest point.
So there's an irony in this absolute key principle in the philosophy of mathematics being named after him.
But the reason is that Fraga, in foundations of arithmetic, pointed out that Hume had enunciated this principle when two numbers are so combined,
as the one has always a unit answering to every use of the other, we pronounce them equal.
OK, so let's see what's being said here.
The idea is that if you have two sets of objects and you can put those two sets in one to one
correspondence so that each unit in one of the sets corresponds to one and only one unit in the other set,
then you can say that the two sets are equally numerous.
They have the same number of elements.
Mathematically, we well, first of all, we use a technical term called finality for the number of elements in a set.
And this is meant to be a generalisation so that we can extend it to infinite numbers, not just finite.
So two sets of the same card inanity if and only if Abhijit two function were a one to one, correspondence can be defined between them.
So let's just get clear what objective function is a function that is both injected and surge active.
So and this is an example of an injected function here.
We've got the domain here, we've got the code domain and you can see that this object is the function of this.
This is the function of this or, as we say, the image of it.
And you can see that there is no object in the code domain, which is the image of two or more objects in the domain.
You never get two arrows going to the same point. OK.
That's an injected function. Here's an example of a subjective function.
Here you can see this one is not injected. We sometimes do have two arrows going at the same point.
But there is no object within the code domain, which is not hit by at least one arrow.
Got that? Now, do you agree that if we have an injected function, if not, we never have two arrows going to the same point here,
then this set must have at least as many elements as this one.
Yeah. Because there has to be a separate element for every act.
Whereas if we have a subjective function, that means every element here gets hit by at least one arrow,
then this set must have at least as many elements as that one agree.
So if we have objective function, a function that is both injected and surgically, if a one to one correspondence,
it follows that the two sets must have the same commonality, the same number of elements.
Now, essentially, what we do when we talk about infinite sets is we take that principle, which is so natural with finite sets,
and we extend it and apply it to infinite sets and cantors were basically comes from doing that.
OK, now when we're dealing with infinite sets rather than attempting to define objection,
we normally make do with a search action, a search active function if we can define a function from set to set B, which is A.
In other words, every element of B gets hit by an arrow.
Then we can say that the commonality of pay must be at least as great as the code Nancy at the OK.
And that's that's normally enough for our purposes.
We don't go to the trouble of trying to define objection a one to one correspondence that in many cases,
would be a lot more complicated and unnecessarily so we'll see that quite shortly.
Now, clearly, if you can define a subjection both ways, then on Hume's principle, the two commonalities should be the same.
OK, now one very important special case, if a suggestion can be defined from the set of natural numbers to any set,
then we say that that stuff is countable or innumerable, in other words.
So we've got a function that goes from the natural numbers. Each natural number is mapped onto an element of this set.
Every single element of that set is hit by at least one natural number, at least one of these arrows from a natural number.
Right. So you can imagine in principle,
writing down the elements of this set in order start according to the natural number which mapped onto them the first, the second or the 4.0.
Now, some of those elements may occur multiple times in the list.
That doesn't matter. We've said we're going to make do with a surge action.
But every single element of that set should be there somewhere in the list if we have correctly defined as objective function.
So we can enumerate the list in the sense of listed in principle because it's infinite.
So we can't actually in practise, but in principle we can. OK.
I've already thought about that. So one of the results that Cantor proved, rather surprisingly,
is that the set of rational numbers and the set of algebraic numbers are both innumerable.
So we're going to see how that works. OK, a rational number is a number that can be expressed as a fraction of integers expressed as a decimal.
If you take a decimal number, a number is rational if and only if that decimal eventually recurs.
So, for example, three point not not not not not not more recurring.
That's the rational 7.5 no more recurring nought point six 666, etc. nought point three six seven three six seven three six seven.
All of these are rational numbers. Now, it's actually pretty easy to show this.
Take that last example nought point three six seven three six seven three six seven,
etc. You can see that that is actually the sum of the geometric series.
OK, you've got 367 over a thousand. That's that Mate Plus three, six seven over a million.
That's that plus three six seven over a billion, which is that the and so on.
So you've got a series in which each each item in the series is 1000 less than the item before.
And you can easily that some geometric geometric progression using this formula, the first element divided by one minus the common ratio.
And that means that some of that will be 367 over 9-9-9.
OK. So any recurring decimal basically is going to be a rational number.
When we're talking about irrational numbers, we're talking about decimals that go on and on forever, but do not actually recur.
OK, now you might then think that the number of rational numbers will be hugely greater than the number of integers taken at the set of integers.
Let's just talk about positive integers for the moment.
One two three four five six seven And so between one and two, there are zillions of rational numbers, right?
One followed by any proper fraction you get a mention is going to be a rational number.
You know, one and seven twelfths or whatever is going to be a rational when you've got all these huge number of rational
numbers between one and two and then you've got the same number between two and three and three and four.
How can it be as Cantor claims that the set of rational numbers, all rational numbers has no more elements than the set of integers?
Well,
let's apply whose principle and very famous argument we set out all the rational numbers in an infinite array of clearly infinite in both directions.
OK. So you can see that the first row has a denominator of one.
The second row has a denominator of two. Third row has to nominate the three, and so the numerator is are in the column.
So the first column has a numerator of one.
The second column has a numerator to the third column as a new range of three.
And so every fraction of positive integers is going to occur somewhere in that array.
Agreed. And moreover, whatever fraction you care to name, it's actually pretty easy to say where in that array it look.
So there's no mystery here. OK, now what we do, we put these fractions in a sequence starting from here.
Then that one, then that one in that one, then that one in that one following the red line.
And you can see that if we carry on in that pattern sooner or later, every single fraction in that array will be taken.
Agree. So in and again, it's not that difficult actually to work out a formula which will tell you at what point in the sequence it will arise.
So we've defined a suggestion, a suggestion from the natural numbers to the fractions.
I've not spelt it out, but it's implicit here.
You can see f of one is one over one effort to two over one after three is one half so that the F function is
simply taking any natural number and mapping it to whichever fraction occurs at that point along the the red line.
So it turns out you can put all the rational numbers in a list.
An infinite list, of course, but that means there are no more natural numbers, so no more rational numbers than there are natural numbers you can pet.
You can define this objection, so we list all of the fractions.
And that's the start of it. Our suggestion maps one to the first of these two to the second three to the third.
As we've seen. A curious fact about this is that every single fraction in that list occurs not just once, but an infinity of times.
I mean, consider the fraction one over three. That's the same as two over six three overnight for over 12.
So you've got this amazing result that that a list in which every single possible fraction
occurs an infinity of times still contains no more elements than the number of natural numbers.
You might be wondering what happens with negatives? Well, if you want to include negative fractions, you just alternate.
Okay? It just means the list will be spaced out twice as much.
OK, so a natural thought at this point would be, well, maybe it's not so surprising.
OK. I mean, infinity is infinity. You've got an infinite number of natural numbers, an infinite number of rational numbers.
Why should it be a surprise that these come out to be the same?
Well, to see the impact of countless result, we need to look at irrational numbers, and I'm just going to introduce the most famous of these,
perhaps it's a beautiful proof, I think really quite elegant, and I think it dates back to Euclid.
Square two cannot be expressed as a fraction of integers. The square root of two is not a rational number.
Amazingly, it's very easy to prove. Suppose that the square root of two is equal to m over n where N and N integers with no common factors.
Now, do you agree? But if f if Root two can be written as a fraction of integers,
then it is possible to write it as a fraction of integers in which the numerator and the denominator have no common factors, right?
You just cancel them. OK. Square both sides of this and you get two equals n squared over in square.
Multiply both sides by n squared. You get to square and then square.
So it follows that and square. There's an even number. Yeah.
Now, if the square is even the square root must be even two because any old number has an odd square.
If you take an old number, we're talking about integers here, say to K +1 and you square it,
you get for K squared plus Fourcade plus one, which is creating an odd number.
So if you've got an even square, you must have an even number that's being squared.
So it follows that n we had n squared is even now we know that Emmys even but his name is even n can be written as two K for some K integer.
And that means that m squared is four k squared and we know that m squared is to n squared.
It follows then that n squared is going to be even as well, from which it follows by the previous reasoning.
The end is even so, we end up with the conclusion Emmys even and then is even which is a contradiction
because we started with the assumption that men have no factor in common.
Turns out they have to have two income.
So if we start with the assumption that the square root of two can be written as a fraction of integers, we end up contradicting that assumption.
Therefore, Root two is not a rational number.
OK, so that shows that the fractions of integers do not exhaust all the numbers, there are numbers like root to which cannot be written in that form.
But the square root of two is at least an algebraic number.
The square root of two is a number that can be written as a solution of an equation in one variable with integer coefficients.
Right. So x squared equals to the solution.
Root two is called an algebraic number.
It's not rational, but it's algebraic. An irrational number is straightforwardly algebraic and over.
B is the solution of the equation. B X equals a any square root or n through to the rational number is algebraic.
As we've seen in the case of square root of two. So we've been forced to acknowledge that there are numbers beyond rational numbers.
Not every number can be written as a fraction of integers.
OK, let's accept then, that there are these other numbers which are solutions two equations with integer coefficients.
And will that suffice? Well, maybe it will.
Maybe it won't. We'll come to that shortly. But let's show for good measure that the algebraic numbers are innumerable numeral.
So just like the rational numbers, we can actually put all the algebraic numbers, which include the rational numbers into a list to prove this.
Let's suppose we got an algebraic equation. Here's a general form of an algebraic equation.
And what are we going to do? Is define the rank of the equation as this.
OK, now don't worry about this. All right, just just take this as a useful way of listing all these equations.
So what we want is a number which indicates, as it were, how big the numbers are in this equation.
So what we're doing, we taking them the constant turn and taking it to absolute value so we don't care whether it's positive or negative.
The positive value of the coefficient of X, the positive value of the coefficient of X squared, etc., etc.,
etc. We're adding the absolute value of all the coefficients together and then adding to that the highest degree of X.
OK. That gives us a number. It's clearly going to be a positive number.
Yeah. Very sensible equation can't be negative because we're taking absolute advantage of time.
Now here's the crucial thing. Suppose you take all the equations that have rank three.
Say there will be a finite number of those and you can list what they are.
So and we can order them first by end, then by the various coefficient.
So this is easiest understood if we take examples. So these equations have rank two because this has coefficients minus one and zero.
So the absolute value of minus one is one at zero.
We get one and the highest degree of X is one, so we get one plus one to rank two.
This has rank two as well. Those are the only two equations of rank two, right?
One of them has a coefficient of minus one before x one has a coefficient of one.
For equations of rank three, there are more of those, including a couple of quadratic.
In order to get rank three here, since the highest degree of X is two, we're only allowed one as the coefficient, so it better be minus one or one.
So those are the only two quadratic that get rank three.
But you can see we're getting more of the linear equations.
You get the idea. So, so the rank simply measures as it were the size of the coefficients of the equation linked with the degree of the equation.
And I haven't. I've just started off with rank four. OK.
So we've got a way of listing all the algebraic equations.
First of all, we list those with rank two, then those with rank three, then those with rank four, then between five and within each group.
We list them in the order just specified, awarded first by and then by and then by eight minus one and so on, and finally by a zero.
OK, so imagine we've got this infinite list of all the all the possible algebraic equations.
Now, every algebraic equation has it most in solutions.
So if any is the highest power of X in the equation, you know, quadratic equation can have at most two solutions.
Imagine solving all these equations, those that are solvable at any rate and listing the roots of the equation in numerical order.
I've mentioned here you could put complex numbers into this if you want, but we're not thinking about complex numbers here.
So now we can make a list that will include all the algebraic numbers because we've got this list of all the algebraic equations.
And then for each of those equations, in order, we list all of the roots of that equation again in numerical order and every single algebra number,
every number, which is a root as of any one of those equations will appear somewhere in that infinite list.
So as before, we can define a suggestion and QED quod erat demonstrated to me proves what we set out to prove.
You can actually produce an infinite list of algebraic numbers, which contains every single algebraic number.
So there are no more algebraic numbers than there are integers.
OK, so again, you might think maybe this isn't a surprise.
Infinity is infinity.
Maybe all infinite sets are of the same size, but now we come to transcendental numbers, and these are irrational numbers that are not algebraic.
Okay, piety of the most famous examples. But if trigonometric functions often yield them as well.
Notice, by the way, that when we're dealing with trigonometric functions,
we standardly think of the angle in radians, not in degrees, so that that fundamentally changes things.
OK. So there are transcendental numbers.
There are numbers that are not roots of a algebraic equations.
Surprisingly, although Pi and E may be the only familiar ones or the most familiar ones.
It turns out that to a rough approximation, all numbers are transcendental.
So this is due to a proof by Cantor, which we now going to see famous dive in the truth.
So Cantor showed that real numbers in general cannot be put into an infinite list.
Rational numbers can, algebraic numbers can, real numbers can't.
And again, we've got a proof by reductio out absurdum.
We start with the assumption that they can be put into a list and then we show that that's impossible.
So let's suppose that the set of real numbers were in fact innumerable could be put into an infinite list.
In that case, it would A44 why it would be true that all the real numbers between zero and one could be put into an infinite list.
Yes. Let's just restrict our attention to that small subset of the real numbers between zero and one.
Ignore all the infinite others. Imagine that they have been put into an infinite list.
So here's the list. That's the first of them.
Second, third, fourth, fifth and so on. And one is the first digit after the decimal point of the first number in the list.
8.4 is the fourth digit off the decimal point of the second number in the list.
And so everyone happy with that. So now look down the long diagonal there.
What I've done, I've chosen the first digit of the first number in the list.
The second digit of the second number of the list. The third digit at the third number in the list and so on.
What we're now going to do is construct a number, a decimal number, which differs from each of those.
So in the fourth place, we're going to choose a digit, which is different from eight four four in the fifth place.
We're going to choose a digit different from a five, five and so on.
Do you agree that if we do that, we will end up with a number which differs from every single number in the list
because it will differ from the number in the eighth place after the decimal point?
OK, so we can define this number, we can call it number C in honour of Cantor.
Let's just say that if the end digit of the ninth number in that list is five,
then the digit of our specially defined number is going to be made zero.
But otherwise, we're going to make it five. So we're going to we're defining a number here.
Every single digit is either going to be zero or five.
But we fixed it so that if the f number in the list happens to have a five at the crucial point, we have a zero.
And if that number has a zero, we have a five. In fact, if it has anything else, we have a thought.
So the number that we defined is going to differ from the entry number in the list at the ninth decimal point.
So effectively what we're doing, we're writing out a number where if you go to say the fourth digit of that number,
you can be quite sure that it will be different from the fourth digit of the fourth number on the list.
It will therefore in the same way it will differ at some point from every single number in that list.
But we started off with the assumption that every single real number is in that list.
We've just defined a number which a real number, which is not in that list.
So we've got a contradiction. This is a for obvious reasons, called a diagonal argument.
It's an argument that works by taking two dimensions of variation and providing some construction that runs down the diagonal.
We're going to be looking at some other diagonal arguments. A very famous one is the proof of cantors theorem.
For any set, the powerset of a that is the set of subsets of a always has a greater carnality than a itself.
So suppose, for example, you've got three people, how many different sets of those three people can you make?
Well, the first person can either be in or out of the set.
Yeah. So that's two possibilities for each of those possibilities.
The second person can be in or out of the set. So that gives you two times two.
And for each one of those possibilities, the third person can either be in or out of the set, which gives you eight.
Yeah. So you get eight subsets. So in general, with a finite set, if you've got an elements,
the number of subsets is two to the end because basically every new element doubles up the possible subsets that you can have.
Bear in mind, the null set is a subset of the set itself is a subset. OK.
So with finite sets, it's very obvious that the set of subsets in this case, the set of those eight subsets has more elements than the initial set.
The set of three is that true for infinite sets?
Will Cantor showed that it was the very nice proof, so let's suppose, first of all, as in innumerable sets.
In other words, it's a set where we can list all the elements of the set in a list, an infinite list fine.
But those are the elements of the set nested along the top.
And let's suppose that we can define a subjective function from each element of that list,
which which hits as it were every single subset of that set.
So if a value one will be some subset of that set and it will be the one to which A1 is mapped by the suggestion.
So we've got a subjective function. It maps each element of the set onto some subset of the set, and it's a subjective function,
which means that every single subset gets hit at least once.
Is that OK? Now imagine then that we set up a table like this where here we've got the subset that to which A1 matches.
Here's the subset to which a two maps. Here's the subset to which a three maps.
And so and we've put a tick or a cross to indicate which elements of the set are actually in that subset.
OK. Don't imagine there's any authority in the ticks and crosses I've put here.
It's entirely arbitrary. OK? I've just said, let's suppose that the first four to have this pattern, they might have a completely different pattern.
It doesn't matter what we're we going to do is go down the diagonal,
look at that diagonal and suppose we consider the set of elements that have crosses down the long diagonal.
OK, that's in this case. That's an A3 and A4.
They're the ones that have crosses down the long diagonal.
In other words, those are the ones that do not belong to the set to which they are mapped by our surge action.
Imagine that we take all of those elements which have a cross in the long diagonal of the former subset of them,
so we form the set of all the elements which are not contained in the subset to which they are mapped.
By similar reasoning to cantors, diagonal of the the diagonal arguments about real numbers,
and we have thus constructed a subset which is not present in the list.
So again, we get a contradiction. It is not possible to have a subjective function from an infinite set when the any set of innumerable,
any innumerable set of objects onto the subsets of that set.
That's quite tricky. This is something that to it's worth thinking about.
You know, the the text of the slides actually explains it.
If you find it difficult as some eyes suggest you do, which isn't surprising to try with some examples with small sets, see how they work out.
See how you fill in the grid. And that will probably help.
Now, in fact, the proof of counsel's theorem doesn't rely on innumerable.
Here we did.
I mean, the only I was only able to set up this grid on the assumption that our objects here, the set of a was innumerable, but quite generally,
where a is any set at all innumerable or not,
we can think of the set of elements of a which are not elements of the subset to which they have been mapped.
And in fact, we get exactly the same kind of contradiction.
It's this this subset, the set of elements which do not belong to the subset to which their map cannot be in the range of function f,
because if X is fixed for any X, then if X is it a subset is an element of X.
It turns out that X also cannot be a sub in an element to this.
So this implies that the power sets of an infinite set must have a card analogy strictly greater than that set.
And I'm going to refer you here to Petzold, who draws some lessons from this about the commonality of the continuum and other infinite numbers.
I mean, effectively, this means that if you start with some set and then you take the set of subsets,
you have to move to a larger number, whether that set was finite or infinite.
So if you start with a set of natural numbers and then you take the set of some subsets of natural numbers, you must get to a greater infinity.
And if you then take the set of subsets of that set, you must get to a greater infinity again and so on and so on and so on.
So not only do we have at least two infinities, namely the number of natural numbers and the number of rational numbers.
Actually, there's an infinite number of infinity.
You can see why some people were rather dubious about cantors theory, but turns out to be to all make sense.
You know, you can't generate contradictions from it. So it's very widely accepted.
Finally, I'm going to end with an important consequences consequence of this for philosophy of logic and mathematics.
Really, very, very important indeed. Bertrand Russell contemplated cantors arguments and you can see how close cantors argument gets to this,
and hence Russell thought about the set of all sets that are not members of themselves.
So, for example, take the set of cats. The set of cats is not itself a cat, so it's not a member of itself.
Great. Whereas the set of all sets is itself a set and is therefore an element of itself.
Take all the sets that are like the set of cats,
all the sets that are not members of themselves think the set of everything that is not an element of itself doesn't mean it can't be a set.
But if it is a set, it's not an element of itself, is it?
Or is it not an element of itself? Well, if it is an element of itself, then it's not an element of itself.
If it's not an element of itself, then it is an element of it. So you get a contradiction.
It's rather similar to the paradox of the village barber who shapes all and only those men who do not shave themselves.
Does he shave himself? OK, well, you can get round that one because you can say either there just is no such barber.
It's an impossibility. Or you can more coming in to say, Well, maybe the barber was a woman.
But the problem with the set of all sets that are not members of themselves is that it seems to be defined in such a straightforward way that to say,
Oh, there's no such thing makes us wonder, Well, why not?
We know what it is for a set to be a member of itself.
Why can't we simply take all the assets that are not members themselves and put them in a big set?
What stops us doing that? Well, it leads to a contradiction. Yeah, OK.
It leads to a contradiction. But if that leads to a contradiction based on such straightforward ideas, where else might there be contradictions?
And you can see the effect that this had on Friday, Russell wrote to Fraser in 1982.
Explaining the paradox, Schrager wrote back to Russell six days later.
So he probably only just received it. Your discovery of the contradiction has surprised me beyond words, and I should almost like to say,
let me thunderstruck because it is rocked the ground on which I'm meant to build arithmetic.
So there we're going to end today. Next lecture, we will see another phenomenal rocking of the ground in the form of girdles theorem.
See you then. Thank you.