Subsets Proper and Improper

Question

How many subsets can be formed from a set of four elements, say $A={e, f, g, h}$ ? How many proper subsets?

Solution

Terminology

An improper subset includes all the elements in the original set. In other words, an improper subset of set $A$ is set $A$ itself.

A proper subset of set $A$ can be any subset of set $A$ except the improper subset.

If “proper” is not specified, “subset” is understood to include the improper subset.

Approach

Consider a set with just one element: Set $D={a}$ . How many subsets does it have? Remember that the empty set is a subset of every set. So set $D$ has two subsets: ${}$ (the empty set) and ${a}$ . The set that includes ${a}$ is improper, and ${}$ is proper.

Now think about a set with two elements: Set $E={a, b}$ . $E$ ‘s subsets include both of $D$ ’s subsets, ${}$ and ${a}$ . And $E$ ’s subsets also include each of $D$ ’s subsets with element $b$ added to it – resulting in subsets ${a}$ and ${a, b}$ – for a total of four subsets, including three proper subsets.

Does the pattern continue? Set $E={a, b, c}$ . $E$ ’s subsets include all four of $D$ ’s subsets, {}, {a}, {b}, and {a, b}; as well as each of $D$ ’s subsets with element c added to it – {c}, {a, c}, {b, c}, and {a, b, c} – for a total of eight subsets, including seven proper subsets.

Each time an element is added to the set, the number of subsets doubles. If there’s just one element, there are two subsets; for two elements, there are $2 cdot 2 = 4$ subsets; for three elements, there are $2^3=8$ subsets, and for n elements, there are $2^n$ subsets.

Each set has one improper subset — that is, just one subset that contains all of the original set’s elements — so the number of proper subsets in each set of n elements is the number of subsets minus one, or $2^n-1$ .