Composition and Inverse Mappings

Part 15, Chapter 15: Mappings and Permutations

Learning objectives

Compute the composition of two mappings
Identify injective (one-to-one) mappings
Identify surjective (onto) mappings
Determine if a mapping is bijective

Mappings get interesting when you start combining them. Composition lets you chain two mappings into a third; the identity mapping is the "do nothing" rule; inverse mappings undo each other. With those three ingredients, plus the three labels injective / surjective / bijective, you have the entire vocabulary that linear algebra, group theory, and topology will demand of you for the next several years.

Composition

Given mappings $f: A \to B$ and $g: B \to C$ , the composition $g \circ f: A \to C$ is defined by

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

Read right to left: apply $f$ first, then $g$ . The notation looks odd until you realise it matches the order in which you actually evaluate. If $f(x) = 2x + 1$ and $g(x) = x^2$ , then $(g \circ f)(3) = g(f(3)) = g(7) = 49$ .

Associative, but not commutative

Composition is associative: $h \circ (g \circ f) = (h \circ g) \circ f$ . So you can drop the brackets, $h \circ g \circ f$ is unambiguous.

Composition is not commutative: in general $f \circ g \neq g \circ f$ . With the same $f$ and $g$ as above, $(f \circ g)(x) = f(g(x)) = f(x^2) = 2x^2 + 1$ , which is not the same as $(g \circ f)(x) = (2x + 1)^2 = 4x^2 + 4x + 1$ . Order matters.

The three labels

A mapping $f: A \to B$ is

injective (one-to-one) if different inputs give different outputs: $f(a_1) = f(a_2) \implies a_1 = a_2$ .
surjective (onto) if every element of $B$ is hit: for every $b \in B$ there is some $a \in A$ with $f(a) = b$ .
bijective if it is both injective and surjective.

Examples on $\mathbb{R} \to \mathbb{R}$ : $f(x) = x^2$ is neither (not injective: $f(-1) = f(1)$ ; not surjective: nothing hits $-1$ ). $f(x) = x^3$ is bijective. $f(x) = e^x$ is injective but not surjective (codomain is all of $\mathbb{R}$ but the image is $(0, \infty)$ ).

Identity and inverse

The identity mapping $\text{id}_A: A \to A$ A:AtoA sends every element to itself: $\text{id}_A(x) = x$ A(x)=x. It is the neutral element of composition: $f \circ \text{id}_A = f$ A=f and $\text{id}_B \circ f = f$ Bcircf=f.

A bijection $f: A \to B$ has an inverse mapping $f^{-1}: B \to A$ uniquely determined by $f^{-1}(b) = a \iff f(a) = b$ . The defining identities are

$f^{-1} \circ f = \text{id}_A, \quad f \circ f^{-1} = \text{id}_B.$

To find $f^{-1}$ for $f(x) = \frac{2x + 3}{5}$ : set $y = \frac{2x + 3}{5}$ , solve for $x$ : $x = \frac{5y - 3}{2}$ , so $f^{-1}(x) = \frac{5x - 3}{2}$ .

Where this shows up

Programming: Function composition in JavaScript or Python (f(g(x))) is exactly this section's composition; lodash.flow([g, f]) is a library helper for it, and the order matters, $f \circ g \neq g \circ f$ in general.
Type Theory: An injective function is the proof that a "subtype" embeds into a "supertype"; a surjective function is a "quotient" or "coverage"; bijection is type-isomorphism. Modern type-system design uses these three concepts daily.
Databases: Inner joins correspond to injective mappings (no row matched twice); a LEFT JOIN that fills nulls corresponds to a partial mapping. Schema-design correctness checks reduce to mapping properties.

(Pick "bijection" from the dropdown, then alter one arrow to break it. Failing elements glow red (two x's sharing a y) or grey (a y with no preimage). The bottom of the widget tells you whether the current mapping is injective, surjective, and/or bijective.)

The pigeonhole principle

For finite sets of the same size, the three labels collapse. If $|A| = |B|$ and $f: A \to B$ is a mapping, then injective, surjective, and bijective are equivalent. The reason is the pigeonhole principle: if $n$ arrows leave $A$ and land in a set of size $n$ , then no doubling-up forces no skipping, and vice versa. For infinite sets, this fails, $f: \mathbb{N} \to \mathbb{N}$ , $f(n) = 2n$ is injective but not surjective.

Try it

Let $f(x) = x + 3$ and $g(x) = 2x$ . Compute $(f \circ g)(x)$ and $(g \circ f)(x)$ and confirm they differ.
Is $f: \mathbb{R} \to \mathbb{R}$ , $f(x) = x^3 - x$ , injective? (Hint: check $f(0)$ and $f(1)$ .)
Find the inverse of $f(x) = 3x - 7$ and verify $f \circ f^{-1} = \text{id}$ by composing.

Pause: if $f$ is injective but not surjective, can it still have a "left inverse", a mapping $g$ with $g \circ f = \text{id}$ ? Try to construct one for $f(x) = e^x$ .

A trap to watch for

Students compose $g \circ f$ and apply $g$ first because $g$ appears on the left. This is the wrong reading. The notation $(g \circ f)(x) = g(f(x))$ requires applying $f$ first, because $f$ is what touches $x$ inside the parentheses. Reading right-to-left feels strange at first; the convention exists because the input enters on the right and travels leftward through the chain of functions. Whenever you see $\sigma \circ \tau$ in the next section on permutations, the same right-to-left reading applies, $\tau$ acts first, then $\sigma$ .

What you now know

You can compose two mappings in the correct order, classify a mapping as injective / surjective / bijective, find the inverse of a bijection by solving for the input, and apply the pigeonhole principle to mappings between finite sets of equal size. The next section specialises this entire toolbox to a single beautiful case, permutations, the bijections of a finite set to itself, and shows you that they form a group under composition.

Quick check

Mark section complete →

References

Lang, S. (1971). Basic Mathematics. Springer. Chapter 14 §2, composition, identity, inverse, and the three classification labels.
Rudin, W. (1976). Principles of Mathematical Analysis, 3rd ed. McGraw-Hill. Chapter 2: bijections and inverse mappings in the analysis setting.
Halmos, P. (1974). Naive Set Theory. Springer. Sections 7–9, functions, composition, and inverse mappings between abstract sets.