I have a problem which is probably quite basic, as I've only just begun studying Set Theory, but I can't wrap my head around it, and need help. The problem is as follows:
$$A = \{1, 2, 3,…, n\}$$
Find the cardinality of the following:
$$\{ (a,S) : a \in S, S \in \mathcal P(A) \}$$
As I understand it, all elements of $\mathcal P(A)$ are sets, including the empty set, and all elements of $S$ will be natural numbers, ranging from $1$ to $n$. So, I (think) I understand that there are $n$ ways to choose $a$; selecting $a$ from any set $S$, there are a maximum of $n$ options. (Please correct if mistaken.)
However, the solution given says there are $2^{n-1}$ ways to select $S$, such that $S \setminus \{a\}$. I don't understand this. I thought this set would give a large set containing subsets of pairs, of the sort (for example) $\{ 1, \{1\} \}$, if $a = 1$ and $S = \{1\}$, or $\{ n, \{1,2,3,4\} \}$, if $a = n$, and $S = \{1,2,3,4\}$, and so on, so no subset will contain duplicates. I don't understand why $S \setminus \{a\}$ is relevant. Please help! The book I'm using gives the cardinality as $n2^{n-1}$, but is not very detailed, and I can't see what's going on. Thank you.
Best Answer
Yes; but they are the subsets of $A$. If $A$ has $n$ elements, then $\mathcal P(A)$ has $2^n$ elements, "starting" from $\emptyset$ up to $A$ itself.
Consider the simple example with $n=3$, i.e. $A= \{ 1,2,3 \}$.
We have that $\mathcal P(A)$ has $2^3=8$ elements:
Thus, for $a=1$ we have that:
i.e. again $8$ elements.
The same for $a=2$ and $a=3$. Conclusion: $24=3 \times 8= n \times 2^n$.
But the definition is slightly more complicated:
We have to pick-up pairs $(a,S)$ such that $a \in S$: this excludes of course the possibility $S=\emptyset$. But other cases must be excluded as well.
As we can verify in the simplified example, with $a=1$ we have only four pairs with $1 \in S, S \in \mathcal P(A)$.
And we have $4=2^2=2^{n-1}$ for our example with $n=3$.
We have again $3$ possible choices for $a$, and thus - in this case - we have $n \times 2^{n−1}$ pairs.
Some more calculations ...
Why in general, for fixed $a$, we have $2^{n-1}$ elements $S \in \mathcal P(A)$ such that $a \in S$ ?
With $n$ elements we have that $\mathcal P(A)$ has $2^n$ elements.
If we remove $a$, the set left $A'=A \setminus \{ a \}$ has $n-1$ elements; thus $\mathcal P(A')$ has $2^{n-1}$ elements.
The subsets of $A$ are all the subsets of $A'$ "plus" the subsets obtained from the previous ones "adding" $a$.
This is shown by the fact that: $2^n=2 \times 2^{n-1}=2^{n-1}+2^{n-1}$.
In conclusion, the subsets of $A$, i.e. the elements of $\mathcal P(A)$ are $2^{n-1}$ subsets with $a$ inside plus $2^{n-1}$ subsets without $a$ [see again the simplified example].
This gives us the fact that, for fixed $a$, the number of pairs $(a,S)$ such that $a \in S$ are $2^{n-1}$.