Thread: Prove comnplement function on [n] is bijective

Please critique the following proof.

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

Prove f is one-to-one: Given [n] where n is odd. Assume and are two unequal sets of odd sized subsets on [n]. We have defined the set complement function and .

If is the complement of on [n] and is the complement of on [n] then . But is the set of even subsets on [n] and is also the the set of even subsets on [n], so must = since the number of even subsets on [n] is fixed. Therefore on [n] so and therefore 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 [n], we need to find another set A such that f(A)=B. Choose A= . Then f( ) = . Therefore f is onto. Since f is one-to-one and onto, f is bijective.

Originally Posted by oldguynewstudent

Let and 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.