Skip to main content

Images, Preimages, Composition, and Classification

What This Concept Is​

Given a function $f : A \to B$, you often want more than pointwise evaluation $f(a)$. You want to reason about how $f$ transforms whole subsets and about structural properties that hold across all inputs. This concept collects four such tools:

  • Image of a subset: $f(S) = {f(a) : a \in S}$ for $S \subseteq A$. Forward pushing.
  • Preimage of a subset: $f^{-1}(T) = {a \in A : f(a) \in T}$ for $T \subseteq B$. Backward pulling. Note: $f^{-1}$ here is a notation for preimage, not for an inverse function -- preimage is defined whether or not $f$ is bijective.
  • Composition: given $f : A \to B$ and $g : B \to C$, define $g \circ f : A \to C$ by $(g \circ f)(a) = g(f(a))$. Order matters and $B$ (the codomain of $f$) can be chosen to agree with the domain of $g$; more generally, the image of $f$ must lie in that domain.
  • Classification by injective, surjective, bijective:
    • Injective (one-to-one): $\forall a_1, a_2 \in A,\ f(a_1) = f(a_2) \rightarrow a_1 = a_2$.
    • Surjective (onto): $\forall b \in B,\ \exists a \in A,\ f(a) = b$.
    • Bijective: both injective and surjective. Bijections have genuine two-sided inverses $f^{-1} : B \to A$.

Together these turn functions from pointwise evaluators into proof objects -- things you reason about structurally.

Why It Matters Here​

The vocabulary here is the vocabulary of half of Semester 2 (algorithm correctness), much of Semester 4 (data-type mappings), and most of modern programming language theory (isomorphism of types). Injectivity and surjectivity are the two quantifier shapes of concept 3 and 4, applied concretely to functions. Students who internalise "injective = forward cancellation, surjective = witness-for-every-output" can read definitions in later modules at full speed.

Images and preimages are where students first meet the idea of lifting a pointwise operation to a set-level operation. Databases, type systems, and probabilistic reasoning all use this lifting; getting comfortable with it here is an investment that returns every semester.

Composition will be the grammar of function-as-object manipulation in every functional programming language and in every category-theoretic treatment you meet later. It is also the structural move behind dynamic programming, algorithmic reductions, and many architecture patterns (pipeline, chain-of-responsibility).

Concrete Examples​

Example 1 -- computing an image and a preimage.

Let $f : \mathbb{Z} \to \mathbb{Z}$ be $f(n) = 2n$.

  • $f({0, 1, 2}) = {0, 2, 4}$ (image).
  • $f^{-1}({0, 2, 4}) = {0, 1, 2}$ (preimage of the image).
  • $f^{-1}({3}) = \emptyset$ (no integer doubles to $3$).
  • $f^{-1}(\text{evens}) = \mathbb{Z}$ (every integer doubles to an even).

Classification: $f$ is injective (different inputs give different doubles), not surjective onto $\mathbb{Z}$ (no integer maps to an odd integer).

Example 2 -- injectivity proof template.

Claim: $g : \mathbb{R} \to \mathbb{R}$, $g(x) = 3x + 5$ is injective.

Proof. Let $x_1, x_2 \in \mathbb{R}$ and suppose $g(x_1) = g(x_2)$. Then $3x_1 + 5 = 3x_2 + 5$, so $3x_1 = 3x_2$, hence $x_1 = x_2$. $\blacksquare$

The opening move is always the same: assume equal outputs, derive equal inputs.

Example 3 -- surjectivity proof template.

Claim: The same $g(x) = 3x + 5$ is surjective onto $\mathbb{R}$.

Proof. Let $y \in \mathbb{R}$. Choose $x = (y - 5)/3$, which exists in $\mathbb{R}$. Then $g(x) = 3 \cdot (y-5)/3 + 5 = y$. $\blacksquare$

The opening move is always the same: let an arbitrary codomain element be given, exhibit a preimage.

Example 4 -- composition and its classifications.

Let $f : \mathbb{Z} \to \mathbb{Z}$, $f(n) = n + 1$, and $g : \mathbb{Z} \to \mathbb{Z}$, $g(n) = 2n$.

  • $(g \circ f)(n) = g(f(n)) = g(n + 1) = 2(n+1) = 2n + 2$.
  • $(f \circ g)(n) = f(g(n)) = f(2n) = 2n + 1$.

These are different functions -- composition is not commutative. Both are injective (composition of injectives); neither is surjective onto $\mathbb{Z}$ (first maps to evens, second maps to all odd integers).

