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.

Alternative definitions 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}\)