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.