Proof that $f: \mathrm{P}(X) \rightarrow \mathbb{N}$ is injective

Question

Situation: Take $n \in \mathbb{N}$, let $X = \{0, 1,..., n-1\}$ and define map $f: \mathrm{P}(X) \rightarrow \mathbb{N}$ through $f(A) = \sum_{i \in A} 2^i$

Question 1: Proof that $f$ is injective.

Question 2: What is the map of $f$?

Could someone please help me with these questions?

I do understand that a function is injective if $f(x)=f(y)$ implies that $x=y$. I also found out that when you take for example $n=3$, you'll get \begin{eqnarray} f(\{0\}) = 2^0 &=& 1 \\ f(\{1\}) = 2^1 &=& 2 \\ f(\{0,1\}) = 2^0 + 2^1 &=& 3 \\ f(\{2\}) = 2^2 &=& 4 \\ f(\{0,2\}) = 2^0 + 2^2 &=& 5 \\ f(\{1,2\}) = 2^1 + 2^2&=& 6 \\ f(\{0,1,2\}) = 2^0 + 2^1 + 2^2 &=& 7 \end{eqnarray}

So the new result is the last one plus 1. Somehow I think this is useful in the proof.

Note: English isn't my first language. So excuse me for any grammar mistakes.

Answer 1

You need to show that if $f(A) = \sum_{i \in A} 2^i = \sum_{i \in B} 2^i = f(B) $, where $A,B \subset \{0,...,n-1\}$, then $A=B$.

First note that $f(A) > 0$ iff $A \neq \emptyset$. Hence if $A =\emptyset$ we must have $B=\emptyset$ and vice versa.

So, suppose that neither of $A,B$ are empty.

The essential result here is that $2^0+2^1+...+2^{k-1} = 2^{k}-1 < 2^{k}$.

Let $k_A = \max A$, $k_B = \max B$, and suppose $k_A \ge k_B$ without loss of generality. If $k_A > k_B$, then we would have $f(A) \ge 2^{k_A}$, whereas the above equality shows that $f(B) \le 2^0+2^1+...+2^{k_B} = 2^{k_B+1}-1 \le 2^{k_A} - 1 < f(A)$, a contradiction. Hence we have $k_A = k_B$.

Now let $A'=A \setminus \{k_A\}$, $B'=B \setminus \{k_A\}$ and repeat the process. This shows $A=B$.

It is clear that $A$ represents the indices of the non-zero coefficients of the binary expansion of $f(A)$, and the minimum is $f(\emptyset) = 0$ and the maximum is $f(\{1,...,n-1\}) = 2^n-1$. Since $f$ is injective, and $|{\cal P(\{1,...,n-1\})}| = 2^n $, we see that the range must be the integers $0,...,2^n-1$.

Answer 2

observe that you are basically just mapping the binary notation of a number to the corresponding decimal number.

for example {0,2}=5(dec)=101(bin)

or {1,2)=6(dec)=110(bin)

see that the nth digit in the binary number is 1 is n is in X, and else it's 0.

so in other words, you have to proof that you can writing a decimal number in only one way in binary