Functions

Informally, for each input element in a set $A$, a function assigns a single output element from another set $B$.

• $A$ is the domain of the function;
• $B$ is the co-domain;

Formally, a function is a set of pairs $(a,b)$ no two of which have the same first element.

Definition: The output of a given input is called the image of that input. The image of $q$ under a function $f$ is denoted as $f(q)$.

If $f(q)=r$, we say $q$ maps to $r$ under $f$. In mathese: $q\mapsto r$.

The set from which all outputs are chosen is the co-domain. We write.

$$f:D\to F$$

when we want to sai that $f$ is a function with domain $D$ and co-domain $F$.

Definition: The image of a function is the set of all images of inputs. $\text{Im }f$

e.g. Cosine function $cos(x)$
$cos:\mathbb{R}\to \mathbb{R}$, which means the domain is $\mathbb{R}$ and the co-domain is $\mathbb{R}$.
The image of $cos(x)$, $\text{Im }cos$, is $\{x\in \mathbb{R}:-1\le x\le 1\}$ which is not the same as the co-domain which is the whole $\mathbb{R}$.

Set of functions with domain and co-domain

Definition: For sets $F$ and $D$, $F^D$ denotes all functions from $D$ to $F$.

For finite sets: $|F^D|=|F{|}^{|D|}$

Identity function and composition

For any Domain $D$, there is a identity function:

$$i{d}_D:D\to D$$

for each domain element $d$ to itself.

Definition: For functions $f:A\to B$ and $g:B\to C$ the functional composition of $f$ and $g$ is the function:

$$(g\circ f):A\to C\text{ defined by }(g\circ f)(x)=g(f(x))$$

e.g.:
Composition of $g(y)=y^2$ and $f(x)=x+1$ is $(g\circ f)(x)=(x+1{)}^2$

e.g.:

Longer Example, Caesar cipher

• Define the function $f:\{A,B,C,...,Z\}\to 0,1,2,...,25$
  $f$ is the encoding function that translates the letters into positions.

• Define $g$ on the domain/co-domain $\{0,1,2,...,25\}$ by $g(x)=(x+3)\text{ mod }26$
  $g$ is the function that traslate the positions for the cipher.

• Define $h$ with domain $\{0,1,2,...,25\}$ and co-domain $\{A,...,Z\}$ (the inverse of the domain and co-domain of $f$). This is the decoding function that translates the new translated position back to the letters domain, i.e. $0\mapsto A$, $1\mapsto B$, etc.

Then $h\circ (g\circ f)$, or $h(g(f(x)))$ applied to every letter in a message is the Caesar cipher.

Associativity of function composition

Function composition satisfies associativity, a.k.a.:

$$h\circ (g\circ f)=(h\circ g)\circ f$$

Proof

for any element $x$ of domain of $f$:

$$(h\circ (g\circ f))(x)=h((g\circ f)(x))\text{ by definition of }h\circ (g\circ f)$$ $$=h(g(f(x)))\text{ by definition of }g\circ f$$ $$=(h\circ g)(f(x))\text{ by definition of }h\circ g$$ $$=((h\circ g)\circ f)\text{ by definition of }(h\circ g)\circ f$$

So we can collapse to the form $h(g(f(x)))$ and the unroll it in the other form by using only definitions.

Functional Inverse

Definition: Functions $f$ and $g$ are functional inverse if $f\circ g$ and $g\circ f$ are defined and are identity functions.

A function that has an inverse is invertible.

One-to-One functions

Definition: $f:D\to F$ is one-to-one (iniettiva) if $f(x)=f(y)$ implies $x=y$.

So there are no two distinct elements that have the same image.

Onto Functions

Definitions: $f:D\to F$ is onto (suriettiva o surgettiva) if for every $z\in F$ there exists an $a$ such that $f(a)=z$

Invertibility of functions

Definition.: $f:D\to F$ is one-to-one if $f(x)=f(y)$ implies $x=y$.
Proposition: Invertible functions are one-to-one.
Proof: Assume an invertible function $f$ is not one-to-one. So there exists $x_1\ne x_2$ where $f(x_1)=f(x_2)=y$.
Then $f^{-1}(y)=x_1$ but $f^{-1}(y)=x_2$ and both cannot be true, by the definition of function.

So, an invertible function is one-to-one.

Definition: $f:D\to F$ is onto if for every $z\in F$ there exists an element $a\in D$ such that $f(a)=z$.
Proposition: Invertible functions are onto.
Proof: Assume an invertible function $f$ is not onto. So there exists an element $\hat{y}$ in co-domain such that for no $x$ does $f(x)=\hat{y}$
But $f^{-1}(\hat{y})=\hat{x}$ for some $\hat{x}$, and by the definition of the inverse, $f(\hat{x})=\hat{y}$, a contradiction.

This is because, by the definition of function, every possible element in the domain has to have an image in the co-domain under the function. So, if the function is invertible, then there is a $\hat{x}$ such that $f^{-1}(\hat{y})=\hat{x}$ and therefore by definition of the inverse we have that $f(\hat{x})=\hat{y}$.