Turing 2018/1: Types of number, Cantor, infinities, diagonal arguments

1
00:00:02,040 --> 00:00:08,940
Well, welcome everybody to the first lecture on Alan Turing on computer ability and intelligence.

2
00:00:08,940 --> 00:00:18,960
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,

3
00:00:18,960 --> 00:00:23,280
which is the degree programme towards which these lectures around.

4
00:00:23,280 --> 00:00:28,260
Anyone here who's not doing computer science philosophy? You're very welcome to.

5
00:00:28,260 --> 00:00:33,300
It's a very interesting topic, and I hope you enjoy the lectures.

6
00:00:33,300 --> 00:00:41,250
As you'll be aware, they're being recorded this year. That's so that they're available in the future.

7
00:00:41,250 --> 00:00:45,760
So for that reason, I'm not going to be taking any questions during the lectures.

8
00:00:45,760 --> 00:00:52,680
But if any problems arise, I will be organising classes during the term for anyone who needs them.

9
00:00:52,680 --> 00:01:01,200
Okay, those doing computer science philosophy later in the term will be having tutorials on the stuff to do with philosophy of mind.

10
00:01:01,200 --> 00:01:07,670
And so when you'll be writing essays and I'll give you details about that later.

11
00:01:07,670 --> 00:01:15,200
The role of the course is part of the introduction to philosophy for the prelims course in computer science and philosophy.

12
00:01:15,200 --> 00:01:24,740
And just to get this out of the way, you have a three hour examination and it contains six either all questions on general

13
00:01:24,740 --> 00:01:32,780
philosophy and six questions on curing from which you are expected to choose for.

14
00:01:32,780 --> 00:01:38,300
And you have to do at least one from each section, so you could end up doing one question on curing.

15
00:01:38,300 --> 00:01:49,310
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,

16
00:01:49,310 --> 00:01:54,590
so you'll probably find that the course is quite fruitful from that point of view.

17
00:01:54,590 --> 00:02:04,970
Here's the overall plan of the lectures. Today we'll be talking about types of number about cantor infinities diagonal argument.

18
00:02:04,970 --> 00:02:09,890
Next lecture We're going to be talking about Hilbert programme and girdles theorem.

19
00:02:09,890 --> 00:02:16,310
We won't be going through Girdles Theorem in all detail, but we will be seeing how it works.

20
00:02:16,310 --> 00:02:23,030
The ingenious method by which girdle proved his result, and by then, you'll understand why it's important.

21
00:02:23,030 --> 00:02:29,390
Lecture three to five Focus on the the really main core of the lectures,

22
00:02:29,390 --> 00:02:38,540
which is Alan Turing's 1936 paper on computable numbers with an application to the incidence problem.

23
00:02:38,540 --> 00:02:45,890
Now that was the paper that introduced the Turing machine and hence virtually invented the computer.

24
00:02:45,890 --> 00:02:50,690
We have a set text for that, which makes it feasible to do this.

25
00:02:50,690 --> 00:02:58,790
It's a fiercely difficult paper, but with the help of this book by Charles Petzold, you should, I hope, find it entirely manageable.

26
00:02:58,790 --> 00:03:04,490
Those doing computer science and philosophy, it's probably a good idea to buy this book.

27
00:03:04,490 --> 00:03:11,360
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.

28
00:03:11,360 --> 00:03:17,630
And of course, you shouldn't be doing that with library books. Okay, so that's lecture three to five.

29
00:03:17,630 --> 00:03:23,240
And then in the last three lectures, we'll be looking at Alan Turing's other very famous paper,

30
00:03:23,240 --> 00:03:30,830
the 1950 paper computing machinery and intelligence, and that's the paper that introduced the Turing test.

31
00:03:30,830 --> 00:03:35,810
So that's where we get into stuff from philosophy of mind and so on.

32
00:03:35,810 --> 00:03:39,860
Okay, so I've mentioned the textbook. Here are the details about it.

33
00:03:39,860 --> 00:03:47,420
It really does contain everything you need to know on the background of the 1936 paper that it contains the

34
00:03:47,420 --> 00:03:57,050
actual text of the paper if you see highlighted here in grey so that you can see exactly what Turing wrote.

35
00:03:57,050 --> 00:04:05,720
But it's surrounded by a lot of commentary, which makes it all comprehensible, explains difficulties, explains corrections and so forth.

36
00:04:05,720 --> 00:04:15,560
What I'll be doing in these lectures is giving you, I hope, enough material that will make that paper much more comprehensible.

37
00:04:15,560 --> 00:04:22,010
Even with petzold help, you might find it difficult sometimes to see the wood for the trees in the lectures.

38
00:04:22,010 --> 00:04:28,670
I'm going to be focussing on bits that are particularly difficult and setting the background for that.

39
00:04:28,670 --> 00:04:35,420
OK? Highly recommended reading a couple of books by Andrew Hodges, which are biographical books about Turing,

40
00:04:35,420 --> 00:04:41,300
but obviously also contain quite a lot of stuff that's relevant to what we're going to be talking about.

41
00:04:41,300 --> 00:04:47,510
His mammoth biography from 1983 and very well known.

42
00:04:47,510 --> 00:04:52,970
If you want to read something during the long vacation, maybe that's a good idea.

43
00:04:52,970 --> 00:05:02,180
A much shorter book, just 58 pages is very well worth reading to get a feel for what Turing was about,

44
00:05:02,180 --> 00:05:09,710
and I'll be mentioning this book, which is a huge collection on Turing remarkable value.

45
00:05:09,710 --> 00:05:14,690
It's actually surprisingly cheap for a book of over 900 pages.

46
00:05:14,690 --> 00:05:21,740
So if you're a real enthusiast and you want an absolute doorstop of a book, that's worth considering that you should.

47
00:05:21,740 --> 00:05:30,560
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.

48
00:05:30,560 --> 00:05:36,530
I'll be mentioning next lecture. Okay, so who was Alan Turing?

49
00:05:36,530 --> 00:05:43,220
Well, he was born in 1912, educated at Hazelhurst and Sherburne schools.

50
00:05:43,220 --> 00:05:49,400
His parents were in India, so he was at boarding school.

51
00:05:49,400 --> 00:05:53,960
He formed a close relationship with another lad at the school called Christopher Malcolm.

52
00:05:53,960 --> 00:05:59,030
And both of them applied to read maths at Trinity Cambridge.

53
00:05:59,030 --> 00:06:06,230
Malcolm was accepted. Turing wasn't. But the next year, Malcolm died of tuberculosis.

