---
Video Title: Constructing the Natural Numbers
Description: Theory of Computation
https://uvatoc.github.io

2.3: Constructing the Natural Numbers
- Constructive Definitions
- Defining the Natural Numbers: Zero and the Successor Function
- Peano's Axioms

David Evans and Nathan Brunelle
University of Virginia
---

So if we're going to find
something new, we've

got to start with something
simple and build up.

So let's start with something simple.

So we're going to try to
define the natural numbers,

and we're going to start
with just some notation.

Here I've made the
assumption that we want

to include zero, but
zero is just a symbol.

Whether this means
what we think of as zero

or not, we haven't
given it any meaning yet.

And we're going to have a function called
successor.

So do we have enough, if we accept those
two things, to define the natural numbers?

What is a successor?

So far we've just said it's a function.

It's something that we can use in building
our natural numbers.

We haven't given it any
meaning yet, but it's going

to acquire some meaning
based on how we use it.

So we can use it
however we want in this

definition to try to give
it some useful meaning.

If you think of the intuition,
what a successor is, a useful thing to

think of as successor would be the next
natural number.

Which a natural way to think of next is
adding one.

Right?

So the successor to one would be two.

But we haven't given it any meaning yet.

Right?

We've just made up a notation.

So now we want to try to define what the
natural numbers are.

So, do we have a starting point?

Do we have any natural numbers already?

Zero.

Zero is a natural number.

That's the reason we had that symbol.

Congratulations to the, what, 17% that
said zero.

At least for this definition, you are
correct.

We've got one.

How many do we want?

All of the infinite numbers.

Yeah.

We want an infinite number.

So we're not going to do it by just
listing them.

Even if the MCS book definition suggested
that's a good way to do it.

And we don't want to use something like
dot dot dot.

And we don't want to make up any new
notation.

Your numerals are just notation.

How can we make more?

Okay, yeah.

We've got to find some way, if we have a
natural number, to build a new one.

So that's what we're going to use our
successor function for.

We're going to say, if we have something
that's already a natural number...

And here we can introduce notation.

So we're going to use n, just because it's
a nice notation.

We're going to say, if n is a natural
number...

How do we make a new one?

S of n.

Yeah.

S of n... And we can
pick some notation.

I'm going to write it
kind of like a function,

because that's a
good way to think of it.

But that's just a notation.

That's saying, if n is a natural number,
we've got this magic symbol s.

And we can put that around n, and that
also produces a natural number.

And it produces a new one.

There's a lot we haven't yet defined,
right?

So we haven't defined anything that tells
us how to tell if two numbers are equal,

or what adding means, or what it means to
be prime.

There's lots of important properties and
natural numbers we don't have yet.

But can we make as many natural numbers as
we need with just these two rules?

That's it, how do we make three?

S of n.

OK.

Well, we don't have two yet.

If we're gonna make three, we got to make
two first.

We only have zero, so what are we gonna
do?

So you're gonna have to make one first
apart.

Ok.

Yeah.

Right.

So we can make three.

We're gonna make, starting from zero,
we're gonna make it successor.

This is a number most of us would think of
as one.

One's just a notation.

There are lots of other
ways we could capture the

property of the successor
of zero, we call it.

And we've got to make two, so that's the
successor of the successor of zero.

And making two, we're using that second
rule.

Actually, we already used the second rule.

Our rule one, this is our rule two.

We use rule one here, because we know zero
is a natural number.

And then we use rule two that said,
if something is a natural number,

so is its successor.

So that was using rule two.

And we're going to use rule two again,
where now n is one to make two.

And then we're going to
use rule two one more time to

make a number that we
could use to represent three.

And we can keep going.

This is not the most efficient
way to write down numbers,

but is really the essence of
what the natural numbers are.

They're defined based on,
we've got a way to find for

any number, its successor
is also a natural number.

And we've given successors sort of
intuitive meaning, the way we're using it.

But there's nothing intrinsic about it.

So this way of thinking about the natural
numbers, the terminology here.

So you've hopefully seen recursive
definitions, at least in discrete math.

And you've probably written recursive
programs, which are in many ways like

recursive definitions, in some ways quite
different.

We need a base case, right?

This is why it's not a circular
definition.

We're not defining a natural number as a
natural number.

We're defining a natural number in terms
of our base case, zero is a natural number.

And in our inductive case, there's an
important if there, right?

We're saying if something's a natural
number, here's how to make a new one.

It doesn't depend on already understanding
a natural number.

It shows us how to build new ones.

So this is a constructive definition.

There are a lot of really nice things
about constructive definitions.

So it is precise.

It tells us we're
defining the set of natural

numbers as everything we
can make using those rules.

If we understand those rules, we can
answer exactly the question of,

given some thing, yes or no, is this a
natural number?

If we can construct it with these rules,
the answer is yes.

If we can't, the answer is no.

Yes, question?

Could you explain, is successor limited to
integers or natural numbers, or is the

successor in term we'll see other
variables?

So the way I've defined
successor here, it is

only defined in this
use on natural numbers.

The n that's in the successor here is a
natural number.

