How can I prove an injection between set of natural numbers $\mathbb{N}$ and the set of binary numbers $B=\{2^{i_{1}},2^{i_{2}},...,2^{i_{k}}\}$ such that :

$$B\xrightarrow{\xi_{s} : \sum_{s=1}^{k}2^{i_{s}}}\mathbb{N}$$

That is for some $n\in\mathbb{N}$ there exists a unique binary number representation for $n$ such that : $$n=2^{i_{1}}+2^{i_{2}}+...+2^{i_{k}}$$

Side Note: This is part of my analysis assignment which is asking me to show that the binary representation of a natural number is unique I wish that no one writes me a proof but rather give me a hint on how to think/approach this proof based on my choice of proving an injectivity of the sets above.

  • 1
    $\begingroup$ As requested, a hint: if two subsets are the binary integers are different, there must be a biggest binary integer that they disagree at. What does this say about the size of the sum? This is using the following characterization of injectivity: a function $f$ is injective iff $x \neq y \implies f(x) \neq f(y)$. $\endgroup$ – Duncan Ramage Sep 23 at 20:36
  • $\begingroup$ I suggest induction. Let $n$ be the least natural number which can be written in two distinct ways as the sum of distinct powers of $2$. Derive a contradiction. $\endgroup$ – lulu Sep 23 at 20:37
  • $\begingroup$ I believe I have understood your point when you said there must be a biggest binary integer they disagree at. Then I must consider the two possible cases concerning the sizes of these sums and derive a contradiction right? $\endgroup$ – WiWo Sep 23 at 20:44

Hint: Consider remainders modulo 2 and repeat to show injectivity.

Here is a simple, spoilered proof of injectivity.

Suppose two binary expansions of length at least $n$ have equal value. That is, for some digits of the expansion $0 \leq a_i, b_i \leq 1$: $$a_n\cdot2^n + \cdots + a_1\cdot 2^1 + a_0 = b_n\cdot2^n + \cdots + b_1\cdot 2^1 + b_0.$$ We endeavour to prove that $a_i = b_i$ for appropriate $i$. Take the remainders modulo 2, which leads us to: $$ a_n\cdot0 + \cdots + a_1\cdot 0 + a_0 = b_n\cdot0 + \cdots + b_1\cdot 0 + b_0; \\ a_0 = b_0.$$ So $a_0 = b_0$, and therefore: $$a_n\cdot2^{n-1} + \cdots + a_1\cdot 2^0 = b_n\cdot2^{n-1} + \cdots + b_1\cdot 2^0.$$ This itself is an equality of binary expansions, so we may proceed by induction to prove this for any $n$ and show the desired result. I will leave the precise details of this induction to you. The end result is that $a_i = b_i$ for $0 \leq i \leq n$, which is to say that the binary expansion is unique.

Here is a proof of injectivity that is more in the analytical spirit, obtained by considering the greatest power that to equal expansions do not share.

Suppose that $A = \{a_1, a_2, \cdots, a_n\}$ and $B = \{b_1, b_2, \cdots, b_n\}$ have the same binary value, that is $\sum{2^{a_i}} = \sum{2^{b_i}}$.
Suppose for contradiction that these sets are not equal. Then certainly there is a largest exponent that occurs in one that does not occur in the other. Without loss of generality, suppose this exponent is $a_x \in A$. Then certainly: $$\sum_{i}{2^{a_i}} = \sum_{a_i < a_x}{2^{a_i}} + 2^{a_x} + \sum_{a_i>a_x}{2^{a_i}}, \text{and} \\ \sum_{i}{2^{b_i}} = \sum_{b_i<a_x}{2^{b_i}} + 0 + \sum_{b_i>a_x}{2^{b_i}}.$$ Recall that $a_x$ was the largest exponent not shared by both, so since they are equal we may cancel the larger sum, obtaining: $$ 2^{a_x} = \sum_{b_i < a_x}{2^{b_i}} - \sum_{a_i < a_x}{2^{a_i}}.$$ The right hand side of this equality is at most the sum of all powers of two less than $a_x$, so: $$ 2^{a_x} \leq \sum_{i=0}^{a_x-1}{2^i} = 2^{a_x} - 1.$$ And this is a contradiction. Hence the sets are equal.

| cite | improve this answer | |

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.