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. They're teams of two people playing against, one team against the other. ts another variable ranging over doubles tennis matches where Rosario partners with Antonio. W x means that Rosario and her partner. Whoever her partner is wins the doubles match x. And we have to find the English sentences that mean the same as the symbolic formula xi tWt. At least 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 arguments 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 have found this more difficult. This whole course is aimed at people who haven't gotten that familiarity, so... So, I think you all found it difficult. Okay. So let's just take them one at a time. Rosario and Antonio win every mach 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 there were partners. They win, or she wins. I mean who wins? They both win, they both win. It's a basic partnership team. Okay well this is existing so it's not that one. Okay let's look at the next one. Rosario sometimes wins the match when she partners with Antonio. So there is a time, there is a game when they're, they're partnered together. When they win. That's this one. So that's correct. No doubt really does capture it. There is a time when they, when they play together and as a partner, as a partnership and they win. Now, now you know, you can look at some sort of gent will say that sometimes this is used exclusively to mean more than one. I mean, I don't think that's the case. I mean you'll find people that say that you know, language is flexible. In any case, in mathematics, we always interpret things like some. sometimes, as at least one. you know? That's the whole point about the way we set things up. We, we, we, eliminate these ambiguities by being specific. And we're specific to say that, whenever you're asserting something exists. Sometime, some game or whatever. You mean at least one. Okay in which case you've got existence from, existent to quantify that means there is at least one tennis game were they play together and they win, okay, so that one is okay. whenever Rosario plays with Antonio, she wins the match. Well that's really again, that's for all t wt. 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, 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, a notation. This notation exists a unique t. Such that wt. You can't say it, and you can say it other way. I mean, you can, this is just an abbreviation for, for for an expression. You know, we've seen that in the problem sets. Hm, yes actually one of the assignments, so you can't capture it but this doesn't capture it, this just says is it at least one it doesn't say that's exactly one we think when, okay. Rosario and Antonio win at least one match when they are partners, that's it that's another one that's fine this one when they are partners Okay. If Rosario wins the match, she must be partnering with Antonio. Well, first of all, there's a, there's a universal quantifier floating around here, I think. Well it's here. because it's saying whenever she wins the match, she must be partnered. So there's a universal quantifier here. But it's even worse, because the universal quantifier is actually for all of X. For all matches. Okay? For all doubles tennis matches where she wins something or other. So this one here is false. So this action 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 partnered. So not only does this not capture it, it, it, there's actually another issue. There's a scope issue involved. Okay. Because here the T ranges only over games where they've played 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 being the, being the right answer. Okay? Well I, 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 becuase I'm familar the way that we've set up the meaning of this in mathematics to correspond to mean at least one and we interpret in mathematics we intepret anything that exerts an existance to mean exists one, at least one. And so things like sometimes, some of these, some of those [NOISE]. they're all interpreted to mean at least one. Okay? Let's look at the next one. Well, same setup as in question 1. The only difference is now we're talking about for all t, w of 2. 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. Oh, that is that. So that one's okay. What about this one? [LAUGH] this has really got nothing to do with that as it is. Rosario has always got nothing to do with winning. It's just saying she always plays together. that would essentially say that that X and t are, are the same variable in fact. And is just saying that this, there's no distinction between X and T. so I think rather than cross out those, say that it's 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. 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, wfx. 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, well that one. I won't cross it out, because at least it talk about winning, so it's a candidate, but not the right candidate. OK? 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. That matches that. That's correct. And finally, if Rosario wins a match, she must be partnering with Antonio. Well essentially, you've got something like for all x here etcetera. So as before, as in question 1. We've got a scope issue here. this is actually about all possible matches, not just the ones where she is, she is partnering. And, thus, the conclusion is that she is partnering on somebody and so, so this doesn't, I mean just talk about winning but it's seems doesn't conclude because there is, there is a scope problem, the way I'm presuming different things and okay so it's not that one. So in this case we've got 'a', we've got 'c' And we've got E. It's kind of unusual to have one of these multiple choice things where three of them are correct, but there you go, sometimes that, sometimes that happens. Okay? Let's move on to question three. On question 3, 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, at this 1d. 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. Let's, that says there don't exist any Xs and Ys for which X is a prime, Y is not a prime, and X is less than one. 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 ask to say whether things are true or false. But this is false, and we do actually know there was no largest prime. That's Euclid's theorem, that the primes are infinite. and in, in, 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. It just means something just, nonsensical. of course, there exists pairs x and y. With x a prime, and y not a prime. And x less than y. So, to say it's not the case is, is, is, is clearly wrong. What does this say? for every x, there is a y. Such that 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, what that says as well, every number is a prime. That's false. Well, boy we, are we [INAUDIBLE] through these. These are, these are just plain false the, the, the absurdly false if you like. That was the one that was okay. What does this say? For every, there is an x so it's for all y what, whoops that says all numbers are prime again. For real that simple says all y's are prime. Well they're not. So that's also absolutely false, we will scratch that one, I mean I am scratching them because not only don't they actually say that, but they actually say something non, nonsensical, what do this one say, for all x there is a y actually [UNKNOWN] 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 one on the other hand does say there's no [INAUDIBLE] prime. Okay, let's move on to number four. Well, I won't go through these in, 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 y's that satisfy 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, the, 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 y's that could satisfy phi. The only one that does so is y equals x. So this actually captures, there is a unique x. So, we said 5x. And these 4. they're, they're not on. If you, if you try to figure out what they say. If they say anything vaguely sensible at all. They turn out to be just nonsensical and they certainly don't capture that. Incidently, this symbol is a moderately common symbol in mathematics. It's not something I made up for the exercise. The exists with the exclamation point does actually mean there is a unique x. You'll, 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 accurately define it in terms of the [INAUDIBLE] 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 observer that this symbol, I mean you do see this symbol sometimes in computer science, very rarely in mathematics except in a situation like this... Well 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, some operation which I'll call x upper arrow y, and we need to be able to express the fact that that's not communicative. 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, is ask ourselves which one of these means there its not commutative, well commutative lets write down what it means to be commutative, commutative means for all x and for all y, x power y equals y power x So that's what being commutated means. Which one of these negates that? Well, when you negate universal quantifiers, you get existential quantifiers. And things that are true become false. So the equality becomes an inequality. And so if you skip through these, you find, yep. Here it was c, that says there is an x, there is a y for which they're unequal. There is an x there is a y for which they're unequal. So that's certainly the negation. Do either, do any of the other ones fall in this as being a negation? Not really and probably not even close because when you negate both the foils become a [INAUDIBLE] They don't remain for all so it's not that one. they don't remain for all so it isn't for all the. So for a variety of reasons none of this 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'll see from students who are beginning to look at proofs. Because what this person has done. Is if identifying the key idea. This is absolutely the key mathematical idea behind this. the factor is that this, this is not prime. and if I'll look, what I'll do, let me just give you the proof that the person should have done. Okay, and then I'll, then I'll discuss why, why there's a problem with writing this down. Okay, so what the person should have done is, is something like the following, he began 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 that it doesn't take just 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, which should maybe prove this is, is true. Okay. We prove this this statement so we are proving the logically equivalent statement, okay so let N be a positive integer and I am doing this one in [UNKNOWN] detail because I am trying to get maximum points for this one, okay Then by basic algebra N squred 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. Okay 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 its a product of two positive integers each greater than 1, okay so that's what a person should have done, now lets go back to what was here this is the key algebraic heart of this thing already But it's not a proof. And the reason students often does 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, the algebraic manipulation right. if the algebraic manipulation is not right, you don't have a valid proof. But the proof is all about giving reasons and making a, giving an explanation. It's a story. A story with a beginning, a middle, and an end. you know, most, you know there's a, there's a, I mean there's a joke about a Woody Allen in the Woody Allen movie where Woody Allen, in the character Woody Allen character says, he's been reading a book it was "War and peace" and he summarizes 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, the full story. this one I think is going to be actually fairly difficult to grade. I'm going to put four for logical correctness here. Because, logically, this is the heart of it. Once you realize that that's the logical heart. So, that's, that's fine. Okay. clarity, I'm going to have to give a zero. just, 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. It just jumps straight in. let's see. Stating conclusion. Well the person did state the conclusion. So I'm going to give that, you have to give full marks. The conclusion is stated. that is, 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, that's just going to be a zero. and then, let's see. What have I got here. overall evaluation, zero. I mean, as, as a proof, I can't really give anything for that. Okay. Well I don't, let me think. you know, actually now I'm going to be a bit generous here. I'm going to give 2 for that I think. Because this is, this is key. I mean this, you, I've got, I'm going to give some credit for this. I mean I It is the key part of this. and it was the, the setting that was wrong. So I'm going to give 2 for that. So that means I go for a, I've got 10 for that one. yeah. A little bit generous, maybe, as a proof. the person certainly has the, 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 judgements, you're trying to sort of asses a whole bunch of different things. 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 go the general gist of how to do this. I mean all instructors differ about their own methods and I'm, I'm just giving you mine as an example but with something that is sort of essentially qualitative as as grading proofs, it's like grading essays. you know, people, people end up with different, you know, there were, there were stricter graders and less strict graders. my goal is always when I'm grading, at, at this kind of a context is to, is to, 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 point out the things that still need to be done. Okay alrighty, well that was the end of the problem set three.