0:00

Well for question one on problem set four, we have to choose which one of the

Â following is equivalent to to this expression.

Â Okay, we're negating a universally quantified statement in which there's

Â conditional. And we're told that there's only one of

Â these, one of these answers is correct. The correct answer, let me just jump to

Â the correct answer and then see what's wrong with some of the others.

Â Is, is part C, the notforall becomes an exist and the negation goes into this

Â part. When you negate a conditional, you end up

Â with the antecedent together with the negation of the consequent.

Â And when you negate the disjunction, the negations filter in, and the disjunction

Â becomes a conjunction. So if you follow the rules about, well

Â they're not rules, they're, but they sort of our rules.

Â But I, I recommend you not to think of them in terms of rules because that's,

Â that's not really getting at what this course is about.

Â but there's certainly patterns of activity that you can get to get to

Â recognize, and then what happens is universals become exists.

Â You have the truth of the antecedence, in place of an implication, of a conditional

Â you have a conjunction. And then when you negate these guys the

Â negation applies to each one and that becomes a conjunction.

Â Okay, but that, but as I used to indicate or I just referred to, really what I want

Â you to do is concentrate always on why it is that you get a behavior.

Â Why does this give you px and not that. Why does negating this give you a

Â conjunction there, so it's all about understanding.

Â and if you, if you simply learn to apply the rules, you really don't have a useful

Â skill, okay? Computers are good at applying rules.

Â That's what they do, that's all they can do.

Â People can go much beyond that. Okay, what's wrong with some of the

Â others. Well, the first one is just hopeless.

Â I mean, there's just nothing remotely like that.

Â If you got that as your answer, then either you were having either a temporary

Â aberration, or you really, really, really haven't got the issue with this.

Â The others, there were reasons why people could go wrong.

Â And the others were put in, because there were mistakes that people frequently

Â make. Okay, in the case of this one, the

Â negation is in the wrong place. when you negate a conditional, the

Â negation doesn't come together with this one.

Â The negation should come inference of here and inference of there.

Â So it's just ,um,mixing up where the negation comes in.

Â Okay, but, otherwise, zero place. So, so it's like applying your bis,

Â you're applying the right sort of, let me call it rule, you're doing the right

Â thing but you're, you're, you've got one step out.

Â It's like getting a negative sign, a minus sign in the wrong place in an

Â equation. looking at this one, well everything went

Â fine except you forgot to change disjunction to conjunction, but

Â everything else was fine. And in the case of this one, you forgot

Â to, then that should be conjunction, and everything else was fine.

Â Okay, so in cases b, d, and e, there was just one thing wrong.

Â It's even possible you just did that by a slip.

Â I mean, heaven only knows you've seen me make slips often enough in the, in the

Â lectures and the tutorials where I write the wrong thing down or I whatever.

Â It's uhh, you have to keep a lot in our minds when we're doing these things.

Â And frequently what a hand does isn't what we're thinking it's doing and

Â sometimes what we say, isn't what we think we're doing.

Â Mathematics is like that, when you're really focusing on the mathematical

Â concepts, in the heart of it. You can make slips with the writing and

Â with the wedge you. I do it all the time, and we all do.

Â That's, that's just part of thinking mathematics.

Â It takes a lot of concentration to focus on the mathematics.

Â And the, the every day things like writing and using words, tend to miss out

Â on that because our mind is focused on the content.

Â 5:00

for every player there is another player they beat all the time.

Â That's not quite the same. If there was a for all there, for all t,

Â then whenever they play p would beat that person, that person q.

Â So that's, that's not quite, you would need a different quantifier.

Â That's just some game. If there was a, for all there you would

Â have it in all the games. There is a player who loses every game.

Â No, no that's all about losing. So hopefully, well, actually, while,

Â while we're on this, what would this look like?

Â if I wanted to put that in a formula, I would start with the following.

Â I would say, there is a q, such that for all p, and for all t, W, p, q, t.

Â In a minute I'll say why I said start with.

Â Because I was looking ahead to what would be wrong with this.

Â But, let's just read it, it says, there is a player, such that for all players

Â and for all times, p beats q in that game.

Â So it sort of says the player loses every game.

Â The problem is, when you take for all p here, one of the p's that are going to

Â pop up is q, him or herself, and a player can't beat himself.

Â So this doesn't quite work. Because the p could include the q itself.

Â In fact one of the p's will be the q, okay?

Â And it's also, well it depends this is, that players going to, yeah, I think that

Â would be okay. No, you've got to be a little bit careful

Â actually. It depends how you interpret the thing.

