Functions

A function assigns to every element of one set exactly one element of another. Hash functions, encodings, permutations of an array, the transition function of an automaton and the indexing of an array are all functions. In discrete mathematics, functions are the tool for comparing the sizes of sets (bijections), for counting (how many maps of a given kind exist) and for building algebraic structures (monoids and groups are sets with a binary operation, which is a function).

A function $f : A \to B$ is a relation $f \subseteq A \times B$ such that every $a \in A$ is related to exactly one $b \in B$, written $f(a) = b$.

If every input has at most one image but some have none, the relation is a proper partial function, not a total function on the stated domain. If an input has two images, it is not even a partial function.

For finite sets of the same size, injective, surjective and bijective are equivalent: a map $f : A \to A$ on a finite set is one-to-one if and only if it is onto. This fails for infinite sets: $f(n) = 2n$ on $\mathbb{N}$ is injective but not surjective.

Surjectivity depends on the codomain: $f(x) = x^2$ is surjective as a map $\mathbb{R} \to [0, \infty)$ but not as a map $\mathbb{R} \to \mathbb{R}$. Injectivity depends on the domain: the same rule is injective on $[0, \infty)$ but not on $\mathbb{R}$.

For $f : A \to B$ and $g : B \to C$, the composition $g \circ f : A \to C$ is $(g \circ f)(a) = g(f(a))$: apply $f$ first. Composition is associative, $h \circ (g \circ f) = (h \circ g) \circ f$, but not commutative in general.

Example for the third row: $A = \{1\}$, $B = \{1, 2\}$, $C = \{1\}$, $f(1) = 1$, $g(1) = g(2) = 1$. Then $g \circ f$ is injective (one-element domain), $f$ is injective, but $g$ is not.

$f : A \to B$ has an inverse $f^{-1} : B \to A$ with $f^{-1}(f(a)) = a$ and $f(f^{-1}(b)) = b$ if and only if $f$ is a bijection. Then $f^{-1}$ is also a bijection and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

Example: $f(x) = 3x + 2$ on $\mathbb{R}$ is a bijection with $f^{-1}(y) = (y - 2)/3$. On $\mathbb{Z}$, the same rule is injective but not surjective (1 has no preimage), so it has no inverse as a map $\mathbb{Z} \to \mathbb{Z}$.

For $f : A \to B$, $S_1, S_2 \subseteq A$ and $T_1, T_2 \subseteq B$:

For real $x$, $\lfloor x \rfloor$ is the largest integer $\le x$ and $\lceil x \rceil$ the smallest integer $\ge x$. So $\lfloor -2.5 \rfloor = -3$ and $\lceil -2.5 \rceil = -2$. Useful facts for integer $n$ and real $x$: $\lfloor x + n \rfloor = \lfloor x \rfloor + n$; $\lceil x \rceil = -\lfloor -x \rfloor$; $\lfloor n/2 \rfloor + \lceil n/2 \rceil = n$; $x - 1 < \lfloor x \rfloor \le x \le \lceil x \rceil < x + 1$.

Let $|A| = m$ and $|B| = n$.

Here $S(m, n)$ is the Stirling number of the second kind (partitions of an $m$-set into $n$ non-empty blocks; see Relations). A surjection is a partition of $A$ into $n$ blocks, followed by an assignment of the $n$ blocks to the $n$ outputs.

Derivation of the onto formula. Let $E_i$ be the set of functions that never take the value $b_i$. A function is onto exactly when it lies in no $E_i$. Any $k$ of the $E_i$ together leave $n - k$ allowed outputs, giving $(n-k)^m$ functions, so inclusion-exclusion gives the alternating sum. The full principle is in Counting.

If $m > n$, no function $A \to B$ is injective: some output has at least two preimages. Generalised form: some output has at least $\lceil m/n \rceil$ preimages.

$|A| = 4$, $|B| = 3$. All functions: $3^4 = 81$. Injective: 0 (since $4 > 3$). Onto:

Reverse direction, $|A| = 3$, $|B| = 4$: all $4^3 = 64$, injective $4 \cdot 3 \cdot 2 = 24$, onto 0.

How many functions $f : \{1, 2, 3\} \to \{1, 2, 3\}$ are not bijections? $3^3 - 3! = 27 - 6 = 21$. How many satisfy $f(f(x)) = x$ for every $x$ (involutions)? The identity, plus the three that swap one pair and fix the third element: 4.

Among any 13 people, two share a birth month ($\lceil 13/12 \rceil = 2$). How many integers must be chosen from 1 to 100 to guarantee that two have the same remainder mod 7? $7 + 1 = 8$.