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.
