2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – DonAntonio
    Commented Nov 17, 2013 at 5:16
  • $\begingroup$ @DonAntonio Nice tip! Does that mean $\{1,2,3\}$ gets paired with $\phi$? Because I don't see any other possible pairing for it. $\endgroup$
    – ankush981
    Commented Nov 17, 2013 at 5:20
  • $\begingroup$ You can do the pairing as you like, but better to follow a well defined and clear strategy just as Ittay's answer proposes. $\endgroup$
    – DonAntonio
    Commented Nov 17, 2013 at 5:22

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Wow, what an answer! This also tells me how the proof works: first remove a certain elements and form all the possible subsets. Now add this element to these and keep pairing. The addition changes the parity every time, which proves these sets are equal in number. :D $\endgroup$
    – ankush981
    Commented Nov 17, 2013 at 5:29
1
$\begingroup$

Just pick one element, i.e. 1

Now, pair it in this way:

$\phi, \{1\}\\ \{2\}, \{1,2\}\\ \{3\}, \{1,3\}\\ \{2,3\}, \{1,2,3\}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .