function

Function

Let $A,B\ne \varnothing$
A (typed) function from $A$ to $B$ is the triple $(A,B,R_f)$, where $A$ is the domain, $B$ is the codomain, 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 (=unique) element of $B$).
Notation:
Instead of $(A,B,R_f)$, we write $f:A\to B$ ($f$ maps $A$ to $B$)
Instead of $x{R}_{f}y$, we write $f(x)=y$ or $x\mapsto f(x)$ ($x$ is mapped to $f(x)$)

Function graph

The graph of a function $f$ is the set of ordered pairs $(x,y)$, with the relation $f(x)=y$

$$R_f=\{x,f(x)\mid x\in A\}$$

Link to original

Domain of a function

If $f:A\to B$ is a function from set $A$ to set $B$, then the domain of $f$ is the set $A$.

Link to original

Codomain

For a function $f:A\to B$, the set $B$ is called the codomain of $f$.
It is the (declared) set within which all outputs of $f$ must lie, but not all elements of $B$ need to be actual outputs of $f$.

Link to original

Image / Range

The image of a function $f:A\to B$ is the set of all output values it can produce:

$$\text{Im}(f)=\{f(a)\mid a\in A\}\subseteq B$$

It is a subset of the codomain $B$. Iff $f$ is surjective, then $\text{Im}(f)=B$.

Link to original

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$.

Link to original

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)

Link to original

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.

(a surjective not injective function)

Link to original

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$.

Link to original

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}$

Function evaluation

$B^A$ denotes the set of all functions $A\to B$ (hom-class or exponential object).

$$\text{ev}:B^A\times A\to B,f\mapsto f(x)$$

Read: The evaluation applies a function $f:A\to B$ to an argument $x\in A$ and returns the result $f(x)\in B$.