Results 1 to 4 of 4

Math Help - Bijective proof

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

    Bijective proof

    This may be totally wrong but please let me know what is wrong with the following proof:

    Give a bijective proof: The number of subsets of [n] equals the number of n-digit binary numbers.

    Let A be the set of all subsets of P(n). Let B be the set of all binary numbers 2^{n}.

    Let a \subseteq A and b \subseteq B and b= b_{1}b_{2}...b_{i}...b_{n}

    Define f: A \longrightarrowB where f(a)=b= b_{1}b_{2}...b_{i}...b_{n} and b_{i} is a 1 or 0 according to whether i \in a or i \notin a respectively.

    Prove: f is bijective
    One-to-One: Assume a_{1}= a_{2} and f(a_{1}) \not=f(a_{2}) where f(a_{1})=b_{1}and f(a_{2})=b_{2}. Now b_{1}\not=b_{2} which means that there is some i where (b_{1})_{i} \not= (b_{2})_{i}. This means that either (i \in a_{1} and i \notin a_{2} ) or (i \notin a_{1} and i \in a_{2} ), but a_{1}=a_{2} which is a contradiction. So f(a_{1}) must = f(a_{2}) which means b_{1}=b_{2}. This proves f is one-to-one.

    ONTO: Given b= b_{1}b_{2}...b_{i}...b_{n} where b_{i} is a 1 or 0 according to whether i \in a or i \notin a respectively, we need to find a such that f(a)=b and a \subseteq A.
    Choose a={ a_{i}|a_{i} is the i^{\{th\}} member of P(n) and b_{i}= 1}. This means a \subseteq A which means f is ONTO. Since f is one-to-one and onto, f is a bijection.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by oldguynewstudent View Post
    Let a \subseteq A and b \subseteq B and b= b_{1}b_{2}...b_{i}...b_{n}
    I think you meant b\in B

    Quote Originally Posted by oldguynewstudent View Post
    Choose a={ a_{i}|a_{i} is the i^{\{th\}} member of P(n) and b_{i}= 1}.
    I guess you mean i-th element of [n], not of P(n). So you can simply write i instead of a_i. (I assume [n]={1,2,...,n}.)

    With the exception of these typos, the basic idea of the proof is ok.

    The same result is true for arbitrary sets, have a look at wikipedia for example.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    This may be totally wrong but please let me know what is wrong with the following proof:

    Give a bijective proof: The number of subsets of [n] equals the number of n-digit binary numbers.

    Let A be the set of all subsets of P(n). Let B be the set of all binary numbers 2^{n}.

    Let a \subseteq A and b \subseteq B and b= b_{1}b_{2}...b_{i}...b_{n}

    Define f: A \longrightarrowB where f(a)=b= b_{1}b_{2}...b_{i}...b_{n} and b_{i} is a 1 or 0 according to whether i \in a or i \notin a respectively.

    Prove: f is bijective
    One-to-One: Assume a_{1}= a_{2} and f(a_{1}) \not=f(a_{2}) where f(a_{1})=b_{1}and f(a_{2})=b_{2}. Now b_{1}\not=b_{2} which means that there is some i where (b_{1})_{i} \not= (b_{2})_{i}. This means that either (i \in a_{1} and i \notin a_{2} ) or (i \notin a_{1} and i \in a_{2} ), but a_{1}=a_{2} which is a contradiction. So f(a_{1}) must = f(a_{2}) which means b_{1}=b_{2}. This proves f is one-to-one.

    ONTO: Given b= b_{1}b_{2}...b_{i}...b_{n} where b_{i} is a 1 or 0 according to whether i \in a or i \notin a respectively, we need to find a such that f(a)=b and a \subseteq A.
    Choose a={ a_{i}|a_{i} is the i^{\{th\}} member of P(n) and b_{i}= 1}. This means a \subseteq A which means f is ONTO. Since f is one-to-one and onto, f is a bijection.
    I see nothing wrong with your proof except a few small notational issues. It seems you use [n] and P(n) interchangeably which is a little confusing, and on the last line you mention the i'th member of P(n)... which is just i, right? Also the way you defined B at the beginning doesn't seem quite right. Perhaps you mean the set of all (binary) integers b such that 0 \leq b < 2^n, or simply the set of all n-digit binary numbers as in the problem statement. And then the "subset of" versus "member of" symbol kompik mentioned.

    But I'm wondering if a shorter proof could be considered rigorous, given that it's really a simple concept we're trying to prove here.

    So, as above, let A be the powerset of \{1,2,...,n\} and let B be the set of n-digit binary numbers (leading zeroes allowed).

    Define f: A \to B, f: a \mapsto b such that for all i, 0 < i \leq n, i \in a if and only if the ith bit of b is 1.

    f is one-to-one because for any a_1 \in A, a_2 \in A, a_1 \neq a_2 there exists an element i which is either in a_1 but not in a_2 or vice versa; because otherwise a_1 = a_2. Therefore the ith bit of f(a_1) differs from that of f(a_2) and f(a_1) \neq f(a_2).

    f is onto because every b \in B can be used to construct an a \in A. Simply build up a by deciding for all i, 0 < i \leq n whether i \in a or i \not \in a according to the ith bit of b.

    Therefore, f is bijective and |A| = |B|.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by oldguynewstudent View Post
    Give a bijective proof: The number of subsets of [n] equals the number of n-digit binary numbers.

    Let A be
    Quote Originally Posted by undefined View Post

    So, as above, let A be the powerset of \{1,2,...,n\} and let B be the set of n-digit binary numbers (leading zeroes allowed).

    Define f: A \to B, f: a \mapsto b such that for all i, 0 < i \leq n, i \in a if and only if the ith bit of b is 1.

    f is one-to-one because for any a_1 \in A, a_2 \in A, a_1 \neq a_2 there exists an element i which is either in a_1 but not in a_2 or vice versa; because otherwise a_1 = a_2. Therefore the ith bit of f(a_1) differs from that of f(a_2) and f(a_1) \neq f(a_2).

    f is onto because every b \in B can be used to construct an a \in A. Simply build up a by deciding for all i, 0 < i \leq n whether i \in a or i \not \in a according to the ith bit of b.

    Therefore, f is bijective and |A| = |B|.
    Compare
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 30th 2010, 10:49 PM
  2. bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 12th 2009, 02:09 PM
  3. [Proof] Two's Complement representation is bijective
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: October 24th 2009, 07:31 AM
  4. Bijective function proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 23rd 2009, 05:35 PM
  5. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 2nd 2009, 01:30 PM

Search Tags


/mathhelpforum @mathhelpforum