Please critique the following proof.

Let $\displaystyle \mathcal{E}$ and $\displaystyle \mathcal{O}$ be the sets of even- and odd-sized subsets of [n], respectively. If n is odd then the set complement function maps sets in $\displaystyle \mathcal{E}$ to sets in $\displaystyle \mathcal{O}$. Is this a bijection? Prove or disprove.

Prove f is one-to-one: Given [n] where n is odd. Assume $\displaystyle \mathcal{O}_{1}$ and $\displaystyle \mathcal{O}_{2}$ are two unequal sets of odd sized subsets on [n]. We have defined the set complement function $\displaystyle f(\mathcal{E}_{1})=\mathcal{\bar{E}}_{1}=\mathcal{ O}_{1}$ and $\displaystyle f(\mathcal{E}_{2})=\mathcal{\bar{E}}_{2}=\mathcal{ O}_{2}$.

If $\displaystyle \mathcal{O}_{1}$ is the complement of $\displaystyle \mathcal{E}_{1}$ on [n] and $\displaystyle \mathcal{O}_{2}$ is the complement of $\displaystyle \mathcal{E}_{2} $ on [n] then $\displaystyle \mathcal{E}_{1} \neq\mathcal{E}_{2}$. But $\displaystyle \mathcal{E}_{1}$ is the set of even subsets on [n] and $\displaystyle \mathcal{E}_{2}$ is also the the set of even subsets on [n], so $\displaystyle \mathcal{E}_{1}$ must = $\displaystyle \mathcal{E}_{2}$ since the number of even subsets on [n] is fixed. Therefore $\displaystyle \mathcal{\bar{E}}_{1}=\mathcal{\bar{E}}_{2}$ on [n] so $\displaystyle \mathcal{O}_{1}=\mathcal{O}_{2}$ and therefore $\displaystyle f(\mathcal{E}_{1})=f(\mathcal{E}_{2})$ proving f is one-to-one.

Now prove f in onto. We are given that f is the complement function on [n]. Given a set B$\displaystyle \subseteq$[n], we need to find another set A such that f(A)=B. Choose A=$\displaystyle \bar{\mathcal{E}}$. Then f($\displaystyle \bar{\mathcal{E}}$) = $\displaystyle \mathcal{E}$. Therefore f is onto. Since f is one-to-one and onto, f is bijective.

Originally Posted by oldguynewstudent

Let $\displaystyle \mathcal{E}$ and $\displaystyle \mathcal{O}$ be the sets of even- and odd-sized subsets of [n], respectively.

What does '[n]' stand for? Do you just mean the natural number n? (I.e., the von Neumann finite ordinal n?). If you do, then I would write this way:

Let f be the function from the powerset of n into the powerset of n defined by:

f(x) = {k in n | k not in x} for x subset of n.

First, just as an aside, though it is not used in the following proof, it is easy to show that, if n is odd, then, for all x subset of n, if card(x) is even then card(f(x)) is odd. (Easy since n is odd and therefore card(n)=n is odd, and an even number plus an even number is even.)

Show that f is bijection from the powerset of n onto the powerset of n:

Suppose x and y are different subsets of n. Without loss of generality, let k be in x but not in y. Then k in f(y) but not f(x), so f is 1-1. So f is an injection from powerset of n into the powerset of n.

Suppose x is a subset of n. So x = f({k in n | k not in x}). So f is onto the powerset of n.

So f is a bijection from the powerset of n onto the powerset of n.