---
Video Title: Do Infinite Sets Exist?
Description: Theory of Computation
https://uvatoc.github.io

4.3: Do Infinite Sets Exist?
- Countable Sets Recap
- Defining an Infinite Set
- Dedekind's Definition
- Equivalence of Two Definitions: 
     No Bijection with Natural Numbers / Dedekind's Definition
- The Natural Numbers are an Infinite Set

David Evans and Nathan Brunelle
University of Virginia
---

This is the definition we had last class,
which I know was a long time ago,

but hopefully you
remember it and have been

contemplating infinite
sets over the weekend.

So a set is countable if
and only if there exists a

surjective function from
the natural numbers to c.

Does this have to be a total function?

So we're going from the natural numbers to
c.

Surjective means we've got at least one
in.

Is it okay if the function's partial?

Yeah, so it's okay if the function's
partial.

If it's partial, it would just mean we
didn't need to use every natural number in

our mapping, but our goal is to show that
c is countable.

So if we can count it without using every
natural number, we're okay.

So here function definitely means partial.

We also define infinite sets.

And these definitions should be a little
more bothersome.

We said it's infinite if there's no
bijection.

So now we know the bijection is the total
function surjective injective.

All of those.

Before getting more on that, I want to ask
the question.

We kind of assume that infinite sets
exist.

And we did some things thinking about
infinite sets.

Is it obvious that infinite sets exist?

It's not obvious at all.

And it's actually a pretty strange
question.

We can always come up with a definition of
something and call that an infinite set.

But there's no obvious notion of what an
infinite set should be.

And it's actually something
people had a pretty

hard time coming up
with a definition for.

The first one that really thought about
this and came up with a good definition of

what an infinite set is, was Richard
Dedenkind.

Does anyone read German?

I think the title means something like,
what are the integers all about?

The z here.

That's a z.

That's supposed to be a z.

That's why we use z for the integers.

It's the German word.

This is the definition he came up with.

It is a definition.

We kind of have this notion of what
infinity means.

What it means for a
set to be infinite is that

it is similar to a
proper subset of itself.

A set that is not similar to a proper
subset of itself is finite.

How do we like the definition?

What does similar mean?

Good point, yeah.

Similar is kind of not a great term to use
here.

We're going to
interpret that, and I think

this is correct in how
he would interpret it.

If we don't care about
the actual elements in a

set, what does it mean
for a set to be similar?

A set is just a collection of mathematical
objects.

The only thing that it
would mean for sets to

be similar is they have
the same cardinality.

This means same cardinality.

So if a set has the same cardinality as a
proper subset of itself, and remember,

when we say regular subset, that could be
the same set.

But proper subset, we really mean there
are some elements that are not in the set.

The proper subset,
if S is a proper subset

of T, T has every element
of S and some more.

There's at least one
element that is in T

but not in S, and every
element in S is in T.

Now this definition starts to seem pretty
weird.

For finite sets, a proper
subset always has

cardinality less than
the set it's a subset of.

We have some elements
that aren't there, and the

cardinality is the count
of the number of elements.

Yeah.

Well, by that definition,
couldn't either only the

natural numbers or the
real numbers be infinite?

There are infinitely many infinite sets.

So if we accept that the natural numbers
is an infinite set, which is part of what

we're going to get to here
with this definition, well then,

the natural numbers with zero
removed is also an infinite set.

Right.

And the natural numbers with one removed
is also an infinite set.

We can remove all of the
numbers we want from the

natural numbers one at
a time, and it's still infinite.

Does that match your intuition?

It should.

So one way to think
about that is, remember our

definition of set cardinality
was a one-to-one mapping.

If we have the natural numbers,
and now we're going to create a subset of

natural numbers which
we remove zero from,

is there a bijection
between those two sets?

Sure.

We connect zero to one.

We connect

same cardinality.

There's a clear bijection between the two
sets, and according to Dedekind's

definition, if we can remove
an element making it a proper

subset without changing
the cardinality, then it's infinite.

So this definition starts to seem pretty
sensible now.

Are these definitions the same?

And so now we've got two definitions.

We have the one that we used last class
that says it's infinite if there is no

bijection between the set and any set of
natural numbers up to k, for any k.

And we have the definition that Dedekind
came up to that said it's infinite if it

is the same cardinality as a proper subset
of itself.

Did those seem like they mean the same
thing?

Yeah.

Yeah.

There's definitely a lot of reasons we
like Dedekind's one better.

This definition is defined as set in terms
of something not existing.

That means to show that a set's infinite,
we've got to prove something doesn't exist.

Proving something doesn't exist can be
done.

It's not so desirable to
have needing to prove

something exists
as part of a definition.

In order for those definitions
to be equivalent, what

are the two things we would
need to be convinced of?

Okay, good.

If I'm understanding...

We need to go in the direction of saying
if according to this definition a set is

finite, it's also finite according to that
one.

So that would mean all of the sets that
have a bijection to the natural numbers up

to K are also Dedekind finite,
meaning not infinite.

Is that easy to see?

So what we would need to do to
show... So we have our two definitions.

We have to show not two also implies not
one.

That's one direction we would have to
show.

We would have to show
the other direction and

we have to show the
positive directions as well.

We could show those four separate things.

We would show the definitions are
equivalent.

So we're not going to do all four.

But is this one easy to do?

Finite by this definition implies finite
by the other definition.

If we have a set that has a bijection to
the set of natural numbers up to K,

what do we know about a subset of that
set?

It has one less number.

Every subset we remove at least one number
from that, the cardinality changes.

So it is not infinite according to
Dedekind's definition.

This fits our intuition.

If a set is finite and we remove any number
of elements, the cardinality is changed.

That satisfies both definitions
consistently.

The infinite case is a little tricky.

We'd have to look at the bijections.

We said the natural numbers is infinite
according to our previous definition

because there's no bijection
to the natural numbers

up to K because they're
natural numbers beyond K.

We know there's no bijection.

Can we show that this property is
satisfied by the natural numbers?

And we pretty much already did.

We already did with this.

We showed the natural numbers
has a proper subset which is

the same cardinality because
we have a bijection between them.

So we've shown both of
these properties enough

to be convinced those
definitions are equivalent.

We've got two definitions that are both
consistent and seem, I don't know if I'd

say intuitive, but should make sense when
you think about them enough.

Let's go ahead and think about this here.

Let's do it.