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?
Best Answer
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.