Functions – Injective if and Only if Surjective for Function f: X to X

functionsproof-verification

Suppose $X$ is a set and $f : X \to X$ is a function. If $X$ is a finite set, prove that $f$ is injective if and only if $f$ is surjective.
Show that when $X$ is an infinite set, the statement is not true in general.

For that, let $X = \mathbb{R}$ and find a function $f: \mathbb{R} \to \mathbb{R}$ which is injective but not surjective, and a function $g: \mathbb{R} \to \mathbb{R}$ which is surjective but not injective

My attempt at the first part

Suppose that the function is surjective but not injective. Let $a,b \in X$ such that $f(a)=f(b)$ but $a \not =b$. Now since this is a finite set mapping to itself then there are not enough elements in $X$ to map to $X$ since two elements were used to map to one element, thus the function can't be surjective. Therefore if the function is surjective it is also injective.

Now suppose that the function is injective but not surjective. Let $a \in X$ such that $f(b)\not =a$ for all $b \in X$. Since the function was assusmed to be injective each $a \in X$ must map to an element of $X$, thus must have two elemetns in $X$ mapping to the same element in $X$. Hence the function can't be injective, therefore if the function is injective it must be surjective.

Would an exponetial function work for injective but not surjective since can't map to negative numbers. And an example of a function that is surjective but not injective could be a log function since none of the negative numbers get mapped to anything?

Also I'm having trouble seeing why it has to be finite for the first part to work. I understand it has something to do with the pigeonhole principle but its not that clear to me.

Best Answer

Your proof is a little informal. Normally this wouldn't be a problem, but the issue is that the formal version of your "counting" argument is precisely what you wish to prove. The proof is not as simple as one would initially be lead to believe.

Let's prove the following statement. Your desired statement will follow.

Let $n\in\mathbb{N}$ and let $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$ be a function. Then $f$ is injective iff $f$ is surjective.

Proof:

We use induction. This clearly holds whenever $n=1$. Fix $n\in\mathbb{N}$ and suppose that every function from $\{1,\ldots,n\}$ into $\{1,\ldots,n\}$ is injective iff it is surjective. Let $f:\{1,\ldots,n+1\}\to\{1,\ldots,n+1\}$ be a function.

Suppose $f$ is injective. Denote $m:=f(n+1)$, and observe that since $f$ is injective, the function $g:\{1,\ldots,n\}\to\{1,\ldots,n+1\}\setminus\{m\}$ given by $g(k)=f(k)$ is well-defined and one-to-one. Define the injection $h:\{1,\ldots,n+1\}\setminus\{m\}\to\{1,\ldots,n\}$ by $$ h(k) = \begin{cases} k & \text{if}\ k<m, \\ k-1 & \text{if}\ k>m. \end{cases} $$ Due to the fact that the composition of injective functions is injective, we have that $h\circ g:\{1,\ldots,n\}\to\{1,\ldots,n\}$ is one-to-one. By the induction hypothesis, $h\circ g$ is onto and hence $h$ is onto. Therefore $g=h^{-1}\circ(h\circ g)$ is a composition of surjective functions, which means that it is surjective. Consequently $f$ is surjective.

(I'll leave the converse to you). $\square$

As far as the examples go, the exponential function works perfectly. However, a logarithmic function doesn't work because it isn't defined on all of $\mathbb{R}$ (and it is injective). To fix this, you could define $f:\mathbb{R}\to\mathbb{R}$ by $f(x)=\ln|x|$ if $x\ne0$ and $f(0)=0$.

Edit: Actually, one can prove that this statement never holds whenever $X$ is infinite. Suppose $X$ is an infinite set. Then there is a countably infinite subset $\{d_1,d_2,\ldots\}$ of $X$. (Caution: This uses the axiom of choice.) Define $f_i,f_s:X\to X$ by $$ f_i(x)=\begin{cases} d_{i+1} & \text{if}\ x=d_i\ \text{for some}\ i, \\ x & \text{otherwise}, \end{cases} \quad\text{and}\quad f_s(x)=\begin{cases} d_{i-1} & \text{if}\ x=d_i\ \text{for some}\ i>1, \\ x & \text{otherwise}. \end{cases} $$ Then $f_i$ is an injection and $f_s$ is a surjection, but neither is a bijection.

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] Surjective and injective functions

By definition, $f$ is a function from $A$ to $B$ if it assigns to each element $a \in A$ an element $f(a) \in B$. A partial function from $A$ to $B$ is exactly what you're after: it is a function assignment to some elements $a \in A$ values $f(a) \in B$. In a context when partial functions are discussed, if you want to emphasize that a function is not partial, then you call it a total function.