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$