# Proving $v(s,p)=2^{p-1}(2s-1)$ is a bijection of natural numbers and $f(s)=2s-1$ is a bijection between natural numbers and odd numbers.

How do I prove this function is bijective? $$v(s,p)=2^{p-1}(2s-1).$$ The domain is natural numbers and the codomain is also the natural numbers.

And this one: $$f(s)=2s-1.$$ The domain is the natural numbers, and the codomain is the odd numbers in the natural numbers.

With this one I would do this to show it's injective: \begin{align} v(s)&=v(s_1)\\ \implies 2s-1&=2s_1-1\\ \implies (2s_1)/2&=(2s_2)/2\\ \implies s=s_1 \end{align} So it's injective since if $$v(s)=v(s_1)$$ then $$s=s_1$$.

And to show it's surjective $$f(s)=y$$: \begin{align} y&=2s-1\\ \implies s&=(y+1)/2 \end{align} Then the function must be surjective since every $$y$$ is the same as the codomain for $$f$$.

Am I correct?

• It is impossible to know if your functions are bijective without knowing what their domains and codomains are. For example, your $f$ is a bijection $\mathbb{R} \to \mathbb{R}$ but is not a bijection $\mathbb{Z} \to \mathbb{Z}$ (or $\mathbb{N} \to \mathbb{N}$). – Clive Newstead Dec 14 '18 at 14:42

## 1 Answer

Yes, "bijective" means "both injective and surjective". "Injective" means "if f(x)= f(y) then x= y" and "surjective" means "for any y, there exist x such that f(x)= y". With f(x)= 2x- 1 then if f(x)= f(y), 2x- 1= 2y- 1. Adding 1 to both sides, 2x= 2y. Dividing by 2, x= y. To show that f is surjective, if y= 2x- 1, then 2x= y+ 1 and x= (y+ 1)/2. Since that last, (y+ 1)/2, exists for all y, the function is surjective.

For $$v(s, p)= 2^{p-1}(2s+ 1)$$, to show "injective" we have to show that if $$v(s_1,p_1)= v(s_2, p_2)$$ then $$s_1= s_2$$ and $$p_1= p_2$$. A crucial point is that $$2^{p-1}$$ is a power of 2 while 2s+1 is an odd number. Use "unique prime factorization".

• So the thing I did was correct, I suppose? What do you mean by using "unique prime factorization? – J. Ras Dec 14 '18 at 15:09
• And can I do it by arguing that every natural number can be written as a product of 2^k-1 and an odd number? – J. Ras Dec 14 '18 at 15:17