---
Video Title: Cantor's Shocking Proof
Description: Theory of Computation
https://uvatoc.github.io

4.5: Cantor's Shocking Proof
- Proving that | pow(S) | is greater than | S | for all sets S.
- Uncountable Sets

David Evans and Nathan Brunelle
University of Virginia
---

What I'm going to talk about is what
Cantor did in the late 1800s that did show

that the power set of a set is bigger than
a set for all sets, not just for finite

sets, so that it also holds for infinite
sets.

This is what we want to show.

We're talking about
set cardinalities, so that

should get us thinking
about the definition.

We've got a surjective
total function, and

we're going to prove
this by contradiction.

So to get a contradiction,
we're going to assume

that it's not the case that
the power set is bigger.

That would mean that
the set S has cardinality

greater than or equal
to that of the power set.

If that's the case, that
means between S and the

power set of S, we have
a surjective mapping.

Every element of the power
set, some function, we want

at least one out and less
than or equal to one in.

If we have that, then S is the same size.

If we're assuming S is bigger than the
power set, that function must exist.

So we're going to have some function G.

We're proving for all sets.

To show that it's not true for all sets, we
just have to find one set that is not true.

Let's assume there exists some set.

So that's going to be the set A.

And for the set A, there's
some function G from.

A to the power set of
A that is a surjective.

This is just following from our
definitions.

Now we've got to do what's the real clever
trick that Cantar came up with.

We're going to have some set.

There's some element of the power set.

Everything in the power set is a set.

And we'll call that a G.

And we'll define that set as the set of
all elements of A that are not elements of

the set that the surjective function G
maps to.

So what we are trying to
show here is that the cardinality

of the power set is bigger
than the cardinality of the set.

So to get that contradiction, we're
assuming the opposite, which would mean

there is a function from A to the power
set of A have one edge going into every

element in the power set without needing
multiple edges out from A.

So if we have one edge into every element
of the power set from a function,

then we're covering them.

Then it's not bigger.

Yeah.

Oh, I meant.

Thank you.

Sorry.

Okay.

Yes, it should be greater than equal to.

Thank you.

You are absolutely correct.

So we need at least
one in, this is the bigger

set, at least one in, and
no more than one out.

Is that correct now?

Okay.

The contradiction we're trying to get is
that if we show that A is not bigger than

the cardinality set, not bigger or equal
to.

The equal to is the real case that we care
about.

Then we're showing the power set is actually
bigger, which is the surprising result.

Yes.

So the last line, now we're going to
define a set.

So this is going to be
the set of all elements

of A, where when we
map them to the power set.

Right.

So remember the elements of the power set
are sets that are subsets of elements of A.

So G A here, A G is some point here,
which we're defining now as the set of all

elements where A is not an element of the
set it maps to.

Let's say A is the natural numbers.

We have the number three and we have a set
in the power set, which is the subset two,

four and seven.

That would be in the set A G because it
doesn't map to the set that contains itself.

If we had one, let's say five here maps to
the set.

That would mean five maps to the set that
contains itself.

So it's not in the set A G.

What's in the power set are sets of
subsets of elements of A.

We're defining A G as a
set, which is all the elements

of A that map to sets that
don't contain themselves.

For the two examples I've shown you,
three should be in A G because it maps to

the set two, four, seven, which doesn't
contain three.

And five should not be.

If this surjective mapping existed,
and I'm just making up what it might be,

A G is well defined.

So how do we get a contradiction?

So, so far everything seems okay,
maybe sort of okay.

Remember that G is surjective.

Every subset of A is in the power set.

So this A G set that I've defined is here.

It's an element of the power set.

It's some subset of A.

So it's in that power set set.

There's got to be some element in A.

We'll call it A of X.

Where G of A of X is equal to A of G.

If that mapping exists, then there has to
be some element that maps to the set that

contains all of the elements that don't
map to themselves.

So is A of X inside A G?

Let's think about the possibilities.

So now we've got A of X.

Set membership is a binary question.

It's either yes or no.

There's only two possible answers.

Could the answer be yes?

Okay.

It can't be yes.

Because that would contradict our
definition of A G.

Because our definition of A G is ones that
don't map to themselves.

So it can't be yes.

It better be no.

Can it be no?

Well, how do we pick A of X?

A of X is the one that maps to A G.

So if it's no, it's got to be in that set
that it maps to.

Because that's how we define the A G set.

But it also can't be in that set.

We've got a contradiction either way.

If that was the case, what is the set that
A of X maps to from G?

Yeah.

That's the A of G set.

That's how we define it.

So both of these are contradictions.

Neither one is possible.

We get to a contradiction.

And we got to the contradiction by
assuming this property.

That the cardinal of A was greater than or
equal to the power set.

So it must be that the power set is
bigger.

So this was the result that shows there is
a set bigger than the first infinite set.

Even though the way we
define an infinite set is one

that we add something to
it and it doesn't get bigger.

So this is a pretty surprising result.

Does this mean there's an uncountable set?

Yeah.

If the power set of the natural numbers is
bigger than the natural numbers,

and we define countable as there's a
bijection to the natural numbers,

then the power set of the natural numbers
is bigger.

And we have our uncountable set.

Should bother you a lot.

This bothered a lot of other people.

These are the kinds of things people were
saying about this when Cantor claimed it.

He had a lot of people upset with him.

Actually, it's a sad story.

He took it pretty personally.

But he knew it was right.

So the more he thought
about it, the more he looked

at his proof, he knew
it was definitely correct.

Despite all these old distinguished people
saying nasty things about him.