[Math] Prove explicitly that if a function has a left inverse it is injective and if it has a right inverse it is surjective

elementary-set-theory

A function g : S → T is said to be a left inverse for the function f : T → S if g◦f equals the identity function on $T$. In this case, f is also a right inverse for g . Prove explicitly that

That t any a function has a left inverse it is injective and if it has a right inverse it is surjective, give an example of a function that has 2 distinct left inverses.

I'm not too sure if i understand the difference the difference of between a left and right inverse to begin with. I think it's left inverse if in f: S –> T and g: T –> S meaning in f is you plug in S to f(x) you get T and for g(x) plugging in T you get S. So g(x) is the inverse of f(x) and vice versa.

Left inverse f(g(x)) = S and right inverse when rather g(f(x)) = T. Definitions have $1_S$ and $1_T$ which confuses me.

To be injective i also know that for every value of the codomain T there must be a unique value of S the domain. So there cannot be more than one value of T that maps into a value of S.

To surjective and everyone value of T the codomain must map to a value the domain S. So for example e^x is not surjective for all real x because its range is y > 0 rather than having a range of all real x. However you could cut the parameters to something like x>0 and even say it's bijective where it is both surjective and injective.

Best Answer

Let $g : S \rightarrow T$ be the left inverse of $f$, it means $g \circ f = I_{T}$. If $f(x) = f(y)$, then $x=g(f(x))=g(f(y)) = y$, so $f$ is injective.

Let $h : S \rightarrow T$ be the right inverse of $f$, it means $f \circ h = I_{T}$. For any $y \in T$ we have $y = f(h(y))$. By arbitrariness of $y$, f is surjective.

Also worth adding that implications go both ways in both cases.

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.

Why abstractly do left and right inverses coincide when $f$ is bijective

The simple algebraic reason is that anything with a left inverse $L$ and a right inverse $R$ has $L=R.$

If left and right inverses are $f^L$ and $f^R$ then apply the associative rule to $f^L\circ f \circ f^R.$

A bijection is, intuitively, a pairing of the elements of $X$ with the elements $Y$ - every element of $Y$ is paired with exactly one $x\in X$ and visa versa.

Every $y\in Y$ is of the form $y=f(x)$ for exactly one $x.$

A left inverse $f^L$ must have $x=f^L\circ f(x)=f^L(y).$

The right inverse needs $f(x)=y=f\circ f^R(y)$ but $f(x)=f(z)$ means that $x=z$, so $x=f^R(y)$ and we get the same $f^R(y)=f^L(y)=x.$

Think of a bijection as a set $P\subseteq X\times Y$ of pairs where each $x\in X$ has exactly on $y\in Y$ such that $(x,y)\in P,$ and visa versa.

For $x\in X$, $f(x)$ is the uniqu element of $y\in Y$ is paired with $(x,y)\in P.$

And we get that $f^R(y)$ and $f^L(y)$ must both be the unique element $x\in X$ such that $(x,y)\in P.$