A Proof that the power set of a set of Cardinality n has Cardinality 2 to the nth power

From www.norsemathology.org

Jump to: navigation, search



Independent Choices

First of all, we can give a motivation for the result: consider a set \left.S\right. of Cardinality \left.n\right.. A subset is made up of elements of \left.S\right.. We can imagine that each element has a decision to make as a subset is being formed: am I in, or out? Each makes its choice independently, so, in the end, there are \left.2\cdot 2\cdot \ldots \cdot 2 = 2^n\right. choices of subsets.

Binary trees

An alternative motivation is given by a binary decision tree. At each node an element makes its choice -- in or out. Left child means "in", right child means "out". The first element makes its choice at depth 0. Then, once the first element has made its choice, the second element makes its choice at depth 1. This goes on until it results in a full binary tree, with depth \left.n\right. (including the leaves).

The leaves represent all possible distinctly different subsets. The number of leaves at this depth for a binary tree is \left.2^n\right..

Proof by Induction

This is best proved by induction, so let \left.P(n)\right. be the proposition that the power set of a set of Cardinality n has Cardinality 2 to the nth power.

Base Case

The base case is easy: if \left.S=\phi\right. (i.e., has zero elements), then the power set \left.\mathcal P \left({S}\right)=\{\phi\}\right., with \left.Card(\mathcal P \left({S}\right))=1=2^0\right.. So the base case is true.

Inductive Step

Now assume \left.P(k)\right.; we want to show \left.P(k+1)\right..

Let \left.T\right. be a set containing \left.k+1\right. elements. Remove one element, calling it \left.e_{k+1}\right.. Now the remaining elements comprise a set \left.S\right. of cardinality \left.k\right., and hence \left.Card(\mathcal P \left({S}\right))=2^k\right..

Every subset \left.V\right. of \left.T\right. is of one of two forms: either \left.V=U\right. or \left.V=U \cup \{e_{k+1}\}\right., where \left.U \subseteq S\right.. Every element of the power set of \left.T\right. is of one of these two forms, i.e. \left.\mathcal P \left({T}\right)=\{U | U \subseteq S\} \cup \{U \cup \{e_{k+1}\} | U \subseteq S\}\right.; those two sets are disjoint (that means that they have no common intersection -- no set is a member of both).

So the power set of \left.T\right., \left.\mathcal P \left({T}\right)\right., has twice the cardinality of \left.\mathcal P \left({S}\right)\right., or

\left.Card(\mathcal P \left({T}\right))=2\cdot 2^k=2^{k+1}\right..


Personal tools