Unit 2 Lesson 2

Injective, surjective, bijective

Three properties that classify the way a function pairs inputs with outputs: injectivity (no two inputs share an output), surjectivity (every output is reached), and bijectivity (both, at once).

Learning Objectives

  • State the definitions of injective, surjective, and bijective functions.
  • Decide which of these three properties a given function has, on finite or real domains.
  • Apply the horizontal line test to a graph.
  • State and apply the composition rules: a composition of injective (or surjective, or bijective) functions has the same property.

Motivation

Every function pairs each input with one output. But the "shape" of that pairing can vary: sometimes different inputs share the same output, sometimes not. Sometimes every element of the codomain is reached, sometimes not. These two simple questions — are the outputs distinct? is every codomain element used? — split functions into three important classes: injective, surjective, and bijective.

The classification matters for a practical reason. As we will see in the next lesson, a function admits an inverse exactly when it is bijective. So before we can ask "can this function be reversed?", we need a vocabulary to describe the property rigorously.

Injective function

A function \(f \colon A \to B\) is injective (or one-to-one) if different inputs always produce different outputs:

\[\forall a_1, a_2 \in A, \quad a_1 \neq a_2 \implies f(a_1) \neq f(a_2).\]

Equivalently, by contrapositive:

\[\forall a_1, a_2 \in A, \quad f(a_1) = f(a_2) \implies a_1 = a_2.\]

The second form is usually easier to work with in proofs: assume two inputs share an output, and deduce that the inputs were in fact the same.

Injective and non-injective

A B
Injective: distinct inputs, distinct outputs.
A B
Not injective: two inputs share an output.

An injective function. The function \(f \colon \mathbb{R} \to \mathbb{R},\; f(x) = 2x + 1\) is injective. Suppose \(f(a_1) = f(a_2)\). Then \(2a_1 + 1 = 2a_2 + 1\), so \(2a_1 = 2a_2\), so \(a_1 = a_2\). The two inputs were the same.

Not injective. The function \(g \colon \mathbb{R} \to \mathbb{R},\; g(x) = x^2\) is not injective: \(g(2) = 4\) and \(g(-2) = 4\) — two different inputs share an output. A single counterexample is enough to refute injectivity.

Surjective function

A function \(f \colon A \to B\) is surjective (or onto) if every element of the codomain is the image of some element of the domain:

\[\forall b \in B, \quad \exists a \in A \text{ such that } f(a) = b.\]

Equivalently, the image of \(f\) equals the whole codomain: \(\mathrm{Im}(f) = B\). When a function is not surjective, there is at least one element of the codomain that no input maps to.

Surjective and non-surjective

A B
Surjective: every codomain element is reached.
A B ↞ not reached
Not surjective: a codomain element has no preimage.

A surjective function. The function \(f \colon \mathbb{R} \to \mathbb{R},\; f(x) = 2x + 1\) is surjective. Given any \(b \in \mathbb{R}\), the equation \(2a + 1 = b\) has the solution \(a = (b - 1)/2 \in \mathbb{R}\) — so every \(b\) is hit.

Not surjective. The function \(g \colon \mathbb{R} \to \mathbb{R},\; g(x) = x^2\) is not surjective: \(-1\) is in the codomain \(\mathbb{R}\), but no real number squares to \(-1\). The image of \(g\) is \([0, +\infty)\), a strict subset of the codomain. Notice that the codomain matters: the same rule \(x \mapsto x^2\) viewed as \(g \colon \mathbb{R} \to [0, +\infty)\) is surjective.

Bijective function

A function \(f \colon A \to B\) is bijective (or a one-to-one correspondence) if it is both injective and surjective.

Equivalently: every element of the codomain has exactly one preimage in the domain. The "at least one" is surjectivity, the "at most one" is injectivity. A bijection sets up a perfect pairing between the two sets, element by element.

A bijection

A B

Both at once. The function \(f \colon \mathbb{R} \to \mathbb{R},\; f(x) = 2x + 1\) is bijective: it is injective (shown above) and surjective (also shown above).

The identity. The identity function \(\mathrm{id}_A \colon A \to A,\; \mathrm{id}_A(a) = a\) is always bijective. It is injective (different inputs go to themselves, hence to different outputs) and surjective (every \(a\) is the image of itself).

A finite bijection. The function \(f \colon \{1, 2, 3\} \to \{a, b, c\}\) with \(f(1) = b,\; f(2) = c,\; f(3) = a\) is a bijection. The three inputs land in three distinct outputs, and every element of the codomain is hit.

The horizontal line test

For a real-valued function with a graph in the Cartesian plane, injectivity and surjectivity have geometric counterparts. The horizontal line at height \(y = b\) consists of all points whose second coordinate is \(b\).

  • Injective ⇔ every horizontal line meets the graph in at most one point. If a horizontal line met the graph at two points \((a_1, b)\) and \((a_2, b)\) with \(a_1 \neq a_2\), then \(f(a_1) = b = f(a_2)\), so \(f\) would fail to be injective.

  • Surjective ⇔ every horizontal line whose height is in the codomain meets the graph in at least one point. A horizontal line that misses the graph corresponds to a codomain value that no input reaches.

  • Bijective ⇔ every horizontal line whose height is in the codomain meets the graph in exactly one point.

This is the analogue, for the output direction, of the vertical line test from the previous unit (which was about the function being well-defined in the first place).

Reading injectivity off a graph

The squaring function \(g(x) = x^2\) fails the horizontal line test: the horizontal line \(y = 4\) meets the parabola at two distinct points, \((-2, 4)\) and \((2, 4)\). The geometric picture confirms what we already saw algebraically — \(g\) is not injective.

