Proving Properties of P(K) when x $\notin$ S

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

 

[Bacle2]

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

 

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

 

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

 

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

 

[glebovg]

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

 

[aeroplane]

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

 

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

Now try for (n+1) elements.

 

[glebovg]

Thank you.

 

[Bacle2]

No problem; glad I could help.