[Math] Checking if a function is injective and surjective

functions

I am doing past paper question and came across the following question:

For each of the following functions, decide whether it is injective
and surjective. Justify your answer.

$f: $ {$-1, 0, 1$} $\to$ {$-1, 0, 1$}

$f(x) = x^3$

$g: $ {$0, 1$} $\to$ {$0, 1, 2, 3, 4, 5$}

$g(x) = 3x + 1$

I have only recently started studying functions, so hoped to check my answers here, because I do not have access to a marking scheme.

My answers and reasoning:

$f$ is not injective, because $\pm x \neq \pm x$

$f$ is surjective because the co-domain {$-1, 0 ,1$} $=$ the range {$-1, 0 ,1$}

$g$ is injective, because $x = x$

$g$ is not surjective, because the co-domain {$0, 1, 2, 3, 4, 5$} $\neq$ the range {$1, 4$}

Please let me know if I have made any errors in my answers or reasoning. Thank you.

Best Answer

Another way to think about it.

If $f:X\to Y$ is a function then for every $y\in Y$ we have the set $f^{-1}(\{y\}):=\{x\in X\mid f(x)=y\}$.

(non-empty subsets of this form are the so-called fibers of $f$ and form a partition of $X$)

Based on that you can say:

$f$ is injective iff $f^{-1}(\{y\})$ has at most one element for every $y\in Y$.
$f$ is surjective iff $f^{-1}(\{y\})$ has at least one element for every $y\in Y$.

So checking a function on injectivity and/or surjectivity boils down to checking how the sets $f^{-1}(\{y\})$ behave.

Related Solutions

[Math] Injective and Surjective Functions

The idea of a mathematical proof is that without dependence of a specific input, if certain properties are true, then the conclusion is also true.

In this case, if the composition is injective then it has to be that the "outer" function is injective, and that if the functions are surjective then their composition is as such.

Showing a specific case is a valid method for disproving a claim, as it shows that at a certain time the properties hold but the conclusion is false.

For example, consider $A=\{0\}$ and $B=\{1,2\}$ and $C=\{0\}$ and $f(0)=1$ and $g(1)=0, g(2)=0$.

The composition $g\circ f$ is a function from $A$ to $C$, since $A$ is a singleton every function is injective. However $g$ is clearly not injective.

This is a counterexample to the claim, thus disproving it.

The proof for the second one, if both functions are surjective then so is their composition, let us check this.

Let $A,B,C$ any sets, and $f,g$ functions as required. To show that $g\circ f$ is surjective we want to show that every element of $C$ is in the range of $g\circ f$. Assume $c\in C$ then there is some element $b\in B$ such that $g(b)=c$. Since $f$ is surjective we have some $a\in A$ such that $f(a)=b$. It follows that $g\circ f (a) = c$ and therefore the composition of surjective functions is surjective.

Now, consider this proof. There was nothing to limit ourself. I did not require anything from $A,B,C$ other than them being sets, and I did not require anything from $f,g$ other than them being functions from/onto the required set in the premise of the claim. Furthermore, I did not check the surjective-ness of the composition by choosing a certain element. I picked and arbitrary element, from a set which was also arbitrary. Using this sort of argument assures us that the property is not dependent on any of the characteristics of the set (for example, some things are only true on finite, or infinite, or other certain sets). This allows us to have a very general theorem. Whenever we have three sets, and two functions which are surjective between them, then the composition is also surjective!

[Math] the practical benefit of a function being injective? surjective

Ed and Aaron, thank you very much for explaining the practical benefits of injectivity and surjectivity.

I have taken what I learned from you and cast it into my own thoughts and experiences. Please let me know of any errors.

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.