2

Suppose we have a function defined as $f: \mathbb{N} \times \mathbb{N}, f(a,b) = 2a-b$

This was my solution: Suppose $z\in\mathbb{Z}$. Then for some $x,y\in\mathbb{N} \times \mathbb{N}, f(x,y) = z.$

$2x-y = z$
$\Rightarrow -y=z-2x$
$\Rightarrow y = -z + 2x$

$2x = z + y$
$\Rightarrow{x = \frac{z+y}{2}}$

This was supposed to show values for $x$ and $y$ exist in the domain for all outputs. But I was told the following:

  • Choice of $(a,b)$ may not be in $\mathbb{N} \times \mathbb{N}$

  • Correct set up but did not choose $a$, $b$ appropriately, based on each case for $y(y>0, y<0, y=0)$

Could someone help me understand what this means?

Shaun
  • 44,997
Marko
  • 41
  • Note that the [tag:proof-writing] tag has a different purpose. Also, please be aware that MathJax works in the title section. – Shaun Apr 14 '23 at 15:28
  • 3
    What is the codomain of your function $f$? This is important when checking if a function is surjective. Based on you supposing $z \in \mathbb{Z}$, presumably your function is $f \colon \mathbb{N} \times \mathbb{N} \to \mathbb{Z}$? This sort of thing is important to state when you are first starting to write proofs. – RobbieA Apr 14 '23 at 15:38
  • I would add a further criticism of this solution: If I tell you $z=1$ for instance, your solution does not tell me what $x$ and $y$ should be. The "solution" $y=-z+2x$ does not determine $y$ until you determine $x$ first. Then $x=\frac{z+y}{2}$ does not determine $x$ until you first determine $y$. So you really have not exhibited what $(x,y)\in\Bbb N\times \Bbb N$ maps to $z$. – Addem Apr 14 '23 at 15:46
  • To add to what @Addem says: you have essentially just restated the question and not proven anything at all. Edward's solution is a good one. – RobbieA Apr 14 '23 at 15:49

2 Answers2

2

Your function could be defined as $f:\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ or as mapping to $\mathbb{Z}$, I am not sure which one is intended.

Mapping to Natural Numbers

If you assume your codomain in $\mathbb{N}$, you must show that every natural number $n \in \mathbb{N}$ could be represented as an image of $f$. In other words, that there exist some $a,b \in \mathbb{N}$ such that $f(a,b) = n$.

It remains to cleverly pick such $a,b$. You have $$ n = f(a,b) = 2a-b. $$ You can pick whatever $a,b$ you like (as long as they are natural numbers) to make the RHS equal the LHS. One simple choice is $a = n = b$, then you have $$ f(a,b) = f(n,n) = 2n - n = n, $$ as desired.

Mapping to the Integers

If your codomain is $\mathbb{Z}$, you have to be able to represent all integers this way, not just all natural numbers. Could you come up with a way how to represent any integer with 2 natural numbers as the image of $f$?

gt6989b
  • 54,422
  • f maps into the natural numbers? with domain N x N ? i.e. $f:\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ – 311411 Apr 14 '23 at 15:56
2

In order to prove surjectivity, one needs to know what you are mapping onto. Assuming that one is mapping onto $\mathbb{Z}$, let us take $z \in \mathbb{Z}$ and then one can prove surjectivity by breaking into four cases:

  1. $z < 0$: Let $x = 0$ and $y = z$. If you do not want to include 0 in $\mathbb{N}$, then we can take $x = 1$ and $y = z + 2$.
  2. $z=0$: Let $x = y = 0$ or $x = 1$ and $y =2$.
  3. $z > 0$ and even: Let $x = z/2.$
  4. $z > 0$ and odd: Let $y = 1$ and $x = (z + 1)/2.$
311411
  • 3,537
  • 9
  • 19
  • 36
Edward_Plumb
  • 66