Lesson 3: Subsets

In lesson 2 we defined and became comfortable with the notion of sets. To recap, a set is just a collection of elements, and elements are just “things”. Therefore, sets are essentially just collections of things. Of course, there were some technical details that we had to iron out, especially with how we write sets. In particular, we can label the sets however we like: A, B, C, THIS, THAT, DONKEY, SET, WHATEVER. This labeling is just shorthand notation for the abstract set itself. Thus, if we want to talk about the set of positive whole numbers, we can label this set by A (or B or DONKEY) and then just talk about A, remembering what it “stands for”. Namely, if we also let B stand for the set of all whole numbers that are greater than 0, then we have that A=B, which is just shorthand for “the set of positive whole numbers is equal to the set of whole numbers greater than 0”, which is true.

Finally, we let ourselves label the elements in the set using the brackets “{}”. Thus, according to the previous paragraph, we have that $A=\{\mathrm{positive\ whole\ numbers}\}$ and $B=\{\mathrm{whole\ numbers\ greater\ than\ 0}\}$ and that $\{\mathrm{positive\ whole\ numbers}\}=\{\mathrm{whole\ numbers\ greater\ than\ 0}\}$ . All of this is just different shorthand notation for the same abstract ideas. Moreover, all of this might have seemed relatively trivial and/or obvious, and in no way related to math. But alas! This is math. Math is the study of sets! Well, at least a lot of math is. Moreover, these “trivialities” will eventually lead us into some deep and profound trouble, thus showing that these ideas are in fact highly non-trivial. (The solution to the second exercise of lesson 2 is closely related to this trouble, and we’ll address it in due time. For now, just be patient.) Thus, we must pay attention!

Let us therefore venture into new territory—namely, let us try to understand the notion of subsets.

Subsets are exactly what they sound like: they are “sub” other sets. If we are given some set—call it A—then a subset is just another set whose elements are all in A. Let us make a formal definition.

Definition 3.1 Given a set called A (we can call it whatever we like), a subset of A, call it B, is a set such that every element in B is also in A. //

Let us discuss a few important points. First of all, the subset of A which we called B is itself a set. Namely, it is a perfectly well defined collection of elements. Another extremely important point that we need to make is that for any set A, A is a subset of itself! Why is this? Well, by the definition of a subset, a subset is just some set whose elements all lie in some other set. Moreover, all of the elements in A certainly lie in A, so A is a subset of itself! There are two things to note here. One is that this is a perfectly logical construction—there is no reason why A can’t be a subset of itself. The second noteworthy fact is that we were forced to make this conclusion simply by the definition of a subset. We could of course change our definition and be led to other conclusions, but this definition is actually very useful. This illustrates a large part, if not all of what mathematics is: the formulation of precise definitions and the study of the inevitable logical conclusions to which they lead.

Let us now discuss an extremely important set, known as “the empty set”. Again, this is just exactly what it sounds like: the set that is empty. Recall that the definition of a set was just a collection of distinct elements. Well, the empty set is a perfectly good collection of distinct elements—it is the collection of no elements!

For now, and for a while, the notion of an empty set might seem pretty absurd, but it actually leads to so much logical beauty and consistency within higher mathematics (some of which we’ll see in much later lessons) that it proves to be a notion that we can’t do away with. Draw whatever philosophical conclusions you’d like from this, but no matter what, the empty set is real! Moreover, every set has the empty set as a subset. We can see this by remembering what it takes for one set to be a subset of another. Suppose we’re given a set A (any set, any set at all) and let us ask whether or not the empty set is a subset of it. What we need is for every element of the empty set to be an element of A. Well, there are no elements of the empty set, so we can truthfully say that there is no element of the empty set that is not also an element of A. This is an example of a vacuous statement (i.e., of a meaningless truth), and for more details on vacuous statements you can check out this note.

Let us get our heads out of the clouds with all of this “set and subset” nonsense and do something fun and concrete. Let us answer the following question: given a set with a finite number of elements in it, how many distinct subsets does it have?

