---
Video Title: Countable Sets
Description: Theory of Computation
https://uvatoc.github.io

3.7: Countable Sets
- Defining Countable
- Cardinality of the Powerset of a Finite Set

David Evans and Nathan Brunelle
University of Virginia
---

Now we're going to define countable.

This is a definition.

We're just introducing a new term.

Countable just means that
the set cardinality is less

than or equal to the cardinality
of the natural numbers.

Another way of stating that from our
definition of less than or equal to is

that means there's some
way we can map the natural

numbers that covers
every element of the set.

If we can do that we We know the set is
not bigger than the natural numbers.

Is the set of binary strings countable?

To show that the binary
strings are counted, we've got to

show that we can map each
binary string to a natural number.

So actually that's a little different from
what we did show.

What are we going to do to map the binary
strings to the natural numbers?

There was a tree somewhere.

Yeah, this tree.

We could do it like this, right?

This is going to be 0, this is going to be
1, this is going to be 2, 3, 4,

5, and so on.

We have a mapping between the binary
strings.

We can assign a natural number to each
one.

We're not going to run out.

We can do it in a clear order.

As computer scientists,
you already know that we can

represent all the natural
numbers with a binary string.

う, we know binary notation and it maps to
our familiar notion of natural numbers.

Another definition, countably infinite,
if it's countable and it's infinite,

then a set is countably infinite.

Is the binary strings countably infinite?

Yeah.

We know it's infinite, we know it's
countable.

It's countably infinite.

Are there any sets

that are bigger?

We're going to first define the power set.

I think most of you have seen this in
discrete math.

So the power set is the set of all subsets
of a given set.

If we want the power
set of one, two, three,

how many elements
will be in its power set?

Yeah, eight, right?

So that's where the name power set comes
from.

It's going to have the empty set,
it's going to have the set containing one,

the set containing two, the set containing
three, the set containing one,

two, and so on.

What is the cardinality of the power set?

Yeah, good.

Sounds like a lot of... how do we know
this?

Can we prove the cardinality of the power
set?

What strategy do you think we should use
to prove this?

Yeah, we can use our constructive
definition of a set, and we can say either

an element or the nth element that you're
adding on, there is in the power set,

or is either an element of the power set,
or it's not an element of the power set.

And that's two cases, and so it's two
times whatever remains.

Okay, good.

That sounds on the right track.

So as we add a new element to a set,
the power set is the old power set plus

the old power set with that element added
to every set.

Can we be more clear?

How are we going to prove it?

Yeah, did you have a...

Oh, I was just thinking of taking

a... Okay, yeah, that's
actually a very clever idea.

One way to think of the power set is a
binary string where for each element in

the set, it's zero or one whether that
element is in there.

We won't get today, but that's actually a
one way to see about the cardinalities is

a very interesting way of looking at
things.

Yeah?

You do it by induction with a base case,
and then for each step up, you take every

single element of that set, and then you
kind of just like insert it into every one

of those sets, and then the two of those
together are the power set.

Cool.

Okay, good.

Yeah, so this seems like something we can
prove by induction.

Proving by induction seems like a good
strategy for this.

Our principle of induction works on the
natural numbers.

We're trying to prove something about
sets.

Remember, our principle of
induction was we're proving

something about some
subset of the natural numbers.

We don't have a principle of induction for
sets yet.

What is the set of the
natural numbers that's going

to allow us to prove
something about all sets?

The idea that she had is, you know,
we should prove this by induction, right?

We're getting... our intuition is that as
we add elements, it's going to grow.

This seems like a property that we can
prove by induction.

The problem is our principle of induction,
what we've proven so far about induction,

only allows us to cover the natural
numbers.

If we were trying to prove
something about all the

natural numbers, we've
got our principle of induction.

If we had that intuition of,
yeah, we can show that as

we grow the set this property
holds, we would be there.

But we're not trying to prove something
about the natural numbers.

At least we haven't stated it as a
property of the natural numbers.

We state it as a property of all sets.

So what what do we need to do to make this
work?

Did you have an idea?

That's a very good point.

Yeah, our induction principle works for
the natural numbers.

We're only ever gonna prove things about
countable sets using it.

This is only gonna work for finite sets.

But the sets that
we're proving it on, this

is... we want to prove
it for all finite sets.

Because the finite sets
are countable, in this case,

these are sets where
the elements don't matter.

All that matters is how many elements
there are.

And certainly this property,
when we're talking about

cardinality, is the actual
elements in the set shouldn't matter.

So that's countable, and
it's countable because

the size of the set
is all that matters.

And what are the
size of the sets that we

care about if we're
talking about finite sets?

They're exactly the natural numbers.

So we are going to be doing this induction
on the cardinality of the sets.

So we are going to start with empty set,
which has cardinality zero.

That's our base case.

I will defer getting into the proof.

Well, we are starting to get to the
question about infinities.

And the question that was raised about,
yeah, are we proving something for all

sets or just finite sets, gets very deeply
at that question.

But you'll have to be disturbed over the
weekend trying to resolve this on your own.

But definitely think about it,
and then we'll continue that next class.