54
00:06:06,230 --> 00:06:11,810
And it seems they had a very intimate affair. Alan Turing was gay,

55
00:06:11,810 --> 00:06:23,630
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,

56
00:06:23,630 --> 00:06:26,370
the relation between mind and body and so forth.

57
00:06:26,370 --> 00:06:36,710
I mean, so some of this is speculative, but it seems very plausible later in his life, as is well known.

58
00:06:36,710 --> 00:06:41,060
He played a huge role in the war in the Second World War.

59
00:06:41,060 --> 00:06:48,920
He was largely responsible for the techniques by which the Nazi Enigma codes were decrypted,

60
00:06:48,920 --> 00:06:56,360
thus enabling allied shipping to escape the U-boats in the Atlantic without cheering.

61
00:06:56,360 --> 00:07:01,100
It's entirely possible that the war would have gone on a lot longer and been a lot more

62
00:07:01,100 --> 00:07:07,670
difficult to win because without being able to divert the ships around the U-boat packs,

63
00:07:07,670 --> 00:07:14,000
Britain's position would really have been quite perilous in the early 1940s.

64
00:07:14,000 --> 00:07:19,130
This was completely unknown until relatively recently because it was all official secrets,

65
00:07:19,130 --> 00:07:25,880
and Turing was prosecuted for homosexuality in the early 1950s.

66
00:07:25,880 --> 00:07:29,840
And again, nobody knew what a hero he was.

67
00:07:29,840 --> 00:07:41,960
He was forced to take hormone treatment, which had very bad effects on him, and he ended up probably committing suicide in 1954.

68
00:07:41,960 --> 00:07:45,170
He seems to have set it up in such a way that there was a little bit of ambiguity.

69
00:07:45,170 --> 00:07:53,180
He he apparently took a bite out of an apple on which he'd committed suicide cyanide.

70
00:07:53,180 --> 00:07:57,410
But it is possible that he killed himself by mistake.

71
00:07:57,410 --> 00:08:02,960
So a plausible suggestion is that he deliberately set it up that way so that his

72
00:08:02,960 --> 00:08:08,030
mother would be able to believe that he hadn't actually killed himself deliberately.

73
00:08:08,030 --> 00:08:11,810
Anyway, back to his early life, he reapplied to Cambridge.

74
00:08:11,810 --> 00:08:17,450
In 1930, he was accepted for King's College, went up in 1931.

75
00:08:17,450 --> 00:08:25,340
He took his part to try pass exams in 1934, passed with distinction and got a research student ship.

76
00:08:25,340 --> 00:08:33,920
Then the next year, he was elected to a three year fellowship, so he obviously did extremely well in maths at Cambridge.

77
00:08:33,920 --> 00:08:43,010
By 1935, he was a fellow and he attended a Part three course given by Max Neumann on the foundations of mathematics.

78
00:08:43,010 --> 00:08:49,550
And this, again, is something that seems to have had quite a profound effect on him to understand why we

79
00:08:49,550 --> 00:08:54,560
need to look a bit at one of the greatest mathematicians of the early 20th century.

80
00:08:54,560 --> 00:09:05,420
David Hilbert Hilbert was born in Konigsberg, the city with which Immanuel Kant is greatly associated.

81
00:09:05,420 --> 00:09:12,320
He was perhaps the most influential mathematician of the early 20th century, partly because he set the agenda.

82
00:09:12,320 --> 00:09:18,200
He made a point of saying, Here are big problems on which we should focus.

83
00:09:18,200 --> 00:09:25,880
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,

84
00:09:25,880 --> 00:09:31,550
the the politeness, the approach, the intuition is the approach, the formalist approach.

85
00:09:31,550 --> 00:09:43,730
And Hilbert is very much a founder of the last of these, the formalised approach CS mathematics as involving manipulations of symbols.

86
00:09:43,730 --> 00:09:50,870
So we discuss proofs and things in terms of their syntactic properties, and we'll see that playing a role later,

87
00:09:50,870 --> 00:09:59,540
especially next time at the 19:00 Paris International Conference of Congress of Mathematicians.

88
00:09:59,540 --> 00:10:07,320
He famously listed prominent unsolved problems of mathematics, including this one,

89
00:10:07,320 --> 00:10:13,430
the tenth problem determination of the solve ability of a Die-Off and time equation.

90
00:10:13,430 --> 00:10:17,660
Now I put this in, partly because Petzold, in his book,

91
00:10:17,660 --> 00:10:24,800
discusses these at some length and very interestingly, so I recommend that you go and look at his book.

92
00:10:24,800 --> 00:10:39,170
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?

93
00:10:39,170 --> 00:10:50,510
And trying to devise a process by which you can tell whether there is a solution or not is a major problem.

94
00:10:50,510 --> 00:10:56,630
The the equations were named after an Alexandrian mathematician, Dave Fanta.

95
00:10:56,630 --> 00:11:05,590
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.

96
00:11:05,590 --> 00:11:12,880
And does this have any integer solutions when N is greater than two?

97
00:11:12,880 --> 00:11:17,350
I mean, it clearly does when any equals one.

98
00:11:17,350 --> 00:11:23,560
It clearly does. When any calls to, for example, three squared plus four squared equals five squared.

99
00:11:23,560 --> 00:11:27,820
Does it have any when an equal three or four or more than that?

100
00:11:27,820 --> 00:11:33,040
And for many years, this was a huge puzzle.

101
00:11:33,040 --> 00:11:44,770
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,

102
00:11:44,770 --> 00:11:52,870
but I don't have room to write it down in the margin. And this intrigued future generations of mathematicians.

103
00:11:52,870 --> 00:12:00,550
They all tried to discover or rediscover this proof that Thelma had supposedly discovered.

104
00:12:00,550 --> 00:12:11,320
It actually took a huge amount of work by lots of mathematicians and eventually was proved by Andrew Wiles in 1995.

105
00:12:11,320 --> 00:12:19,000
I think most people think that Sam probably found an ingenious proof that applied to certain cases,

106
00:12:19,000 --> 00:12:30,920
but not to all because proving it as a general theorem is actually extraordinarily difficult requires very sophisticated mathematics.

107
00:12:30,920 --> 00:12:36,920
OK, let's have a quick look at some of Gilbert's other problems, apart from the one concerning Di Fantine equations.

108
00:12:36,920 --> 00:12:44,420
We've got the continuum hypothesis that's a very important problem in philosophy of mathematics.

109
00:12:44,420 --> 00:12:49,040
Again, here on, I'm not going to discuss it, but I'm just going to refer you to Petzold.

