Exercises: Functions

DataField.Dev

Exercises: Functions

These run from mechanical warm-ups to full proofs, code, modeling, and a conjecture you must test before you settle. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the daggered (†) and odd-numbered problems are in the appendix answers-to-selected.md — try them before you peek. Throughout, "function" means the §9.1 object: a rule that assigns to every input exactly one output, together with its domain and codomain.

Part A — Warm-ups (⭐)

9.1 † For each relation, decide whether it is a function from $A = \{1,2,3,4\}$ to $B = \mathbb{Z}$, and if not, name which half of "exactly one" fails (totality or single-valuedness): (a) $\{(1,2),(2,4),(3,6),(4,8)\}$; (b) $\{(1,2),(2,4),(3,6)\}$; (c) $\{(1,2),(1,3),(2,4),(3,6),(4,8)\}$; (d) $\{(1,0),(2,0),(3,0),(4,0)\}$.

9.2 Let $f\colon \{-2,-1,0,1,2\} \to \mathbb{Z}$ be $f(x) = x^2 - 1$. List $f$ as an explicit set of ordered pairs, then state its range. Is the range equal to the codomain $\mathbb{Z}$?

9.3 † For $f\colon \mathbb{Z} \to \mathbb{Z}$, $f(x) = 3x - 2$, compute the image $f(\{0,1,2\})$ and the preimage $f^{-1}(\{1, 4, 5\})$. (Remember: $f^{-1}(\cdot)$ here is a set, not an inverse function.)

9.4 Compute each, paying attention to sign: $\lfloor 7.2 \rfloor$, $\lceil 7.2 \rceil$, $\lfloor -7.2 \rfloor$, $\lceil -7.2 \rceil$, $\lfloor -4 \rfloor$, and $\lceil 4 \rceil$.

9.5 † Let $f(x) = x \bmod 5$ on the domain $\{0,1,2,\dots,14\}$ with codomain $\{0,1,2,3,4\}$. Compute the preimage $f^{-1}(\{2\})$. How many elements does it have, and why is that count what it is?

9.6 Classify each by inspection (injective? surjective? bijective?), with a one-line reason: (a) $f\colon \mathbb{Z} \to \mathbb{Z}$, $f(x) = x + 100$; (b) $g\colon \mathbb{Z} \to \mathbb{Z}$, $g(x) = \lvert x \rvert$; (c) $h\colon \mathbb{R} \to \mathbb{R}$, $h(x) = 5$.

Part B — Prove it (⭐⭐)

9.7 † (Scaffolded — fill the missing steps.) Prove that $f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = 7x - 4$, is injective. Fill the blanks, following the §9.3 template ("assume equal outputs, derive equal inputs"):

Assume $f(a_1) = f(a_2)$. By the definition of $f$, this means $\underline{\hphantom{xxxxxx}} = \underline{\hphantom{xxxxxx}}$.
Adding $4$ to both sides gives $\underline{\hphantom{xxxxxx}} = \underline{\hphantom{xxxxxx}}$.
Dividing both sides by $7$ gives $\underline{\hphantom{xxxx}}$, which is what injectivity requires. $\blacksquare$

9.8 Prove that $f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = 7x - 4$ (same function as 9.7), is surjective, using the §9.3 surjectivity template (start from an arbitrary $b$, construct an $a$ with $f(a) = b$). Having proved both, what may you now conclude about $f$, and which theorem of §9.4 lets you conclude $f$ has an inverse?

9.9 † Prove that $f\colon \mathbb{Z} \to \mathbb{Z}$, $f(n) = 2n + 1$, is injective but not surjective. (For "not surjective," exhibit a single codomain element with no preimage and justify it in one line — a counterexample in the sense of Chapter 2.)

9.10 Let $f\colon A \to B$ and $g\colon B \to C$ be functions. Prove that if $g \circ f$ is injective, then $f$ is injective. (Hint: assume $f(a_1) = f(a_2)$ and apply $g$ to both sides; you do not need $g$ to be injective.)

9.11 † Prove that the composition of two surjections is a surjection: if $f\colon A \to B$ and $g\colon B \to C$ are both surjective, then $g \circ f\colon A \to C$ is surjective. (This is the companion to the in-chapter injection proof; use the "peel one layer" strategy in reverse — start from a target in $C$.)

