title: "Function"

Function

Definition. A function $f: A \to B$ assigns to each element of the domain $A$ exactly one element of the codomain $B$; formally it is a relation $f \subseteq A \times B$ in which every $a \in A$ appears in exactly one pair.

The key properties are Injective, Surjective, and bijective. Machines compute functions from strings to answers, and resource bounds are functions from $\mathbb{N}$ to $\mathbb{N}$ compared by Big-O. Defined in Lecture 2.