Bijections and Inverse Functions

Bijections are the working definition of "the same size" used throughout mathematics, most explicitly in Finite Sets and Counting, where a bijection between a finite set and $\{1,\dots,n\}$ is the definition of "having $n$ elements," and in the theory of infinite cardinal numbers, where two sets are declared to have equal cardinality exactly when a bijection between them exists (this is how one proves $|\mathbb N| = |\mathbb Z| = |\mathbb Q| < |\mathbb R|$). In algebra, the automorphisms of any structure — bijective structure-preserving self-maps — form a group under Composition of Functions, and permutation groups are literally groups of bijections of a finite set to itself. In analysis, the Inverse Function Theorem gives local conditions under which a differentiable map is a bijection near a point and computes the derivative of the resulting inverse. In cryptography, block ciphers such as AES are, for each fixed key, bijections on the space of possible blocks — this is mathematically forced, since a legitimate recipient must be able to decrypt uniquely. In computer science, hash functions used for perfect hashing and bijective encodings (e.g. Gödel numbering schemes, Cantor pairing functions) rely on explicit bijections between combinatorial structures and $\mathbb{N}$. In statistics and probability, change-of-variables formulas for densities require the transforming map to be a (locally) bijective, differentiable function so that the inverse and its Jacobian are well defined.

Ask the tutor: Why does surjectivity alone require the Axiom of Choice to build a right inverse, while injectivity alone does not need choice for a left inverse?

Think of a function $f : A \to B$ as a machine that assigns to each element of $A$ an arrow pointing into $B$. Two things can go wrong if you try to build a "reverse machine" that sends each output back to where it came from. First, two different inputs might point to the same output — then the reverse machine would not know which one to send you back to. This failure is exactly the failure of injectivity. Second, some element of $B$ might have no arrow pointing at it at all — then the reverse machine has nothing to do when handed that element. This failure is exactly the failure of surjectivity. A bijection is a diagram of arrows with none of these defects: every element of $B$ has exactly one arrow coming in. Reversing every arrow then produces a perfectly well-defined function $B \to A$ — the inverse. This is why the two hypotheses are not redundant with each other: injectivity handles the "too many inputs share an output" problem, surjectivity handles the "some outputs are orphaned" problem, and a genuine reversal needs both problems solved simultaneously.

Example 1 (finite, asymmetric sets — explicit bijection and its inverse). Let $A = \{p, q, r, s\}$ and $B = \{2, 3, 5, 7\}$ (note: $A$ has abstract labels, $B$ has concrete distinct primes — deliberately asymmetric so no hidden relabeling coincidence can mask an error). Define $f : A \to B$ by

Checking injectivity. The four output values $5, 2, 7, 3$ listed for $p,q,r,s$ are pairwise distinct. Hence no two distinct inputs share an output, so $f$ is injective. (Formally: if $f(x_1)=f(x_2)$ with $x_1\ne x_2$ then two of $\{5,2,7,3\}$ would coincide, which is false by inspection of the four values.) Checking surjectivity. $B = \{2,3,5,7\}$ and the range of $f$ is $\{f(p),f(q),f(r),f(s)\} = \{5,2,7,3\} = \{2,3,5,7\} = B$. So every element of $B$ is hit, and $f$ is surjective. Hence $f$ is a bijection. By the theorem, $f$ has a unique two-sided inverse $g = f^{-1} : B \to A$. Following the proof's construction, $g(y)$ is the unique $x$ with $f(x) = y$:

Verification of both identities directly. Compute $g(f(x))$ for each $x \in A$:

So $g \circ f = \mathrm{id}_A$ on all four elements. Compute $f(g(y))$ for each $y \in B$:

So $f \circ g = \mathrm{id}_B$ on all four elements. Both identities hold on every element of the (finite) domains, so $g$ is genuinely a two-sided inverse, confirming the theorem's guarantee.

Example 2 (a bijection between intervals of different lengths, with explicit formula for the inverse). Let $A = [1, 4]$ and $B = [0, 9]$, two closed real intervals of different lengths ($3$ versus $9$ — chosen asymmetrically to avoid the misleading special case of equal-length intervals). Define

(We use the monotone affine map $f(x) = 3x-3$, since a quadratic would not be injective on an interval containing both signs of $x-$vertex; affine maps are automatically injective when the slope is nonzero, which we verify below.) Checking injectivity. Suppose $f(x_1) = f(x_2)$, i.e. $3x_1 - 3 = 3x_2 - 3$. Adding $3$ to both sides gives $3x_1 = 3x_2$, and dividing by $3$ (nonzero) gives $x_1 = x_2$. So $f$ is injective on all of $\mathbb{R}$, in particular on $[1,4]$. Checking that $f$ maps $[1,4]$ into $[0,9]$. $f$ is increasing (slope $3>0$), so its minimum and maximum on $[1,4]$ occur at the endpoints: $f(1) = 3(1)-3 = 0$ and $f(4) = 3(4) - 3 = 9$. Since $f$ is continuous and strictly increasing, $f([1,4]) = [f(1),f(4)] = [0,9]$ (this uses the Intermediate Value Theorem to guarantee every value between $0$ and $9$ is attained, plus monotonicity to guarantee no value is skipped or repeated). Checking surjectivity onto $B=[0,9]$. We just showed $f([1,4]) = [0,9] = B$ exactly, so every element of $B$ is attained: $f$ is surjective onto $B$. Hence $f : [1,4] \to [0,9]$ is a bijection. Solve $y = 3x - 3$ for $x$:

So define $g(y) = \dfrac{y}{3} + 1$ for $y \in [0,9]$. Check $g$ maps $[0,9]$ into $[1,4]$: $g(0) = 1$, $g(9) = 4$, and $g$ is increasing, so $g([0,9]) = [1,4]$, matching the domain $A$. Verify both composite identities symbolically (not just at endpoints). For $x \in [1,4]$:

For $y \in [0,9]$:

Both identities hold for every point in the respective domains (not merely at a few sample points), confirming $g = f^{-1}$ rigorously. Note the inverse of a bijection between intervals of different lengths ($3$ vs. $9$) still exists and is affine — bijectivity does not require any relation between the "sizes" as measured by length, only the exact correspondence described in the definition.