1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Instead of showing one is less then the other, how about showing that the difference of the ouputs is not $0$. Since the inputs are not same so at least one $x_i \neq y_i$, therefore...... $\endgroup$ – Anurag A Aug 11 '18 at 19:39
  • $\begingroup$ I'm not exactly sure what contrapositive means here. $\endgroup$ – copper.hat Aug 11 '18 at 19:40
  • $\begingroup$ @AnuragA, I wanted to do that but it seems weird to just state that. In any case, he wants us to show one is less than / greater than the other. $\endgroup$ – alwaysiamcaesar Aug 11 '18 at 19:43
  • $\begingroup$ @copper.hat I'm not sure either. I'm taking "Introduction to Upper Division Mathematics" and the professor seems to think we already know methods of proof. It's my first quarter... Either way, that's how I interpreted proof by contraposition from my cursory google search. $\endgroup$ – alwaysiamcaesar Aug 11 '18 at 19:45
  • $\begingroup$ @copper.hat I'm pretty sure he means contra-positive. I,e. proving $x\ne y\implies f(x)\ne f(y)$ by showing that $f(x)=f(y)\implies x=y$ $\endgroup$ – DanielWainfleet Aug 11 '18 at 21:36
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ We can suppose x < y without loss of generality? If we'd assumed the opposite it would just be a matter of proving b(x) > b(y)? Am I understanding this correctly? $\endgroup$ – alwaysiamcaesar Aug 11 '18 at 20:11
  • $\begingroup$ @V.Poghosyan: Yes, that would be slightly better (to just assume $x\neq y$), it would avoid an ambiguity with $<$. The proof would then just show that $b(x) \neq b(y)$ but that is all you need. My last sentence only depends on injectivity, not order. $\endgroup$ – copper.hat Aug 11 '18 at 20:14
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.