Bijective proof

Oct 2009
255
20
St. Louis Area
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 \(\displaystyle 2^{n}\).

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

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

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

ONTO: Given b=\(\displaystyle b_{1}b_{2}...b_{i}...b_{n}\) where \(\displaystyle b_{i}\) is a 1 or 0 according to whether i \(\displaystyle \in \) a or i \(\displaystyle \notin\) a respectively, we need to find a such that f(a)=b and a \(\displaystyle \subseteq\) A.
Choose a={\(\displaystyle a_{i}|a_{i} \) is the \(\displaystyle i^{\{th\}}\) member of P(n) and \(\displaystyle b_{i}\)= 1}. This means a \(\displaystyle \subseteq\) A which means f is ONTO. Since f is one-to-one and onto, f is a bijection.
 
Mar 2010
116
41
Bratislava
Let a \(\displaystyle \subseteq\) A and b \(\displaystyle \subseteq\) B and b=\(\displaystyle b_{1}b_{2}...b_{i}...b_{n}\)
I think you meant \(\displaystyle b\in B\)

Choose a={\(\displaystyle a_{i}|a_{i} \) is the \(\displaystyle i^{\{th\}}\) member of P(n) and \(\displaystyle 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.
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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 \(\displaystyle 2^{n}\).

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

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

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

ONTO: Given b=\(\displaystyle b_{1}b_{2}...b_{i}...b_{n}\) where \(\displaystyle b_{i}\) is a 1 or 0 according to whether i \(\displaystyle \in \) a or i \(\displaystyle \notin\) a respectively, we need to find a such that f(a)=b and a \(\displaystyle \subseteq\) A.
Choose a={\(\displaystyle a_{i}|a_{i} \) is the \(\displaystyle i^{\{th\}}\) member of P(n) and \(\displaystyle b_{i}\)= 1}. This means a \(\displaystyle \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 \(\displaystyle 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 \(\displaystyle A\) be the powerset of \(\displaystyle \{1,2,...,n\}\) and let \(\displaystyle B\) be the set of \(\displaystyle n\)-digit binary numbers (leading zeroes allowed).

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

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

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

Therefore, \(\displaystyle f\) is bijective and \(\displaystyle |A| = |B|\).
 
  • Like
Reactions: oldguynewstudent

Drexel28

MHF Hall of Honor
Nov 2009
4,563
1,566
Berkeley, California
Give a bijective proof: The number of subsets of [n] equals the number of n-digit binary numbers.

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

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

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

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

Therefore, \(\displaystyle f\) is bijective and \(\displaystyle |A| = |B|\).
Compare