51 Consider a Set

Consider this set: A = {a, b, c, d}.

As defined in the first reading assignment, a subset of A is another set that contains only elements from the set A, but many not contain all the elements of A. A proper subset is a subset that is not identical to the original set—it contains fewer elements.

We can list all of the subsets of A:

{} (or Ø), {a}, {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}

You can see that there are 16 subsets, 15 of which are proper subsets.

Listing the sets is fine if you have only a few elements. However, if we were to list all of the subsets of a set containing many elements, it would be quite tedious. Instead, let’s consider each element of the set separately.

In our example, there are four elements. For the first element, a, either it’s in the set or it’s not. Thus there are 2 choices for that first element. Similarly, there are two choices for b—either it’s in the set or it’s not. Using just those two elements, we see that the subsets are as follows:

{}—both elements are not in the set
{a}—a is in; b is not in the set
{b}—a is not in the set; b is in
{a,b}—a is in; b is in

Two choices for a times the two for b gives us 2² = 4 subsets. You can draw a tree diagram to see this as well.

Now let’s include c. Again, either c is included or it isn’t, which gives us two choices. The outcomes are {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}. Note that there are 2³ = 8 subsets.

Including all four elements, there are 2⁴ = 16 subsets. 15 of those subsets are proper, 1 subset, namely {a,b,c,d}, is not.

In general, if you have n elements in your set, then there are 2ⁿ subsets and 2ⁿ − 1 proper subsets.