Â for all t, t just goes over games of tennis.

Â 6:48

Whereas we're just talking about games of tennis in which people, people win.

Â So you, you, you'd have to sort of think about it and decide whether you need to

Â put clauses in here, to make it clear that you're only looking a t's where they

Â play together. There'll be similar issue here.

Â Again, you could start with, if you wanted to do this one, you would start

Â with saying there isn't a p, let's see, for all q, for all t, w, p, q, t.

Â The only difference is here we had qp and here we've got pq.

Â But you'd have the same issue., among the qs is a possible p.

Â And you'd have to be careful to take account of the fact that the t itself

Â ranges over all possible games. And you only want to be making a

Â statement about the games that we did play together.

Â and you could have, amend this, you could put clauses in.

Â There are various ways out of that. if I thought this was a big deal I'd have

Â thought about it before I started to record this little piece.

Â But, I think we've, we've solved the problem in any case.

Â That one came up the first time, that was the one that that has that meaning.

Â None of the others do, so put those as no's, and we've solved that one, okay?

Â Let's go on to number three. Now normally when I'm going through

Â examples in classes, I don't make deliberate mistakes.

Â I don't need to because I make plenty of real mistakes, when I'm going through

Â mathematics in any case. But this time, I'm going to make a

Â deliberate mistake and I'm going to do it to emphasize the issue that's going to

Â come up here. Okay, so what I'm going to do is go

Â through these three and give you answers to all of them.

Â but one of them's actually going to be a wrong answer, and then we'll correct it.

Â So this one, actually if you remember the previous question, this is the one that

Â we saw. That means everyone wins the game, okay?

Â For all the players p, there's a player q and a time t to a p beats q and that

Â time. What does this say, everyone beats, well

Â it's almost the same, right? Except instead of playing every player

Â beats one player, you say everyone beats everyone else, at some time, in some

Â game. Okay, because it's all, it's all pairs of

Â p and q. And this one, it's essentially well,

Â actually, what's the difference? That one is for all p, there exists a q.

Â This one is for all q, there exists a p. So, this isn't, doesn't say everyone wins

Â a game. This one says, everyone loses again,

Â okay? Seem plausible?

Â Well, one of these is actually is actually not possibly true.

Â Let's just see. Could that be true?

Â We, we're talking about, whoops, there's a typo there.

Â That should be possibly. Okay, let's correct the typo.

Â I got it right up there. Okay, let's see which one cannot possibly

Â be true. Okay, that's what the issue is here.

Â Well, that could possibly be true. Okay, that's okay.

Â That could be true, everyone beats everyone else all the time.

Â Not sometime. Well, everyone loses a game.

Â Well, that's certainly possible, that's okay.

Â Coming to this one, can this, is it possible for this to be true?

Â It's certainly possible for that to be true.

Â 11:26

Because the problem is, no player, can beat herself, or himself, whichever you

Â want, okay? No player can beat herself.

Â So that can't possibly be true. So this is the guy, that can't possibly

Â be true. And it can't possibly be true because the

Â q and the p have to be equal. What you would have to say if you wanted

Â to make that something that could be true, was you'd have to say, if for all

Â p, for all q. if p and q are different then there is a

Â t so it should w, p, q, t, then you'd be okay.

Â Because you'd say for all pairs p and q providing they're different.

Â Then at some time, at some game, p does beat q in that game, so that would be a

Â way of making it possible. But as it stands, that's cannot possibly

Â be true because players cannot beat themselves.

Â Okay, so the issue was whether you can take the formulas and correctly tie them

Â into what they say about the real world. It wasn't mathematics that was deciding

Â these, it was the real world. And in the real world, players cannot

Â beat themselves. Well, actually, in a figurative way,

Â players beat themselves all the time. But in the sense we're talking about

Â here, that's not the case. Okay, now let's move on to question four.

Â 13:03

Okay, now this expression is, is, is a colloquial expression.

Â And so, when I set this question up, I, I realize that for non native speaking

Â English students this would be a, this would be somewhat challenging.

Â So what I did is I only gave you options that you should be able to distinguish

Â between, by, by doing the logical structure.

Â the reason I like to give these kind of examples is because they capture an awful

Â lot of social and cultural knowledge and, and there's an interesting challenge.

Â In capturing that kind of thing in, in formalisms.

Â but to help you along, I, I gave you three options, that you should be able to

Â sort out just on the basis of logic. If you know what, what being a lover

Â means in this case. So being a lover means you're in a mutual

Â relationship which means you've got, you love someone and that person loves you.

Â 13:59

But if you look at this one this says for this person x, so these are all about

