l, you, you might be able to say, well, I think if you try and swap it round, you run into sort of a American melanoma type problems. So to try and avoid that, I think I would, I would want to write it this way. And then the final clause, but that's easy, of course, that's just say you can fool all the people all the time. Okay, I'm, I'm more really happy with that. You might have different opinions on, on the best way to write them. But number two is a bit ugly, but I, I'm not sure we can make a better job of that one. Okay. In any case, we've, we've, we've negated the thing and, and this was nice and clean. Okay, now, now let's look at number nine. Well, number nine involves one of the most important and most famous, some might say infamous formulas of advanced mathematics, of university level mathematics. It's this definition when students entering math, entering university to study mathematics for a math major, it's this definition that, that usually causes them the most problems during their first year. In fact, I think it's this definition that probably is responsible for more math majors giving up mathematics in their first year at university than anything else. It's, it's a really tricky thing to understand as, as many of you have noticed and I've seen from discussions on the, on the forum. Figuring this out is really hard. This was hundreds of years of effort starting with the invention of the calculus by Newton and Leibniz in the, in the 17th century. It took a long time, you know, 700 years before mathematicians were able to figure out the notion of continuity and come up with this definition. This was late 19th century that this was done and it was a, it was a tricky thing. Negating it is relatively straightforward actually because we've, we've got rules for doing them and so when you negate it, what you get is that for all becomes exists and the, it's still a greater than. We're still talking about positive numbers epsilon. The exist becomes a for all. The for all becomes an exists and then there's a bunch of stuff that's in a bracket here. This is a conditional, an implication and so when you negate it, you get the antecedent conjoined with the negation of the consequence. So here's the antecedent. Again, I haven't put parentheses around that because this is a mathematical statement and that, that takes precedence over the, over the conjunction or disjunction. These are just connectives. They're operators that bring things together. So that's a piece on its own, that guy, conjoined with the negation of this guy. Okay? And the negation of it being less than epsilon, is it greater than or equal to epsilon? Okay, so, so that's the negation and that's relatively mechanical to do that as long as you sort of pay attention to preserving things that need to be preserved, changing for all to exist and negating a conditional. The interesting question is what on earth does this thing mean? You know, you can read it through as I just did for all x greater than zero. There's a delta greater than zero such that for all x yada yada yada. What does it mean? Well, this is capturing in symbolic language in an algebraic formalism. It's capturing something geometric. So let's see what it's capturing. Let's look at the original definition of continuity. It's about functions. So let's look at a function this way. I'll draw the real line vertically. This is a real line.  So this is the real lines instead of writing horizontally as we usually do. I'm going to write it horizontally. And the function f is going to take numbers here to numbers here. Okay? So somewhere here we've got a, f applies to that and it gives me f of a. Okay. Now we try to capture the notion of continuity today. That means when we go slightly to the left or right of a, and left or right is up and down the way I've represented it, then the numbers don't sort of have a discontinuity. And the way to capture that, it turns out, and chances are very, very high that you're not going to follow this the first time. It's going to take you weeks if you need to to master this. But here's what this formula says. It says the epsilons are going to work on here. It says let's take an epsilon here.  So I'm going to take an epsilon interval around f of a. And what this definition says is that given an epsilon and one of these intervals, I can find a delta. So here's a plus delta and a minus delta. So starting with an epsilon, which gives me an interval here. For any one of those, I can find a delta which gives me an interval here such that, now let's look at this. Any x in this region, because this says that x is within delta of a. So any x in this interval gets sent to an image f of x in here. So it's saying in order to make sure that all the values of the function are in this interval, I can find an interval around a such that they're all sent into here. So if I want to hit the target, imagine this as hitting the target, like throwing data to that board. If I want to hit the target within a specified accuracy of a, of f of a, I can always do it by starting out within an interval of a. So to get within a given interval around f of a, I can always find an interval around a that does it. So everything from here gets sent into here. And if you think about it long enough, you'll realise what that means is that the function is continuous at here. There's no, no, no jumps. And to try and understand that, let's look at what this guy means in terms of a diagram. I'll do the same thing again. I'll draw the real line. And I'll draw the real line. And here's a. And here's f of a. Now the negation says there is some epsilon. In, in the previous case, this was happening for all epsilons. You could find a delta. In this case there's a fixed epsilon that we can find. And we look at the interval f of a minus epsilon. Okay. What it says is that there is an epsilon such that no matter what you take here, no matter which one you take here, here we found one of these guys. We said take any interval here, we can find an interval here. Here we're saying there is an interval here for some epsilon such that no matter what delta we take here, no matter how small you make this delta, no matter how close you are here, that was a point that gets sent to that. You can always find a point in here that gets sent outside of there. Maybe sent that way, maybe sent that way. So the sum epsilons here that no matter what you do here, no matter how close you are to a, something gets sent out here. In other words, there are points really, really, really close to a that gets sent outside this region. So there's no way that you can, you can get all points in here. A gets sent to that, but arbitrarily close to a, there are points that get sent away. So there's a discontinuity because only a gets sent close to a. When you get, well some of the points may be, but no matter how close you get to a, you'll find points that are sent further away. So that's a discontinuity. Things jump. There's a sort of jump from there to things here or here. Now I, the chances are high that if this is the first time you've seen this, that explanation is going to be hard to follow. This is really difficult to understand. This is extremely, extremely hard. And the goal of this course actually isn't for you to understand this. The goal of this course is to give you the machinery so that you're now able to take a whole semester course on real analysis during which you should be able to understand that. So I wouldn't worry too much if you can't understand this. The point is if you could understand the first part and understand how to deal with the formalism, you now have the machinery you need to understand this, this very deep conceptual definition from within mathematics. Okay, and to have reached that stage in four weeks, I think this is pretty, pretty remarkable. The hard part is to come, and for those of you that want to go on and study more mathematics sooner or later and hopefully sooner, you're going to need to master this definition of what it means. Okey dokey, well as far as we're concerned, we're done with this one. Well for question one on problem set four, we have to choose which one of the following is equivalent to this expression. Okay, we're negating a universally quantified statement in which there's a conditional. And we're told that there's only one of these, one of these answers is correct. The correct answer, let me just jump to the correct answer and then see what's wrong with some of the others, is part C. The not for all becomes an exist, and the negation goes into this part. When you negate a conditional, you end up with the antecedent together with the negation of the consequence. And when you negate a disjunction, the negations filter in and the disjunction becomes a conjunction. So if you follow the rules about, well they're not rules, they're, I mean they sort of are rules, but we, you know, I recommend you not to think of them as in terms of rules because that's not really getting at what this course is about. But there are certainly patterns of activity that you can get to, get to recognise. Then what happens is universals become exists. You have the truth of the antecedent in place of an implication of a conditional, you have a conjunction. And then when you negate these guys, the negation applies to each one and that becomes a conjunction. Okay, but as I just indicated or I just referred to, really what I want you to do is concentrate always on why it is that you get that behaviour. Why does this give you px and not that? Why does negating this give you a conjunction there? So it's all about understanding. If you simply learn to apply the rules, you really don't have a useful skill, okay? Computers are good at applying rules. That's what they do. That's all they can do. People can go much beyond that. Okay. What's wrong with somebody others? Well, the first one is just hopeless. I mean, there's just nothing remotely like that. If you've got that as your answer, then either you are having a temporary aberration or you really, really, really haven't got the issue of this. The others, there are reasons why people could go wrong and the others were put in because of the mistakes that people frequently make. Okay? In the case of this one, the negation is in the wrong place. When you negate a conditional, the negation doesn't come together with this one.  So it's just mixing up where the negation comes in. Okay? But otherwise you apply. So it's like applying, you're basically applying the right sort of, let me call it rule. You're doing the right thing but you've got one step out. It's like getting a negative sign, a minus sign in the wrong place in an equation. Looking at this one, well, everything went fine except you forgot to change disjunction to conjunction. But everything else was fine. And in the case of this one, you forgot to, that that should be conjunction. And everything else was fine. Okay? So in cases B, D and E, there was just one thing wrong. And so it's even possibly just did that by a slip. I mean heaven only knows, you've seen me make slips often enough in the lectures and the tutorials where I write the wrong thing down or whatever. We have to keep a lot in our minds when we're doing these things. And frequently what our hand does isn't what we're thinking it's doing and sometimes what we say isn't what we think we're doing. Mathematics is like that. When you're really focusing on the mathematical concepts and the heart of it, you can make slips with the writing and with the words you use. I do it all the time. And we all do. That's just part of thinking mathematics. It takes a lot of concentration to focus on the mathematics. And the everyday things like writing and using words tend to miss out on that because our mind is focused on the content. Okay, let's go on and look at number two now. So for number two, let me just begin by reading this formula out in everyday English, or at least stilted everyday English. It says for every person P, there's a person Q and a game T such that P beats Q in game T. So more colloquially, everybody beats somebody in some game. Everybody beats somebody in some game. Everybody beats somebody in some game. Well, which one say the same as that? That one certainly does. That means the same as everybody beats somebody in some game. It doesn't mean the same as that. It's not that one. That's not a possibility. For every player there's another player, they beat all the time. That's not quite the same. If there was a for all there, for all T, then whenever they play, P would beat that person, that person Q. So that's not quite. You would need a different quantifier. That's just some game. If there was a for all there, you would have it in all the games. There is a player who loses every game. No, no, that's about losing. That's a player who. Well, actually, while we're on this, what would this look like? If I wanted to put that in a formula, I would put that with the following. I would say there is a Q such that for all P and for all T, W, P, Q, T. In a minute I'll say why I said start because I was looking ahead to what would be wrong with this. But let's just read it so it says there is a player such that for all players and for all times, P beats Q in that game. So it sort of says the player loses every game. The problem is when you take for all P here, one of the P's that are going to crop up is Q him or herself, okay? And a player can't beat themself. So this doesn't quite work because the P could include the Q itself. In fact, the one of the P's will be the Q. Okay? And it's also, well it depends. This says that player is going to, yeah I think that would be okay. You've got to be a little bit careful actually. It depends how you interpret the thing. For all T, T just goes over games of tennis. Whereas we're just talking about games of tennis in which people win. So you'd have to sort of think about it and decide whether you need to put clauses in here to make it clear that you are only looking at T's where they play together. There'll be a similar issue here. Again, you could start with, if you wanted to do this one, you would start with saying there is a P, let's see, for all Q, for all T, W, P, Q, T. The only difference is here we had QP and here we've got PQ. But you'd have the same issue. Among the Q's is the possible P and you'd have to be careful to take account of the fact that the T itself ranges over all possible games and you only want to be making a statement about the games that they play together. And you could have a tremendous, you could put clauses in. There are various ways out of that. If I thought this was a big deal out of thought about it before I started to record this little piece. But I think we've solved the problem in any case. That one came up the first time. That was the one that has that meaning. None of the others do. So put those as no's and we've solved that one. Okay? Let's go on to number three. Now normally when I'm going through examples in classes, I don't make deliberate mistakes. I don't need to because I make plenty of real mistakes when I'm going through mathematics in any case. But this time I'm going to make a deliberate mistake and I'm going to do it to emphasise the issue that's going to come up here. Okay? So what I want to do is go through these three and give you answers to all of them. But one of them is actually going to be a wrong answer and then we'll correct it. So this one, actually if you remember the previous question, this is the one that we saw that means everyone wins a game. Okay? For all players P, there's a player Q and a time T. So it's a P beats Q at that time. What does this say? Everyone beats, well it's almost the same, right? Except instead of playing every player beats one player, you say everyone beats everyone else at some time in some game. Okay? Because it's all pairs of players P and Q. And this one, it's essentially, well actually what's the difference? That was for all P there exists a Q. This is for all Q there exists a P. So this doesn't say everyone wins a game. This one says everyone loses a game. Okay? Seem plausible? Well, one of these is actually not possibly true. Let's just see. Could that be true? We're talking about, whoops, there's a typo there. That should be possibly. Okay, let's correct the typo. I've got it right up there. Okay, let's see which one cannot possibly be true. Okay, that's not the issue is here. Well, that could possibly be true. Okay, that's okay. That could be true. Everyone beats everyone else all at a time, at some time. Well, everyone loses a game. Well, that's certainly possible. That's okay. Come into this one. Can this, I mean, is it possible for this to be true? It's certainly possible for that to be true. It's certainly possible for this to be true. We're talking about the real world here when people are playing tennis. Is this one the one that can't possibly be true? No, there doesn't have to be one. You could have said that none of these are the case. In fact, if you've got this far, you probably did say they're all okay. But actually, this one's not okay. Because when you say for all P and for all Q, that includes the case of Q and P being equal. That would mean everybody has to beat themselves at some time amongst everything else. So a player cannot beat every other player because the problem is no player can beat herself or himself, whichever you want. Okay? No player can beat herself. So that can't possibly be true. So this is the guy that can't possibly be true. And it can't possibly be true because the Q and the P have to be equal. What you would have to say if you wanted to make that something that could be true was you'd have to say for all P, for all Q, if P and Q are different, then there is a T, so it should W, P, Q, T. Then you'd be okay because you'd say for all pairs P and Q providing their difference, then at some time, at some game, P does beat Q in that game. So that would be a way of making it possible. But as it stands, that cannot possibly be true because players cannot beat themselves. Okay? So the issue was whether you can take the formula doesn't correctly tie them into what they say about the real world. It wasn't mathematics that was deciding these. It was the real world. And in the real world, players cannot beat themselves. Well, actually in a figurative way, players beat themselves all the time, but in the sense we're talking about here, that's not the case. Okay? Now let's move on to question four. Okay, now this expression is a colloquial expression, and so when I set this question up, I realised that for non-native speaking English students, this would be, this would be somewhat challenging.  The reason I like to give these kind of examples is because they capture an awful lot of social and cultural knowledge and there's an interesting challenge in capturing that kind of thing in formalisms.   But if you look at this one, this says for this person X, so these are all about a person X, they all talk about some person X. This doesn't say that person's a lover, this part says that person is in a relationship with everybody else. So this part because there's a universal quantifier that says X loves Z and Z loves X. So this person X is in a loving relationship with everybody. Well, that's nonsensical, so we can forget that one. So it comes down to these two because in each of these, it says the person is in a loving relationship. X is in a relationship with some Z and it's mutual. X loves Z and Z loves X. The same clause here. So the choice is between A and C. Well, let's look at what A, what A says. That says for all X and for all Y, if the X is in a loving relationship, then Y loves X. Now, the Y doesn't come in here so that the for all Y is to do with this part. So it says take any person X, if that person is a lover, then every person loves them, if they know them. So that actually is the correct one. Okay? All people love a lover. Of these three, that's the one, you know, you could argue about whether that's the absolute best interpretation, but out of these three, it's certainly a correct one. And so it's the one here. Let's look at this one. This one is a little bit different because it's got for all Y in here. So it says for all X, if X is a lover, then when it doesn't say then it says and for all Y, L, Y, X. So the for all actually applies to this part as well. So what this really, what follows from this is that for all X and for all Y, L, Y, X. In other words, everybody loves everybody. Well, that's not the case because this isn't conditional on being a lover. This just really says that's the case and that's the case. So part of this is saying that for all X and for all Y, L, Y, X. Well, that's not the case. I mean, it's not the case that everybody loves everybody. The world would be a nice place, I guess, if that was true, but it's not true. So it can't be that one. So we've eliminated this one because it doesn't capture, it doesn't use the fact that it's being a lover. And we've eliminated this one because it basically just boils down to saying everybody loves everybody and that leaves this one. And this is definitely one good interpretation of everybody loves a lover. Okay? So we were able to reason that one out and I would hope that even without the detailed understanding of what this means in English, there's only one of these that will stand up to analysis. Then after all, the idea is to sort of look at how the formalisms capture relationships from the real world. Well, for question five, we have to find which statements are false. Okay, so let's just hear what they say. For all X, for all Y, for all Z, if X is less than or equal to Y and Y is less than or equal to Z, then X is less than or equal to Z. That's true. It's actually known as the transitivity of the order relationship. Okay, if X is to the left of Y and Y is to the left of Z, then X is to the left of Z. Okay. So that one's true. What does this one say? For all X, for all Y, if X is less than or equal to Y and Y is less than or equal to X, then X is equal to all. That's true. Okay? The only way you can have X less than or equal to Y and Y less than or equal to X is if they're actually equal. What about part C? For all X, there is a Y. Well, that's certainly the case because given an X, you can take Y equals X, and then you'll have X less than or equal to Y and Y less than Y. So that one's true. It's beginning to look as though they're all true. Let's look at the last part. There is an X such that for all Y, Y is less than X, or X is less than Y. Well, you might be tempted to say, yep, given any X, it's the case that every other Y is either less than X or bigger than X. But wait a minute. Among the Ys governed by a universal quantifier is the X you start with. So if there was an X with that property, how could this happen? Because when you look at all the Ys, among those Ys would be X itself. So you would have X less than X, which is impossible. So that one's false. And it's false because the universal quantifier includes the X itself. Given an X, any X that you find, when you universally quantify over Ys, you include that X. And then that fails, and that fails. So there's the one that's false, and there is a false one. And it fails because universal quantifiers go over everything, and that means the Y, among the Ys that you're looking at, is the X that you start with. Okay? Well, for the last question on problem set four, which is question six, we have to look at this piece of reasoning that a student gave. This was actually when I first gave this course in the fall of 2012. And a student was trying to understand the Euclid's proof that the prime numbers are infinite in number. And there was a key step where you form that product when you add one, and the student wanted to verify that in fact, rain plus one was not divisible by a P, and came up with this argument. So I thought this would be a good answer to look at. It raises a number of interesting issues. So first of all, let's just see what the student does. Suppose N is divisible by P. Well, arguably the student, you could say the student doesn't begin by saying what N is, and doesn't say what P is. But I think in this context there's no need to. It's already been stated that N is an integer. It doesn't matter whether it's positive or negative, by the way. And it's already said that N is prime. So there's, in this context, I don't think there's any need to demand that the student repeats it here. What's key is that the student is writing down the assumption on which the argument is going to be based. Okay. So I'm going to say that I'll come to the various other issues in a minute. The opening I think is fine. Okay. That's good. What does the student do then? Then there's an integer Q. Should I say A equals PQ? Yes. That's a definition of divisibility. I'm not going to demand that the student spells that out because it's fairly clear what's going on. So N plus one is P percent of that's okay. Then dividing through by Q, by P. If I name this one over P. Now the student's now written a lowercase Q there. That's obviously meant to mean uppercase Q. I'm not going to worry about that. That's just a typo inviting it. Ditto here. So I'm not going to deduct anything for that. Those are just typos. I mean just using the wrong lowercase and uppercase confusion. So N plus one is not divisible by P. Okay. Logical correctness. Well in a sense this is okay, right? I mean everything steps fine. So I'm going to give three. Why aren't I giving four? I'll come to that in a minute. What about clarity? I've got to give four. This is absolutely clear what's going on. Stay at the conclusion. Yep. Conclusion stated. That's four for that one. A reasons given. Absolutely reasons are given. Yeah. I mean as I observed at the time the student sort of doesn't say this is by definition of divisibility and so forth. But you know there's a limit to how much you can write down within the context of this class and the intended audience which is the students in this class. Then this is fine. You know, it's fine to put more details in the reasons if you want to own the side of caution. But given the fact that this is absolutely clear, I think there's enough reasons given. Okay. And that brings me to the overall evaluation. And this is where I'm going to put a zero down. And this is also why I didn't give a full four for this because this is logically correct in terms of doing mathematics. But this is an argument about integers. And the integers is a number system in which you can add, subtract and multiply. What you can't do is divide. Division is not an operation on the integers. It's an operation on the natural, on the rational numbers and on the real numbers. But it's not an operation on the integers. So in going into division, this argument goes beyond the realms that we're permitted to use. So I'm giving a, I'm being generous here actually and saying I'll give you three because it's, this is mathematically correct in terms of the rational numbers. I mean I could have been tougher and I could have reduced it to two. I could have even put a zero down. But as I've said before, I'm looking for reasons to give people and take them away. We're trying to make people better thinkers, not to make them feel bad about themselves, okay? So I'm going to give credit where it's due. But strictly speaking it's not right. Here's what the students should have done. Okay, so we've got the first part. We've written n equals pq. Okay, that was okay. Okay. Now what I'm going to do is I'm going to argue by contradiction. I'm going to say suppose n plus one were divisible by p. Then there is an integer, call it r, so I said n plus one equals pr. Then we have n plus one minus n equals pr minus pq, which is p into r minus q. But n plus one minus n is one. So what I've shown is that p times r minus q equals one. That means that p, that means that one is divisible by p. But that's a contradiction. p is a prime number. So it's at least equal to two. So it can't divide into one. One isn't divisible by any, by two or three or anything. So there's a contradiction. Hence the original assumption here was false. Hence n plus one is not divisible. Notice that this is almost the same in a sense. This is equivalent to this. It's not the same but it's equivalent. Because the r here is n plus one over p. So this is the r. So I've said, I mean I'm sort of doing the same thing except here I'm not using division. I'm doing everything in terms of divisibility which means I'm doing it in terms of addition, subtraction and multiplication. All I'm using here is addition, subtraction and multiplication. I'm not using division. I'm getting around it by introducing this r, if you like. And that's a significant difference because we simply don't have division as an operation in the integers. We have divisibility which is a property that may or may not hold between two integers. But we can't divide one integer by another because division is not an operation in the integers. Okay?  I think I was generous with this one because I tend to be generous. And that means the total grade is 19. Okay? Well that was the end of the problem set for. How did you get on with assignment six? If you followed everything so far and managed to do fairly well on all six assignments, you should have a good idea of the kind of linguistic precision required in mathematics. Now we can start to put that precision to use in proving mathematical statements. In the natural sciences, truth is established by empirical means involving observation, measurement and the gold standard experiment. In mathematics, truth is determined by constructing a proof, a logically sound argument that establishes the truth of the statement. The use of the word argument here is, of course, not the more common everyday use to mean a disagreement between two people. But there is a connection in that a good proof will preemptively counter explicitly or implicitly all the objections, the counter arguments that a reader might put forward. When professional mathematicians read a proof, they generally do so in a manner reminiscent of a lawyer cross-examining a witness, constantly probing and looking for flaws. Learning how to prove things forms a major part of college mathematics. It's not something that can be mastered in a few weeks. It takes years. What can be achieved in a short period and what I'm going to try to help you do here is gain some understanding of what it means to prove a mathematical statement and why mathematicians make such a big deal about proofs. First, what is a proof and why do we use them? I'll answer the second question first since their purpose dictates what they are. Proofs are constructed for two main purposes, to establish truth and to communicate to others. Constructing or reading a proof is how we convince ourselves that some statement is true. I might have an intuition that some mathematical statement is true, but until I've proved it or read a proof that convinces me, I can't be sure. But I may also have to convince someone else, and that's the second purpose of a proof. For both purposes, a proof of a statement must explain why that statement is true. In the first case, convincing myself, it's generally enough that my argument is logically sound and I can follow it later. In the second case, where I have to convince someone else, more is acquired. The proof must also provide that explanation in a manner the recipient can understand. Proofs written to convince others have to succeed communicatively as well as be logically sound. There's actually not as much of a distinction here as my words might imply. For complicated proofs, the requirement that a mathematician can follow his or her own proof a few days, weeks, months, or even years later can also be significant. So even proofs written purely for personal use need to succeed communicatively. The requirement that proofs must communicate explanations to intended readers can set a high bar. Some proofs are so deep and complex that only a few experts in the field can understand them. For example, for many centuries most mathematicians believed, or at least held a strong suspicion, that for exponents n greater than or equal to 3, the equation x to the n plus y to the n equals z to the n has no positive whole number solutions for x, y and z. That was conjectured by the French mathematician Pierre de Fermat in the 17th century, but it wasn't finally proved until 1994 when the British mathematician Andrew Wiles constructed a long and extremely deep proof. Over the centuries it became popularly known as Fermat's Last Theorem. Since it was the last of several mathematical statements Fermat announced that remained to be proved. Most mathematicians, myself included, lacked the detailed domain knowledge to follow Wiles's proof ourselves. But it did convince the experts in the field, the field by the way's analytic number theory, and as a result Fermat's ancient conjecture is now regarded as a theorem. Fermat's Last Theorem is an unusual example however. Most proofs in mathematics can be read and understood by all professional mathematicians. Though it can take days, weeks or even months to understand some proofs sufficiently to be convinced by them. I've chosen the examples in this course to be understood by a typical student in a few minutes, or possibly an hour or so. Examples given to college mathematics majors can usually be understood with at most a few hours effort. Proving a mathematical statement is much more than gathering evidence in its favour. To give one famous example, in the mid-18th century the great Swiss mathematician Leonard Euler said he believed that every number beyond two can be expressed as a sum of two primes. This property of even numbers had been suggested to him by Christian Goldbach and became known as the Goldbach conjecture. It's possible to run computer programs to check the statement for many specific even numbers, and to date, 2012, it's been verified for all numbers up to and beyond 1.6 quintillion. Most mathematicians believe it to be true, but it's not yet been proved. All it would take to disprove the conjecture would be to find a single even number n for which it could be shown that no two primes sum to n. Incidentally, mathematicians don't regard the Goldbach conjecture as important. It has no known applications or even any significant consequences within mathematics. It's become famous solely because it's easy to understand, was endorsed by Euler and has resisted all attempts at solution for over 250 years. Whatever you may have been told at school, there's no particular format that an argument has to have in order to count as a proof. The one absolute requirement is that it is a logically sound piece of reasoning that establishes the truth of some statement. An important secondary requirement is that it's expressed sufficiently well that an intended reader can, perhaps with some effort, follow the reasoning. In the case of professional mathematicians, the intended reader is usually another professional with expertise in the same area of mathematics. Proofs written for students or laypersons generally have to supply more explanations. This means that in order to construct a proof, you have to be able to determine what constitutes a logically sound argument that convinces not just yourself, but also an intended reader. Doing that's not something you can reduce to a list of rules. Constructing mathematical proofs is one of the most creative acts of the human mind and relatively few are capable of true original proofs. But with some effort, any reasonably intelligent person can master the basics and that's my goal here. Euclid's proof that there are infinitely many primes, which I gave in the first lecture, is a good example of a proof that requires an unusual insight. Let's look at it again. Here's what we did. The idea was to show that if we list the primes in increasing order, then the list can be continued forever. So we imagine that we've listed the primes. P1 is 2, P2 is 3, P3 is 5, etc. All of it was some stage Pn. And we show that we can always add another prime to the list. And to do that, we look at this number n, which we obtain by multiplying together all the primes in the list so far, and then adding one. Now this number n consists of the product of all those numbers P1 through Pn plus one, so it's certainly bigger than all of those numbers. So n is bigger than all the primes in the list. Well, if n is prime, then we know that there's a prime bigger than Pn, namely n. In which case, we can continue the list. Probably not by adding n itself. n, because it's the product of all these plus one, is going to be a lot bigger than Pn, so n is almost certainly not the next prime. But that doesn't matter. If n is prime, it shows there is a prime bigger than the one at the end of the list, and that means we can continue the list. The alternative is that n is not prime. In which case, there's a prime q less than n that divides it. But none of the primes in the list can divide n. Since if you divide n by any of those primes, you're left with that remainder one. If you try to divide P1 or P2 or any of these primes into this number n, it gets swallowed up by this part, and then there's a remainder of one. Okay? So q has to be bigger than Pn. Those are the first n primes, so if q's not equal to one of those, it must be later on in the list. In which case, we've shown again that there's a prime bigger than Pn, and the list can be continued. Again, this particular q that divides n is not necessarily the next prime, but as before, that doesn't matter, showing that there is another prime is all you need to do because then you can take the next prime, whatever it is, and add it to the list. Either way, either if n is prime or if n is not prime, either way, there's another prime to add to the list. It follows that there are infinitely many primes, and the theorem's proved. There are two creative ideas in this proof. The first one is here to show that if we list the primes in increasing order as P1, P2, etc., then the list can be continued forever. So the first creative idea is to think about listing the primes and showing that the list can always be continued. The second creative idea is this one. Defining this number n in such a way that it guarantees that we can always find another prime. I would say that this idea is one that most mathematicians would come up with sooner or later. It's a fairly obvious one. This one is genius. Okay. This is true genius. Let me give you another example. And this time I'm going to prove that result I promised earlier that the square root of 2 is irrational. And I'm going to write it the way mathematicians typically do when they write up results for publication in professional journals or in books. Namely, we call it out by calling it a theorem. So in mathematics a result that's sufficiently significant or important that it's worth mentioning as such is called a theorem. In this context let me mention there's another word we often use called lemma. And a lemma is a result which is worth calling out for some reason but doesn't quite merit the status of being called a theorem. It's actually if you like a little theorem. Okay, the next thing a mathematician typically does is indicate that we're going to begin the proof. Okay? So this is just part of the way mathematicians lay things out. We specify the theorem and then we say we're going to give the proof. You don't have to do it this way. It's just a convention.  Proofs are about their logical structure, not the way we write them down. I'm going to begin by assuming on the contrary that the square root of two were rational. Now if you've never seen the proof that the square root of two is a rational before, this first step is going to seem pretty mysterious. Why do I begin by assuming the opposite of what I'm trying to prove? Well by the time I get down here, you'll see why. The reason this is a great example is in about six or seven lines, I can make it clear why I'm doing something right in the first step. Okay? Well in that case, if square root of two were rational then there were natural numbers pq with no common factors such that the square root of two is p over q. Remember a rational number is one that can be expressed as the quotient of two integers. In the case of a positive number it would be two natural numbers. And we can always pick those natural numbers or those integers to have no common factors. In other words, when we write a rational number as a quotient, we can always cancel out any common factors and express it as a quotient where the two numbers themselves have no common factors. Again it might seem a little bit mysterious why I'm being particular about any common factors but as with the first step by the time I get down here it will be clear why I'm doing this. Well squaring that equation gives me two equals p squared over q squared. Rearranging I get two q squared equals p squared. I multiply both sides by q squared that gives me a two q squared on the left and then when I multiply the right by q squared it cancels that q squared and I'm left with a p squared. So p squared is even. It's equal to twice something. Hence p is even. Why? Because the square of an even number is an even number, the square of an odd number is an odd number. So the only way I could get the square of a number p to be even is if the number p itself is even. Even squared is even, odd squared is odd. So p is two r for some r. I'm now going to take this equation p equals two r and use it to substitute back in this equation. So I take this equation, I've got two q squared equals p squared and p equals two r. So I've got two q squared equals two r all squared which is four r squared. Well forget the middle term now. I've got two q squared equals four r squared. I can cancel the two. Well if q squared is two r squared, then q squared is even. But exactly as happened before with p squared, if q squared is even, then q is even. Aha. You see what's happened? I've deduced here that p is even. I've deduced here that q is even. So p and q are both even. But they can't be because we assume p and q had no common factors. If they're both even, then they have two as a common factor. But this is impossible since p and q have no common factors. Well the logical reasoning here, the algebra, the arithmetic, is all sound. That's absolutely, everything's perfectly sound. How can we have arrived at an impossible conclusion by a piece of sound reasoning? Well the only thing that can possibly have gone wrong is we began by making a false assumption. Remember we began with an assumption. The only way we can have reached a false conclusion by a valid argument, and this is valid, if you don't believe me, go and check it for yourself, there's not many steps. See if there's anything wrong in any of these steps, there isn't. If we reach a false argument by a logical argument, then we must have started with a false assumption. Hence the original assumption that the square root of two were rational must be false. Hence, square root of two must be irrational. And when I was at school, teachers used to insist that we write QED at the end of a proof. Quadirat demonstrandum, which is Latin. It is actually not a bad idea to indicate when a proof ends. And mathematicians have different ways of doing it. Sometimes they write a little box at the end. How you express it, how you lay it out on the page is not that critical. I mean, the idea is to lay it out in a way that can be followed.  It's the logical flow of the steps. It has to be logically precise and you have to be able to follow it. But there's the proof. The reason this is a good example to give is it's short, it's concise, and all of the steps are simple arithmetical steps. It's very easy to follow every step, and yet when you follow this small number of simple steps, you've proved a significant result. In fact, this result when it was first discovered by one of the Pythagoreans in Ancient Greece was dramatic. It changed the course of Greek mathematics because until then they felt that quotients of integers were sufficient to measure any length. But square root of two is the length of the diagonal of a right angle triangle whose sides measure one. And when this result was proved by one of the Pythagorean mathematicians, it showed that quotients of integers were not sufficient to measure all lengths in geometric figures. And that changed the course of Greek mathematics and subsequently the rest of mathematics. It was extremely dramatic. Incidentally, there's a story you'll read about in books and on websites that say that this was discovered by a young mathematician and that the Greek mathematicians of the Pythagoreans were so annoyed and so scared that this would kill their career and their profession that they threw him overboard. There's absolutely no evidence whatsoever that that was the case. It's a great story, but like many stories it's probably not true. Okay, but in any case we've now shown that the square root of two is irrational. And there we go. I mean this is really a remarkable result, very short, very elegant. Incidentally, when mathematicians talk about aesthetics, when they talk about an elegant proof or a beautiful proof, this is the kind of thing they have in mind. Not that it looks beautiful the way it's written out, in fact I've just worked through it and it doesn't look particularly beautiful to look at, but the logical structure is beautiful. Every step counts, the result is established and every step can be understood fairly straightforwardly. The complexity doesn't come because there's deep results involved, deep facts, deep concepts. The proof works because of the structure, the logical structure. Okay, so now you know why root two is irrational. Let me say a little more about that proof. It's an example of what mathematicians call proof by contradiction. And proof by contradiction is a general method that works as follows. You want to prove some statement phi. You start by assuming not phi. You reason until you reach a conclusion that's false. Often by deducing both psi and not psi for some statement psi. For example, in the proof that the square root of two was irrational, we proved that P and Q have no common factors, and yet we knew that P and Q were both even. So we have a statement and it's negation. Or not strictly speaking it's negation, but close enough for these purposes. This is not an factor rendering of psi and not psi. But the point is we've deduced two contradictory things. It cannot be the case that they have no common factors and that they're both even. But a true assumption cannot lead to a false conclusion. Hence the assumption not phi must be false. Remember, we began by assuming not phi. We reach a false conclusion, a contradiction, a true assumption can't lead to a false conclusion, so the assumption must be false. In other words, phi must be true. If not phi is false, then phi is true. Well we begin by wanting to prove some statement phi, and we're going to end up with phi. And in the middle, we reason by assuming the contrary. So here's the contradiction proof going on in here. There's phi, there's phi. In here, we're reasoning with not phi. We start by assuming not phi and we reach a conclusion, a false conclusion, and conclude that that's false. Let me say a little bit more about this. We can look at proof by a contradiction in terms of truth tables. What can we conclude from a proof of theta yields psi where psi is false? In the case of the proof of root two being rational, the theta was the statement square root of two is rational, and the psi was the false statement that we never actually wrote out in full, that P and Q are both even and have no common factors, which is false, because there's no such, there are no pairs of integers which are both even and have no common factors. So in terms of the proofs by contradiction, the theta is the assumption you make at the start of the proof and the psi is the false conclusion you reach at the end. So I'm going to use truth tables to understand how it is that starting with an assumption and reaching a false conclusion leads to concluding that the assumption was false. And since the assumption was counter or contrary to the thing we're trying to prove, that would amount to proving a theorem. Okay. So I'm going to write down the truth table for theta yields psi or theta conditional psi. Right, the truth values down T, T, T, F, F, T, F, F. And we know what the table looks like here, it's T, F, T, T. Well if we've carried out a proof of this, that means this thing is true. So we can forget that line. We're only interested in what happens when this thing is true. So we've carried out a proof that this implication, this conditional is true. So it's one of these three. In this case, however, the psi is false. There's the psi false. Here psi is true. Here psi is true. Here psi is false. So this is the only line in the truth table which fits this. We have this being true, which means it's one of these three, and we have psi being false. That's the only possibility. In other words, theta is false. So when in a proof by contradiction, you make an assumption, a counter assumption, an assumption counter to what you're trying to prove, and you carry out some reasoning to deduce a false conclusion, a contradictory conclusion, or a contradiction. So you've established in your argument that this thing is true. This says that the argument is valid. Then the conclusion from having reached a false conclusion, the big conclusion, the global conclusion, is that your original assumption is false. Okay, it's a little difficult to explain this in words because we have to keep talking about truth and falsity and assumptions and conclusions and assumptions and sub assumptions and so forth. But if you go through the original proof that square root of two is irrational once more, and then think about it in terms of what I just said a moment ago about proof by contradiction in general, and then think about it in terms of this truth table analysis, and hopefully you should be able to understand why proof by contradiction work. It's a very clever idea, and they used a lot in mathematics, and I've just noticed I've misspelled truth tables, so let me put the L in there. Okay, there we go. That was a fairly lengthy discussion of such a short argument, but I know from many years of experience the beginners find the root to proof hard to really understand. You may think you understand it, but do you really? Let's see if you can produce a similar one. Try to prove that the square root of three is irrational. You should definitely try to do this exercise, but be prepared to spend some time at it. Go on, give it a try. I'll say it again. This course is about the process of thinking, not about getting results. You can use the thinking abilities you develop in a course like this to get results in other courses and in other situations in your life. It doesn't matter if you don't get the root three proof, you'll have benefited from trying. Truths by contradiction, which we use in the root two theorem, are a common approach because they have a clear starting point. To obtain a direct proof of some statement phi, you have to generate an argument that culminates in phi, but where do you start? The only way to proceed is to try to argue successively backwards to see what chain of steps ends with phi. There are many possible starting points, but just one goal, and you have to end up at that goal. That can be difficult, but with proof by contradiction, there is a clear starting point, and the proof is complete once you have deduced a contradiction. Any contradiction with such a wide target area, that's often a much easier task. The proof by contradiction approach is particularly suited to establishing that a certain object doesn't exist. For example, that a particular kind of equation does not have a solution. You begin by assuming that such an object does exist, and then you use that assumed object to deduce a false consequence of a pair of contradictory statements. The irrationality of the square root of two is a good example, since that states the non-existence of two numbers, p and q, whose ratio is equal to root two. Even though there is no cookie-cutter template approach to constructing proofs, there are some guidelines. We just met two. Proof by contradiction is often a good approach when there's no obvious place to start. And proof by contradiction is a useful method to prove non-existence statements. Of course, you still have to construct a proof. You've simply replaced a narrow goalpost with an unclear starting point by a much wider one with a known starting point. But like Robert Frost's fork in the trail, that choice can make all the difference. There are a number of other guidelines. I'll tell you some, but do bear in mind that these are not templates. As long as you continue to look for templates to construct proofs, you're going to encounter significant difficulties. You have to start each new problem by analysing the statement that you want to prove. What exactly does it say? What kind of argument might establish that claim? Let's look at another guideline. How might you go about proving a conditional statement? One of the form A implies B. We want to prove a conditional phi yield psi. When we know this is true if phi is false, so we can assume phi is true. Why do we know it's true if phi is false? Well, that was part of the definition of the conditional that we developed using truth tables. So to prove it, we assume phi and deduce psi. This of course confirms the point I made earlier that despite its strange definition, its counterintuitive definition perhaps, the conditional really does capture genuine implication because in all actual practical examples, when you try to establish a conditional, what you do is you assume phi and you deduce psi. And this is genuine implication. This says that psi is following from phi. For example, let X and Y be variables for real numbers and prove the following. If X and Y are rational, then X plus Y is rational. Okay, this is not a surprising result. This is nothing deep. I'm focusing not on the result but on the method I use to prove it. And so I've deliberately chosen an example that's extremely simple so that we can look at the process of reasoning that's involved in proving a conditional. So step one, assume X and Y are rational. In that case, there are integers P, Q, N and M such that X is P divided by M and Y is Q divided by N. Where in that case, X plus Y is P divided by M plus Q divided by N, which equals PN plus QM divided by MN. Hence X plus Y is rational. Okay, as I mentioned a moment ago, there's nothing surprising here. It's almost not a proof at all. It's just really adding two things together. But it actually is a proof because it has the right structure of a proof. Here's what we did. We began by assuming X and Y are rational. We concluded that the sum is rational. And in the middle, there was an argument to demonstrate that fact. The argument was actually fairly typical in what we first did was take the assumption and then unpack the assumption in terms of some useful information. And once we'd done that, we reasoned with that information to get a conclusion that in fact was the thing we were aiming for. So we write down the assumption, we carry out some reasoning and we reach the conclusion. All three steps are important. Declare the assumption, carry out the reasoning in a clear, understandable fashion, and then state the conclusion when you've reached it. Remember that proofs have two purposes. One is to convince yourself, and two is to convince other people. And you may know what you're doing if you don't mention what your assumption is, or what your conclusion is. Or I'll guarantee from experience that a week from now, you'll forget exactly what you were doing. So it really is good, even for your own purposes, to write down what your assumptions are. But certainly from a communicative angle, it's important to begin by stating the assumption, then to lay out the reasoning in a simple understandable fashion, and then to state the conclusion that you've reached. Okay? Well, that's the most basic method of proving a conditional. Let me give you a quiz. Let r and s be irrational numbers. See which of the following are necessarily irrational. And let me stress that word necessarily. Number one, r plus three, number two, five times r, number three, r plus s, number four, r times s, and number five, square root of r. No, this is a quiz format, where I'm just asking you to select the ones that you think are necessarily irrational. But unlike most of the quizzes, where I expect you to be able to answer very quickly, I'd like you to think a little bit before you answer each of these. Because the focus isn't really on getting the answer right. I mean, obviously I want you to get the answer right. I'm sure you do too. But that's not the focus. The focus is on the reasoning that you need to carry out in order to get those answers. In each case, you're probably going to have to carry out one or two lines of simple reasoning in order to answer the question. That's the focus of this particular quiz. In fact, in the assignment that's coming up in assignment seven, I'm going to ask you to write out proofs of each of the five answers. So let me stress that the focus is on the logical reasoning. Okay, see how you do. Well, the ones that are necessarily irrational are one, two, and five. In each case, you use the fact that a rational number is one that can be expressed as a quotient of two integers and an irrational number is one that cannot be so expressed. And then you carry out a couple of lines of reasoning to show that r plus three has to be irrational. If r plus three was rational, then r would be rational. Likewise, you would carry out a couple of lines of reasoning to show that if five r was rational and could be expressed as a quotient of two integers, then so could r. And similarly, you carry out a similar argument for the square root of r. The two that are necessarily irrational are three and four. In order to show that r plus s is not necessarily irrational, what you would need to do are find examples of irrationals r and s for which the sum is rational. Well, how about taking r is a square root of two and s equal to, let's say, ten minus the square root of two. r plus s is equal to ten, which of course is rational. It's an integer. We know that the square root of two is irrational, and a very simple argument shows that ten minus the square root of two must be irrational. In fact, the argument you show that this number is irrational is a combination of the two arguments you used in parts one and two. Okay, so r and s are irrational, but their sum is rational. In the case of this guy, we could take r equals square root of two and s equals square root of two. r and s are both irrational, and yet r times s is two, which is rational. Okay, how did you do? Remember that then in assignment seven, I'm going to ask you to give proofs of each of the five answers. Well, conditionals involving quantifiers are sometimes best handled by proving the contrapositive. What's the contrapositive? Well, we met that in assignment four. So to prove a conditional phi yield psi, what you can do is prove not psi yields not phi. That's the contrapositive of phi yields psi. You reverse the phi in the psi, and you put negations in front of them. And in assignment four, if you look back, we prove that those two are equivalent. We prove that using truth tables. So let's look at an example of how this might work. And the example I'll take is this one. I want to prove that if the sine of an angle theta is not equal to zero, then for all n in the natural numbers, theta is not equal to n pi. Okay, there's a conditional. And I'm in the middle of some argument, we'll imagine, and I want to prove that if the sine of theta is not zero, then theta is not a whole number, multiple of pi. Where the statement's equivalent to not the case that for all n in n theta not equal to n pi implies not that sine theta is not zero. But there's lots of knots in here, so let's clear them all out and put this into a positive form. So in positive form, this is not for all n in n. We're going to get the exists n in n, and the knot is going to move inside, and it's going to negate this knot. It's going to wipe that one out, and then I'm going to have theta equals n pi. Yields, knot that sine theta is not zero means that sine theta is zero. So this is the contrapositive of this. And that's the thing we're trying to prove. Well, we know this. We know that whenever you've got a whole number multiple of pi, its sine is zero. So this proves the desired result. Obviously, this is a highly contrived manufactured example. Again, the focus is not what I'm actually proving. It's the method I'm proving. I'm picking simple examples so that we don't have to worry about the mathematical content. We can just look at the logical reasoning. And in this case, we start out. We want to prove something. We replace it by the contrapositive, and then we prove the contrapositive. In this case, the proof of the contrapositive, we just pull on well-known knowledge about the sine function. That the sine crosses the x-axis whenever you're at a whole multiple of pi. Okay, let me tell you about one more thing involving proofs of conditionals. To prove a biconditional, phi equivalent to psi, we generally construct two proofs. One of phi yield psi, the other of psi yields phi. And since the biconditional is just a conjunction of the two conditionals, that clearly amounts to a proof of the biconditional. Occasionally, it's easier to prove the two conditionals phi yield psi and not phi yields not psi. And I'm going to leave you to find out why this is enough. Why does this work? If you look back at the assignments, you should find a clue as to why it's enough to prove these two in order to prove the biconditional. Okay, now I'd like you to complete assignment seven. As usual, completing an assignment means at least you should attempt all of the questions. You may not be able to get them all out, at least not at first. But remember, the benefit from working on the assignments in this course is actually trying them. Whether you get them out or not is not that important. Remember my favorite example of learning to ride a bike? The fact that you don't succeed in riding a bike for many days or weeks when you're learning doesn't mean you're not making progress. The same with learning to swim. You actually get the benefit during the process when you're trying and failing, and then suddenly you find you can either ride the bike or you can swim. And it's the same with this kind of material in this course. Okay, good luck on assignment seven. Well, I wonder all of the questions in assignment seven, but there's still a few of them. Starting with number one, prove or disprove the statements, all bears can fly. Well, we'll find a counter example. I mean, that's false. And to show it's false, what I need to do is to find a counter example. And an obvious one is the ostrich. That's a bird that can't fly. So we've got a counter example. Okay. Well, now let's look at number two. Prove or disprove the claim for all x in r, for all x and y in r, x minus y squared is greater than zero. That's also false. And again, it's approved for something that's a universal quantifier. I just like the one above it, it's a universal quantifier, or in this case two universal quantifiers. And it's approved that a universally quantified statement is false. What you need to do is find a counter example. Well, that's one way of doing it at least. And the most obvious one here, well, anything that takes x and y equal will do it. So let's give a specific counter example. Let's take x equals y equals one. And in that case, x minus y squared equals zero, and zero is not strictly greater than zero. Okay. It came close, right? If we'd excluded x and y being zero, then we'd have a positive result. But it says it's true for all x, y in r, and a single counter example is all it takes. And in this case, any pair of equal numbers gives us a counter example. Okay, number three. Prove that between any two and equal rationals there's a third rational. So let's let x and y be rationals, x less than y. Okay. Then, because they're rationals, x is p over q. We can write y is r over s where p, q, r and s are integers. And we have to show there's a number between. Well, the obvious thing is to take the mean. Let's just take x plus y over two. And if that's rational, then, then we'll prove the result. Well, here's the proof that it's rational. X plus y over two is equal to p over q plus r over s over two. Okay. Which is p s plus q r over q s all over two. Which is p s plus q r over two. What was it, q s? Can't see underneath my hand here. Which is rational because it's a quotient of two integers. But of course, x is less than x plus y over two is less than y. And we're done. Okay, that's one, two and three knocked off very, very, very quickly. Let's go on to do number seven, the one about square root of three. Well, just as we did with the square root of two, we're going to prove it by contradiction. So, I'm going to assume square root of three were rational. Then, I could write three root three is p over q where p and q are natural numbers. And I can always assume that they have no common factors. Okay? Because if you pick a pair of integers, a pair of natural numbers that do have a common factor, you can cancel it out. So, you can always express a rational number in that form. Then if we square that, I get three is p squared over q squared. So, I can multiply across by the q squared and get three q squared equals p squared. So, three divides p squared. But three is prime. And if a prime divides p squared, that means three divides p. The prime divides a pair of numbers multiplied together, it divides one of the numbers. So, three divides p. So, that means p is of the form three, let's call it three r. Okay? So, that means p squared equals nine r squared. So, I can take p squared and substituting it back in here to get three q squared equals p squared equals nine r squared. So, if I forget the middle term now, three q squared equals nine r squared. Let me factor the three out. I've got q squared equals three r squared. So, that means three divides q squared. But if three divides q squared, then just as before with p, that means that three divides q. And now I've got a contradiction. Since p and q have no common factors, then yet we've just shown that three is a common factor. So, there's a contradiction. Almost exactly the same as the one for square root of two. So, if we compare the two, cf, the proof for square root of two. In the case of the square root of two, we talked about numbers being even. But if we talk about something like p being even, that's just another way of saying two divides p. So, really all I've done here is I've taken the free risk proof, the one for root two. And instead of talking about it in terms of even and odd, I could recast it in terms of whether it's divisible by two or not. And then the facts, the fact about two that we use there, we said if two divides p squared, then it divides p, it used the fact that two was prime. So, I might just as well use three. So, it's exactly the same proof as before, except instead of talking about divisible by two, I'm talking about being divisible by three. I didn't express it that way before. I talked in terms of even and odd. But even just means it's a multiple of two. Okay, well, we've moved on. Let me decide which one to do next. I think I'll do number eight. That shouldn't take too long. So, we'll do number eight next. Okay, so the converse of an implication, of a conditional, is the implication in the opposite direction where you swap around the antecedent and the consequence, but everything remains more or less, otherwise unchanged. So, the converse of this is if the yarn rises, the dollar falls. We just swap them around. Same here. If negative y less than negative x, then x is less than y. And in the case of c, if two triangles have the same area, then they are congruence. Now, in terms of what we're doing, this is totally trivial. This is just swapping things around without doing anything. What I'm really trying to get at with this exercise is in part to contrast it with the contrapositive. And also to observe that truth and falsity can change. In this case, we start out with something that's true. This is a true implication. That's a true implication too. So sometimes the converse of a true implication is a true implication. Let's look at this one. If two triangles are congruent, they have the same area. That's true. But this one, if two triangles have the same area, they're congruent, that one's false. So sometimes the converse of a true statement is true, and sometimes the converse of a true statement is false. Now, that's a different situation from what we find with the contrapositive. But when you swap around the order, you can sometimes get truth going to false, and you can sometimes preserve truth. Okay, well, that's really all of this to that. It was just to sort of give an opportunity to reflect on these things and to recognise that truth and falsity plays its own game when you're dealing with converses. Okay, let's go on and do number 11. Okay, that was that one about the rational numbers. We've already looked at some of these in the lecture where we've observed that some of them are rational. Let me see we observe that this one can be rational. We observe that this one can be rational. And there's an issue about this one being rational. Okay, these were easy. We did those in the lecture. That was a later issue. That leaves one, two, and five. They're the ones where they're irrational. And so we have to prove them this time. Okay, and so starting with number one, say, what we're trying to show is that it is irrational. So yes, it's irrational. Okay, and let's see. Suppose, suppose that r plus three were rational. Okay, that's a plus sign there. Then r plus three would be of the form p over q, where p and q are integers, where then r would equal p over q minus three, which is p minus three q over q, which is rational. And that's a contradiction, because r is assumed to be irrational. And we've shown that if r plus three were rational, then r would have to be rational. And the others are similar. You simply assume the contrary, you express it in terms of p over q, and then you do a tiny little amount of manipulation, and you end up showing that the number r is rational here, and that square root of r is, and that r is rational in the square root example. Okay, very straightforward. Nothing really more to be said about this one. Okay, the only one left now to do on assignment seven is question 12, so let me just quickly go through question 12. Well, the key facts that you use in dealing with all of these are that if n is even, then, and actually if and only if, then n is 2k for some k, some integer k. Okay? And that n is odd if and only if n equals 2k plus 1 for some k. Okay, the even numbers are the ones that are multiples of two, and the odd ones are the ones that are one more than the multiple of two. Okay, they've been between the multiples of two. So for example, if we do part a, if m and n are even, then we would have m equals 2k. For example, we'd have n equals 2l, so m plus n would equal 2k plus 2l, which is 2 into k plus l, which means it's even. It's 2 times something else. Do I need to do one more? Well, let me just do one more anyway, just because I've, I mean, I'm on a roll now. Let me do a number d, part d. If one of them is even, it's 2k, and the other one's odd, it's 2l plus 1, then m plus n equals 2k plus 2l plus 1, which equals 2 into k plus l plus 1. Okay? So it's two, it's twice something plus 1, et cetera, for all the others. Okay? Nothing terribly deep about, about these things, but in terms of providing out a proof, it's basically a case of just capitalising evens and odds in this way, and doing a tiny amount of algebra. Okay, that was a very easy assignment, I think. Well, it was meant to be an easy assignment, it's easy for me to say that, right? I've been doing this for years. If you haven't met this kind of thing before, then it probably isn't an easy assignment. I fell into the trap of mathematicians there of of saying something's easy in the same way we talk about trivial. That's the sort of a term of art that we use in the game. So everything's easy when you know how to do it, right? Okay, but I was looking ahead to assignment 8, which was decidedly difficult for me and for you guys. Okay, assignment 8 coming next is difficult. Question 1 in problem set 5 asks us to judge whether this is a valid proof or not. Well, certainly the algebra looks correct, right? If M and N are odd, then by definition an odd number is simply one that's not even and an even number is one that's a multiple of 2. So an odd number has to be of the form 2P plus 1, so that's okay for some P and for some Q. So if the odd introduces that, in which case multiplying them together, you get that, the algebra's correct, so M and N is odd. Everything's so far to this part because it doesn't complete the proof. What we've shown is if. We've shown that M and N is odd if M and N are odd. In other words, we've proved the implication that way, okay? If M and N are odd, then M and N is odd. So in this statement, we've proved the right-left implication and we need to show the other part. We need to prove the only if part. In other words, the implication from left to right. It's if and only if. So we've proved the if part from right to left. We need to prove the only if part from left to right. Ie, we need to show, let's write it out in full. If it's not the case that M N are odd, then M N is odd. Is not odd. Yeah, is not odd. Okay, there are various words you can talk about this, okay? Ie, but if it's not the case that M N are odd, that should have been a comma there. Okay. If it's not the case that M and N are odd, then M times N is not odd. Okay? I got the tense correct, the plurality, that was I and that is. Okay. If at least one of M and N is even, then M times N is even. If M equals two K, it doesn't matter which one we assume is going to be even because multiplication is going to be commutative. If M equals two K, then M N equals two K times N, which is even. So this was hard, this is hard to going to set the world on fire, right? I mean, there's nothing terribly deep about this. It's extremely elementary. And it's not that you don't know this and understand it. The question is, can you write it down in a proof? And the point here is that if M equals two K, then M N equals two K times N, which is odd. And the point here is that we have to start with the definitions. And the definitions are, N is even if and only if there's an integer K, so it's that N equals two K. And N is odd if it is not even. So starting from these two definitions, this is the proof we give. The first part that was actually given to us, that was fine from those definitions. We started with the definitions. Going the other direction, we took the definition. So the question is simply, all this really involves is reducing this to the definition. And then the argument itself is very simple. That was a slightly more complicated bit of algebra, but not much more. So it's not about the complexity of the algebraic manipulations. You've been able to do that for years, I know that. The question is, can you reduce the statement to something coming from the definitions? Of course, in many cases you simply would. This would be so simple compared with most proofs in mathematics. You wouldn't go into these details, but the focus here isn't on the, at this stage, isn't on the complexity of the argument. The focus is on the structure of the argument. Are you able to get the logical structure right? And experience tells me that it takes most of us, and it certainly took me a long time to get the sense of what do I have to prove in order to prove something? That's not something that's not cookie cutter. You've got to build up experience in what constitutes a proof and be able to judge whether a proof is correct or not. Okay, let's go ahead and look at number two now. Let me jump first of all straight to the correct answer. And the correct answer is A. This says there are people and there are times at which you can fool those people. So you can fool some of the people, some of the time. Remember, existence quantifiers are what we use in mathematics to capture the word some or at least one. A little bit atypical in terms of what the word some means in everyday language. Okay, and here the way I've expressed it is there is a person and there is a time such that you cannot fool that person at that time. Okay, there's a person and a time such that you cannot fool that person at that time. Which is actually equivalent to saying you can't fool all the people all the time. Formally you could take that part and you could rewrite it as it's not the case that for all x and for all t, fxt. It's not the case that you can fool all the people all of the time. Okay, but I wrote it this way because we're only asking for the equivalence. I'm not saying which is the closest way of capturing it. I'm just saying which is one's equivalence. Okay, let's look at part B. What does this, well does the first part look the same in all of these three? So the distinction is in the second part. So let's see what this one says. Can we express that in English? Well this is tricky to express in English because of these American Melanoma Foundation type issues. I mean you could say something like, oh let's say you can't fool everyone. Let's try something like this. That's some time or other. For everyone it's the case that you can't fool them at some time or other. I mean really what it says is it's not the case for every person. There's a time when you can fool them. Okay, so you can't fool everyone at some time or other. Yeah, that's sort of, I can't think of a way of saying this that really makes, that reads well in English. And yet which really captures this. But hopefully it's clear what the thing means. It's not the case for every person. There's a time when you can fool them. Okay. To me that says the same but you may interpret that one different. Because this is one of these things like American Melanoma Foundation that it's ambiguous as natural language softness. Okay, let's see again in the case of this one, what does this one say? It's not the case that there is an X and there is a T so that you should conform. This one I think is easy to say in English. Okay, it basically says you can never fool anyone. Okay, it's not, you cannot find a single person in a single time, such that you can fool that person at that time. You can never fool anyone. So this one I'm very happy with. Okay, that one really captures it. And the smiley doesn't indicate that I think that's true. It indicates that I think that's a really clean interpretation of what that one means. And number four doesn't arise because we've already found something correct. Well questions three, four and five were just truth table arguments. That was essentially revision material. So I won't go through those here. Let's just take a look at question six, which when you first meet it looks as though it might be terribly deep, especially since we've seen this now after we've looked at things like square root of root two and square root of root three. But actually this one, when you step back and think about what it says, turns out to be very simple. We simply observe that whenever n is a perfect square, in other words, it's the square of some integer, any integer, no infinitely many integers, so there are infinitely many perfect squares. Then of course the square root of n is just k, which is rational. And that's all that is to that one. I mean not only is it rational, it's a whole number. The point is there are infinitely many numbers n for which the square root of n is a whole number and hence rational, namely all the perfect squares. Okay, that's all that is to that. You don't really need to say any more. That's it. That shows that it's true and it tells you why it's true. And that's the proof. Of course you only asked really to sort of say whether it was true or false. But it was this that I was interested in. Can you construct a proof of its negation, of it or its negation? That was really what it's about. It's all about proving things here. Okay. Well finally, question seven is one of these fallacious proofs. There's a whole range of these things. Quite amusing. Usually they depend upon dividing by zero in some disguised form. This one's different, okay? So let's follow it through. Because normally the point is just to find the mistake. We're clear that there's going to be a mistake because one doesn't equal two. And indeed one of the things I asked you to do was to find the mistake. But the focus here isn't so much on finding the mistake. It's on how do you grade this as a proof? And remember when we're grading proofs, logical correctness is certainly part of it so there's going to be some losses of grade here. But also it's about communication. Okay. So let's go through this one and just see how we would grade the thing. Okay. Well for example, is it clear? It's absolutely clear. So we're going to have to look at four marks for clarity. Is it very clear? There's a good strong opening. We start with the identity. One minus three equals four minus six. Okay. Both sides are equal to two. So full marks for giving the idea of the opening. The conclusion is stated. So it's four marks for stating the conclusion. And reasons given, yes. Absolutely. Adding nine plus four, nine over four to both sides. This is completing the square to give you a perfect squares. Then we're seeing factors, which it does. That's why we added nine over four to both sides. Taking square root of both sides. Absolutely. Reasons, reasons, reasons. So in terms of the structure, this is wonderful. Now overall I'm going to have to give you zero, right? I mean that's clear because the thing is plain false. The question is, you know, what do I give for logical correctness? Well, first of all we need to identify the identity, where the errors are occurring, right? And the errors here, it's in this line. Because when you take square roots, then of course there are positive and negative square roots that we had. And in fact the correct solution is to say the minus left hand side, the negative root on the left hand side minus one minus three over two. And it's the positive root you would take on the right hand side when you take square roots. So that's what you should have. In other words, three over two minus one equals two minus three over two. In other words, a half equals a half. Okay, so no big deal there. I mean that's nice. The world still exists. A half does equal a half even though all doesn't equal two. So the issue here was when you're taking square roots, there are two possible signs. And the one that makes it valid is the negative on the left and the positive on the right. Okay. So this is where the mistake is. The only question is, do we give partial credit for the fact that there's logical correctness everywhere else? This is a judgment call. I would say that these steps are so simple. It's just a very elementary algebra arithmetic that at this level, I'm not going to give particular credit for getting these bits right. And I'm going to say this is a big mistake. This is huge. Okay, when you take square roots, you have to take a plus for a minus. That's a mathematical mistake. Realising that. Not recognising that you need to worry about the signs when you take square roots. So that's a bigger of a mathematical point of view. So this grading that I've given it, which means I'm actually giving 16, means I'm giving no points at all on the mathematical correctness. I'm giving lots of credit on everything else. Now, if this was a mathematics course, I wouldn't be using this rubric this way. I would take account of these, but they would have less weight. I mean, these have all got the same weight at maximum of four. And that's because the focus of this course is on proofs and reasoning and communication. And these are important parts of that. You know, the assumption in this course is that you already can do some mathematics. And so I'm not really grading you on that. I'm grading you on mathematical thinking and mathematical communication. So there's zero marks here on the mathematics, but there's four marks and everything else. And this is the reason why I did this one. This is where everything is well laid out, but the thing is playing wrong. So it distinguishes between mathematical correctness and the mathematical thinking and the communication and then writing a proof out correctly. Having said that, in this case, it's blatantly obvious that something's gone wrong. But very often in mathematics, mathematicians, professional mathematicians make mistakes, buried in proofs. And because they're professionals, they can usually write things correctly. We know how to, we learn as part of becoming mathematicians, we learn how to write things out, we give reasons. So in fact, this, although it looks absurd here, you often find that because mathematicians know how to lay things out well, results get published even though they're absolutely wrong. And whenever result gets published, basically what that means is that the referee of the journal where it's published has graded it and said, this is, this is correct, this is absolutely correct. So, you know, this is not an unrealistic situation in principle when false results get proved and when false results get published, that is, of course they never really proved. The false results get published when what's going on then is that the referee has gone through it and thought everything's okay. Okay. Here it's dramatic because the answer's absurd and it's blatantly false. But this is actually not an unrealistic scenario. And so giving a high grade isn't, it's not a bad thing. I'm doing this to emphasise the distinction between the various things we're looking at here. And this one, I think, makes it clear that there are other issues involved other than, other than logical correctness. But as I say, if this was a regular mathematics course, I wouldn't be giving 16 out of 24. In fact, I'm not even sure I'd give any marks for this if a student came up for this because it really, this is really a big mistake. Okay. But within this context, within the context of this course, this is the kind of thing we're looking for in looking at mathematical thinking and mathematical proofs and communication. Okay. There we go. Well, that's the end of the problem set questions. But let me leave you with one more tantalising little puzzle. We are probably familiar with the story of Archimedes, lived in Greece about 250 BCE or thereabouts, who was asked by the king to determine whether a crown he'd been given was actually made of pure gold or not and that involved calculating the density. And he knew how to calculate to find out the, the, the mass of the, the weight of the crown. But the question was how do you calculate its volume? No, no, Archimedes knew lots of mathematics for calculating volumes. Indeed, he'd invented a lot of that mathematics. He was able to calculate areas of circles and volumes of spheres and various other shapes like boxes and rectangles and pyramids and so forth. He knew all of that stuff. So he had a lot of mathematics at his disposal that he could have applied. But it didn't seem to work for something irregular, like a crown or at least not easily. But then one day when he's taking a bath, this is the story, the story goes, when he's taking a bath, he has this, this amazing insight. He says to himself, if I immerse the crown in water, it will displace some water. In fact, the amount of water it will displace is exactly equal to the volume of the crown. So if I collect the water when it spills out of the bath and when I put a crown inside it into the water, then I'll be able to just measure the volume of the water in a standard way and I'll know the volume of the crown. And, and as that story goes, he was so impressed and tickled by his solution that he jumped out of the bath and ran stark naked through the streets crying out, Eureka, Eureka, which is Greek for I found it, I found it. Now, I've known lots of mathematicians, I certainly haven't known Archimedes, but I doubt if even a mathematician deep in the throes of solving a problem would run naked through the streets. However, I can imagine him being extremely pleased with himself and having a great adrenaline rush when he had that insight, because that's a great example of thinking outside the box. He knew lots of techniques for calculating volumes. He invented many of them, but on this occasion he thought outside the box and found a really elegant solution that was different. And the puzzle I'm going to give you is very much along those lines and it actually is about taking a bath. And here it is. If it takes half an hour for the cold water faucet to fill your bathtub and an hour for the hot water faucet to fill it, how long will it take to fill the tub if you run both faucets together? Now this looks like one of those frustrating little word problems you get in high school, okay, where you end up, you sort of say that the rate of flow of the cold water be F and then T and you write down some equations and you figure something out, okay. And I'm sure you know how to do that. You can apply a standard technique for doing this kind of thing involving rates of change and you get the answer. But you don't need to do any of that. You don't need to do any calculations at all in order to solve this one. If you think outside the box, you can answer it without doing any of those calculations based on the rates of flow or anything like that. You simply have to think of the problem a different way. If it helps, if you're inspired by the Archimedes story, you might want to run a bath and get in the bath and see if you can come up with the idea then. I must admit from personal experience that a lot of my best ideas in solving mathematical problems and improving mathematical theorems throughout my career have actually been obtained when I've been sitting in a bath or shortly after taking a bath. There's something so relaxing about getting in a bath that it frees the mind to come up with these out of the box solutions. So this isn't really about do you know the standard methods? You probably do. This is about can you think about this in a different way that allows you to solve it without really doing any of this music whatsoever. Okay? Well, with that hint, I'll leave you to it. Enjoy. How did you get on with assignment seven? In this lecture, I'll say something about how to prove statements that involve quantifiers, which is true for almost all mathematical theorems. Universally quantified statements of the form for all natural numbers N, some property A N holds, where the quantification is over all natural numbers are often proved by a method known as induction. I'll explain the method of induction with some examples from number theory. Number theory is one of the most important branches of mathematics. It studies the properties of the natural numbers, one, two, three, etc. We look at some elementary parts of the subject in later lectures, but for now it provides good examples of induction proofs. But first, let's look at how we might prove an existence statement. We want to prove there exists x such as A of x. The obvious way is to find an object A for which A of A. For example, to show that there's an irrational number, just prove that square root of two is irrational, which we did. Unfortunately, this doesn't always work. Sometimes we use indirect proofs. For example, I worked through that problem about the cubic equation, where we showed that there was a point on the x axis where the curve crossed it, and hence that the cubic had a solution. We never found the solution, we just showed that one existed. Let me give you a really fascinating example of an indirect proof. I'm going to prove that there are irrationals, R and S, such that R to the power S is rational. That actually came up in assignment seven, if you remember, and I promised then that I would do this later. Well, now is that later. The proof involves considering two cases. Case one, if the square root of two raised to the power square root of two happens to be rational, we can take R and S both equal to square root of two. Then, by the assumption that square root of two to the square root of two is rational, we've shown that there are numbers R and S which are irrational with R to the power S rational. Well, if case one isn't the case, then we must be in case two, which is where root two to the root two is irrational. In which case, take R equals square root of two to the square root of two, and S equals square root of two. And if we do that, then R to the power S is root two to the root two, all to the root two, which by the way that exponents work is root two to the power root two times root two, which is root two squared, which is two, and two is rational. So, again, we've proved that there are irrationals R and S such that R to the power S is rational. Taken together, case one and case two prove the theorem. I really like this example. It's not just clever, but it's cute, and it's cute because of the way it works. We really don't know whether this number root two to the root two is rational or irrational. It's probably irrational actually, but the point is we don't need to answer that question. We just look at the two alternatives. If it does happen to be rational, seems weird, but if it does happen to be rational, then we can find irrationals R and S without the S rational this way. On the other hand, if root two to the root two is irrational, which probably is the case, but again we don't need to know that, then we take R to be this number, S to be that number, and then R to the S is two, which is rational. So we don't know officially which one of these is the case, and more to the point, we don't need to prove which one of these is the case. We simply look at the two alternatives, and depending on which alternative we're in, we take different rationals, we take different irrationals R and S with R to the S being rational. So the choices of R and S are different in the two cases, but because these two cases exhaust all possibilities, this number is after all either rational or irrational, then this proves the result. By the way, this is known as the method of proof by cases, and it's a method that's used a lot in advanced mathematics. Pretty neat, eh? Well now let's take a look at how we might prove a statement involving a universal quantifier. Suppose we wanted to prove a statement for all x, a of x. One way is to take an arbitrary x and show that it satisfies a of x. For example, to prove that for all n, there is an m, m bigger than n squared, where the variables m and n range over the natural numbers, but this is a pretty trivial example. But I want to focus on the method that you would use to handle the two quantifiers in a statement like this, where in particular the first quantifier is a universal quantifier. Let n be an arbitrary natural number. Set m equal to n squared plus 1. Then m is bigger than n squared. And this proves the statement, there is an m, m bigger than n squared. And it follows that the statement for all n, there is an m, m bigger than n squared is true. Okay, well as I said, this is pretty trivial. Let's just see what's going on in terms of the logical reasoning. You want to prove a statement involving two quantifiers of the form for all n, there is an m, m bigger than n squared. What we're going to do is eliminate one quantifier by replacing it by an arbitrary natural number. Now by arbitrary, I mean we make no assumptions at all other than the fact that it is a natural number. The argument will have to hold for any natural number whatsoever because we're trying to show that this is true for all n. So we pick an arbitrary one. Then we carry out some reasoning to verify the rest of the formula. Okay, when we eliminate that for all n, we're trying to prove that there is an m, m bigger than n squared, which is this statement. Now in this case, it's a trivial argument. We just square n, add one, and let n be that number. So we explicitly find an m that satisfies this property. In practice, you're probably going to have to do a lot of work here with a more significant example. There could be several lines or even pages of arguments involved at this stage. But the point is you eliminate the first quantifier by picking an arbitrary n, then you carry out some reasoning to prove the rest of the formula, which is this thing here. And when you've done that, because the argument works for an arbitrary natural number, it follows that you've proved it in this form. The for all n has been handled by reasoning with an arbitrary natural number. So we've taken away one of the quantifiers, carried out some reasoning, and proved the result. But let me stress that this works because the n that we pick is arbitrary. Well another approach would be to use a method of contradiction. To prove for all x of x, assume not for all x of x. This is equivalent to exist x, not A of x. Well, let c be an object such that not A of c. Notice that this isn't an arbitrary object. It's a specific object, admittedly an object whose identity we may not know, that is guaranteed to exist by this. The point is to prove this universal statement we began by assuming it's negation. It's negation gives us an existential statement, and that tells us that there will be some object, a specific object, for which not A of c. Now we've got a starting point to carry out a proof to derive a contradiction. Now a reason with c, together with the fact that not A of c, to derive a contradiction. Now the exact reasoning you use will depend upon what the statement a says. But the general pattern is this. You want to prove for all x of x, and you're going to use contradiction. So you assume not for all x of x. That's equivalent to exist x, not A of x. And that tells you you can find an object, or at least you know that an object exists for which not A of c. And then if you can, you reason with that object using the fact that not A of c, to derive a contradiction. Okay, again, we'll see examples of this later on. I'm just giving you the general overview of the way these arguments work. So, as in the previous case, if this looks a little bit mysterious, it'll become clearer, I hope, when we look at some specific examples later. In fact at this stage you might want to look back at assignment 7 and see what was going on there in the light of one I've just said here.  Well, the correct answer is no. This is not a valid proof. The point is, picking a positive rational p arbitrarily is not the same as letting p be arbitrary. The choice of p may indeed be arbitrary, but once you've made it, you've got a specific p. We've even said what it is. That's actually different from saying let p be arbitrary. An arbitrary choice of p leads to a specific p, which you may have chosen arbitrarily, but you might have been unfortunate in your choice. You might have chosen a p that just happens to make something happen without there being any specific reason. It's a subtle point I know, but it's an important point, so you really need to sort this one out. Letting p be arbitrary is not the same as picking in an arbitrary fashion a specific p. The point is that p is specific. Its choice may have been arbitrary, but once you've made it, it's specific. In contrast when you argue with an arbitrary p, you don't know anything about the p. You certainly wouldn't know that it was equal to 0.001 or whatever. You may need to think about that one a little bit longer, or talk it over with some of your colleagues. Now let's look at proof by induction. This is the special case where we're proving universal quantified statements where the quantifier ranges over the natural numbers. For example, suppose I want to prove that 1 plus 2 plus et cetera et cetera et cetera plus n equals a half n n plus 1. The sum of the first n natural numbers is a half times n times n plus 1. Well, if you're meeting this problem for the first time, a smart thing to do is to begin by checking the first few cases. First of all to see if it's true for the first few cases, and to see if there's a sense of what's going on. So if n equals 1, what do we get? Well then we've just got 1 here, and putting n equals 1 into the formula, we have half times 1, times 1 plus 1, which is a half times 1 times 2, which is 1, and indeed 1 equals 1. So it's true in the first case. In the second case, n equals 2, what do we have?  So if the formula is correct for n equals 2, we might want to try n equals 3. What do we get then? We get 1 plus 2 plus 3 equals a half, 3, 3 plus 1, which is a half, 3, 4, which is 6, which is correct. So the formula checks out for the first three cases, and we might want to do a couple more cases. But at least that gives us some sense of what's going on. By doing this we understand what the formula, we understand what the equation is saying. Now so far this isn't a proof. This is just checking the first three cases. In fact you've got to be very careful about jumping to conclusions based on the first three or four cases. So let me just stress that. This is not a proof. Okay, let me stress it again. Beware of jumping to conclusions. And to drive this point home, let me give you an example where if you jump to conclusions you'll come to the wrong conclusion. Consider the formula pn equals n squared plus n plus 41. If you start working out values for this formula, you find something rather interesting. You find that all values of pn for n equals 1, 2, 3, et cetera, are prime numbers. Well, not quite. That's true until you reach n equals 41. And when you get to 41, you find that p of 41 works out at 1681, which is 41 squared. So the first series of values for n equals 1, 2, 3, et cetera, all the way up to 41, which is well beyond the number of cases most people would try out by hand. You find you've got a prime number. But if that leads you to believe that this formula generates primes for every n, then you're going to be wrong. Because when you get to n equals 41 it's no longer prime. This example, by the way, is due to the famous Swiss mathematician Lennard Euler in 1772. And it's a cautionary tale telling us not to jump to conclusions based on numeric evidence. Nevertheless, it's always a good idea, it's often a good idea to begin looking at a problem by working out a few cases. Not only do you get an understanding of what the formula is about, but you can sometimes, when you work out a few cases, you can find a pattern. In this case, there actually isn't much of a pattern to find. You work out the values and you just get numbers, and it turns out that the first 40 of them are primes. But in this case, if you look at what's going on after, even if you did maybe a couple more, n equals 4, n equals 5, you'd begin to see a pattern of what's going on, how the two parts of the formula are combining what's happening to the half. The half is dividing into the second one here, the first one here, the second one there. And after you've done a few cases, you can often find a way of capitalising on the pattern that's there in order to produce the proof that I'll show in a minute. So induction proofs can often be derived by looking at the first few cases, seeing what the pattern is when you start plugging the numbers in, and then actually building a correct rigorous proof. Okay, so the next step now is to begin with this numerical evidence, and our understanding of how the formula works in order to come up with a rigorous proof of the fact that this formula holds for every n. The method of induction depends on a principle known as a principle of mathematical induction. Okay, and here's what it says. Suppose you want to prove a statement for all n, a of n. Establish the following two statements. One, a of one. That's known as the initial case, or the initial step. Two, prove the following statement. For all n, for all natural numbers n, if a of n is true, then a of n plus one is true. That's known as the induction step. Now intuitively, this gives the statement for all n, a of n as follows, by the initial step, step one, a of one. If we now apply the induction step in the special case where n equals one, we have a of one by the initial step, and that yields a of n plus one, which is a of two. So by two, or by step two, a of two, a of one yields a of two. So from a of one, we can conclude a of two. Okay, we begin by proving the initial step. So if we've proved a of one, then we know that one's true. We can now apply the induction step in the special case where n equals one, and having proved this, if we have a of one, we can conclude a of two. Then we can do the same thing again. Once we've got a of two, we can put the two in here and conclude a of three. So by a of two and the induction step, we can conclude a of three, et cetera, all the way through the natural numbers. So it's a little bit like taking a row of dominoes, and you knock the first one down, and providing the dominoes are close enough so that when one gets knocked down, the next one gets knocked down, then once you start to topple a row of dominoes, the first one not goes down, then the first one knocks down the second one, the second one knocks down the third one, the third one knocks down the fourth one, the fourth one knocks down the fifth one, and so on and so on and so on, all through the natural numbers. So you get a row of dominoes falling down. So this basically says knock the first domino down and put the dominoes close enough together so that when one falls, the next one falls. Okay, that intuitive explanation is fine as far as it goes, but that's certainly not a rigorous demonstration of this method. The fact that proving these two together does yield that universally quantified statement, that's actually quite a deep result of mathematics. And let me just stress that. You need an axiom or a principle to make this work called the principle of mathematical induction. The principle of mathematical induction is what tells you that one and two above, steps one and two above, yield for all n, a of n. Okay, now we have the method of induction laid out before us. I'll apply it in order to prove that identity that we looked at a moment ago about the sum of the first n natural numbers. So I'm going to prove a theorem now that for any natural number n, one plus two plus three plus yada, yada, yada, plus n is a half n, n plus one.  I'm going to use a method of mathematical induction. And since one of the purposes of a proof is to explain why something is true, it's usually good form to indicate to the reader the method you're going to use. It's orientates the reader to what's going to come next. And I'm using a standard method here, namely mathematical induction, so it's good form to indicate that that's the method I'm going to use. Well, I have to do two things. I have to show that this is true when n equals one, and then I have to show that if it's true at n, it follows at n plus one. So the first step is to say that for n equals one, the identity reduces to, well, n equals one on the left hand side, I've just called one, put n equals one on the right hand side, I've got a half times one times one plus one, which is a half times one times two. And indeed the left hand side does equal the right hand side. So that's true since both sides equal one. So we've proved the first step. Incidentally, you may have noticed that I referred to this not as an equation, but as an identity. And the reason is there's an equation is something that you solve to find the value of a variable, either x in the case of a real number equation or n in the case of a natural number equation. But this isn't an equation that you solve for n. This is an identity. It's something, it tells you that the two sides are always equal. And we use the word identity to refer to an expression like this that claims or that states that two things are equal for all, for all values of n. So these two sides are identically equal. So the correct terms are an identity for something like this, an equation for something that you solve. Having said that, like many mathematicians in practice, I'm sometimes not particular in the words I use. If you caught me talking to my colleagues, you might find me using the word equation where I mean identity. Possibly even using the word identity where I mean equation, all that one's less likely. But strictly speaking, an equation is something you solve and identity is something that states that two things are always equal. Okay, let's move ahead. We've proved that the result is true at n equals one. The next step is the induction step. So I'm going to assume the identity holds for n. Ie I'm going to assume one plus two plus n equals a half n, n plus one. And let me note now and I'll put this in brackets. I want to deduce one plus two plus n plus one equals a half n plus one, n plus one plus one. Okay, that's just a note for myself to indicate the target I'm aiming for. And the challenge now is to start with what I know and deduce where I want to get. Well, how can I get this from this? Well, one way would be to add n plus one to both sides of that identity, which means that I'd get the left hand side here and then hope that when I work out the right hand side, having added n plus one, I end up with this expression. Okay, so let's add n plus one to both sides of, let me call it star. So star is the identity I'm assuming. Let me add n plus one to both sides of that. That gives me one plus two plus plus n plus n plus one is a half n, n plus one plus n plus one. So I've now got the left hand side of what I want to prove. I need to show that the right hand side is the right hand side of the thing I want to prove. So I need to show that that is the same as that. Well, let's just see what happens. I can take the half out as a common factor. So I've got a half into n, n plus one plus two into n plus one. And that equals a half n squared plus n plus two n plus two, which is a half n squared plus three n plus two. And this factors. This is a half n plus one n plus two. But that's the same as that. I can write it explicitly if you like as a half n plus one n plus one plus one, which is the identity with n plus one in place of n. Hence, by the principle of mathematical induction, the identity holds, and we're done. We've proved the initial step, a simple matter of observation, and we've proved the induction step by a fairly simple algebraic argument. And that's it. That's mathematical induction in practice, where this screen came up about a quarter of an hour into the lecture. Did you spot anything wrong with it at the time? Can you see anything wrong with it now? Well, the problem's in here. This isn't the polynomial I meant to write down. What I meant to write down here was the polynomial p of n equals n squared minus n plus 41. I got the sign wrong. And for this, it is the case that for all values of the polynomial for n equals one, all the way up through n equals 40, it's prime. Okay, all the way up. And then p of 41. If you put that in, it's 41 squared minus 41 plus 41, which is 41 squared. Which is this number here? 1681. Let me call that p sub minus to indicate there's a minus sign here. Because the polynomial I wrote down, I'll call p plus of n, was this one, plus n, plus 41. That one is actually prime for n equals one through 39. And if I put 40 in there, let's put the minus in there to distinguish it. If I put 40 in there, I get what? I get 40. N squared plus n is n times n plus one. So it's 40 times 40 plus one plus 41. Which is 40 times 41 plus 41. So I've got 40 times 41. And then another 41. That means I've got 41 lots of 41, which again is 41 squared equals 1681. These are sort of the same polynomial when you look at it in terms of the behaviour here. If you just see what's going on. They were both actually due to, well actually, I'm not sure historically whether, or I wrote them both down, but clearly once this has been discovered, you're just manipulating them. And what I did when I was giving the lecture, this is spontaneous. By the way, almost all of these lectures are spontaneous. They're not meant to be polished lectures. I mean, I'm familiar with the material. So it sometimes looks as though I'm just sort of reading it from a book. But if I am reading it from a book, it's a book in my head. I'm having taught it for many years. Basically what I'm recording is spontaneous. And this just, I just pulled this off from my memory and I confused two things. I knew that it didn't really matter what the sign was, but it does make a difference as to where it stops being primed. If you pick the negative sign, it's primed all the way up to 40. If you pick the positive sign, it's primed all the way up to 39. So it was a technical error, but in principle it was correct. And it certainly, whichever one you pick, gives a wonderful example of the fact that just because you have a repeating pattern, it doesn't mean to say something's true for all n. And remember that I introduced this as an illustration of caution when I was talking about induction proofs. OK, well, what happened was the first time I gave this course, many students found the mistake and I thought it was good to leave it in the second time I gave the course so that students would have a further chance of finding the mistake themselves. It's always fun to find mistakes. This time I decided to leave it in, but put in a quiz at the end just to prompt anyone that hadn't noticed the mistake that there was actually a mistake. OK, so now you know what's going on here and you've seen me make a wonderful mistake in public, which is something that all good mathematicians should do. OK, well, that brings us to the end of 8.0, lecture 8.0. Let's move on to lecture 8.0 where the correct answers are this one, this one, and this one. If you check back at the description I gave of the method of induction, you shouldn't have any difficulty realizing why this is the correct answer, why this is the correct answer, and this is the correct answer. So if you got any of these wrong, you definitely need to go back and look at the lecture again and make sure you really understand induction. It's a very important technique in mathematics. Well, let me give you another example of an induction proof now, and this time I'll lay out the proof in a way that makes explicit the connection between the argument I give and the description of induction I gave a moment ago. And the example I want to give is the following theorem, well, calling it a theorem is actually a bit of a stretch, but here's what I'm going to show, that if x is a positive real number, then for any natural number n, 1 plus x to the n plus 1 is bigger than 1 plus n plus 1x. Okay, this result is not going to set the mathematical world on fire, but it is a good example to illustrate the way mathematical induction works, and in particular to connect the arguments that I'm going to use to the early description I gave for mathematical induction. So here's the proof. Well, I'm going to begin by stating the method I'm going to use to mathematical induction, since one of the purposes of proofs is to explain why something is true. It's always a good idea to begin by stating the method you use that orientates a reader to the argument that's about to come, and to connect it to the description I gave of induction before, I'm going to let n, let a of n be the statement 1 plus x to the n plus 1, bigger than 1 plus n plus 1x. So by induction, I'm going to prove for all n, a of n. Well, the first step is to prove a of 1, and a of 1 is the statement 1 plus x squared is bigger than 1 plus 2x.  Is this true? Well, the answer is yes. It's true by the binomial theorem, which tells us that 1 plus x squared is equal to 1 plus 2x plus x squared, which is bigger than 1 plus 2x, because x squared is strictly positive. Notice that x is positive, so in particular x is non-zero, hence x squared is strictly positive, hence we have a strictly positive term here, hence that expression is strictly bigger than 1 plus 2x. So a of 1 is true. The induction step involves proving for all n, a of n implies a of n plus 1. Or how do we typically prove a statement like this? We pick an arbitrary n and prove a of n implies a of n plus 1. And how do we prove an arbitrary n like this? We assume the antecedent and deduce the consequence. Well, a of n is the statement 1 plus x to the n plus 1 greater than 1 plus n plus 1x.  So the induction step boils down to assuming this and deducing that from it. So I'm going to focus on this now, and I'm going to begin by looking at the first expression, 1 plus x to the n plus 2. In order to use the induction hypothesis, I'm going to pull out one of these terms and write that as 1 plus x times 1 plus x to the n plus 1.  And that equals 1 plus n plus 1x plus x plus n plus 1x squared, which equals 1 plus I've got n plus 1x and another x. So altogether I've got n plus 2x plus n plus 1x squared. And this is positive.  And that part of it, the part here connected with this is this. In other words, this is proves a n plus 1. And the theorem follows by induction. Okay, I've laid this out in gory detail here, but my purpose was to connect the kind of argument that you give when you do an induction proof with the description of induction that I gave a moment ago in terms of predicates a n. Okay, so this is, so what I've been doing here is really emphasising how my earlier description of induction connects to an actual proof. If you take out all of the pedagogic stuff that I've put in here, you've really got a two or three line argument. I mean it really boils down to that step and then this step here. Those are the two key steps of the, of the induction proof. Okay, well there we are. Let me summarise how induction works. You want to prove that some statement a n is valid for all natural numbers n. You first prove a 1. That's usually a matter of simple observation. The next step is give an algebraic argument to establish the conditional a of n yields a of n plus 1. Usually you assume a of n and then you deduce a of n plus 1 from it. And typically you do that by looking at the form of a of n plus 1, manipulating it into such a form that you can apply a of n in order to carry out an argument. In other words, reduce a of n plus 1 to a form where you can use a of n. Conclusion, by the principle of mathematical induction, this proves for all n a of n. Occasionally you might have to work pretty hard to establish the first case. Generally this step is easy and this one is where you have to put in the effort. But neither of these two steps on their own constitutes an induction proof. It's the whole package that constitutes induction. My illustration of induction as, as knocking over a row of dominos, while it's intuitively helpful, obscures the fact that this principle of mathematical induction is actually a pretty deep principle of mathematics. The reason it's deep, by the way, is because this is talking about an infinite collection. It's talking about all of the natural numbers and there are infinitely many of them. And the moment you start talking about infinity in mathematics there are subtleties and complexities lurking on the wings. Incidentally, that's why we usually complete a proof by writing a sentence something like, by the principle of mathematical induction, the result follows. Because this is heavyweight. And it's usually a good practice and a shrewd move to mention a heavyweight if there's a heavyweight in the move. Okay, well that's induction. I'd better tell you about a fairly common variant of induction. We sometimes need to prove a statement in the form for all n greater than or equal to n zero a of n, where n zero is some fixed number, five or ten or 20 or a million or something. In this case, the first step is to verify a of n zero. A of one may not be true. In fact, it's usually the case that when we are trying to prove something of this form, the reason we have an a of n zero is to verify a of n zero is to verify a of n zero . The reason we have an n zero as the starting point is precisely because the result doesn't hold at the beginning. We have to go out somewhere through the natural numbers until the result starts to hold. General induction starts at one, this variant starts at some point beyond one. But other than that, the argument is essentially the same. In particular, the induction step is to prove for all n greater than or equal to n zero, a of n implies a of n plus one. In fact, the example of induction I want to give you next uses this variant of induction. And that example is part of a famous result of mathematics called the fundamental theorem of arithmetic. Before I do, let me give you a quiz. Is one a prime number? Okay, I know this isn't the focus of the course, but there's a lot of confusion about this. And if we don't clear it out of the way now, it's going to keep haunting us as we go through the material that's coming up. Now, you know, I could of course simply give you the answer. And in previous times when I've given this kind of course, both in a MOOC and elsewhere, I've given students the answer. But it's one of these things that people just don't sort of really pay attention to. And then it comes up again when there are homework exercises and discussions. So what I'm going to do is give you this as a quiz. So I want you to answer whether this is a prime number or not, whether one is a prime number or not. Okay? Well, the answer is one is not a prime number. And the reason is the definition. Here's the official definition of a prime number. It's a positive integer n greater than one whose only exact divisor is one and n. That's all there is to it. It's a definition. So from now on, please be very careful that you really know the definition of a prime number. One is not a prime number. Incidentally, whilst on the topic of getting definitions cleared out, let me make another remark. Zero is not a natural number. Again, this is by definition. Zero is an integer, but it's not a natural number. Historically, the natural numbers are the counting numbers and people historically started counting at one, two, three, et cetera. Zero was very much a Johnny Com lately. Okay? So these come around all the time. They cause confusion. It's some unnecessary confusion, so I thought I would get it out of the way now and I would draw your attention to this definition by putting it in as a quiz. Okay? Now let's go on to what I was planning to do. Here's the part of the fundamental theorem of arithmetic that I want to prove. And it's the following theorem. Every natural number greater than one is either prime or a product of primes. Now we have to use that variant of induction for this one because it's not true at n equals one. The theorem only holds for n equal to two or more. In fact, one is the only number for which it doesn't hold. So we're only just in the variant. We've just missed one point. But we have to start at n equals two. In other words, the first step of the induction is going to involve looking at n equals two, not n equals one. But with that one change, it's going to mean induction proof. So proof would be by induction. Well, the induction statement n is, well, you might think it's going to be n is either prime or a product of primes. Okay? Based on the examples we've seen so far, you might imagine that a of n, the induction statement, is that n is either prime or product of primes. Well, that turns out not to be the case. That just doesn't work. We have to pick something else. And this is what we pick. For all m, if two is less than or equal to m is less than or equal to n, then m is either a prime or a product of primes. So the induction statement a of n talks about all the numbers between two and n being prime or products of primes. So it's a sort of cumulative statement, if you like. As we go up through the natural numbers, we iterate on the cumulative fact of things being primes or product of primes. And the induction proof establishes that a n is true for all n bigger than one. So we have to start with the first step, namely n equals two. Here of two says what? Well, if n equals two, there only is one m between two and n. So the universal quantify here is essentially vacuous. I mean, it's just a special case. It's a generous case. There is just n equals two. So this statement when n equals two simply says two is either prime or product of primes. Which is true. Two is a prime. Now we're going to assume a of n and deduce a of n plus one. Well, a of n plus one is going to talk about all numbers m between two and n plus one. So let's look at one of those m's. Let m be a natural number, two less than or equal to m less than or equal to n plus one. Well, if m is less than or equal to n plus one, m is either less than or equal to n or m is equal to n plus one. If m is less than or equal to n, then by a of n, m is either a prime or a product of primes. The only other possibility is that m equals n plus one. Well, if n plus one is prime, then m is prime. So what happens if m equals n plus one and n plus one is not prime? Then a natural number is pq such that one less than pq less than n plus one and n plus one equals pq. If n plus one is not prime, then it can be obtained as a product of two smaller numbers. Not being prime means you can find two smaller numbers whose product equals the number. Two smaller numbers other than one that is. So this is just a definition of not being prime. Well, since two less than or equal to p and q less than or equal to n, by a n, p and q are either primes or products of primes. These two numbers p and q are less than n plus one, so they're less than or equal to n. That means these numbers are m's that fit into the induction hypothesis. They're less than or equal to n, so by a of n, each of these is either a prime or a product of primes. But n plus one is a product of them. So n plus one is a product of two numbers, each of which is either a prime or a product of primes. Hence n plus one is a product of primes. The theorem follows by induction. If you look back through this proof now, you'll see why we took our induction statement to be this somewhat more complicated looking statement.