Take the 2-minute tour ×
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.

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|improve this question
    
We're missing some context here... –  Yuval Filmus Feb 25 '11 at 2:17
    
Sorry, fixed it. –  user7478 Feb 25 '11 at 2:33
1  
Homework tag missing? –  Myself Feb 25 '11 at 3:06

1 Answer 1

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

 
discard

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.