Proof of Bijection

Question

Let $\def\Powerset{\mathcal P}X = \{1, 2, . . . , n\}$. Define a map on $f : \Powerset(X) \to \Powerset(X)$ as follows: for any $A ⊆ X$,

Let $f(A) =\begin{cases}A \setminus\{n\} &\text{, if }& n \in A,\\ A \cup\{n\} &\text{, if }&n \notin A\end{cases}$

Prove that $f$ is a bijection which maps odd subsets of $X$ onto even subsets of $X$ and vice versa (here, “odd” and “even” refers to the cardinality, i.e. number of elements, in a subset). Use this to find the number of even subsets of $X$ and the number of odd subsets of $X$.

Answer 1

To show the bijection:

Surjectivity:

For $A\subset X,$ if $A$ contains $n,$ then $A=f(A\setminus \{n\});$ if $A$ doesn't contain $n,$ then $A=f(A\cup\{n\}).$

Invectivity:

For $A\subset X,$ if $f(A)$ contains $n,$ then $A=f(A)\setminus \{n\};$ if $f(A)$ doesn't contain $n,$ then $A=f(A)\cup\{n\}.$

Since the inverse map can be explicitly expressed and well-defined, the map is a bijection.