Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 1 down vote accepted
  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$?

share|cite|improve this answer
Thanks, but for #1, I'm able to show how they are equal using what you said. But how do I prove it is disjoint from there? – user7478 Feb 25 '11 at 2:47
I added a hint to that part. See edited answer. – milcak Feb 25 '11 at 2:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.