Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Is this true or false? I also need an explanation as to how we can get the subsets.

share|cite|improve this question
Hint: look up "cardinality of the power set". – Deepak Jun 8 '14 at 11:06
Take a subset $A_1$ and pair it up with its complement. Take another subset $A_2$ not already considered and pair it up with its complement. Continue... – David Mitra Jun 8 '14 at 11:51
A set containing all subsets of a set A is called a power set. It always has even cardinality, except when A is an empty set. So, false. – Rok Kralj Jun 8 '14 at 12:27
@DavidMitra: of course, you are assuming $1001 > 0$, otherwise for some $n$ $A_n$ equals its own complement... ;) – askyle Jun 8 '14 at 15:27
@DavidG: The power set of the empty set is the set containing the empty set, which has cardinality one. – Hurkyl Jun 8 '14 at 18:24

Match each element of the set with a $0$ or a $1$. Each arrangement of $1001$ $0$s and $1$s represents a subset, where a $1$ means that that element is in the subset and a $0$ means that element is not in the subset.

There are $2^{1001}$ arrangements of $1001$ $0$s and $1$s, so there are $2^{1001}$ subsets of a set with $1001$ elements.

share|cite|improve this answer

HINT: $$\sum_{k=0}^{1001}\binom{1001}{k}=2^{1001}$$

share|cite|improve this answer
With the proper interpretation of $\binom{1001}{k}$, that works, too :-) – robjohn Jun 8 '14 at 11:16
is the statement false? – Surdz May 24 at 3:26

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.