Dismiss Notice
Join Physics Forums Today!
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)

  1. Jul 21, 2007 #1
    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. jcsd
  3. Jul 21, 2007 #2


    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?
     
  4. Jul 22, 2007 #3
    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)?
     
  5. Jul 22, 2007 #4
    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
  6. Jul 22, 2007 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  7. Jul 22, 2007 #6
    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).
     
  8. Jul 23, 2007 #7

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Given any arbitrary subset A of X, each element of X is either in A or is not. So...
     
  9. Jul 24, 2007 #8
    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?
     
  10. Jul 24, 2007 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  11. Jul 24, 2007 #10
    What Dick is talking about is the characteristic function. So [tex] x \in A [/tex] or [tex] x \not \in A [/tex](i.e. 2 possibilities) which leads to [tex] |\mathcal{P}(X)| = 2^n [/tex].
     
    Last edited: Jul 24, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook