# Bijective proof

#### 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.

#### kompik

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.

• oldguynewstudent and undefined

#### undefined

MHF Hall of Honor
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|$$.

• oldguynewstudent

#### Drexel28

MHF Hall of Honor
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

• oldguynewstudent and undefined