# The total number of subsets of a set of size 1001 is odd

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

-
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.
HINT: $$\sum_{k=0}^{1001}\binom{1001}{k}=2^{1001}$$
With the proper interpretation of $\binom{1001}{k}$, that works, too :-) –  robjohn Jun 8 '14 at 11:16