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 6
Loading...
Из курса от партнера Stanford University
Introduction to Mathematical Thinking
1376 оценки
Из урока
Week 6
This week we complete our brief look at mathematical proofs
Познакомьтесь с преподавателями
Dr. Keith DevlinCo-founder and Executive Director
H-STAR institute
With Problem Set Six was all about whether we could recognize valid proofs
or not. And by a proof being valid, we mean more
than it's logical correct. Logical correctness is an important part
of being a proof but the other part is its communicative aspect.
Remember proofs are about two things. They're about establishing the truth of
something, and about providing reasons for the truth.
And to provide reasons, you have to lay it out in, in the proper way now.
How you actually express it i, is not that important.
I mean, high school teachers are very often follow this method that you
especially with proofs in geometry, that you write down statements in a left
column. And you write reasons in the right
column. Well that's fine.
It's, it's, they probably do that because they want to emphasize that there are two
parts to prove. There's a sort of logical correctness,
and they put that on the left side. And then there's the reasons that, that,
that, the rationales that make us understand on the right hand side.
but there's really no need for that. That's just, it's, they probably do that
for pedagogic reasons or for traditional reasons.
professional mathematicians almost never do that.
wha, what those of us in the business do, this will actually tell a story, because
that's what a proof is. It's a story, and like all stories it has
a beginning, it has a middle, and it has an end and the, the bit in the middle has
to lead from the beginning to the end. Now the beginning is usually a hypothesis
or an assumption or a statement of the method.
And the thing at the end is a conclusion when you sort of sign off and say, this
is what we set out to prove, we're done. and providing it tells a logical story,
and makes it clear why the various steps have been taken.
Then it's a valid proof. Okay?
So and, and when we're looking at proof, you have to look at it from two
perspectives. Is the logic correct?
And by the logic I mean maybe the arithmetic or the algebra, whatever we're
using. And is the structure correct, and how you
lay it out, is, is, is really up to you, so long as it's clear.
So, let's look at this one, first of all, from the point of view of telling a
story, does this. Tell a story.
Does it have a good beginning? Does it have a good middle?
The middle is usually the longest part. And does it have an end?
A conclusion. And the and if I, the rubric that I've
prepared for doing the peer reading of the the final exam, actually has specific
categories that cover these things. Okay so let's just look at this one.
Okay so we begin very well, we state the method, it's a standard method.
And if we're using a standard method it really is important to begin by saying
that. Because remember, if you're trying to
communicate something to a reader you need to help the reader.
Tell them what you're going to do, tell them why you're doing something.
Tell them why you have done something. You shouldn't leave it up to the reader
to try and figure out what you mean. That's not a good proof, that's actually
a challenge. It's a problem.
Someone should be able to read a proof and, and be convinced by what they read,
not by what they have to do themselves to, to fill in the big gaps you've left.
Okay its induction, so you begin by, by by looking at the first case.
In most examples, the first case is pretty trivial.
It's an obvious truth and, so that's, that's very, that's very rarely a
problem. so the next step is, so let's take them
off as we go through. We stay to the method, the method
requires the first steps, we've done that, you know, we check all the
correctness later on, but when you checking it, it'll, the, the, that
everything is there that needs to be. Induction means you then assume the
hypothesis, that you assume the result for stage n.
and then, then when you work through it, usually what you have to do is, is
actually explicitly say what the hypothesis is.
So, we write down, this is what we're assuming now within the course of the
induction proof. So, we've done that.
Then we do some algebra, this is the middle part of the story really where we
actually do some work, this is where you need some mathematical virtuosity.
we're using the induction hypothesis that we'll check later that we aren't using it
incorrectly. We state the reason for this last step,
we state the fact that it's the induction hypothesis.
That's a big deal, it's an induction proof.
You need to state when you're using the hypothesis.
There's only a couple of steps here, so it's fairly obvious when you're using it.
But many induction proofs are pages long so you need to sort of help the reader
with that. Little bit more algebra, then we've
observed that the, the inequalities have been established for N plus 1, so we say
that. This establishes the inequality for N
plus 1. so that's the end of the subplot.
In a, in a sense there's a big plot. That's by induction, then the subplot of
this story is you make an assumption and you reach a conclusion on the basis of
that assumption. So in here, from here to there, there's a
little subplot which has its own beginning, middle, and end.
This is a little proof within a proof. This is a proof that if you make that
assumption, you can conclude the, the corresponding result for n plus 1 in
place of n. So we've got a story within a story.
And when we're done, when we've completed the little story, then the big story gets
completed. Not automatically, it gets completed
because we pull upon a very powerful property, a very powerful principle.
An axiom, in some cases, if you want to regard it as an axiom, called the
Principle of the Axiom if Mathematical Induction.
this is a powerful piece of mathematics that says if you, if you can produce a
little plot like this, a little substory then that follows.
And the conclusion for the whole story. The one that began by saying we're trying
to prove that is that the inequality holds for all n.
So we've ticked off the reason, this is also a reason, it depends upon that
reason but this is a separate reason, this is a reason for the whole story
being correct and then we tick off the conclusion, OK?
So this proof has all of the right structural aspects Of telling a story
that explains what's going on. Okay, now let's check if we'd, we've got
it right. The tricky part is usually in here, this
is where people very often go wrong. So let's just make sure we've, we've got
this part right. what are we doing?
We're saying, we're trying to prove inequality of two to the N plus one,
we're trying to prove two to the n plus 1 is greater than 2 times n plus 1.
We're going to take this inequality and replace n by n plus 1 on both sides and
produce the, produce it. So we begin by the left hand side of the
thing we're trying to prove. We pull out one of the 2s.
Why? Because we want to somehow use that,
that, that fact there. Because we've assumed it here.
This is the induction hypothesis that we're, we're, we're going to use and so
we need to get the statement we're trying to prove in terms of n plus 1 in terms of
that. So we do it this way, and then we can say
the 2 gets carried over. The 2n is bigger than two times n by the
induction hnypothesis. Okay, so that's the key step there.
Induction hypothesis, we're given the reason.
Now we do a little bit more algebra. 2 times 2n is 4n.
4n is 2n plus 2n. Why did we do that?
Because we want to be able to get a 2 times n plus 1 out of it.
That of course, is is bigger than or equal to 2n plus, plus 2.
Because n itself is bigger than 1. So I might as well replace that by a 2,
and make it possibly smaller. And then I can have a 2n plus 2, and then
2n plus 2 equals 2 times n plus 1. Okay.
So, all of this is correct. Okay, and it establishes that this guy is
bigger than everything everything else is either an equal sign or a greater than or
equal to Two N plus one. Unfortunately, this is one of those cases
where, what's usually true to the obvious, isn't true, okay.
This, actually, is false, this is not the correct theorem.
which means the proof is certainly not valid, so this guy is false.
And the thing that went wrong wasn't the proof here.
It was the first step, because it's not true for n equals one.
It's false for n equals one. For n equals one, this is false.
In fact, it's also false for n equals two.
2 to the 1 is not bigger than 2. It equals 2.
2 to the 2 is not bigger than 2 times 2. They both equal 4.
However, 2 to the 3 is 8, which is bigger than 6.
And from then onwards, it remains, it remains valid.
So, this is actually false. Not because the mathematics went wrong,
but because we were careless. And we didn't check the initial step.
Okay, if you wanted to turn this into a valid theorem, you would have to insert
here a clause, n bigger than 2. You would have to say for any natural
number n, bigger than 2, 2n is bigger than, 2 to the n is bigger than 2n.
Then the proof would be fine. The first step would be n equals, 3, the
first val-, the first value for which the theorem is stated.
so in principle it's a correct result. and in principle this can be turned into
a, well, in practice, this can be turned into a direct proof.
But it doesn't hold for n equals 1 and n equals 2.
So technically, and technically it's a big deal because we said it was true for
all n and it's not. this guy is false, and the proof is, is,
is not, not valid. even though the, the mathematical
manipulation, in the middle was perfectly okay.
now, yeah, obviously this is an easy example, you probably spotted that right
away. I didn't bury this in, in a, in a massive
symbol so you, you over looked it, it was right up there to be seen and I'm sure
many of you spotted that. but I want to make a point with this.
This kind of mistake is actually pretty common.
You'd be amazed, well maybe you wouldn't be amazed but and I'm certainly not
amazed because I've been a mathematician for many years and I've seen this kind of
mistake many times and I've made it myself many times.
You're trying to prove something by induction, and I'll say, professional
mathematicians do this all the time. You've been thinking about it for a long
time. You come up with some really clever ideas
to prove the induction step. And all your focus is on this, because
this is the hard part. And in the course of doing that, you
maybe simplify the theorem, you make some changes.
And at some point, you lose the fact that the first case is true.
You know, you maybe began with a problem where it actually was true, and then you
changed it, you generalize it. All sorts of things.
But you're so focused on what you thought was the difficult part, and, and what had
been the difficult part, that you forget the fact that the first case is no longer
true. so it, it's actually go, there, there's
been a significant number of mathematicians, good mathematicians,
professional mathematicians, who've produced induction proofs where the first
stop wasn't as obviously true as they thought.
In fact it was false. not proofs as simple as this admittedly,
this was, it was just an example, but the point I want to make is do be careful
about first steps because professionals fall down on it all the time.
You've just got so much to hold in your mind when you're proving the theorems,
and when the proofs go on for several pages you start to lose details.
We all do. We're human.
We've got a limited mind, a finite mind and we can only hold so much in our minds
at the same time. So the answer to the question is, is a
proof valid or not? It's a clear no.
It's not valid. The best you can see is you can rephrase
the statements and make the proof correct, but as it stands it's not valid.
So much for that one. Well, now let's take a look at this one.
This is one from set theory, so, th-this may be a subject, that, many of you have
not seen at least not at an advanced level like this.
Okay, let's just follow it through, see what happens.
If a is a nonempty finite set x that has n elements, then x has exactly 2 to the
power n distinct subsets. Okay, and we'll do what we did in the
previous one. We'll first of all check if the structure
is correct. If this tells us a story, and there's
plenty of explanations. is there a beginning, a middle, and an
end? And is, is, are the explanations there?
standard methods. Se we still know what the method is, so
that's good. the case n plus 1 is true we know now to
be very careful to check that, that really is the case.
We'll come back in a minute and do that. Since if x is a set with exactly 1
element, say x equals a, then x has a 2, so here this, we've given reasons
explicit reasons We'll come back and check the exactness in a minute, as I
said. Okay, next step assume, so there's, you
know, we, we, we've done the first step. We've, we've said the method, we've done
the first step. Next one, assume the theorem is true for
n. Induction hypothesis.
Now we let a sti, we take, let x be a set with n plus 1 elements.
We assume we got a set with one more element.
What are we going to do? Pick something in this, and we'll come
back later and see what all of this is about.
Yada, yada, yada, yada, yada, yada. Then here's the thing we're looking for
next. So we're going to have to check the
accuracy of all of that. But the next thing is, establish in the
theorem for n plus 1. Then, by the principle of induction, it's
true for all n. So, yep this is a good story.
It, as a story this, this looks fine. It's got the right structure, beginning,
middle, end and there seems to be the reasons in there.
Okay, that's one part. The other part that we have to check is
whether it's logically correct. Okay, remember, validity means logically
valid. And communicatively valid, or
communicatively, communicatively effective, if you like.
Okay? Let's do the case n equals 1 is true.
Well, we are going to look at this carefully.
Since if x is a set with exactly one element, say x equals singleton a, then
there are just two subsets. There's the empty set, yup.
And this is at x itself because there are no more elements to go into a sub set.
So in this case, not only is, do we have this here but this is really correct.
So that's, we'll put a little smiley here because that's correct, okay.
Now we are going to have to check this bit.
So we'll take a set with n plus one elements, we pick one element of the set
and we throw it away. So Y is a set X with A thrown away.
Okay? So since we've thrown one element away,
the set we're left with Y has only N elements.
X with N plus one elements, we're throwing one away, so we're left with N
elements. Now we can apply the induction hypothesis
to Y because a set with N elements has two to the N subsets.
So we're going to list them. There's Y one all the way up through Y to
the two N, two to the power N. So those are the subsets of Y.
Now we ask ourselves What are the possible subsets of x?
Well all of these are subsets of x. And for each one of them, if we throw a
back into it, we get another subset of x. So we have the subsets of this, we have
all of the subsets of y, together with all of those subsets augmented by this
element here that we originally threw out.
And here I've made that explicit and I [INAUDIBLE] .
Well how many sets do we have in this list?
We've got two to the n in the first half and another two to the n in the second
half. The index here goes from one to two to
the n, as it does there. So there were two lots of two to the n
which is two to the n plus one sets in this list.
And that establishes it to n plus 1. So, so the logic is absolutely fine.
this line here, is arguably overkill. Because I've just, I've written it down
here, and now I've put it in words. but this what's, this is essentially an
audience design, this is an introductory class and so I'm assuming that many of
you have never seen this kind of thing before, and for beginners at, at
something you, you, you spell things out in detail.
If this was, you know an advanced undergraduate class or students who had
completed a course in set theory. I wouldn't have bothered writing that
part. I would have just left that out as being
superfluous. but since proofs are meant to communicate
the reason for something being true, it's important to put in the reasons when you
think they're going to be required for the reader.
So there's a large element of audience design in writing a proof.
that's just the way it is, in fact quite frankly a professional mathematician
would write the theorem and here's what the professional mathematician would say,
Proof: Trivial, by induction. That is probably all A mathematician
would write, by the way, mathematician is very like QED, but I, I mean that was
like, when I was in high school in my geometry class.
And I thought it was kind of clever then, and I still like it, in a strange bizarre
sort of way. It's fine to start off [INAUDIBLE] proof,
but in any case that's what a mathematician would say.
because when you've been doing this for many years, it is trivial, but now it
only works in the cloak of professional mathematicians, it's certainly not the
case that an undergraduate taking a course could get away with that, because,
It doesn't, it doesn't convince the professor that the student knows if it's
correct or not. something like this is fine, okay, in an
introductory class this is about right with or without that clause.
Okay I'm making heavy weather of this one just as I did in the previous one,
because I am trying to establish what's involved In, in, in making good proofs
and being able to understand proofs. Okie-dokie?
Right, let's go on to number 3. Well I'm not going to do this one in, in
full detail because we've we've essentially done it already.
We've already I mean the answer is true. Okay.
but that really wasn't what the issue was about.
it was very about being able to prove this.
well we're seeing it, proved, or we've proved it, one or the other.
For p equals 2, and for p equals 3. when we first met it for p equals 2 in
the, in the lecture, I talked about even and odd.
and then when we came to look at its, later on for p equals three, I, I,
observed that, we could have, that we could have cut the first proof in terms
of divisible by two or not divisible by two and then if you take the proof for p
equals two And replace even and odd by divisible by 2 and not divisible by 2.
You can replace that phrase by divisible by 3, and not divisible by 3 and get the
proof. So the proof here hinged upon, divisible
by 3. And that was a generalization from
divisible by 2. But you can actually take another step
and for an arbitrary prime p, you can replace divisible by three, divisible by
p. It wasn't the fact that it was two that
mattered, actually, it was the fact that two was a prime number.
It wasn't the fact that it was three that mattered It was the fact that three is a
prime number. If you look through the proof, the fact
that we use is that these guys if they divide a product, they divide the numbers
in the product. and so if it, if it only depended upon
the fact that two was prime and that three was prime, then it really only
depends upon the fact that it is a prime And so, you can just replace the whole
argument by divisible by P and it all goes through.
And so, it's the same argument as before, except for a general part.
And I think that's really all I need to all I need to say for this one.
This, this I think justifies we can, this actually, I mean, in terms of giving a
proof here's what I would say. The arguments, so here's how I would
express it. And if someone insisted that I write
something down, the argument used previously, for p equals 2, and p equals
3 generalizes immediately. That means there's really no extra effort
involved in doing it, to any prime P. That actually constitutes a proof.
In this context when we've done 2 and 3, that does constitute a proof.
Because it establishes a truth and it tells you why.
It's perfectly good. Proofs don't have to have lots of algebra
in them, lots of arithmetic. If it's a, if it's a sound reason based
upon previously established results, it's a proof.
A proof has to be logically correct and it has to convince the, the reader, that
it's true. That does.
I mean, its logical correctness was already established in the previous ones,
and we've referred back to that. Okay, now we're going to do number four.
Well for question four, we have to use the grading rubric.
and as you'll see this is going to involve some significant Qualative
judements. Even though we've separated out grading
into these these these six different criteria for each one of these we're
going to have to exercise judgement. So you're going to find this challenging
at first. In fact you'll find it challenging even
at the end of the course although hopefully you'll have more confidence
doing it. And in the process you'll have understood
more about mathematical proofs. But let's just press ahead and and see
what we've got here. Okay first of all we're going to look for
logical correctness. this is an argument that involves some
arithmetic and some algebra. So logical correctness is going to
involve both both the logic itself and the on the shoes of al-, arithmetic and
algebra. So, all of those have to be correct.
So let's take it step by step. the left hand side for n equals 1 is well
if n equals 1, there's just 1 term in this sum, and it's 1 over 1 times 2.
And the right hand side is 1 over 1 plus 1, which is 2.
So indeed, this is correct. Left hand side and the right hand side
are both a half. Okay?
assume the identity holds for n. What's going on here?
Well, we have to figure out what's going here, don't we?
I mean the author hasn't provided any explanation.
So when it comes to looking for reasons, I'm going to be a I'm going to be
critical at this point. In fact, what is going on is that the
author is taking the sum and separated out the final term.
You've got a sum from 1 to n plus 1, so we take the first n and leave them there
and we pull out the final term and put it out here.
Okay, so this is indeed correct. It's just taking a sum of n plus 1 terms.
I'm grouping it in terms of n terms and then the final terms.
So it's absolutely correct. what's going on here?
Well, again, because I've got lots of experience, I've, I've seen hundreds of
igduction, induction proofs in my life. recognize at once that the author simply
using the induction hypothesis, again that's going to be an issue for reasons.
But in terms of, of correctness, this guy does indeed equal this.
And that's just carried forward. what's going on here?
let's see. That's, so there's two terms.
First of all the, we're putting it over a common denominator.
So we have to take this and multiply numerator and denominator by n plus 2,
which is which is, gives us this part. And then we add that one onto it as well.
So there's actually two steps concatenated into one here.
There's expressing in terms of a common denominator, then combining them.
then we're just expanding that. Then we've used a binomial identity to
get from here to here. And then we've cancelled n plus 1 to get
from there to there. So all of these steps are correct, so the
the logic is correct. Okay.
So we get four max with that. What about clarity?
Well leaving aside reasons, I think this is perfectly clear.
Everything is expressed well, all s-, almost all the steps are unarguably, this
was two steps in one in going from here to here, you know if from this line to
this line there were two steps. It was expressing this one in terms of a
common denominator and then combining them.
But at this level of development, where we're looking at mathematical proofs in
number theory, I think we can assume that a reader of a proof can, can follow this
without without any real problems. so I think in terms of clarity we're
going to have to give four. This is, this is perfectly clear.
you know, absolute reasons. We're going to look at reasons
separately. But what about opening?
Well, there's an opening. It's, it's sort of standard method.
It's using induction. And the author begins by saying
induction. And then locally, in terms of doing the
induction there's a local opening here. So we're going to get four marks for the
for the opening. And here's our conclusion.
Yup, well there's actually two conclusions.
There's a sub-conclusion in, in, in the induction proof.
Assume for n, conclude it for n plus 1. And then there's a final conclusion at
the end. Okay.
So I'm going to have to give four marks for that one too.
now this is pretty generous already. For a proof that's in, that's quite a
challenge, because we had to, when we looked at this, we really had to sort of
figure out what was going on here. and let's just see what's really missing.
This identity here. There's no reason given for that.
It should've said something like separate out the final set.
That would have been fine. Okay.
What about this one. This identity here, oh dear, this is a
real problem. That should definitely have said by the
induction hypothesis. This is an induction proof.
You really should mention when you're using the induction hypothesis.
So that's a real problem for me. It should be a problem for you too.
this one. Not so much of a problem.
It would have been nice if the, if the person that said something like express
using a common denominator. That would have been nice.
for this one in here, if you want to put a reason, you could say by elementary
algebra because that really is algebra. What about from here to here?
Same, same. You could have just said by elementary
algebra. And for this one here, you could say
cancel n plus one. Okay.
I don't worry about this one, at this level as I said, wi-wi-with, with, with
looking at then proof, we're looking at proofs in, in number theory so heavens
above we can assume that the reader can follow this kind of steps.
So this isn't a big deal. this isn't a big deal.
This isn't a big deal. That's not a big deal.
This is a huge deal. This is an induction proof.
It's about proofs. It's about reasoning, and we're using one
of the most powerful techniques in mathematics, certainly number theory,
which is induction. So this is, these are big guns.
We need to mention that we're, we're using the heavy artillery here.
and this is significant as well. This is w-, the thing that sets it up.
yes, you could say that the reader could figure it out.
In fact, we could assume the reader figures almost everything out, given
time. But a proof isn't meant to be a challenge
in the sense of, you know, can, can you see what I'm thinking.
The proof is meant to be an explanation, saying, here is what I'm thinking.
Here is what's going on. So, in terms of a proof, this is pretty
hopeless. there just are not reasons given.
As I said, these are not important. These two really need to be, and this
one's absolutely critical, and I would say that this one is, is, is really
important. A, it's, it's the key to the proof
really. interestingly enough, up here reasons
were given, the left-hand side. This was very clear, I mean we took care
of, we give credit for the fact that this was easy to follow, in terms of clarity,
okay, don't have specific reasons, but it was so clear that you could follow the
reasoning. in this case, we had to think for a
minute, what's going on? Here we had to think for a minute, what's
going on? And you really shouldn't be doing it at
that, that, that level. these, yeah you have to think about it,
but I think it's, it's, it's, it's fairly transparent.
So, zero for reasons. Okay, there are just no reasons given
essentially. And two of them are critical reasons.
If the, if these reasons had been missing, but these two had been in, I
wouldn't have worried. I would have given four marks for
reasons. If this one had been in and maybe that
one was missing, I think I would have given them three.
So basically, I'm saying there's three for that one, and there's one for that
one. And they're both missing, and, and these
I don't care about. on the other hand, the overall picture of
this, is, is, is of, a complete lack of reasons.
By the way, with these proofs, what I've done is I've taken proofs that I've
given, I've, I've, I've returned from students over the years, and I've
condensed them so that they can fit onto a single slide.
Normally, this would have been taking a lot more space, but I condensed it and
kept the highlights just to emphasize various points.
So this is a sort of composite of proofs that I've seen over the time over the
years from different students. So these are the kind of things that crop
up all the time. Okay?
What about overall evaluation? [SOUND] I'm going to give this three.
You know, it's still a good proof. I mean it's a good proof.
I've given, you know, I, I've penalized for the reasons, and I think justifiably.
But overall, reasons aside, this is, this is a good proof, they also just needs to,
just needs to be a little bit more helpful towards the reader.
And, that means I've gotta total, aggregate grade of 19, which I think is,
is a fair grade. We've lost five marks, the students lost
five marks but I think justifiably, given the absence of the helping.
it was nice that, you, you know, listen, you could say this is sort of generous,
well, this was very nicely done in particular.
The author not only said he took well, but concluded it well.
You know, when you finished a proof and proofs remember have beginnings, middles
and ends, when you got to the end you know, it's like a performance.
You've told a story and, and if you go to the theater, at the end of the
performance. The cast comes to the front of the stage
and takes a bow, maybe the drums roll or something else, there's a clash of
cymbals or something, you know you've got there, you've achieved something.
Take your bow, so if you give a proof sign off and say that you've done it and,
and take the bow and get the audience's applause and
Okay. Well, hope you did well on that one.
Well how did you get on with question five?
this was a kind of cute little thing it just in many ways it, its very similar to
question two, that was explicitly set theoretical.
but this is a it's based on set theory but its expressed in, in, sort of
everyday terms. So let's just let's just see, I mean
obviously it's false, right? So the question is can you find out where
the mistake is? So, let's see, let us, let us, we're
going to follow this through, let's assemble the statements, in any group of
any Americans everyone, that's just a statement, that's the definition so
there's nothing wrong with that. We're going to prove s n by induction on
the n. Okay, since everyone in a group of one
American has the same age, s1 is true. That's true, that's okay.
Assume s n is true for some n, any n. Then prove s n plus 1.
so you pick an arbitrary group of n plus 1 Americans.
again, this is very similar, so to question two.
we show that everyone in G has the same age.
Okay? And to show that everyone has the same
age, its enough to show that any two members picked at random have the same
age. So we let two elements b and G okay.
let's see that's fine, we've got n is at least one.
So G is a group of at least two Americans, so we can find two Americans
in there, find two people in there and there definitely are two people in G.
we remove one of the elements from G, and then we're left with a set of n elements.
By the induction hypothesis, that's true. Ditto with taking b out.
That allows us to use the induction hypothesis, which is true here.
dear, dear me. Now let c be any person in G other than a
and b. How do I know there is going to be
another person? N is at least 2, n, n is at least 1,
right? N, n, is a natural number, so n is at
least 1. So the set G has at least 2 members, but
if n actually does equal 1, it only has two members.
So, this thing goes wrong right after the first step.
It doesn't work when you've got n equals 2, and in fact, that, that, that's where
the problem is. so here it's gone wrong.
There may not be a person other than a and b.
apart from that, everything's fine if you follow this through.
but this thing goes wrong because once you've got more than one American
involved the thing is false. Which, which intuitively of course is
obvious. Because if you pick a group of two
Americans, then the chances are that they don't have the same age.
So just by common sense, even when you pick a pair of Americans at random, the
chances are high that they don't have the same age.
So intuitively you might think that this has got to go along pretty quickly, it's
gotta go along once you've got more than one American.
but what goes here is buried, it stays 13 i, in a rather lengthy proof.
So, so the answer is it's false. of course we knew it was false.
But the answer to the question is, it's false because this is the step that goes
wrong. There may not be a person other than a
and b. Other than that, [LAUGH] yes, we're fine,
okay. you know, it's a, stating methods all
that kind of thing so if we're doing this rather rubic, it would go along on very,
very important technicality. Okay, how did you do in that one?
Well this was really just, just sort of for fun, but, a, but the focus, of
course, for, for all this problem set was on can you recognize proofs that has been
valid or invalid and can you assign a grade to a proof.
recognize it was valid or invalid is, is, is, is perhaps the easier of the two
assigning grades is tricky and that's what we're, what we're, why we're going
to be spending more time looking at how to grade examples.
Okay well there we go with Problem Set 6.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2019 Все права защищены.
