>> So, welcome back to another screencast on basic set operations and set theory. In this one, we're going to talk about a kind of mysterious idea called cardinality. On the surface of it, cardinality is actually pretty easy if you're working with finite sets. So, the cardinality of a finite set, A. And we're going to use the, it looks like absolute value notation, for A. It is the number of elements in A. Now, the key word here in this definition is finite. Okay? We have a finite set, A, where we could start counting the elements at the beginning and eventually we'll stop. Then the number of elements in that finite set is what we mean by the cardinality. So, for example, here are 4 examples, actually. The set consisting of A, B, and C. Its cardinality, you see there with the symbols there, is 3. Because there's 1, 2, 3 elements in it. Similarly, there are 1, 2, 3 elements in this set here, 2, 20, 200. This set here, the set of all natural numbers x such that x squared is less than 20. Its cardinality is 4. And why is that? Well, what's in that set? Let's write that out in roster notation and see. So, we're dealing with positive integers here, so 1 is in there, because 1 squared is less than 20. Two's in there, because 2 squared is less than 20. Three is there. Four is there, but that's it. So, it's 1, 2, 3, 4 elements for a cardinality of 4. The cardinality of the empty set is 0, because quite simply there's nothing in the empty set. So, that gives it a cardinality of 0. So, here's a quick concept check to possibly head off a frequently misunderstood idea about cardinality. So, suppose you have A and B are finite sets. And the cardinality of A is less than or equal to the cardinality of B. So, what does that mean about A and B themselves? Does that mean that A is the subset of B? That A is a proper subset of B? That B is a subset of A? That B is a proper subset of A? Or none of the above? The answer here is none of the above. And if that surprises you, then you've just got to be careful about what cardinality is. Cardinality is simply the number of elements in a set. So, if I know that a set, A, has let's say 2 elements. Let me just make one up. A is equal to the set consisting of the letters X and Y. So, that's got a cardinality of 2. And B is some set that has a slightly larger cardinality. Just because I know that 1 cardinality is less than the other, doesn't tell me anything about the elements themselves in the set. For example, I could let B be the number 3, 6, 9, and 12, okay? So, the cardinality of B is 4. The cardinality of A is 2. And those 2 cardinalities are less than or equal to each other. But A's not a subset of B. They're completely apples and oranges here. So, none of the above. Just by knowing the cardinalities of 2 sets and how they relate doesn't really tell us anything about the sets themselves. Now, the converse could possibly be true here. If A happens to be a subset of B, then it would certainly be true that the cardinality of A is less than or equal to the cardinality of B. But that's 1 direction of the conditional statement. The opposite direction does not necessarily hold, as you see here. So, we're dealing with finite sets here. You might be asking, well, what about infinite sets? Well, with infinite sets, it gets pretty complicated. And I want to just sort of get slightly into the weeds with you here with this idea about cardinality of infinite sets is not really something we're equipped to talk about yet. So, here's an example. The set of all natural numbers, right here, starting at 1. I've listed out the first 10. And a set I'm going to call 2N, just to represent the set of all even natural numbers. Now, on first blush, which set is bigger? N or 2N? Well, in one sense, N is way bigger than 2N. I mean, it's pretty clear that 2N is a proper subset of N. In fact, you should see, you know, somehow that the set of all natural numbers is "twice as big" as the set of all even natural numbers. But in fact, so you should say, like, the cardinality of N is bigger than the cardinality of 2N. It's got more elements in it. But it's more complicated than that. Because look at this. I can make a 1 to 1 correspondence between every element of N and every element of 2N just by lining them up like this. So, because I can connect every element of the natural numbers with every element of the even natural numbers in a 1 to 1 sort of way like this, then we should really say that N and 2N have the same number of elements. Have the same cardinality. And in fact, that's what we end up later on, we need to say. They have the same cardinality. Not because one has more elements than the other. Because pretty clearly N has a lot more, maybe twice as many elements as 2N. But they have the same cardinality, because I can construct a 1 to 1 pairing off of the elements in this way. So, they have the same cardinality, even though one's a proper subset of the other. And that's just kind of weird. So, like I said, it's complicated. It's even more complicated than that. Because think of something like the natural numbers and the rational numbers. Now, you'd have to say, well, surely to goodness the rational numbers is an enormous set. It's bigger than the integers, it's bigger than the natural numbers for sure. But it turns out that they have the same cardinality, too. And just to kind of illustrate why that is, let's just list the rational numbers in kind of an interesting way. And to simplify this, I'll look at only the positive rational numbers. Look at the positive rational numbers. I'll start with 1 here. I'll put 2 here, 3 here, 4 here. I'm going to make sort of a grid across here. And that extends infinitely this way. In the second row of the grid, I'm going to put 1/2, 2/2, 3/2, 4/2, 5/2, 6/2, and so on. And in this third row, I'm going to put 1/3, 2/3, 3/3, and you can kind of see what I'm doing here, 4/3, 5/3, and so on. And the next row will be 1/4, 2/4, and you kind of get the picture here. So, if I keep creating this grid, I'm actually going to end up covering all the positive rational numbers at some point in this grid here. And it'll extend infinitely this way, as well. Now, a lot of these are double counted. For example, 2/2 and 1 are really the same number here. But at least the positive rational numbers are all included in this list here. And so, but the way I've listed it here in a grid, I can actually go through and attach a natural number to every one of these rational numbers, like so. I'm going to pair off this one with 1. This one with 2. This one with 3. This one with 4. Skip that one. This one with 5. This one with 6. This one with 7, 8, 9. And so, you can see what I'm doing here is I'm able to, by going kind of up through the diagonals like this, I can list off each of these positive rational numbers and pair it off with a natural number. So, actually, the natural numbers and the positive rational numbers, which I'll denote with a little plus there, have the same cardinality. Even though the positive rationals is in some sense enormously much larger than the natural numbers. They have the same cardinality. So, we don't want to think of cardinality as just merely being the number of elements in a set. Because that works for finite sets. But for infinite sets, it goes completely off the charts here. So, to talk about the cardinality of infinite sets, we need the idea of a function, which is coming up in the next chapter. So, cardinality is useful for us here and now in the finite set case just by counting the number of elements in the set. But again, that's only for finite sets. Thanks for watching.