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

3.6: Defining Set Cardinality
- Cardinality of Finite Sets
- Cardinality of Infinite Sets

David Evans and Nathan Brunelle
University of Virginia
---

When we talked about numbers last class,
we said, well, they're ordinal numbers and

cardinal numbers, and the way we define
natural numbers, we, until we give them

some purpose, it's not clear what they
are.

So now we're going to
see if we can use natural

numbers to measure
sizes, to give us cardinality.

We haven't defined cardinality,
so we're going to define it.

We have an intuition that it's something
about how much, how many there are.

So the first step to define
it is going to be what

it means for two sets to
have the same cardinality.

The definition we're going to use,
and this is a widely accepted definition,

is that if we can
find a bijection, this is

a one-to-one mapping
between the two sets.

That means every element in the sets maps
to exactly one element in the other set.

One-to-one mapping, that means they have
the same cardinality.

That seems like a pretty
good match to our intuition

about what cardinality
of sets should mean.

Is this enough for us to
talk about there's a set

that has seven elements
from just this definition?

So this says if we already know the
cardinality of some set, we can tell any

other set whether it has the same
cardinality or not.

If we want to talk about a set having a
size, we need something else.

Yeah, what do we need?

Well, we defined our sets earlier,
and we talked, like, you had a three set.

Mm-hmm.
Good.

So you could just say
if your cardinality is the

same as my seven set,
then you have a cardinality.

Yeah.

Okay, good, yeah.

We need some sets whose cardinality we
know.

We need something that we can say,
this is a three set.

If you can map your
set one-to-one onto this

set, your set also
has cardinality three.

What would be a good idea for what we use?

We could arbitrarily make a three set.

What would be a natural thing to use for a
three set?

Good.

Define the three set as the natural
numbers up to three, not including three.

And that is handy because
we don't have to do something

special to find the four set or
the five set or the seven set.

We can define them all at once because we
have a notation.

This is the notation the
book uses for the set of all the

natural numbers from zero
up to not including that number.

So now we can talk about the cardinality
of any finite set by having a mapping

one-to-one to one of these special sets
that we have defined its cardinality.

Two sets have equal
cardinality and we can map them

to a particular set to
say what its cardinality is.

What about infinite sets?

Is there going to be any bracket k set
that we can map that set to?

There isn't.

What it means to be infinite is there is
no finite number that will match that size.

We're not going to ever find a bijection.

But this definition that we started with
still seems pretty good.

So we're going to not limit the definition
to finite sets.

We're gonna say that the definition,
the same whether it's finite or infinite,

Two sets have the same cardinality if
there's a bijection.

For the finite sets, we
have a convenient way

to name them based
on the natural numbers.

For the infinite sets, it's going to get a
lot weirder and more complicated.

Or at least, it doesn't correspond to some
intuition.

If we define equality, we can also define
less than or equal to.

If there's a mapping that is
surjective from A to B, well

that means that the size
of A is at least the size of B.

I set it in the opposite direction here.

This is intuitive, right?

From our equality definition, if there's a
one-to-one mapping, if there's a direction

where there's a mapping
at least in one direction,

we know one set is not
bigger than the other set.

Do we buy these two facts?

We have two sets that have the same
cardinality.

And I've started to use that notation.

And remember, that's a bijection.

Does that mean that the cardinality of A
is less than or equal to B, and the

cardinality of B is less than or equal to
A?

Yeah.

A bijection is also a surjection.

So a bijection means there's one-to-one.

Surjection means you're
covering this set, but

you might not use
everything in the other set.

So if you have a bijection, you definitely
have a surjection in both directions.

What about this property?

Is this one as obvious as the other one?

If you have the surjection in both
directions, do you have equality?

This one is much less obvious.

And this one actually took about a decade
for people to actually prove this.

So this one is famous enough.

It's got a theorem with Kantor.

He was actually the first one to state the
theorem, but he didn't prove it.

And others proved it.

So that one seems pretty intuitive that it
should be true.

It's definitely not obvious.

We're not going to get into the proof of
that.