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$) must agree with the domain of $g$.
  • 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 odds plus gaps).

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)$ (equality needs injectivity); $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 / Where This Shows Up Later​

  • Semester 2 (algorithms). An algorithm's worst-case behavior is its image over the input space; a reduction from problem $X$ to problem $Y$ is an injective map that preserves solutions. Dynamic programming is compositional by construction.
  • Semester 3 (software design). Type isomorphisms are bijections between value sets. Functor laws (identity, composition) are exactly the composition facts on this page, abstracted.
  • Semester 4 (systems). File descriptors are pre-images of integer keys; access control checks are preimages of "permitted" subsets.
  • Semester 6 (distributed). A distributed system's execution is a function from time to global state; checkpoints and snapshots are images over time slices.
  • Semester 7 (architecture). Context maps in DDD are often bijective translations; non-bijective ones motivate an anti-corruption layer. Bijective transformations preserve semantics; non-bijective ones drop or merge information.

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, but equality requires injectivity?
  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​