[Math] Determine injective or surjective of these functions

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?

Best Answer

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

Motivation

When I go hiking, I want to be able to retrace my steps and get back to my starting point.

When I go to a store, I want to be able to return home.

When I swim out from the shore, I want to be able to get back to the shore.

Going somewhere and then coming back to where one started is important in life.

And it is important in mathematics.

And it is important in functional programming.

Domain, Codomain, and Inverse

If a function maps a set of elements (the domain) to a set of values (the codomain) then it is often useful to have another function that can take the elements in the codomain and send them back to their original domain values. The latter is called the inverse function.

In order for a function to have an inverse function, it must possess two important properties, which I explain now.

The Injective Property

Let the domain be the set of days of the week. In Haskell one can create the set using a data type definition such as this:

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday

Let the codomain be the set of breakfasts. One can create this set using a data type definition such as this:

data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage

Now I create a function that maps each element of the domain to a value in the codomain.

Here is one such function. The first line is the function signature and the following lines is the function definition:

f  ::  Day  ->  Breakfast
f  Monday       =  Eggs
f  Tuesday      =  Cereal
f  Wednesday    =  Toast
f  Thursday     =  Oatmeal
f  Friday       =  Pastry
f  Saturday     =  Ham
f  Sunday       =  Grits

An important thing to observe about the function is that no two elements in the domain map to the same codomain value. This function is called an injective function.

[Definition] An injective function is one such that no two elements in the domain map to the same value in the codomain.

Contrast with the following function, where two elements from the domain -- Monday and Tuesday -- both map to the same codomain value -- Eggs.

g  ::  Day  ->  Breakfast
g  Monday       =  Eggs
g  Tuesday      =  Eggs
g  Wednesday    =  Toast
g  Thursday     =  Oatmeal
g  Friday       =  Pastry
g  Saturday     =  Ham
g Sunday        =  Grits

The function is not injective.

Can you see a problem with creating an inverse function for g :: Day -> Breakfast?

Specifically, what would an inverse function do with Eggs? Map it to Monday? Or map it to Tuesday? That is a problem.

[Important] If a function does not have the injective property then it cannot have an inverse function.

In other words, I can't find my way back home.

The Surjective Property

There is a second property that a function must possess in order for it to have an inverse function. I explain that next.

Did you notice in the codomain that there are 8 values:

data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage

So there are more values in the codomain than in the domain.

In function f :: Day -> Breakfast there is no domain element that mapped to the codomain value Sausage.

So what would an inverse function do with Sausage? Map it to Monday? Tuesday? What?

The function is not surjective.

[Definition] A surjective function is one such that for each element in the codomain there is at least one element in the domain that maps to it.

[Important] If a function does not have the surjective property, then it does not have an inverse function.

[Important] In order for a function to have an inverse function, it must be both injective and surjective.

Injective + Surjective = Bijective

One final piece of terminology: a function that is both injective and surjective is said to be bijective. So, in order for a function to have an inverse function, it must be bijective.

Recap

If you want to be able to come back home after your function has taken you somewhere, then design your function to possess the properties of injectivity and surjectivity.

[Math] Is this a function and injective/surjective question

For your first question, suppose that we had two elements of $A$ with the same coordinate: that is, we had $(a, b) \in A$ and $(a, c) \in A$. Then by definition of $A$, we have that $b^2 = a = c^2$, so $b^2 = c^2$. So does it follow that $b = c$? (It doesn't.)

For the second, you are correct that it is injective: For if $f(n) = f(m)$, then $$(2n, n + 3) = (2m, m + 3) \implies n + 3 = m + 3 \implies n = m$$ You're also correct that it's not onto, since it never hits $(1, 0)$. If it were onto, then you'd select an arbitrary element of $\Bbb{Z} \times \Bbb{Z}$ and find an element of $\Bbb{Z}$ mapping to it.