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!
Best Answer
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.