# Homework Help: Power Sets

1. Jan 27, 2012

### glebovg

Let S be any finite set and suppose $x \notin S$. Let $K = S \cup \left\{ x \right\}$.

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

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. Jan 28, 2012

### Bacle2

For 3), think of a bijection ; the subsets of K either contain x , or do not contain it. Try some small examples.

3. Jan 28, 2012

### aeroplane

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.

4. Jan 28, 2012

### glebovg

aeroplane, so I get $S \cap \left\{ x \right\} - S^{c} \cup \left\{ x \right\} \Leftrightarrow \left\{ x \right\}^{c}$. 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)?

5. Jan 29, 2012

### aeroplane

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.

6. Jan 29, 2012

### glebovg

By S' do you mean the complement of S, or some other arbitrary set?

7. Jan 29, 2012

### aeroplane

Sorry, some other arbitrary set, S={s_1,s_2,...,s_n}, S'={s'_1,...,s'_n} since both are finite.

8. Jan 30, 2012

### Bacle2

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.

9. Feb 4, 2012

### glebovg

Thank you.

10. Feb 5, 2012

### Bacle2

No problem; glad I could help.