Understanding the solutions to questions concerning cardinalities and power sets. 
Let $A = \{1, 2, 3, ... , n\}$. Find the cardinalities of the following sets:

*

*$\{(a, S) \mid a \in S, S \in P(A)\} $

*$\{(S, T) \mid S \in P(A), T \in P(A), S\cap T = \emptyset \}$

Please note that I have only recently (a week ago) started to study some basic, introductory set theory, and will probably need a detailed explanation. Prior to this exercise, my book only offered a brief definition of a power set and of the cartesian product.

*

*$\{(a, S) \mid a \in S, S \in P(A)\}$
What confuses me here is the fact that when considering the cartesian product, we normally multiply the cardinalities of the sets, but in this case, the cardinality of $S$ seems to vary, as it is an element of the power set. The book mentioned that I should start with choosing $n$ elements from $A$ and that there are $2^{n-1}$ choices for $S$. From where does the latter come from?


*$\{(S, T) | S \in P(A), T \in P(A), S\cap T = \emptyset \}$
The solution to this one, $3^n$, I don't understand at all.
 A: To find the cardinality of $\{(a, S) \mid a \in S, S \in P(A)\}$ we first note that $a$ can take $n$ values. Next we need to find how many sets $S$ can represent. Since $a\in S$, we need to find the number of possible sets $S\in P(A)$ that contain $a$. This is given by $$|P(A)|-|\{S\mid a \notin S\}|=|P(A)|-|P(A\setminus \{a\})|=2^n-2^{n-1}=2^{n-1}.$$ Thus the cardinality of our set is $n 2^{n-1}$.

To find the cardinality of $\{(S, T) \mid S \in P(A), T \in P(A), S\cap T = \emptyset \}$ we can break it down into cases as follows:

*

*If $S$ has cardinality $0$, i.e. $S=\emptyset$, then $S\cap T = \emptyset$ for all $T\in P(A)$. This gives $|P(A)|=2^n$ ordered pairs.


*If $S$ has cardinality $1$, then $S=\{a_1\}$ where $a_1\in A$. Now $P(A)$ contains $|P(A\setminus \{a_1\})|=2^{n-1}$ sets that don't contain $a_1$. Since we have $n$ choices for $a_1\in A$, we need to multiply by $n$ to get all cases where $S$ has cardinality $1$. This gives $n2^{n-1}$ ordered pairs.


*If $S$ has cardinality $2$, then $S=\{a_1,a_2\}$ where $a_1,a_2\in A$. Now $P(A)$ contains $|P(A\setminus \{a_1,a_2\})|=2^{n-2}$ sets that don't contain $a_1$ or $a_2$. Since we have $\binom{n}{2}$ choices for $S$, we need to multiply by $\binom{n}{2}$ to get all cases where $S$ has cardinality $2$. This gives $\binom{n}{2}2^{n-2}$ ordered pairs.
$\quad \quad \vdots$


*If $S$ has cardinality $n$, then $S=A$. Now $P(A)$ contains $|P(\emptyset)|=1$ set $T$ for which $A\cap T=\emptyset$, namely $T=\emptyset$. Thus the number of of possible $T$ when $S$ has cardinality $n$ is $1$.
Adding all these cases gives the total number of ordered pairs $(S,T)$ which satisfy the required criteria. The sum is:
$$2^n+n2^{n-1}+\binom{n}{2}2^{n-2}+\cdots +\binom{n}{n-1}2+1 $$
Now we notice that this is the binomial expansion $(2+1)^n=3^n$.
