0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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}$). $\endgroup$ – Clive Newstead Dec 14 '18 at 14:42
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So the thing I did was correct, I suppose? What do you mean by using "unique prime factorization? $\endgroup$ – J. Ras Dec 14 '18 at 15:09
  • $\begingroup$ 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? $\endgroup$ – J. Ras Dec 14 '18 at 15:17

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.