Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.)

share|cite|improve this answer

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\})$

share|cite|improve this answer
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$?

Continuing your education …

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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