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: Power Sets

  1. Jan 27, 2012 #1
    Let S be any finite set and suppose [itex]x \notin S[/itex]. Let [itex]K = S \cup \left\{ x \right\}[/itex].

    1. Prove that P(K) is the disjoint union of P(S) and [itex]X = \left \{T \subseteq K : x \in T \right\}[/itex]. That is, show that [itex]P(K) = P(S) \cup X[/itex] and [itex]P(S) \cap X = \emptyset [/itex]

    2. Prove that every element of X is the union of a subset of S with {x}, and that if you take different subsets of S you get different elements of X. Argue that, therefore, X has the same number of elements as P(S).

    3. Argue that the previous two parts allow you to conclude that if S is a finite set, then P(K) has twice as many elements as P(S).

    I can do 1. Can anyone help with 2 and 3?
     
  2. jcsd
  3. Jan 28, 2012 #2

    Bacle2

    User Avatar
    Science Advisor

    For 3), think of a bijection ; the subsets of K either contain x , or do not contain it. Try some small examples.
     
  4. Jan 28, 2012 #3
    For 2) any element T of X is subset of K with x inside it. x isn't in S so T must be at least {x}, but it can also include elements of S since K is the union of S and {x}. If you take two elements SU{x} and S'U{x} in X, thinking about the set SU{x}-S'U{x} should help you prove the last part.
     
  5. Jan 28, 2012 #4
    aeroplane, so I get [itex]S \cap \left\{ x \right\} - S^{c} \cup \left\{ x \right\} \Leftrightarrow \left\{ x \right\}^{c}[/itex]. How does it allow me to conclude that if we take different subsets of S we get different elements of X and that X has the same number of elements as P(S)?
     
  6. Jan 29, 2012 #5
    For two sets SU{x} and S'U{x} in X, SU{x}-S'U{x} is the empty set iff S=S'. Every set of X has to be at least {x}, so the difference between two elements has to be related to a difference in the subsets of S. Then you can think of X as P(S) where each element has {x} attached to it, so it must have the same number of elements.
     
  7. Jan 29, 2012 #6
    By S' do you mean the complement of S, or some other arbitrary set?
     
  8. Jan 29, 2012 #7
    Sorry, some other arbitrary set, S={s_1,s_2,...,s_n}, S'={s'_1,...,s'_n} since both are finite.
     
  9. Jan 30, 2012 #8

    Bacle2

    User Avatar
    Science Advisor

    Basically, for every set without a specific x, you can find a new set with that x, by adjoining x to any of the existing sets, and there are no other possible subsets of S\/{x}, since subsets of S\/{x} must contain either elements of S, or elements of {x}:

    Maybe you can also use combinatorial identities:

    Number of subsets of a set with n elements:

    0-element subsets: nC0 ( " n choose 0" )

    1-element subsets nC1

    .....

    n-element subsets nCn

    _____________________________

    nC0+nC1+....+nCn = (1+1)n

    Now try for (n+1) elements.
     
  10. Feb 4, 2012 #9
    Thank you.
     
  11. Feb 5, 2012 #10

    Bacle2

    User Avatar
    Science Advisor

    No problem; glad I could help.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook