Injective function example proof

Question

I'm struggling with the following homework question:

Let $n\in \mathbb{N}$.

Prove that the function $b:\begin{Bmatrix}0,1 \end{Bmatrix}^n\rightarrow\begin{Bmatrix}0,1,2,...,2^n-1\end{Bmatrix}$ defined by

$b(x_0,x_1,...,x_{n-1}) = \sum_{i=0}^{n-1}x_i\cdot 2^i$

is injective.

Is the function also a bijection? Give a quick reason for your answer.

Here's the definition of an injective function:

Suppose $X$ and $Y$ are sets and $f:X\rightarrow Y$ is a function.

$f$ is injective iff whenever $x_1,x_2 \in X$ and $f(x_1) = f(x_2)$, we have $x_1=x_2$

The professor mentioned that we should do this using proof by contraposition. So

I'm trying to prove that:

$b$ is injective iff whenever $(x_0,x_1,...,x_{n-1}), (y_0,y_1,...,y_{n-1}) \in \begin{Bmatrix}0,1\end{Bmatrix}^n$ and

$(x_0,x_1,...,x_{n-1}) \ne(y_0,y_1,...,y_{n-1})$ we have $b(x_0,x_1,...,x_{n-1}) \ne b(y_0,y_1,...,y_{n-1})$

So it would suffice to show that one is greater/lesser than the other.

From the formula of the sum of a geometric series we get that the set of size n with all $1$'s in

the domain maps to the last element of the co-domain $(2^n - 1)$. I'm not sure where to go from

here. Intuitively, any set of size n that's not all $1$'s will map to an element that's lesser

than $(2^n - 1)$, but how can I state this mathematically?

Thanks!

Answer 1

I am assuming that this is what is meant by contrapositive:

Suppose $x,y \in \{0,1\}^n$ and $x<y$. We want to show that $b(x) \neq b(y)$.

Let $k$ be the largest index such that $x_k \neq y_k$. Such an index must exist since otherwise $x=y$. Furthermore, we must have $x_k=0, y_k=1$, otherwise, since $2^0+\cdots+2^{k-1} < 2^k$, we would have $x>y$.

Let $x'_i = x_i$ for $i=1,...,k$ and $x'_i = 0$ otherwise. Define $y'$ similarly. Note that $b(x) = b(x')+b(x-x')$ and similarly for $y$.

By choice of $k$ we have $b(x-x') = b(y-y')$.

We have $b(x') \le 2^0+\cdots+2^{k-1} < 2^k \le b(y')$ and so $b(x)<b(y)$.

Note that we have shown that $b$ is strictly increasing. Hence $b(\{0,1\}^n)$ must contain $2^n$ elements and since $0 \le b(x) \le 2^n-1 $ we see that $b$ is surjective and hence bijective.

Answer 2

Assume that $b(x_0,x_1,...,x_{n-1}) = b(y_0,y_1,...,y_{n-1})$, hence $b(x_0,x_1,...,x_{n-1})-b(y_0,y_1,...,y_{n-1})=0$, i.e.,

$\sum_{i=0}^{n-1}(x_i-y_i)2^{i}=0$.

This is the binary expansion of a number, which is unique. Therefore, $x_i-y_i=0$ for all $i$, which means that $x_i=y_i$.

Answer 3

Let $(x_0,...,x_{n-1})=x\ne y =(y_0,...,y_{n-1}).$ Note that $|x_i2^i-y_i2^i|\leq 2^i$ for each $i.$

Let $k=\max \{i:x_i\ne y_i\}.$ By def'n of $k$ we have $b(x)-b(y)=\sum_{i=0}^k (x_i2^i-y_i2^i)$. Now we have $$|b(x)-b(y)|=|(x_k2^k-y_k2^k)+\sum_{0\leq i<k}(x_i2^i-y_i2^i)|\geq$$ $$\geq |x_k2^k-y_k2^k|-\sum_{0\leq i<k}|x^i2^i-y_i2^i|\geq$$ $$\geq 2^k-\sum_{0\leq i<k}2^i=2^k-(2^k-1)=1.$$

Note: In case $k=0$ we use the (usual) convention that the sum of any empty collection is $0,$ so $\sum_{0\leq i<0}(Anything)_i=0.$

This is not a contra-positive proof.

The sets $\{0,1\}^n$ and $\{z\in \Bbb Z: 0\leq z\leq 2^n-1\}$ each have exactly $2^n$ members. If $C,D$ are any finite sets with the same number of members, any injective $b:C\to D$ is a bijection.