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: 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: i.e. its cardinality is n: Then we can count the elements of the power set in the following way:

 # of elements in subset: Example of subsets How many such subsets            The total number of subsets is the sum: We know, from identities involving binomial coefficients that this sum is equal to: Therefore, the cardinality of the power set of a finite set is equal to: 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: 