Composition & Inverse Functions

Composition: machines in a pipeline

Take $f : A \to B$ and $g : B \to C$. The output of $f$ is a legal input for $g$, so chain them: feed $x$ into $f$, then feed $f(x)$ into $g$. The result is the composition $g \circ f$, defined by

$(g \circ f)(x) = g(f(x)).$

It's a single function $A \to C$ — the whole pipeline collapsed into one machine.

Now the bomb everyone steps on — and I mean everyone, without exception, at least once: $g \circ f$ means "$f$ first, then $g$", even though $g$ is written first. The notation reads right-to-left because $f$ is the inner function — it touches $x$ first. Read $g \circ f$ as "$g$ after $f$". Get this backwards and every composition problem you ever do comes out wrong. The inner function fires first; the notation is deliberately counterintuitive, so train the damn reflex now, before it bites you in the eigenvalue lesson.

For the chain to be legal, the codomain of $f$ must match (or sit inside) the domain of $g$ — the pipe fittings have to connect. Output type of stage one = input type of stage two.

Associative yes, commutative almost never

Composition has one nice algebraic law and one infamous missing one.

Associative: stacking three machines, it doesn't matter how you group the bolting: $(h \circ g) \circ f = h \circ (g \circ f).$ Both sides are just "$f$, then $g$, then $h$" — the pipeline is the pipeline regardless of which joint you mentally assemble first. So we drop parentheses and write $h \circ g \circ f$.

Commutative? Almost never. In general $g \circ f \ne f \circ g.$ Order matters, and this is your first sighting of noncommutativity — a property that will dominate the matrix stratum like a goddamn tyrant. Concrete proof: let $f(x) = x + 1$ and $g(x) = x^2$ on $\mathbb{R}$. Then $(g \circ f)(x) = g(x+1) = (x+1)^2, \qquad (f \circ g)(x) = f(x^2) = x^2 + 1.$ At $x = 1$: $(g \circ f)(1) = 4$ but $(f \circ g)(1) = 2$. Different functions. "Square then add one" is not "add one then square" — obviously, once you see it, and yet people assume composition commutes constantly. It does not. Burn that in: the order of operations is part of the operation.

Composition preserves injectivity and surjectivity — with proof

Good news: the nice properties survive the pipeline. Let $f : A \to B$ and $g : B \to C$.

Theorem (injectivity). If $f$ and $g$ are both injective, so is $g \circ f$. Proof. Assume $(g \circ f)(a) = (g \circ f)(b)$, i.e. $g(f(a)) = g(f(b))$. Since $g$ is injective, equal $g$-outputs force equal inputs: $f(a) = f(b)$. Since $f$ is injective, this forces $a = b$. So $g \circ f$ is injective. $\blacksquare$ (Peel the machines off one at a time, outermost first.)

Theorem (surjectivity). If $f$ and $g$ are both surjective, so is $g \circ f$. Proof. Take an arbitrary $c \in C$. Since $g$ is surjective, there's a $b \in B$ with $g(b) = c$. Since $f$ is surjective, there's an $a \in A$ with $f(a) = b$. Then $(g \circ f)(a) = g(f(a)) = g(b) = c$. So every $c$ has a preimage — surjective. $\blacksquare$

Corollary. The composition of two bijections is a bijection. (Both halves survive.) This is exactly why "same size" will be an equivalence relation in the cardinality lesson — bijections compose.

The identity function: the "1" of composition

Every set $A$ has a do-nothing machine — beautiful in its absolute boredom — the identity function $\operatorname{id}_A : A \to A$ defined by $\operatorname{id}_A(x) = x$ — input comes out untouched. It's the multiplicative-$1$ of the composition world: bolting it on changes nothing. $f \circ \operatorname{id}_A = f, \qquad \operatorname{id}_B \circ f = f \quad \text{for } f : A \to B.$ Keep $\operatorname{id}$ in mind — it's the yardstick that defines what an inverse is, and it will show up in proofs constantly from here to the end of this course.

Inverses: running the machine backwards

Now the climax. A function $f : A \to B$ has an inverse $f^{-1} : B \to A$ if running $f$ then $f^{-1}$ (and vice versa) gets you back where you started:

$f^{-1} \circ f = \operatorname{id}_A \qquad \text{and} \qquad f \circ f^{-1} = \operatorname{id}_B.$

$f^{-1}$ undoes $f$: whatever $f$ did to $x$, $f^{-1}$ reverses it. And here is the theorem that ties the whole stratum together:

$f$ has an inverse if and only if $f$ is a bijection.

Let me show you why, because it's the payoff of the last two lessons. For $f^{-1}$ to be a well-defined function that undoes $f$:

• $f$ must be injective, or undoing is ambiguous. If $f(a) = f(a') = b$ with $a \ne a'$, then $f^{-1}(b)$ wouldn't know whether to return $a$ or $a'$ — single-valuedness of $f^{-1}$ dies. No collisions allowed.
• $f$ must be surjective, or $f^{-1}$ isn't total. If some $b \in B$ is never an output of $f$, then $f^{-1}(b)$ has nothing to return — undefined. No orphans allowed.

No collisions and no orphans is exactly bijective. So bijection $\iff$ invertible. The injective/surjective/bijective machinery from last lesson wasn't bookkeeping — it was the precise diagnosis of which machines can be run backwards, and you've just collected the payoff. This is what rigor buys you: surprising connections that aren't surprising at all once you've defined everything correctly.

Finding $f^{-1}$ in practice: solve $y = f(x)$ for $x$. For $f(x) = 3x + 1$ (which we proved bijective): $y = 3x + 1 \implies x = \tfrac{y - 1}{3}$, so $f^{-1}(y) = \tfrac{y-1}{3}$. (That's the very expression the surjectivity proof coughed up last lesson — no accident.) Check it: $f^{-1}(f(x)) = \tfrac{(3x+1) - 1}{3} = \tfrac{3x}{3} = x = \operatorname{id}(x)$. ✓ The machine, run backwards, lands you home. And inverses of bijections are themselves bijections — file that away, it makes "same cardinality" symmetric in the boss fight ahead.