Â person x, they all talk about some person x.

Â This doesn't say that person's a lover, this part says that person is in a love,

Â in a relationship with everybody else. So this part, because it's a universal

Â quantifier, that says L love, x loves z and z loves x.

Â So, this person x is in a loving relationship with everybody.

Â But, well that's nonsensical, so we can forget that one.

Â So, it comes down to these two. Because in each of these, it says the

Â person is in a loving relationship. X is in a relationship with some z and

Â it's mutual. X loves z and z loves x.

Â The same clause here. So the choice is between a and c.

Â Well let's look at what a, what a says. That says, for all x and for all y, if

Â 15:01

Now the y doesn't come in here so the, the for all y has to do with this part.

Â So it says take any person x, if that person is, is a lover, then every person

Â loves them, if they know them, so that actually is the correct one.

Â Okay, all people love a lover, of these three, that's the, that's the one.

Â You know, you could argue about whether that's the absolute best interpretation,

Â but out of these three it's certainly a correct one.

Â And so it's, it's the one here, let's look at this one.

Â This one is is, is a little bit different, because it's got for all y in

Â here. So, it says for all x, if x is a lover,

Â then it doesn't say then, it says and for all y, L, y, x.

Â 15:56

So the for all actually applies to this part as well.

Â So what this really, what follows from this is that for all x and for all y, L,

Â y, x. In other words, everybody loves

Â everybody. Well that's not the case, because this

Â isn't conditional on being a lover. This just really says that's the case and

Â that's the case. So part of this is saying that for all x

Â and for all y, L, y, x. Oh, that's not the case, I mean it's not

Â the case that everybody loves everybody. The world would be a nice place I guess

Â if that was true, but it's not true. So it can't be that one.

Â So we can, we've eliminated this one, because it's, it doesn't capture, it

Â doesn't use the fact that, being a lover. And we've eliminated this one.

Â Because it basically just boils down to saying everybody loves everybody.

Â And that leaves this one. And, and this is definitely one, one good

Â interpretation of everybody loves a lover.

Â Okay, so we, we will be able to reason that one out, and I would hope that even

Â without the detailed understanding of what this means in English.

Â there's only one of these that will stand up to analysis, and after all the idea is

Â to sort of look at how the formulas capture relationships from the real

Â world. Well for question five, we have to find

Â which statements are false. Okay, so let's just see what they say.

Â for all x, for all y, for all z, if x is less than or equal to y and y is less

Â than or equal to z, then x is less than or equal to z.

Â That's true. It's actually known as the transitivity

Â of the of the order relationship. If x is to the left of y, and y is to the

Â left of z, then x is to the left of z. Okay, so, that one's true.

Â What does this one say. For all x, for all y, if x is less than

Â or equal to y and y is less than or equal to x, then x is equal to.

Â Well, it is true, okay? the only way you can have x is less than

Â or equal to y or y is less than or equal to x is that they're actually equal.

Â What about part c? For all x is equal to y, [SOUND].

Â Well, that's certainly the case, because given the x, you can take y equals x and

Â then you have x less than or equal to y and y is, so that one was true.

Â It's beginning to look like they're all true.

Â Let's look at the last part. there is an x such that for all y, y is

Â less than x or x is less than y. Well you might be tempted to say, yup,

Â given any x it's the case that every [UNKNOWN] y is either less than x or

Â bigger than x. But wait a minute, among the y's,

Â governed by a universal quantifier is the x you start with.

Â So if there was an x with that property, how could this happen?

Â Because when you look at all the y's, among those y's would be x itself.

Â So you would have x less than x, which is impossible, so that one's false.

Â 19:01

And it's false because the universal quantifier includes the x itself.

Â Given an x, any x that you find you, when you universally quantify over y's, you

Â include that x, and then that fails, and that fails.

Â So there's the one that's false. And there is a false one.

Â And it, it fails because universal quantifiers go over everything.

Â And that means the, the, the, the y will, among the y's you will be looking at, is

Â the x that you start with, okay? Well for the last question on problem set

Â four, which is question six, we have to look at this piece of reasoning that a

Â student gave. This is actually when I first gave this

Â course in the Fall of 2012 and a student was trying to understand the, Euclid's

Â proof that the prime numbers are infinite in number.

Â And there was a key step where you from that product and you add one.

Â And a student wanted to verify that in fact N plus 1 was not divisible by p.

Â And came up with this argument. So I thought this would be a good one to

Â look at. It raises a number of interesting issues.

Â So, first of all let's just see what a student does.

Â Suppose N is divisible by p. Well, arguably the student, you could say

