1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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


    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


    User Avatar
    Science Advisor

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