110
00:12:49,040 --> 00:12:53,660
That's something he discusses and is well worth knowing about proving the

111
00:12:53,660 --> 00:12:59,630
consistency of the axioms of arithmetic that something will be coming back to,

112
00:12:59,630 --> 00:13:10,310
particularly next time. The Riemann hypothesis and Goldmark conjecture gold, but conjecture is a favourite of philosophers.

113
00:13:10,310 --> 00:13:23,090
It's the claim that any even number greater than two can be expressed as the sum of two prime numbers.

114
00:13:23,090 --> 00:13:29,450
Philosophers love it because it hasn't yet been proved.

115
00:13:29,450 --> 00:13:39,860
So when I started out studying maths at Oxford quite a long time ago, there were three of these very famous unsolved problems,

116
00:13:39,860 --> 00:13:44,360
and one of them was the full-color theorem, which got proved the subsequent year.

117
00:13:44,360 --> 00:13:49,160
One of them was Fermat's Last Theorem, which, as I say, was proved in 1995.

118
00:13:49,160 --> 00:13:54,620
I'm hoping that Girlboss conjecture will last a bit longer so that we philosophers can continue to give.

119
00:13:54,620 --> 00:13:59,220
It is a nice example. OK.

120
00:13:59,220 --> 00:14:09,030
Let's come to here. But the challenge is that Hilbert set, he set out a programme in philosophy of mathematics.

121
00:14:09,030 --> 00:14:15,390
He wanted to establish foundations for mathematics, which were provably consistent.

122
00:14:15,390 --> 00:14:24,660
So starting from axioms which were ideally self-evident, clearly true and manifestly consistent.

123
00:14:24,660 --> 00:14:32,730
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.

124
00:14:32,730 --> 00:14:37,410
There's no inconsistency there and a set of axioms from which in principle,

125
00:14:37,410 --> 00:14:43,440
all mathematical truths can be deduced by the standard rules of First Order predicate logic.

126
00:14:43,440 --> 00:14:51,960
So I assume you've all learnt, first of all, the predicate logic, standard logic that we inherited from Fraga.

127
00:14:51,960 --> 00:15:06,300
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?

128
00:15:06,300 --> 00:15:09,930
A related problem, the incidents problem,

129
00:15:09,930 --> 00:15:17,130
the problem that Alan Turing was going to be concerned with the decision problem, can an effective procedure be devised,

130
00:15:17,130 --> 00:15:26,310
which would demonstrate in a finite time with any given mathematical proposition is or is not provable from a given set of axioms?

131
00:15:26,310 --> 00:15:36,930
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.

132
00:15:36,930 --> 00:15:42,690
We also want to have a procedure which in a finite time is going to tell us as it were,

133
00:15:42,690 --> 00:15:48,240
mechanically simply by applying this procedure in a mechanical way to tell us

134
00:15:48,240 --> 00:15:53,950
whether any given proposition is or is not provable from the set of axioms.

135
00:15:53,950 --> 00:16:03,180
Okay. Some of the relations between those will become much clearer next time when we talk about girdle.

136
00:16:03,180 --> 00:16:11,070
The 1936 paper, which is said, the sort of central topic of these lectures.

137
00:16:11,070 --> 00:16:15,570
Second, the decision problem, the entitlements problem.

138
00:16:15,570 --> 00:16:20,370
It showed, in fact, that there could be no such procedure.

139
00:16:20,370 --> 00:16:26,490
But the paper starts, as the title suggests, from the concept of a computable number.

140
00:16:26,490 --> 00:16:33,990
So then the paper the ultimate aim of Turing's paper is to settle the incidence problem.

141
00:16:33,990 --> 00:16:39,510
It gets there by talking about a certain kind of number, a computable number.

142
00:16:39,510 --> 00:16:48,900
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.

143
00:16:48,900 --> 00:16:54,990
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.

144
00:16:54,990 --> 00:16:57,390
We'll talk about completeness and consistency.

145
00:16:57,390 --> 00:17:08,700
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.

146
00:17:08,700 --> 00:17:18,240
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.

147
00:17:18,240 --> 00:17:25,530
So here are some set standards used in mathematics the set of natural numbers one two three four You're studying computer science.

148
00:17:25,530 --> 00:17:32,310
You've probably been told the first natural number zero. I'm going to take the first natural number to be one because zero.

149
00:17:32,310 --> 00:17:37,770
Isn't that natural? Is it real? OK? It's actually pretty harmless for most contexts.

150
00:17:37,770 --> 00:17:41,520
Whether you take the natural numbers are starting from zero or one.

151
00:17:41,520 --> 00:17:52,350
We're going to go with one the set of integers from Xylem and German of the symbol Zaidi's commonly used for that.

152
00:17:52,350 --> 00:17:59,130
The set of integers obviously is both positive and negative, and zero the set of rational numbers.

153
00:17:59,130 --> 00:18:05,880
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.

154
00:18:05,880 --> 00:18:15,690
Obviously not zero on the bottom. And that set is commonly denominated Q, probably for quotient.

155
00:18:15,690 --> 00:18:25,320
And then there are real numbers, say R, and real numbers essentially correspond to to all the non complex numbers,

156
00:18:25,320 --> 00:18:32,160
all the numbers that we normally handle when we're doing things like calculus or trigonometry and so forth.

157
00:18:32,160 --> 00:18:41,370
Those are all real numbers now. Real numbers include irrational numbers, numbers that cannot be written as a fraction of integers,

158
00:18:41,370 --> 00:18:48,100
algebraic numbers which are roots of algebraic equations and transmittal numbers, which on either of those?

159
00:18:48,100 --> 00:18:55,350
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.

160
00:18:55,350 --> 00:19:02,920
Some of what we do could apply equally to complex numbers, but they're not really relevant to the business here.

161
00:19:02,920 --> 00:19:09,010
OK. Now, these are obviously all infinite sets.

162
00:19:09,010 --> 00:19:17,980
There's an infinite number of natural numbers. There's an infinite number of rational numbers and so forth.

163
00:19:17,980 --> 00:19:24,820
But what Georg Cantor did was show that not all of these infinities are the same.

164
00:19:24,820 --> 00:19:29,710
We're going to end up with more than one type of infinity.

165
00:19:29,710 --> 00:19:35,200
So that's the theory of Tehran's finite cardinal numbers.

166
00:19:35,200 --> 00:19:46,150
And the key to understanding how this works is a principle that's to my mind, somewhat ironically known as Hume's principle.

167
00:19:46,150 --> 00:19:56,440
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.

168
00:19:56,440 --> 00:20:02,740
So there's an irony in this absolute key principle in the philosophy of mathematics being named after him.

169
00:20:02,740 --> 00:20:13,630
But the reason is that Fraga, in foundations of arithmetic, pointed out that Hume had enunciated this principle when two numbers are so combined,

170
00:20:13,630 --> 00:20:20,770
as the one has always a unit answering to every use of the other, we pronounce them equal.

171
00:20:20,770 --> 00:20:25,570
OK, so let's see what's being said here.

172
00:20:25,570 --> 00:20:34,930
The idea is that if you have two sets of objects and you can put those two sets in one to one

173
00:20:34,930 --> 00:20:44,350
correspondence so that each unit in one of the sets corresponds to one and only one unit in the other set,

174
00:20:44,350 --> 00:20:48,220
then you can say that the two sets are equally numerous.

175
00:20:48,220 --> 00:20:52,150
They have the same number of elements.

176
00:20:52,150 --> 00:20:59,670
Mathematically, we well, first of all, we use a technical term called finality for the number of elements in a set.

177
00:20:59,670 --> 00:21:07,660
And this is meant to be a generalisation so that we can extend it to infinite numbers, not just finite.

178
00:21:07,660 --> 00:21:17,290
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.

179
00:21:17,290 --> 00:21:25,800
So let's just get clear what objective function is a function that is both injected and surge active.

180
00:21:25,800 --> 00:21:29,230
So and this is an example of an injected function here.

181
00:21:29,230 --> 00:21:40,540
We've got the domain here, we've got the code domain and you can see that this object is the function of this.

182
00:21:40,540 --> 00:21:44,470
This is the function of this or, as we say, the image of it.

183
00:21:44,470 --> 00:21:54,760
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.

184
00:21:54,760 --> 00:21:58,630
You never get two arrows going to the same point. OK.

185
00:21:58,630 --> 00:22:04,510
That's an injected function. Here's an example of a subjective function.

186
00:22:04,510 --> 00:22:11,140
Here you can see this one is not injected. We sometimes do have two arrows going at the same point.

187
00:22:11,140 --> 00:22:17,710
But there is no object within the code domain, which is not hit by at least one arrow.

188
00:22:17,710 --> 00:22:34,060
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,

189
00:22:34,060 --> 00:22:39,730
then this set must have at least as many elements as this one.

190
00:22:39,730 --> 00:22:45,780
Yeah. Because there has to be a separate element for every act.

191
00:22:45,780 --> 00:22:53,550
Whereas if we have a subjective function, that means every element here gets hit by at least one arrow,

192
00:22:53,550 --> 00:22:59,850
then this set must have at least as many elements as that one agree.

193
00:22:59,850 --> 00:23:06,930
So if we have objective function, a function that is both injected and surgically, if a one to one correspondence,

194
00:23:06,930 --> 00:23:11,700
it follows that the two sets must have the same commonality, the same number of elements.

195
00:23:11,700 --> 00:23:20,940
Now, essentially, what we do when we talk about infinite sets is we take that principle, which is so natural with finite sets,

196
00:23:20,940 --> 00:23:30,300
and we extend it and apply it to infinite sets and cantors were basically comes from doing that.

197
00:23:30,300 --> 00:23:37,260
OK, now when we're dealing with infinite sets rather than attempting to define objection,

198
00:23:37,260 --> 00:23:48,300
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.

199
00:23:48,300 --> 00:23:53,100
In other words, every element of B gets hit by an arrow.

200
00:23:53,100 --> 00:23:59,460
Then we can say that the commonality of pay must be at least as great as the code Nancy at the OK.

201
00:23:59,460 --> 00:24:02,190
And that's that's normally enough for our purposes.

202
00:24:02,190 --> 00:24:09,540
We don't go to the trouble of trying to define objection a one to one correspondence that in many cases,

203
00:24:09,540 --> 00:24:15,780
would be a lot more complicated and unnecessarily so we'll see that quite shortly.

204
00:24:15,780 --> 00:24:27,040
Now, clearly, if you can define a subjection both ways, then on Hume's principle, the two commonalities should be the same.

205
00:24:27,040 --> 00:24:36,580
OK, now one very important special case, if a suggestion can be defined from the set of natural numbers to any set,

206
00:24:36,580 --> 00:24:41,620
then we say that that stuff is countable or innumerable, in other words.

207
00:24:41,620 --> 00:24:49,090
So we've got a function that goes from the natural numbers. Each natural number is mapped onto an element of this set.

208
00:24:49,090 --> 00:24:55,150
Every single element of that set is hit by at least one natural number, at least one of these arrows from a natural number.

209
00:24:55,150 --> 00:25:00,070
Right. So you can imagine in principle,

210
00:25:00,070 --> 00:25:09,760
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.

211
00:25:09,760 --> 00:25:13,660
Now, some of those elements may occur multiple times in the list.

212
00:25:13,660 --> 00:25:18,130
That doesn't matter. We've said we're going to make do with a surge action.

213
00:25:18,130 --> 00:25:27,070
But every single element of that set should be there somewhere in the list if we have correctly defined as objective function.

214
00:25:27,070 --> 00:25:32,470
So we can enumerate the list in the sense of listed in principle because it's infinite.

215
00:25:32,470 --> 00:25:37,840
So we can't actually in practise, but in principle we can. OK.

216
00:25:37,840 --> 00:25:43,540
I've already thought about that. So one of the results that Cantor proved, rather surprisingly,

217
00:25:43,540 --> 00:25:49,390
is that the set of rational numbers and the set of algebraic numbers are both innumerable.

218
00:25:49,390 --> 00:26:03,850
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.

219
00:26:03,850 --> 00:26:11,770
If you take a decimal number, a number is rational if and only if that decimal eventually recurs.

220
00:26:11,770 --> 00:26:17,200
So, for example, three point not not not not not not more recurring.

221
00:26:17,200 --> 00:26:28,660
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.

222
00:26:28,660 --> 00:26:35,680
All of these are rational numbers. Now, it's actually pretty easy to show this.

223
00:26:35,680 --> 00:26:39,820
Take that last example nought point three six seven three six seven three six seven,

224
00:26:39,820 --> 00:26:46,510
etc. You can see that that is actually the sum of the geometric series.

225
00:26:46,510 --> 00:26:54,190
OK, you've got 367 over a thousand. That's that Mate Plus three, six seven over a million.

226
00:26:54,190 --> 00:27:00,370
That's that plus three six seven over a billion, which is that the and so on.

