---
Video Title: Counting the Binary Strings
Description: Theory of Computation
https://uvatoc.github.io

4.6: Counting the Binary Strings
- How many infinite binary strings are there?
- Any bigger sets?
- Je le vois, mais je ne le crois pas!

David Evans and Nathan Brunelle
University of Virginia
---

What about the infinite binary strings?

Getting back to our motivating question
from the last class.

The finite binary strings are countable.

We can represent every natural number of
the finite binary string.

For the infinite binary
strings, one way to show that

they're uncountable would be
to map them to the power set.

If we can show that there's a bijection
between the power set and the natural

numbers and the
infinite binary strings, that

would certainly show
that they're uncountable.

Can you think of how to do that?

Good, yeah.

So one way to think about a set, if
we have... Here's our natural numbers.

The power set of natural numbers is,
for every element of that set,

you have the choice whether to include it
or not.

And you have all combinations.

To get the power set, the power set includes
the empty set, which is none of those.

It includes the set with zero and nothing
else.

It includes the set with one and nothing
else.

We can define the power set as,
for every element of the set, there's a

bit string that says yes or no as that
element in it.

And all of those put together is the power
set.

So that, I think, is a pretty easy way to
see that the cardinality of those two is

the same, and we can't count the infinite
binary strings.

The other argument that
is similar to the one about

real numbers in the book
is the diagonalization.

If there is a mapping between the binary
strings and the natural numbers,

there should be a way of writing them
down.

And it should include every binary string.

So to prove that that doesn't exist,
what the diagonalization arguments do is

say we're going to go on the diagonal and
we're going to flip each bit.

Because they're infinitely long strings,
we can go forever.

And we're always going to generate some
string that's not in the table.

If that was in the table, when we got to
it, we flipped one of its bits.

We're flipping one
bit of every string, and

because it's infinite,
we can keep doing that.

And we're always going to generate a
string that's not in the table.

So we have uncountable sets.

Is there anything bigger
than the set of all the

binary strings or the power
set in the natural numbers?

Yeah, what's bigger?

Sure.

What Kantar proved, the power set of the
set is always bigger than the set.

So we can keep doing power sets.

But lots of things that you would think
are bigger or not.

So definitely the power set
of the power set of the natural

numbers is bigger than the
power set of the natural numbers.

But the real numbers, same, and that's in
the book, That Proof.

Certainly expanding the
range of the real numbers,

that's just adding two
copies of each, right?

One with a zero in front, one with a one
in front.

We can do the same bijection there.

It doesn't get bigger.

This is more surprising.

This is actually
probably one of the most

surprising ones, and
we won't try to prove this.

The product of the reels is also not
bigger.

If you think about that
geometrically, that's

saying the line is the
same as the square.

Those look like pretty different size
sets.

This is actually the one
that's the most famous

quote about this area,
which you might have heard.

Any French speakers want to translate
that?

Yes.

I don't know French, but I can just kind
of guess from Spanish.

Even better.

I see it, but I don't believe it.

Exactly, yeah.

That's how it's usually translated.

This was Cantor's quote.

A lot of people think this
was about showing the real

numbers are uncountable or
showing the power set proof.

This was actually about this, showing that
these two are the same size.

That was the thing that he found most
surprising, which is pretty surprising.

And we know power sets are going to be
bigger.

So the big question, we've got the natural
numbers.

We can call that the first infinite set.

And we've got the power set of the natural
numbers, which we know is the same as the

number of reals and the same as the number
of binary strings.

What we don't know is if there is anything
between those two.

So these are defined as ALF numbers.

ALF zero is the smallest infinite
cardinal.

ALF one is the second smallest.

It is unknown if that is the power set of
the natural numbers, the cardinality of

the power set of the natural numbers,
or if there's something between those.

And what's actually more interesting is
not just that it's unknown.

It's proven that it cannot be decided
based on at least the commonly used axioms.

So it's not that it's unknown,
it's actually provably unsettlable,

which is a pretty strange concept.

But all these things with infinities get
to be pretty strange concepts.

We won't get into that anymore in this
class.

That's definitely an
interesting thing to ponder

and to take a set theory
class about someday.

That we can fix oursystem that we should
be using Heyd develop color blue.

We can do the rules so that we can pick
each other.
That were the rules together.

We can do this together in our playground
Purple.

Because we are nosotros with And to teach
us You can say We are here