The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: Math Kangaroo 7-8, Math Kangaroo 9-10, AMC-8, AMC-10, AMC-12.

The power set of a set S is the set of all the subsets of set S.

The notation for the power set of the set S is:

equation

Compute the cardinality of the power set of a finite set S:

Remember that the cardinality of a finite set is the number of its elements, so the problem boils down to counting the elements of the power set.

Assume that the set S has n elements:

equation

i.e. its cardinality is n:

equation

Then we can count the elements of the power set in the following way:

# of elements in subset:Example of subsetsHow many such subsets
equationequationequation
equationequationequation
equationequationequation
equationequationequation

The total number of subsets is the sum:

equation

We know, from identities involving binomial coefficients that this sum is equal to:

equation

Therefore, the cardinality of the power set of a finite set is equal to:

equation

Yet another, simpler way of deriving the cardinality of the power set of a finite set is the following:

Let F be a finite set. What is the cardinality of the power set P(F)?

Solution:

Let x be an element of F. In any subset of F x is an element or is not an element. Therefore, any subset can be generated by assigning one of 2 states to each element of F: present or absent. The total number of combinations of states is equal to the number of subsets.

Thus, if F has n elements, it will have 2n subsets.

The cardinality of P(F) is:

equation