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

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$