Count subsets and power-set elements

From a subset to a power set

A subset of A uses only elements of A. The power set collects all those subsets as its own elements. Keep the braces: a number and a set containing that number are different objects

1. 1A power set is a set of sets The power set of A contains every subset of A. Its elements are subsets, not the individual numbers inside A \(\displaystyle \mathcal P(A)=\{B:B\subseteq A\}\)
2. 2Include the two boundary subsets The empty set is a subset of every set, and A is a subset of itself. Both belong to the power set. When A is empty they are the same subset, not two different subsets \(\displaystyle \begin{gathered}\varnothing\in\mathcal P(A)\\A\in\mathcal P(A)\end{gathered}\)

A

\(\displaystyle \{2,5\}\)

Which is an element of the power set of A?

List the whole power set

For A containing 2 and 5, the subsets have zero, one or two elements. There is one empty subset, two one-element subsets and one whole-set subset. This is four subsets, not two

Power set

\(\displaystyle \{\varnothing,\{2\},\{5\},\{2,5\}\}\)

How many elements are in the displayed power set? Count its subsets, not the individual numbers inside them

Why the number doubles

Suppose all subsets of A have been listed and a new element b is added to A. Each old subset gives two different new subsets: one without b and one with b. No two pairs overlap, and every new subset appears. Adding one distinct element therefore doubles the count

1. 1Count independent inclusion choices For each of the n distinct elements, choose include or exclude. Every sequence of choices gives exactly one subset, and every subset gives one such sequence \(\displaystyle |\mathcal P(A)|=2^{|A|}=2^n\)

A has five distinct elements. How many elements are in its power set?

The empty base set

The empty set has no elements to choose. There is still one selection: choose nothing. The power set of the empty set therefore contains one element, the empty set. A set containing the empty set is not itself empty

How many elements are in A itself?

Proper and nonempty are different conditions

A proper subset is not equal to the whole set. A nonempty subset is not the empty set. For a nonempty base set, removing both leaves all subsets except these two. For an empty base set there are zero nonempty proper subsets: the two exclusions name the same subset

1. 1Apply a filter only when requested Proper means not equal to A. Nonempty means not equal to the empty set. Each separate restriction removes one subset. Removing both removes two different subsets only when A is nonempty \(\displaystyle \begin{gathered}\text{proper: }2^n-1\\\text{nonempty: }2^n-1\end{gathered}\)

A

\(\displaystyle \{1,3,6\}\)

How many proper subsets does A have? The empty subset is allowed, but A itself is excluded

A

\(\displaystyle \{1,3,6\}\)

How many subsets of A are both nonempty and proper?

How many nonempty proper subsets does the empty set have?

Written enumeration practice, ungraded

On paper, list the entire power set of A. Group your subsets by their size, include the empty subset and the whole set, and check that there are eight distinct subsets. This construction is not automatically marked; a correct count alone does not verify your list

Model enumeration

The eight subsets have sizes 0, 1, 1, 1, 2, 2, 2 and 3. The list below contains each one once. The order of these subsets, or of numbers within a subset, does not change the power set

Written justification practice, ungraded

Explain on paper why an n-element set has the displayed number of subsets. Your argument must explain both why different include-or-exclude choices cannot give the same subset and why every subset appears. The next screen gives a model; your written explanation is not automatically marked

Model counting argument

Label the n distinct elements. For each label choose include or exclude, giving a product of n factors of two. If two choice lists differ at any label, one resulting subset contains that element and the other does not, so the subsets differ. Conversely, any subset determines its inclusion choices for every label. Thus the correspondence is one-to-one and covers all subsets. For the empty set, the single empty choice list corresponds to the empty subset