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 22 = 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 23 = 8 subsets. Including all four elements, there are 24 = 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 2n subsets and 2n − 1 proper subsets.Licenses & Attributions
CC licensed content, Original
- Mathematics for the Liberal Arts I. Provided by: Extended Learning Institute of Northern Virginia Community College Located at: https://online.nvcc.edu/. License: CC BY: Attribution.
