Book of Proof, third edition
Richard Hammack · Free textbook
Read §12.2, printed pp.228–230, for injection/surjection; §12.5, printed p.240 / PDF p.252, for inverses.
Open the sourceFunctions and what they forget
A map may preserve structure, collapse it, or merely rename it.
Prerequisites: 02 · Why enlarge the number system?, 03 · Sets: the grammar of selection
Understand
Objectives
- Specify domain and codomain before classifying a function.
- List a fiber, including an empty one when appropriate.
- Distinguish a bijection from an isomorphism of a named structure.
Start with something you can see
Assign each person a birthday. Predict whether a birthday identifies one person: two people can share it. To inspect a smaller map, square each integer from −2 through 2. Predict the inputs that give output 1 before filling the table. The MIT lecture separates the collision test from the coverage test at 12:07. [1]
Give the idea a precise name
A function f:X→Y assigns every input in its domain X exactly one output in its codomain Y. It is injective if distinct inputs never share an output; surjective if every member of Y is reached; bijective if both. For y∈Y, the fiber over y is the set of inputs x∈X with f(x)=y. A fiber can be empty. A bijection is an isomorphism only if it also preserves the named structure, such as graph adjacency.
f⁻¹({y}) = {x∈X : f(x)=y}
The superscript −1 on a set denotes inverse image, not an inverse function: the inverse function exists only for a bijection to the chosen codomain. The braces collect all qualifying inputs; the colon means “such that.” For composition (g∘f)(x)=g(f(x)), f acts first when its outputs lie in the domain of g.
Work one small world
Let X={−2,−1,0,1,2}, Y={0,1,4}, and f:X→Y send x to x². The fiber over 1 is {−1,1}; the fiber over 4 is {−2,2}. Every output in Y is reached, so f is surjective, but it is not injective. With X={0,1,2} and the same Y, the same formula is bijective. If the codomain is instead {0,1,4,9}, the fiber over 9 is empty and the map is not surjective.
| Input | Square | Fiber of that output in the five-input domain |
|---|---|---|
| −2 | 4 | {−2,2} |
| −1 | 1 | {−1,1} |
| 0 | 0 | {0} |
| 1 | 1 | {−1,1} |
| 2 | 4 | {−2,2} |
Counterexample to “the formula alone decides invertibility”: x² on ℝ→ℝ is neither injective nor surjective; on ℝ→[0,∞) it is surjective but not injective; on [0,∞)→[0,∞) it is bijective with square-root inverse. Changing only the declared sets changes the answer. A bijection of graph vertices still need not preserve adjacency.
THE BRIDGEA projection is a function with fibers too. Describing them identifies exactly which input distinctions disappear.
WHERE THIS IDEA STOPSInjectivity depends on the domain, surjectivity on the codomain. No graph-isomorphism claim follows from a bijection alone.
Experiment
Open the fibers lab with f(x)=x² on {−2,−1,0,1,2}. Select output 1 and predict the two inputs in its fiber. Restrict the domain to {0,1,2}, then use Transfer · absolute value; distinguish an inverse image from an inverse function.
When does changing the domain turn an irreversible-looking function into an invertible one?
Check & explain
For f:ℝ→[0,∞) defined by f(x)=x², which is correct?
- Bijective
- Surjective but not injective
- Injective but not surjective
For f:{−2,−1,0,1,2}→{0,1,4} given by f(x)=x², how many inputs are in the fiber over 4?
Teach back
Give two functions with the same formula x² but different declared domains or codomains. Classify each and explain whether its inverse image of {1} is an inverse function value.
- Name both sets for each function.
- Calculate an explicit fiber and collision or missing output.
- Separate inverse image from inverse function.
Read deeper
Lecture 2: Cantor's Theory of Cardinality (Size)
MIT OpenCourseWare · Lecture · 85 min
Start at 5:00. Watch the short core 12:07–15:07; then the longer passage 5:00–20:00. The full 85-minute lecture is available from the same link.
Open the source