Learn how to think the way mathematicians do – a powerful cognitive process developed over thousands of years. Mathematical thinking is not the same as doing mathematics – at least not as mathematics is typically presented in our school system. School math typically focuses on learning procedures to solve highly stereotyped problems. Professional mathematicians think a certain way to solve real problems, problems that can arise from the everyday world, or from science, or from within mathematics itself. The key to success in school math is to learn to think inside-the-box. In contrast, a key feature of mathematical thinking is thinking outside-the-box – a valuable ability in today’s world. This course helps to develop that crucial way of thinking.
Tutorial for Problem Set 3
Loading...
您將學習的技能
Number Theory, Real Analysis, Mathematical Logic, Language
審閱
4.8（1,442 個評分）
- 5 stars1,215 ratings
- 4 stars188 ratings
- 3 stars24 ratings
- 2 stars3 ratings
- 1 star12 ratings
JJ
Apr 16, 2019
In the last lecture, based on what he previous taught, the professor give us the definition of limitation which is the beginning of the Calculus. I wish I taken this course before university.
HD
Jun 01, 2018
Great course about mathematical thinking, mathematical logic and proofs. I have a much better grasp on doing rigorous proofs after taking this course. Thanks for putting it together for us!
從本節課中
Week 3
This week we continue our analysis of language for use in mathematics. Remember, while the parts of language we are focusing have particular importance in mathematics, our main interest is in the analytic process itself: How do we formalize concepts from everyday life? Because the topics become more challenging, starting this week we have just one basic lecture cycle (Lecture -> Assignment -> Tutorial -> Problem Set -> Tutorial) each week. If you have not yet found one or more people to work with, please try to do so. It is so easy to misunderstand this material.
教學方
Dr. Keith Devlin
Co-founder and Executive Director
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.
