# Bijective proof

• May 27th 2010, 08:31 PM
oldguynewstudent
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 $\longrightarrow$B 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.
• May 27th 2010, 11:49 PM
kompik
Quote:

Originally Posted by oldguynewstudent
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
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.
• May 28th 2010, 12:05 AM
undefined
Quote:

Originally Posted by oldguynewstudent
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 $\longrightarrow$B 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 $i$th 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 $i$th 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 $i$th bit of $b$.

Therefore, $f$ is bijective and $|A| = |B|$.
• May 28th 2010, 12:11 AM
Drexel28
Quote:

Originally Posted by oldguynewstudent
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

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 $i$th 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 $i$th 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 $i$th bit of $b$.

Therefore, $f$ is bijective and $|A| = |B|$.

Compare