# Understanding the solutions to questions concerning cardinalities and power sets.

Let $$A = \{1, 2, 3, ... , n\}$$. Find the cardinalities of the following sets:

1. $$\{(a, S) \mid a \in S, S \in P(A)\}$$
2. $$\{(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.

1. $$\{(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?

1. $$\{(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.

• Is the first one written right? If $S \in P(A)$ is the empty set, then what is $a\in S$? Jun 15 '16 at 19:24
• @AdamFrancey Well, I've just checked, and this is exactly what is written in the book. I didn't even notice that, to be honest. Does this render the question unanswerable? Jun 15 '16 at 19:31
• Weird. Does it have something to do with(or do you know why they say) "there are $2^{n-1}$ choices for $S$"? Since $S \in P(A)$ but $|P(A)| = 2^n$? Jun 15 '16 at 19:44
• Ah I see now. Pick an $a \in A$. There are $2^{n-1}$ sets in $P(A)$ that contain $a$ (straightforward to prove). So you have $\{(a,S)\}$ where each particular $a$ has $2^{n-1}$ possible choices for $S$. Not sure why they stated it so awkwardly! Jun 15 '16 at 20:30
• To answer my first comment: the existence of $a$ is implied in the definition, excluding the possibility that $S$ is the empty set. Jun 15 '16 at 20:37

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

• Got it, thanks for your help. Jun 16 '16 at 6:52