This is indeed an interesting question, but before we answer it let us first consider why we had to ask it in the way that we did. First, why did we limit ourselves to finite sets? This is so that we can get a finite number of distinct subsets. In particular, if we ask how many distinct subsets an infinite set has, we’ll always get an infinite number. This is because we can just form one-element subsets, and since there are infinitely many elements, there will be infinitely many such one-element subsets—and these aren’t even all of the subsets! For example, if the set under consideration is $A=\{\mathrm{positive\ whole\ numbers}\}$ , then $\{1\}$ is a subset, $\{2\}$ is a subset, $\{3\}$ is a subset, and so on, and we clearly get infinitely many subsets. This isn’t even considering $\{1, 2\}$ , or $\{45, 67, 12763\}$ . Also, why do we ask for distinct subsets? Suppose we consider the set $A=\{1, 2, 3\}$ . Then $\mathrm{SET1}=\{2,3\}$ is a subset of A, as is $\mathrm{SET2}=\{1, 3\}$ , and $\mathrm{SET3}=\{2,3\}$ . But SET1=SET3! Thus SET1 and SET3 don’t make distinct subsets, despite the fact that they both make subsets. Clearly the information that is most important to us is the number of distinct subsets. Accordingly, let us finally tackle this problem.

We start as we almost always do with math problems: with some examples. Consider a set with only two elements in it, call it $A=\{a,b\}$ . Note that “a” and “b” could be anything: numbers, horses, apples, ideas, whatever. All that is important to us is that there are two elements in this set. How many distinct subsets of A are there? Well, we know that the empty set is a subset of A, since the empty set is a subset of all sets. So the total so far is 1. We also know that A is a subset of A, since any set is a subset of itself. So the total so far is 2. Next, we can easily read off that $\{a\}$ is a subset of A, and $\{b\}$ is a subset of A, and that’s it. There’s clearly no other distinct subsets. We can see that there are no others because a subset of a two-element set must have at most two elements (since no subset can be larger than the set containing it). Thus a subset of a two-element set either has 0, 1, or 2 elements. There’s only one 0-element subset (the empty set), there’s only one 2-element set (the set itself), and there’s 2 distinct 1-element sets (by definition of the fact that the set has two elements). Thus, there are 4 distinct subsets of any two-element set.

Let us consider a 3-element set, call it $A=\{a, b, c\}$ . We then have the empty set (total current subset count=1), the whole set (total current subset count =2), the three 1-elements subsets $\{a\}, \{b\}, \{c\}$ (total current subset count=5), and the three 2-element sets $\{a,b\}, \{b,c\},$ and $\{c,a\}$ (total current subset count=8). This is all of them, so the total number of distinct subsets of a 3-element set is 8. For a 1-element set, we have two distinct subsets: the empty set and the set itself. Thus we have the following pattern, where the number of elements in the set are on the left and the number of distinct subsets of the set is on the right:

$1 \rightarrow 2$

$2 \rightarrow 4$

$3 \rightarrow 8$

There is a pattern here—namely, an “exponential” one. Recall that $2^3$ is short for “2 raised to the power of 3”, or equivalently “3 products of 2”, so that $2^3=2 \times 2 \times 2=8$ . Similarly, $2^4=2 \times 2 \times 2 \times 2 =16$ . Well, the pattern that we see forming above is that the number on the right is simply “2 raised to the number on the left”. In other words, $2^1=2, 2^2=4$ , and $2^3=8$ .

The pattern does indeed continue, and one can prove that a set with N elements has $2^N$ distinct subsets, where N is any whole number greater than or equal to $0$ . Note that this even works for $N=0$ . We see this as follows. According to the pattern, a $0$ -element set should have $2^0=1$ distinct subsets (anything to the power of $0$ is defined to be 1). However, there is only one $0$ -element set, and that is the empty set. The empty set has the empty set as a subset, since every sets has the empty set as a subset. The empty set has itself as a subset, since every set has itself as a subset. But “itself” is the empty set! Thus these two subsets are actually the same! Moreover, the empty set can’t have any 1- or 2- or 3- element subsets since the set itself has $0$ elements. So we’re done, and there’s only one distinct subset, just like the pattern predicted!

(The general proof of this pattern involves some mathematics that we won’t see for a few more lessons. In particular, we’ll need to understand what a function is before we can give the general proof of this pattern, and functions won’t come until lesson 6 (But they’re just as easy!). Of course, the ambitious reader is encouraged to try to either prove the general pattern or at least convince herself of its truthfulness. There are a couple of different ways to prove it, and we’ll see the easiest such way in the lesson titled “Proving the Pattern”.)

Note also that this pattern ( $N \rightarrow 2^N$ ) relies heavily on the fact that the empty set is a subset of every set, and that every set is a subset of itself. Of course, we could modify those definitions so that we don’t “pick up” these subsets in our counting, in which case the pattern would be $N\rightarrow 2^N-2$ since we’ve “lost out” on these two sets (the empty set and the set itself). Or we could just change one of the definitions and get $N\rightarrow 2^N-1$ . However, the definitions we have give us this nice pattern, and many other even more beautiful results, so we’ll stick with them.