Common Confusion / Misconceptions​

  1. Mixing image and preimage directions. The image pushes forward from $A$ to $B$; the preimage pulls backward from $B$ to $A$. Writing $f(T)$ when you mean $f^{-1}(T)$ is one of the most common notational bugs.
  2. "Injective means every output is used." That is surjectivity, not injectivity. Injectivity means distinct inputs stay distinct; surjectivity means every codomain element is hit. A function can be one without the other.
  3. $f^{-1}$ read as the inverse function. $f^{-1}$ applied to a set is the preimage (always defined). $f^{-1}$ applied to a value presupposes $f$ is bijective. Context disambiguates, but beginners confuse the two.
  4. Composition direction. $g \circ f$ applies $f$ first, then $g$. The notation is right-to-left (historical convention from function notation). Reversing the order gives a different function.
  5. Forgetting codomain for surjectivity. "Is $f$ surjective?" has no answer without a specified codomain. $f(n) = 2n$ on $\mathbb{Z}$ is not surjective onto $\mathbb{Z}$, but it is surjective onto the even integers.

How To Use It​

Injectivity proofs:

  1. Start: "Let $a_1, a_2 \in A$ with $f(a_1) = f(a_2)$."
  2. Unpack $f$'s rule and manipulate the equation.
  3. Conclude $a_1 = a_2$.

Surjectivity proofs:

  1. Start: "Let $b \in B$ be arbitrary."
  2. Construct a preimage $a \in A$ (often by solving $f(a) = b$).
  3. Verify $f(a) = b$ and note $a \in A$ explicitly.

Composition arguments:

  1. Check codomain of $f$ matches domain of $g$.
  2. Compute $(g \circ f)(a) = g(f(a))$.
  3. Use known facts: the composition of injectives is injective; composition of surjectives is surjective; composition of bijections is a bijection.

Images and preimages:

  1. Start from the definition: $y \in f(S)$ iff there exists $s \in S$ with $f(s) = y$.
  2. $a \in f^{-1}(T)$ iff $f(a) \in T$.
  3. Useful identities (prove by element-chasing): $f(S_1 \cup S_2) = f(S_1) \cup f(S_2)$ (always); $f(S_1 \cap S_2) \subseteq f(S_1) \cap f(S_2)$ (injectivity ensures equality for every pair of subsets); $f^{-1}(T_1 \cup T_2) = f^{-1}(T_1) \cup f^{-1}(T_2)$ (always); $f^{-1}(T_1 \cap T_2) = f^{-1}(T_1) \cap f^{-1}(T_2)$ (always).

Transfer to the module project​

Use this concept to state, justify or challenge one claim in the workflow project. Name the mathematical model and the execution assumptions separately; software behavior is not established by an analogy alone.

Check Yourself​

  1. What is the standard opening move in an injective proof? In a surjective proof?
  2. Why is $f(S_1 \cap S_2) \subseteq f(S_1) \cap f(S_2)$ always true, and why does injectivity ensure equality for every pair of subsets?
  3. Give a function on $\mathbb{Z}$ that is surjective but not injective; also one that is injective but not surjective.
  4. Why is composition not commutative in general? Give a minimal example.
  5. What does $f^{-1}(\emptyset)$ equal, regardless of $f$? What about $f^{-1}(B)$?
  6. If $g \circ f$ is injective, what can you conclude about $f$? About $g$? (Only one of the two conclusions is forced.)

Mini Drill or Application​

Classify each function and justify (state "injective: yes/no because…", "surjective: yes/no because…"):

  1. $f : \mathbb{Z} \to \mathbb{Z}$, $f(n) = n + 1$
  2. $g : \mathbb{R} \to \mathbb{R}$, $g(x) = x^2$
  3. $h : \mathbb{Z} \to \mathbb{Z}$, $h(n) = 0$
  4. $p : \mathbb{R}{\ge 0} \to \mathbb{R}{\ge 0}$, $p(x) = x^2$
  5. $q : \mathbb{Z} \to \mathbb{Z}$, $q(n) = n^3$
  6. $r : \mathcal{P}({1, 2}) \to {0, 1, 2}$, $r(S) = |S|$

For two of these, compute one image and one preimage of interesting subsets. For two of them, decide whether they have a well-defined inverse function, and if so write the inverse rule explicitly.

Read This Only If Stuck​

Use the bounded reading guide to locate this lesson's topic in MCS or Rosen. These links open book indexes. Find the named topic in your edition, read one relevant explanation, then reconstruct the argument with the book closed.

When image intersection equality really needs injectivity​

For every function, f(S∩T)⊆f(S)∩f(T). The reverse can fail because an output may have one preimage in S and a different preimage in T, with no preimage in their intersection. Injectivity forces those witnesses equal and repairs the argument.

Be precise about the quantifier: equality for one particular pair S,T does not imply f injective (take S=T=∅). Equality for every pair of subsets does: if f(a)=f(b) with a≠b, take S={a},T={b} to contradict it. This illustrates how an omitted “for every” changes a characterization.

Composition g∘f is defined when f's actual image lies in g's domain; identical intermediate declared sets are sufficient but stronger than necessary. Transfer attempt: prove P8, then construct the typed counterexample in P9.

Use Practice Solutions and Feedback after your attempt, and Proof and Model Contracts to audit assumptions.