In lesson 2 we defined and discussed sets, and in lesson 3 we studied subsets of those sets. We now go on to study the notion of “sets of sets”, which not only is an extremely powerful mathematical tool, but also is the tip of an incredibly difficult mathematical iceberg. In other words, the idea of “sets of sets” is not only extremely useful, but also extremely problematic (at times). After exploring this idea for a bit, we’ll see where the trouble comes from in this lesson and the next one.
So what is a set of sets? As usual, it is exactly what it sounds like: a set whose elements are themselves sets. Okay, I know this might seem a bit strange and a bit too abstract, so let’s take this slowly (because it’s extremely important). We begin by recalling what we need to make a set. Namely, all we need is a collection of distinct “things” which we call elements. As discussed before, elements could be numbers, or donkeys, or ideas, or some combination of any of these and anything else that you can think of. Accordingly, we can think of a set itself as a single element of some other set. After all, a set is a “thing”, and we have a well-defined notion of when two sets are distinct from each other. Therefore we are perfectly able to consider a set whose individual, indivisible elements are entire sets. Let us look at some examples.
Our first example will seem kind of tedious and unnecessary, but it will truly illustrate the power of the idea of “sets of sets”, and it will hopefully make clearer the distinction between elements, sets, subsets, and sets of sets. Let us consider the following two sets: and . Note the nested brackets! The brackets are nested this way because a) we’re using the set notation that we’ve developed over the last couple of lessons and b) the elements of SET2 are themselves sets, subject to the same notation. SET2’s individual elements are the sets . Thus, if we were to ask whether or not SET1=SET2, the answer would be no. For these two sets to be equal, we’d need all of the elements in SET1 to be in SET2, and vice versa. In fact, these two sets could hardly be less equal! The reason for this is that none of the elements in SET1 are in SET2, and none of the elements in SET2 are in SET1. For example, the element “1” is in SET1, but it is not in SET2 because SET2 has 3 elements, and none of them are “1”. Of course, the element in SET2 is a set which contains the element “1”, but that most certainly does not mean that the element in SET2 is “1”.
Similarly, SET1 is not the same set as , because the elements “5” and “6” in SET1 are not in SET3. Moreover, the element “” in SET3 is not in SET1. Finally, I leave it to you to make sense of why and are not the same sets. (Hint: is the element “” of SET2 in SET4? Is the element “” of SET4 in SET2? Hint for Hint: No and no.)
We’ll now take our second example as an opportunity to make a useful mathematical definition. As we saw in lesson 3, any finite set has a certain finite number of distinct subsets. In particular, we saw that if a set has elements, then it also has distinct subsets (recall what “” means from lesson 3). We can now formulate this precisely by using our notion of a set of sets. Recall that a subset of a set is itself a perfectly good set. Thus, we can define the set of subsets of a given set. In other words, if we have some set and we call it A, then we can define the set of all subsets of A, and we call this new set the power-set of A. We note that the individual elements of the power-set of A are distinct subsets of A. This definition makes sense because we know how to tell when two subsets are distinct or not. Accordingly, using this new terminology, the pattern that we derived in lesson 3 is simply that if a set has elements, then its power set has elements. The difference is that the elements of these two sets are of a completely different type—the elements of the set itself are whatever they were to begin with (apples, donkeys, numbers, or whatever), and the elements of the power set are subsets of the set.
For example, consider the following set: . From the pattern derived in lesson 3, we know that there should be 8 (which is ) distinct subsets of this set, and indeed there are. Now, however, we have the mental machinery to be able to write down these subsets as elements of the power set of A. Let’s denote the power set of by (remember, it’s just notation, and we’re having stand for “the power set of whatever is in the parentheses”). If we denote the empty set by , then we have the following expression for :
Thus, one element of is and another is and yet another is . There are indeed 8 elements in .
The power set is just one example of a “set of sets”, but it is a particularly nice example because it is created “from” another set. In other words, if we’re given any set A, we can always form the set of all of A’s subsets. But of course we’re not limited to power sets when we’re considering sets of sets. I can take a set of apples, a set of oranges, and a set of bananas, and then form another set simply by considering each one of my sets of fruit as a single element of a 3-element set. While there’s nothing wrong with that, it also isn’t particularly interesting.
This provides a great stopping point for this lesson, because it allows me to make another note on what mathematics is “really” all about. We’ve already seen that mathematics is the art form in which precise definitions are made and their logical consequences are studied. It is a true “art” form, though, because some of these consequences and constructions are more interesting—and hence more beautiful—than others, and it is the artist’s job to uncover this beauty. In the next lesson, we’ll see a quite remarkable conclusion that we’ve been moving towards; one that will show us that the world of mathematics is more subtle than we could possibly know.
As always, the exercises are optional. There are no grades here, and no tests. Some of these just might be fun to think about.
1) Let and let . How many elements does A have? How many elements does B have? Does A=B?
2) Knowing that a set with elements has a power set with elements, how many elements does the power set of the power set have? In the notation of letting denote the power set of , the question is to find the number of elements in . (hint: what if where M is some other number?)