Â the student doesn't begin by saying what N is, and doesn't say what p is.

Â But in this context there's no need to. It, it's already been stated that N is an

Â integer. It doesn't matter whether it's positive

Â or negative by the way. And it's already said that p is a prime.

Â So I'll just, in this context, I don't think there's any need to demand that the

Â student repeat it here. What's key is that the student is, is, is

Â writing down the assumption on which the argument is going to be based.

Â Okay, so I'm going to say that the, oh I'll come to the various other issues in

Â a minute, the opening I think is fine. Okay, that's good.

Â What does the student do then? then as an integer q to the a equals pq.

Â Yes, that's the definition of divisibility.

Â I'm not going to demand that the student spells it out because it's, it's fairly

Â clear what's going on. So N plus 1 is P [INAUDIBLE], that's

Â okay. Then dividing through by by q by p,

Â you're going to have N plus one over p. Now the student's now written a lower

Â case q there and that's obviously meant to be an upper case q, I'm not going to

Â worry about that. That's just a typo in writing it, ditto

Â here. so I'm not going to deduct anything for

Â that those are just typos. I'm just using the wrong lowercase and

Â uppercase confusion, so NH is not divisible by p.

Â Okay, logical correctness. But in a sense this is okay, right?

Â I mean there's everything steps fine and the arithmetic's true.

Â So, I'm going to give 3, why aren't I giving four?

Â I'll, I'll come to that in a minute. What about clarity?

Â I'm going to give 4. This is absolutely clear what's going on.

Â State the conclusion, yep. Conclusion stated, that's 4 for that one,

Â 22:21

a reasons given, absolutely reasons are given.

Â yeah I'm going to sort of observe at the time the student sort of doesn't say,

Â this is by definition of divisibility, and so forth.

Â But you know, there's a limit to how much you can write down within the context of

Â this class, and the intended audience, which is the students in this class.

Â Then this is fine you know, it's fine, so we put more details in the reasons if

Â you, if you want to weigh on the side of caution.

Â But given the fact this is absolutely clear I think there's enough reasons

Â given, okay. And that brings me to the overall

Â evaluation. And this is where I'm going to put a zero

Â down. And this is also why I didn't give a full

Â four for this, because this is logically correct in terms of doing mathematics,

Â but this is an argument about integers. And the integers is a number system in

Â which you can add, subtract, and multiply.

Â What you can't do, is divide. Division is not an operation on the

Â integers. It's an operation on the natural, on the

Â rational numbers and on the real numbers. But, it's not an operation on the

Â integers. So, in, in going into the equation.

Â 23:54

But as I've said before I'm looking for reasons to give people marks, not to take

Â them away. We're trying to make people better

Â thinkers, not to make them feel bad about themselves, okay, so I'm going to give

Â credit where it's due. But strictly speaking it's not right.

Â Here's what the student should have done, okay, so we've got the first park we've

Â written N=PQ. Okay, that was okay.

Â Okay, now what I'm going to do is I'm going to argue by contradiction.

Â I'm going to say suppose N plus 1 were divisible by P.

Â Then, there is an integer called R such that N plus 1 equals PR.

Â Then, we have N plus 1 minus N, equals PR minus PQ, which is P into R minus Q.

Â But N plus 1 minus N is 1. So what I've shown is that P times R

Â minus 1 equals 1. That means that P, no, that means that 1,

Â is divisible by P. But, that's a contradiction, P is a prime

Â number. So, it's at least equal to 2.

Â So, it can't divide into 1. One isn't divisbly by any, by two or

Â three or anything so there's a contridiction.

Â Hence, the original assumption here was false.

Â Hence N plus 1 is not divisible by P. Notice that this is almost the same, in a

Â sense this is equivalent to this. It's not the same as this, but it's

Â equivalent, because the, the R here, is N plus 1 over P.

Â So this is the R. So I've said, and I'm sort of doing the

Â same thing except here, I'm not using division.

Â I'm doing everything in terms of divisibility, which means I'm doing it in

Â terms of addition, subtraction and multiplication.

Â All I'm using here is addition, subtraction and multiplication.

Â I'm not using division. I'm getting around it, by introducing

Â this R, if you like. And that's a significant difference,

Â because we simply don't have division as an operation in the integers.

Â We have divisibility, which is a property that may or may not hold between two, two

Â integers. But we can't divide one integer by

Â another because, division's not an operation in the integers.

Â Okay, so I, I gave a reasonable amount of credit for this.

Â I think I was generous with this one because I tend to be generous.

Â And that means the total grade is 19, okay?

Â