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

2.4: Defining Equality (for the Natural Numbers)
- What does it mean for two numbers to be "equal"?
- Proving 2 = 2

David Evans and Nathan Brunelle
University of Virginia
---

How should we define equality?

So now we've got a definition,
and this gets to some of the questions you

asked about, well, does this match our
concept of a number?

And does it do addition right?

Let's start with equality.

Addition is fairly complicated.

How are we going to decide if two natural
numbers are equal?

Is there some intrinsic notion of
equality?

So that's definitely what we want to
capture.

But what they represent is really
complicated.

We don't have anything
in this definition that says

this represents some
abstract concept of threeness.

And what threeness
means is the same thing if

you've got three apples
or three watermelons.

That's what threeness means, right?

That's a pretty difficult concept.

So how should we think about equality?

Yeah.

Okay, good.

Yeah.

So if there's only one way
to get to a number, then we

could determine equality
based on how you got there.

So maybe we can build up a definition of
equality.

But the first thing
I want to point out,

equality, this is something
we have to define.

So there's no intrinsic notion of what
equality means.

For any new definition we have,
if we have defined a set of things,

we might need to define a new notion of
equality.

So if we're going to define
equality for the natural

numbers, it's something
we actually have to define.

It's not obvious what it is.

So how can we define it?

Can we build up to a definition of
equality?

Zero is equal to zero, and
two natural numbers are

equal if the numbers near
the successors to are equal.

Okay, good.

Yeah.

So you've actually got pretty much the
whole definition.

The first part is the one that I want to
start with.

Right.

So the first thing we know, zero is equal
to zero.

We know zero equals to zero.

But we want to define equality.

Let's define equality.

So we could think of equality on any
number of numbers.

Let's keep it simple.

Equality is a property of two.

Right.

We have two natural numbers.

You want to say if they're equal.

And the first thing we know is zero is
equal to zero.

So how do we use that in our definition?

We've got...

We want to have a
definition that applies to

the whole set of objects
we're talking about.

So it should apply to any two natural
numbers.

And we should give them names.

And there's nothing special about these
names, but we like to use M and N.

N and M.

They're actually really bad choices
because they're hard to say distinctly.

We've set up our definition and you
started with, well, zero is equal to zero.

So how do we put that into a definition of
this form?

Because we want to make our definition
apply to any natural numbers.

Yeah.

Okay, good.

So if N is zero and M is zero,
then N equals M.

And I used is here instead of equal
because we're defining equal.

That's assuming we have some way of
matching this symbol zero with N, right?

Which I think we can
accept that we have because

there's only one way to
write zero, which is zero.

We're off to a good start, right?

We've covered the case where they're both
zero.

Is there another case we should cover when
N equals zero?

So if N is zero, right, this is case one.

We're going to have a bunch of cases here.

So there's two clauses to that.

There's N is zero and M is zero.

Can we split those?

What if M is not zero?

Good.

The case that we start with, if N is zero,
M is zero, N equals M.

Otherwise...

So that's one case.

The case where N is zero.

What's the other case?

If N is not zero, what do we know about N?

Good.

Yeah, right.

So our construction rule, right?

This is one of the really nice things
about definitions by construction.

Case one covered this case.

The only ways we can make natural numbers
are either at zero or by rule two,

it is the successor of some other one.

And here we have to be careful mixing up
the N's and M's and K's, right?

Because the N there is the K in what you
said.

So that means if N is not zero,

N is S of K,

how do we decide now if N is equal to M?

Know from the definition of natural
numbers that it must be S of K for some,

like the successor of K for some K,
which is a natural number.

Yeah, what do we do next?

I just have a question.

Yeah, good.

If you can say if N is
zero, isn't this like is

that's equally as
ambiguous as saying equals?

Yeah.

What does the is mean here?

That's a good, right?

So if our way of defining equal is it
means is, then that's not very good, right?

But the is here really is just a
notational thing.

Is here is exact match to that notation.

This is a very different notion than
equal.

So in this case, we're saying N is the
successor of K for some K.

That is a equality statement in some
sense, but it is really just a linguistic

how we constructed these symbols together
statement.

So there's no notion that we're assuming
is means equal.

It's just this is the way we made it.

Yeah.

Question.

How did... Yeah.

So this otherwise is...
I should make... Okay.

So if N is zero, we can have this.

This is case one A.

M is zero.

And case one B, M is not zero.

Those are both sub cases of the initial
case where N is zero.

Was there another question?

Yeah.

So I don't think you're
going to cover all the

cases by seeing if they're
successor of each other.

If N is successor of M, that's not equal.

And if M is successor of N, that's also
not equal.

If that would fit our definition.

But that doesn't cover all numbers,
right?

That is so we want to know that four is
not equal to two.

Question.

Those two rules by themselves would not
cover the...

Is for a successor of two.

They're true, but they wouldn't cover all
the numbers we want.

Yeah.

Did you have another question?

Yeah.

So next we want to check if M is zero.

Okay, great.

Yeah.

Right.

So we're going to break it down into two
cases like we did before.

So now we've got case 2A.

We've got the case where...

If M is zero and N is the successor of
something, what do we know?

Yeah.

They're not equal.

We know, at least we're
assuming, or it seems

intuitive, that zero is not
the successor of anything.

We might need to be a little careful about
that, though.

Our last case, if M is not zero, then M
must be the successor of some other thing.

Let's use Q.

