# Surjective and Injective function

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?

• You're on the correct track, but your reasoning is too vague to be a proof. You need to start with an assumption $f(m_1, n_1) = f(m_2, n_2)$ and develop your even-odd argument a bit more. – T. Bongers Oct 19 '18 at 17:26

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

• "Overkill?" Perhaps. T. Bongers answer is probably a lot easier, but your answer does capture the thought process that the OP was considering. (i.e. that the results have an "even part" and an "odd part" and ... so on.) – fleablood Oct 19 '18 at 18:27
• fleablood.Thanks for your comment. – Peter Szilas Oct 19 '18 at 19:24

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.

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