Set theory - Cardinality of P(X)

[smithg86]

Homework Statement

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.>

Homework 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

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?

 

[d_leet]

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?

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?

 

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

 

[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.]

 

[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?

 

[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).

 

[morphism]

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

 

[smithg86]

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).

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

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?

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?

 

[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?

 

[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.