Lesson 3 Solutions

Exercise 1) If C is a subset of B, and B is a subset of A, then C is a subset of A. True or false?

Solution: True. Recall that in order to see if C is a subset of A, we need to ask if every element in C is also in A. Well, we know that B is a subset of A, so every element in B is in A. We also know that C is a subset of B, so every element in C is an element in B. So if you hand me an element of C, then I know it’s in B, and since it’s in B, I then know it’s in A. Since this is true for any element that you handed me in C, we have thus established that every element in C is also in A, so C is a subset of A.

This may have been obvious, but it’s a good example of what it means to be rigorous and detailed.

Exercise 2) It is hopefully clear that there are infinitely many 1-element sets “out there”. This is because $\{1\}, \{2\}, \{3\}, \{4\}$ , and so on are all one element sets, and this isn’t even including $\{\mathrm{cup}\}, \{\mathrm{table}\}, \{\mathrm{this\ chair}\},\{\mathrm{that\ chair}\}, \{\mathrm{that\ chair\ over\ there}\}, \{\mathrm{that\ other\ chair}\}, \{\mathrm{lion}\},$ and so on. Similarly, there are infinitely many 2 element sets, and infinitely many 3-element sets (and so on). The question is, then, how many $0$ element sets are there? (hint: I give away the answer somewhere in this lesson, but can you say why this is so?)

Solution: There is exactly one $0$ -element set. To show that this is the case, we employ a very common method of proof. Namely, we’ll show that there is one, and then we’ll suppose that there’s another. We’ll then show that this supposed “other” is in fact the same is the original one, and that therefore there can only be one.

We know that the empty set is a $0$ -element set, simply because that’s how it’s defined. Thus we know that there is at least one such set. Now let’s suppose that there’s another. We want to show that any other $0$ -element set is actually equal to the empty set. And how do we show that two sets are equal? We show that they have the exact same elements. Namely, we show that every element in one set is in the other, and every element in the other is also in the first. I.e., we show that they both “contain each other”, thus showing that they’re equal. In this proof we’ll rely heavily on the validity of vacuous truths, which you can read about in the post “Meaningless Truth”.

Let’s call the empty set $\emptyset$ and let’s call the other $0$ -element set that we’re supposing exists $A$ . We want to show that $\emptyset = A$ , and to do this we show that every element in $\emptyset$ is also in $A$ , and vice versa. Well, there are no elements in $\emptyset$ , so every element in it is vacuously in $A$ . In the exact same way—namely using the vacuously true statement that a $0$ -element set is a subset of every set—we conclude that every element in $A$ is also in $\emptyset$ . Thus these two sets are equal, and so there is only one $0$ -element set!

This is much more detailed than any solution to this problem requires, but it’s a nice setting for discussing this type of logic, which will be relied upon heavily in future lessons to derive much less trivial results.

Back to lesson 3

On to lesson 4