Lesson 4: Sets of Sets

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: $SET1=\{1, 2, 3, 4, 5, 6\},$ and $SET2=\{\{1, 2\}, \{3,4\}, \{5,6\}\}$ . 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 $\{1, 2\}, \{3, 4\}, \{5,6\}$ . 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 $\{1, 2\}$ in SET2 is a set which contains the element “1”, but that most certainly does not mean that the element $\{1, 2\}$ in SET2 is “1”.

Similarly, SET1 is not the same set as $SET3=\{1, 2, 3, 4, \{5,6\}\}$ , because the elements “5” and “6” in SET1 are not in SET3. Moreover, the element “ $\{5, 6\}$ ” in SET3 is not in SET1. Finally, I leave it to you to make sense of why $SET2$ and $SET4=\{\{1, 2, 3\}, \{4, 5, 6\}\}$ are not the same sets. (Hint: is the element “ $\{1, 2\}$ ” of SET2 in SET4? Is the element “ $\{1, 2, 3\}$ ” 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 $N$ elements, then it also has $2^N$ distinct subsets (recall what “ $2^N$ ” 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 $N$ elements, then its power set has $2^N$ 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: $A=\{a,b,c\}$ . From the pattern derived in lesson 3, we know that there should be 8 (which is $2^3$ ) 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 $A$ by $P(A)$ (remember, it’s just notation, and we’re having $P()$ 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 $P(A)$ :

$P(A)=\{\{a,b,c\},\{a,b\},\{a,c\},\{b,c\},\{a\},\{b\},\{c\},\{\}\}$

Thus, one element of $P(A)$ is $\{a,b\},$ and another is $\{a,b,c\},$ and yet another is $\{\}$ . There are indeed 8 elements in $P(A)$ .

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.

Exercises:

1) Let $A=\{1,2,3,4,5\}$ and let $B=\{\{1,2\},\{3,4\},\{5\}\}$ . How many elements does A have? How many elements does B have? Does A=B?

2) Knowing that a set with $N$ elements has a power set with $2^N$ elements, how many elements does the power set of the power set have? In the notation of letting $P(A)$ denote the power set of $A$ , the question is to find the number of elements in $P(P(A))$ . (hint: what if $N=2^M$ where M is some other number?)

Solutions to Exercises

Next Lesson

Previous Lesson

9 Responses to Lesson 4: Sets of Sets

Anonymous says:

April 24, 2014 at 9:10 pm

“(Hint: is the element “\{1, 2\}” of SET2 in SET4? Is the element “\{1, 2, 3\}” of SET4 in SET2? Hint for Hint: No and no.)”
Very subtle!

- TrueBeautyOfMath says:
  
  May 1, 2014 at 1:31 am
  
  Indeed! Subtlety is not always my strong suit 😉
  
b007e says:

August 2, 2015 at 6:18 pm

Question 1: Set A has 5 elements, set B has 3 elements and, no A is a distinct set from B.

Question 2: This took me awhile and I had to use some pen and paper to write it out, but it works for at least two of the models. Where M is the number of terms in the power set of the power set and N is the number of terms in the power set and P is the power to which 2 is at to describe the number of terms in the power set:
M = N x P – (0.25N)^2
if N >1

- TrueBeautyOfMath says:
  
  September 21, 2015 at 12:21 am
  
  Question 1 is spot on, but there’s actually an even simpler answer to question 2. It’s tough to compute explicitly, because of A has 2 elements than P(P(A)) has 16 elements, if A has 3 elements then P(P(A)) has 256 elements, and if A has 4 elements then P(P(A)) has 65,536 elements (and these numbers keep getting WAY larger as the size of A grows). That said, there is a nice, simple pattern that describes this that comes from applying what we did in this lesson twice.
  
57biotechcado says:

November 18, 2015 at 7:05 pm

Let A=\{1,2,3,4,5\} and let B=\{\{1,2\},\{3,4\},\{5\}\}.

>> How many elements does A have?

>>> Set A does have 5 elements.

>> How many elements does B have?

>>> Set B does have 3 elements, being the three of them sets with different elements.

>> Does A=B?

>>> The sets are not equal, the first set, namely A, does have five elements, different from the set B that does have 3 elements, the latter being sets .

2 – – Knowing that a set with N elements has a power set with 2^N elements.

>> how many elements does the power set of the power set have?

1st — I am going to use the model given at the lesson –> P(A) = ((2)**(N));

2nd — there is an explicit relationship shown at the question as a hint, N = 2**M;
( where M would be taken as the number of elements in a given set)

3rd — Uniting the latter gives that…

P(P(A)) = (2)**((2)**M)

- TrueBeautyOfMath says:
  
  January 29, 2016 at 2:09 pm
  
  Sorry for my late reply on this, but this answer is perfect! Absolutely perfect. Not only is it correct, it is also explained perfectly. Well done!
  
Erick says:

September 3, 2016 at 3:45 pm

Hi, im not sure if you’re still keeping track of the comments anymore, but I’m curious about something. You mentioned that, like an artist, the mathematician’s job is to discover beautiful truths from our initial definitions. How do you get better at this? I feel that if it wasn’t for your guidance throughout I wouldn’t discover anything particularly interesting conclusions. Also how do you know that your conclusions are more interesting than others?

- TrueBeautyOfMath says:
  
  September 21, 2016 at 9:58 am
  
  Hi Erick,
  
  Sorry for my crazy lateness on this reply! I am indeed still keeping track of comments (though slowly, clearly! 🙂 ) and am currently working quite hard on Volume 2. Your questions are indeed great questions, and cuts exactly to the core of what it REALLY means to do math. Namely, if you were taking piano lessons, the analogous question would be to ask your teacher: “how do I make more beautiful music?”…To which the short answer would, of course, be…practice! Now, what “practice” actually means is the million dollar question, because in music it most certainly does not mean “practice your scales over and over and over again.” As mentioned in various places on this site and in the book, “scales” are of course important, but to start CREATING beautiful music (or math) one must do more than the drills. One must spend a great deal of time reading great math (the analogue of listening to great music) and internalizing it—mastering it to the point where it becomes a part of your intuition.
  
  One must also experiment and play around with various ideas. This in fact answers your question about how we know some conclusions are more interesting than others—the answer is simply that by playing around with others we see that the results are not as elegant or simple or profound or what have you than those that some other set of definitions might give. Of course, truly amazing results can still arise even in this scenario, where one set of results can be derived painstakingly and tediously from one set of definitions, and easily and elegantly from another set of definitions: does this make one set “correct”? What if some results are easier in one set of definitions and harder in another set of definitions, while some other results are easier in the latter set and harder in the former set? Might there be some better definitions that encapsulate ALL of these results elegantly?
  
  The results that I present on this site and in the book(s) are the product of years, decades, and sometimes centuries of very hard work by very many brilliant mathematicians, and getting to the point where one can start finding new beautiful mathematical results on their takes just as much time as it would for a budding musician to be able to start writing new, beautiful music of her own. It requires years of dedicated work, lots of trial and error, lots of failure (with some successes as well), and lots of experimentation. The goal of this site and the book(s), however, is to show what ACTUALLY is out there to be done, and show that one can indeed CREATE mathematics in a world of math far more diverse than high school would have us think. To actually become good/great at this art form that we are now aware of takes just the same kind of approach as any art form. But the first step (in my opinion) is realizing that it is an art form, and approaching it with the same kind of patience, respect, and awe.
  
  I hope that helps/answers your questions. Let me know if not and I’ll happily try again! 🙂 And I hope you keep enjoying the site and commenting!
  
Anonymous says:

May 15, 2017 at 10:46 pm

This site is fucking amazing, thanks for giving us this nice present.