Share
Explore BrainMass

Subsets of a finite set

(a) List all subsets of the set {a, b, c, d}.

(b) Determine the number of subsets of the set A = {a, b, c, d, e, f}, without writing them down.

(c) Determine the number of subsets of the set B = {a, b, c, d, e, f, g, h, i} , without writing them down.

Solution Preview

(a) In listing all the subsets of the set {a, b, c, d}, we can arrange them by the number of elements in the subset. Since {a, b, c, d} has four elements, each of its subsets has either 0, 1, 2, 3, or 4 elements.

Subsets with 0 elements. There is only one subset with no elements (that's the empty set, or the null set, as it's also called).

Subsets with 1 element. There are four subsets with one element: {a}, {b}, {c}, {d}.

Subsets with 2 elements. There are six subsets with two elements: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.

Recall that the order of the elements within a set doesn't matter, so that the set {b, a} is identical to the set {a, b}, and we list that set only once.

Subsets with 3 elements. There are four subsets with three elements: {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}.

Subsets with 4 elements. There is only one subset with four elements: {a, b, c, d}.

------------------------------------------------------

(b) A = {a, b, c, d, e, f}.

One way to determine the number of subsets of A is to approach the problem as follows:

The set A has six elements, so think of representing the elements of A (the elements a, b, c, d, e, f) by the numbers 1, 2, 3, 4, 5, and 6, respectively (i.e., represent "a" by "1", represent "b" by "2", etc.).

Now let S be any subset of A, and think of ...

Solution Summary

For part (a), all of the subsets of the set {a, b, c, d} are listed.

For part (b), a detailed, step-by-step presentation of the number of subsets of the set A = {a, b, c, d, e, f} is given.

For part (c), a detailed, step-by-step presentation of the the number of subsets of the set B = {a, b, c, d, e, f, g, h, i} is given.

Finally, one of the methods used to compute the numbers of subsets of sets A and B (in parts (a) and (b)) is applied to the original set, {a, b, c, d}, and it is shown that that result is equal to the number of subsets listed in part (a).

$2.19