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

3.1: Sets and Naturals
- How to define Sets
- Sets and the Natural Numbers

David Evans and Nathan Brunelle
University of Virginia
---

This question that is both a really
important practical question for computing

and a really deep theoretical
mathematical question that

causes people to go crazy
and change their worldviews.

We want to understand what are all the
things that can be represented by strings

of bits, and what are the things that
cannot.

Last class we started talking about
natural numbers, so we'll continue from

there, building up from that, to get to
this question about infinities.

And try to understand
what are the things that can

and cannot be represented
by finite strings of bits.

We defined natural numbers last class.

What about sets?

Can we come up with a definition for sets?

So these are good definitions of what a
set is, right?

So if we understand a
set as it's some collection,

it's a collection where
we don't care about order.

Something can only either be in it or not
be in it.

There's no count.

It's not a bag where we can count the
number of times.

What I want to see if we
can get to is something more

like the constructive definition
that we have for numbers.

So we said we could build up all the
numbers starting from zero, and all we

need to create all the numbers is a
successor function.

These descriptive
definitions of sets are useful,

but they assume we
know what a collection is.

So in some sense, defining
a set as a collection sort of

assumes we already know
everything we need to know about sets.

So any other ideas how we can build up a
definition of sets?

It's either the empty
set or it's another set

with an additional
element appended to it.

Good.

Yeah, right.

So this is very analogous to the
definition we have of numbers.

So we have a base set.

Our base set is the empty set.

And there are different notations people
use for the empty set.

Usually it's not empty set in quotes.

The two most common,
the zero and the slash,

and the set brackets
with nothing in them.

And we will probably use both of those.

We're going to try to
mostly use the zero with

the slash as a special
notation for the empty set.

So once we've got the empty set,
how do we build up more sets from there?

Good.

Yeah.

So what should we union?

So union is kind of like successor.

It's a way to add things to sets.

What should we union the set with?

Let's assume we have some notion of
things, right?

So we're going to, if
something's a set, from a

set, when we union things
into a set, we get a set.

So X could be anything.

Then we're going to say S union.

So what are we actually unioning with?

Is it with X or with something else?

Yeah, a set containing X, right?

So if we had an insert operation,
if you think of sort of the set functions

in most programming languages, there's
one that is like union that takes a set.

There's one like insert that takes an
element.

And we haven't really defined our set
operations, right?

This definition is assuming we already
know what union means.

But if we know what
union means, we've got to

create a set that contains
X and do our union.

This could make us a little nervous and
uncomfortable.

Our constructive definition of set is
assuming we already know how to make a

singleton set and we already know what
union means.

If we were really building things up from
scratch, we would have to define those

things in a way that allowed us to use
them.

As an intuitive constructive definition of
a set, this makes sense.

Does this construction produce a new set?

Is S union the set containing X a new set?

Or is it the same set that you started
with?

Yeah, it depends, right?

It could produce the same set.

It doesn't always produce a new set.

Which would also make us a little nervous,
right?

If we're saying we can build up
sets from empty set, we would

like a construction that always
is going to produce a new set.

But this seems like
a rule that we could

produce all sets from
if X could be anything.

X could certainly be another set.

I'm going to tweak this a little bit to
change the rule to this.

So now we don't need an X, right?

That rule was kind of uncomfortable
because it required drawing this X from

some mysterious universe that we might not
have defined yet.

So now we're going to avoid that.

We're going to say define the empty set,
which we'll denote like this.

And we're going to have an inductive
clause that says we can construct a new

set by uniting S with the set containing
S.

Is that going to allow us to build up
interesting sets?

So certainly it's not
going to allow us to build

everything we intuitively
think of as a set today, right?

So we think of the set containing 1,
2, 3 as a set.

This is not going to allow us to build...

Well, will it allow us to build something
that we can think of as the set 1, 2, 3?

If we think of these as a way to represent
the natural numbers... So 0 is a set.

What's the next set going to be?

Well, the only set we have at this point
is 0, is the empty set.

So that means the set,
this union, the empty

set union, the set
containing the empty set.

What would be a better
way to write the set of the

empty set union, the set
containing the empty set?

It's just the set containing the empty
set.

If we union the empty set with something,
we get what we had.

So we can erase that.

What's the next set going to look like?

This might be a little hard to say
verbally.

Actually, it's going to be a different
set.

It's not the same set, because it's going
to be a set that now has two elements.

It has the element, the
empty set, and it has

the element, the set
containing the empty set.

We can keep going.

We can think of this as zero, this as one,
this as two.

Are we convinced we
can build up something

that represents the
natural numbers this way?

Yeah.

Is this definition limited to the
cardinality of the natural number?

This is kind of the fundamental question
we're going to get at most of the class,

so maybe I don't want to try to answer it
now.

This set, in some sense, is exactly the
same set as the natural numbers.

It's just a different notation.

We haven't assigned any other operations
or meanings to these things.

This is exactly the same set as the
natural numbers.

So in that sense, it should have exactly
the same cardinality.

But what is that?

Is that construction?

That's construction, not a storm,
right?

Okay.

We're okay.

Okay.

The hurricane is far, far away still.

This looks like another way of saying,
well, let's get rid of that mysterious

successor function, which we used last
class to define the natural numbers,

and use something that
seems more familiar that we

already know, that's the
union and set operations.

And now we can define the equivalent of
the natural numbers.

It's kind of a weird notation for writing
the natural numbers.

This is not... I don't think I did the
brackets right.

It's a hard notation to see what three
looks like.

Some weird bracketed way.

I think that is right.

That is three.

Okay.

It's going to be hard to count much higher
than three like this.

But in theory, we can count as high as we
want.

It's a good representation of the natural
numbers.

So both of those are different sets of
rules for constructing objects.

We can construct
mathematical objects using

those two rules, and
they're really similar.

In some sense, these are really the same
sets of rules.

They're just different notations.

And our intuition about what adding one
means, or what successor means,

or what unioning means, those are meanings
that humans add on top of that.

But in terms of the
mathematical definitions, they

are equivalent other than
the notations at this point.

And if we start assuming other
operations on them, well, then

we can define them in ways
that will make them different.