Functions: injective, surjective and bijective

In calculus a function is usually a formula, like \(f(x) = x^2\). In the rest of mathematics a function is something more general and more precise: a rule that assigns to each element of one set exactly one element of another. The sets matter as much as the rule. Squaring is a different function on \(\mathbb{R}\), on \([0, \infty)\) and on \(\mathbb{Z}\), and it has different properties on each. This lesson gives the set-theoretic definition of a function, the three key properties of injectivity, surjectivity and bijectivity, and the theory of composition and inverses that ties them together. Lesson 12 uses bijections to compare the sizes of infinite sets.

The definition

A function \(f\) from a set \(A\) to a set \(B\), written \(f : A \to B\), assigns to each \(a \in A\) exactly one element \(f(a) \in B\). The set \(A\) is the domain and \(B\) is the codomain. The range, or image, is the set of values actually taken, \(f(A) = \{f(a) : a \in A\}\), which is a subset of the codomain and may be smaller.

Formally, a function is identified with its graph, the set of pairs \(\{(a, f(a)) : a \in A\}\), which is a subset of \(A \times B\). A subset \(G \subseteq A \times B\) is the graph of a function exactly when every \(a \in A\) appears as the first coordinate of exactly one pair in \(G\). This is the 'vertical line test' from calculus, made precise: every vertical line through a point of the domain meets the graph exactly once.

Two functions are equal when they have the same domain, the same codomain and the same value at every point. So \(f, g : \mathbb{R} \to \mathbb{R}\) given by \(f(x) = (x + 1)^2\) and \(g(x) = x^2 + 2x + 1\) are equal, even though the formulas look different. And \(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\), is a different function from \(h : \mathbb{R} \to [0, \infty)\), \(h(x) = x^2\), because the codomains differ. This distinction matters for surjectivity.

Something fails to be a function if some element of the domain has no value, or has more than one. The rule '\(f(x) = 1/x\)' does not define a function \(\mathbb{R} \to \mathbb{R}\), because \(f(0)\) is undefined; it does define a function on \(\mathbb{R} \setminus \{0\}\). The rule 'send \(x\) to a number whose square is \(x\)' does not define a function on \([0, \infty)\), because 4 would have to go to both 2 and \(-2\); choosing the non-negative square root fixes this.

Injective functions

A function \(f : A \to B\) is injective, or one-to-one, if different inputs give different outputs: for all \(a_1, a_2 \in A\), \(f(a_1) = f(a_2) \implies a_1 = a_2\). This is the contrapositive of '\(a_1 \ne a_2 \implies f(a_1) \ne f(a_2)\)', and it is the form to use in proofs. To prove that \(f\) is injective, suppose \(f(a_1) = f(a_2)\) and deduce \(a_1 = a_2\). To prove that \(f\) is not injective, find two different inputs with the same output.

For functions on intervals of \(\mathbb{R}\), a strictly increasing or strictly decreasing function is injective, and a differentiable function with \(f\prime(x) > 0\) everywhere is strictly increasing. That gives a calculus test: \(x^3 + x\) is injective on \(\mathbb{R}\) because its derivative \(3x^2 + 1\) is always positive. The definition, however, needs no calculus and works for functions on any sets.

Surjective functions

A function \(f : A \to B\) is surjective, or onto, if every element of the codomain is hit: for every \(b \in B\) there exists \(a \in A\) with \(f(a) = b\). Equivalently, the range equals the codomain. To prove surjectivity, take an arbitrary \(b \in B\) and construct an \(a\), usually by solving \(f(a) = b\) in scratch work, then check that the \(a\) lies in the domain and really works. To disprove it, find one \(b\) that is never hit.

Bijections

A function that is both injective and surjective is bijective, or a bijection, or a one-to-one correspondence. A bijection pairs up the elements of \(A\) and \(B\) perfectly: every element of \(B\) is matched with exactly one element of \(A\). For finite sets, a bijection exists exactly when the sets have the same number of elements, which is what counting means: to count a set of five things is to set up a bijection with \(\{1, 2, 3, 4, 5\}\).

For finite sets of the same size, injective and surjective are equivalent. If \(|A| = |B| = n\) and \(f : A \to B\) is injective, then the \(n\) values \(f(a)\) are distinct, so they fill all of \(B\). This is a form of the pigeonhole principle: if \(|A| > |B|\), no function \(A \to B\) can be injective, so some two elements of \(A\) share an output. Among any 13 people, two have birthdays in the same month. For infinite sets the equivalence fails completely: \(n \mapsto 2n\) from \(\mathbb{N}\) to \(\mathbb{N}\) is injective but not surjective. That failure is the starting point of lesson 12.

Composition

If \(f : A \to B\) and \(g : B \to C\), the composition \(g \circ f : A \to C\) is defined by \((g \circ f)(a) = g(f(a))\): first apply \(f\), then \(g\). Composition is associative, \(h \circ (g \circ f) = (h \circ g) \circ f\), because both sides send \(a\) to \(h(g(f(a)))\). It is not commutative: with \(f(x) = x + 1\) and \(g(x) = x^2\) on \(\mathbb{R}\), \((g \circ f)(x) = (x + 1)^2\) while \((f \circ g)(x) = x^2 + 1\).

