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.