A Mathematician's View of Proof - Sarah Hart

So in this then my final Gresham lecture, I want to talk about one of the defining characteristics of mathematics and that's proof. So if we imagine ourselves 2000 years ago in ancient Greece, as we we're all well educated people, we all know that there are four elements that make up everything in the universe, earth, air, fire, and water. And we also all know that if you have a right angled triangle, the square on the hypo news is the sum of the squares on the other two sides. Now, today we still believe one of those things, but probably we don't believe the other. And the difference is proof. We have proved pyrosis theorem mathematically. And when you have a mathematical proof, as long as it's correct, then what you've proved is true and it's true now and it'll stay true. So today I'm gonna show you some of my all time favorite mathematical proofs. We're gonna talk along the way about what makes a great mathematical proof. But everything I'll show you today has something in common and that is a flash of pure genius that makes these things even more delightful. So I hope you'll enjoy them. And I thought we should start with, since we've already mentioned one theorem proving pyres is theorem. Now there are lots and lots of different proofs. This theorem has been discovered and rediscovered in lots of different cultures over many different times, many proofs, hundreds of them are out there. So it's hard to pick the favorite. Uh, but I've got two to show you 'cause I couldn't pick. Uh, let's just remind ourselves, we all all know rissy theum, but just to be sure, if you take any old RightAngle triangle and it sides are AB and hypotonus C, then we know that A squared plus B squared equals C squared. Okay? Iconic equation. So we're gonna take this triangle and we are gonna look at two diagrams and you almost don't need any words this point, these two diagrams almost just tell their own story. So both of those show a big square. Uh, its side is A plus B. And inside that square we've got four copies of our triangle and then some space that's left. Now on the left hand side, the space that's left is a square of side C in the right hand side. Apart, once you've taken account of those four triangles, the space that's left is divided into two squares. One has side A and one has side B. So because you've got the same area in each picture, those areas are the same. So we can straightaway say that C squared plus four times the area of that build triangle is equal to A squared plus B squared plus four times the area of that triangle. And so those things are equal. So we get A squared plus B squared equals C squared. I think it's a very pretty little proof. I wanna show you another proof though. And this is not because we need to prove something twice. If our first proof is correct, that's fine, that's all we need. But often we see that if you look at it things from a different viewpoint and prove things in a different way. A, it's fun, there's no problem with that. But also it can show you different approaches, maybe ways you might generalize what you're talking about, techniques you might use elsewhere. And the other proof of phys serum, I'm gonna show you I really like it because to me it feels surprising that the outcome tells you something about the areas of squares.'cause it doesn't seem to involve any of those things along the way. So let's see it. Here's our triangle, our right angle, triangle sides, A, B, and C as before. And we're gonna drop just a perpendicular from that top vertex like that. That divides our triangle into two smaller triangles. Now each of those smaller triangles is similar to the one we started with, similar as in all the angles match up. And just make sure we believe that the one on the left, that green one, we can see the right angle there, we can see it's got that yellow angle the same as the, the big triangle. Well, whatever's left, we know yet the yellow and red angles add up to 90 degrees because they're in the big triangle. So the remaining angle must be the same as this red one. And in the the blue triangle on the right, same thing we get, we get now the red and yellow angles as before. So those two triangles are similar to the big one. And we know about similar triangles that uh, ratios of lengths of corresponding sides are equal. So if we look at that big triangle, if we take the hypotonus length C and the second longest side, a C divided by A will equal that corresponding ratio in, in the left hand triangle. So the, the hypo news of that one is A, and the next longest side is X. So we get C over A equals A over X. And we can do the same thing in the right hand triangle this time comparing the hypotonus to the shortest side. So in the big triangle, C over B must be equal to in the small triangle, B over Y. Okay, so we get these two expressions. Now all we're gonna do is tidy those up a bit, get rid of the fractions, rearrange a little bit. And we see from these we find an expression for A squared it equals cx. And for B squared on the right that equals CY. Now we want to know what's A squared plus B squared. So we can just add those up. A squared is cx, B squared is CY, bring out that factor of C. Now what's x plus Y? Oh it's just CX and Y is how we divided up that that long bottom side C. So again, we get this, it just falls out pys Ethereum A squared plus B squared equals C squared. I really love this 'cause yeah, it's just a surprise to me. Nothing about areas really in here. Some we just do a couple of little calculations with similar triangles and outcomes Ethereum in a completely different way from how we saw it before. So that's just beautiful and there are hundreds of proofs of pyros the out there. So I encourage you to go and have a look and try and find your favorite proof of pyrosis theorem. Well, let's think then about what comprises of proof. Before you can do anything, before you can even write the word proof and begin what you're going to do, you need something that you want to prove. So Pyrosis theorem tells us something about right angle triangles, which had to first be noticed. So you look at lots of different RightAngle triangles and after a while you notice this relationship between the length of the sides, you spot a pattern and you make a conjecture. And then, and only then are you gonna try and prove it. So in order to do any kind of proofs at all, we have to be good at making conjectures. And that's all about spotting patterns. So we're gonna have a practice pattern spotting. Now, uh, so here's a question. Um, we've gotta work out what the pattern is here. So you draw a circle, um, you draw some points on the circumference end points, let's say n equals three to begin with. Uh, and we are gonna join those points with lines like this. So n equals three, join the points with lines. And the question is into how many regions can we divide the circle by doing this? Alright, so with three points you can instantly see I've got four regions that I've divided that circle up into. So a bit early perhaps to make a conjecture and equals three gives answer four, we don't, you know, we haven't got enough information, so let's get some more data. Here's some more data. Okay, so the numbers here are how many regions we've managed to divide the circle into with one point, just the circle itself, one region, two points. We've divided that region up into two. So we've got two regions, three points gives you four, four points. You can eyeball that and see it's eight five points. You might not necessarily instantly count that in your head, but let's count it 1, 2, 3, 4, 5, uh, 6, 7, 8, let's see, 9, 10, 11, and then that last bit, 12, 13, 14, 15 and 16. Okay, so look at that pattern. 1, 2, 4, 8, 16. We are in a position to make a conjecture, right? We, we, this is like oh, powers of two, but if we want to prove this, uh, you sort of think, well how, okay, the number of regions seems to be doubling whenever I add a point and all of the lines that go with it. So somehow doing this is gonna perhaps divide each region into two. That's how we might double, but it seems really hard to do this calculation. And the way I counted those off there was a bit haphazard. It's hard to spot what's, what's going on the structure of what's going on. So if we don't know how to do our proof, perhaps we, we do the next one up and see if we can do it in a bit more of an organized way. So let's, let's think what happens when we have six points. So I've sort of drawn them kind of haphazardly on this circle and let's count in a more systematic way. So with six points here and we've got the regions on the outside, there's six of those. Were the ones with, you know, curved parts to them. And then we can kind of go back in the triangles next to those, those little regions there. There's six there. So six plus that went up to 12. And then we've got this kind of six pointed star and the points each comprised two more regions, the ones I've colored yellow. So we've got another 12 regions there, so 24 so far. And then we've got another six regions that I'm colored in green here. So up to 30. And then there's only one region left, which rather messes up our lovely <laugh>, our lovely idea that we were gonna prove powers of two. Well, well what's happening here and I have to break it to you only gets worse. The next two numbers in this pattern are 57 and 99, right? So we're getting further and further away from the powers of two that we thought. So what I was really doing here is saying yes, we need to make conjectures and spot patterns, but we really, really, really need proofs proof means never having to say you are sorry <laugh>, we are not gonna have to go back on our word. If we could prove we can work out what this pattern is and prove, um, prove it, get a formula and prove it, then we are going to know for sure what happens rather than having to make a guess which might then later be wrong. Um, so I'm gonna leave to you if you want to think about what on earth this might be and what's going on in the transcript for the lecture. I have put what the formula is and I've given a proof of what it is. So it's a bit long to long to do now, but if if you're interested in that, you can look at that later. So this is, this is my, we need to prove things for sure. So then once we've made a conjecture and we think we know what the right answer is, we want to prove it, we have to prove it. What is a good proof? Then? I'm talking about, I'm saying the proof. I'm showing you a a lovely and beautiful and I can say that because I didn't think of them. You know, these are, these are wonderful mathematical edifices passed down, uh, through the ages for us to all marvel at and be just, just enjoy for their loveliness. What is it that mathematicians rate about a proof? What do we think makes a good proof? Well, let me give you an example of something that will, first of all, not a good proof and then we'll we'll see how to make it good and it's another possible pattern. So this one is about, uh, an expression, I'll call it F of N. And you work out n squared plus n plus 41 A. And we're working this out for numbers N starting at zero. So whole, whole number integers. So if you put N equals zero into that, you just get the constant term 41. So that's a prime number. If you put n equals one, you get 43. Also a prime number N equals two, uh, 47, also a prime number N equals three. Let's do it. Is it 53 also a prime number? Oh gosh, lots of prime numbers coming out here. If you take this a bit further, um, the first few terms you can see all of them are prime. It's prime. For the first 10 values, it's prime for the first 20, it's primed. For the first 30, you start thinking, oh my goodness, I've got a prime number generator here. Well, since the incident of the circles, uh, perhaps we don't necessarily believe that all of these numbers are going to be primed forever. And in fact we'd be right to be skeptical. These are not always prime. So how could we prove that once we've discovered it? So what we might do, in fact the first time we see a question like this, we might, and it's perfectly legitimate thing to do, just keep plugging in values and see, just keep going and going and going. And eventually this is the bad proof after a very long time and I'm not going to do it. But it wouldn't make for a great lecture. We find we get to the number 1,681 and we notice, oh, that's not prime. Oh, it's not prime, right? We can stop. We found a value event, which that is not prime. Uh, and so you, you can, this is, it would be a correct proof, it's just not a great proof. It doesn't really tell you anything. It doesn't have insight. You've just plugged away at it. So you can call this a proof by exhaustion if you like. But a great proof of this is to notice something about what's going on. That 41, if we put n equals 41 into that expression, then every term 41 is a constant at the end. Everything with an n in, if you put n is 41, um, will now be divisible by 41. So every term will be divisible by 41. So we've got a, a multiple of 41 will come out a bigger multiple than one. And so that can't be a prime number. So that observation, once you've noticed that means you don't have to do any calculations at all, which is always good. And you certainly don't have to do loads and loads of them. You just notice of course this can never be prime. And another great thing about this observation, which makes it a good, a good proof, is that you can generalize it pretty much instantly because there was nothing special about the number 41 there really, uh, that enabled us to do this trick. So we can instantly generalize this and make our own little theorem that says actually no expression like this, but of this form, something like a n squared plus BN plus C, no expression like that will always give you prime numbers for n greater new to zero. And we can, that proof will go something like this. Um, if the number C the constant term is not a prime number, then you are already happy at when N equals zero.'cause when n equals zero, the output is C not prime done. So we only need to worry about what happens when C is prime. But when C is prime the trick I've just noticed instantly works F of C will give you something that isn't not a prime number.'cause we will have a factor of that prime. So we are done. So it's, it's an observation that one makes your proof extremely short, but two, we can generalize it and get a much more, um, wider result. So that for me is, is the essence of what makes a good, good proof. It's elegant, it's short, it's ingenious, and, and it tells you something about what the situation, okay? So I'm gonna show you now, uh, three different proofs that use three ideas or concepts that are really ingenious and they sort of lead us to techniques that we might be able to use more widely. And each of them, i i I love for their different reasons. So the first one is about this question, how many different sums add up to n So n you know, positive whole number like three and what I'm talking about, everything's a whole number here and I'm counting as different. You'll notice two plus one I'm saying is different from one plus two. So I I'm, the order matters to me if, if you, if that doesn't matter to you, it's a different question with a different answer, um, that you might think about separately for in this case, just genuinely what are the things in what order add up to three and there are four possibilities. Three, two plus one, one plus two, one plus one plus one. Okay? So there's four sums that make three and there are eight sums that make four if you could check if you like. So is well is it powers of two? Now we, again, we are still a bit suspicious after the, the circles in this case though it does turn out that it's powers of two. But how could we, how on earth could we prove this? We're somehow thinking it's gotta double, the number of sums has to double every time you go up by one. So you might think, well is there a way to make those sums that that give you three? I can turn those into sums that give you four by just adding one somewhere, but I've gotta do it systematically. Um, maybe I just increase the first number by one. That would work. All of those are sums that give you 4, 4, 3 plus one. So the three becomes four, two plus one becomes three plus one. So on that obviously isn't giving us everything. So is there something else we could do? Well, maybe we can add an extra term, we can add a one at the end if we do that, then three becomes three plus one, two plus one becomes two plus one plus one. So on. So now you've got eight things, but unfortunately, uh, we've got some duplicates and we've got some missing subs. So this doesn't give us everything. Maybe there's more things we can do. But if you try and explore the possibilities here, it becomes so horrible and complicated and messy. It's really, really difficult to make progress if you take this approach. And so you might feel a bit stuck. And then inspiration has a lovely, lovely argument that that settles this and shows that indeed if you wanna add, make the thumbs, the add to n, there are two to the N minus one of them. So for example, when n equals four, N minus one is three, two cubed is eight. That's the correct answer. And the little bit of genius that allows this to happen is, is this, it's turning this question into a different question with the same answer, which it's easier to calculate in that other context. So what you do is you take a a, a, a string of ones n of them, um, just in a line with little gaps between them. So if you've got N ones, how many gaps N minus one, okay, between in each of those gaps we are gonna put a symbol, we've got a choice of two symbols and we can do every possibility. So the first symbol we can use if we want is a plus sign. And the next one is a letter G. That seems a bit odd. G is gonna stand for glue. That's why, because if you've got two ones with it with a g between them, you are going to glue them together to make a bigger number is an example. If you take five ones in a row, um, and where you have a g, you're gonna glue those together. So you've got one glue to one that makes two, then a plus sign, that means plus, uh, then one glue to one glue to one that makes three. So we've coalesced into two plus three and we can see that actually every possible sum that makes in this case five in general n you, you can arrive at by doing this process in exactly one way. It's really kind of well-defined, uh, setup. So this is allows us to translate that question about thumbs that make a number into saying how many ways are there to put in n minus one spaces, um, symbols where you've got two possibilities for each one. So plus or G plus or G. So there's two ways to fill the first space times two for the second space times two times two times two N minus one spaces. That's our answer. That's the number of ways to assign those symbols. Two to the n minus one. And therefore that's the number of sums. So that little flash of insight there that allows you to translate this question to something we can answer much more easily, that's the key to this beautifully simple argument, which I really love. Okay, next one. The principle here is so kind of self-evident that when I tell you it, you're gonna think that's ridiculous <laugh>, that it's even got a name, but it's extremely useful, extremely, extremely useful. And it's this, it's called the pigeonhole principle, uh, because the, the, you imagine some pigeons and they're going to each go to a pigeonhole. Um, but if you've got more pigeons than pigeonhole, there's gonna be at least one pigeonhole that has more than one pigeon in it. That's, that's literally as easy as as this is the whole principle, right? Um, if you wanna be more formally, if you have K boxes and n objects to put in them, if n the number of objects is bigger than K, the number of boxes, then we are guaranteed that at least one box will contain more than one object, however they arrange themselves. Or maybe they all go in one box. So maybe they spread themselves out as widely as they can, like people sitting on a bus. But in this case, if there's more than more objects than boxes, we are guaranteed to have a box with at least two more than one uh, object in it. Okay? So this is used in so many proofs in mathematics and many are, you know, very beautiful but would take a long time to, to uh, give you the background behind. So I'm gonna give you kind of a toy example. It's not particularly profound, but it's kind of fun. Um, I picked a totally random number here, 42. You can, uh, this works for any number, uh, any whole number. Um, it says there's a multiple of 42, which consists just of zeros and ones. Now, okay, I'm not being clever, I'm not saying write it in binary <laugh>, I mean genuinely writing in base 10 in our normal number system, we can guarantee that there will be a multiple of 42 or in fact any number as we'll see, which just has ones and zeros in it. So lots of possible numbers out there of that form. But how do we go looking for these things and how do we prove that this is always gonna be possible? Well, the argument goes like this. Let's just think about numbers that only have ones 1, 1111 and salt. So obviously you can carry on that sequence as, as far as you like. Those are gonna be the, the things that are going in the boxes. They're, those are the objects that we're gonna put into boxes. The boxes are going to be remainders, take any number. If you divide it by 42, you get some quotient, don't care about that. And a remainder, the remainder is somewhere between zero and 41. Can't be 42 or more.'cause otherwise we could take off another multiple. So when you divide by 42, there are exactly 42 possible remainders from zero to 41 inclusive. So we're gonna take these numbers, we only need to go as far as the 43rd number. And at that point we know by the pigeonhole principle we're putting those numbers into the boxes that go with the remainder. There must be at least two of these numbers somewhere in the sequence that have the same remainder when you divide by 42.'cause there are 43 numbers going into 42 possible boxes, which we label with the remainder. So that must, it just must happen. Pigeonhole principle. So we have these two numbers, at least two numbers. So we'll take the bigger one, there's the bigger one, there's the smaller one. They're both some multiple of 42. We don't care what plus the same remainder are. So all we need to do now is subtract the smaller from the bigger. If you do that, you get some string of ones followed by a string of zeros and that is gonna be a multiple of 42 'cause we the remainders cancel with each other. So this is just guaranteed to happen, which I think is very cool. And it, and it, the 40 twoness of this was not important at all. We could do this for any number n just take the first I guess n plus one numbers that are a sequence of ones and then look at what happens when you divide by n the remainder. There are n possible remainders n plus one numbers to put in them is that same argument. So any positive integer n divides some number of this form, which I think is kind of cool and unexpected. There's no reason to think that that would be guaranteed. So that's quite fun. And the pigeonholed principle, yeah, really, really useful technique. Okay, the next idea is something that geometry proofs just really, really often do this kind of thing. So I'll show you a, a nice little theorem which is perhaps not as well known as some of the other theorems in geometry that we may encounter, but it's very pretty viviana's theorem. So take an equilateral triangle, put draw a point anywhere inside that triangle you like anywhere at all. And if you work out the distances from that point to the, to the sides of the triangle, the sum of those distances, it's always equal to the height of the triangle. So I think it's a lovely little fact. So let's see a proof of this. The first thing to notice in, in this triangle, indeed in any triangle, the area of a triangle is half the base time is the height. Okay? So if the base, I'll just call the base B, the area is half base time is height fine. Now here's the trick, uh, we're gonna join some extra lines that weren't there in the question <laugh>, this is, you know, it's when you're trying to do geometry proofs yourself and you see one of these things maybe your first go, oh, why didn't they just put that line in already? But you know, <laugh>, once it's okay, like we don't always, I may not have thought of is proof and we may not have done but this we're just admiring the beautiful masterpieces here, you know, without feeling annoyed that we didn't think of them. We just admire the loveliness. So let's admire the loveliness. Let's join some lines. We're gonna join this point to all the vertices of the triangle like that, that divides this triangle up into three. Uh, so now we're gonna just unfold the diagram and we see we've now got these three triangles. All of 'em have the same base. It's an equilateral, the original triangle is equilateral, same base B. And so that total area is the sum of the areas of these three. And of course what is all of their areas, half of the base times their height. So we get this, we've got half BX plus a half B, uh, z plus a half BY. And if you just bring out the common factor, you can see instantly x plus Y plus Z equals h. So really, really nice little fact about equilateral triangles that I love. And the, the, the key to this was just drawing in those lines. So always look for lines that you can draw in if it's a circle through drawing a tangent, something like that. Okay, so this of course this proof involved a diagram calls, it's a proof, it's a result in geometry about triangles. You might expect a diagram, but diagrams and visual helps can be really useful in proofs that are not necessarily coming from geometry. So I'm gonna show you a couple of those. And the first is probably better known than the second. Um, but they, they, the one leads to the other. So the first one is about we sometimes call these triangular numbers. It's basically when you add up the first few numbers, one plus two plus three, and so on up to N. So you can think of this as making triangles and how many dots you need to make triangles of each size. So for the first one it's like one dot and then a, a a a two by two triangle if I can call it that. Um, you have to add another row which has two dots, dots in it. So one plus two gives you three. Then for the, the triangle of kind of size three, um, it's got, you have to add three more in the bottom. So one plus two plus three six. And then for the fourth triangle number, I'm calling these T four, T five and so on. We have one plus two plus three plus four, which is 10, you can go on 15, 21, 28. So, so this is the number we're interested in this quantity. Is there a formula for this? Adding the numbers from one to n uh, we'll call that TN the n triangular number. Is there a formula that will save us some time? So we're sort of instinctively a bit lazy, we don't wanna spend all day adding up laboriously the numbers all the way from one up to have a big N is a million, whatever, it's, well, okay, there is <laugh>, spoiler alert, there is, and, and the way to see what the formula is one way relies on pictures. So here is the nth triangular number. Well in this case n equals six, but you know, general, here we go, all these dots piled up. So we've got, uh, kind of this is uh, n high and n dots along the bottom. And all we're gonna do is just not change the number of dots at all. We're just gonna technical terms, scooch this along so that we've now created a RightAngle triangle there and the number of dots, I've just put each of them in a side little square. And what we're gonna do is we're gonna take that exact picture, copy it, turn it over and join it on. So we're now gonna get two of these things. And now what we've got, um, is in, we've got a rectangle and the total number of dots in that is the area of that rectangle, which is its base times its height, and that is n plus one is but obscured along the bottom we've got n from the original triangle plus that one extra. And the height of this thing is our n So the total area of this rectangle is just n times n plus one. That's twice the number we need.'cause we use two copies of our triangle. So all we need to do to, to get the formula for the end trying the number is just divide by two and this is the formula. So there's a lovely, uh, anecdote. It's unclear how much evidence there is that it really happened. But the great mathematician, uh, gauss, it said when he was a a small child at school, the teacher at the end of probably a long day, I, I imagine this teacher wanting just a half an hour of peace. So he, so he said to his pupils, okay guys, you are gonna sit down and I want you to add up all the numbers from one to a hundred while I just sit quietly over here, be my brow. Um, and then his lovely pupil g immediately, sir, it's 5,050 <laugh> because he had the legend, has it worked out this formula and realize in order to add all the numbers from one to a hundred, that's n equals a hundred. You just have to do a half times, a hundred times 101. And so you can do that instantly, whereas adding them all up one by one takes you an an awful long time and you probably make some mistakes. So I dunno if that's true, but it's a nice story. Um, okay, so this is the numbers adding up just the numbers from one to end. Let's raise our game a little bit. Let's add the squares, the first n squares one plus four plus nine plus 16. And so on up to n squared, I'll call that sn for squares. What's that? Now you may have seen, if you've seen that first proof with do with visual proof for the triangular numbers, you may have seen, I've certainly seen proofs of this that involve fitting pyramids into cuboids. Now for me, at that point it kind of switches and I find the algebraic proof of whatever this formula's gonna turn out to be. I find the algebraic proof more easy and intuitive than fitting pyramids into cuboids. Maybe that's different for you. And of course everyone has their own tastes in these things, but there is a visual proof that I find really helpful in seeing some of the connections with the, the triangular number formula. I'm gonna show you that, um, I like it a lot. So here's a triangle, but instead of dots, we've now got numbers. So in the first row it's ones and then twos, threes, fours and so on. And so what, what have we got in here? Well, the, the second row, two twos at four, the third row three threes is nine, four fours is 16. So what we've got here is the sum of each row is that square number and the sum of the numbers in the whole triangle is exactly the thing we're interested in the sum of the first end squares. So if we could work out what the, the total of the numbers was in this triangle, that's the thing we're after. So you take that triangle, we're just gonna knock it over to the right and to the left, get two more copies of it. So's exactly the same numbers involved, we've just tipped them over. So each of these triangles, the sum of the entries is our SN that we're interested in. Now what we're gonna do is superimpose these triangles on top of each other. So we'll now could of combine all of these three triangles and we'll do that the numbers, we are just gonna add the numbers in each place together. And if you do that, now this might take a little bit of thinking, you might have to convince yourself of this. Every entry in this combined triangle is two n plus one. If I just add another little row in there, just on each one we can see. So if you look at the top corner there, n plus one plus n, that's two n plus one, uh, go down, we get n plus one plus two plus n two n plus one. Hopefully you can convince yourselves that every entry in this combined triangle is two n plus one. So we can add all of those up. If we know how many entries there are, how many two n plus ones have we got to add together? And if we do that well how many entries are there in the each of these triangles? It's just the number of dots in a, in a ular size, n So it's the n triangular number. And if we do that, we've got these three triangles combined. So we've got three times the sum we're interested in. So we find that three times our sn that we want is just equal to two and plus one times the nth triangular number, which we just proved was N half N and plus one. And so to get our sn we just divide everything by three, right? And this is the formula we get. So if you've seen this formula before, you will, you know, it's, it's come out correct for me, I saw this formula and the way I was, um, taught to prove it originally uses a technique, an algebraic technique called proof by induction, which we're, we're not gonna talk about today, but it's a very excellent proof technique. But it does not that just doing it purely algebraically does not really explain why this formula is so clearly related to the formula for the triangular numbers. So I really love this proof because it gives an insight into what the connection is between them. Um, so yeah, I top mark this proof for me, I really enjoy it. So we've seen these proofs, uh, these two visual proofs. I'm gonna go back to one that is, does not involve drawing a diagram, but it's one of the first oldest proofs that we, that we have dates back to Euclid. And it uses an amazing idea. Uh, we're gonna prove that there are infinitely many prime numbers and you may have seen this proof before, but I have to include it in a lecture of the best proofs of all time, right? It's kind of, you know, you can't, I'd be thrown outta the mathematician's guild, which doesn't exist if I didn't include this proof. It's so amazing because it really, if you think how on earth can you prove that something goes on forever? How, how is that we can't do, how can we do this? And it involves doing a little fault experiment. So here we go. Imagine this wasn't the case. Imagine that actually there's only a finite number of primes, then you can imagine a list of them all 2, 3, 5, 7, and so on up to whatever the highest prime number is. Let's call it p Now we're gonna make a number, I'll call it n you make it by multiplying all the prime numbers together and adding one. Now that number n let's think about it if we're gonna try and factorized it, well, it's not divisible by any of these prime numbers on our list. It's one more than a multiple of two. So it's not divisible by two, it's one more than a multiple of three. It's not divisible by three, it's one more than a multiple of every single prime on the list of primes that we have. So this number N is not divisible by any of the primes on our list. So it doesn't have any factors that are primes on our list. So that either means the n itself is prime, that's what is a prime number. It's only divisible by itself. And one, either it's prime itself or it's got a prime factor that we didn't know about before. Either way, there's something gone wrong. We found a new prime that wasn't on our allegedly complete list of primes. So this, at this point we say magic word contradiction. This contradicts our, our assumption that we made. The, the assumption that we made can't be right 'cause we've ended up with something that that doesn't make sense. I call this the Sherlock Holmes method of proof. Once you've eliminated the impossible, whatever remains, however improbable must be the truth. So in fact, our assumption that there's only a finite number of primes led us down the garden path of something that ended up being impossible. We had a complete list of primes and now we found a prime that wasn't on our list. So actually all along there must have been infinitely many prime numbers. So this is a fantastic idea. You know, you take your life in your hands and say, okay, I think this thing is right, but I'm gonna just assume the opposite and see where it takes me. Hopefully I find some, you know, I prove that one equals zero, which we know isn't correct. So I, my initial assumption, uh, was wrong. And so my thing I really wanted to prove must be true. The great mathematician Gh Hardy, there he is looking very severe. Uh, he says, this is one of the great techniques, one of the finest weapons that we have at our disposal. It's a far finer gambit, he said than any chess gambit. A chess player may offer the sacrifice of a porn or even a piece, but a mathematician offers the game. We can risk everything to see if our, if, if our hypothesis is true. So I'm gonna show you just one other proof by contradiction. Now we know what the technique is and again, it's a, it's an old proof, but it's just so amazingly ingenious that it's, it's gonna make you smile. Makes me smile. Okay? So we are gonna prove that the square root of two is irrational. So a rational number is one that you can write as a fraction of whole numbers. Something like A over B where A and B are whole numbers. If you can't do that, then we say the number is irrational. Now there's no one you've, you know, when people first started thinking about mathematics and numbers, there was no suspicion that such numbers could exist, but they do. And even in the most sort of commonly occurring places, I mean the square root of two is just the length of the diagonal of a square of side one. You know, we haven't had to delve down the back of the sofa for this thing. In some weird esoteric situation, it's really naturally occurring. The square root of two, um, you can't avoid it even in the most basic of geometry. So the idea that this thing is can't be written as a fraction, um, is, is very strange and exciting and exhilarating. And, but how do we prove it? Again, it's this, how do we know we can't check all possible fractions? So we've gotta use a different argument. And the argument is this, proof by contradiction. Let's imagine a world in which actually the square root of two is rational. What would that mean? It means we can write it as a fraction, but once you've got a fraction, you can always cancel it down to its lowest form. If there's any common factors on the top and the bottom, you can cancel them. So if there, if there is a fraction that is route two, we can assume that we've just canceled it down, cancel any common factors and so we can um, be happy that we would be able to write route two as some A over B in its lowest form. No common factors in A and B, they're co prime. Alright, so we dunno anything about route two. So let's square both sides so we don't have to think about that scary thing. If we square both sides, we get that two is equal to A squared over B squared. Um, so we can rearrange that A squared equals two B squared. Now at this point, let's think about numbers. A is a whole number so is B. So the square of A is an even number. Now if you take an odd number and multiply it by itself, the answer is still odd, odd times odd equals odd. So a can't be an odd number, it must be an even number. So A is twice some other whole number C let's say. Okay, we put that back into what we've got. So two B squared is, is equal to a squared A is two C. So a squared is two C all squared, which is four C squared. And now we've got two B squared is equal to four C squared. We can cancel a a two there and find that B squared is twice C squared. Now with this looks a bit familiar 'cause we just sort of had something like that already. B must be an even number because it's square is even the square of an old number is odd. So B must be even, but oh, hang on a minute. Didn't we start by saying A and B had no common factors and now we've proved they're both even that can't be right, that's impossible. That's a contradiction. Okay, so our initial assumption that route two was rational led us to something that obviously false. And so, so it must be all along that route two is irrational. So that's the power of a proof by contradiction. It allows you to deal with cases where there's infinitely many possible things that you would have to check and deal with it in a, in a really efficient way. Wonderful proof technique. Alright, so we talked about some lovely proofs. We've talked about making conjecture and then we have to prove it, but you can't get something for nothing. Every proof relies on either facts you already know are true, like an odd number times an odd number is an odd number. Um, or, or even further back than that basic axioms facts that we are just, we don't even try to prove. We say these are sort of truths we hold to be self-evident. An example of this is in geometry, of course we all learn very early on that the SSON triangle add up to 180 degrees. The proof of that, or one proof goes like this, very simple. You take your triangle, you draw a line through a parallel to BC that gives you, so the, the angles I've marked as green, those are equal 'cause their alternating angles are equal, right? Same with the blue angles, equal 'cause alternating angles are equal. And then we say, well, we know the angles on a straight line add up to 180 degrees. So that means the green plus red plus blue is 180. Those are the angles in my triangle done. But the very first thing we said was draw a line through a parallel to BC that is one formulation of the famous fifth postulate, the parallel postulate of Euclid. It's an axiom that he uses. He says, we're gonna begin with these axioms that are just obviously true as some discussion as to how obvious that is. But if you don't, if you remove any of those basic ground rules, I mean if you remove the parallel postulate, this proof does not work. So you, you can't even start this proof. So it opens up the possibility for maybe other things can happen if we, if we put ourselves into different geometries. So it's not that this theorem is false or that the proof is false, but really there's an invisible asterisk that says assuming the axioms of Euclid and geometry, right? We've got, if those are our ground rules, then we can prove this. If those are not our ground rules, we get other things that can happen. So if you start looking at the geometry on the surface of a sphere, on a curved surface, you get triangles whose angles can add up to things other than 180 degrees, which is wonderful. Um, you might think, well how there aren't even any straight lines. How can I make a triangle? But what, what we have to think about what, what a straight line actually is doing for us. What is the kind of philosophical definition of a straight line? If that's not too esoteric on a plane between two points, the straight line between them is the shortest path between them. So if we take that as really the motivating reason to think about lines on the surface of its sphere, the shortest path between two points, the shortest paths there, um, are arcs of great circles like equators. And that's why planes flying long haul will follow those curved paths rather than going in what looks like straight lines on the map. So if you take those as our kind of spherical lines, then you can think about triangles where, which are bounded by three lines. Now that all sounds like it's gonna get extremely complicated and horrible. Um, spherical geometry sounds scary, but there is one proof spherical geometry that is so lovely. It tells us something about triangles that I want, I want to show it to you. And this is what we can do. We, we, we are not any longer having to involve the, the parallel postulate that is not valid in the serp on the surface of a sphere, okay? So it involves us knowing this shape. So this is the shape you can't really have on a plane. Um, it's the shape bounded by two, its spherical lines, it's called a loon. It's a bit like, you know, a crescent moon or something. Um, and there's one that I've highlighted, but actually every pair of lines will create two loons. There's, there's one kind of a shadow loon on the round going round the back that's also created by these two lines. So take this loon here, we can work out. Its, its area based on the surface area of the sphere. It's very easy if you, if the angle there is X between the lines, then that same proportion of the total area, um, will be, will be used by the loop. So we don't need to know the formula for the surface area of a sphere. If you do great, let's just call it s uh, then the area of that loon with that angle is just x three sixtieths of the total surface area, whatever that happens to be. Okay, so now with that in mind, let's imagine a spherical triangle. So that is the region bounded by three of these spherical lines. Any pair of those lines defines a loom, well actually one loon at the front and one loon at the back. So there's my spherical triangle, the blue one, and then I've got three loons that are created by the three possible pairs, green, red, and yellow. And actually at the back, that whole thing is repeated sort of anti typically, if that's a word. Um, you've got three loons kind of going round to the back and they all, uh, overlap in another copy of that triangle at the back. Alright? So we are gonna now think about that sphere. The whole surface of the sphere is completely covered by these six loons that we've defined, but there's some overlap. So we can't say that the surface area of the sphere is just the sum of the areas of these six loons 'cause of the overlapping bits. We've gotta take those into account. The triangle at the front there has, is covered by those three loons. So we've counted that three times and the triangle at the back is also covered by the, the, the sort of shadow loons at the back. So we've counted that three times as well. So we've counted six triangle areas instead of actually just two. So if we take away four of those, then we'll everything ought to match up. So what I'm saying is the surface area of the sphere is two lots of the red loon. So the red one and its shadow two green loons green one in its shadow two yellows. And then we take away four whatever the area of the triangle is, which we don't need to worry about, and that, that those are equal. Okay? We know how to find the area of a loon. If the angles in the triangle X, y, and Z, then we're gonna get X three sixtieths, Y three sixtieths and Z three sixtieths. Those are gonna be the areas of our loo, our loos. So we get this expression and what we're gonna find out is something about the, the angle sum X plus Y plus Z on the plane. That would be 180 degrees on the sphere. You can rearrange this and you find that the angle cell x plus Y plus Z is bigger than 180, it's 180 plus a bit. And the amount by which it exceeds 180 is dependent on the area of the triangle. How much of the surface of the sphere is taken up by this triangle. And that intuitively makes a lot of sense. If you think about a very big triangle like the one we saw, angles are much bigger than 180. But if you imagine a really small triangle, make it smaller and smaller and smaller and smaller, we are getting closer and closer to the 180 until in the limit. Maybe you talk about drawing a triangle on a, a sphere of infinite radius, IEA plane <laugh>, you recover the, the Euclidean 180 that we all know. So I just love this argument. I think it's so beautifully simple and gives a fascinating fact about spheres. So we've seen lots of different proofs and some of these proofs are thousands of years old. Is there anything new under the sun? Well, there's one huge question. There's one huge development. Um, and that is computers. So we can ask ourselves to finish with can computers ever do proofs? Can computers prove theorems? And there are sort of three parts to this. There are three ways in which we might employ computers. The first has been happening for, for decades already, and that is computer assisted proofs. Maybe you've got some, most famously the four color film if you, if you're familiar with that, you've got some thing you're trying to prove and maybe you find a way to say, if I could just check these, I don't know, 200,000 cases <laugh>, um, and, and make sure that it holds in all these cases, then they would be representative of the whole thing. And I, I could prove really rigorously that it would work. You know, kind of con everything might be reducible to one of these configurations. And of course you aren't gonna be able to check those cases by hand, but you can program a machine to check them. So that has, that is happening and have been happening for many decades and I'm, you know, okay, ideally we'd all love a half page beautiful, elegant proof, but you know, if we can prove our fear of at all, that's good <laugh>. So these things, I think they're completely valid and if you worry like how do you know the computer hasn't made a mistake? Well, how do you know you haven't made a mistake? You know, like do humans make more or fewer mistake than computers that are correctly programmed? You know, discuss, I think the chance of a, a strain neutrino changing the ting to one and making, making, uh, the computer output be wrong is small and probably smaller than an error in a proof of 200 pages or something, which some mathematical theorems, they, they are that long or even longer to prove. So that's one computer assisted proofs two, which is kind of starting to happen and it's a really interesting area of research is computer or machine verification of proofs. So a human does a proof and then you turn it into kind of language that the machine can understand and it checks the proof for logical consistency. And I think that's very interesting. Um, you know, we have spellcheckers why not proof checkers. The final, the final frontier of this and we are really in the infancy is computers. Can they find new theorems and prove them without human kind of intervention? And that is, you know, not really happening yet, I would say, but maybe the aggression professor in a hundred years <laugh> can revisit this question. So the concept of proof then, as we've seen, I hope I've convinced you it's really absolutely vital to mathematics and it makes mathematics different really from other disciplines in science. What we can do is test our hypotheses really, really stringently. We can never absolutely a hundred percent prove something because something could always turn up and, and turn over our, our preconceived ideas. You know, Newton's laws work brilliantly unless you happen to be going almost at the speed of light and then you need to bring in other, other possibilities. Doesn't make make Newton's laws less good in, in everyday life, but we know we need to refine our ideas and that can happen when we, um, when we are doing science, we test things with experiments, you know, in a court of law we have to prove things beyond reasonable doubt. And in mathematics we have to prove things beyond unreasonable doubt. So, you know, I think that's the, the highest standard of proof. Um, well I hope you've enjoyed this and all my lectures in my series, it's been a real honor to serve as the question professor of Geometry. Thank you very much.