# Help understand this proof of even and odd subsets

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.

• In your example there are four subsets with an even number of elements and four with an odd number of elements: you have to try to pair up even sets with odd ones. – DonAntonio Nov 17 '13 at 5:16
• @DonAntonio Nice tip! Does that mean $\{1,2,3\}$ gets paired with $\phi$? Because I don't see any other possible pairing for it. – dotslash Nov 17 '13 at 5:20
• You can do the pairing as you like, but better to follow a well defined and clear strategy just as Ittay's answer proposes. – DonAntonio Nov 17 '13 at 5:22

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.
$\phi, \{1\}\\ \{2\}, \{1,2\}\\ \{3\}, \{1,3\}\\ \{2,3\}, \{1,2,3\}$