The cube function \(f(x) = x^3\), in contrast, passes the test: every horizontal line meets its graph at exactly one point. So \(f\) is injective (and, viewed as \(\mathbb{R} \to \mathbb{R}\), also surjective — hence bijective).

x y −2 2 2 4 y = 4 (−2, 4) (2, 4)
\(g(x) = x^2\): the line \(y = 4\) hits the graph twice — fails the test, not injective.
x y −2 2 2 4 y = 2 (∛2, 2)
\(f(x) = x^3\): the line \(y = 2\) hits the graph once — and so does every other horizontal line. Injective.

Composition preserves these properties

Let \(f \colon A \to B\) and \(g \colon B \to C\). Then:

  1. If \(f\) and \(g\) are both injective, so is \(g \circ f\).

  2. If \(f\) and \(g\) are both surjective, so is \(g \circ f\).

  3. If \(f\) and \(g\) are both bijective, so is \(g \circ f\).

Proof (injective case)

Suppose \(f\) and \(g\) are injective, and that \((g \circ f)(a_1) = (g \circ f)(a_2)\). Unfolding the composition: \(g(f(a_1)) = g(f(a_2))\). Since \(g\) is injective, \(f(a_1) = f(a_2)\). Since \(f\) is injective, \(a_1 = a_2\). So \(g \circ f\) is injective.

The surjective case is similar: pick any \(c \in C\). Since \(g\) is surjective, there is \(b \in B\) with \(g(b) = c\). Since \(f\) is surjective, there is \(a \in A\) with \(f(a) = b\). Then \((g \circ f)(a) = g(b) = c\). So \(g \circ f\) is surjective.

The bijective case follows by combining the two.

Connection to Computer Science

A function from inputs to outputs is essentially a lookup. An injective function is one without "collisions" — no two inputs map to the same output, which is exactly the property a good hash function tries to approximate (though true hash functions can never be perfectly injective when the input space is larger than the output space). A unique primary key makes the map from records to IDs injective — no two records share an ID — but not surjective, since almost every possible ID value (every unused integer or UUID) points at no record at all. It becomes a bijection only once you shrink the target set to exactly the IDs in use; then the correspondence is perfect and you can "decode" any ID back to its one record.

The codomain matters

Whether a function is surjective depends on its codomain. The rule \(x \mapsto x^2\) is not surjective when viewed as \(\mathbb{R} \to \mathbb{R}\), but the same rule is surjective when viewed as \(\mathbb{R} \to [0, +\infty)\). Two functions with the same domain and the same rule but different codomains are different functions (as we saw in Unit 1), and one can be surjective while the other isn't.

Injectivity, by contrast, does not depend on the codomain — only on the rule and the domain. Restricting or expanding the codomain cannot create collisions between two distinct inputs.

This is why we insisted, when we first defined functions, that the codomain is part of the data of a function and not just a convenience. Properties like surjectivity are codomain-sensitive, so we have to track the codomain to ask whether they hold.

Exercises

Exercise 1

For each function below, decide whether it is injective only, surjective only, bijective (both), or neither.

a)

\(f \colon \mathbb{R} \to \mathbb{R},\; f(x) = x + 7\).

This function is:

b)

\(g \colon \mathbb{R} \to \mathbb{R},\; g(x) = x^2\).

This function is:

c)

\(h \colon [0, +\infty) \to \mathbb{R},\; h(x) = x^2\).

This function is:

d)

\(k \colon [0, +\infty) \to [0, +\infty),\; k(x) = x^2\).

This function is:

Exercise 2

Consider the function \(f \colon \{1, 2, 3\} \to \{a, b, c, d\}\) defined by \(f(1) = b,\; f(2) = a,\; f(3) = c\).

a)

\(f\) is injective.

b)

\(f\) is surjective.

c)

\(f\) is bijective.

Exercise 3

Recall the graphs of the reference functions from Unit 1.

a)

The absolute value function \(f \colon \mathbb{R} \to \mathbb{R},\; f(x) = |x|\).

Apply the horizontal line test. The function is:

b)

The identity function \(\mathrm{id} \colon \mathbb{R} \to \mathbb{R},\; \mathrm{id}(x) = x\).

Apply the horizontal line test. The function is:

c)

A constant function \(c \colon \mathbb{R} \to \mathbb{R},\; c(x) = 5\).

Apply the horizontal line test. The function is:

Exercise 4

Let \(f \colon \mathbb{R} \to \mathbb{R},\; f(x) = 5x - 3\). We claim \(f\) is injective. Fill in the missing steps of the proof. Suppose \(f(a_1) = f(a_2)\). In your answers, write \(a_2\) simply as a2 (no subscript).

a)

Exercise 5

Let \(f \colon A \to B\) and \(g \colon B \to C\). Decide whether each statement is true or false.

a)

If \(f\) and \(g\) are both injective, then \(g \circ f\) is injective.

b)

If \(g \circ f\) is injective, then \(f\) must be injective.

c)

If \(g \circ f\) is surjective, then \(f\) must be surjective.

Summary

  • Injective: different inputs always go to different outputs. \(a_1 \neq a_2 \implies f(a_1) \neq f(a_2)\).

  • Surjective: every codomain element is reached. \(\forall b \in B,\, \exists a \in A : f(a) = b\). Equivalently, \(\mathrm{Im}(f) = B\).

  • Bijective: both injective and surjective. Every codomain element has exactly one preimage.

  • Horizontal line test: injective iff every horizontal line meets the graph in at most one point; surjective iff every horizontal line at a codomain height meets the graph in at least one point; bijective iff exactly one.

  • Composition preserves all three properties: a composition of injective (or surjective, or bijective) functions has the same property.