---
Video Title: Defining Addition
Description: Theory of Computation
https://uvatoc.github.io

3.2: Defining Addition
- How to define addition for the Natural Numbers

David Evans and Nathan Brunelle
University of Virginia
---

One of the questions last class was about,
can we do addition?

So we define these natural numbers.

If they are a good way of
representing what we think of as

natural numbers, we should
be able to do addition on them.

We should be able to define something on
these objects that we can construct

through these strange rules that behaves
the way when you are in first grade,

or probably many of you younger than that,
you learn what addition means.

We should be able to define it.

So let's try.

So can we define addition to work on these
objects that we're constructing?

It's always a good idea to start with a
definition with definition.

And that seems kind of silly, but it's
actually important.

All the definition is, is
we're making up some

notation or some term
and we're giving it meaning.

We're trying to make up
something and give it meaning

that matches our
intuitive notion of addition.

So we're going to define addition.

Let's define it in terms of just two
numbers.

Our goal is to define what it means to add
two numbers.

So we're going to introduce a and b as
variables.

Those are our natural numbers.

The English language around addition is
kind of complicated, right?

I don't know a word more like add that
would be in place of sum.

This is what we're defining.

That's defining add.

Probably using the math notation makes
more sense.

We're defining what a plus b means.

What's the easy case?

Good.

So which one is zero?

Both of them.

Both of them?

Okay.

So that's maybe the easiest case.

If they're both zero, what's the sum?

Is there almost as easy a case that we can
use that covers a lot more possibilities?

At least one is zero.

Okay, good.

If one of them is zero, the sum is the
other one.

Which one do we want to make zero?

Does it matter?

It's going to affect the rest of the
definition, but certainly either one would work.

We can make either one zero.

I'm going to make the first one zero,
because I think that's a little more natural.

If a is zero, a plus b is b.

The use of the equal symbol there is kind
of dangerous, right?

So we're not defining equality here.

Probably I should actually write is
instead of equal.

So now we need case two.

What is the condition for case two?

If we only have two cases,
the condition for case two better

cover every other scenario,
which means a is non-zero.

If a is non-zero, what do we know about a?

Definitely a plus b is not equal to b if a
is not zero.

Can we break a down into pieces if we know
a is non-zero?

Metaphorically, it's the successor.

With the notation we're using here,
that means a is something like this.

And for some other natural
number, p is some natural

number, something
represented by this construction.

And a must be p union set of p.

Then a plus b is what?

The notation is hard here, and we're using
it to be like sets.

But if you think about what it really
means, this is a is p plus one.

The intuitive meaning of how we define the
union of the set of the thing.

Yeah, so what's that?

It's p.

Good.

An intuitive thing we wanted to say is a
plus b is now p plus b plus one.

With our funny notation,
what that means is

it's the plus is what
we're trying to define.

Right?

So this is a recursive definition.

We're defining plus in terms of plus.

And this is unioned with that p.

So is this a good definition?

If you were teaching a
second grader what addition

is, this is not the way
you would want to do it.

I think that's true.

Maybe a third grader, this would be a good
way to do it.

They're ready for that trauma by third
grade, I think.

I hope so.

I only have a second grader, so I don't
know.

By these two cases alone,
have we defined addition

that's going to work on
any two natural numbers?

Where our constructor is the way we're
making natural numbers.

Yeah.

I think we have.

And the reason we have it, p is smaller
than a.

Do you think of this like a recursive
procedure definition?

And you could certainly turn this into
code.

You are subtracting one each time you use
the recursive definition.

So you're eventually going to get down to
the base case, where a is zero.

And you're going to have your answer.

So this is not an efficient way, if you
were implementing a program to do addition.

Efficient way to do it, but it is going to
be correct.

Yeah.

That we're using plus in our definition.

Is that what's unsaid?

Okay, good question.

Yeah, it should make you somewhat
uncomfortable.

We're doing that all over the place.

This is the recursive call.

We also defined a natural number in terms
of a natural number.

We defined a set in terms of a set.

We define things recursively all the time.

When you have a recursive definition,
the way to know it's not circular is to

know that, yeah, we're not defining a plus
b in terms of a plus b.

If we were doing that, that's like if we
said a good definition is a good definition.

We're not making any progress.

In this case, what we're
doing is we're defining

a plus b in terms of the
predecessor of a plus b.

We still haven't defined
plus, but the combination of

the two rules is going to
be enough to define plus.

And you are right to be uncomfortable with
that.

There is a whole philosophical
question of whether this is

really valid, which I don't
want to get into today, right?

Because there could be other ways to
interpret that.

The way we want to interpret this,
as this is really a definition that means

addition the way we are, is one way of
interpreting that.

That's the fixed point of these two
definitions, that if we assign plus the

meaning we think it has, this all makes
sense and seems to behave correctly.

Definitely not obvious that that's the
only way to interpret this.

Yes, question?

Why did we use the set notation instead of
the successor?

Yeah.

Okay, good question, yes.

Did it matter that we changed the
notation?

Let's say we wanted to find addition with
the successor notation.

We definitely have to change this.

How would we have to change this if we use
the other notation?

Right.

Instead of A is this, then we would say A
is the successor of P. And instead of

this, we would say the successor of P plus
B.

Which is maybe a little more readable and
satisfying, because thinking of the

successor is a more
natural way to think of

adding one than the
unioning a set with itself.

The meanings are the same.

It's just a question of,
here's the notation that we're

using that maps to this abstract
concept we have in numbers.

So the only reason that I
introduced that was to hopefully

make that point was to say
that, yeah, these are symbols.

When we talked about defining the actual
numbers using the successor function,

that was kind of magic because we don't
have a successor function.

We at least didn't have that defined,
and maybe that's an unclear notion,

but it's part of the definition just as a
symbol.

These are just syntactic things at that
point.

Whereas union is something we have a bit
more of an intuition about, and we can get

a definition that has exactly the same
meaning and produces things that we can

map one to one to the numbers
that we were producing with the

successor and to our intuitive
concept of what a number is.

So they are exactly the same meaning.

Until we give anything more
meaning than we've given it, they're

exactly the same as just
changing the way we write it down.

Let's see.

Let's see.