Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
show 6 more comments

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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
show 7 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.