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^{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^{3} = 8 subsets.

Including all four elements, there are 2^{4} = 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^{n} subsets and 2^{n} − 1 proper subsets.