Properties of functions

Naive set theory: Functions

Properties of functions

Terminology

Injective, surjective, bijective

A function $f$ from $X$ to $Y$ is called:

injective, an injection, one-to-one, if every $y\in\mathrm{im}(f)$ has exactly one original: $\text{If }f(x_1)=f(x_2)\text{, then }x_1=x_2\text.$ Injectivity of a function can also be defined as follows: $\text{If }x_1\neq x_2\text{, then }f(x_1)\neq f(x_2)\text.$
surjective, a surjection, if the range of $f$ is the entire set $Y$ : $\mathrm{im}(f)=Y\text.$
bijective, a bijection, if the function $f$ is both injective and surjective.

Examples

We consider the following functions:

$f:\;\{a,\alpha\}\rightarrow \{A,B\},\\f(a)=A, f(\alpha)=A$
$g:\;\{a,\alpha, b\}\rightarrow \{A,B\},\\g(a)=A, g(\alpha)=A,g(b)=B$
$h:\;\{a,b\}\rightarrow \{A,B,C\},\\h(a)=A, h(b)=B$
Then:
$f$ is not injective and not surjective;
$g$ is not injective, but is surjective;
$h$ is injective, but not surjective.
None of the functions $f$ , $g$ , and $h$ is bijective.

$\varphi:\;\mathbb{Z}\rightarrow \mathbb{N}, \varphi(n)=\begin{cases} 2n &\text{if }n\ge 0\\ -2n-1 &\text{if }n< 0\end{cases}$
is a bijection.

We can also define injectivity, surjectivity, and bijectivity of the function $f$ from $X$ to $Y$ ook as follwos:

If there is a function $g$ from $Y$ to $X$ such that $g\circ f=\mathrm{id}_X$ , then $f$ is injective;
If there is a function $h$ from $Y$ to $X$ such that \ $f\circ h=\mathrm{id}_Y$ , then $f$ is surjective;
If both conditions hold, then $f$ is bijective and $g=h=f^{-1}$ .

Let $f:\;X\rightarrow Y$ be a function from $X$ to $Y$ and $g:\;Y\rightarrow Z$ a function from $Y$ to $Z$ . Then the composition $g\circ f$ is a function from $X$ to $Z$ and:

if $f$ and $g$ are both injective, then $g\circ f$ is also injective;
if $f$ and $g$ are both surjective, then $g\circ f$ is also surjective;

Suppose that $f$ and $g$ are both injective. Let $x_1$ and $x_2$ be arbitrary elements of $X$ and suppose that $(g\circ f)(x_1)= (g\circ f)(x_2)$ . So: $g\bigl(f(x_1)\bigr)=g\bigl(f(x_1)\bigr)$ . Because $g$ is injective it follows that $f(x_1)=f(x_2)$ , and similarly because $f$ is injective we can then concloude that $x_1=x_2$ . Thus, $g\circ f$ is injective.

Suppose that $f$ and $g$ are both surjective. Let $z$ be an arbitrary element of $Z$ . Because $g$ is surjective, there is some $y\in Y$ such that $g(y)=z$ , and similarly because $f$ is injective, there is some $x\in X$ such that $f(x)=y$ . Then: $(g\circ f)(x)=g\bigl(f(x)\bigr)=g(y)=z$ . Thus, $g\circ f$ is surjective.

Let $f:\;X\rightarrow U$ be a function from $X$ to $U$ and $g:\;Y\rightarrow V$ be a functon from $Y$ to $W$ . Then, the function $(f\times g):\;X\times Y\rightarrow U\times V$ can be defined as $(f\times g)(x,y)=(f(x),g(y))$ for every $x,y)\in X\times Y$ and the following statements are true:

If $f$ and $g$ are both injective, then $f\times g$ is also injective;
If $f$ and $g$ are both surjective, then $f\times g$ is also surjective;

Suppose that $f$ and $g$ are both injective. Let $(x_1,y_1)$ and $(x_2, y_2)$ in $X\times Y$ are elements such that $(f\times g)(x_1,y_1)= (f\times g)(x_2,y_2)$ . Thus, $\bigl(f(x_1),g(y_1)\bigr)=g\bigl(f(x_2), g(y_2)\bigr)$ . So, $f(x_1)=f(x_2)$ and $g(y_1)=f(y_2)$ . Because $f$ and $g$ are both injective: $x_1=x_2$ and $y_1=y_2$ , which means that $x_1,y_1)=(x_2,y_2)$ . In other words, $f\times g$ is injective.

Suppose that $f$ and $g$ are both injective. Let $(u,v)$ in $Z$ be an arbitrary element. Because $f$ is surjective, there is an $x\in X$ such that $f(x)=u$ . Because $g$ is surjective, there is an $y\in Y$ such that $g(y)=v$ . Then, $(f\times g)(x,y)=g\bigl(f(x),g(y)\bigr)=(u,v)$ . So, $f\times g$ is surjective.

Inverse function

Inverse function

If $f:\;X\rightarrow Y$ is a bijection, then the inverse function of $f$ is the bijective function $f^{-1}:\;Y\rightarrow X$ with $G_{f^{-1}}=\bigl\{(y,x)\in Y\times X\mid (x,y)\in G_f\bigr\}$ .

For a bijective function $f$ from $X$ to $Y$ and the inverse function $f^{-1}$ from $Y$ to $X$ :

$f^{-1}\circ f = \mathrm{id}_X$ ;
$f\circ f^{-1} = \mathrm{id}_Y$ .

Examples

The inverse function of $f:\;\mathbb{Z}\rightarrow \mathbb{Z},\quad f(n)=n+1$ is $f^{-1}:\;\mathbb{Z}\rightarrow \mathbb{Z},\quad f^{-1}(n)=n-1$ .

The inverse function of $g:\;[-1,1]\rightarrow [-1,1],\quad g(x)=x^3$ is $g^{-1}:\;[-1,1]\rightarrow [-1,1],\quad g^{-1}(y)=\sqrt[3]{y}$ .

The function rule of the inverse function of
$\varphi:\;\mathbb{Z}\rightarrow \mathbb{N},\quad \varphi(n)=\begin{cases} 2n &\text{if }n\ge 0\\ -2n-1 &\text{if }n< 0\end{cases}$
is
$\varphi^{-1}(m)=\begin{cases} \tfrac{1}{2}m &\text{for even }m\\ -\tfrac{1}{2}(m+1) &\text{for odd }m\end{cases}$