9.12 Let $f\colon A \to B$ be a bijection. Prove that its inverse $f^{-1}\colon B \to A$ is also a bijection. (Hint: you already know $f^{-1} \circ f = \operatorname{id}_A$ and $f \circ f^{-1} = \operatorname{id}_B$; use the §9.4 invertibility theorem rather than re-deriving everything.)

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it — hand-trace and include an # Expected output: comment, matching the book's convention. Represent a finite function as a dict {input: output}, exactly as in §9.1 and the Project Checkpoint.

9.13 † Write image(f, S) that returns the image $f(S)$ as a set, given a finite function f (a dict) and a subset S of its domain (an iterable). Test it on f = {0:0, 1:1, 2:4, 3:9} and S = {1, 2, 3}, and include the expected output.

9.14 Write preimage(f, T) that returns the preimage $f^{-1}(T)$ as a set, given a finite function f and a subset T of its codomain. Test it on f = {-2:4, -1:1, 0:0, 1:1, 2:4} and T = {1, 4}, and include the expected output. Explain in a comment why the result can be larger than T.

9.15 † Write is_bijective(f, codomain) from scratch (do not import the Toolkit) and use it to decide whether p = {0:2, 1:0, 2:3, 3:1} is a bijection onto range(4). Then write one extra line that, using your function, prints the inverse of p only if p is bijective. Include the expected output.

9.16 Write a function is_idempotent(f) that returns True iff $f \circ f = f$ on a finite function f (i.e., $f(f(x)) = f(x)$ for every x in the domain, assuming $\operatorname{range}(f) \subseteq \operatorname{domain}(f)$). Test it on the "round-down-to-even" map f = {0:0, 1:0, 2:2, 3:2, 4:4}. Include the expected output. (Idempotent maps are the projections you will meet again in Chapter 12.)

Part D — Find the error (⭐⭐)

Each argument below is wrong. State precisely which step fails and why, citing the relevant definition or theorem.

9.17 † Claim: $f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$, is injective. "Proof": Assume $f(a_1) = f(a_2)$, so $a_1^2 = a_2^2$. Taking square roots of both sides gives $a_1 = a_2$. Therefore $f$ is injective. $\blacksquare$ — Find the flaw, and give a one-line counterexample showing the claim is actually false.

9.18 Claim: For every function $f\colon A \to B$, the preimage $f^{-1}(B)$ equals $A$ and the image $f(A)$ equals $B$. "Proof": the preimage of everything is everything, so $f^{-1}(B) = A$; by the same logic $f(A) = B$. $\blacksquare$ — One of these two equalities always holds and the other can fail. Say which is which, and give a concrete $f$ that breaks the false one.

9.19 † Claim: If $f\colon A \to B$ is surjective, then it is invertible, because surjectivity means every $b \in B$ has a preimage, so we can define $f^{-1}(b)$ to be "the" preimage. "Proof": set $f^{-1}(b) = a$ where $f(a) = b$. $\blacksquare$ — Identify the exact word in this argument that hides the bug, name the property that is missing, and give a small surjective $f$ for which the "definition" fails to define a function.

9.20 Claim: For functions $f\colon A \to B$ and $g\colon B \to C$, the composition $g \circ f$ means "apply $g$ first, then $f$," because $g$ is written first. "Justification": we read left to right. — Explain why this is backward, and trace $g(f(2))$ for $f(x) = x+1$ and $g(x) = 2x$ to show which function truly runs first.

Part E — Model it (⭐⭐ / ⭐⭐⭐)

Translate each real scenario into the discrete-math objects of this chapter — name the domain, codomain, and the property at stake.

9.21 † (Model it.) A URL shortener turns a long URL into a short code and must be able to turn the short code back into the original long URL on every visit. Model the shortener as a function: what is the domain, what is the codomain, and which property of §9.3–9.4 must it have for the "turn it back" step to be possible at all? What goes wrong, in this chapter's language, if two different long URLs ever receive the same short code?

9.22 (Model it.) A seating system assigns each of the 300 ticket-holders to one of 300 numbered seats, with no seat shared and no seat left empty. Model the assignment as a function $f\colon \text{People} \to \text{Seats}$. Which single property captures "no seat shared and none empty," and which theorem of §9.3 lets you conclude that property from just "no two people share a seat"? Justify the appeal to that theorem by checking its hypotheses.

9.23 † (Model it — type signatures.) A library exposes a function with the type signature Callable[[bytes], bytes] that is documented as "compress losslessly." Translate "lossless" into a property of this chapter, explain (using §9.4) why decompression is exactly the inverse, and state what the type signature alone fails to guarantee about the function (think §9.2: codomain vs. range).

