Prove comnplement function on [n] is bijective

**oldguynewstudent** · Jun 23rd 2010, 08:19 PM

Please critique the following proof.

Let $\mathcal{E}$ and $\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 $\mathcal{E}$ to sets in $\mathcal{O}$ . Is this a bijection? Prove or disprove.

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

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

**MoeBlee** · Jun 24th 2010, 08:54 AM

Originally Posted by oldguynewstudent

Let $\mathcal{E}$ and $\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.

Thread: Prove comnplement function on [n] is bijective

LinkBack

Thread Tools

Display

Prove comnplement function on [n] is bijective

Similar Math Help Forum Discussions

Is my work correct? Prove the following is bijective.

How to prove this function is bijective

Prove about no bijective fuction exist

let f:A ---> B and g:B ---> C (if both are bijective, prove g o f is bijective)

How to prove that this function is bijective...

Search Tags