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)?
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: