Chapter 9: Functions — Key Takeaways
A one-page reference. Reread this before an exam; follow the section links back into index.md for the
worked proofs.
Core definitions
| Term | Definition | Symbol |
|---|---|---|
| Function $f\colon A \to B$ | a subset of $A \times B$ with exactly one output per input (totality + single-valuedness) | $f(a) = b$ |
| Domain | the set of allowed inputs | $A$ |
| Codomain | the declared output set (a type promise) | $B$ |
| Range (image of $f$) | the outputs actually produced; $\operatorname{range}(f) \subseteq B$ | $\{f(a) \mid a \in A\}$ |
| Image of a set $S$ | push $S$ forward | $f(S) = \{f(a) \mid a \in S\}$ |
| Preimage of a set $T$ | pull $T$ back — a set, exists for every $f$ | $f^{-1}(T) = \{a \mid f(a) \in T\}$ |
| Identity | "do nothing" function | $\operatorname{id}_A(a) = a$ |
Codomain vs. range: the type checker verifies the codomain; only a proof reveals the range. The gap between them is what "surjective" measures.
The three properties (memorize the tests)
| Property | Formal definition | Plain meaning | To prove | To disprove |
|---|---|---|---|---|
| Injective (one-to-one) | $f(a_1)=f(a_2) \rightarrow a_1=a_2$ | no collisions | assume $f(a_1)=f(a_2)$, derive $a_1=a_2$ | one collision (two inputs, same output) |
| Surjective (onto) | $\forall b\,\exists a:\ f(a)=b$ | range $= B$ | take arbitrary $b$, build an $a$ with $f(a)=b$ | name a $b$ never produced |
| Bijective | injective and surjective | perfect pairing | prove both | disprove either |
Finite tests (function as a dict):
- injective $\iff$ len(set(f.values())) == len(f)
- surjective $\iff$ set(f.values()) == set(codomain)
Composition and inverses
| Idea | Rule |
|---|---|
| Composition $g \circ f$ | $(g\circ f)(a) = g(f(a))$ — apply $f$ first (rightmost runs first) |
| Defined when | codomain of $f$ = domain of $g$ |
| Commutative? | No in general ($g\circ f \neq f \circ g$) |
| Associative? | Yes ($h\circ(g\circ f) = (h\circ g)\circ f$) |
| Preserves properties | inj∘inj = inj; surj∘surj = surj; bij∘bij = bij |
| Invertible | $\exists g$ with $g\circ f=\operatorname{id}_A$ and $f\circ g=\operatorname{id}_B$; then $g=f^{-1}$ (unique) |
★ The central theorem
$$f \text{ is invertible} \iff f \text{ is bijective.}$$ Why: surjectivity $\Rightarrow$ every $b$ has a preimage (existence); injectivity $\Rightarrow$ it is unique (uniqueness); existence + uniqueness = a well-defined inverse.
Slogan: to invert, bijize. Finite inverse = swap each
(key, value)pair — valid only if $f$ is a bijection.
Finite-set equivalence (sets up pigeonhole, Ch. 17)
For finite $A, B$ with $\lvert A\rvert = \lvert B\rvert$: $$\text{injective} \iff \text{surjective} \iff \text{bijective}.$$ Read in reverse = pigeonhole: more items than boxes $\Rightarrow$ some box has two. False for infinite sets — the engine of Chapter 10.
Standard functions (and the traps)
| Function | Maps | Watch out |
|---|---|---|
| Floor $\lfloor x\rfloor$ | $\mathbb{R}\to\mathbb{Z}$, greatest int $\le x$ | rounds toward $-\infty$, not zero: $\lfloor -3.2\rfloor=-4$ |
| Ceiling $\lceil x\rceil$ | $\mathbb{R}\to\mathbb{Z}$, least int $\ge x$ | $\lceil -3.2\rceil=-3$ |
Truncation int(x) |
rounds toward zero | int(-3.2)=-3 $\neq$ math.floor(-3.2)=-4 |
| Mod $x \bmod n$ | $\mathbb{Z}\to\{0,\dots,n-1\}$ | surjective, not injective from a bigger domain |
| Exp $b^x$ / Log $\log_b x$ | inverse bijections | $\log_b(b^x)=x$; $\log$ turns $\times$ into $+$ |
Handy: pages for $n$ items, $k$ per page $=\lceil n/k\rceil$. Balanced BST height $=\lfloor\log_2 n\rfloor$.
Decision aid: "which property do I need?"
| If you want to… | You need $f$ to be… |
|---|---|
| undo / reverse a transform (lossless codec, decryption) | bijective (invertible) |
| guarantee no two inputs map to one output (lossless compression accepts inputs injectively) | injective |
| guarantee every target value is reachable | surjective |
| make reversal hard (password hash, one-way function) | non-invertible (by design) |
| compare two set sizes (Ch. 10) | find a bijection between them |
Common pitfalls
- Formula $\neq$ function. A function is rule + domain + codomain. Same formula, different domain/codomain $\Rightarrow$ different function (and possibly different classification).
- Preimage $f^{-1}(T)$ is a set, not an inverse. It exists for every $f$; the inverse function $f^{-1}$ exists only when $f$ is bijective.
- Composition order. $g\circ f$ does $f$ first. Reversing the order generally changes the result.
- Floor is not truncation on negatives.
- Hash collisions are a theorem, not a bug: domain bigger than codomain $\Rightarrow$ not injective.
Toolkit additions — dmtoolkit/functions.py
| Function | Signature | Returns |
|---|---|---|
| classify | is_injective(f), is_surjective(f, codomain), is_bijective(f, codomain) |
bool |
| compose | compose(g, f) |
dict for $g\circ f$ (apply $f$ first) |
| invert | inverse(f) |
dict for $f^{-1}$; raises if $f$ not injective |
Functions are stored as dicts {input: output}. is_bijective is reused in Chapter 10 as the test for
"same size." inverse enforces the invertibility theorem by refusing non-bijections.
Connections
- Backward: built on Chapter 8 (ordered pairs, Cartesian product, finite cardinality).
- Forward: Chapter 10 (cardinality via bijections), Chapter 14 (floor/log in complexity), Chapter 17 (pigeonhole), Chapter 26 (hash functions, one-way functions).