Understanding Series: Functions
Or when you draw potatoes to understand the maths behind ML.

# Functions

You might remember functions from your high school courses. What you saw at this time was actually a very very tiny fraction of the actual world of functions. Indeed, when we say functions, the first thing that comes to mind is the $f(x)=\ldots$ notation, where $x$ (the argument) and $f(x)$ (the value) are both real numbers. Therefore, in high school, a function was a mathematical relation between a real number ($x$) and another real number ($f(x)$), hence the notation $f:\mathbb{R}\rightarrow\mathbb{R}$.

Example : $f(x)=x^2$. For $x=0.5$, we have $f(x)=0.25$.

Here, we are going to expand this paradigm. That is, we are not going to make the assumption that $x$ and $f(x)$ are real numbers. From now on, $x$ and $f(x)$ can be real numbers, vectors, potatoes, soccer balls, whatever. They will just be elements from sets.

Don't forget that you can check all the other Understanding Series on my Github repo.

## 1. Function

A function from one set $E$ to another set $F$ is a mathematical relation from $E$ to $F$ such that each argument $x$ in $E$ has an image $f(x)$ in $F$.

When dealing with functions and sets, it is useful to make potato diagrams (that's a word I just invented) like below:

Remarks:

• All arguments in $E$ must have a unique image in $F$. If an argument in $E$ doesn't have an image, or if it has two or more images, then $f$ is not a function.
• Multiple arguments in $E$ can have the same image in $F$. This is the case in the potato diagram above.
• Multiple images in $F$ can have no corresponding argument. In other words, some images in $F$ can be alone in their potato, without any arrow linking them to any argument in $E$. This is also the case in the potato diagram above.
• The set that contains all existing functions from a set $E$ to another set $F$ is written as $\mathcal{F}(E,F)$. For instance, the set that contains all possible real-valued functions, as seen in high school, is written as $\mathcal{F}(\mathbb{R},\mathbb{R})$.

## 2. Injection

A function $f$ from $E$ to $F$ is an injection if and only if two distinct arguments in $E$ have two distinct images in $F$.

Mathematically: $\forall (x,x')\in E^2, x\neq x' \Rightarrow f(x)\neq f(x')$.

The above mathematical sentence reads "for all $x$ and $x'$ in set $E$, if $x$ and $x'$ are distinct then their images are also distinct". Therefore, the left-hand side of the arrow is an hypothesis ("if $x$ and $x'$ are distinct") and the right-hand side is a consequence of this hypothesis ("then their images are also distinct").

This is the property of an injection. For instance, in the potato diagram above, $f$ is not an injection because there are two distinct arguments in $E$ that point towards the same image in $F$.

On the potato diagram below, however, $f$ is an injection: for every distinct pair of arguments, we have a distinct pair of images.

Note that it's OK to still have images in $F$ that have no arguments in $E$.

How to show that a function is an injection?

Instead of using the definition above, we are going to use its contraposition. The contraposition of $A\Rightarrow B$ is $\bar{B}\Rightarrow\bar{A}$, where $\bar{A}$ and $\bar{B}$ are the negations of $A$ and $B$, respectively.

For example, the contraposition of "I live in Paris $\Rightarrow$ I live in France" is "I don't live in France $\Rightarrow$ I don't live in Paris".

Therefore the contraposition of the definition above is $\forall (x,x')\in E^2, f(x)= f(x') \Rightarrow x=x'$. It reads "if two images are equal, then their corresponding arguments are necessarily equal".

So in order to show whether $f$ is an injection, we first make the hypothesis that for all $(x,x')\in E^2, f(x)=f(x')$ and we show that it leads to $x=x'$.

Example : Let's take the function $f(x)=2x+3$, with $x\in\mathbb{R}$. Is it an injection?

As mentioned above, we start with the hypothesis that $\forall (x,x')\in\mathbb{R}^2, f(x)=f(x')$ and we show whether it leads to $x=x'$:

$$\forall(x,x')\in\mathbb{R}^2, f(x)=f(x') \Rightarrow 2x+3=2x'+3 \Rightarrow 2x=2x' \Rightarrow x=x'$$

Therefore, $f$ is an injection.

Your turn: Let $f$ be a function such that $f:\mathbb{R}\backslash\{1\}\rightarrow \mathbb{R}, x\mapsto\dfrac{2x+3}{x-1}$.

$\mathbb{R}\backslash\{1\}$ means that we remove the number $1$ from $\mathbb{R}$ because $f$ is not defined for this argument (don't forget that kittens die in a horrible death when you divide by zero).

Is $f$ an injection?

Answer: $\forall(x,x')\in\left(\mathbb{R}\backslash\{1\}\right)^2$:

\begin{eqnarray} f(x) & = & f(x')\nonumber \\ \dfrac{2x+3}{x-1} & = & \dfrac{2x'+3}{x'-1} \nonumber \\ (2x+3)(x'-1) & = & (2x'+3)(x-1) \nonumber \\ 2xx'-2x+3x'-3 & = & 2xx'-2x'+3x-3 \nonumber \\ 3x'+2x' & = & 3x+2x \nonumber \\ 5x' & = & 5x \nonumber \\ x' & = & x \nonumber \end{eqnarray}

Therefore, $f$ is an injection.

## 3. Surjection

A function $f$ from $E$ to $F$ is a surjection if and only if each image in $F$ has an argument in $E$.

Mathematically: $\forall y\in F, \exists x\in E, f(x)=y$.

The above mathematical sentence reads "for every image $y$ in $F$, there exits an argument $x$ in $E$ so that, when we apply $f$ to $x$, we land on $y$". In other words, if $f$ is a surjection, there can be no element in $F$ that is alone in its potato, without any arrow pointing to it. On the two potato diagrams above, $f$ is not a surjection because there are images in $F$ that have no arrows pointing to them.

On the potato diagram below, however, $f$ is a surjection (but it's not an injection).

How to show that a function is a surjection?

The principle is that we start from any image $y=f(x)$ in $F$ and we show that it's possible to "invert" the equation and write it in the form of $x=g(something)$. If we manage to do that, it means that for all image $y$ in $F$, there exists an argument $x$ that, when we apply a certain function $g$, yields $y$. This is the definition of a surjection.

Example : Let's take the function $f(x)=2x+3$, with $x\in\mathbb{R}$. Is it a surjection?

As mentioned above, we start from $y=f(x)$ and we try to invert the equation. $\forall y\in\mathbb{R}$ :

$$y=f(x) \Leftrightarrow y=2x+3 \Leftrightarrow 2x=y-3 \Leftrightarrow x=\dfrac{y-3}{2}$$

Therefore, $f$ is a surjection.

Your turn: Let $f$ be a function such that $f:\mathbb{R}\backslash\{1\}\rightarrow \mathbb{R}, x\mapsto\dfrac{2x+3}{x-1}$. Is $f$ a surjection?

Answer: $\forall y\in F:$

\begin{eqnarray} y & = & f(x) \nonumber \\ y & = & \dfrac{2x+3}{x-1} \nonumber \\ y(x-1) & = & 2x+3 \nonumber \\ yx-y & = & 2x+3 \nonumber \\ yx-2x & = & 3+y \nonumber \\ x(y-2) & = & 3+y \nonumber \end{eqnarray}

And now we need to stop because we cannot divide by $y-2$ unless $y\neq 2$ (mind the kittens!). Therefore, we cannot isolate $x$ unless $y\neq 2$, which is not consistent with the fact that it needs to work for every $y\in F$.

Therefore, $f$ is not a surjection.

## 4. Bijection

A function $f$ from $E$ to $F$ is a bijection if and only if it is both an injection and a surjection, that is, if and only if each image in $F$ has a unique argument in $E$.

Mathematically: $\forall y\in F, \exists! x\in E, f(x)=y$.

The above mathematical sentence reads "for every image $y$ in $F$, there exists a unique argument $x$ in $E$ so that, when we apply $f$ to $x$, we land on $y$".

On the potato diagram above, $f$ is a bijection. There is a one-to-one correspondance between arguments in $E$ and images in $F$.

How to show that a function is a bijection?

Usually, we show that it's an injection and a surjection.

## 5. Inverse bijection

Let $f$ be a bijection from $E$ to $F$. The function from $F$ to $E$ that maps every $y\in F$ to a unique argument $x\in E$ such that $y=f(x)$ is called the inverse bijection of $f$ and is written as $f^{-1}$.

Basically, if $f$ is a bijection from $E$ to $F$, then $f^{-1}$ is its sister bijection that goes the other way round. Let the potato diagram below speaks for itself:

So if we start from any argument $x\in E$, we can apply $f$, follow the arrow, and we land in $F$ on an image $y$ such that $y=f(x)$. Then, starting from this very same image, we can apply $f^{-1}$, follow the arrow in the inverse way, and we arrive on the initial argument $x\in E$ where we started from.

Mathematically: we start from $x$, we first apply $f$, which yields $f(x)$, then we apply $f^{-1}$ to $f(x)$, which yields $f^{-1}\left( f(x) \right)$, and all these operations lead us back to $x$, so that in the end we have:

$$f^{-1}\left( f(x) \right) = x$$

We can apply the same reasoning but instead of starting from $E$, we can start from any image $y\in F$, then apply $f^{-1}$ first, which yields $f^{-1}(y)$, and finally apply $f$ to $f^{-1}(y)$, yielding $f\left( f^{-1}(y) \right)$. These operations lead us back to our initial $y$, so that:

$$f\left( f^{-1}(y) \right) = y$$

In both cases above, what we did is start from an element in any of the two sets, apply a bunch of functions and ended up on the same element where we started from. It happens that there's a function that does exactly that. It's called the identity function, and it's written as ${\rm Id}_E$ or ${\rm Id}_F$ depending on which set we start from. The job of the identity function is very simple: it maps an element to itself. If we apply the identity function to a potato, it returns this very same potato. Mathematically:

$$\forall x\in E, {\rm Id}_E(x) = x \qquad \text{ and } \qquad \forall y\in F, {\rm Id}_F(y) = y$$

And remember, we also wrote above that:

$$\forall x\in E, f^{-1}\left( f(x) \right) = x \qquad \text{ and } \qquad \forall y\in F, f\left( f^{-1}(y) \right) = y$$

Mixing all of the above allows us to write that :

$$\forall x\in E, f^{-1}\left( f(x) \right) = {\rm Id}_E(x) \qquad \text{ and } \qquad \forall y\in F, f\left( f^{-1}(y) \right) = {\rm Id}_F(y)$$

Or, in a more compact way:

$$f^{-1}\circ f = {\rm Id}_E \qquad \text{ and } \qquad f\circ f^{-1} = {\rm Id}_F$$

where the $\circ$ sign is the composition operation: $(f\circ g)(x) = f(g(x))$.

So what this means is that when we apply a function followed by its inverse (or the other way round), it boils down to applying the identity function. The story ends where it began.

How to find the inverse bijection?

It's the same as when we want to show whether a function is a surjection: we start from any image $y=f(x)$ in $F$ and we show that it's possible to "invert" the equation and write it in the form of $x=g(something)$. If we manage to do that, then the function $g$ is the inverse bijection of $f$.

Remark : if $f$ is not a surjection, then we won't be able to invert the equation, hence no inverse bijection. This is consistent with the fact that for $f$ to have an inverse bijection, it has to first be a bijection itself (injection + surjection).

Your turn: What is the inverse bijection of $f:[-2 ; +\infty] \rightarrow \mathbb{R}, x\mapsto \sqrt{x+2}$.

Answer: $\forall y\in F:$

\begin{eqnarray*} y & = & f(x) \nonumber \\ y & = & \sqrt{x+2} \nonumber \\ y^2 & = & x+2 \nonumber \\ x & = & y^2-2 \nonumber \end{eqnarray*}

The inverse bijection of $f$ is $f^{-1}:\mathbb{R} \rightarrow [-2 ; +\infty], y \mapsto y^2-2$.