# Ordered pairs in set-builder notation.

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.

• "all elements of $\mathcal P(A)$ are sets". 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. – Mauro ALLEGRANZA Jul 10 '17 at 14:15
• @MauroALLEGRANZA why not make an answer to the question instead of several comments that do the same thing? – Bob Krueger Jul 10 '17 at 14:33
• I understand how the set produced looks like this: { (1, ∅), (1, {1}), (1, {2}),...,(n, {1,2,3,...,n}) } It's the S \ {a} bit I don't understand. Why must S not include {a}? I'm probably wording this badly, as this is very new to me, but I don't see why (a, {a}) can't be a pair, in which case the cardinality is simply a x S = a x |P(A)|, i.e., 2n^2. As an aside, I'm wondering about the empty set, which has no elements, in which case a ∈ S is impossible when S = ∅. I really need a human tutor I think. – Septic Womb Jul 10 '17 at 14:57

"all elements of $\mathcal P(A)$ are sets".

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:

$\mathcal P(A) = \{ \emptyset,\{ 1 \}, \{ 2 \}, \{ 3 \}, \{ 1,2 \}, \{ 1,3 \}, \{ 2,3 \}, \{ 1,2,3 \} \}$.

Thus, for $a=1$ we have that:

$\{ (1,S): S ∈ \mathcal P(A) \} = \{ (1,\emptyset),(1,\{ 1 \}),(1,\{ 2 \}),(1,\{ 3 \}),(1,\{ 1,2 \}),(1,\{ 1,3 \}),(1, \{ 2,3 \}),(1,\{ 1,2,3 \}) \}$

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:

$\{ (a,S) : a∈S, S∈ \mathcal P(A) \}$.

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

• Thank you for your help! It's starting to make sense, I'll have to read it a couple of times so it sinks in. I think what you're getting at (I hope I'm not mistaken!), is that in each pair, the S-component must have the a-component as an element? So, for example, the pair (2, {3,4,5}) would not satisfy the conditions of the overall set, as 2 ∉ {3,4,5} ; is that correct? Sorry for my naivety, and thank you very much for your time and patience. – Septic Womb Jul 10 '17 at 15:51
• @SepticWomb - correct. The pair $(1, \{ 1,2,3,4,5 \})$ is in while the pair $(2, \{ 3,4,5 \})$ is not. – Mauro ALLEGRANZA Jul 10 '17 at 19:12

For every fixed $a \in S$, there are $2^{n-1}$ subsets of $S$ that contain $a$, namely as much as all subsets of $A\setminus\{a\}$ (we just add $a$ to it, and clearly every $S$ with $a \in S$ can be written as $S = \{a\} \cup (S\setminus\{a\})$ (and $S\setminus\{a\}$ is a subset of $A \setminus \{a\})$ so $S \to S\setminus \{a\}$ is a bijection between $\{S \subseteq A: s \in A\}$ and $\mathcal{P}(A \setminus \{a\})$.

As there are $n$ choices for $a$ we get that this set has $n2^{n-1}$ elements.

Another way to get the same result:

First you select $a$. There are $n$ possibilities for that.

Then you have to select an $S\subseteq A$ such that $a\in S$. It is a given that $a$ must be there, but for each of the $n-1$ other elements of $A$, you have a choice of either including it in $S$ or not. So there are $n-1$ choices with $2$ possibilities. By the principle of multiplication, this gives $$n \cdot \underbrace{2 \cdot 2 \cdots 2}_{n-1\text{ twos}} = n 2^{n-1}$$ valid $(a,S)$ pairs.