show that the function f is bijection

[zodiacbrave]

a function f, that maps from the Cartesian Product of the positive integers to the positive integers. where
f(x,y) = 2^(x - 1) * (2y - 1).


I have to show that this function is both one-to-one and onto. I started trying to prove that it is onto, showing that there exists an n such that f(n,0) = n but I am not sure where to go from here.


Thank you

 

[daon2]

a function f, that maps from the Cartesian Product of the positive integers to the positive integers. where
f(x,y) = 2^(x - 1) * (2y - 1).


I have to show that this function is both one-to-one and onto. I started trying to prove that it is onto, showing that there exists an n such that f(n,0) = n but I am not sure where to go from here.


Thank you

Do you know what onto means? Plugging in (n,0) gives you a negative power of 2 which shouldn't be in your range at all, right? In fact you are claiming this is a bijection from set-pair of positive integers to the positive integers. so why are you plugging in 0 at all? Take a positive integer n in Z. You need to show it is of the form 2^(x-1)*(2y-1) for some x and y in Z. That is what this function being onto means.

 

[SlipEternal]

To restate using some notation: Define \(\displaystyle f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}\) by \(\displaystyle f(i,j) = 2^{i-1}(2j-1)\).

To prove that it is one-to-one, assume not. Then there must exist \(\displaystyle i,j,i',j'\) such that \(\displaystyle f(i,j)=f(i',j')=2^{i-1}(2j-1)=2^{i'-1}(2j'-1)\). Take log base 2 of both sides: \(\displaystyle i-1+\log_2{(2j-1)}=i'-1+\log_2{(2j'-1)}\), and thus \(\displaystyle i-i'=\log_2{(2j-1)}-\log_2{(2j'-1)}=\log_2{\frac{2j-1}{2j'-1}}\). \(\displaystyle (i-i')\in\mathbb{Z}\). But, neither \(\displaystyle 2j-1\) nor \(\displaystyle 2j'-1\) can be divisible by 2. The only integer power of 2 that is not divisible by 2 is \(\displaystyle 2^0\). Therefore, \(\displaystyle \log_2{\frac{2j-1}{2j'-1}}=0=i-i'\Rightarrow i=i'\). It is not hard to show from there that \(\displaystyle j=j'\).

To prove onto, let \(\displaystyle n\in\mathbb{N}\). Let \(\displaystyle i-1\) be the highest power of 2 that divides \(\displaystyle n\). Thus, there must exist \(\displaystyle k\in\mathbb{N}\) such that \(\displaystyle 2^{i-1}*k=n\) and 2 cannot divide \(\displaystyle k\) (otherwise \(\displaystyle i-1\) would not be the highest power of 2 that divides \(\displaystyle n\)). Since 2 does not divide \(\displaystyle k\), 2 must divide \(\displaystyle k+1\). Thus, there must exist \(\displaystyle j\in\mathbb{N}\) such that \(\displaystyle 2j=k+1\). Now, \(\displaystyle f(i,j)=n\) as desired.