PROFESSOR: So it's time to examine uncountable sets.
And that's what we're going to do in this segment.
So Cantor's question was, are all sets the same size?
And he gives a definitive answer of no.
Cantor's theorem, which we're about the present,
will show that, in fact, there isn't any biggest infinity.
For any given infinity, you can find a bigger one
in a very simple way.
But let's begin by coming up with the simplest
form of Cantor's diagonal argument,
of how do you prove that a set is not countable?
Remember, a set is countable if you can list it,
possibly with repeats.
So A is countable if there is a sequence, a0, a1, a2, such
that every element in the set A shows
up at some time or other in the list, possibly more than once.
And the only things in the list are elements of A.
And we saw as an example that the finite bit strings,
the finite strings of zeroes and ones,
with the finite binary words, are
an example of a countable set.
And we claimed last time, and now we're
about to prove that the difference is
that if you look at the infinite bit strings-- One-way infinite.
They have a beginning, and they go on infinitely right.
The notation being 0, 1 to the omega,
where omega is an indication of one of the symbols
for a kind of infinity.
And this is going to be an example of an uncountable set.
How are we going to prove that?
Well, the setup for using a diagonal argument
is to think about drawing a matrix.
Suppose that I have some way of enumerating
the infinite binary sequences, the 0, 1 to the omega.
So there's a sequence s0, there's a sequence s1,
there's a sequence s2.
Let's lay them out as though they were the rows of a matrix.
So s0 is this infinite binary sequence, 0, 0; 1, 0;
and so on.
And the column labels are simply the coordinate labels for s0.
So this s0, 0; s0, 1; and so on.
s1 is the next infinite binary sequence
in this hypothetical list.
And it starts 0, 1, 1, 0, and goes on, and so on,
down the line.
So the row labels are this numeration of binary sequences.
And the column labels are coordinate labels.
And this is a matrix that's infinite to the right
an infinite down.
But it definitely has an upper left corner.
So the trick is to try to find an infinite binary
sequence that is not in this list,
that it differs from every row.
If I can do that, then I've shown
that any attempt to enumerate all
of the binary sequences in 0, 1 to the omega-- any sequence
like s0, s1, s2 of binary sequences
is missing something, which means you can't really list it.
Well, how do you find a sequence that's not here?
Well, pretty easy.
You look at the first digit.
And that was a 0.
So you choose the first digit of the new sequence
to be 1, the opposite of 0.
You choose the second digit to be
the opposite of the coordinate of a digit 1 of s1,
and complement that.
Now here, the digit 2 of S2 is a 0.
So let's make that a 1.
And the next one of the diagonal is a 0, and so on.
We're going to complement all of the bits along this diagonal.
So I get a diagonal sequence.
That's why this argument is called the diagonal argument.
Well, let's think about this diagonal sequence.
It just goes on, right down the diagonal of this two
dimensional infinite matrix.
What we can say about it is that it differs from every row.
Why is that?
Well, it differs from the 15th row at the 15th position,
or coordinate 15.
It differs from the 99th row at coordinate 99.
It's not in the matrix.
It's not a row of any matrix.
And that immediately tells you it's over.
Any attempt to list all of the elements in 0, 1 to the omega
is going to omit a diagonal element.
It's not possible to list all of them.
In other words, there isn't any surjection
from the non-negative integers to 0, 1 to the omega,
because I've just shown you how, if you give me
a surjection onto binary sequences, in effect,
I'm giving you with N a 0 sequence, a first sequence,
a second sequence, and so on.
Then I know exactly how to find something that's not there.
There can't be a surjection from N to 0, 1 to the omega.
It's just not true.
And that's why we can say that 0, 1 to the omega
is uncountable.
Definition of countable-- or an equivalent formulation
of countable, remember, is that there
is a surjection from the non-negative integers
to the set.
Well, there isn't any.
We just proved it.
So N is not surj 0, 1.
By the way, it's also quite easy to say
that there is a surjection from the infinite binary sequence
to the non-negative integers.
You could map a binary sequence to the coordinate
of the first one in it.
And that maps every infinite binary sequence
to a non-negative integer.
It hits every non-negative integer lots of times.
I hit five with a sequence that starts
with four zeros and a one.
The only sequence that doesn't go anywhere
is the all-zero sequence.
But by the way, if you check the definition of surj,
it doesn't require that the function be total.
Surj means that there is a function that
is a surjection to N. But there doesn't
have to be greater or equal one arrow out.
There just has to be less than or equal to one arrow
out, so it's a function.
But of course, it's easy enough to make it
total, the all-zero sequence.
Just map it to 0.
So now you have both the 0 and the sequence
that starts-- Any sequence that starts with 1
will all map to 0.
OK.
So if we remember our intuition, surj
is read as greater than or equal to.
So this tells us that the infinite binary sequences
are a larger set, at least as large a set
as the non-negative integers.
And the converse is true.
The non-negative integers are not at least as large
as the infinite binary sequences.
So we can really say that non-negative integers
are strictly smaller than the set of infinite binary
sequences.
Now, strictly smaller is in quotes
because, again, we don't know exactly what
the size of infinite sets is.
All we're doing we, really, is talking
about properties objections, bijections, surjections,
injections.
OK.
So let's make an explicit definition.
I'm going to say that A strict B means that there
is no surjection from A to B. So if we read A surjection
B intuitively, as A greater than or equal to B,
this is saying it's not true that A
is greater than or equal to B. Or in ordinary language
and thinking about sets, if it's not true
that you're greater than or equal to B,
you must be strictly less than B.
So that's the motivation for the word strict.
But remember, we're talking about infinite sets.
And we can't go around assuming too many properties of strict
until we've proved them.
One non-trivial property, by the way,
is I've defined strict that it's not true
that there is a surjection from A to B,
but I'm not insisting that there must
be a surjection from B to A, which would
be the second companion part.
That is, A is not greater than or equal to B,
and B is greater than or equal to A. Turns out, technically,
you can prove that.
If there isn't any surjection from A to B,
there will be a surjection from B to A.
But that's using a set theoretic argument that's not so obvious.
And we don't need it.
So this is the definition of strict.
A straight B means you cannot get a surjection from A to B.
And we're intuitively reading it as A is strictly smaller than
B. And what we've just shown then is that the non-negative
integers strict 0, 1 to the omega,
the infinite binary sequences.
OK, now Cantor's theorem is a wonderful generalization
of this.
It's a powerful generalization, but the proof is pretty much
the same, although it sometimes looks a little different
as it's written up.
And what Cantor's theorem says, it's
just beautifully elegant and simple.
It says simply that the power set is strictly
better than the set.
A strict power set of A, for every set A,
even if A is finite.
Because remember, if A is finite, say A has n elements,
then the power set of A has 2 the n elements.
And you could check that even for n equals 0,
n is less than or equal to the-- n is less than 2 to the n.
0 is less than 2 to the 0, which is 1.
2 is less than 2 squared, which is 4, and so on.
So even for finite sets, we have A strict power set of A.
But the cool thing is that it works even for infinite sets.
Let's take a look.
It's a diagonal argument again.
But now, I mustn't assume that A is countable.
I'm not going to assume that I can really
list the elements of A. But we'll think about it
as though we could.
Let's think about this matrix again.
So suppose A is this set of elements, a, b, s, t, d, e.
I'm scrambling up the alphabet on purpose,
because I don't want you to get the idea that we're assuming
that A is countable, that you can list all the elements of A.
I'm not assuming that.
But I'm just writing out a sample of elements of A.
And let's suppose that I was trying
to get a surjection from A to the power set of A.
So suppose I have a function f that maps each
of the successive elements of A to some subset of A. So f of a
is part of the power set.
It's a subset of capital A. f of b is a subset of capital A,
and so on.
And suppose I had a setup like this.
I'm going to draw a matrix that looks like the diagonal matrix.
And we're going to extract a diagonal set and discover that
that diagonal set is not one of the f's.
It's not f of anything, which means that f is not
going to be a surjection.
So let's look at it again.
So here's this matrix, where I'm labeling
the columns of the matrix by the elements of A.
No particular order here, but in order to draw a matrix,
I have to write them down in some order.
And likewise, the first row is going
to be f of this element a.
Well, what is in f of A? f of A is
going to be a set of elements.
So let's just write the elements in f
of A down, under the corresponding column label.
So here's an example, where f of A has an a and no b,
and has it has an s in it, no c, no d.
It has an e.
Likewise, f of b has an a and b, and no s or t,
but it's got a c, and so on.
So I filled in this matrix by taking
f of an element in A, which is supposed to be a subset of A,
and writing out all of the elements in that subset,
under the corresponding element of the subset.
So a b goes under a b if it's in f of c, and s goes under an s
if it's in f of c.
Nothing goes under a t if t is not in f of C.
And that's what we're seeing here.
So I'm laying out as though I was
using 0's and 1's for an infinite binary sequence.
I'm laying out each of the sets that
are in the range of f along this row.
And now with this setup, and I can define a new set,
which is not going to be an f.
How do I get that?
Well, what I'm going to do is in my new set
I'm not going to have any of the elements that
appear on the diagonal.
So if a is a member of f of A, that
means that a appears in this coordinate,
it's not going to be in my set.
If b is in f of b, meaning that b appears
in the f of b row under the column b,
it's not going to be in my set.
On the other hand, s is not in f of s,
because there's no s there.
So I'm going to put an s there in magenta.
And likewise, I'm going to stick elements
in or out the opposite of whether they
appear on the diagonal.
And this is going to give me a set D, which
is going to be my diagonal set.
So if we write this out, what we're
saying is suppose that I have a function f
from A to the power set of A. Then what I'm going to do
is define a subset of A that's not in the range of f,
namely set D, which is the set of those elements
in A, such that little a is not an f of a.
Namely, if an element appeared on the diagonal
because an element with column label A was in the row f of a,
then I left that out of my set.
And if it was not in that location in the matrix,
I put it in my set.
So I'm keeping all the elements that
aren't on the diagonal, that's my diagonal set D.
And what I know about it is that D is not in the range of f,
because it differs from every possible row of the matrix.
If the row is labeled with f of a as f of a,
then it differs in the column a, f of a from that row.
And therefore, my set D is not a row of this matrix.
And that means that it's not equal to f of anything.
So I've just found that there is no f arrow into D. D's not
in the range of f.
That means that if I had such an f from A to the power set of A,
it's not a surjection, because D is always left out.
So f is not a surjection.
And since, you know, f is any function from A
to the power set of A, none of them are surjections,
and that means there is no surjection from A to the power
set of A. In other words, A strict power set of A.
There is no surjection.
Now, a special case of this, of course,
is that the non-negative integers are strictly
smaller than the power set of N. Of course,
that's just an instance of Cantor's theorem.
We're applying A being the set of non-negative integers.
So there is no surjection from the non-negative integers
to the subsets of non-negative integers.
Again, that means that the power set of N
is an example of an uncountable set,
because the definition of countable
is that there would be a surjection from N
to power set of N. We're saying there isn't any,
so it's not countable.
Not countable is usually phrased as uncountable.
So the power set of N is maybe our second example
of an uncountable set, the first one
being the infinite sequences of binary numbers.
Now as a matter of fact, just as we had a general way
to prove countability-- you can show that a set is countable
if there is a surjection from a set you
know is countable onto the target,
then the target's countable.
Take the contrapositive of that lemma,
and you can say that if a set A is uncountable
and there is a surjection from C to A,
then C has to be uncountable.
That's just the contrapositive of the previous one.
If C was countable, then A would be countable.
So if A is uncountable, C must be uncountable.
So this gives us, again, a nice general way
to prove uncountability of sets, once I
have a couple in my repertoire.
Well, it means that we could have deduced
that 0, 1 to the omega, that the infinite binary sequences were
uncountable, because we know that there's is
a bijection between the infinite binary sequences
and the power set of N.
We described that bijection without knowing anything
about any other properties of the infinite binary sequences
in the power set of N, whether they were countable or not.
But now that Cantor's theorem tells us
that the power set of N is uncountable
and there's a bijection, the previous lemma says,
in particular, there's a surjection from 0, 1 to omega
to the power set of N, which means 0, 1 to the omega
is uncountable.
So what I'm illustrating then is that the proof that we used
directly by a diagonal argument to figure out
that 0, 1 to the omega was uncountable,
it's really a special case of the more general
diagonal argument that we used to prove Cantor's theorem.
And we get that 0, 1 to the omega
is uncountable as a consequence of Cantor's theorem
about the power set of N. And so we've got two different ways
then to prove that the infinite binary sequences are
uncountable.
Another example of an uncountable
set, it's the real numbers.
And they're a cute example.
Remember, we saw that the rational numbers
were countable.
The real numbers are uncountable.
Well, how do I prove that?
I'm just going to show you a surjection
from the real numbers onto the infinite binary sequences.
How am I going to do that?
Well, it's a kind of stupid trick, but it works.
I'm using both positive and negative reals.
So let's look at some real number,
and look at its binary representation,
so for the moment that it's positive.
So let's look at, say, the binary representation
of some number, like 3 and 1/3.
So that means that if we're thinking
of these as binary places, this is the 0's place,
the 2's place, the 4's place.
This is half's place, the quarter's place,
the eighth's place.
Then the binary representation of 3 and 1/3 would be 2.
And then this infinite repeating-- not decimal,
but [? bicipal-- ?] binary expansion, 010101.
And we will examine how I know that that's a third.
But take it for granted that that's
what you get as the repeated fraction.
You could figure that out by just doing division of 1
by 3 in binary.
Anyway, just as there's a decimal expansion
of every real number, there's a binary expansion just using
base 2.
So here's the binary expansion of 3 and 1/3.
So what I'm going to do is I'm going
to map 3 and 1/3 to this binary sequence.
I'm going to ignore the decimal place.
Binary is not decimal place.
It's a [? becimal ?] place, or binary position.
And I'm just going to take this to mapping
the sequence, 11010101.
And I claim that this is a surjection
because you're going to hit every possible binary
sequence in this way.
Well, almost.
Let's take a closer look.
There's a problem with mapping to things that start with 0,
because let's examine that a half is 0.10000000.
So I would map it to that.
And it will end.
But there's an ambiguity, because a half is also equal
to 0.011111, just as 0.999999 is equal to 1.000000 in decimal,
you get the same infinite carry issue here in binary.
So numbers that end in all ones have another way
to represent the very same number by a sequence that
ends in all zeroes.
So how am I going to hit-- if I'm
using up a half to hit this one, what's left to hit that one?
Oh, how about using minus 1/2?
It's there, and that's part of R,
so I'm just going to map the negative numbers
to the version of the expansion that starts with 0
and has an infinite number of ones.
And the positive one that ends with an infinite number
of zeroes.
And otherwise, I'm going to map plus and minus
numbers to the same place.
So this is going to give me the needed surjection from R
to the infinite binary sequences.
And by our previous lemma, that implies, sure enough,
that the real numbers are uncountable.