9.24 (Model it.) An ID-card system maps each employee to a 4-digit PIN. The company has 12{,}000 employees. Using a property and a theorem from this chapter, argue that two employees must share a PIN, and name the more general principle (and the chapter that proves it) that this is an instance of.

Part F — Conjecture and test (⭐⭐⭐)

9.25 † (Conjecture and test, then prove or disprove.) For a finite set $A$ with $\lvert A \rvert = n$, how many **bijections** $f\colon A \to A$ are there? First write code that, for small $n$ (say $n = 0,1,2,3,4$), enumerates all functions $A \to A$ and counts how many are bijections; tabulate the counts. From the table, conjecture a closed-form formula in $n$. Then prove your conjecture by a direct counting argument (think: how many choices for $f(a_1)$, then $f(a_2)$ given that, and so on). State your answer using factorial notation, and note which later chapter (per the book's plan) studies such counts systematically.

9.26 (Conjecture and test.) Define $g\colon \{0,1,\dots,n-1\} \to \{0,1,\dots,n-1\}$ by $g(x) = (a x + b) \bmod n$ for fixed integers $a, b$. Write code that, for $n = 10$ and every pair $(a,b)$ with $0 \le a, b < 10$, checks whether $g$ is a bijection. Tabulate which values of $a$ make $g$ a bijection (the value of $b$ should not matter — confirm that). Conjecture the condition on $a$ (in terms of $a$ and $n$) that makes $g$ a bijection. You are not asked to prove it here — this is exactly the modular-inverse condition that Chapter 23 will prove; report your conjecture and the evidence.

Part G — Interleaved & Deep Dive

Mixing in earlier chapters keeps them sharp.

9.27 † (Ch. 8 + 9.) Let $A$ and $B$ be finite with $\lvert A \rvert = 3$ and $\lvert B \rvert = 2$. Using the Chapter 8 count for $\lvert A \times B \rvert$ and the function definition of §9.1, count the total number of functions $f\colon A \to B$ (each input independently chooses an output). Then count how many are surjective. Can any be injective? Justify each count.

9.28 (Ch. 2 + 9.) Write the statement "$f$ is not injective" as a fully quantified logical sentence (use $\exists$ and the negation rules from Chapter 2), starting from the definition $\forall a_1, a_2,\ \big(f(a_1) = f(a_2) \rightarrow a_1 = a_2\big)$. Your negation should read as a precise description of a collision.

9.29 † (Ch. 6 + 9.) Let $f\colon \{0,1,\dots,n\} \to \{0,1,\dots,n\}$ be a bijection, and define its $k$-fold composition $f^{(k)} = f \circ f \circ \cdots \circ f$ ($k$ times), with $f^{(0)} = \operatorname{id}$. Prove **by induction on $k$** that $f^{(k)}$ is a bijection for every $k \ge 0$. State $P(k)$, give the base case, and in the inductive step cite the in-chapter theorem that the composition of two bijections is a bijection.

9.30 (Ch. 8 + 9, Deep Dive.) Recall from §9.6 that for a finite domain a function "is" a dict. Let $\lvert A \rvert = m$ and $\lvert B \rvert = n$. Give a clean bijection-free counting argument for the number of functions $A \to B$, then explain in one sentence why this count is written $n^m$ and how that notation foreshadows Chapter 10's idea that the set of functions $A \to B$ is sometimes denoted $B^A$.

9.31 † (Deep Dive — toward Chapter 10.) The §9.3 finite theorem says injective $\Leftrightarrow$ surjective for $f\colon A \to B$ when $A, B$ are finite of equal size. Show this fails on infinite sets by giving, for $A = B = \mathbb{N}$ (with $\mathbb{N}$ including $0$): (a) a function that is injective but not surjective, and (b) a function that is surjective but not injective. Explain in one sentence why these "near-misses" are exactly what makes infinite cardinality (Chapter 10) interesting.

9.32 (Deep Dive.) Prove that if $f\colon A \to B$ is injective and $g\colon A \to B$ is injective, their "pairing" is not generally a function — i.e., explain why injectivity is a property of one function and cannot be combined pointwise the way you might combine two number-valued functions by addition. Then state precisely what is true: the restriction of an injective $f$ to any subset $S \subseteq A$ is still injective, and prove it in two lines.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: explicit use of the right template (injectivity: assume equal outputs, derive equal inputs; surjectivity: take arbitrary $b$, build a preimage), correct attention to domain and codomain, and a clean conclusion ending in $\blacksquare$.