Tutorial for Problem Set 6

Loading...

En provenance du cours de Stanford University

Introduction to Mathematical Thinking

1060 notes

Stanford University

Introduction to Mathematical Thinking

1060 notes

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.

À partir de la leçon

Week 6

This week we complete our brief look at mathematical proofs

Tutorial for Assignment 816:08

Tutorial for Problem Set 636:28

Rencontrer les enseignants

Dr. Keith Devlin
Co-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.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play