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

From Norsemathology
Jump to navigation Jump to search

Motivation

Independent Choices

First of all, we can give a motivation for the result: consider a set of Cardinality . A subset is made up of elements of . 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 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 (including the leaves).

The leaves represent all possible distinctly different subsets. The number of leaves at this depth for a binary tree is .

Proof by Induction

This is best proved by induction, so let 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 (i.e., has zero elements), then the power set , with . So the base case is true.

Inductive Step

Now assume ; we want to show .

Let be a set containing elements. Remove one element, calling it . Now the remaining elements comprise a set of cardinality , and hence .

Every subset of is of one of two forms: either or , where . Every element of the power set of is of one of these two forms, i.e. ; 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 , , has twice the cardinality of , or

.

Q.E.D.