# Functions

Functions are mappings between sets if for every input there is exactly one output. (So there cannot be mutiple outputs corresponding to a single input like in a relation.)

$f: A \rightarrow B$, A function $f$ from $A$ to $B$

- Domain: $Dom(f)$
- Range: (also called image): $Im(f) = Ran(f) = {f(x) \mid x \in Dom(f)}$
- Equality: $f(a) = g(a)$ for all $a \in A$

## Operations #

- Domain restriction
- Restriction
- Composition: $(g \circ f)(x) = f(g(x))$
- Associative: $h \circ (g \circ f) = (h \circ g) \circ f$
- Monoid

## Properties #

On function: $f: A \rightarrow B$

**Total**- $Dom(f) = A$
- If for every input the function is defined
- Otherwise partial

**Injectivity**: maps distinct elements to distinct elements- evey input has a different output
- Formally: $\forall (a, b) \in A$: $f(a) = f(b) \Rightarrow a = b$
- $|A| \leq |B|$ if there is an injection $f: A \rightarrow B$
- injection, into, one-to-one

**Surjectivitity**: all outputs have inputs- for each $b \in B$ there exsists an element $a \in A$ such that $f(a) = b
- $|A| = |B|$ if there is an bijection $f: A \rightarrow B$
- surjection, onto

**Bijective**: total, injective and surjective- Injective: bijection from $Dom(f)$ to $Ran(f)$

**Invertible**: if its inverse relation $f^{-1}$ is also a function- When a function is reversed (the relation) is possibly not a function because there might be input values that map to different outputs. A function is
*invertible*if the ralation you get is also a function. - $f$ is only invertible if and only if $f$ is an injection
- If $f$ is invertible then $f^{-1}$ is also invertible
- If $f$ and $g$ both invertible then $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$

- When a function is reversed (the relation) is possibly not a function because there might be input values that map to different outputs. A function is

## Growth of Functions #

**Big-O notation**: $f \in O(g)$ for all $n \geq k$: $|f(n)| \leq c \cdot |g(n)|$**Big-Theta:**$\Theta(f)$ set of all functions that have the same order of $f$