Theorem. Let \(f : A \to B\) and \(g : B \to C\). (a) If \(f\) and \(g\) are injective, so is \(g \circ f\). (b) If \(f\) and \(g\) are surjective, so is \(g \circ f\). (c) Hence the composition of bijections is a bijection.

Proof. (a) Suppose \((g \circ f)(a_1) = (g \circ f)(a_2)\), that is \(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\). (b) Let \(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) = c\). (c) follows from (a) and (b). \(\blacksquare\)

There are partial converses: if \(g \circ f\) is injective then \(f\) must be injective, and if \(g \circ f\) is surjective then \(g\) must be surjective. But \(g\) need not be injective in the first case, nor \(f\) surjective in the second. The practice problems ask for proofs and counterexamples.

Inverse functions

The identity function on \(A\), \(\operatorname{id}_A(a) = a\), does nothing. A function \(g : B \to A\) is an inverse of \(f : A \to B\) if \(g \circ f = \operatorname{id}_A\) and \(f \circ g = \operatorname{id}_B\); that is, \(g(f(a)) = a\) for every \(a\) and \(f(g(b)) = b\) for every \(b\). We write \(g = f^{-1}\).

Theorem. A function \(f : A \to B\) has an inverse if and only if it is a bijection. The inverse, when it exists, is unique.

Proof. Suppose \(f\) has an inverse \(g\). If \(f(a_1) = f(a_2)\), apply \(g\) to get \(a_1 = g(f(a_1)) = g(f(a_2)) = a_2\), so \(f\) is injective. For any \(b \in B\), the element \(a = g(b)\) satisfies \(f(a) = f(g(b)) = b\), so \(f\) is surjective. Conversely, suppose \(f\) is a bijection. For each \(b \in B\), surjectivity gives some \(a\) with \(f(a) = b\), and injectivity says it is the only one. Define \(g(b)\) to be that unique \(a\). Then \(f(g(b)) = b\) by construction, and \(g(f(a)) = a\) because \(a\) is the unique preimage of \(f(a)\). For uniqueness, if \(g\) and \(h\) are both inverses then \(g = g \circ \operatorname{id}_B = g \circ (f \circ h) = (g \circ f) \circ h = \operatorname{id}_A \circ h = h\). \(\blacksquare\)

Do not confuse the inverse function \(f^{-1}\) with the reciprocal \(1/f\), and do not confuse it with the preimage. For any function \(f : A \to B\), bijective or not, and any \(S \subseteq B\), the preimage \(f^{-1}(S) = \{a \in A : f(a) \in S\}\) is a subset of \(A\). With \(g(x) = x^2\) on \(\mathbb{R}\), \(g^{-1}(\{4\}) = \{-2, 2\}\) and \(g^{-1}(\{-1\}) = \emptyset\), even though \(g\) has no inverse function.

Images and preimages of sets

Images and preimages interact with set operations in a way that is partly tidy and partly not. For \(f : A \to B\) and subsets \(S, T \subseteq A\) and \(X, Y \subseteq B\): preimages respect everything, \(f^{-1}(X \cup Y) = f^{-1}(X) \cup f^{-1}(Y)\) and \(f^{-1}(X \cap Y) = f^{-1}(X) \cap f^{-1}(Y)\). Images respect unions, \(f(S \cup T) = f(S) \cup f(T)\), but only half of intersections: \(f(S \cap T) \subseteq f(S) \cap f(T)\), with equality when \(f\) is injective. For \(g(x) = x^2\), \(S = \{-1\}\) and \(T = \{1\}\), the left side is \(g(\emptyset) = \emptyset\) while the right side is \(\{1\}\).

Checking properties of finite functions

For functions between finite sets, injectivity and surjectivity can be checked by brute force. The code below represents functions as Python dictionaries, tests the properties, builds an inverse when one exists, verifies the composition theorem on random examples, and counts how many of the \(n^n\) functions on an \(n\)-element set are bijections. The answer, \(n!\), is the number of ways to arrange \(n\) objects in order.

import random
from itertools import product
random.seed(10)

def injective(f):
    return len(set(f.values())) == len(f)

def surjective(f, B):
    return set(f.values()) == set(B)

def inverse(f, B):
    if not (injective(f) and surjective(f, B)):
        return None
    return {b: a for a, b in f.items()}

A = [1, 2, 3, 4]
f = {1: 'c', 2: 'a', 3: 'd', 4: 'b'}
print("f bijective:", injective(f) and surjective(f, 'abcd'), " inverse:", inverse(f, 'abcd'))

# composition of injections is an injection (random tests on sets of size 5)
ok = True
for _ in range(500):
    S = list(range(5))
    f = dict(zip(S, random.sample(S, 5)))
    g = dict(zip(S, random.sample(S, 5)))
    gf = {a: g[f[a]] for a in S}
    ok &= injective(gf)
print("compositions of bijections were bijections:", ok)

for n in range(1, 6):
    D = range(n)
    count = sum(1 for vals in product(D, repeat=n) if len(set(vals)) == n)
    print(f"n={n}: {n**n:5d} functions, {count:4d} bijections")

f bijective: True  inverse: {'c': 1, 'a': 2, 'd': 3, 'b': 4}
compositions of bijections were bijections: True
n=1:     1 functions,    1 bijections
n=2:     4 functions,    2 bijections
n=3:    27 functions,    6 bijections
n=4:   256 functions,   24 bijections
n=5:  3125 functions,  120 bijections