# Bijections from $A$ to $B$, where $A$ is the set of subsets of $[n]$ that have even size and $B$ is the set of subsets of $[n]$ that have odd size

Let $A$ be the set of subsets of $[n]$ that have even size, and let $B$ be the set of subsets of $[n]$ that have odd size. Establish a bijection from $A$ to $B$. The following bijection is suggested for $n=3$:

$$\matrix{A: & \{1,2\} & \{1,3\} & \{2,3\} & \varnothing\\ B: & \{1,2,3\} & \{1\} & \{2\} & \{3\}}$$

I know that first we have to establish a function that is both surjective and injective so that it is bijective. I don't know where to take a step from here in the right direction. So I need a bit of guidance.

Something suggested is let f be the piecewise function:

$$f(x) = x \setminus \{n\}\text{ if }n \in x\text{ and }f(x) = x\cup\{n\}\text{ if }n \notin x$$

-
You might pick an $n$ and see how that function works if you apply it to the sets in A. Maybe that will give an idea for the general case. –  Ross Millikan Oct 6 '11 at 2:35
Salazar, I edited the function to what the suggestion should have been, whether it was or not: what you originally had does not make sense, since it defines $f(x)$ in a self-contradictory fashion. –  Brian M. Scott Oct 6 '11 at 3:01

The function says to map a subset either to itself minus $\{n\}$ (if the subset contains $n$) or to itself union $\{n\}$ (if the subset does not contain $n$). Clearly a subset cannot both contain $n$ and not contain $n$, so there is no problem deciding which case we are in.

To prove the $f$ is injective, let $A_1$ and $A_2$ be two subsets and consider $f(A_1) = f(A_2)$. Either we have $$A_1 - \{n\} = f(A_1) = f(A_2) = A_2 - \{n\}$$ or $$A_1 \cup \{n\} = f(A_1) = f(A_2) = A_2 \cup \{n\}.$$ In either case, we can conclude that $A_1 = A_2$, and so $f$ is injective.

To prove that $f$ is surjective, let $B$ be an element of the range of $f$ (i.e. a subset of odd size). If $B$ contains $n$, then $B - \{n\}$ is a subset of even size that maps to $B$ under $f$. If $B$ does not contain $n$, then $B \cup \{n\}$ is a subset of even size that maps to $B$ under $f$. Since everything in the image has something in the domain that maps to it, $f$ is surjective.

-
This is an elementary combinatorial question, and the suggested proof is very much a combinatorial proof. –  Brian M. Scott Oct 6 '11 at 2:55
what if $n = 0$? –  Salazar Oct 6 '11 at 3:00
@Salazar: For $n=0$ the result is false: the empty set has only one subset, itself, and that set has an even number of elements. –  Brian M. Scott Oct 6 '11 at 3:02
That is what I thought @BrianM.Scott . So would it work to say that f: A -> B (the current function), then we define g: B -> A. I was thinking that f(g(x)) is the identity for B, and g(f(x)) for A. So this implies g is the inverse of f, so f is a bijection. –  Salazar Oct 6 '11 at 3:08
@Salazar: If you can find $g:B\to A$ such that $f\circ g$ is the identity, you’ve shown that $f$ is a bijection. And there’s a very good candidate for $g$: if you haven’t already spotted it, take a look at the hint in my answer. –  Brian M. Scott Oct 6 '11 at 3:11

The example shown for $n=3$ illustrates the suggested bijection (which I corrected from the version in your post): the two sets in each column differ only by the presence or absence of the number $3$. Note that $x$ and $f(x)$ always differ in size by exactly $1$, so one of them must have even size, and the other must have odd size. This shows that the suggested $f$ really does take even-sized sets to odd-sized sets. Now you have to show that $f:A\to B$ is injective and surjective.

• To show that $f$ is injective, assume that $x,y\in A$ and $f(x) = f(y)$, and try to show that this forces $x=y$.

• To show that $f$ is surjective, start with a set $y\in B$ and try to find an $x\in A$ such that $f(x)=y$. This isn’t hard if you think about how $f$ works. (HINT: Consider $f$ as a function from $\wp([n])\to\wp([n])$; what does $f$ do to members of $B$?)

-

For $n$ an odd positive integer, there is a natural procedure. The mapping that takes any subset $E$ of $[n]$ with an even number of elements to its complement $[n]\setminus E$ is a bijection from $A$ to $B$.

Dealing with even positive $n$ is messier. Here is one way. The subsets of $[n]$ can be divided into two types: (i) subsets that do not contain $n$ and (ii) subsets that contain $n$.

(i) If $E$ is a subset of $[n]$ with an even number of elements, and does not contain $n$, map $E$ to $[n-1]\setminus E$. Call this map $\phi$.

(ii) If $E$ is a subset of $n$ with an even number of elements, and contains $n$, map $E$ to $\{n\} \cup \phi^{-1}(E\setminus\{n\})$.

-

Number the members of the set $1,2,3,4,\ldots,n$.

For every subset with an even number of elements, there is a corresponding set with an odd number of elements, that corresponds in this way:

• If $1$ is a member of the set with an even number of elements, then delete $1$ from the set to get a set with an odd number of elements.
• If $1$ is not a member of the set with an even number of elements, then add $1$ to the set to get a set with an odd number of elements.

For example, suppose the set is $\{1,2,3,4\}$. Then we have this correspondence between sets with an even number of elements and sets with an odd number of elements: $$\begin{array}{rcl} \text{even} & & \text{odd} \\ \hline \varnothing & \leftrightarrow & \{1\} \\ \{1,2\} & \leftrightarrow & \{2\} \\ \{1,3\} & \leftrightarrow & \{3\} \\ \{1,4\} & \leftrightarrow & \{4\} \\ \{2,3\} & \leftrightarrow & \{1,2,3\} \\ \{2,4\} & \leftrightarrow & \{1,2,4\} \\ \{3,4\} & \leftrightarrow & \{1,3,4\} \\ \{1,2,3,4\} & \leftrightarrow & \{2,3,4\} \end{array}$$

This won't work with the empty set because we don't have an element to which we can assign the number $1$.

-