1
$\begingroup$

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

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

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)$.

1 Answers 1

1
  1. Show that $P(K) \subset (P(S) \cup X)$ and $(P(S) \cup X) \subset P(K)$. To show this, argue that if $A \in P(K)$ is some set, then so must $A \in (P(S) \cup X)$. And conversely. To see that $P(S)$ and $X$ are disjoint, let $A \in P(S)$ and $B \in X$. Why cannot it ever be the case that $A=B$? Try to find an element of one set that is not an element of the other.

  2. Pick some subset $A \in X$. How does the construction of $X$ allow you to prove that $A$ is the same set as some subset of $S$ union the singleton $\{x\}$?

  3. Can you find a one-to-one correspondence between $P(S)$ and $X$? How does this allow you to count the number of subsets of $K$?

  • 0
    I added a hint to that part. See edited answer.2011-02-25