(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Let X be a finite set with n elements. Prove that P(X) has 2^n elements.

<This is an extra credit problem for a summer class I'm taking.>

2. Relevant equations

P(X) is the power set of X, the set of all possible subsets of X.

The principle of induction.

The characteristic function:

Let X be a set and let A be one of its subsets. The characteristic function 'X' of A is the function 'X'_A (x): X --> {0,1} defined by:

'X'_A(x) = 1, if x is in A OR

0, if x is not in A

The book also gave the following as a hint:

The notation Y^Z is sometimes used for the set of all functions from the set Z to the set Y. The map which takes a set to its characteristic function is a bijection from the set P(X) of all subsets of X to the set {0,1}^X. Since the notation '2' is sometimes used for the set {0,1}, this explains why the notation 2^X, instead of P(X), is sometimes used for the set of all subsets of X.

Notation:

|X| = the cardinality of X

2^n is read as '2 raised to the nth power'

x_k is the kth element in the set X

3. The attempt at a solution

I wasn't sure how to interpret the hint, so I tried induction on n, the cardinality of the set X.

Induct on n.

Base case, n = 1.

Let X = {x_1}

P(X) = {<empty set>, x_1}

|P(X)| = 2 = 2^1.

So the base case holds.

For the inductive hypothesis (I.H.), assume:

If n=k, |P(X)| = 2^k

X = {x_1, x_2, ... , x_k}

To complete the proof, I need to show that if n=k+1,

|P(X)| = 2^(k+1) = 2*2^k

I know:

X = {x_1, x_2, ... , x_k, x_(k+1)} = {X from the I.H.} <union> {x_(k+1)}

I got stuck here. The problem is that I don't know how to show adding another element to X makes the size of P(X) double. Can anyone help?

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Set theory - Cardinality of P(X)

**Physics Forums | Science Articles, Homework Help, Discussion**