227
00:27:00,370 --> 00:27:09,550
So you've got a series in which each each item in the series is 1000 less than the item before.

228
00:27:09,550 --> 00:27:20,470
And you can easily that some geometric geometric progression using this formula, the first element divided by one minus the common ratio.

229
00:27:20,470 --> 00:27:27,160
And that means that some of that will be 367 over 9-9-9.

230
00:27:27,160 --> 00:27:35,320
OK. So any recurring decimal basically is going to be a rational number.

231
00:27:35,320 --> 00:27:46,690
When we're talking about irrational numbers, we're talking about decimals that go on and on forever, but do not actually recur.

232
00:27:46,690 --> 00:28:01,660
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.

233
00:28:01,660 --> 00:28:05,800
Let's just talk about positive integers for the moment.

234
00:28:05,800 --> 00:28:13,120
One two three four five six seven And so between one and two, there are zillions of rational numbers, right?

235
00:28:13,120 --> 00:28:18,610
One followed by any proper fraction you get a mention is going to be a rational number.

236
00:28:18,610 --> 00:28:24,760
You know, one and seven twelfths or whatever is going to be a rational when you've got all these huge number of rational

237
00:28:24,760 --> 00:28:29,530
numbers between one and two and then you've got the same number between two and three and three and four.

238
00:28:29,530 --> 00:28:39,700
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?

239
00:28:39,700 --> 00:28:40,720
Well,

240
00:28:40,720 --> 00:28:55,180
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.

241
00:28:55,180 --> 00:29:01,960
OK. So you can see that the first row has a denominator of one.

242
00:29:01,960 --> 00:29:10,150
The second row has a denominator of two. Third row has to nominate the three, and so the numerator is are in the column.

243
00:29:10,150 --> 00:29:14,080
So the first column has a numerator of one.

244
00:29:14,080 --> 00:29:18,250
The second column has a numerator to the third column as a new range of three.

245
00:29:18,250 --> 00:29:29,410
And so every fraction of positive integers is going to occur somewhere in that array.

246
00:29:29,410 --> 00:29:38,260
Agreed. And moreover, whatever fraction you care to name, it's actually pretty easy to say where in that array it look.

247
00:29:38,260 --> 00:29:49,780
So there's no mystery here. OK, now what we do, we put these fractions in a sequence starting from here.

248
00:29:49,780 --> 00:29:57,160
Then that one, then that one in that one, then that one in that one following the red line.

249
00:29:57,160 --> 00:30:09,520
And you can see that if we carry on in that pattern sooner or later, every single fraction in that array will be taken.

250
00:30:09,520 --> 00:30:20,320
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.

251
00:30:20,320 --> 00:30:28,720
So we've defined a suggestion, a suggestion from the natural numbers to the fractions.

252
00:30:28,720 --> 00:30:31,690
I've not spelt it out, but it's implicit here.

253
00:30:31,690 --> 00:30:40,180
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

254
00:30:40,180 --> 00:30:51,460
simply taking any natural number and mapping it to whichever fraction occurs at that point along the the red line.

255
00:30:51,460 --> 00:30:56,500
So it turns out you can put all the rational numbers in a list.

256
00:30:56,500 --> 00:31:06,220
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.

257
00:31:06,220 --> 00:31:12,540
You can define this objection, so we list all of the fractions.

258
00:31:12,540 --> 00:31:18,490
And that's the start of it. Our suggestion maps one to the first of these two to the second three to the third.

259
00:31:18,490 --> 00:31:28,570
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.

260
00:31:28,570 --> 00:31:37,690
I mean, consider the fraction one over three. That's the same as two over six three overnight for over 12.

261
00:31:37,690 --> 00:31:45,700
So you've got this amazing result that that a list in which every single possible fraction

262
00:31:45,700 --> 00:31:54,400
occurs an infinity of times still contains no more elements than the number of natural numbers.

263
00:31:54,400 --> 00:31:58,990
You might be wondering what happens with negatives? Well, if you want to include negative fractions, you just alternate.

264
00:31:58,990 --> 00:32:06,410
Okay? It just means the list will be spaced out twice as much.

265
00:32:06,410 --> 00:32:14,450
OK, so a natural thought at this point would be, well, maybe it's not so surprising.

266
00:32:14,450 --> 00:32:21,320
OK. I mean, infinity is infinity. You've got an infinite number of natural numbers, an infinite number of rational numbers.

267
00:32:21,320 --> 00:32:26,160
Why should it be a surprise that these come out to be the same?

268
00:32:26,160 --> 00:32:37,830
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,

269
00:32:37,830 --> 00:32:46,260
perhaps it's a beautiful proof, I think really quite elegant, and I think it dates back to Euclid.

270
00:32:46,260 --> 00:32:52,710
Square two cannot be expressed as a fraction of integers. The square root of two is not a rational number.

271
00:32:52,710 --> 00:33:03,300
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.

272
00:33:03,300 --> 00:33:08,820
Now, do you agree? But if f if Root two can be written as a fraction of integers,

273
00:33:08,820 --> 00:33:15,690
then it is possible to write it as a fraction of integers in which the numerator and the denominator have no common factors, right?

274
00:33:15,690 --> 00:33:24,540
You just cancel them. OK. Square both sides of this and you get two equals n squared over in square.

275
00:33:24,540 --> 00:33:28,620
Multiply both sides by n squared. You get to square and then square.

276
00:33:28,620 --> 00:33:34,440
So it follows that and square. There's an even number. Yeah.

277
00:33:34,440 --> 00:33:44,350
Now, if the square is even the square root must be even two because any old number has an odd square.

278
00:33:44,350 --> 00:33:49,920
If you take an old number, we're talking about integers here, say to K +1 and you square it,

279
00:33:49,920 --> 00:33:54,090
you get for K squared plus Fourcade plus one, which is creating an odd number.

280
00:33:54,090 --> 00:33:59,430
So if you've got an even square, you must have an even number that's being squared.

281
00:33:59,430 --> 00:34:10,320
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.

282
00:34:10,320 --> 00:34:17,580
And that means that m squared is four k squared and we know that m squared is to n squared.

283
00:34:17,580 --> 00:34:25,560
It follows then that n squared is going to be even as well, from which it follows by the previous reasoning.

284
00:34:25,560 --> 00:34:31,170
The end is even so, we end up with the conclusion Emmys even and then is even which is a contradiction

285
00:34:31,170 --> 00:34:35,500
because we started with the assumption that men have no factor in common.

286
00:34:35,500 --> 00:34:38,160
Turns out they have to have two income.

287
00:34:38,160 --> 00:34:51,420
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.

288
00:34:51,420 --> 00:34:56,120
Therefore, Root two is not a rational number.

289
00:34:56,120 --> 00:35:11,030
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.

290
00:35:11,030 --> 00:35:14,780
But the square root of two is at least an algebraic number.

291
00:35:14,780 --> 00:35:23,720
The square root of two is a number that can be written as a solution of an equation in one variable with integer coefficients.

292
00:35:23,720 --> 00:35:30,290
Right. So x squared equals to the solution.

293
00:35:30,290 --> 00:35:34,430
Root two is called an algebraic number.

294
00:35:34,430 --> 00:35:41,630
It's not rational, but it's algebraic. An irrational number is straightforwardly algebraic and over.

295
00:35:41,630 --> 00:35:49,310
B is the solution of the equation. B X equals a any square root or n through to the rational number is algebraic.

296
00:35:49,310 --> 00:35:59,330
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.

297
00:35:59,330 --> 00:36:03,290
Not every number can be written as a fraction of integers.

298
00:36:03,290 --> 00:36:13,230
OK, let's accept then, that there are these other numbers which are solutions two equations with integer coefficients.

299
00:36:13,230 --> 00:36:16,940
And will that suffice? Well, maybe it will.

300
00:36:16,940 --> 00:36:26,960
Maybe it won't. We'll come to that shortly. But let's show for good measure that the algebraic numbers are innumerable numeral.

301
00:36:26,960 --> 00:36:38,270
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.

302
00:36:38,270 --> 00:36:44,810
Let's suppose we got an algebraic equation. Here's a general form of an algebraic equation.

303
00:36:44,810 --> 00:36:49,350
And what are we going to do? Is define the rank of the equation as this.

304
00:36:49,350 --> 00:36:57,410
OK, now don't worry about this. All right, just just take this as a useful way of listing all these equations.

305
00:36:57,410 --> 00:37:04,820
So what we want is a number which indicates, as it were, how big the numbers are in this equation.

306
00:37:04,820 --> 00:37:13,790
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.

307
00:37:13,790 --> 00:37:20,930
The positive value of the coefficient of X, the positive value of the coefficient of X squared, etc., etc.,

308
00:37:20,930 --> 00:37:31,720
etc. We're adding the absolute value of all the coefficients together and then adding to that the highest degree of X.

309
00:37:31,720 --> 00:37:40,250
OK. That gives us a number. It's clearly going to be a positive number.

310
00:37:40,250 --> 00:37:49,780
Yeah. Very sensible equation can't be negative because we're taking absolute advantage of time.

311
00:37:49,780 --> 00:37:57,620
Now here's the crucial thing. Suppose you take all the equations that have rank three.

312
00:37:57,620 --> 00:38:02,930
Say there will be a finite number of those and you can list what they are.

313
00:38:02,930 --> 00:38:08,350
So and we can order them first by end, then by the various coefficient.

314
00:38:08,350 --> 00:38:22,040
So this is easiest understood if we take examples. So these equations have rank two because this has coefficients minus one and zero.

315
00:38:22,040 --> 00:38:26,120
So the absolute value of minus one is one at zero.

316
00:38:26,120 --> 00:38:31,820
We get one and the highest degree of X is one, so we get one plus one to rank two.

317
00:38:31,820 --> 00:38:36,980
This has rank two as well. Those are the only two equations of rank two, right?

318
00:38:36,980 --> 00:38:42,050
One of them has a coefficient of minus one before x one has a coefficient of one.

319
00:38:42,050 --> 00:38:51,350
For equations of rank three, there are more of those, including a couple of quadratic.

320
00:38:51,350 --> 00:39:01,670
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.

321
00:39:01,670 --> 00:39:05,660
So those are the only two quadratic that get rank three.

322
00:39:05,660 --> 00:39:10,730
But you can see we're getting more of the linear equations.

323
00:39:10,730 --> 00:39:22,230
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.

324
00:39:22,230 --> 00:39:28,040
And I haven't. I've just started off with rank four. OK.

325
00:39:28,040 --> 00:39:35,360
So we've got a way of listing all the algebraic equations.

326
00:39:35,360 --> 00:39:43,880
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.

327
00:39:43,880 --> 00:39:55,160
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.

328
00:39:55,160 --> 00:40:03,500
OK, so imagine we've got this infinite list of all the all the possible algebraic equations.

329
00:40:03,500 --> 00:40:08,780
Now, every algebraic equation has it most in solutions.

330
00:40:08,780 --> 00:40:16,580
So if any is the highest power of X in the equation, you know, quadratic equation can have at most two solutions.

331
00:40:16,580 --> 00:40:27,500
Imagine solving all these equations, those that are solvable at any rate and listing the roots of the equation in numerical order.

332
00:40:27,500 --> 00:40:33,860
I've mentioned here you could put complex numbers into this if you want, but we're not thinking about complex numbers here.

333
00:40:33,860 --> 00:40:42,770
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.

334
00:40:42,770 --> 00:40:52,730
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,

335
00:40:52,730 --> 00:41:01,220
every number, which is a root as of any one of those equations will appear somewhere in that infinite list.

336
00:41:01,220 --> 00:41:09,650
So as before, we can define a suggestion and QED quod erat demonstrated to me proves what we set out to prove.

337
00:41:09,650 --> 00:41:18,950
You can actually produce an infinite list of algebraic numbers, which contains every single algebraic number.

338
00:41:18,950 --> 00:41:25,070
So there are no more algebraic numbers than there are integers.

339
00:41:25,070 --> 00:41:31,280
OK, so again, you might think maybe this isn't a surprise.

340
00:41:31,280 --> 00:41:33,230
Infinity is infinity.

341
00:41:33,230 --> 00:41:44,120
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.

342
00:41:44,120 --> 00:41:53,360
Okay, piety of the most famous examples. But if trigonometric functions often yield them as well.

343
00:41:53,360 --> 00:41:56,450
Notice, by the way, that when we're dealing with trigonometric functions,

344
00:41:56,450 --> 00:42:07,220
we standardly think of the angle in radians, not in degrees, so that that fundamentally changes things.

345
00:42:07,220 --> 00:42:11,630
OK. So there are transcendental numbers.

346
00:42:11,630 --> 00:42:20,480
There are numbers that are not roots of a algebraic equations.

347
00:42:20,480 --> 00:42:27,560
Surprisingly, although Pi and E may be the only familiar ones or the most familiar ones.

348
00:42:27,560 --> 00:42:33,940
It turns out that to a rough approximation, all numbers are transcendental.

