Surjective and Injective function

Question

Let $N=\{1,2,3...\}$ be the set of natural numbers and $F:N \times N \rightarrow N$ be such that $f(m,n)=(2m-1)*2^n.$

(A)F is Injective.

(B)F is Surjective.

(C)F is Bijective.

(D)None of the above.

I can see that F can never be surjective because 1 does not have a pre-image.

And it seems injective to me because $2m-1$ term would always be odd, $2^n$ term would always be even, and hence the product will always be Even, and for different values of m and n, we would get a different even number.

Is my Reasoning correct?

Answer 1

Overkill?

A) $f$ is injective.

Let $f(m,n)=f(k,l)$, i.e.

$i:=(2m-1)2^n= (2k-1)2^l.$

The positive integer $i$ has a - Fundamental Theorem of Arithmetic - unique prime factorization.

Since $(2m-1)$, $(2k-1)$ are odd,

we have $n=l$.

Then

$(2m-1)2^n= (2k-1)2^l$ implies

$2m-1=2k-1$, or $m=k.$

Combining

$f(m,n)=f(k,l)$ implies $m=k$, and $n=l.$

https://en.m.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

Answer 2

To expand my comment, you need to make the reasoning a lot more precise. Start with an assumption that there are natural numbers $m_1, m_2, n_1, n_2$ for which

$$f(m_1, n_1) = f(m_2, n_2).$$

Then you have

$$(2m_1 - 1)2^{n_1} = (2m_2 - 1) 2^{n_2}.$$

Now we can assume without loss of generality that $n_1 \le n_2$, so that

$$2m_1 - 1 = (2m_2 - 1)2^{n_2 - n_1}.$$

Now the left side is odd, so the right side is odd too; thus, $n_2 - n_1 = 0$ (why?). But then we get $2m_1 - 1 = 2m_2 - 1$, hence $m_1 = m_2$. This completes the proof.

Answer 3

I can see that F can never be surjective because 1 does not have a pre-image.

Let's prove that.

If $f(m,n) = (2m -1)*2^n = 1$ then as $2m-1$ and $2^n$ are integer factors of $1$ and the only integer factors of $1$ are $\pm 1$ so $2^n = \pm 1$ and that is only possible if $n = 0$ which is not possible as $0 \not \in \mathbb N$.

So it is not surjective.

(In fact for any odd number $2k - 1$ then $f(m,n) = (2m-1)*2^n = 2k-1$ would be impossible. $f(m,n)$ will always be even.)

And it seems injective to me because 2m−1 term would always be odd, 2n term would always be even, and hence the product will always be Even,

Which shows it can not be surjective

and for different values of m and n, we would get a different even number.

That's a bit of a leap. How do you know they will be different?

Let's prove it.

$f(m,n) = (2m-1)*2^n$ will have a unique prime factorization. As $2m-1$ is odd the power of $2$ of any value of $f(m,n)= (2m-1) 2^n$ will be $n$.

So if $n_1 \ne n_2$ then $f(a,n_2) = (2a - 1)2^{n_2} \ne (2b- 1)2^{n_1} = f(b,n_2)$ for any possible $a,b$. (Because the power of $2$ in the prime factorizations of those two numbers are different.)

And if $m_1 \ne m_2$ then $2m_1 - 1 \ne 2m_2 - 1$ and the prime factorizations of $(2m_1 - 1)*2^a \ne (2m_2 - 1)*2^b$ for any possible $a,b$ must be different for the different odd factors.

So if $(m_1, n_1) \ne (m_2 n_2)$ then either $n_1 \ne n_2$ or $m_1 \ne m_2$ (or both). In either case then $(2m_1-1)2^{n_1} \ne (2m_2-1)2^{n_2}$.

So $f$ is injective.

A) is true, B) is false, C) is false (as bijective implies surjective) and D) is false (it is one of the above).