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 [duplicate]

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.

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$.

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\})$.