349
00:42:33,940 --> 00:42:44,020
So this is due to a proof by Cantor, which we now going to see famous dive in the truth.

350
00:42:44,020 --> 00:42:51,460
So Cantor showed that real numbers in general cannot be put into an infinite list.

351
00:42:51,460 --> 00:42:57,550
Rational numbers can, algebraic numbers can, real numbers can't.

352
00:42:57,550 --> 00:43:00,700
And again, we've got a proof by reductio out absurdum.

353
00:43:00,700 --> 00:43:07,810
We start with the assumption that they can be put into a list and then we show that that's impossible.

354
00:43:07,810 --> 00:43:14,860
So let's suppose that the set of real numbers were in fact innumerable could be put into an infinite list.

355
00:43:14,860 --> 00:43:22,270
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.

356
00:43:22,270 --> 00:43:28,810
Yes. Let's just restrict our attention to that small subset of the real numbers between zero and one.

357
00:43:28,810 --> 00:43:36,730
Ignore all the infinite others. Imagine that they have been put into an infinite list.

358
00:43:36,730 --> 00:43:40,120
So here's the list. That's the first of them.

359
00:43:40,120 --> 00:43:49,630
Second, third, fourth, fifth and so on. And one is the first digit after the decimal point of the first number in the list.

360
00:43:49,630 --> 00:43:54,700
8.4 is the fourth digit off the decimal point of the second number in the list.

361
00:43:54,700 --> 00:44:02,320
And so everyone happy with that. So now look down the long diagonal there.

362
00:44:02,320 --> 00:44:06,400
What I've done, I've chosen the first digit of the first number in the list.

363
00:44:06,400 --> 00:44:11,860
The second digit of the second number of the list. The third digit at the third number in the list and so on.

364
00:44:11,860 --> 00:44:22,090
What we're now going to do is construct a number, a decimal number, which differs from each of those.

365
00:44:22,090 --> 00:44:31,030
So in the fourth place, we're going to choose a digit, which is different from eight four four in the fifth place.

366
00:44:31,030 --> 00:44:36,370
We're going to choose a digit different from a five, five and so on.

367
00:44:36,370 --> 00:44:43,780
Do you agree that if we do that, we will end up with a number which differs from every single number in the list

368
00:44:43,780 --> 00:44:51,820
because it will differ from the number in the eighth place after the decimal point?

369
00:44:51,820 --> 00:44:57,790
OK, so we can define this number, we can call it number C in honour of Cantor.

370
00:44:57,790 --> 00:45:06,670
Let's just say that if the end digit of the ninth number in that list is five,

371
00:45:06,670 --> 00:45:12,030
then the digit of our specially defined number is going to be made zero.

372
00:45:12,030 --> 00:45:19,060
But otherwise, we're going to make it five. So we're going to we're defining a number here.

373
00:45:19,060 --> 00:45:22,840
Every single digit is either going to be zero or five.

374
00:45:22,840 --> 00:45:32,860
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.

375
00:45:32,860 --> 00:45:39,360
And if that number has a zero, we have a five. In fact, if it has anything else, we have a thought.

376
00:45:39,360 --> 00:45:46,170
So the number that we defined is going to differ from the entry number in the list at the ninth decimal point.

377
00:45:46,170 --> 00:45:54,000
So effectively what we're doing, we're writing out a number where if you go to say the fourth digit of that number,

378
00:45:54,000 --> 00:46:00,450
you can be quite sure that it will be different from the fourth digit of the fourth number on the list.

379
00:46:00,450 --> 00:46:07,560
It will therefore in the same way it will differ at some point from every single number in that list.

380
00:46:07,560 --> 00:46:12,930
But we started off with the assumption that every single real number is in that list.

381
00:46:12,930 --> 00:46:18,930
We've just defined a number which a real number, which is not in that list.

382
00:46:18,930 --> 00:46:28,220
So we've got a contradiction. This is a for obvious reasons, called a diagonal argument.

383
00:46:28,220 --> 00:46:35,480
It's an argument that works by taking two dimensions of variation and providing some construction that runs down the diagonal.

384
00:46:35,480 --> 00:46:42,080
We're going to be looking at some other diagonal arguments. A very famous one is the proof of cantors theorem.

385
00:46:42,080 --> 00:46:51,750
For any set, the powerset of a that is the set of subsets of a always has a greater carnality than a itself.

386
00:46:51,750 --> 00:47:03,750
So suppose, for example, you've got three people, how many different sets of those three people can you make?

387
00:47:03,750 --> 00:47:09,930
Well, the first person can either be in or out of the set.

388
00:47:09,930 --> 00:47:14,760
Yeah. So that's two possibilities for each of those possibilities.

389
00:47:14,760 --> 00:47:20,070
The second person can be in or out of the set. So that gives you two times two.

390
00:47:20,070 --> 00:47:25,380
And for each one of those possibilities, the third person can either be in or out of the set, which gives you eight.

391
00:47:25,380 --> 00:47:31,500
Yeah. So you get eight subsets. So in general, with a finite set, if you've got an elements,

392
00:47:31,500 --> 00:47:39,630
the number of subsets is two to the end because basically every new element doubles up the possible subsets that you can have.

393
00:47:39,630 --> 00:47:45,590
Bear in mind, the null set is a subset of the set itself is a subset. OK.

394
00:47:45,590 --> 00:47:55,790
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.

395
00:47:55,790 --> 00:47:59,660
The set of three is that true for infinite sets?

396
00:47:59,660 --> 00:48:09,770
Will Cantor showed that it was the very nice proof, so let's suppose, first of all, as in innumerable sets.

397
00:48:09,770 --> 00:48:17,420
In other words, it's a set where we can list all the elements of the set in a list, an infinite list fine.

398
00:48:17,420 --> 00:48:22,880
But those are the elements of the set nested along the top.

399
00:48:22,880 --> 00:48:36,500
And let's suppose that we can define a subjective function from each element of that list,

400
00:48:36,500 --> 00:48:43,640
which which hits as it were every single subset of that set.

401
00:48:43,640 --> 00:48:55,760
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.

402
00:48:55,760 --> 00:49:04,790
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,

403
00:49:04,790 --> 00:49:10,100
which means that every single subset gets hit at least once.

404
00:49:10,100 --> 00:49:22,760
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.

405
00:49:22,760 --> 00:49:27,080
Here's the subset to which a two maps. Here's the subset to which a three maps.

406
00:49:27,080 --> 00:49:35,750
And so and we've put a tick or a cross to indicate which elements of the set are actually in that subset.

407
00:49:35,750 --> 00:49:40,970
OK. Don't imagine there's any authority in the ticks and crosses I've put here.

408
00:49:40,970 --> 00:49:48,500
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.

409
00:49:48,500 --> 00:49:53,420
It doesn't matter what we're we going to do is go down the diagonal,

410
00:49:53,420 --> 00:50:02,180
look at that diagonal and suppose we consider the set of elements that have crosses down the long diagonal.

411
00:50:02,180 --> 00:50:07,190
OK, that's in this case. That's an A3 and A4.

412
00:50:07,190 --> 00:50:09,380
They're the ones that have crosses down the long diagonal.

413
00:50:09,380 --> 00:50:19,600
In other words, those are the ones that do not belong to the set to which they are mapped by our surge action.

414
00:50:19,600 --> 00:50:29,200
Imagine that we take all of those elements which have a cross in the long diagonal of the former subset of them,

415
00:50:29,200 --> 00:50:39,880
so we form the set of all the elements which are not contained in the subset to which they are mapped.

416
00:50:39,880 --> 00:50:46,570
By similar reasoning to cantors, diagonal of the the diagonal arguments about real numbers,

417
00:50:46,570 --> 00:50:52,270
and we have thus constructed a subset which is not present in the list.

418
00:50:52,270 --> 00:51:03,820
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,

419
00:51:03,820 --> 00:51:10,660
any innumerable set of objects onto the subsets of that set.

420
00:51:10,660 --> 00:51:16,480
That's quite tricky. This is something that to it's worth thinking about.

421
00:51:16,480 --> 00:51:20,500
You know, the the text of the slides actually explains it.

422
00:51:20,500 --> 00:51:33,580
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.

423
00:51:33,580 --> 00:51:40,850
See how you fill in the grid. And that will probably help.

424
00:51:40,850 --> 00:51:45,020
Now, in fact, the proof of counsel's theorem doesn't rely on innumerable.

425
00:51:45,020 --> 00:51:45,740
Here we did.

426
00:51:45,740 --> 00:51:58,760
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,

427
00:51:58,760 --> 00:52:03,440
where a is any set at all innumerable or not,

428
00:52:03,440 --> 00:52:17,810
we can think of the set of elements of a which are not elements of the subset to which they have been mapped.

429
00:52:17,810 --> 00:52:23,320
And in fact, we get exactly the same kind of contradiction.

430
00:52:23,320 --> 00:52:33,170
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,

431
00:52:33,170 --> 00:52:41,210
because if X is fixed for any X, then if X is it a subset is an element of X.

432
00:52:41,210 --> 00:52:48,440
It turns out that X also cannot be a sub in an element to this.

433
00:52:48,440 --> 00:52:57,920
So this implies that the power sets of an infinite set must have a card analogy strictly greater than that set.

434
00:52:57,920 --> 00:53:07,820
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.

435
00:53:07,820 --> 00:53:16,430
I mean, effectively, this means that if you start with some set and then you take the set of subsets,

436
00:53:16,430 --> 00:53:22,070
you have to move to a larger number, whether that set was finite or infinite.

437
00:53:22,070 --> 00:53:31,430
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.

438
00:53:31,430 --> 00:53:38,510
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.

439
00:53:38,510 --> 00:53:45,800
So not only do we have at least two infinities, namely the number of natural numbers and the number of rational numbers.

440
00:53:45,800 --> 00:53:50,180
Actually, there's an infinite number of infinity.

441
00:53:50,180 --> 00:53:57,000
You can see why some people were rather dubious about cantors theory, but turns out to be to all make sense.

442
00:53:57,000 --> 00:54:04,570
You know, you can't generate contradictions from it. So it's very widely accepted.

443
00:54:04,570 --> 00:54:11,140
Finally, I'm going to end with an important consequences consequence of this for philosophy of logic and mathematics.

444
00:54:11,140 --> 00:54:20,050
Really, very, very important indeed. Bertrand Russell contemplated cantors arguments and you can see how close cantors argument gets to this,

445
00:54:20,050 --> 00:54:26,800
and hence Russell thought about the set of all sets that are not members of themselves.

446
00:54:26,800 --> 00:54:35,170
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.

447
00:54:35,170 --> 00:54:44,830
Great. Whereas the set of all sets is itself a set and is therefore an element of itself.

448
00:54:44,830 --> 00:54:47,080
Take all the sets that are like the set of cats,

449
00:54:47,080 --> 00:54:55,690
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.

450
00:54:55,690 --> 00:55:01,090
But if it is a set, it's not an element of itself, is it?

451
00:55:01,090 --> 00:55:08,360
Or is it not an element of itself? Well, if it is an element of itself, then it's not an element of itself.

452
00:55:08,360 --> 00:55:12,370
If it's not an element of itself, then it is an element of it. So you get a contradiction.

453
00:55:12,370 --> 00:55:18,370
It's rather similar to the paradox of the village barber who shapes all and only those men who do not shave themselves.

454
00:55:18,370 --> 00:55:25,720
Does he shave himself? OK, well, you can get round that one because you can say either there just is no such barber.

455
00:55:25,720 --> 00:55:32,710
It's an impossibility. Or you can more coming in to say, Well, maybe the barber was a woman.

456
00:55:32,710 --> 00:55:42,520
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,

457
00:55:42,520 --> 00:55:49,570
Oh, there's no such thing makes us wonder, Well, why not?

458
00:55:49,570 --> 00:55:53,020
We know what it is for a set to be a member of itself.

459
00:55:53,020 --> 00:55:57,790
Why can't we simply take all the assets that are not members themselves and put them in a big set?

460
00:55:57,790 --> 00:56:02,650
What stops us doing that? Well, it leads to a contradiction. Yeah, OK.

461
00:56:02,650 --> 00:56:10,930
It leads to a contradiction. But if that leads to a contradiction based on such straightforward ideas, where else might there be contradictions?

462
00:56:10,930 --> 00:56:17,440
And you can see the effect that this had on Friday, Russell wrote to Fraser in 1982.

463
00:56:17,440 --> 00:56:24,940
Explaining the paradox, Schrager wrote back to Russell six days later.

464
00:56:24,940 --> 00:56:34,630
So he probably only just received it. Your discovery of the contradiction has surprised me beyond words, and I should almost like to say,

465
00:56:34,630 --> 00:56:43,390
let me thunderstruck because it is rocked the ground on which I'm meant to build arithmetic.

466
00:56:43,390 --> 00:56:54,340
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.

467
00:56:54,340 --> 00:56:56,560
See you then. Thank you.