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.

  • $\begingroup$ "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. $\endgroup$ Jul 10 '17 at 14:15
  • 2
    $\begingroup$ @MauroALLEGRANZA why not make an answer to the question instead of several comments that do the same thing? $\endgroup$ Jul 10 '17 at 14:33
  • $\begingroup$ 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. $\endgroup$ 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}$.

  • $\begingroup$ 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. $\endgroup$ Jul 10 '17 at 15:51
  • $\begingroup$ @SepticWomb - correct. The pair $(1, \{ 1,2,3,4,5 \})$ is in while the pair $(2, \{ 3,4,5 \})$ is not. $\endgroup$ 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.


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.