# Cardinality of the intersection of 2 power sets

Prove that the cardinality of the intersection of the power sets of two sets is of the form $2^n$ for some positive $n$.

My Thoughts:

Let the 2 sets be A and B

$$A = \{1,2,3,4,5\}$$

$$B = \{3,4,5,6,7\}$$

so,

$A\cap B = \{3, 4, 5\}$

$P(A\cap B ) = \{\{\varnothing\} ,\{3\},\{4\},\{5\},\{3, 4\},\{3 ,5\},\{4, 5\}, \{3, 4, 5\}\}$

$|P (A \cap B )| = 2^n$, where $n$ is the number of elements in the set

$|P (A\cap B )| = 2^3 = 8$

I proved 1 case. But how do I prove for all cases?

-
You did not really prove 1 case. "Intersection of the power sets" has a different meaning than "the power set of an intersection"; the problem was about the former, while you dealt with the latter. –  Jonas Meyer Nov 21 '12 at 17:33
@JonasMeyer They are in fact equal, and the proof follows from that pretty quickly. That's the main thing which should be shown though. –  Cocopuffs Nov 21 '12 at 17:35
@Cocopuffs: Yes, I edited my wording before (or while) you commented. Thank you. –  Jonas Meyer Nov 21 '12 at 17:36

Well, if we know that $P(A)\cap P(B)=P(A\cap B)$, then by knowing that $P(X)$ has $2^n$ elements we are done.

To see this note the following:

$X\in P(A)\cap P(B)$ then $X\subseteq A$ and $X\subseteq B$, therefore $X\subseteq A\cap B$ and so $X\in P(A\cap B)$. Similarly in the opposite direction, we have $P(A)\cap P(B)=P(A\cap B)$.

Now we use the fact that if $X$ has $n$ members then $P(X)$ has $2^n$ members to deduce that $P(A)\cap P(B)$ has $2^{|A\cap B|}$ elements.

Note however that the question is false. If $A\cap B=\varnothing$ then $P(A)\cap P(B)=\{\varnothing\}$ whose size is $2^0$, and $0$ is never a positive number.

-
How do we prove that $P(A) \cup P(B)$ = $P(A \cup B)$? –  Rinzler Nov 8 '14 at 20:59
@Broly: We don't? Because it's false? Why are you asking here, instead of finding the several posts that were made on this topic on the main site? –  Asaf Karagila Nov 8 '14 at 21:00
Ok. I mistook writing, I meant $\cap$ instead of $\cup$, but I have just seen that your answer answers also my stupid question, right? –  Rinzler Nov 8 '14 at 21:03
Oh, in that case my answer above should answer your question. I'm still not 100% sure why you'd ask it in the comments. But the question is generally not stupid. –  Asaf Karagila Nov 8 '14 at 21:04
By the way, lol, why my first equality is not valid? Following your same reasoning (steps) in your answer, it seems to be correct, but it is not, because I am wrong, right? –  Rinzler Nov 8 '14 at 21:08