1. ## 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 $\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.

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

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

3. 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 $\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|$.

4. 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
Originally Posted by undefined

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