# 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