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|\).