Additionally, this pattern is again just the inevitable logical consequence of precise definitions that we’ve made. The power of all this abstraction with sets and subsets is that if you have 10 dogs and I have 10 ideas and my friend has 10 cars, we all know how many ways we can “split up” these sets regardless of what these sets actually contain. This is just one of many ways in which abstraction is powerful, and we’ll see much cooler examples of this power and beauty in coming lessons!

Next, we tackle an extremely important issue: the notion of sets of sets!

Exercises:

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?

2) It is hopefully clear that there are infinitely many one 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?)

Solutions to Exercises

Next Lesson

Previous Lesson

13 Responses to Lesson 3: Subsets

Anonymous says:

November 21, 2013 at 2:31 am

you seem to have a preoccupation with donkeys. 🙂

Reply
- TrueBeautyOfMath says:
  
  November 21, 2013 at 2:35 am
  
  I guess I have indeed made it appear that way, though in reality I don’t think I’ve ever even seen one. I guess they’re just somehow the perfect noun for reflecting arbitrariness 😉
  
  Reply
Chris says:

July 5, 2014 at 12:21 pm

I’ve been following up until here very excited ….and now I have lost you…

Reply
- TrueBeautyOfMath says:
  
  July 12, 2014 at 10:27 am
  
  can you say what it is in particular that is confusing? Either which paragraphs/statements specifically, or which ideas generally? I’ll try to help since it is likely the case that others are confused on similar things!
  
  Reply
YatharthROCK says:

July 12, 2014 at 10:06 am

Set’s Universality
==================

> Math is the study of sets! Well, at least a lot of math is.

Really? I mean, the study of sets was always relegated to an easy first chapter in math textbooks and that’s it. How, for example, is the notion of sets applicable in calculus or trigonometry? (If you couldn’t figure out that I was a n00b yet, now you know.)

The Point of Math
=================

> This illustrates a large part, if not all of what mathematics is: the formulation of precise definitions and the study of the inevitable logical conclusions to which they lead.

I resonate so strongly with this! Unfortunately, my peers seem to think that it’s just about memorizing formulas. So much so that theygo for these special classes that just make them *practice* math; can you believe that? (Although to be fair, it is a constraint imposed expanded contrived geometrical ‘proofs’ we have to write in the exams which the heavy time limit doesn’t leave time to actually think about the problems.)

Infinite Cardinals
==================

> In particular, if we ask how many distinct subsets an infinite set has, we’ll always get an infinite number.

Would the cardinality of the original set and of it’s power set (as I dimly recall from my textbooks what the latter set should be called w.r.t. the first) be of different types of infinities? (Something along the lines of Aleph_null and Aleph_1 or sth; I don’t have a good intuition for infinity yet.)

Distinct Subsets
================

> Also, why do we ask for distinct subsets?

Also, as soon as we use the term power set as the set of all the possible subsets of anothe set (I should have started giving these sets names half a sentence ago); we don’t need to mention that they have to be distinct explicitly, as that is included in the definition of a set.

Proving the Pattern
===================

> The general proof of this pattern involves some mathematics that we won’t see for a few more lessons.

Really? I’d tried to wrack my own brain, and this what I came up with without even knowing the values for the first few cases: for each (distinct) element of the set, you can either include in in your current sub-set or disclude it making you choose between two options. Simply multiply it into the number of possibilities and you get `2^n`.

How might this be converted into a ‘rigorous’ proof? I do understand their importance and look, as I was reading this great Introduction to Analysis book called Spivak’s Calculus (where it was great fun to show just why even stuff you’d think was too basic to be able to be proven was true); but I can’t formulate the statements right now.

Losing the empty sub-sets
=========================

