# Determine injective or surjective of these functions

I have the following functions:

\begin{align} f&: \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N} \\ g&: \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N} \end{align} defined by $f(x, y) = (x + y, x)$ and $g(x, y) = (x - y, y)$.

a) Calculate $g\circ f$ for the originals $(2, 2), (3, 5)$ and $(4, 1)$. \begin{align} f(2, 2) &= (2 + 2, 2) = (4, 2) \text{ and then } g(4, 2) = (4 - 2, 2) = (2, 2)\\ f(3, 5) &= (3 + 5, 3) = (8, 3) \text{ and then } g(8, 3) = (8 - 3, 3) = (5, 3)\\ f(4, 1) &= (4 + 1, 4) = (5, 4) \text{ and then } g(5, 4) = (5 - 4, 4) = (1, 4) \end{align}

b) Give a function description for the function $h: \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ with $h = g \circ f$ and show that it counts for all $x$, $y$ element of $\mathbb{N}$.

I have no idea how to tackle these two questions, don't even know where to begin.

c) Show that $f$ is injective, but not surjective.

To show that something is injective, I would need to find an element of the codomain that does not have an element in the domain. To find something that is surjective, I would need to find an element in the codomain that has more than one original.

Some sample input/output data:

input -> output
\begin{align} (0, 0) &\to (0, 0)\\ (0, 1) &\to (1, 0)\\ (0, 2) &\to (2, 0)\\ ...&\text{etc...}\\ (1, 0) &\to (1, 1)\\ (1, 1) &\to (2, 1)\\ ...&\text{etc...}\\ (2, 0) &\to (2, 2)\\ (2, 1) &\to (3, 2)\\ \end{align} ...etc...

Now, if I have e.g. the element $(0, 1)$ in the codomain, then there is no corresponding element in the domain. In element $(0, 1), x = 1$, but then $y$ has to be $-1$ to make the $0$, and since the domain is $\mathbb{N} \times \mathbb{N}$, this cannot be.

Another example, this time with element $(1, 0)$ in the codomain. This means that $x = 0$, and that $y = 1$. So the corresponding element in the domain should then be $(0, 1)$, but when this element is put into $f$, it goes to $(1, 1)$. In other words, $(1, 0)$ also does not have an original.

Is this evidence enough to say that this function is not surjective, or do I still need to prove it further?

d) We confine the function $f$ now to $$f: \mathbb{N} \times \mathbb{N} \to \{(n, m)\lvert n \geq m\}$$ still with $$f(x, y) = (x + y, x).$$ Show that the inverse of $f$ now does exist, and calculate this inverse.

My problem here is that there are elements that satisfy $n \geq m$, but these are not inverse. For example, if I put $(2, 1)$ into $f$, the answer is $(3, 2)$. This is not the inverse of $(2, 1)$ What is the thinking mistake I'm making here?

-
You seem to have mixed up your definitions of injective and surjective. You should go take a new look at them. –  Tobias Kildetoft Dec 11 '12 at 14:46
But $g$ as defined isn't a function $\mathbb N^2 \to \mathbb N^2$? –  martini Dec 11 '12 at 14:46
@Tobias - why? It seems legit :-) Injective is when an element in a domain has a maximum of one element in the codomain (that is none or one). Surjective is when an element from the domain maps to a minimum of one. –  Garth Marenghi Dec 11 '12 at 14:57
@martini I don't understand what you are trying to say. –  Garth Marenghi Dec 11 '12 at 14:57
That is not what you wrote, and this time you mixed up domain and codomain –  Tobias Kildetoft Dec 11 '12 at 14:58

For (b):

Note that $$h = g\circ f(x,y) = g(x+y, x) = (y, x).$$

For (c):

Surjective? No. For this to be true you would have to be able to find $x,y$ such that $f(x,y) = (x + y, x)= (1,2)$. That would mean $x = 2$ and $y = -1 \notin \mathbb{N}$. So that is not possible.

Injective? Say that $f(x,y) = f(x', y')$. We are assuming that two different inputs give the same output. For $f$ to be injective we need to prove that the inputs actually are the same. So we have $f(x,y) = f(x',y')$ and we need to prove that $x= x'$ adn $y = y'$. That $f(x,y) = f(x', y')$ means that $(x+y, x) = (x' + y', x')$. But if this is true then we certainly have that $x = x'$. And if $x=x'$ and $x + y = x' + y'$, then it follows that $y = y'$. Hence $f$ is injective. Note that $x'$ (the backtick or prime or what ever one calls it) is just another element. It isn't doesn't mean that it is necessarily related tot $x$. One could have chosen another variable name instead.

For (d):

Now say that $(n,m)\in \mathbb{N} \times \mathbb{N}$ with $n\geq m$. To prove that $f$ now is surjective, you want to find $x,y$ such that $$f(x,y) = (n,m)$$. But since $n\geq m$ you can write $n = m + a$ for $a\geq 0$. So you want $(x,y)$ such that $$x + y = n\quad \text{and}\quad x = m.$$ Well pick $x = m$. Then left is to find $y$ such that $x+y = n$, and with the choice of $x$, that means that we want $y$ so that $m + y = n$. That is $m + y = m + a$. This you have if you exactly if pick $y = a$. So $f$ is both injective and surjective here. It is clearly surjective and the injectivity follows from the fat that there was only one way to pick $x$ and $y$.

(I guess that there is the subtle assumption that $0\in \mathbb{N}$.)

-
Thank you very much for answering my questions :-) The other question I wanted to ask you, was what Say that (x+y,x)=(x′+y′,x′). Then x=x′ and y=y′, so f is injective means. I have this also in my textbook (f(x) = f(y)) as an explanation of why a something is surjective, but I can't wrap my head around it (also, what do the backticks (x') mean)? –  Garth Marenghi Dec 11 '12 at 15:51
@GarthMarenghi: First: the $x'$ just means an element in $\mathbb{N}$. One could also have chosen to use another letter instead of $x'$. Second: That $f$ is injective means that if $f(x,y) =$f(v,w)$, then$x = v\$. I can edit my answer to add a bit more detail. –  Thomas Dec 11 '12 at 16:24
Thanks once again for the additional info. I read your paragraph on injective at For c) a couple of times, but I still don't get it. I mean, if you assume that the inputs are the same (without actually inputting something), then won't they be? –  Garth Marenghi Dec 11 '12 at 18:02
@GarthMarenghi: Glad to help. Actually I assumed that the output was the same and proved that then the inputs are the same. This is exactly the definition of what it means to be injective. –  Thomas Dec 12 '12 at 2:41
@Tobias I'm sorry to bother you again on this, but there's one thing I thought I grasped, but I'm not sure I do. You say <br /><br /> But if this is true then we certainly have that x=x'. <br /><br /> Why is it that if we assume that when f(x,y)=f(x',y') means that (x+y,x)=(x'+y',x') is true, that x=x′? –  Garth Marenghi Dec 13 '12 at 14:14