function

Function

Let $A,B\ne \varnothing$
A function from $A$ to $B$ is the triple $(A,B,R_f)$, where $A$ is the domain (Definitionsmenge), $B$ is the codomain (Zielmenge), and $R_f$ is a relation also called the graph of the function with the following property:
$R_f\subseteq A\times B:\forall x\in A\exists !y\in B:x{R}_{f}y$ (each element of $A$ is related to exactly one element of $B$).
Notation:
Instead of $(A,B,R_f)$, we write $f:A\to B$.
Instead of $x{R}_{f}y$, we write $f(x)=y$ or $x\mapsto f(x)$

function graph

The graph of a function $f$ is the set of ordered pairs $(x,y)$, where $f(x)=y$: $R_f=\{x,f(x)\mid x\in A\}$

Input shift.

$f(x-a)$ shifts a function to the right by $a$, because in order to get the same output as $f(c)$ with $c=x-a⟹x=c+a$.

Injective (one-to-one) function

A function $f:A\to B$ is called injective if $\forall x_1,x_2\in A:f(x_1)=f(x_2)⟹x_1=x_2$
Or conversely: $\forall x_1,x_2\in A:x_1\ne x_2⟹f(x_1)\ne f(x_2)$

(an injective but not surjective function)

Surjective (onto) function

A function $f:A\to B$ is called surjective if $\forall y\in B\exists x\in A:f(x)=y$
In words: every element in the codomain is the image of at least one element in the domain.

Bijective function

A function $f:A\to B$ is called bijective if it is both injective and surjective.
A bijection basically means that there is a one-to-one correspondence between all elements of the domain and the codomain: For every unique element in $A$, there is a unique element in $B$.

EXAMPLE

$f_1:\mathbb{R}\to {\mathbb{R}}_0^{+}:x\mapsto x^2$ is not injective, because $f_1(-1)=f_1(1)$ and it is not surjective, because $f_1(x)\ge 0\forall x\in \mathbb{R}$ (negative real numbers are not in the codomain).
$f_2:{\mathbb{R}}_0^{+}\to \mathbb{R},x\mapsto x^2$ is injective, but not surjective because we canot reach negative numbers.
$f_3:\mathbb{R}\to {\mathbb{R}}_0^{+},x\mapsto x^2$ is not injective but surjective ($x^2=z$ has a solution for all $z\in {\mathbb{R}}_0^{+}$).
$f_4:{\mathbb{R}}_0^{+}\to {\mathbb{R}}_0^{+},x\mapsto x^2$ is bijective.

If a function from two finite sets of equal length is injective, it is also surjective (→ bijective).

Let $A,B$ be finite sets, $|A|=|B|=n$, $A=\{a_1,\dots ,a_n\}$.
$f:A\to B,f(a_i)=b_i⟹f\text{ injective}⟺f\text{ surjective}$

Proof:
Injective $⟹$ surjective:
$b_1,\dots b_n$ are pairwise different: $b_i=b_j⟹a_i=a_j⟹i=j$ (injective)
$⟹\underset{=f(A)=\{f(x)\mid x\in A\}}{\underbrace{\{b_1,\dots ,b_n\}}}=B$
(“slight abuse of notation” … in logic, they use $f[B]$ for the image of $B$ under $f$)]
$f(A)=B$ → surjective
Surjective $⟹$ injective:
Assumption $f(A)=B$
Assume it’s not injective $\exists k\ne l:a_k\ne a_l\wedge \underset{f(a_k)}{\underbrace{b_k}}=\underset{f(a_l)}{\underbrace{b_k}}$
$⟹|\underset{f(A)}{\underbrace{\{f(a_1),f(a_2),\dots f(a_n)\}}}|<n⟹f(A)\ne B⟹$ not surjective.
Strictly formally, we would need to first define the cardinality with bijective functions to get to the definition of equality for bijective images…
But uhm this thing makes quite obviously sense if you just look at the definition.

The theorem above can be extended to inifinite sets: Two infinite sets have the same size if there is a bijection between them.

→ Not all infinite sets are the same size! (since we cannot find a bijection between them)

Transclude of composition

Identity function

The identity function on a set $A$ is the function ${\text{id}}_A:A\to A,x\mapsto x$.

Inverse function

$f:A\to B$
$f^{-1}:B\to A⟺\underset{A\to B\to A}{\underbrace{f^{-1}\circ f={\text{id}}_A}},\underset{B\to A\to B}{\underbrace{f\circ f^{-1}={\text{id}}_B}}$
$f^{-1}$ exists if and only if $f$ is bijective.

EXAMPLE

$f:\mathbb{R}\to \mathbb{R},x\mapsto x^3$
→ $f^{-1}:\mathbb{R}\to \mathbb{R},x\mapsto \sqrt[3]{x}$
$f^{-1}(f(x))=\sqrt[3]{x^3}=x$
$f(f^{-1}(x))=(\sqrt[3]{x}{)}^3=x$

EXAMPLE

$f:\mathbb{R}\to \mathbb{N},x\mapsto 0$
$f^{-1}:\mathbb{N}\to \mathbb{R},n\mapsto f^{-1}(n)$
$f^{-1}(f(x))=f^{-1}(0)=x$ (always $f^{-1}(0)$ for any x)
$⟹f^{-1}\circ f\ne {\text{id}}_{\mathbb{R}}$

An inverse function exists if and only if the function is bijective and the inverse has to be bijective too.

$f:A\to B,\exists f^{-1}:B\to A⟺f\text{ bijective}$
$\exists f^{-1}⟹f^{-1}\text{ bijective}$ (since the inverse of $f^{-1}$ is $f$ which we assumed to be bijective so the theorem applies to $f^{-1}$ too).

Proof:
“$⟹$”
Let $g=f^{-1}$, we want to show $g$ is surjective and injective.
$\forall y\in B:(f\circ g)(y)=y$ (one of the conditions for the inverse function)
$⟹\forall y\in B\exists x\in A:f(x)=y$ (e.g $x=g(y)$, as in the line above: $f(g(y))$)
$⟹f$ surjective
$f(x)=f(y),x=g(f(x))=g(f(y))=y⟹f$ injective
“$⟸$”
$f$ bijective, we want to proof there is an inverse.
$\forall y\in B\exists x\in A:f(x)=y$ (definition of surjective)
$f$ injective $⟹\nexists z\ne x:f(z)=y$
Let $g:B\to A,y\mapsto$ the unique $x$ such that $f(x)=y$
$g(f(x))=g(y)=x$ ($g\circ f$ is the identity function)
$f(g(y))=f(x)=y$ ($f\circ g$ is the identity function)
$⟹g=f^{-1}$

preimage

Preimage (or inverse image) of a set

$$f^{-1}(C)=\{x\in A:f(x)\in C\}$$

is the set of all elements in the domain $A$ that get mapped to elements in $C$ under $f$.
Note that this notation does not require $f$ to be invertible - it just describes which inputs lead to outputs in $C$.

Example

For $f(x)=x^2$ and $C=[1,4]$, we have:

$$f^{-1}(C)=[-2,-1]\cup [1,2]$$

since these are all the values of $x$ where $f(x)$ lands in $[1,4]$.

Link to original