And if M is the successor of Q and N is
the successor of P, M is the successor of.

Q, the only way N and M are equal is if P
and Q are equal.

So this is a recursive case, right?

We're defining equal in a recursive way.

This allows us to make progress.

Because now, instead of needing to know if
N is equal to M, now we know they're both

successors of something, maybe something
different, maybe the same, but now we need

to know if they're successors of the same
thing.

This definition is going to cover all the
natural numbers if all the natural numbers

are built up with these two rules starting
from zero.

We have a theorem here.

Proposition.

We haven't proved it yet.

So, should those things be equal?

If we think of, well, the
successor of the successor of

zero corresponds to our concept
of two, and two equals two.

Intuitively, we think they should be
equal.

Are they equal by our definition?

We're going to need to use the definition
of a quality.

But we can use it.

We're going to go through, first case is
going to be 2b.

And then we're going to have is the successor
of zero equal the successor of zero.

And then we got to go through our
definition again.

We're going to go through case 2b is zero
equal to zero.

And then we're going to end up with case
1.

And my wording of case 1 is a little more
compact instead of breaking into two.

I actually like the way you did it better,
that this should be case 1a.

That says they're equal.

Okay.

So we have proved, and to make it a good
proof, we should have some Latin at the end.

We have proved that two equals two.

What kind of proof is this?

Lots of different answers.

I've heard induction a couple of times.

Does it look like an induction proof?

A proof by induction means we're proving
something about some infinite set.

Right?

That's when we use proof by induction.

This is not proving something about an
infinite set.

Our definitions are recursive.

Right?

So they do lend themselves to induction.

And we'll get to that next class.

But in this case, we didn't need to use
induction.

We just follow steps.

Right?

And a proof where you follow steps is a
direct proof.

Right?

So even though many of you said you were
not familiar with direct proof,

all of you are actually familiar with
direct proofs and have done direct proofs.

That's all it means to
say it's a direct proof,

is you didn't use any
fancy proof technique.

You just follow the sequence of steps
using logic.

Part of what we assumed
in our definition of

equality, and I'll show
you where we assumed it.

We assumed... Actually, in here.

This is the case where we assumed it.

We assumed that if n is the successor of
something, it can't be zero.

We assume that there's no number whose
successor is zero.

Do we know that?

So maybe our definition gives us that,
right?

Our definition says zero is a natural
number, and if n is a natural number,

its successor is.

But this isn't quite a sort
of a recursive definition

where we build up
things linguistically, right?

This doesn't tell us
there isn't a natural

number negative one
whose successor is zero.

At least it doesn't...

It seems like the way we're
constructing our natural

numbers, there's no way that
we're going to hit zero again.

And maybe if we were really
clear about what this notation

meant, we would know we
would never hit zero again.

So I think that's actually...

I kind of accept that answer saying this
definition, at least as I would interpret

it, would say, yes, there's no number
that's successor is zero.

But it's a little bit murky.

Yeah?

I'm just out of curiosity.

So when we started this whole process,
we were defining what natural numbers

were, and right now
we're defining notions.

Is the definition of a natural number a
preconceived notion here?

So this is a good question.

If the question is like, what are we...

You know, we're trying to define things
without preconceived notions, but we're

using lots of things that seem kind of
like preconceived notions in this.

Is that capturing what you're asking?

Yeah.

If this was a set theory class,
you would really build from scratch.

Right?

And say, we're not going to use anything.

Right?

So we're certainly using logic.

Right?

We're assuming we know logic.

We know what and means.

We know what implications are.

We know how to put all these things
together.

So maybe you've got to assume some amount
of logical rules.

Right?

But we're also using some other things
maybe.

I think here we're not using too much
else.

But we are often assuming sort of a lot of
other things when we make our definitions.

Right?

That we have some intuitive notion of that
we haven't defined formally.

And certainly if we only built up on
things that we define formally from

scratch, we would probably not get to
addition by the end of the semester.

Which would be kind of sad because we want
to learn something about computation.

Yeah?

So, with the definition that we have of a
set.

Which is that zero is a natural number.

And that s of zero is a natural number.

Yeah.

Would it not also satisfy that in the case
where s of zero is zero?

Yeah.

It might.

So certainly like...
And I'll show you.

Piano was not satisfied
that you could just assume

that there's no number
whose successor is zero.

He had an axiom that said there's no
number whose successor is zero.

This is his not equal.

There's no number that you can add one to
and get one.

That's his equivalent
of the axiom that says

there's no number
whose successor is zero.

If you start from zero.

So depending on a lot of complicated other
assumptions, you might know that.

And I'll just point out... So from
your survey, this is something that...

Thinking about definitions is something
that is really challenging.

Something that hopefully you will all
develop more of.

I don't know what to read into this.

So I've done the same survey when I taught
discrete math two years ago.

And it looks like people have...

It's a different population, but...

Maybe people have gotten worse since
discrete math.

I don't know.

The main point I hope you got from
today...

So all these mathematical concepts,
going back to the simplest things like the

numbers that you learned to count with when
you were three... These are not natural.

Natural numbers are not a natural concept.

They are concepts defined by humans and
they can be defined different ways.

And the way that you define them has a big
impact on how you think.

And good definitions are really useful
tools for thinking.

One of the things that
we hope you will get out of

this class is both critical
reading of definitions...

To think about whether they're good and
whether they do what they should...

And abilities to make up your own
definitions.

So we'll continue with that next class.