# Set theory - Cardinality of P(X)

1. Jul 21, 2007

### smithg86

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?

2. Jul 21, 2007

### d_leet

Think about what subsets this new set has. It obviously contains the set whose power set you assume has cardinality 2^k in the induction hypothesis as a subset, so it certainly has AT LEAST 2^k subsets, but none of these contain the element x_(k+1). So you now have that this set X has 2^k subsets none of which contain x_(k+1), what other subsets does this set have?

3. Jul 22, 2007

### ZioX

The set {0,1}x{0,1}x{0,1}....x{0,1} (n times) has cardinality 2^n. Can you find a bijection from this set to P(X)?

4. Jul 22, 2007

### smithg86

ZioX, I was unable to find such a bijection. Here's what I was able to do:

I 'grouped' the subsets of X by their cardinality. For example, <null set> has cardinality 0, {x_1}, {x_2}, ... , {x_k} have cardinality 1, {x_1, x_2}, {x_1, x_3}, ... have cardinality 2, etc.

Let P_i (X) be the set of all subsets of X with cardinality i [note: P_i (X) is a r-subset of X]. I was able to figure out that |P_i (X)| = "k choose i", if |X| = k. Also, P(X) = <the sum from i=0 to i=k of> P_i (X). The intersection of P_a (X) and P_b (X) = <empty set> iff a does not equal b, and both a,b are between (inclusive) 0 and k. Because P_a (X) and P_b (X) are pairwise disjoint, the union of all P_i (X), from i=0 to i=k, is equal to P(X) and the sum of their cardinalities is equal to |P(X)|.

The binomial theorem gives us:
(a+b)^k = <the sum from i=o to i=k of> a^(k-i) * b^i * "k choose i"
let a=b=1, giving us:
2^k = <the sum from i=o to i=k of> "k choose i" = the number of elements in P(X), as required.

[i was able to prove this using a few theorems from last semester's textbook - theorems that aren't present in this textbook. hence, i didn't prove that P_i (X) = "k choose i"; in fact, this textbook doesn't even cover r-subsets. also, i'm not exactly sure how to justify the a=b=1 step.]

Last edited: Jul 22, 2007
5. Jul 22, 2007

### Dick

Your not understanding the hint is leading you to really over complicate the problem. An element of P(X) is a subset of X, call it A. An element of 2^X is list of 0's and 1's, one for each element of X. What might that value of 0 or 1 have to do with the whether the corresponding element of X is in A?

6. Jul 22, 2007

### ZioX

If you still want to do an induction you could do some argument like this:

|P(X)|=2^k.

Consider all of the nonempty subsets of X, of which there is 2^k-1. For each one of these we can add the new element, so we have 2^k-1 more subsets. There will be two more, the empty set, and the set containing only the new element. Adding all these up we get 2^k-1+2^k-1+1+1=2*2^k=2^(k+1).

7. Jul 23, 2007

### morphism

Given any arbitrary subset A of X, each element of X is either in A or is not. So...

8. Jul 24, 2007

### smithg86

ZioX,
After reading your last comment, I was able to prove the statement using induction. Thanks for your help.

Dick,
I'm not sure I fully understand the connection between the characteristic function and the subset of X, call it A. Here's what I have so far. Feel free to correct me:

A subset of X, call it A, is an element of P(X). Say there are m elements in X:

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

We look at A. For an example, let A = {x_1, x_2}
I can write:

A = {1*x_1, 1*x_2, 0*x_3, 0*,..., 0*x_m},
where x_i, if i>2, is being multiplied by zero.

A = {'X'_A(x_1), 'X'_A(x_2), ... , 'X'_A(x_m)}

[The first thing that came to mind was the dot product - in this case between the set X and the characteristic function. But A = {x_1, x_2} is not equal to {x_1, x_2, 0, 0, 0, ... ,0}]

'X'_A(x_i) is the characteristic function for set A evaluated on the element x_i. Recall that 'X'_A(x_i) = 1 if x_i is in A and 'X'_A(x_i) = 0 if x_i is not in A.

I want to show that P(X) has 2^m elements. If I can show that a bijection exists between P(X) and a set with 2^m elements, I have completed the proof. The set A, expressed as a combination of X and the characteristic function, has m elements. Each element is "given the opportunity to choose" 0 or 1, so we have (2 choices) x (2 choices) x...... m times, or 2^m.

But here is where I get confused: isn't A an arbitrary subset of X - don't I need to consider all the other subsets? Also, I'm not comfortable with the way I derived 2^m elements. And I really have no idea how to 'construct' a bijection between P(X) and {0,1}. Can anyone explain this to me?

9. Jul 24, 2007

### Dick

An element of 2^X is a map from the elements of X to the set {0,1}. Let f be the map from subsets to 2^X. If A is a subset of X, then let f(A) be the map g such that g(x_i)=0 if x_i is not in A and g(x_i)=1 if x_i is in A. Do you see why this might be a bijection between P(X) and 2^X?

10. Jul 24, 2007

### tronter

What Dick is talking about is the characteristic function. So $$x \in A$$ or $$x \not \in A$$(i.e. 2 possibilities) which leads to $$|\mathcal{P}(X)| = 2^n$$.

Last edited: Jul 24, 2007