I need help understanding the proof of the following statement, as given in the book I'm following:
Show that a non-empty set has an equal number of even subsets (that is, subsets with an even number of elements) and odd subsets.
The idea of bijection or C(n,k) hasn't been introduced yet, so the proof relies on simple logic:
Divide all subsets into pairs such that each pair differs only in their first element. Each pair contains an even and an odd subset, so their numbers are the same.
I'm not at all sure I follow this. If I consider the subsets of $\{1,2,3\}$ to be $\phi, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}$, how are the pairings to be done? I could start as follows:
$$
\{1\} \Leftrightarrow \{2\}
$$
$$
\{3\} \Leftrightarrow \phi
$$
$$
\{1,2\} \Leftrightarrow \{3,2\}
$$
But then I don't see how $\{1,3\}$ and $\{1,2,3\}$ can be paired. More generally, I don't see how the proof works. Please explain.
Best Answer
The explanation in the text is indeed unclear. The idea is to fix one element from the set, say, $1$ in your example, and then pair every subset that does not contain $1$ with one that does contain $1$. This gives the pairing: $$ \emptyset \iff \{1\}, \{2\} \iff \{1,2\}, \{3\}\iff \{1,3\}, \{2,3\}\iff \{1,2,3\} $$
The pairing is simply obtained by removing $1$ if it were in the set, or adjoining $1$ if it was not in the set. This operation changes the parity of the subset and is a reversible process, thus a bijection.