d. It's just a case of looking what the contrapositive does. It flips the order of the things and puts negations in front of them. So actually writing them down was not what the challenge was. The point of this exercise was to give you an example to sort of help cement the fact that the contrapositive is actually logically equivalent. Because is this one true? Yes. Congruent rectangles have the same area. If rectangles don't have the same area, they're not congruent. Those are both true. If a triangle is right angles, so we've got Pythagoras theorem. If a triangle is added. Each one of these is clear that one is equivalent to the other. If this thing happened to be true, then that thing would happen to be true. If that thing was true, then that would be true. So I think these four examples will illustrate the fact that contrapositives are logically equivalent to the original statement. Okay, I said I was just going to do six, ten and twelve, but as I was working through this one, I thought it would be a good idea to look at question 14, which is very similar. So let me do question 14 as well. Okay, and number 14 is about converses. Where again, as with a contrapositive, you flip the order round, but in this case you don't inject any negation signs. It's simply the implication in the opposite direction. Okay? Which means actually these four are going to be very straightforward because we're just doing the order. So this one would be if two triangles have the same area, then they're congruent. Now already we've shown by an example now that the converse is not necessarily logically equivalent to the original statement. Because the original statement is true, but the converse is false. Now that's not always the case. Let's look at this one. The converse of this one is the following. If in a triangle with sides A, B and C, with C the largest, it's the case that A squared plus B squared equals C squared, then the triangle is right-angled. Now this is true. It's Pythagoras' theorem. And the converse of Pythagoras' theorem is true. So these are both true. But what's going on is that we've actually started out with something that's not just an implication. When it actually is an equivalence, then when you've got an equivalence, then you take the converse. You've just got another part of it. Okay, the statements and the converse are both the two halves of an equivalent. So you can get the same true values, but only when there's an equivalence already there. In the case of this one, the converse would be if n is prime, then 2 to the n minus 1 is prime. And the converse of this one is if the dollar falls, the yarn arise. And in this case, there's no reason to assume that one necessarily follows from the other, unless in some way the other two conferences are linked. Okay, well, I hope you managed to get the four converses written down correctly. But as I indicated a moment ago, that wasn't really the point of this. The point was to sort of give us examples of the fact that converses don't necessarily yield equivalent statements. When you take a converse, you don't get something that's equivalent. Whereas with the contrapositive that we looked at in the previous example, in example 12, when you take the contrapositive, you do get something that's equivalent. Okay, okay. Well, that should, I think, take care of assignment number four. Okay, let's see what we've got with the problem set two. By the way, this part of the course, we've been looking at taking expressions in everyday language or problems that might arise from the real world in a certain sense. And try to make them precise. And that of course means that for people whose language, whose native language is not English, this is even more complicated because we have to deal with the complexities of the English language and try to eliminate the ambiguity from that and make things precise. When it comes to these issues about necessary and sufficency, I actually don't think it makes a lot of difference if you're a native speaker in English. This is tricky when you first meet it. And it's easy to make a slip. So this is one of those occasions where I don't think there's an advantage to being a native English speaker. We native English speakers find this difficult too. Okay, in the case of necessity, a condition is necessary if it follows from this. So what we're asking for is, is it the case that if six divides n, then the condition x holds. That's what we're asking. Does the condition x follow from n being divisible by six? Well, let's see. Is it the case, for example, that if six divides n, does it follow that three divides n? Well, the answer is yes. If six divides it, then three divides it. Okay? So that one's necessary. We'll hold this one. Well, notice that n equals six itself satisfies this condition. Okay, if n equals six, then six divides n. But it's six divisible by nine. In the answer now. Again, n equals six satisfies the condition of being divisible by six. But does it then follow that n's divisible by 12? In other words, it's six divisible by 12. No, it's not. What about n equals 24? Well, again, n equals six gives us an example of a number that's divisible by six. But that number's not necessarily 24. Right? Because it's six. So it's not that one. Okay. N squared divisible by six. N squared divisible by three. Well, let's just see. Six divides n certainly implies three divides n. If six divides it, then three divides it. And if three divides n, then three divides n squared. So that one's okay. Again, if six divides n, then, of course, two certainly divides n because six does. And if six divides n, then three divides n. So two divides n and three divides n. In other words, n is even and divisible by three. So it's that one. So we've got parts a, e and f. And this is the condition. This is the way it caches out in terms of implication. And in the case of the counter examples that we use to prove some of these false, the simplest counter example was n equals six itself. Okay? Well, that takes care of number one. Let's move on to number two. Well, in the case of sufficency, we have to look to see if the condition implies that n is divisible by six. Okay? Sufficency means implies n is divisible by six. So for each of these statements, we have to ask ourselves does it imply that n is divisible by six? Well, if n is divisible by three, in order to, if we, if we think the answer is it's not sufficient, then we have to find an example, we have to find a counter example of a number that's divisible by three that's not divisible by six. Well, why don't we check n equals three? Three is divisible by three, but three is not divisible by six. So that's a counter example. So that one's not sufficient for being divisible by six. That doesn't imply x is divisible by six. Because in particular, three is divisible by three, but not divisible by six. What about part b? Let's take n equals nine. That's a counter example. n is divisible by nine, but n is not, but, but, but if we take n equals nine, then the n is divisible by nine, but nine is not divisible by six. So that's a counter example. n is divisible by 12. Is it the case that if 12 divides into n, does it follow that six divides into n? The answer is yes. So that one's okay. What about n equals 24? Is it the case that if n equals 24, does it follow that six divides in? In other words, does six divide 24? Again, the answer is yes. So that one's true. n squared is divisible by three. Does it automatically follow that n is divisible by six? Well, why don't we take the same counter example we did in part a? Let's take n equals three, then certainly three divides n squared. Okay. But does six divide n? Does six divide three? The answer is no. Six does not divide n. So three divides n squared. Six does not divide n. So it can't be that one. Finally, n is even divisible by three. I could write that as saying n is even is to say that two divides n and it's divisible by three. So I can just rewrite this statement to say that two divides n and three divides n, but if two divides n and three divides n, then it's the case that six divides n. Okay? So that one's true. And when we come to question three in a minute, it's really going to be a matter of combining questions one and two. So we've now got all the information we need to answer the next one. Well, question three asks us for necessary and sufficient. So let's just see what we did in question one without the necessity. In in question two without the sufficiency. Let's remind ourselves what we had. Let me see now, we got necessity that was true in A, wasn't it? It was true in E, it was true in F. Remember correctly? Yeah. Okay? Actually, I'm not remembering. I'm working these out as I go through because I don't have the one in front of me anymore. Sufficiency, let's see, that was C, it was D, and it was F. Okay? By the way, if I'm making this look fluent, it's because I've been doing this for many years. Although you can still catch me out with a well, with a puzzling, with a question that's described in a puzzling way, even the experts can be caught out with this kind of thing. Okay? So we just have to look for the ones which have an X in both rows, in both columns, and the only one that does is this one. In all of the other ones, you've either got necessity or sufficiency or neither in the case of Part B. Okay?  The only one that's both is Part F. And that takes care of number three. Well, we're moving along rapidly now. Let's go ahead. Question four starts out simply enough because it's a very straightforward if-then statement. And when you've got an if-then statement, identifying the antecedent is pretty straightforward because it's the part that goes with the if. Okay? So it's this one. If the apples are red, then they're ready to eat. Okay? So this was an easy start, but these things are going to get a little bit more tricky as we move forward. Let's have a look at the Part B. Okay? Well, we're talking about sufficiency and sufficiency is the thing that does the implying. Okay? So what does the implying here? Well, F been differentiable. That's the one that does the implying because the differential property of a function implies that it's continuous. Okay? Sufficiency does the implying. So sufficiency is the thing we're looking for. So the antecedent is a sufficiency, which is differentiability. Well, I said these become a little bit tricky as soon as you get into them. Even though in one sense this is straightforward, my experience is that many students, including myself, when I was a student and the kids today, if I don't really put my mind to it, I have to think a little bit to just flesh these out. Alrighty? Let's move on to Part B. Okay? Remember, we're still looking for the antecedent, the thing that does the implying. This case, again, this actually is fairly straightforward because it doesn't matter whether you put the if clause first or second. It's the thing that goes with the if, so long as it's an if and not an only if. The thing that just goes with a naked if is the thing that's the antecedent. So in this case, it's this guy. It's F is integral. That's the thing that does the implying. And whenever actually, it's sort of the same as if. It's another way of using, a way of saying if. This tells us the condition under which something happens. This is bounded under the conditions that F is convergent, whenever F is convergent or if F is convergent. So it's that guy. Okay? So this is the antecedent. This is the antecedent. Let's move on to the party. When the case of necessity. Necessity is the thing that follows. So our necessary condition is the thing that follows. Okay? So we have to ourselves ask ourselves, what is it that's following in this case? Okay. Any answer is? This thing. Okay. So this is the antecedent because n being prime is necessary. So n being prime is the thing that's the consequence of the antecedent. So it's this that implies that. So this is the antecedent. All ready? Let's move on to part F. How did you do with that one? Well, this is where we start combining words like if and when with an only. And because it says only when Carl is playing, this guy is the consequence. The team wins only when Carl is playing. So if you know that the team wins, you can conclude that Carl is playing. Because the only win when Carl is playing. So that's just another way of saying that Carl is playing is a consequence of the team winning. Okay? So this is the antecedent. And as I mentioned at the beginning of this discussion, even if you're a native English speaker, these typically cause people a lot of trouble. Just the way the human mind works. It's not to do with the native languages to do with the way the mind works. Well, these two are a little bit more straightforward than the last one or two because the when is really almost the same as if. That just tells you the condition on which something is. So the thing that just goes with a when without an only combined with it is the antecedent. Okay? So the antecedent in this case is that Carl is playing because it's when he's playing that the team wins. If you know that Carl is playing, then you can conclude that the team is going to win on the basis of this statement. So that's the antecedent there. And it doesn't matter whether the when clause comes first or second, as was the case with an if clause, it can come first or it can come second. That's still the antecedent. Okay? Being the antecedent is not directly related to whether you're the first clause or the second clause in a sentence. It gets to go with which word you're combined with. If it's an if or if it's a when, then that combines with the antecedent. If it's an only if or an only when, then that flips it round. And then you're dealing with the consequence. Okay? Well that's takes care of those kind of examples. And the last two parts, or the last three parts of this question of this problem were a little bit different. Okay? Well in this case, it's certainly true that if m and n are even, then mn is even. We know that. So the question is, is it the case that if m, n is even, then m and n are even? So that's what this boils down to. This, this implication. Okay? We know what, there's two implications here. It's an if and only if. So that means the equivalence. It means the implication holds in both directions. And one equivalent, and one implication is certainly true. If m and n are even, then mn is even. And so it boils down to the question, if the product is even, then are the two numbers necessarily even? And once you get it down to that stage, all you need to do is just observe. There are many counter examples. We could take m equals two, n equals three, then mn equals six. So here we've got a product that's even, but it's not the case that both numbers are even. So this is a counter example. So the answer to the question is no. This is a statement about any pairs of integers. And if we found one pair of integers that, that makes it fail, then the whole statement fails. So it's a counter example that we need to find. And we found one, m equals two, n equals three. The product is even, but it's not the case that both numbers are even. Okay? Now let's move on to number six. So number six asks us, is it the case that mn is odd, if and only if m and n are odd? Well, I'm sure you all realise that the answer is yes. And you won't necessarily realise the reason, you know the reason why, because there were two facts. We know that odd times odd, I better say is not equals, is odd. And we know this even times anything, any number odd or even is even. So if you take two odd numbers and multiply them together, you get an odd number. If you take a number, a pair of numbers, any one of which is even, and multiply them together, you get even. And when you combine those two, this falls out of it. And if you don't see that, I mean, I'll leave it to you actually. If you want to sort of give a little bit more detail and express it as an implication in both directions, that's fine. You could discuss this, and I'm sure you could discuss this endlessly on the forums and that would be a good idea if you want to. But I'm just going to leave it with the observation that it's really just these two facts that give you this result. Okay? This tells you how the parity even and odd works. And once you know that, you know that. But have fun with this one and discuss it amongst yourselves and settle to your own satisfaction what constitutes a rigorous proof of this thing. Remember, there's actually no sort of gold standard of what is or is not a rigorous proof. It depends on the experience of the audience. A proof in many ways involves audience design. You've got to cast that proof at the level of detail and precision that matches the audience. You know, typically a mathematician, a professional mathematician would simply say, and you see this actually in books and in papers, a mathematician might very well say, this is trivial. Okay? And that would be the proof. In advanced works on mathematics, you often see remarks like the proof is trivial. It has to be said that a beginner might take several days to see why something's trivial. When mathematicians use that kind of expression, they're doing it with a particular audience in mind, namely other professional mathematicians. So, you know, if you read that and it doesn't seem trivial to you, it doesn't mean you're stupid, it just means you haven't spent many years working as a professional mathematician. It's just a way we classify things. And proofs involve a lot of audience design when you write and formulate proofs. Okay? Well, one way to do all of these is by truth tables. And if you work out the truth tables, you find that A is true, that B is true, C is not true, D is true, D is true, and F is true. So simply by using truth tables, you could answer this. This one we've already seen in the lectures and discussions. We've sort of looked at these, this equivalence. This one, and where is it? That one. Those are examples of what's known as De Morgan's Laws after a mathematician Augustus De Morgan. That if you take a negation with a disjunction, you end up with a conjunction of the two negations. And if you take a negation of a conjunction, you end up with a disjunction of the two negations. Okay? So that was a basic fact about implication that a conditional is true if either the antecedent is false or the consequence is true. So that was the truth table that we worked out for the conditional. Those are De Morgan's Laws. That one's not the case anyway. This one, you could probably reason this one out in terms of implication. Just think in terms of when implication. Under which circumstances can you start with an assumption P and deduce two conclusions? And then see when that doesn't happen. Okay? And you should end up with this. So it's possible to reason this one out. Just in terms of implication. And the same is true for this one. You could reason it out. This one I think is easier to reason out than that one because of fewer symbols to deal with. This says that if you have an assumption and then you have another assumption, you can make a conclusion from it. Well, do you do it in two steps? Do you assume P? And then on the basis of that show that if Q is true, then R is true? Or do you simply assume that both P and Q is true and deduce R? Those two things would be equivalents. This is sort of doing it in two steps, and this is combining the two assumptions. They both really tell us that there are two assumptions. There's one assumption, then there's another assumption. And in this case, we've explicitly said there are two assumptions. And in both cases, it's the R that's following from them. Okay, so the question is how and when do you get from P and Q to a conclusion R? So this is, you could reason it out. And if you feel uneasy about that, you could just work out the truth table. Okay, but since we've spent a lot of time on truth tables and the assignments, my recommendation would be that you would go through these and actually try to reason them out in terms of what they mean.  But people are not computers. They're much more interesting creatures than that. And I think we have the power of reasoning. And so I would suggest you go through these and try to reason them out in terms of what these things mean. Because that, after all, is really what this entire course is about. We're in question eight. We make use of the course evaluation rubric. This is the first of many questions that you'll be asked to do, making use of this rubric in order to evaluate purported mathematical proofs. Well, here's the first one. The claim is that for any two propositions P and Q, not P, conjoined with not Q, is equivalent to not P and Q. The argument is fairly short. In fact, all of the ones I'm going to be using as examples are short. That's why they're good as examples. In particular, I want to be able to give the solutions on a single slide, as I'm going to do here. So in a way, these are not typical. In fact, if you do test flight at the end of the course, you will almost certainly see proofs presented by other students, which are much more complicated and much longer and perhaps have all sorts of mistakes in them. The arguments I'm giving you, they are, they all began as arguments that were produced by students over the years when I've taught this material. But what I've done is I've picked particular aspects of proofs where students typically go wrong. And so the examples will have one or two common mistakes embedded in them, just so you get used to looking at proofs from the different perspectives, as captured by the rubric, and seeing how they work and don't work. As I mentioned in the, in the description of the use of the rubric on the course website, the way it will work is that because I'm using short examples, in each particular example, some of these, these, these, these features won't really apply. In which case you have to sort of default and give four, or zero, depending on how the student handles it. Typically you would end up giving full marks because it just doesn't really apply. Okay. Well, let's, let's take a look at how the, how this one was done. And so we'll, we'll, I'll, I'll pretend that it was done by a single student, even though this is a composite of the kind of things that students have done over the years. Okay. Well, it's an equivalence. So we have to prove it in two directions. We have to prove that this implies that and that implies that. So there are two equivalences to prove here. So let's just check the left-right implication. So suppose that not p and not q is true, then a conjunction is true if and only if the two conjuncts are true. So if the conjunction is true, then both not p and not q are true. Okay. That's correct. That's what conjunction means. If not p is true, that means p is false. That's what negation means. If not q is true, that means q is false. So the truth of these two negations means the falsity of p and q. But if p and q are both false, then again because of the way a conjunction works, p and q is false. Hence not p and q is true again because of the way negation works. So that's absolutely okay. Okay. The left-to-right was proved great. What about right-to-left? Well in this case the student makes an attempt to be fairly sophisticated by saying the other argument, the argument in the other direction works the other way. If it does work the other way, it's absolutely okay to simply say that. There's no requirement that you would have to repeat something that's, that's obviously the case. But we'd better check that it is obviously the case because we're actually evaluating whether this is the case. Okay. So let's, let's spell out what this person didn't do. In other words, we'll try to do the same as here going to the direction. So we're going to assume it's not the case that p and q. Okay. Let me just say we'll assume that's true. And that's sort of redundant but I want to talk about truth and falsity. So we'll assume that not p and q is true. That means that p and q is false because of the negation. If the negation is true, it means that p and q is false. Well what does that mean? That means that at least one of p and q is false. Okay. Because you only need one of them false to make the conjunction false. Ah, but the other one, whichever it is, could be true. It doesn't have to be. But there's nothing to rule out the fact that the other one's true. So one of p and q is true. That means one of not p and not q could be false. At least one of them is false. So the other one could be true. That means one of those could actually be false. One of these guys, not p and q could be false. That means if one of them could be false, it means not p and not q could be false. That's not ruled out. In other words, that implication does not work. Just because not p and q is true, it does not necessarily follow that not p and not q is true. It could be false. We're not saying it is, we're saying it could be. So there isn't an implication. There is no implication from right to left because you could have that without having that. That thing could in fact be false. In other words, the original claim is a false claim. It's simply not true. So this statement, though it was a nice attempt to be somewhat sophisticated, it didn't work because in fact the argument does not work the other way. I mean it is essentially the same kind of argument and if it had been correct, that would have been fine. You wouldn't need to give this. But it's not correct. So now we're going to have to sort of put some numbers in here that capture what we've just said. OK? Well what am I going to say? There are four marks available for logical correctness. The left to right part was absolutely correct. This is logically correct. So I'm just going to give half marks for that. I'm going to say two captures the fact that left to right was correct. But remember logical correctness is just one aspect of proof. There are other factors too. And that's what the rubric items are doing. So let's look at what we've got. Clarity. This is absolutely clear. Even here it was clear. It was wrong, but it was clear. So in terms of clarity this is very clear. So I'm going to give full marks for clarity. Is there an opening? Insofar as there's any reason to give an opening here, yes it begins by stating that we're going to go from left to right. And so I'm going to give four for that. Now you could say maybe the person should have begun by saying to prove an equivalence you have to prove implications from left to right and right to left. Well you know it's a judgement call. I would say that for someone at this stage where they're producing arguments like this, and this is a nice argument. This is perfectly correct. For someone that's producing this, I think it's okay to say, yeah it's obvious by the way they're doing it that they're doing that. But remember even though the rubric does break a difficult task into smaller pieces, they're still not easy. So these are going to be judgement calls. I would say that there's enough demonstration of knowing the person knowing what he or she is doing to just say I'm not going to insist that they say proving an equivalence is enough to prove left to right and right to left. I think it's clear from the way they're doing it. But they do start out by saying assume one and prove the other one. Okay? What about stating a conclusion? Absolutely, it was stated we have implication in both directions. This just justifies what I've just said. So the person has now said we have implication in both directions. So just emphasising the fact that he or she knew exactly what they were doing. Remember also that we're really trying to do formative assessment rather than summative. The process is one of seeing what the person has done well and rewarding what they did well. It's not about trying to take marks off. When we do this kind of thing we should always be looking for reasons to give marks, to acknowledge what's been done correct and then to point out things to improve. So we begin by adopting a positive giving marks attitude. That's the best way to do this kind of thing. So I'm always going to be looking for reasons to give marks. On the other hand, if there's any, you can't give marks if they're not justified. Okay. What about reasons? I mean reasons were given but it was really the same as in the first case. The reasons for the other part that should have been given weren't because the person thought it was the same and it wasn't. So some of the reasons are here. They were given as a person was going along. So I'm going to have to give two for that one because it was only half a proof. I mean the proof was listed. The result's false. So this is absolutely false. So the most I could give here is two because even though reasons were given, that's not a reason. That would have actually been a reason if it was correct. If this kind of argument was correct that would have been okay but it's not. And then overall, again I'm just going to have to give two because it's basically just half a result. Okay. That's really what it's coming down to. The person has laid it out well so he or she is going to get a lot of marks for laying it out correctly. But they're going to be losing some marks because they were only half of the thing. I'm just saying there's only half available and so I'm giving half the marks. So the total is going to be 18. It's maybe a little bit generous actually. After all, this thing is false. In fact, if this was a mathematics course and I was sort of grading people for doing mathematics work, I think I'd have been much more harsh. I'd have probably come down at 10, 12, maybe even less. But this is about much more than mathematics. It's about mathematical thinking. It's about communication. It's about understanding proofs. In reality, the mark I've given the person is two. I've given them two out of the four. So essentially, I've said this is worth half marks in terms of the overall evaluation because half the proof is okay. But because we are also rewarding or looking to reward proof structure, communication, all of those other aspects of proofs, which are important, I'm going to give credit for the fact that the person has got the general idea. So I've got 18. As I say, maybe we can add it as a little bit generous. I'm inclined to think it's a little bit generous myself. On the hand, this is a 75%. Okay. Which means 25% has been docked, if you like, or not given. And let's look at what happened. This was essentially just one mistake. The person looked at it and didn't look close enough, but it comes down to just one error. It's one error in logic. The person who could produce that argument almost certainly could produce the correct argument in either direction to show that it was false. So it really comes down to one slip. And frankly, it seems to me that if you docked more than 25% or maybe 30% for just one error, then that's kind of harsh. We are after all trying to turn people into better mathematicians to make them better mathematical thinkers. So let's look at what they do right, and then give credit for that. And this person has done a lot of things right. There was just one mistake. And it was a mistake that almost certainly this person shouldn't have made. They had the ability not to make the mistake. But people do make mistakes. So we're not going to give Markzware for free. But having hesitated a little bit on the 18, I've actually now talked myself back into saying 18 is actually a pretty good grade. Now everybody, well, that's the end of that problem set. How did you get on with that massive assignment four? To give you a chance to complete it, this lecture is also fairly short. And this time, the assignment is down to a single page. So keep working on that last assignment. It really is crucial to master those ideas and that terminology. Knowing when and why one statement implies another and being able to distinguish between necessity and sufficiency are crucial abilities in today's world. There are two more language constructions that are fundamental to expressing and proving mathematical facts and which mathematicians therefore have to be precise about. The two quantifiers, there exists and for all. When we've made these terms precise and are sure we know how to use them properly, our analysis of language will be over. The word quantifier is used in a very idiosyncratic fashion here. In normal use, it means specifying the number or amount of something. In mathematics, it's used to refer to the two extremes. There is at least one and for all. These are all we need to look at because of the special nature of mathematical truths. When mathematics is viewed as a subject in its own right, as opposed to being a set of tools used in other disciplines and walks of life, the core of the subject is the theorem. And the majority of mathematical theorems have one of two forms. There is an object X having property P. For all objects X property P holds. I'll take these one at a time. We're looking at statements of the form, there's an object X having property P. For example, the equation X squared plus two X plus one equals zero has a real root. We can emphasise that this is an existence statement by writing it in the following form. There is a real number X such that X squared plus two X plus one equals zero. Or we could write it this way. There exists a real number X such that X squared plus two X plus one equals zero. Doesn't matter whether we write it with an is or an exists. It's an existence statement. The symbolic abbreviation that mathematicians use for exists is a back to front E. E for exists of course. So a mathematician would write this as follows. There exists an X such that X squared plus two X plus one equals zero. This symbol is called the existential quantifier. The simplest way to prove an existential statement of this form is to find an actual X that satisfies the property. And with this example it's easy. Take X equals negative one and X squared plus two X plus one equals negative one squared which is one plus two times negative one which is negative two. Then we've got the plus one. One minus two plus one equals zero which solves it. Well that was a simple example. Sometimes we can prove an existential statement without finding an actual object that satisfies the property. Let me give you an example of that. I'm going to prove this statement. There exists an X such that X cubed plus three X plus one equals zero. I'm not going to find an actual X that solves this cubic equation but I am going to show that there is a solution. I'm going to start by looking at the function Y equals X cubed plus three X plus one. This is a continuous function. Continuity of functions is actually a fairly deep topic. I will touch on it briefly at the end of the course but from our present purpose all I need to know is that a continuous function is one whose graph is a smooth curve with no breaks and jumps. And you should be sufficiently familiar with cubic equations by now to know that the cubic equation has a nice smooth curve that looks something like that in many cases. Up and down two curves. The point is it doesn't have any jumps. If X equals negative one this curve has value or this function has value. Negative one cube which is negative one plus three times negative one which is negative three plus one which is negative three. If X equals plus one the curve or the function has value Y equals one plus three plus one which equals five. So the curve lies below the X axis for X equals negative one and above the X axis for X equals plus one. So it looks something like this. Put the origin here with a look at negative one. We're going to look at plus one. It's going to lie somewhere down here at negative one. It's going to lie somewhere up here at plus one. And somewhere it's going to cross the axis. It looks like that, that, who knows. The point is it's going to have to cross the axis somewhere or other rather to the left of the origin or to the right of the origin. It doesn't matter where. The important point is somewhere between negative one and plus one. This curve crosses the axis and when it crosses the axis the Y value is zero. So we haven't said which X solves the equation. We haven't even said whether the X is negative or positive. But we do know there is such an X. We've shown that the X exists that satisfies the equation without finding such an X. This is an example of an indirect proof. We haven't proved it directly by finding an X that solves the equation. We've simply shown that there is an X that solves the equation. A lot of mathematical proofs are of this nature. We show that there is a solution to some equation or that there is an object that satisfies some property or other without finding such an object. Pretty cool, huh? Time for a quiz. A simple modification of that last argument use a more specific result. Which of the following is it? Is it one? There is an X less than zero, such that X cubed plus three X plus one equals zero. Or is it two? There's an X greater than zero, such that X cubed plus three X plus one equals zero. Okay, which one do you think it is? Well, the answer is one. And here's how we can get that. In the previous argument, I looked at the curve at X equals negative one and X equals plus one. And I showed it looked something like this. At negative one, the curve was below the X axis. At plus one, the curve was above the X axis. And so it has to cross the X axis somewhere between negative one and plus one. But instead of going between negative one and plus one, I could go between negative one and the origin itself. Well, note that if X equals zero, then Y equals X cubed plus three X plus one is one. So at zero, it's somewhere up here. Which means it's negative at negative one. It's positive at zero. So it's somewhere between negative one and zero that it crosses the axis. Since the curve lies below the X axis at X equals negative one, and above the X axis at X equals zero, it must cross the X axis between negative one and zero. Or I could prove it a different way. I could simply observe that if X is greater than or equal to zero, then X cubed plus three X plus one is greater than zero. And in particular it is not equal to zero. So two is false. And that just leaves one. We know that one of these two has to be true as a result of the previous argument. And so if we can eliminate two, as I've just done here, then I can conclude one. So either way, either by refining the previous arguments or by deducing it from the previous result by this observation, I end up showing that the equation has a root somewhere between negative one and zero. I still haven't found that root, but I have sure that there is a root. It's an indirect proof. Incidentally, in giving that last proof, I was careful to distinguish between the terms negative one and minus one. Chances are your middle or high school teacher made a big deal of that. Like many professional mathematicians, maybe even most of us, I'm generally far less careful. I tend to use negative and minus interchangeably. It's not that we don't know the distinction. It's just that at that university level, we focus on other issues. And since this is a university course, I'll assume you can use your knowledge of arithmetic to determine the intended meaning, just as we do with everyday language. In this course, a similar issue arises with implication and the conditional. And since that distinction is likely new to you, I'm going to try to always use the correct term. But when I'm talking with my professional colleagues, we just talk about implication to cover both cases and rely on our shared knowledge of the concepts to disambiguate. In both cases, the distinctions are important, which is why we emphasise them in our teaching. But once we're sure everyone has fully grasped the issues, we adopt a more relaxed attitude, confident that our understanding will keep us out of trouble. The same kind of argument I just used to show that a certain cubic equation has a real root can be used to prove the wobbly table theorem. Suppose you're sitting in a restaurant at a perfectly square table with four identical legs one at each corner. Because the floor is uneven, the table wobbles. One solution is to fold a small piece of paper and insert it under one leg until the table is stable. But there's another solution. Simply by rotating the table, you'll be able to position it so that it doesn't wobble. You might enjoy trying to prove this. The solution is simple, but it can take a lot of effort before you find it. It's very much a thinking outside the box question. It would be an unfair question on a timed exam. And I'm not giving it as a course assignment. But it's a great puzzle to keep thinking about until you hit upon the right idea. I'll leave you with it. Even if you can't think of a mathematical solution, you could go off in search of a square wobbly table and confirm the theorem experimentally. Meanwhile, let's get back to our main theme. Sometimes it's not immediately obvious that a statement is an existence assertion. In fact, many mathematical statements that do not look like an existence statement on the surface turn out to be precisely that when you work out what they mean. For example, a statement that's a number x is rational is an existence statement. And here's why. Let's take the specific statement square root of 2 is rational. As it happens, this is a false statement. But we're just using it as an example of a statement. So on the face of it, this doesn't look like an existence statement. But it actually is because we can write it as there exists natural numbers p and q such that square root of 2 equals p divided by q. Or using our symbolic abbreviation, exist p, exist q such that square root of 2 is p over q. Incidentally, when we do come to prove that the square root of 2 is not rational, we'll do it by assuring that there are no values of p and q that satisfy this equation. So we'll prove a non-existence statement. Well, this expression is fine. So long as we know in advance that p and q denote natural numbers, I mean here I said it explicitly. Here I didn't. So how do you know that p and q denote natural numbers? I mean maybe they should denote real numbers or complex numbers. The answer is you make it more specific. And you do that by writing it in the following way. There exists a p in n and there exists a q in n such that root 2 equals p over q, where n denotes a set of natural numbers. Incidentally, another font that's often used to denote the set of natural numbers is something like this. An n with a double line for the diagonal. In this course, I'm assuming that you're familiar with basic set theory and you know what the membership symbol means. If you're not, then there is a course supplement and I'm just going to leave it to you to read that supplement. And of course there's a course textbook if you acquire the textbook. That's my own book, Introduction to Mathematical Thinking. In any case, I'm going to assume that you are familiar with set theory and I'm not going to talk about it in the course itself. You sometimes see mathematicians write it in an even more abbreviated fashion. There exists a pq in n such that square root of 2 is p over q. That's fine if you're confident about the material and you're familiar with the notations. But we're going to be looking at examples where there are many different types of quantifiers coming in together and then if you start putting them together in this fashion, there's a possibility of getting confused and going off course. So I would say at the early stages, keep things distinct as they are here and try to avoid that for now. As I say, professional mathematicians write this kind of thing all the time. But just as when we're beginning to learn mathematics, it's important that we distinguish things like negative and minus and then when we master them, we tend to forget the distinctions or we don't forget them but we don't make them explicit. So here when we're beginning to look at quantifiers, I think it's important to be very explicit and then once you really understand it, then you can do what we do in the business. We just write things in the simplest fashion confident that we know what's going on and that the way we write it won't mislead us. Incidentally, see if you can prove that the square root of 2 is not rational. We'll do that in class later but see if you can do it now. What that amounts to is proving that there do not exist p and q in the natural numbers such that the square root of 2 equals p over q or that 2 equals p squared over q squared. This is the statement you actually prove in order to show that the square root of 2 is irrational. It's not a difficult argument but it's rather clever and ingenious. It's fairly short and the chances are that you're not going to come up with it but it's worth giving it a shot. You know, spend a half an hour or so thinking about it to see if you can prove that statement. Good luck on that one but we will come back to that in class. How are you doing? Do try to show that the square root of 2 is irrational. Not so much to find the proof but to get used to what it's like to do university level mathematics. One feature you need to get used to in mastering college mathematics or more generally what I'm calling mathematical thinking is the length of time you may need to spend puzzling about a problem or even one particular detail. For the most part without seeming to be making progress. High school mathematics courses particularly in the US are generally put together so that most problems can be done in a few minutes with the goal of covering an extensive curriculum. At college there's far less material to cover but the aim is to cover it in more depth. That means you have to adjust to the slow pace with a lot more thinking and less doing. At first this comes hard since thinking without seeming to be making progress is initially frustrating but it's much like learning to ride a bike. For a long time you keep falling or relying on training wheels and it seems you'll never get it. Then suddenly one day you find you can do it and you can't understand why it took so long to get there but that long period of repeated falling was essential to your body learning how to do it. Training your mind to think mathematically about various kinds of problems is very much like that. OK, semen over. The one remaining piece of language we need to examine and make sure we fully comprehend is the universal quantifier which asserts that something holds for all x. This notation means for all x it's the case that something other. The symbol here is an upside down letter A which means for all. For example if I wanted to say the square of any real number is greater than or equal to zero I could write it like this. For all x, x squared greater than or equal to zero. So the short way of actually saying that is for all x, x squared greater than or equal to zero. Just as we would write things like there exists an x such that x squared equals zero. Notice that I didn't use the word all in this sentence. I use the word any. The same thing happened with exist. There are different words we can use to express an existence assertion and there are different words we can use to express a for all assertion. This is the universal quantifier. How do I know what the x means? Well I have to specify what it means. If I want to be explicit I would have to write something like for all x in the set of real numbers x squared greater than or equal to zero. Okay let's take a look at combinations of quantifiers. Most statements in mathematics involve two or more quantifiers combined. For example if I want to say there's no largest natural number. What I would write is this. For all m in the set of natural numbers there is an n in the set of natural numbers such that n is bigger than m. For all natural numbers m there is a natural number n such that n is bigger than m. That clearly says there's no largest natural number. Note that the order of the quantifiers is important. If I swap those quantifiers round and write exists an n in n such that for all m in n n is bigger than m. The result says there is a natural number n which has the property that for all natural numbers m n is bigger than m. In other words this says there is a natural number bigger than all natural numbers which is false. All I've done is swapped the quantifiers round but in so doing I've turned a true sentence into a false sentence. Remember that example from the American Melanoma Foundation? In their fact sheet they wrote one American dies of melanoma almost every hour. Using our quantifiers we could write that like this. There exists an American such that for every hour a dies in our age. There is an American such that every hour a dies in our age. Poor guy. I mean quite amazing. What the writer obviously meant was the following. For every hour there is an American such that a dies in our age. It will be different Americans for different hours. Now as I mentioned earlier in the case of everyday English these are almost never a problem. Everyone understands the context. We know what's meant. We know that this one is not meant because this is clearly wrong. We know that that one's the one that's meant. And with a simple mathematical example like this one arguably it's not important either because it's everybody knows what's meant. We know that there is a there is no largest natural number. We know it must be this one and not this one. So in these examples there's probably no problem. But we want to use mathematical notation in complicated situations and to talk about things we don't yet understand. That means we can't disambiguate. It's really important that we say things in the right order. OK. I think it's time for a quiz. So how did you get on? Where the literal meaning of this statement is captured by number one. That's the literal meaning. It says there is a licence for which there are two distinct states that that licence comes from. So this is the literal meaning but it's false. Licences are issued by states. You can't get a licence that's issued by two separate states. So the correct answer to the question is number one. But it's not what the person who wrote that sentence in the form in the driver's licence application meant to say. Let's look at number two. That says there are two different licences, they're different, there are two licences which are issued by one state. Well I guess it's possible that you could own two licences that are both issued by the same state if you had two identities or something like that. So this is a possibly true statement but it's not what the sentence means. Let's look at number three. That says there were two licences and two states, different states, different licences. There were two licences and two states, one licence comes from one state, the other licence comes from the other state. This is the sentence that the driver's licence application meant to say. So the literal meaning is number one which is false. Number two may be true but it's not what the sentence is about. Number three is clearly the intended meaning. It's a meaning that we would all understand from this because we know about licences and about states and so forth. So this is the one we understand but it's not the literal meaning. It doesn't matter when you're applying for a driver's licence unless I guess if you get into trouble you get your lawyer might try to get you off by arguing on the basis of the mathematical meaning. Good luck if you want to try that. But in mathematics we can't allow this kind of thing to happen. We can do all sorts of problems and in mathematics we can't hire a lawyer to get it out of difficulty. Okay let's look at the next question in this quiz. Well the correct answer is number three. Let's see why. What does the first one say? It says there is a licence and there are two different states such that that licence is valid in one state and valid in the other state. So it says there's a licence that's valid in two states. Well okay, it's true because in America when you have a licence valid in one state it's valid in any state you can use it anywhere. So it doesn't say anything particularly interesting. What about number two? That says for every licence and for every pair of states which could even be the same state, the licence is valid in one state or it's valid in another state. Well is it actually false? There's a statement because there can be invalid licences. If you've got an invalid licence that means the whole thing is wrong. This one is the one that captures that sentence. Let's just read it. It says for every licence, any licence, if there is a state in which that licence is valid then that licence is valid in all states. So three is the one that captures this sentence. One is actually a true statement but of very little relevance and two is actually a false statement. It's false remember because you can have invalid licences. So it's not the case that for all licences and for all states the licence is valid in one state or another state. Okay, how did you do on that? You might have had difficulty reading the formulas in that last quiz. If so, check out the supplementary video tutorial called How to Read Mathematical Formulas. You'll find it in the same place you access all of regular tutorial videos. In this video, I'll explain how you read mathematical formulas. Just as you're probably familiar with an arithmetic and algebra, you need to know the conventions regarding the order in which logical operators apply. Well let me begin by just quickly summarising the precedence order for applying the logical connectives. The ones that bind the most tightly, the ones that are sort of the strongest if you want, that have told something close together, are the quantifiers for all and exist. And a quantifier applies to whatever comes adjacent to it. Okay? Now typically what comes adjacent to it involves various other things like hands and ores and knots so you would put them in parentheses or brackets, square brackets or whatever. So very often in fact I almost always make a habit of putting whatever I want next to it in parentheses because so for all then applies to everything that comes there. Okay? It binds tightly to this, applies to everything, the same with existing here.  So I could say for all B red B and that would apply to the red balls and if there was something else here, you know if there was an da da da then the for all would not apply to that. If I wanted to for all to apply to that I'd have to put parentheses around there. I didn't put parentheses here, I could do. Again especially when I'm giving introductory level courses I usually put parentheses around quantifiers but if you look at some of my research work and advanced courses you'll find I often don't do that. That's fairly consistent among instructors. You know the golden rule is if there's any doubt whatsoever and if you're beginning on this material there certainly will be doubts. If there's any doubts put parentheses in. You know you can't have too many, well that's not quite true if you have too many parentheses it gets hard to read it. So you have to strike a balance but always if there's going to be any ambiguity put the parentheses in and mix parentheses along square brackets or even spaces. I'll try to remember to give an example in a minute with a space because you can sometimes use spaces to disambiguate but the golden rule must be you want to avoid someone being left unclear as to what the meaning is. Negation is about the same strength as, well is the same strength as the quantifiers. So the negation applies to whatever's immediate next to it and since we usually want a whole bunch of things to be negated then the negation is followed by parentheses and then it applies to everything between there. Let me give you the following example. Suppose you wanted to say not the case that three is greater than zero and three is less than zero. Okay, well is three bigger than zero? Yes. Is three less than zero? No. So here I've got a conjunction of something that's true and something that's false. So this conjunction is false so its negation is true. So this guy is true but supposing I wrote it this way, not the case three greater than zero and three less than zero. Supposing the parentheses didn't include both of those, they just included one of them. In that case, what have I got? This guy is false. This guy, three is greater than zero is true so that guy's false. So here I've got a conjunction of false things so I've got something that's false. So these clearly aren't the same because this one's true and that one's false. Here the negation applies to everything in between, which makes it true. Here the negation only applies to the thing next to it. Now I could have gone back here and put parentheses here and I'll mention that in a moment. It actually comes up in the next priority. That wouldn't have changed things. That wouldn't have changed things because the negation would apply to what was in the next parentheses. Negation applies to whatever comes next and what comes next is the whole thing because the parentheses includes the whole thing. So simply putting parentheses inside doesn't change anything. It makes it maybe a little bit clearer. Although this is one of those cases where adding parentheses arguably makes things a little bit less clear. But in terms of the logic, the issue between these two wasn't whether there were parentheses around the three greater than or less than zero. The issue was whether the parentheses governed everything that was next or just the one thing that was next. So these are not the same. The next one is conjunction. Let me now just pick up that thing I mentioned before. When I did that the first time, I wrote this. I said, three is bigger than zero and three is less than zero. Now I in fact left a space. If you watch what I did, I left a space. And I realised at the time I was doing it that that's what I was doing, which is why I decided to pick it up now. So this says that three is bigger than zero and three is less than zero. You actually don't strictly speaking need parentheses around here because this is an atomic formula as we sometimes call it. This is a basic building block out of which we're building more complex formulas. This simply states a fact, three greater than zero, an atomic fact, a single fact. This states another atomic fact, three less than zero. So when you have basic facts about arithmetic or whatever, they stand on their own. The conjunctions and the quantifiers are what combine these basic facts. So you strictly speaking don't need to put parentheses around these. This is a case where I typically would just leave a bit of extra space in here to sort of make it clear that this is a unit and that's a unit. On the other hand, if you want to be safe and it's always wise to be safe if you're at all unsure, you could put those things in. And I did this here. I went back and put them in just to make it clear. Okay? Then some mathematicians would say that conjunction, disjunction are more or less the same or conjunction, disjunction implication. We're getting down to a sort of a general grouping now where everything is roughly the same strength. There are actually some arguments that say that conjunction should be tighter than disjunction, but it's not particularly strong. In any case, I think in, this is a case where one should always use parentheses to disambiguate. The point is that the conjunction applies to whatever's to the left of it and whatever's to the right of it. And if you want it to apply to a whole bunch of things, you put them inside parentheses. Likewise here, you would have a whole bunch of things. And the same is true for disjunction implications. So regardless of whether you think that's stronger than those, the issue should never really arise because you should always put things in parentheses to just say it's this guy or this guy. And in here there could be a whole bunch of things. And that whole bunch of things will be disjoint with this. And likewise here, if you have an implication or a conditional, this whole thing would be the antecedent and this will be the consequence. Now in here there may be all sorts of conjunctions and disjunctions and stuff. There may be quantifiers in here. There may be quantifiers in here. There could be all sorts of stuff in here. Negation signs inside. This whole thing would imply that whole thing. So whenever you're looking at, I mean the basic thing with all of these is when you've got a quantifier or a negation symbol or a conjunction or a disjunction or an implication or equivalence actually. I didn't talk about equivalence but equivalence is just a conjunction of two implications, the by conditional. So we could put that one in here as well. Strictly speaking, if you did assume that that had more tight binding than this, you could write something like this. You could write A and B or C and D. And if you put space in there, that I would think is fairly clear that it meant to be this or that. So this is, I would say, at least the way I was brought up. Let's put it that way. As a mathematician, I was brought up to us to say that that actually is okay and it's not ambiguous. But I would almost certainly now, I think I've cured myself of that childhood sin, I would always put in parentheses and say it's A and B or C and D. I mean you just have to be very careful about not making sure that things are nicely not ambiguous. Okay? So golden rule, put parentheses in. And then everything applies to whatever comes between the next parentheses. It's kind of optional as to whether you have parentheses around the quantifiers. But the parentheses that follow providing you always do it, there shouldn't be any problem. Okay? Now let me illustrate those points with examples that are all related to that quiz at the end of lecture five. Okay? So let's take these one at a time. This was actually from that particular quiz. I've got a for all and for all applies to everything that's adjacent to it. Now that parentheses there teams up with that parentheses there. And I've actually written them not as parentheses but as square brackets to make it absolutely clear. That is the thing that the for all applies to. Okay? For all applies to all of this. In particular, what it's going to say is that pick any license and then it's going to say something about the licenses. Now the license L is going to appear on both sides of this conditional and it will be the same L because the L has been picked here and once you pick the L it'll apply to everything here. So that L is bound by that quantifier. Okay? So I would say L is bound by the quantifier for all L. Okay? Quantifier binding. Okay? So let's read it now in English. It says for any license L if there is a state in which L is valid if L is valid in some state at least one state then L is valid in every state. Okay? For any license L if L is valid in some state the exists here simply applies to this. The exists binds what's next to it so the exist simply binds this thing. Likewise the for all binds what's next to it which is this thing. So what this says is for any license or for every license L something happens. What happens? If that license L is valid in some state then that same license is valid in every state. So this is the one that actually says a license that's valid in one state is valid in every state. Which is true in the United States by the way. Okay? That's the first one. Let's look at the second one. What's the difference? Let's see what we've got for all applies to something in the middle. So for all applies to everything here because I've got the parentheses. The only difference is that instead of having a conditional or an implication I've got a conjunction. So let's see how we would read that. Okay? I mean the binding is the same. The for all applies to everything here. This exists applies to this thing. This for all applies to this thing. And the L is the same L here as here. Because once you've said the for all L within this expression here the L is determined by that. The L is still bound. So as was the case there, the L inside here is bound. Okay? But how would we read it? We'd say for every license L there is a state in which the license is valid and the license is valid in all states. So let me just write that down. For any license L there is a state in which L is valid and L is valid in every state. Now it doesn't mean the same as the previous one. Let's think about this. For any license L for any license there is a state in which that license is valid and L is in fact valid in every state. But this is actually false. This precludes the fact that there are invalid licenses. For example, if you go to California and you drive with too much alcohol in your bloodstream you will find yourself with an invalid license. Not every license is valid. So this is actually a false statement. The one above was true. This is true in the United States. This is false. This means something different. In fact really it's the first thing that was the problem. For every license there is a state in which it's valid. Well that's simply not the case. Already the first conjunt makes it invalid. Didn't arise in the first one because in the first one the part that said it's valid in a state was the antecedent. If it's valid in a state then it's valid in all states. So that said for every license if it's valid in a state. This says for every license it is valid in a state. Well that's not the case. Not all licenses are valid. Okay. So there is a distinction between these two and in fact the distinction is a meaningful one in terms of validity of licenses and so forth. Let's look at this one. Well here we don't have these brackets. So let's see what's going on. This means for all L for every license there is a state that the license is valid in that state. Well is that true? Is it true? Remember this is a unit. The for all and the exist apply to whatever's next. So there's a line here. The for all and the exist don't apply to that. They apply to what's next and there was no bracket so it doesn't get included here. So what this actually says is that for every license there is a state in which that license is valid. So what this really says is that all licenses are valid somewhere. Well okay that's not true and the statement is if that's the case then for all S2 that would say L. Well haha. This would say that L is valid in all states. Well now we've got all sorts of things gone wrong. As a conditional this guy would look on the face of it as if it was going to be true because the antecedent is false. It's not the case that all licenses are valid somewhere. There can be valid licenses. So this is a false antecedent. Now you might be tempted to say since it's a false antecedent the conditional is true. But not quite because this guy isn't even defined. This isn't defined. This is meaningless. What's L? What is that L? It's not governed by that quantifier. This is just an orphan. It's just sitting there. We don't know where it comes from. We don't know what it means. It's just a letter that has no internal meaning to this formula. So it's not the case that this is a valid conditional. It's actually undefined. This is meaningless unless you know what L is. If you know what L is you can assign meaning. And once you know what L is then if L replied to my license, if that L there was my license then we would have a meaningful and in fact a true conditional. But as it stands you've just got a completely unbound variable. So the L there is what we might sometimes call just an unbound or free variable. Unbound variable, free variable. Until you assign a value to it it doesn't have any real meaning. And then let's finally look at this one for all L1. What's the difference here? It's somewhat similar to the one up here but not quite. Let's just read it through. It says for every license and for all pairs of states the license is valid in one state and the license is valid in two states. Well that really just means all licenses are valid in all states. Again this is not the case in the United States because you can have invalid licenses. So we've got something that's actually false. And it's over. I mean there's redundancy here. Because the second S adds nothing new. It simply says for all licenses and for all states the license is valid in that state and it's valid in the other state. So we could just scrap that and scrap that and we'd have the meaning without any of that stuff. So there's nothing actually wrong with this. It's just, I mean it's a false statement but it's got redundant clauses. The second clause says adds nothing that the first one didn't already state. OK. Finally let me just try to distinguish between four cases that beginners typically find to be very confusing. They're actually really very distinct and if you find this confusion between these four that's a sure sign that you haven't yet mastered the notations and what they mean. OK. Let me just write down a transcription of what it means and then let's just ask ourselves exactly what that signifies. So in English that would say for every X if P of X then Q of X. OK. For every X if P of X then Q of X. This is very common. OK. For every number, for every real number, if that number is non-negative then it has a square root, et cetera, et cetera, et cetera. So this occurs a lot in mathematics, this kind of statement for every X if P of X then Q of X. OK. Very meaningful. And it's the same X here notice. Once you've got that for all the X here is the X here. So whatever X providing the X satisfies P then it satisfies Q. So this establishes a relationship between P and Q because if you've got an X that satisfies P then that X will definitely satisfy Q. So this is a very strong and very common statement to make. This is also pretty common. This says for every X P of X and Q of X. It says that every X satisfies P and Q. It's kind of strong. I mean it doesn't occur terribly frequently because that's really the same. I mean you could equally, you could just as equally say for all X P of X and for all X Q of X because you're basically saying everything satisfies P and Q and that's equivalent to everything satisfies P and everything satisfies Q. Notice by the way that this is non-ambiguous because of the binding. The for all binds what's next to it so the for all can only bind that. The for all binds what's next to it and so I don't need the parentheses here because in this case the for all absolutely can't be confused with that. So here's a case where you don't need extra parentheses. I didn't even write the parentheses here. You don't need them. This is totally clear in this case. Okay. And it's equivalent to that. So you don't see this very often because it really is just saying everything satisfies P and everything satisfies Q. But it's okay if that arises. Don't worry about it. It might in a context it might be sensible to write that down. But it doesn't have the same sort of logical force that this does. This has real logical force. It establishes that there's a relationship between P's and Q's. Okay what about this one? This says there is an X for which P of X and Q of X. This is again pretty common in mathematics. This is quite a strong statement. It says you can find a single X which satisfies P and satisfies Q. So you can find an X which has the property P and which has the property Q. So this is a strong statement. That one was strong. That one's strong. I mean this one's strong but it's only strong because each part is strong. So there's almost a redundancy in the way it's written. So this is, maybe I would put strong in quotation marks to sort of say well yes it is strong but it's not strong because of the logical structure. It's strong simply because it's making a statement about P and Q both been satisfied by all X's. Okay what about this last guy? This is one that people often write down and this really means nothing in any real sense. It says what there is an X such that if P of X then Q of X. Okay there is an X such that if P of X then Q of X. It's pretty rare to ever need to say that actually. This really doesn't arise particularly frequently that you would need to say something like this. If you see yourself writing and exist with an implication chances are very high that you've sort of got confused. Let me just put it this way. Let me just say that this is weak. Okay it's not on the same strength as these guys because this says for every X if it satisfies P then it satisfies Q. That's making a strong statement. For every X there's an implication. This simply says there's one X for which there's an implication. Well in a sense the implication is almost vacuous then. I mean one thing to say for example is that if you can find an X that does not satisfy P. In other words you can find an X for which P of X is false. If you can find an X anywhere for which P of X is false then you'll have a conditional that's necessarily true. So this can be made true by finding an X that doesn't satisfy P. That's all it would take to make this thing true. So if you're trying to make a stronger statement, if you're trying to make an existence statement, if you're using this to say there is an X with a certain property then you could make this guy true simply by finding an X that does not satisfy P because if you can make that part false the conditional becomes true. So that's one of the reasons really why this is weak. I'm sure there will be circumstances where this could have some significance but basically my message for you would be forget that one. It's just if you see yourself writing an exist with an implication after it the chances are very high that you've got confused. Always be prepared to override what I say. All sorts of circumstances can arise but in general these guys are all quite significant. That's particularly significant. That one's very significant. This one is sort of less so because it really just reduces to the two separate things. And this one is really pretty weak. So exists combined with implications. If you see that flag it and say do I really mean what I'm writing that? Okay well I hope that's helped clear up some of the basic issues about reading formulas but like many things at this stage really the only way to get rid of any confusions is to just do a whole bunch of examples for yourself. Okay good luck on sorting these things out as you work through the rest of the course. Okay problem set three. So we've got a variable ranging over doubles tennis matches. Doubles by the way is when you have two people playing against two other people, two teams of two people playing against one team against the other. T is another variable ranging over doubles tennis matches where Rosario partners with Antonio. WX means Rosario and her partner. Whoever that partner is wins the doubles match X and we have to find the English sentences that mean the same as a symbolic formula exists to TWT. Now this kind of thing is always a stretch because we're taking everyday language which is ambiguous and vague and underspecified and can be sort of pummeled and stretched in different directions and we're going to capture it with a formula which is precise and well defined. So when it says mean the same there's going to be some slack here and sometimes there's a little bit of argument so that one could have. I've picked an example where I think it's fairly clear at least from a mathematical perspective it's clear. If you haven't got used to dealing with mathematical language you may find this more difficult and this whole course is aimed at people who haven't got that familiarity so I think you will find it difficult. Okay so let's just take them one at a time. Rosario and Antonio win every match where they are partners. Well that's actually every match where they are partners there's really a hidden for all T in this thing. It's about a for all T. In fact basically what you're saying is in every match where they are partners they win or she wins. I mean one wins they both win, they both win. It's a partnership team. Okay whereas this is existing so it's not that one. Okay let's look at the next one. Rosario sometimes wins a match when she partners with Antonio. So there is a time, there is a game when they partner together when they win. That's this one. So that's correct. Now that really does capture it. There is a time when they play together and as a partner there's a partnership and they win. Now now you can look in some sources to say that sometimes it is used exclusively to mean more than one. I mean I don't think that's the case. I mean you've found people to say that. Language is flexible. In any case in mathematics we always interpret things like some, sometimes at least one. That's a whole point about the way we set things up. We eliminate these ambiguities by being specific. And we are specific to say that whenever you are setting something exists, some time, some game or whatever, you mean at least one. Okay? In which case you've got existential quantifier. That means there is at least one tennis game where they play together and they win. Okay? So that one's okay. Whenever Rosario plays with Antonio, she wins the match. Well that's really, again, that's for all T, W, T. So it's not that one. Rosario and Antonio win exactly one match where they are partners. Well that one isn't going to work, all right? Because that says exactly one match. There's no specification here of exactly one match. If you wanted to do that, there's a notation. This notation exists a unique T such that W, T. You can say it and you can say it other ways. I mean you can, this is just an abbreviation for an expression. We've seen that in the problem sets. Actually one of the assignments. So you can capture it, but this doesn't capture it. This just says there's at least one. It doesn't say there's exactly one where they win. Okay? Rosario and Antonio win at least one match when they are partners. That's it. That's another one. That's fine. At least one match when they are partners. Okay. If Rosario wins the match, she must be partnering with Antonio. Well, first of all there's a universal quantifier floating around here, I think. Yeah. Because it's saying whenever she wins the match, she must be partnering. So there's a universal quantifier here. But it's even worse because the universal quantifier is actually for all x, for all matches. Okay? For all doubles tennis matches where she wins something or other, something else. So there's actually here what's generally known as a scope problem. In this statement, the quantification is actually over something different. It's over all possible double tennis matches, not just the ones where she's partnering. So not only does this not capture it, there's actually another issue. There's a scope issue involved. Okay? Because here, the T ranges only over games where they play together. In this case, we're looking at games where Rosario plays with whoever she's playing with. Okay? So there are a couple of things that prevent this one been the right answer. Okay? Well, I'm, you know, as I said at the beginning, from a mathematical perspective, this is actually very clear. It's definitely B and it's definitely E. And the reason I can be so definitive about that is because I'm familiar with the way we've set up the meaning of this in mathematics to correspond to mean at least one. And we interpret in mathematics, we interpret anything that exerts an existence to mean exists one, at least one. And so things like sometimes, some of these, some of those, they're all interpreted to mean at least one. Okay? Let's look at the next one. Well, same setup as in question one. The only difference is now we're talking about, for all T, W of T. So let's, let's run through this one. Rosario and Antonio win every match where they are partners. So every match where they are partners, that would be for all T, because that's what T captures, T is the doubles tennis matches where they partner, and they win. Well, that is that. So that one's okay. What about this one? I mean, this has really got nothing to do with that, has it? Rosario always has got nothing to do with winning. It's just saying she always plays together. That would essentially say that did X and T have the same variable, in fact. I mean, it's just saying that there's no distinction between X and T. So I think rather than cross that as said, that was wrong, I'll say this isn't even a candidate. I mean, it's got nothing to do with winning. Okay. Let's look at part C. Whenever Rosario partners with Antonio, she wins the match. Whenever she partners, that's for all T, she wins. She wins, they wins. So it's all the same in doubles tennis. So that's okay. What about this one? Sometimes Rosario wins the match. No. I mean, first of all, it's, it's not about T, it's about X. Sometimes she wins with whoever she's playing with. And it's an existential one, so it's essentially of the form Exist X W of X. That's really what it means. Sometimes Rosario is in the winning team. She wins. Well, that's not that. It's a different quantifier, and it's over X, not T. So, not that one. I won't cross it out because at least it does talk about winning, so it's a candidate, but it's not the right candidate. Okay. Rosario wins the match whenever she partners. This is whenever she partners, that's essentially for all T, and whenever that happens, she wins. Okay. Bingo. How much is that? That's correct. And finally, if Rosario wins the match, she must be partnering with Antonio. Well, essentially you've got something like for all X here, et cetera. So, as before, as in question one, we've got a scope issue here. This is actually about all possible matches, not just the ones where she's, she's partnering. And the conclusion is that she's partnering with Antonio. So, so this doesn't, I mean, it does talk about winning, but it's, it doesn't come close because there's, there's a scope problem. The variable doesn't mean different things. Okay. So it's not that one. So in this case, we've got a, we've got c, and we've got e. That's kind of unusual to have one of these multiple choice things where three of them are correct, but there you go. Sometimes, sometimes that happens. Okay. Let's move on to question three. When question three, if you look through these, looking for something that seems to say there's no largest prime, I think you quickly end up looking at this one d, which says that for any number x, there is a number y, which is prime and bigger than x. So that certainly says there's no largest prime. Now the question is, do any of these say the same in a different way? Well, let's just look at them in turn. That says there don't exist any x's and y's for which x is a prime, y is not a prime, and x is less than y. Well, there are plenty of pairs x and y that satisfy that. So this is actually false. So, I mean, we weren't, we weren't asked to say whether things are true or false. But this is false, and we do not, we do actually know there was no largest prime. That's Euclid's theorem that the primes are infinite, and the list of primes goes on forever. So it can't be this because this is actually false. But in any case, it doesn't mean the same. This just means something just nonsensical. Of course, there exist pairs x and y with x prime and y not a prime and x less than y. So to say it's not the case, it's clearly wrong. What does this say? For every x, there is a y, such a x. Well, first of all, that would say for all x, x is prime, that would say every number is a prime. So that's false as well. So that can't possibly be it. That can't be it. That can't be it. What does this one say? For all x and for all y, x is, that says as well, every number is a prime. That's false. Wow. Why are we, are we rattling through these? These are, these are just plain false. They're absurdly false, if you like. That was the one that was okay. What does this say? There is an x such that for all y, whoops, that says all numbers are prime again. Forget that. It simply says all y is a prime. Well, they're not. So that's also absurdly false. Scratch that one. I mean, I'm scratching them because not only don't they actually say that, but they actually say something nonsensical. What does this one say? For all x, there is a y, x, whoo, same thing again. What this actually says is that everything is a prime, which is false and it's absurdly false. So it's not just that A, B, C, E and F don't capture it. They don't capture anything sensible whatsoever. This is one on the other hand does say there's no largest prime. Okay, let's move on to number four. Well, I won't go through these in detail as I did with the previous question because the same kind of considerations apply. The only one that actually captures it is E. Let's just read what it says. There is an x which satisfies phi and for all ys that satisfies phi, x and y have to be equal. In other words, it's impossible to find a y that satisfies phi other than the x that you start with. So there is one. The statement begins by saying there is something that satisfies phi and this part says it's the only thing that satisfies phi because if you look at all the possible ys that could satisfy phi, the only one that does so is y equals x. So this actually captures the busy unique x such that phi of x and these four, they're not only, if you try to figure out what they say, if they say anything vaguely sensible at all, they turn out to be just nonsentrical and they certainly don't capture that. Incidentally, this symbol is a moderately common symbol in mathematics. It's not something I made up for the exercise. The exist with the exclamation point does actually mean there is a unique x. You'll find that quite a bit in mathematics. Often you need to be able to say there is a unique solution to something. Now, this exercise tells you that you don't need to have a separate quantifier to mean there is a unique one because you can actually define it in terms of the standard existential quantifier and the universal quantifier. So this is in fact just an abbreviation but it's a useful abbreviation and so you'll often see it. Okay? Well, for question five, let me observe that this symbol, I mean you do see this symbol in sometimes in computer science, very rarely in mathematics except in a situation like this where I'm using this to refer to some arbitrary but unspecified binary operation. So this isn't a particular operation, I just mean there is some operation which I'll call x up at r or y and we need to be able to express the fact that that's not commutative. So this doesn't have a particular interpretation, I'm just using it to mean any particular, any unspecified binary operation. And so what we need to do is ask ourselves which one of these means that it's not commutative. Well commutative, let's write down what it means to be commutative.  So that's what being commutative means. Which one of these negates that? Well, when you negate universal quantifiers you get existential quantifiers and things that are true become false or the equality becomes an inequality. And so if you skip through these you find, yep, there it was, c. That says there is an x, there is a y for which they are unequal. There is an x, there is a y for which they are unequal. So that's certainly a negation. Do either, do any of the other ones fall in as being a negation? Not really, not even close, because when you negate both are for alls become an exist. They don't remain for alls, so it's not that one. They don't remain for alls and there's a for all there. So for a variety of reasons, none of these three qualify for that. So there's no, there's no possibility of having two possible expressions. That's the only one. Okay. Okay, question six, evaluating this proof. And this is very typical of the kind of work you see from students who are beginning to look at proofs. Because what this person's done is they've identified the key idea. This is absolutely the key mathematical idea behind this. The fact is that this, this is not prime. And in fact, what I'll do, let me just give the proof that the person should have done. Okay, and then I'll discuss why there's a problem with writing this down. Okay, so what the person should have done is, is something like the following. You begin by saying the claim is logically equivalent to the following statement for any positive integer n, n squared plus 4n plus 3 is not prime. It's logically equivalent to that. To say there doesn't exist an integer for which that's prime is logically equivalent to saying that for any positive integer, it's not prime. And the person then was going to, should maybe prove this is, is, is true. Okay. We prove this, this statement. So we're proving a logically equivalent statement. Okay. So let n be a positive integer. And I'm doing this one in gory detail because I'm trying to get maximum points for this one. Okay. Then by basic algebra, n squared plus 4n plus 3 equals n plus 1, n plus 2, n plus 3. But n plus 1 and n plus 3 are positive integers, each greater than 1. N plus 1 is at least 2, n plus 3 is at least 4. So these are positive integers greater than 1. So by definition, n squared plus 4n plus 3 is not prime. Because it's a product of two positive integers each greater than 1. Okay. So that's what the person should have done. Now, let's go back to what was here. This is the key algebraic heart of this thing. Alrighty. But it's not a proof. And the reason students often do this kind of thing is they're used from high school, they're used to the fact that algebra is all about algebraic manipulation. And indeed it is. But we're talking about proofs here. And a proof is much more than getting the algebraic manipulation rights. If the algebraic manipulation is not right, you don't have a valid proof. But a proof is all about giving reasons and making a, giving an explanation. It's a story. A story with a beginning and middle and an end.  It's about, it was war and peace. And he summarises it by saying it was about some Russians. Well, this is like saying it's about this. Obviously war and peace is just about some Russians, but there's much more than that. And that's really what we're doing here. We're looking for the full story. This one's actually, I think, going to be fairly difficult to grade. I'm going to put four for logical correctness here because logically this is the heart of it. Once you realise that, that's the logical heart.  There's just no clarity about this because there's no explanations, nothing. Okay. This is really nothing, nothing valuable here. Opening. There isn't an opening. Just jump straight in. Let's see. Stating conclusion. Whether person did state the conclusion. So I'm going to get that. You have to form acts. The conclusion is stated. That's, that is how you're supposed to end. Okay. As I did here, that's not prime. Reasons, there are no reasons given. Okay. I mean, that's just going to be a zero. And then, let's see what I've got here. Overall valuation is zero. I mean, as a proof, I can't really give anything for that. Okay. Well, let me think. You know, actually, now I'm going to be a bit generous here. I'm going to give two for that. I think because this is key. I mean, I'm going to give some credit for this. I mean, it is the key part of this. And it was the setting that was wrong. So I'm going to give two for that. So that means I've got four eight. I've got ten for that one. Yeah, a little bit generous maybe as a proof. The person certainly has the algebraic ability. And seeing this is key. I mean, that really is, yeah. Okay. I was, I was, I think that's okay. I think that's actually a good mark to give for that one. Okay. But these are not easy to do. You're making value judgments.  The way we've structured this course is you'll be seeing a lot of exercises like this. And the intention is that by the time we get to the end of the course, you'll have got the general gist of how to do this. I mean, all instructors develop their own methods. And I'm just giving you mine as an example. But we're something that's sort of essentially qualitative as grading proofs is. And it's like grading essays. You know, people, people end up with difference, you know, there are stricter graders and less strict graders. My goal is always when I'm grading this kind of a context is to look for reasons to give people marks because I want to give the credit for what they're doing, but at the same time points out the things that still need to be done. Okay. All righty. Well, that was the end of problem set three. How did you get on with assignment five? Mastery of quantifiers is the one last ability you need to be able to cope with definitions of mathematical concepts and with mathematical reasoning. I'm going to begin by looking at the way negation affects quantifiers. But before I start, let's see how you're progressing by a way of a quiz. Okay. Let's see what we have. Is it the case that for every real number x, x plus one is greater than or equal to x? Yes it is. Is it true there is a real number x? So it's at x squared plus one equals three. Well that would mean x squared equals two. So we're really saying, is it true that there exists a number x? Whose square is two? Well, if we were talking about the rational numbers, the answer would be no, because the square root of two is irrational. But for the real numbers, it's true. What about this one? Well, for very large negative x, x cubed is an extremely large negative number which will dominate all of these numbers. So for large negative x, this expression, this cubic expression, is negative. So it's not the case that it's always positive. So that one's false. What about this one? Is it true that for all x there is a y? x cubed plus y cubed equals zero. That would mean y cubed is equal to minus x cubed. The answer is yes. Given any x, just let y be negative x. When you cube a number, you cube a positive number, it's positive. You cube a negative number, it's negative. So by taking y equals negative x in all cases, you get zero. So this one's true. What about this one? Is there an x such that whatever y you add to it, you get zero? The answer is no. If the quantifier is with the other way around, the answer would be yes. For every y, there is an x such that x plus y equals zero. Namely, you let x be negative y. But it's not the case there is one x that works for all y. So that one's false. What about this one? Well, is it the case that for all x there is a y such that if x is non-negative, then y squared equals x? Well, let's look. Supposing we took an x. If x was negative, then game over because this conditional would be true. It would have a false antecedent. If that x was non-negative, then there is a y whose square is x, namely the square root of x. So whatever x we take, there's always going to be a y that satisfies this. It's true. You might have to think about this one a little bit because there are two cases involved. Given an x, you can find a y that makes this thing true. If the x you're given is negative, any y will make that true because if the x is negative, the antecedent is false. But if the x you're given satisfies this condition, if the x you're given is non-negative, then the y you pick is the square root of x. See what's going on? If you're given a negative x, there is no y that satisfies y squared equals negative x, not in the real numbers. But that eliminates that case. So this one's quite subtle. I suggest you think about this one. It's the kind of thing that you encounter quite a lot in mathematics. Okay? Well, how did you do? Okay, let's move on. In mathematics and in everyday life, you often find yourself having to negate a statement involving quantifiers. Yeah, of course, you can do it simply by putting a negation symbol in front. But that's not enough. At least often it's not enough. You need to produce a negation, not a negative one. The examples I'll give should make it clear what I mean by positive here. But roughly speaking, a positive statement is one that says what is rather than what is not. In practice, a positive statement is one that contains no negation symbol or else one in which any negation symbols are as far inside the statement as is possible without the resulting expression being unduly cumbersome. Let's look at our first example of negating a quantified statement. Let A of x be some property of x. For example, x is a real root of the equation x squared plus 2x plus 1 equals 0. And I'll show that not for all x A of x is equivalent to, there exists x such that not A of x. For example, it's not the case that all motorists run red lights is equivalent to there is a motorist who does not run red lights. In this case, it's pretty obvious that these two are equivalent. The proof that I'm going to give in the general case is actually the same reasoning you automatically do when you look at this specific case. If it seems hard to follow, the issue is purely one of the abstraction. I'm proving an equivalence, so I'm going to prove an implication from left to right and then from right to left. So we begin with the left to right case. I'm going to assume not for all x A of x. Well, if it's not the case that for all x A of x, then at least one x must fail to satisfy A of x. So, for at least one x, not A of x is true. In symbols, there exists an x such that not A of x is true. Well, that's the left to right implication. I assumed not for all x A of x, and I concluded there exists an x not A of x. Now we want to do the other implication. So, assume exists x not A of x. Well, in this case, there's an x for which A of x is false. That's just expressing this in everyday English. Well, if there's an x for which A of x is false, then A of x cannot be true for all x. In other words, for all x A of x must be false. Expressing that in symbols, it's not the case that for all x A of x. And now I've proved the second implication from exists x not A of x to not for all x A of x. Assume exists x not A of x conclude not for all x A of x. If you found this reasoning had to follow, it's purely because of the abstraction. The logic is exactly the same as in the example. Almost certainly you had no difficulty with this example and that's because you're familiar with this situation. The human brain is very good at doing logical reasoning about familiar situations. When we turn those situations into abstract versions, the brain finds it difficult, at least at first. And in fact one of the things about becoming a mathematician is learning to take familiar everyday reasoning that we don't even think about, we just do it automatically and reproduce it in an abstract situation. And it's the abstraction that's causing your difficulty. You can follow the logic but you find it difficult to follow it in an abstract situation. And that's just because of the way the human brain works. Okay, why don't you try this one? Show that not there exists an x A of x is equivalent to for all x not A of x. And before you start, you might want to look at an everyday example. This is coming up as an example in the assignment for this lecture but you might want to try it now while this example is fresh in your mind. Okay, good luck on that one. With that one under our belts, now we can go back and look at that earlier example of the negation of all domestic cars are badly made. Let's see with a set of all cars, D of x means that x is domestic and M of x means that x is badly made. With this notation, the sentence becomes for all x in C, D of x implies M of x. For all cars, if the car is domestic, then it's badly made. We've already seen what happens when you negate a universal quantifier. The negation becomes there exists an x in C such that dx does not imply M of x. And here I've actually abbreviated the following. Not the case dx implies M of x. Well, it's not much of an abbreviation but instead of writing not dx implies M of x, I've used this simple notation dx does not imply M of x. But in any case, looking at our previous example, the one that I illustrated with the motorist, when you take for all x something and you negate it, you get there exists x with the negation of the thing inside. Just compare what's going on here with the previous example. One comment, why am I not saying exists x not in C. Beginners students often do this kind of thing. And the reason they do it is they are trying to go through a formula symbolically and negate things. And that's not the way to go about these things. You've got to think about what the symbols mean. In this case, it's talking about x's which are in C. The only x's we're interested in are x's which are in C. In other words, the only object we're interested in are cars. But if the only objects we're interested in are cars, the negation will only be talking about cars. So the in C part simply tells us which kinds of objects we're dealing with and we don't negate that. Okay, now let's look at this part. We know that dx does not imply m of x is equivalent to d of x and not m of x. In fact, this was the key part of our reasoning to figure out the truth table for the conditional. d of x does not imply m of x if d of x can hold and nevertheless m of x can fail. So we looked at this when we did truth tables. So the negation of the original sentence, which is this, is equivalent to, there exists x in C, this part is the same as this part. d of x and not m of x. Well, what does this mean in everyday language? It means there is a car which is domestic and is not badly made. And that's it. So if you found it difficult to figure out the negation of this sentence when we first looked at this example, now because we've got this notation and this little method for dealing with these negations, you should be able to follow it through fairly straightforwardly. Moreover, the previous time when we looked at this, even if you got the answer, you might not have been totally confident that you got the answer right. This kind of reasoning makes it clear that this is the right answer. And that's the whole point of introducing this formal notation and this logically precise reasoning. We're no longer left not certain if we've got the exact best correct, logically correct negation. The mathematics leads us to the answer. And that is the correct answer. Okay, let's do another example. Let's look at the claim all prime numbers are odd. Now we all know that this is false. And we know it's false because we know that two is a prime number, which is not odd. But let me tease apart the logic that underlies that conclusion. Because in more complicated situations where we're not familiar with the domain or with the result, all we'll have to use is the logic itself. So I want to make heavy weather of this in order to understand the kind of reasoning that we'd use in situations where we don't know the answer. Okay. So I'm going to let P of X mean X is prime. And I'm going to let O of X mean that X is odd. So the sentence can be written symbolically as for all X if X is a prime, then X is odd. When I negate this, I get, exists X, not PX, gives O of X. Or another way of writing it, there is an X such to P of X and not O of X. The negation of not for all X, P of X implies O of X is there exists an X such to P of X and not O of X. In words, IE, there is a prime that is not odd. So in order to prove that this is false, which is the same as proving that the negation is true, the logic says, find a prime that is not odd. And we can. Two is a prime that's not odd. So if I want to prove conclusively that this statement is false, which is the same as proving that its negation is true, what I need to do is demonstrate that there is a prime that's not odd. And in this case, that's immediate. We just pulled two out of the hat, observed that two is prime and it's not odd. Therefore, the negation is true, the original statement is false. Well, in that simple example, that was making much a do about nothing. But in more complicated situations, going through the underlying logic is often the only way forward. By now, you should have noticed the pattern of behavior that's happening with these symbolic negations. When we negate, a for all becomes exists and the for all sort of jumps inside and when it jumps inside, we can manipulate it and get the result into a positive form where the negation is at the most innermost point. You can actually turn these into formal symbol manipulation rules, which means you can implement them on computer systems and there are computer systems that do this kind of reasoning for you. I'm recommending very strongly that you don't do that because what we're trying to get at is mathematical reasoning and moving symbols around doing symbolic manipulation is not mathematical reasoning. It's connected with mathematical reasoning, it supports mathematical reasoning, we can use it in mathematical reasoning, but the real essence of what we're trying to do is to understand what the statements mean, understand what the symbols represent, and reason with the concepts. It's reasoning with concepts that mathematical thinking is all about, not symbolic manipulation. Okay. We showed that this was false by finding a counter example. In this case, the counter example was two. Supposing I modify it as follows. All prime numbers bigger than two are odd. In symbols, for all x bigger than two, if x is a prime, then x is odd. Okay. Now I'm going to give you a quiz. What is the negation of this statement? Is it one there exists an x less than or equal to two such that p of x are not o of x? Or is it two? There exists an x greater than two such that p of x are not o of x. Okay. Which one of those two do you think it is? Where the correct answer is two? It says there exists a number bigger than two which is prime that is not odd. That's the negation of that statement. Why isn't it number one? Well, because the original statement is about numbers bigger than two. So the negation must be about numbers bigger than two. We don't simply negate every symbol in sight and say, well, in terms of the ordering on the real line, if we negate something being bigger than two, then it means it's less than or equal to two. That's a symbolic negation. That's a sort of a detailed localized negation about the ordering on the real line. But the sentence as a whole means something about all numbers bigger than two. So its negation means something about all numbers bigger than two. Okay. Well, let's move on. Let x denote a person, let p of x mean x players for sports team T, and let h of x mean x is healthy. And let me look at the statement, there is an x such that p of x and not h of x. What does that mean in everyday English? There is an unhealthy player on team T. Now let me negate that. I'm going to find the negation by symbolic manipulation. Now this remember is the method that I'm suggesting that we don't use. I'm doing it that way in order to illustrate the mathematics and the underlying logic. If we negate this, we know that when we negate an exists, it turns into a for all. And then the negation moves inside, if you like. And then when we move that negation inside, we get not p of x or h of x. So the negation moves inside, we get p of x becomes not p of x. When we negate a conjunction, we get a disjunction. And when we double negate something, we get the original thing back. Remember this is not the way I'm recommending you do it. I'm doing this as an illustration of the underlying logic. This thing looks familiar. Remember when we looked at the conditional? p conditional q means the same as not p or q. They have the same truth table. So this guy can be rewritten as p of x plus h of x. In English, all players on team t are healthy. Well, is that the negation of that? There is an unhealthy player on team t. Well, if it's not the case that there's an unhealthy player on team t, then all the players on team t must be healthy. Which is definitely the case. That is definitely the negation of that. And again, let me stress. This is not the way you should do this kind of thing. I'm using this to illustrate how negation behaves with quantification. Next point. Suppose I write down a sentence like the following. For all x, if x is greater than 0, then there is a y, such that xy equals 1. Is that true or is it false? Well, there's no way of knowing. It depends what the x denotes. If x denotes a motorist or an automobile or a healthy team player, it's completely nonsensical. If x denotes a natural number, it makes sense but it's false. If x denotes a rational number, it makes sense and it's true. But the point I want to make is that a quantifier only tells you something if you know what the variable denotes. Associated with any quantifier, we have what's called the domain of quantification. Which tells us what does the x denote. If the domain of quantification is obvious, if we've set it in advance or the context makes it clear what it is, then we can use statements like that. If there's any danger of misunderstanding, if there's any potential ambiguity, we can make the quantifier more explicit by stating the domain of quantification. To make this more explicit, I could write it as, for all x in the set of rational numbers, if x is positive, then there is a y, such that xy equals 1. And now I've got a true statement that's unambiguous. It tells us that for every positive rational, well, wait a minute, wait a minute. I haven't actually been explicit as to what the y is, have I? Now arguably, having made it clear that the x denotes a rational, it's reasonable to assume that the y denotes a rational. But if I want to, I could be even more explicit and say for all x in q, if x is greater than 0, then there is a y in q, such that xy equals 1. I think most mathematicians would agree that if you're explicit about the quantifier at the beginning of a statement, then absent any indication to the contrary, the other quantifiers denote the same thing. But if there's any possibility of misunderstanding or if there's any potential ambiguity, it's better to be explicit everywhere as to what the quantifiers denote. Something else you need to be aware of with regards to quantification is that mathematicians sometimes omit the quantifier. We write things like if x is greater than or equal to 0, then square root of x is greater than or equal to 0. If you see an expression like this, what that means is the following. For all x, perhaps in r, or perhaps in something else, for all x in r, x greater than or equal to 0 implies square root of x greater than or equal to 0. Or something like that, depending on what the x denotes. I've assumed from the context, and this is a reasonable assumption, I've assumed that the variable is meant to range over the real numbers. Even though there's no explicit quantifier here, this would be read as meaning something like that. This is what's known as implicit quantification. The mathematician is simply leaving out of the formal expression any explicit mention of the quantifier. It's left implicit in the way this is written. Now, this is a fairly advanced point. I'm certainly not recommending you do this, but the professionals do this all the time, so you need to be aware of it in case you come across it in something that you read. But please avoid doing this. I realise by saying this that I'm saying do as I say, not as I do, because like all professional mathematicians, I do write things this way all the time, but while you're still learning about these ideas, it's best to avoid doing it because if you don't use this in the right kind of context, all kind of difficulties can arise. And having given you one caution, let me give you another one. This is about combining quantifiers with conjunction and disjunction. Let me just do this by way of an example. Let n, the set of natural numbers, be the domain of quantification. Let e of x mean x is even and let o of x mean x is odd. Look at the formulas for all x, e of x or o of x and for all x, e of x or for all x, o of x. I guess I don't need that last bracket, right? Okay? For all x, e of x or o of x and for all x, e of x or for all x, o of x. Notice that the first one is true. It says for every natural number, it's either even or it's odd. What does the second one say? It says every natural number is even or every natural number is odd. Well, that's false. Well, the point I'm trying to make here is you can't just take a for all and take it inside a bracketed expression. If you do that, you'll like it to end up turning a true statement into a false statement or vice versa. Similarly, if I take there exists x, e of x and o of x, we do it with an an this time and I'll take exists an x, e of x and exists an x, o of x. Again, I've put that extra bracket in there. Can't stop myself doing that. What have I got? This says there is an x which is both even and odd, which is false. What does this one say? There is an x that's even and there is an x that's odd. That's true. So the same thing happens with exists and conjunctions say. You can take an existence statement like this and in this case it's false but if you pair them up in this way, it's true. In other words, be very careful when you're reasoning with quantifiers, conjunctions and disjunctions. You can't simply take things inside the way you sometimes do in arithmetic. If you think about what these things mean, you're not likely to run into that difficulty. But if you start treating these as symbolic expressions to manipulate, then things could go badly wrong. Time for a quiz. Okay, well we've just seen that this expression something like for all x a x or b x is not equivalent to for all x a x or for all x b x. The example we looked at was whether numbers are even or odd. And it was a case that for all natural numbers, the number is either even or odd. But it's not the same as saying that all natural numbers are even or all natural numbers are odd. In the case of even or odd for natural numbers, this is true, but both of these disjunctions are false or the disjunction is false. Okay, what about this? Instead of having disjunction, we've got conjunction. Are these equivalent or not? What do you think? Well the answer is yes. They are equivalent. Now you could argue this in an abstract form, but let's just look at an example that's pretty illustrative. Let's take something like all athletes are big and strong. Okay, so x denotes athletes, a means big, b means strong. So that says all athletes are big and strong. This would say all athletes are big and then we'd have all athletes are strong. It's pretty clear that in the case of the example, that is equivalent to the conjunction of those two. If all athletes are both big and strong, then in particular they're all big and they're all strong. And conversely, if they're all big and they're all strong, then they're all big and strong. In other words, when you've got universal to quantification, if it's combined with a conjunction, then you get the equivalence of these two forms. But if universal quantification is combined with a disjunction, they're not necessarily equivalent. I mean, this isn't a proof. This is just an example.  So the answer is yes in this case. Let's look at another variant. Well, again, in this case, when we had even and odd numbers, that showed that these are not necessarily equivalent. But what about this, where we have an existential quantifier combined not with a conjunction, but with a disjunction? Do we have equivalence in this case? What do you think? Again, the answer is yes. These are in fact equivalent. What would be a good example? Oh, let's take something like there is a player. Let's keep with athletic examples. There are player who, let's say, who is a good attacker or a good defender. Okay, so there is a player who is a good attacker or a good defender. Is that the same saying? Let's just simplify it a little bit. There is a good attacker or there is a good defender. Okay. And we're going to disjain those. So if there is a player who is a good attacker or a good defender, one or the other, then whichever one it is will be here. If the player who is referred to here is going to either be a good attacker or a good defender, so one of those two is going to be true, which means that the disjunction is true. So if this is true, then that's true. And conversely, if there's a player who's a good attacker, then that player is a good attacker or a good defender, in fact a good attacker. Or if it's this one, then that's true. So we have an implication that way with a disjunction and we have an implication that way with a disjunction. The equivalent. Again, this isn't a proof. This is just an example to illustrate the fact. But you shouldn't have any difficulty taking that example and turning that into a simple little argument. At least I hope you won't have any difficulty doing that. Turning that into a simple argument to show that that implies that and that implies that. So in the case of existential quantification, if we have it with a conjunction, then we don't get equivalents. But if we have it with a disjunction, then we do have equivalents. And if you think about what's going on here, the fact is that for all is like, and let me put quotes on here because this is a sort of a specialised use. For all is like conjunction. And exists is like disjunction. Because for all says it's something's true for all and conjunction means that all of the conjuncts have to be true. This simply says there's at least one and this says there's at least one. So that's all about all things. And that's about at least one. So we get good behaviour. What do you call it? It's good or not? You get this nice behaviour if we have exists with disjunction because exists is essentially a disjunction sort of thing. And for all is a, that was on the previous slide, for all is really a conjunction, sort of thing. And it's when they're mixed up, when you get the disjunctive thing here and the conjunctive thing here that things fall apart. Okay. Well, there you go. How did you get on with those two parts of the quiz? And this is the last point I want to make about quantifiers. Suppose we're having a discussion about, oh, let's say the real numbers. So if we have variables x, y and z, they're assumed to denote real numbers. The domain of quantification will be the set of real numbers. And in the course of the discussion about the real numbers, we want to talk about rational numbers, or particular rational numbers. And then we might want to mention that there's a rational number x. Well, there's one way we can do that. We can talk about the rational number in this context. We can say there is an x in q. Or we can say for all y y q. Or if I want them to talk about a natural number, I can say for all n in the set of natural numbers. So by introducing explicit domains of quantification in this way, in the course of discussing real numbers, I can restrict attention to particular rationales or natural numbers or whatever. And so in the course of an argument, I can actually use multiple domains of quantification. Well, in examples like this where we're talking about different sets of numbers, this is fine. But in other situations, it really doesn't make sense to introduce multiple domains of quantification.  So suppose the domain of quantification is the set of animals. And then I might want to say something like every leopard has spots. Well, how would I do that? Well, I suppose I could say for all x in the set of lepids, x has spots. But in the next sentence I might want to talk about tigers, and then giraffes, and then who knows what. And very soon I could have a whole range of different domains of quantification floating around. And that's not very clean. It's not very nice, and it's certainly not very sensible. Because the discussion isn't really about lepids, or tigers, or giraffes or whatever. It's about animals. And if the discussion's about animals, then the set of animals should be the domain of quantification. So instead of writing something like that, what I should write is for all animals, if that animal is a leopard, then it has spots. That allows me to say something like there is an animal which is a horse and has spots. There's a spotted horse. Or I could say for all x, if x is a tiger, then x doesn't have spots. The point is that when I'm talking about animals, then when I refer to specific animals, I'm not changing the domain of quantification. I'm still talking about animals. I'm just describing properties of particular kinds of animals. The discussion is still about animals, so the domain of quantification should be animals. It's different here, because the domain of quantification, arguably, is the set of real numbers, or the set of all numbers. And then, because we have these standard subsets, it's okay to introduce things like this. You don't have to. You could actually use something analogous to this. But in this kind of situation, yes, if you're talking just about real numbers, then you really don't want to be introducing particular sub-dimage. You should use the analogue of these kinds of expressions and talk about if it's a rational and this, if it's a natural number than this. But if this is really a discussion about all numbers, not just the real numbers, then these are just particular categories of real numbers and natural numbers and so forth. And you can have sub-domains. You can have different domains of quantification. This isn't an issue of right or wrong. It's an issue of whether it's sensible and helpful to work in a certain way. And using separate sub-domains of quantification is fine if they are natural domains and it makes sense to talk about it that way. But the idea of a domain of quantification is that tells us what it is we're talking about. If we're talking about animals, then don't introduce different domains of quantification that are not animals. Even if they're sub-domains, it gets complicated. Okay, that's enough about quantifiers for now. I suggest you go away and see how you get on with assignment number six. Well for assignment six, I'm just going to do the last three questions, number seven, eight and nine. I think you should be able to do the first six on your own and check it on your own or with other students. So in number seven, we have to negate statements and put them in positive form. Part A was for all x in n, there is a y in n, x plus y equals one. The negation for that is, and I think you'll get the same answer as I do if you get it right. There is an x in n, such of all y in n, x plus y is not equal to one. You could have written that last part as not x plus y equals one, if you like, and that's equally correct. I'll just use this way of writing it. Okay, and in this one, for all x greater than zero, there is a y less than zero, x plus y equals zero. The negation of that in positive form is there is an x greater than zero and it's greater than zero. Okay? For all y less than zero, these don't change around. They stay the same way because these simply tell us what x is and why as we're looking at. And we get x plus y not equal to zero here. Okay, for part C, there is an x greater, there is an x, such that four greater than zero, negative epsilon less than x less than epsilon. And when you negate that, you get for all x, there is an epsilon greater than zero. And in this case, you're going to have to sort of split this into two. If one of two, if x is not between negative epsilon and plus epsilon, then either x is less than or equal to negative epsilon or x is greater than or equal to epsilon. I didn't put parentheses around either of these. I mean, I could have done if I wanted to be also clear, but this takes precedence over the logical operations, arithmetic expressions or inequalities and so forth. Take precedence over logical connectives because these are connectives. They connect statements about mathematics. And this is a statement about mathematics and that's a statement about mathematics. But if you wanted, you could have put parentheses around that, and you could have put parentheses around that. That would have been another way of doing it. Moving on to the last part, for all x and n, for all y in n is a z in n, x plus y equals z squared. We're not talking about whether these are true or whatever, we're just writing them down and negating them. So you get exist an x in n, exist a y in n, for all z in n, and I've just written this again, x plus y not equal to z squared, you could simply put a negation sign in front of that expression. Okay, well that's, that's, that's number seven. It's fairly straightforward. Let's move on to number eight. Question eight is our old friend, Abraham Lincoln, and the, this famous statement of his, or allegedly famous statement of his. And we need to negate that famous sentence, or let's let fx t mean you can fool person p at time t, and then his statement is this one. You can fool all of the people some of the time. There are some times when you can fool everybody. You can fool some of the people all of the time. So there are some people that can be fooled for all, at all times. But you cannot fool all of the people all of the time. Okay, let's just mechanically go through and negate that, looking at the formalism, and then we'll try to interpret the answer and, and, and express the answer in terms of English. Okay, so negate exists, it becomes for all, when it for all it becomes exists. Fpt becomes not fpt. Okay, conjunction becomes disjunction. Again, I'm not putting these in parentheses. And I'm not going to do it here because this is a, this is a, is a whole. The quantifier is binding. They're, they're very tight binding. And then we have disjunction, conjunction here, and then disjunction is here, they're, they're less tightly binding. So looking at this one, they exist becomes for all, for all becomes exist, we get negation. Conjunction becomes disjunction. And the negation here just disappears. So I've got a positive statement. Okay, so in terms of the formalism, this is fairly routine. In fact, this is such a routine thing that this is essentially algorithmic. I just went through and applied the, the patterns, the rules that I've observed happening. The interesting part of this, I think, and you weren't asked to do it, but let's do this. Let's see how we can express this in English language. And we're not going to get something quite as, as nice as this, I don't think, because we need to try and be, to avoid ambiguity as much as possible. So the first part would be the best I can think of at the moment is, let's see, at any time there is someone you can't fool. And, oops, or, because we've negated, or, okay. Let's have a look at this one. I can't really think of anything better than to say the following. For every person, you can't always fool them. Wel