Let S = {1,2,...,n}. Define a function f from E = {subsets of S with even cardinality} to

O = {subsets of S with odd cardinality}

as follows: Given T E a subset of S with even cardinality, if n T , then define f (T ) = T \ {n}. Otherwise, if n / T , then define f (T ) = T {n}.

(a) Check that f is well defined, meaning that for all T E then f(T) O. (b) Show that f is onto.

(c) Show that f is one-to-one. (d) Explain how this proves that |E| = |O| = 2^(n1).