Results 1 to 2 of 2

Math Help - Prove comnplement function on [n] is bijective

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244

    Prove comnplement function on [n] is bijective

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by oldguynewstudent View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is my work correct? Prove the following is bijective.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 28th 2010, 07:48 PM
  2. How to prove this function is bijective
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 8th 2010, 07:30 AM
  3. Prove about no bijective fuction exist
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: November 8th 2009, 06:31 AM
  4. Replies: 1
    Last Post: April 21st 2009, 10:45 AM
  5. Replies: 2
    Last Post: April 13th 2009, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum