---
Video Title: Principle of Induction
Description: Theory of Computation
https://uvatoc.github.io

3.3: Principle of Induction

David Evans and Nathan Brunelle
University of Virginia
---

Induction is a concept that many people
find frightening.

And in some ways that's good.

Like it should be frightening because it
allows you to do very powerful things.

But it shouldn't be mysterious.

Depending on which version
of discrete math you took,

you should have all encountered
induction in some way.

Often not till pretty close to the end of
the class and maybe more as a procedure of

here's steps to follow, then here's why it
works.

So what I'm going to try to do is give you
an understanding of why induction works.

Because it doesn't always work.

It only works in really special cases.

The principle that induction builds on is
this.

If we have some subset
of the natural numbers, we'll

call it x, and it has to
satisfy two properties.

We've introduced all these weird ways of
writing the natural numbers from now on.

By default, I'm going to write them using
the common understanding and we're going

to think of the numbers the way you are
all.

People intuitively familiar with the
natural numbers before this class.

So hopefully you haven't
lost your nice simple intuition

about natural numbers
and sets and things like that.

We're going to use them
without going back to our

explicit definition, except
for when we need to.

And we actually still will need to at some
points.

So now it's a subset of the natural
numbers.

This is what the fancy n means.

And it satisfies two properties.

It contains zero.

And if it contains some n, it also
contains the successor event.

So this is actually using the first
definition.

You can also think of this as just n plus
one.

Sorry, I just told you I'm
going to stop using my wacky

notation about numbers
and this definition uses it.

If it contains n, it contains the
successor event.

If those two things are true, then that
set x must be the natural numbers.

I guess I should make... So
we haven't defined subset.

I hope you've seen subset before.

Subset is kind of a misleading term.

When we want to say not equal to,
it's a strict subset.

Subset means less than or equal to or the
same or less elements.

With the notation, it's more clear what
subset is.

We've introduced a bunch of stuff that
should bother you.

We're going to assume you have an
intuition about these things, but

definitely ask if I'm using
notations or symbols, but we're

not going to try to define
everything we use formally.

Because if we did that, we would not get
to the question that was asked about

infinite cardinales and things,
probably for the whole semester.

Hopefully, our intuitive
definitions are all

consistent and correct and
unambiguous from now on.

Okay.

So what is this?

I call this a principle.

Is this an axiom?

Is this logic?

Is it a theorem?

What is it?

I don't really know how to say it,
because logic seems like a Boolean sort of

thing, because it still has numbers in the
plus one sense.

Okay, yeah.

So I think if I did a slack poll,
and I won't do it now, I think that's

probably the answer
that would get the

plurality, is that it's
some kind of logical use.

You learn proof by contradiction.

You learn proof by induction.

You learn all these proof methods that are
kind of logical tricks.

And it can be, but what makes it a theorem
is, this is something we can prove,

right?

This isn't something that we have to
accept.

This is something that we can actually
prove.

And once we've proven it, we can use it as
logic as a way of constructing proofs.

But this is something we can prove.

How can we prove this?

Any ideas?

What would be a good strategy for proving
a statement like this?

Yes, yeah.

Can you do a proof by
contradiction where you

assume that some natural
number isn't in the set?

Excellent.

And then you work backwards
to reach those assumptions,

and get out of the
bench, and we get to zero.

Excellent.

Any time we're trying to prove something
about everything, the strategy of looking

for a contradiction is not always going to
work, but it's a good one to think of.

Because to get a
contradiction for something that

is a proof about all,
this is for any subset.

We can get a contradiction if we can find
one that it's not true for.

If we're trying to prove a
for all kind of thing, to get a

contradiction we just have to
find one case where it's not true.

Let's assume to get a contradiction that
it's not true.

This is n.

If it's not the case that x equals n,
then there's some set y of the elements of

the natural numbers that this is not true
for.

If this doesn't hold, y is non-empty.

So that means we're going to have the set
y, which is the natural numbers minus x.

All the ones that it's not true for.

We're going to assume, to try to get a
contradiction, that y is non-empty.

This is like subtraction.

Sometimes people use the slash instead of
subtract.

It's basically one set minus all the
elements of the other set.

All of the elements of the natural numbers
that are not in x.

We're going to assume that y is non-empty.

What does that mean about y, if it's not
empty?

It has at least one element.

We actually need even better than that.

Because if we just said it has one element
and we're going to pick one, well,

the fact that the one we picked doesn't
have the proper meaning doesn't help us.

Because maybe we picked the wrong one.

We need to pick a special element.

If we're going to pick
one element to try to

get a contradiction,
which one should we pick?

Yeah.

The smallest one?

Yeah.

And this is actually a subtlety that we're
assuming there is a smallest element.

For this set there is, because it's
well-ordered.

Not all sets have a smallest element.

If we don't know there's a smallest
element, we would have a problem there.

But for a set of natural numbers,
intuitively, you should be pretty

convinced that there is a smallest
element.

We're not going to prove that the natural
numbers are well-ordered now.

But we're going to assume that they are.

And it has some smallest element.

And we'll call that z.

What do we know about z?

So we know z is not zero.

Because zero is an x.

So what must z be?

It's not zero.

And it's a natural number.

Okay.

Yeah.

It must be the successor of something.

There are only two ways to make a natural
number.

Every natural number is either zero or the
successor of some other natural number.

So that means this one we picked must
either be zero.

But it's not zero.

Because of rule one here.

Zero is an x, so zero cannot be y.

Which means z is the successor of some
other element.

What should be the case about that other
element?

By this rule, if p is in x, what do we
know about the successor of p?

It is also in x.

That means p must not be in x.

If p was in x, then z was in x.

But we said z was an element of y,
which is the elements not in x.

If p is not in x, well, p should have been
in y.

But if p was in y and z is its successor,
well, p is smaller than z.

Of course, we didn't define smaller.

But intuitively, I hope you get the...

Like, the successor is bigger than the
thing that it's succeeding.

So that means p should have been in y,
but p is less than z.

So we have our contradiction.

We started with this assumption that y is
not empty.

And we used the definition
of the natural numbers

and the two properties
here to get a contradiction.

So that means our assumption is false.

And our assumption was y is not empty.

Well, if y is not empty is false,
that means y is empty.

And if y is empty, then x equals n.

Those are the same sets.

What we've proven is now that any subset
of the natural numbers that satisfies

these properties is actually all the
natural numbers.

Is this enough to prove induction?

To do proof by induction?

What do we need to do to get from here to
the way you use proof by induction?

Well, we have one more little step.

This principle that we've stated here, this
applies to any subset of natural numbers.

We can define the subset x any way we
want.

So this is going to be
the predicate that we're

trying to prove applies to
all of the natural numbers.

If we can show these two properties,
this is usually our base case,

and we can show the
inductive case, then we've

shown it holds for all
the natural numbers.

So that's all that's going on here.

There's no change in logic, there's
nothing that we have to invent.

All we need to do is prove this theorem,
and now we need to pick the right subset,

and we can do proofs by induction.

Reformation.

That's right.