# List all subsets of {a, b, c, d, e}, containing a but not containing b

I wonder...can I solve this by just getting A = {a, c, d, e} minus those subsets which do not contain a?

So, let A be {a, c, d, e}. |A| is 2^4 = 16 And let B be {c, d, e}. |B| is 8 And let C be subset of subsets of {a, b, c, d, e}, containing a but not containing b

Can I conclude that that |C| will be 8, that is, |A| - |B|?

I could enumerate these:

• {a}
• {a, c}
• {a, d}
• {a, e}
• {a, c, d}
• {a,c, e}
• {a, d, c}
• {a, d, e}

Which are 8, not including the empty set so I guess there is some mistake with my reasoning. Could you people point that out for me?

P.S: this question is from the book Discrete Mathematics: Elementary and Beyond, by Lovász et al.

-
You missed $\{a,c,d,e\}$, and you counted $\{a,c,d\}$ and $\{a,d,c\}$ as different though they are the same. Otherwise your logic is fine. –  vadim123 Jul 11 '13 at 18:26
You can count the subsets that contain $a$, but not $b$, without listing, since you get them by adding $a$ to a subset of $\{c,d,e\}$. –  André Nicolas Jul 11 '13 at 18:37
You may want to specify that $a \ne b$. –  dfeuer Jul 11 '13 at 18:40

All you need to do is list all subsets of $\{c,d,e\}$, and then add $a$ to each of those. There are eight of them. (You've listed $\{a,c,d\}$ twice though, and you missed one of the eight.)

-

You missed $\{a,c,d,e\}$. And, you have listed $\{a,c,d\}$ twice. This is because in set notation, the order of the elements within the brackets does not matter (so $\{a,c,d\}$ is the same set as $\{a,d,c\})$

-
Yes, I knew that! Just a mistake for lack of the proper attention. Thanks. –  rodrigoalves Jul 11 '13 at 18:39

An important concept is something called a "power set". If $S$ is a set, then the power set of $S$ is the set of all subsets of $S$, and may be written $P(S)$, $\mathcal P(S)$, or $\mathscr P(S)$, depending on taste.

For example, $$\mathcal P(\varnothing)=\{\varnothing\}$$ and $$\mathcal P(\{1,2\})=\{\varnothing,\{1\},\{2\},\{1,2\}\}.$$

List out $|\mathcal P(S)|$ for $S=\{1,\ldots,n\}$ for a few small values of $n$.

Now think about how you might represent the power set of $S$ as a finite sequence of $1$s and $0$s, that is, as a bit vector.

Can you see why the power set has the size it does for each $n$?

If $S$ and $T$ are sets, then $S^T$ is the set of all functions from $T$ into $S$.
Mathematicians often like to define $2:=\{ 0, 1 \}$.
Can you see how $2^T$ relates to $\mathcal P(T)$? Can you see how $|2^T|$ relates to $|T|$?