PROFESSOR: Cardinality is the word
that's used to refer to the size of infinite sets.
And before we go further, let's take a quick look
at why we're interested in infinite sets
in a course that's Mathematics for Computer Scientists.
Why does computer science care about infinite sets?
Well, like every data structure that you'd
examine in computer memory is finite
and the integers individually are finite,
you only calculate with finite things.
But, the infinite abstraction happens right at the beginning.
Although any given integer is finite, the set of all integers
is infinite.
And although any given matrix is finite,
the set of all the matrices that might
be represented in a computation are an infinite set.
So, we take infinite sets for granted and reason
about them all the time.
The second, from a pedagogical point of view,
introducing the concept of infinite sets
and reasoning about them carefully
forces you to go beyond your intuition
and really follow the rules and reason
in a careful mathematical way.
Because although some properties that you're familiar with from
finite sets carry over to infinite sets, others don't.
And in order to know which is which,
you have to be thinking carefully about the rules
and properties that they have, as opposed
to just going by intuition and familiar properties.
And finally, the reasoning that goes
into comparing the sizes of infinite sets, which
is the topic of today's video, has profound implications
in computer science because it leads
to the insight about the logical limits of computation
and examples of specific problems
that computers can't solve, which we'll
be taking up in a later video.
But for now, let's go back to the topic of cardinality.
So, there was this mathematician in the late 19th century
named Cantor who was actually working on Fourier's series.
And he discovered that the kind of series
that he was working with diverged
in infinitely many places, which sounds kind of bad.
But he wanted to get across the idea
that it didn't diverge in very many infinite places.
And that led him to this idea of comparing
the sizes of infinite sets.
So, this is Cantor's idea.
We know from the mapping dilemma that if you're
looking at finite sets A and B, then the size of A
is greater than or equal to the size of B
if and only if A surj B, were surj
is this technical relation which means there exists a surjection
function from A to B that is a function with greater
than or equal to one arrow into every element of B.
And Cantor's idea was saying, well,
it works fine for finite sets.
Why don't we take this as the definition of what we mean by A
is at least the size of B for infinite sets?
So, we're going to think of A surj B
now as saying, A is as big as B. And for finite sets,
it's literally true that A surj B if and only if the size of A
is greater or equal to the size of B.
Now, let me take a moment to say that this notion of size
or cardinality, when you're talking about infinite sets,
it's kind of a no-no.
There's an abstract concept of what cardinal numbers are, what
these infinite numbers are.
But the truth is, they're technical and not of very much
use.
So, we will never actually be talking about the cardinality
or size of an infinite set.
But what we will do is compare them.
We're going to have a nice elementary theory of the idea
that the cardinality of one set is
greater than or equal to the cardinality of another set.
And the basic definition is going to be based on surj.
Similarly, bijection is even easier.
A bij B means that there's a bijection from A to B.
And we're going to interpret that
as saying that A and B are the same size.
That is, for finite sets, it literally means A
and B have the same number of elements.
We're going to adopt the notion of a bijective relation
for infinite sets as meaning, I don't know what their size is,
but I know it's the same because there's
a bijection between them.
There's a perfect one to one correspondence between As
and Bs.
Let's look at an example of where bijection comes up.
The power set of N-- if N is the non-negative integers--
the power set of N is all the subsets
of non-negative integers.
And let me just remark that there is an obvious bijection
between the subsets of integers and the infinite bit-strings,
the infinite strings of zeroes and ones.
So, N is the set of non-negative integers, 0, 1, 2.
If you take any subset of N, here's one with has 0,
missing 1, has 2 and 3, missing 4, 5, has 6,
and so on, then what I can do is represent such a subset,
possibly an infinite subset now, by an infinite sequence
of ones and zeros.
Put in ones in the position where elements in the subset
occur and zeroes in positions where elements don't occur.
This was exactly the same bijection
that we had found between the non-negative-- the bit-strings
and the finite subsets of the non-negative integers.
But now, we're just extending it to arbitrary subsets
of the non-negative integers.
So, this defines a bijection between any subset
of integers corresponds to an infinite bit-strings.
And conversely, from any infinite bit-string,
you can reconstruct what subset it refers to.
So, we use this notation [? 0,1 ?] to the omega,
meaning the infinite bit-strings that are infinite to the right.
They have a beginning.
In comparison to [? 0,1 ?] superscript star,
which refers to the finite sets of bit-strings.
So now, let's examine the standard size properties
that you would expect if these relationships of surj and bij
behaved like relationships between sizes.
So, one basic property that finite sizes have
is that if A is equal to B and B is equal to C in size,
then the size of A and the size of C are the same.
That's certainly true for finite sets.
Does it hold for infinite sets, where now equality is
going to be replaced by bij?
Well, we have to check it.
Is it true that if A bij B and B bij C implies A bij C, well,
how do you prove that?
Well, it's true, and here's how.
By definition, since A bij B, that
means that you have a bijection g from A to B.
And since B bij C, you have a bijection f from B to C. Now,
I need from these two bijections that I'm
given, I need to find a bijection between A and C.
Well, that's easy.
What you do is you use g to go from A to B,
and then you use f to go from B to C. And you compose them,
and that gives you the needed bijection from A to C. So,
define h to be the composition of f and g.
And it's easy to check that if g and f are bijections, then
their composition is a bijection.
So, that's how I find the needed bijection from A to C. So,
this property works out just fine.
The similar property applies to at least as big as,
greater than or equal to.
For finite sets, if A is greater than or equal to B
and B is greater than or equal to C in size,
then A is greater than or equal to C.
And actually, the same argument that worked for bij
works for surj, because the composition
of surjective functions is a surjective function.
So, if A surj B and B surj C implies A surj C.
Now again remember, although we're thinking of surj
as meaning greater than or equal to in size,
you cannot take these size properties for granted.
They have to be proved.
Surj has a technical definition having
to do with surjective functions, functions with greater
than or equal to one arrow in.
That is not the same as talking about equality
of some kind of sizes.
Well, let's look at an example where the size properties hold
but they're less obvious.
Because here's another familiar size property.
If A and B are each of size greater than
or equal to the other one, then they're the same size.
So, if the size of A is greater than or equal to the size of B
and the size of B is greater than or equal to the size of A,
then A and B are the same size.
Now, this is certainly true for finite sets.
It's kind of, you don't even think about that fact.
And it holds for infinite sets.
But, it's not so obvious.
So, what we're saying is that if I have a surjective function
from A to B and I have another surjective function from B
to A, then there's a bijection between A and B.
And the problem here is that this surjection from A to B
might not be a bijection.
And this surjection from B to A might also not be a bijection.
So, where's the bijection going to come from?
I have to build it.
And so, this is not an obvious property, it's true.
It's called the Schroeder-Bernstein Theorem.
And the trick, basically, is you take the bijection from A to B
and the bijection from B to A and you take parts of one
and combine it with parts of the other.
And in a slightly ingenious way that
actually is contained in a problem in the text,
you can find the bijection from A to B,
but it does take a little bit of ingenuity.
So this is a size property that works for surj and bij,
but you can't say it's obvious.
Well, let's look at an unfamiliar size property.
Something that's not true of finite sets
where we have to start being careful and not just hand wave
and use our intuition about finite sets.
Namely, for infinite sizes, size plus 1 is equal to size.
Now, what exactly does that mean?
Well, let's just illustrate it with an example.
In fact, in some ways, you can the definition
of an infinite set is that its size plus 1
is equal to its size.
Let's look at a simple example.
So, on the bottom, I have the non-negative integers.
And on the top, I have the positive integers.
So, I can get from the positive integers
to the non-negative integers just by throwing in zero.
So, that's where the plus one comes from.
Here's a nice infinite set.
I add another element to it, and I get another infinite set,
but they are the same size.
I have to show a bijection between them
to show they're the set size.
Well, you know what the bijection is.
Map 0 to 1, 1 to 2, 2 to 3.
This is a bijection which you know as the add one function.
The add one function maps the non-negative integers
to the positive integers, and it's a perfect bijection.
Therefore, adding one element to the non-negative integers--
to the positive integers does not get me a larger set,
it gets me another set of the same size.
And this argument actually generalizes
to any infinite set.
If you throw in one extra element,
you could still find a bijection between the original set
and the set with one extra element.
So, N is the same size as the positive integers.
Well, in fact, let's look at this one.
I can enumerate on the top all the integers,
both positive and negative.
0, 1, minus 1, 2, minus 2, and so on.
And that gives me the set consisting of all the integers.
And over here, I can have 0, 1, 2,
just the non-negative integers.
And you can see the orderly way in which I've
listed the integers at the top.
That implicitly defines a bijection.
I'm going to map zero to the zeroeth element of the sequence
above.
1 to 1, 2 to minus 1, 3 to 2, 4 to minus 2.
And in this way, I have actually defined
a bijection between the non-negative integers and all
the integers.
In other words, you take half of the integers, namely
the non-negative integers, and it's still
the same size as all of them.
There's a bijection between N and Z.
Now, you could write a formula, actually,
if you were trying to figure out what does the number N go to?
What positive or negative integer?
There's some not very hard formula involving
dividing N by two and rounding.
But, that doesn't matter.
Once I've figured out some sensible way
to list all the elements of the integers in a row,
then I can wind them up against the non-negative integers.
And that listing, in effect, defines the mapping
in a perfectly clear way without necessarily having a formula.