Functions
A function assigns each input exactly one output. Functions model everything from hash tables to encryption.
Definition
A function \(f: A \to B\) assigns to each element of the domain \(A\) exactly one element of the codomain \(B\). The range (or image) is the set of outputs actually produced. A rule that gives some input two outputs, or none, is not a function.
Injective functions
A function is one-to-one (injective) if different inputs always give different outputs: \(f(a) = f(b)\) implies \(a = b\). \(f(x) = 2x\) on the integers is injective; \(f(x) = x^2\) is not, since \(f(2) = f(-2)\). Injective functions never 'collide'.
Surjective functions
A function is onto (surjective) if every element of the codomain is hit by some input. \(f(x) = 2x\) from integers to integers is not onto, since odd numbers are never produced; from reals to reals it is onto. Whether a function is onto depends on the chosen codomain.
Bijections
A function that is both injective and surjective is a bijection: it pairs up the domain and codomain perfectly. Bijections have inverses \(f^{-1}\). For finite sets, a bijection exists exactly when the sets have the same size, which is the formal meaning of 'same number of elements'.
Composition
The composition \((g \circ f)(x) = g(f(x))\) applies \(f\) first, then \(g\). Order matters: with \(f(x) = x + 1\) and \(g(x) = 2x\), \(g(f(3)) = 8\) but \(f(g(3)) = 7\). Compositions of injections are injections, and of bijections are bijections.
(g \circ f)(x) = g(f(x))The pigeonhole principle
If more than \(n\) objects are placed into \(n\) boxes, some box holds at least two. In function terms, there is no injection from a larger finite set to a smaller one. Among any 13 people, two share a birth month; among 367 people, two share a birthday.
Floor, ceiling, and modular functions
The floor \(\lfloor x \rfloor\) rounds down to an integer and the ceiling \(\lceil x \rceil\) rounds up: \(\lfloor 3.7 \rfloor = 3\), \(\lceil 3.2 \rceil = 4\). The mod function \(n \bmod m\) gives the remainder, \(17 \bmod 5 = 2\). These functions appear constantly in algorithms, such as computing how many pages are needed for \(n\) items.
Infinite sets and countability
Bijections compare infinite sets too. The integers can be paired with the natural numbers (0, 1, -1, 2, -2, ...), so they are countable. Cantor's diagonal argument shows the real numbers cannot be listed: there are 'more' reals than integers, a startling result about different sizes of infinity.
Key takeaways
A function assigns exactly one output per input. Injective means no collisions; surjective means every target is hit; bijective means both, with an inverse. Composition applies functions in order. The pigeonhole principle forbids injections into smaller sets, and bijections reveal different sizes of infinity.
Flashcard
A function from A to B
Check your understanding
Is f(x) = x^2 from the integers to the integers one-to-one?