We could define other kinds of successors
for other kinds of objects.

And we could define a successor function.

There's nothing magic about this.

This is really just giving it a name that
gives us an intuition about what it is

that corresponds to how we use it for
defining natural numbers.

But it's just a function.

It's really just a notation here.

But we're using it, you could think of
implementing it as a function as well.

Yeah, question?

So what does add mean?

We haven't defined add yet.

So our intuition is addition should make
sense in this world, right?

Because natural numbers, we know what
addition is.

But the question of, are
we adding one or does it,

if you add two natural
numbers, do you get the sum?

We haven't defined what addition is yet.

We certainly could.

For this to be a good definition of
natural numbers that matches what we've

learned about numbers since we were three
years old or earlier, we would like

addition to behave in a way
that maps these meanings

to the meanings that we
get when we use addition.

But so far we haven't defined addition.

So it's not clear whether addition works
or not.

Our goal would be to find a way to define
addition that works with this.

And maybe we'll have time to do that in a
future class.

Probably not today.

So when you say it
doesn't map to your notion

of a number, in what
sense does it not map?

Or what aspects of it don't map to your
notion of a number?

Well, the only number I see up there is
zero.

So we haven't provided notation.

But there are lots of notations for
numbers, right?

The concept of a number is what you can do
with it.

You know, this is not the way you would
write three.

But, you know, you could also write three
like this.

There are lots of ways
someone could get the concept

of three across that
also would be unfamiliar.

I think I know Chinese.

I hope this is right.

Is that Chinese for three?

So that you might guess is three.

And that's why I can write, but there are
lots of different notation systems that

would write down the concept of three in
different ways.

Whether this behaves like our concept of
three, so far it's the successor to two,

and its successor is something we could
call four.

So that sounds a lot like
three, without defining things

like addition or equality,
which we haven't even defined.

We haven't seen enough to say it behaves
in all the ways we accept three to behave.

But I don't think we've seen anything that
says it doesn't behave like three.

Ah, oh, good question.

Are we defining cardinal or ordinal
numbers here?

Well, so we're defining natural numbers,
right?

That was our goal.

They have more of a sense
of cardinal numbers, although

using the natural for
ordering is also very natural.

We could certainly use these as
cardinalities, right?

We could use these to measure quantities.

We could also use them for ordering,
right?

We definitely have a well-defined order
here.

The more successors you are, the later in
the order you are, right?

So these concepts of ordinal and cardinal
numbers are definitely very well connected.

And so far, what we've defined really
could be used for either.

The one thing I would say, because we
started with zero, it has a bit more of a

flavor of cardinal numbers than ordinal
numbers.

If we started with one, it would have more
of a flavor of ordinal numbers.

But that's just an arbitrary symbol,
right?

I could have used
something... I could have used

a smiley emoji or something
else instead of zero.

Actually, that still looks like a zero.

Something I can draw... I was going to
draw an apple.

That also looks like a zero.

Something I can draw that doesn't look
like either a house, a zero, or a one.

We can use any symbol we want for zero.

We're assigning it meaning, and I'm giving
it a name that makes it natural to us,

but there's nothing special about this
yet.

Zero only becomes special once we define
addition and multiplication.

Then zero starts to have...

Well, it has special meaning here because
it's our base case.

If we defined addition in a particular
way, zero could behave like one.

We haven't done anything
that says zero behaves

in the way we expect
zero to behave yet.

So this is a recursive definition,
but it's not circular.

It's building on from the base case,
not assuming we're already known.

So this way of defining the natural
numbers is actually a bit over a hundred

years old, which in some sense is very
recent, given that we have been using

counting numbers for thousands or tens of
thousands of years.

People didn't really think about how to
define them until piano in the late 1800s,

and he came up with this definition, which
is very similar to what I've shown you.

It's a little hard to read because it's in
Latin, but he's got his base case,

and he's got his successor function.

This is, if a is a natural number,
then a plus one is.

So his successor function actually looks a
little more natural to you.

It's a plus one, but it's just a successor
function.

And you can see that piano was in the no
crowd, right?

He started from one, at least a notation
that was one.

At least in this first book about it.

He actually changed his mind.

Later in his writings, he started from
zero.

It's controversial.

Okay.

This is page one.

There was like a presection of notation.

By page two, he was already proving that
two is a natural number.

This is pretty fast moving.

Piano was a big influence on
Whitehead and Russell, who

took about 150 pages to get
to proving one plus one is two.

And Piano was already doing it on the
second page.

And that's partly a reflection of,
yeah, these are all axioms, right?

So he started with a lot of assumptions,
not building from scratch, right?

So he was the first one to try to build up
a concept of natural numbers without

assuming we knew what
they were and to think

really careful about how
to define these things.

But he also took a lot more for granted.

Russell Whitehead tried to build up from
even simpler notions.

And he's proving two is one because one is
a natural number by this definition,

right?

And by the second
rule, one plus one is the

definition, and our notation
for one plus one is two.

All right, so it's kind
of a vacuous proof,

introducing this notation
of two for one plus one.

Yes.

Thank you.