2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Is the first one written right? If $S \in P(A)$ is the empty set, then what is $a\in S$? $\endgroup$ Jun 15 '16 at 19:24
  • $\begingroup$ @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? $\endgroup$ Jun 15 '16 at 19:31
  • $\begingroup$ 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$? $\endgroup$ Jun 15 '16 at 19:44
  • 1
    $\begingroup$ 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! $\endgroup$ Jun 15 '16 at 20:30
  • 1
    $\begingroup$ To answer my first comment: the existence of $a$ is implied in the definition, excluding the possibility that $S$ is the empty set. $\endgroup$ Jun 15 '16 at 20:37
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Got it, thanks for your help. $\endgroup$ Jun 16 '16 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.