I love how elegance is the goal for a lot of math. Another (and for me, the more important) aspect of the ugliness of `2^n – 2` is that we would have to special-case the empty set, where the empty set and the set itself are the same thing. As for `2^n -1`, there would be ambiguity† about whether we should include ∅ as a subset of ∅ because it is the set itself or whether we shouldn’t as we agreed that null sets don’t count as sub-sets (the precise resolution of which would depend on how you excluded the null sets from the definition of subsets.

Meta
====

As always, thanks for the posts! (Also, hope I’m not over-loading you by asking too much 🙂

Reply
b007e says:

August 2, 2015 at 2:33 pm

Question 1 ought to be true because, as you iterated earlier,
Definition 3.1 Given a set called A (we can call it whatever we like), a subset of A, call it B, is a set such that every element in B is also in A. //

That is, if every element in subset B is in set A, and every element in subset C is in set B, then every element in subset C is in set A.

Question 2 You did specifically mention specifically that, by the pattern of 2^0 there would be only 1 subset, that subset being itself. Furthermore, if there is only one distinct subset that results in a given set, then there is only one possible set that can result in that.

If that logic doesn’t suffice, then we just ask how many different ways there can be nothing. And no matter how quantum mechanical you get there’s only one way for there to be nothing, and that is to have an absence of something!

Anyways, I’ll enjoy jumping into this Michael.
P.S., I am your cousin.

Reply
- TrueBeautyOfMath says:
  
  September 21, 2015 at 12:18 am
  
  Hey Cuz! To be honest, I’m not sure which cousin this is (your email doesn’t give it away and if you’re really my cousin (which I’m sure you are, not doubting that) then you’ll know better than anyone that we have quite a few cousins), but your answers and on the money. The “proof” that’s usually used for the fact that there’s only one 0-element set involves the following. We know that the empty set is a 0-element set, so let us now suppose that there is another 0-element set, and let us call it A. The question now is whether or not A is different from the empty set. Indeed, it is PRECISELY the empty set because there is no element in A that isn’t in the empty set, and there is no element in the empty set that isn’t in A (and the reason for both of these is that there is simply no element in either!). So indeed we don’t need to get quantum mechanical to see that there’s only one way to have nothing 🙂
  
  Hope you enjoy Cuz!
  
  Reply
  - 57biotechcado says:
    
    November 16, 2015 at 6:15 pm
    
    Does the following implies that if there exists a set of all empty sets of all sets there is just one set in the mentioned set, being the empty set indeed?
    
    Reply
    - TrueBeautyOfMath says:
      
      November 17, 2015 at 8:39 pm
      
      hmmm, not sure what you mean by “the set of all empty sets of all sets”. There’s only one empty set: it’s the set with no elements in it. There is no notion of an empty set OF a set. Feel free to re-explain though in case I’m misunderstanding what you said 🙂
      
      Reply
      - 57biotechcado says:
        
        November 17, 2015 at 9:49 pm
        
        What I tried to say it is the following:
        Given that
        
        >> the empy set is a subset of every set.
        
        >> there is no element in the empty set.
        
        Now I suppose a set, name it Gorilla, containing All empty sets from all sets.
        
        The implication I deduced from the latter was that Gorilla is the empty set even if it’s mentioned members.
        
        I want to add that it seems like a puzzle when I think about it.
        
        I hope that the idea will be clearer now; Thanks for your answer!
      - TrueBeautyOfMath says:
        
        November 17, 2015 at 9:54 pm
        
        Still, there’s that phrase though: “empty sets from all sets” (the set you call Gorilla). There is only one empty set, and it happens to be a subset of every set. There is not more than one empty set, just one. I don’t understand the implication simply because I don’t understand the setup: it doesn’t mean anything to say that a set contains “all empty sets from all sets,” because there is only one empty set, period. One can consider the set whose single element is the empty set, then this is a 1-element set whose element is a set (the element is the empty set itself). This set would NOT be empty because it contains one element: the empty set. The empty set ITSELF is the set with no elements, and there is only one empty set. So again, considering “the set of all empty sets” just doesn’t have any actual meaning. Or, at most, the set of all empty sets has one element: THE empty set (note that I say “the” empty set, not “an” empty set, because there is only one).
      - 57biotechcado says:
        
        November 18, 2015 at 3:51 pm
        
        What I understood about your answer is that clearly exists just one empty set that is indeed a subset of every set.
        
        It does not matter if I create a set where I want to join the empty set that is subset of every set because it is meaningless.
        
        It stills being just one empty set.
        
        I also understood that if there would be a set containing the empty set, that set is the empty set.
        
        Thanks for your answer.
      - TrueBeautyOfMath says:
        
        January 29, 2016 at 2:11 pm
        
        Exactly, except for one small thing. At the end you say “if there would be a set containing the empty set, then that set is the empty set,” and I think what you mean (since every set contains the empty set), is that if the empty set contains some other set, then this other set is the empty set. Is that what you meant to write?
        
        Thanks for all your great comments, answers, and questions!