PROFESSOR: So we're finally ready to tie up these ideas about mapping properties to counting properties. And let's begin with the remark we already made, that if there's a bijection from one set to another, if there's a bijection from a finite set A to a finite set B, then A and B have the same size. By the way, those vertical bars, absolute value of A, when it's a set refers us to the size of the set for finite sets. So it means if A has n elements, then the absolute value of A is n.
OK. Let's use this bijection idea immediately. Here's a nice example. Suppose you want to figure out how many subsets are there of a finite set A? Suppose you didn't know yet. All right. So what we're asking about is, what's the size of the power set of A? Remember the power set of A is all of the possible subsets of the set A. Well suppose A has three elements. What is the power set of A look like? If capital A has elements little a,b,c. It's a set of size three. Then the power set of A is going to have one subset with no elements, three subsets with one element, they're listed there. It's going to have three more subsets with two elements, and one subset with three elements. For a total of eight subsets in the power set of A.
So let's see what the counting argument in general would be. So suppose that A has n elements. And we'll number them from a 0 up through a n minus 1, because computer scientists usually zero origin index. So A is a set of n elements, indicated there. Suppose I have some arbitrary subset of A. Let's suppose that it has a 0, then there's no a 1, that's what this space is for. It has a 2. It has a 3. Doesn't have a 4.
And it goes on for awhile in some uncertain way. And it ends it actually has the last element a and minus 1 in it. Well I can take the subset like this and have it correspond to a bit-string, where I put a 1 where the element is there in the subset, and a 0 where the element is not there in the subset. So there's a 1 because a 0 is in the subset followed by a 0, because a 1 is not in the subset, followed by two 1's because a 2 and a 3 are in the subset, followed by a 0 because a 4 is not, and so on, ending with a 1, because a n minus 1 is in the subset.
So in short, the bit-string the [? case ?] bit in the string is 1, if and only if, a sub k is in the set. Now this clearly defines a bijection between subsets and strings. Because given a subset, I can uniquely determine the string, and given the string, I can uniquely determine the subset. So there's one arrow in and one arrow out of each of those things. So I could immediately conclude then by this bijection theorem that the number of n bit-strings is equal to the size of the power set of A. Well, now every computer scientist knows how many n bit-strings there are, right? There are 2 to the n n-bit bit-strings. And therefore, the power set of A has 2 to the n elements. We can get rid of the n because it was the size of A.
We have this nice formula. The power set-- the size of the power set of a finite set A is 2 to the size of A. Well there are some more counting rules like the bijection rule that relates sizes of sets by inequalities according to whether the mappings are surjective injective functions and so on. So let's take a quick look at those.
Suppose that I have a surjective function from A to B. Well that means there's less than or equal to 1 arrow out of every element of A, that's what function means. And there is greater than or equal to 1 arrow in to every element of B. That's what surjective means. So here's this function from A to B. That means less than or equal to 1 arrow out. And that means that there have to be more elements in A than there are arrows since there's at most, one arrow out of every element of A and that accounts for all the arrows.
So the size of A has to be greater than or equal to the number of arrows when you have a partial function. When it's a surjection, that means that there's an arrow coming into every element of B. That means that there have to be at least as many arrows as there are in B. Because everything in B has at least one arrow coming in. So if you look at these two pieces, the size of A has to be greater than or equal to the number of arrows. And the size of B has to be less than or equal to the number of arrows. Putting them together, we have the mapping rule for surjections.
If I have a surjective function from A to B it means the size of A is greater than or equal to the size of B for finite A and B. The same argument goes for injections. With an injection, I have less than or equal to 1 arrow in. And what does that tell me? Well if it's total, then there's at least 1 arrow out of everything. And that means that the size of A has to be less than or equal to the number of arrows. Because every element in A contributes an arrow, maybe more than one.
OK. If it's an injection, there's less than or equal to 1 arrow coming into each element of B. That means that B had better be big enough to catch all the arrows. So the number of arrows has to be less than or equal to the size of B. Put those two inequalities together and you find that if you have a total injective relation from A to B, that implies that the size of A is less than or equal to the size of B for finite A and B. The statement here that it's a totally injective relation is for generality. But the truth is, whenever there's a total injective relation there's also a totally injective function.
I'll leave that to a class exercise to work out. So to summarize, what we can do is characterize these kinds of jection relations between sets. So let's define A bij B. So this is going to be a binary relation between two sets A and B. And its meaning is that there's a bijection from A to B. So the definition of bij is a binary relation where the domain and the co domain are the class of finite sets or all sets for that matter. surj B, A surj B means that there is a surjective function from A to B. Again, surj is a binary relation between sets. And finally, A inj B says, there's a total injection relation from A to B. So we have those three relations between sets.
And what we've just shown is that if there's a bijection between A and B, that's true, implies that the size of A is equal to the size of B. And in fact, it's not hard to prove the converse. If the size of A and the size of B are the same, then it's easy enough to find a bijection between them. Similarly, if there's a surjection from A to B, that's true, if and only if, the size of A is greater than or equal to the size of B. And if there's an injection from A to B, that's true, if and only if, the size of A is less than or equal to the size of B.
So this-- the existence of these kinds of relations between sets is a handle on their relative sizes. And this applies for finite sets A and B. Because we really know what the size of infinite sets are. So it wouldn't make sense to talk about the mapping Lemma for infinite sets. However, we can ask some questions about infinite sets. So one natural question to ask is, let's look at some finite properties. If the size of A and B are the same and the size of B and C are the same, obviously, the size of A and C are the same. And that corresponds directly to an insertion about bij because the size of A equals the size of B, for finite sets, is the same as A bij B.
So what this says is that if A bij B and B bij C, then A bij C. If there's a bijection from A to B and a bijection from B to C, then there's a bijection from A to C. Corresponding property for finite sets, again, is greater than or equal to-- if A is greater than or equal to B greater than or equal to C, then A is-- the size of A is greater than or equal to the size of C. And that would correspond to a similar statement about the surjection relation, A surj B, B surj C, implies A surj C.
And finally, more interesting one, is that if A and B are each greater than or equal to each other, if A is greater than or equal to B and B-- the size of B is greater than or equal to A, then in fact, they're the same size. A is equal to B. That would correspond to the following statement in terms of jections, if A surj B and B surj A, then A bij B. Now all of these facts follow immediately for finite sets A and B. But we're going to be interested in whether they hold for infinite sets. So they follow immediately for finite sets from the Mapping Lemma because the Mapping Lemma says that these bij and surj relations are the same is equal and greater than or equal to [INAUDIBLE].
So again, this is immediate from the Mapping Lemma. But now I can ask whether or not these same properties hold for infinite sets. It's an exercise in reasoning about properties of mappings and relations. And the answer is that the first two claims go through easily if you're trying to prove them for finite sets, for infinite sets, the basic ideas. Let's look at the first one. It says that if A-- If there's a bijection from A to B and there's a bijection from B to C, then there ought to be one from A to C. How do you find it?
Well it's actually easy. You just compose the bijection from A to B with the bijection from B to C. And it's a very easy exercise that the composition of bijection is a bijection. Likewise, the composition of surjections is a surjection. And that proves the second claim easily. But the third claim is much more interesting and is not obvious. It's called the Schroeder-Bernstein theorem. And it will come up a little bit in a few more lectures.