Function Composition and Inverses - Discrete Math

SECTION 1

Historical Context & Motivation

The idea of applying one process after another—what we now call function composition—is so fundamental that it predates the modern notion of a function itself. Ancient astronomers chained geometric transformations to predict planetary positions, and medieval algebraists composed arithmetic operations to solve equations. Yet it was not until the seventeenth and eighteenth centuries that mathematicians began to treat functions as first-class objects that could be combined, inverted, and studied in their own right.

The formal framework for inverse functions crystallized alongside the development of group theory and abstract algebra in the nineteenth century, where the notion of an 'undoing' operation became central to understanding symmetry and structure. Today, composition and inversion are indispensable in discrete mathematics: they appear in database query pipelines, compiler passes, encryption–decryption pairs, and the algebraic structures that unify all of these applications.

1694 • Leibniz Introduces 'Function'

Gottfried Wilhelm Leibniz coins the term functio to describe quantities that depend on a variable, laying the linguistic groundwork for treating mappings as objects.

1748 • Euler Formalizes Notation

Leonhard Euler's Introductio in Analysin Infinitorum popularizes the f(x) notation, making it natural to write composed expressions like f(g(x)).

1854 • Cayley and Group Theory

Arthur Cayley publishes foundational work on groups of permutations, where composition of bijections and their inverses become the central operations.

1888 • Dedekind's Set-Theoretic Functions

Richard Dedekind defines functions as mappings between sets, giving composition and inversion their modern set-theoretic formulations used throughout discrete mathematics.

1936 • Church and Lambda Calculus

Alonzo Church develops the lambda calculus, where function composition is the primary computational mechanism, directly influencing functional programming languages.

The central questions these developments address are deceptively simple: given two functions f and g, when and how can we form a new function by chaining them? And under what conditions can we 'undo' a function—that is, find a function f⁻¹ such that composing f with f⁻¹ returns us to where we started? Answering these questions rigorously requires the language of sets, domains, codomains, and the classification of functions as injective, surjective, or bijective.

SECTION 2

Core Principles & Definitions

Before diving into composition and inverses, recall that a function f : A → B is a relation from set A to set B in which every element of A is paired with exactly one element of B. The set A is the domain, B is the codomain, and the subset of B actually hit by f is the range (or image). This precise setup—distinguishing domain, codomain, and range—matters enormously when we compose functions or attempt to invert them.

Function Composition (g ∘ f)

Given f : A → B and g : B → C, the composition g ∘ f : A → C is defined by (g ∘ f)(x) = g(f(x)). The codomain of f must match (or be a subset of) the domain of g.

Injective (One-to-One)

A function f : A → B is injective if f(a₁) = f(a₂) implies a₁ = a₂. No two distinct elements in A map to the same element in B. Injectivity is necessary for a left inverse to exist.

Surjective (Onto)

A function f : A → B is surjective if for every b ∈ B there exists at least one a ∈ A with f(a) = b. The range equals the entire codomain. Surjectivity is necessary for a right inverse to exist.

Bijective (One-to-One and Onto)

A function that is both injective and surjective is bijective. Bijections are precisely the functions that possess a two-sided inverse f⁻¹ : B → A satisfying f⁻¹ ∘ f = id_A and f ∘ f⁻¹ = id_B.

Identity Function (id)

The identity function id_A : A → A maps every element to itself: id_A(a) = a. It serves as the neutral element for composition: f ∘ id_A = f and id_B ∘ f = f.

✦

KEY TAKEAWAY

Think of function composition like an assembly line in a factory: raw material enters machine f, which produces a semi-finished product, and that product immediately enters machine g, which outputs the final result. The order matters—reversing the machines changes the output. An inverse function is like running the assembly line in reverse: if every product is unique (injective) and every possible product actually gets made (surjective), you can trace any final output back to exactly one piece of raw material.

SECTION 3

Visual Explanation — Composition as a Pipeline

The diagram shows three sets A, B, and C with elements mapped by f (cyan arrows) and g (violet arrows). The dashed pink arc represents the composite g ∘ f, which sends each element of A directly to C by first applying f, then g. For example, 1 maps to a under f, then a maps to y under g, so (g ∘ f)(1) = y.

The arrow diagram above illustrates the essence of composition. Each element of A has exactly one arrow under f leading to B, and each element of B has exactly one arrow under g leading to C. The composite g ∘ f is obtained by following both arrows in sequence. Observe that the intermediate set B is 'hidden' in the composite—an external observer sees only the net mapping from A to C. This perspective is critical in software engineering, where intermediate data structures may be optimized away, and in algebra, where composition lets us build complex transformations from simple, well-understood pieces.

⚠

Notation Warning

In g ∘ f, the function on the right (f) is applied first. This right-to-left convention matches how we evaluate g(f(x))—start with the innermost function. Some computer science texts use left-to-right (pipeline) notation: f ; g or f >> g. Always check which convention a given text uses.

SECTION 4

Mathematical Framework

Composition — Formal Definition

COMPOSITION DEFINITION

(g ∘ f)(x) = g(f(x)), for all x ∈ A

where f : A → B and g : B → C. The resulting function g ∘ f has domain A and codomain C.

Composition is associative but generally not commutative. Associativity means that for f : A → B, g : B → C, and h : C → D, we have h ∘ (g ∘ f) = (h ∘ g) ∘ f. This can be verified element-wise: both sides evaluate to h(g(f(x))) for every x ∈ A. Non-commutativity means that g ∘ f and f ∘ g are generally not equal—and in fact, f ∘ g may not even be defined when the domains and codomains do not align.

ASSOCIATIVITY OF COMPOSITION

h ∘ (g ∘ f) = (h ∘ g) ∘ f

for f : A → B, g : B → C, h : C → D. Both sides equal the function x ↦ h(g(f(x))).

Inverse Functions — Formal Definition

INVERSE FUNCTION

f⁻¹ ∘ f = id_A and f ∘ f⁻¹ = id_B

A function f : A → B has a (two-sided) inverse f⁻¹ : B → A if and only if f is bijective. Here id_A and id_B are the identity functions on A and B respectively.

The requirement of bijectivity is not merely a technicality—it is structurally necessary. If f fails to be injective, then two distinct elements a₁ ≠ a₂ satisfy f(a₁) = f(a₂) = b, and there is no well-defined way to assign f⁻¹(b) to a unique preimage. If f fails to be surjective, then some b ∈ B has no preimage, and f⁻¹(b) would be undefined. The left inverse (a function g with g ∘ f = id_A) exists if and only if f is injective, and the right inverse (a function h with f ∘ h = id_B) exists if and only if f is surjective. When both exist, they coincide and equal the unique two-sided inverse.

INVERSE OF A COMPOSITION

(g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹

When both f and g are bijections, the inverse of their composition reverses the order—akin to removing layers in the opposite order they were applied (the 'socks and shoes' rule).

💡

Socks-and-Shoes Principle

To undo putting on socks then shoes, you remove the shoes first, then the socks. Similarly, to invert g ∘ f, you first invert g (undo the last operation), then invert f (undo the first). This principle generalizes: (h ∘ g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹ ∘ h⁻¹.

SECTION 5

Injectivity, Surjectivity, and Invertibility

Understanding when a function can be inverted requires classifying it by how it relates its domain and codomain. The following diagram contrasts the three key properties—injective, surjective, and bijective—using concrete finite-set examples. These properties also interact with composition: composing two injections yields an injection, composing two surjections yields a surjection, and composing two bijections yields a bijection.

Three panels compare an injective function (left, cyan), a surjective function (center, pink), and a bijective function (right, amber). Only the bijective function possesses a two-sided inverse. Note how injectivity guarantees a left inverse and surjectivity guarantees a right inverse; bijectivity combines both properties.

Composition Preserves Injectivity and Surjectivity

Property of f and g	Property of g ∘ f	Proof Sketch
Both injective	Injective	g(f(a₁)) = g(f(a₂)) ⇒ f(a₁) = f(a₂) (g inj.) ⇒ a₁ = a₂ (f inj.)
Both surjective	Surjective	For c ∈ C, ∃ b with g(b)=c (g surj.), ∃ a with f(a)=b (f surj.), so (g∘f)(a)=c.
Both bijective	Bijective	Combines both results above; (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹.
g ∘ f injective	f must be injective	f(a₁)=f(a₂) ⇒ g(f(a₁))=g(f(a₂)) ⇒ a₁=a₂ by injectivity of g∘f.
g ∘ f surjective	g must be surjective	range(g∘f) ⊆ range(g), so if range(g∘f) = C then range(g) = C.

How composition interacts with injectivity and surjectivity

SECTION 6

Worked Example — Composition and Inversion on Finite Sets

Consider the sets A = {1, 2, 3}, B = {a, b, c}, and C = {x, y, z}. Define f : A → B by f(1) = b, f(2) = c, f(3) = a, and define g : B → C by g(a) = z, g(b) = x, g(c) = y. We will compute g ∘ f, verify that both f and g are bijections, find their inverses, and confirm that (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹.

Composition and Inverse on {1,2,3} → {a,b,c} → {x,y,z}

1
Step 1 — Compute g ∘ f

Apply f first, then g to each element of A. (g ∘ f)(1) = g(f(1)) = g(b) = x. (g ∘ f)(2) = g(f(2)) = g(c) = y. (g ∘ f)(3) = g(f(3)) = g(a) = z.

g ∘ f : 1 ↦ x, 2 ↦ y, 3 ↦ z
2
Step 2 — Verify f is bijective

Injective: f(1) = b, f(2) = c, f(3) = a — all images are distinct, so f is one-to-one. Surjective: the range {a, b, c} equals the codomain B, so f is onto. Hence f is bijective.

f is bijective ✓
3
Step 3 — Find f⁻¹

Reverse each pair: f(1) = b ⇒ f⁻¹(b) = 1, f(2) = c ⇒ f⁻¹(c) = 2, f(3) = a ⇒ f⁻¹(a) = 3.

f⁻¹ : a ↦ 3, b ↦ 1, c ↦ 2
4
Step 4 — Find g⁻¹

Similarly: g(a) = z ⇒ g⁻¹(z) = a, g(b) = x ⇒ g⁻¹(x) = b, g(c) = y ⇒ g⁻¹(y) = c.

g⁻¹ : x ↦ b, y ↦ c, z ↦ a
5
Step 5 — Verify (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹

Compute f⁻¹ ∘ g⁻¹ on each element of C. (f⁻¹ ∘ g⁻¹)(x) = f⁻¹(g⁻¹(x)) = f⁻¹(b) = 1. (f⁻¹ ∘ g⁻¹)(y) = f⁻¹(g⁻¹(y)) = f⁻¹(c) = 2. (f⁻¹ ∘ g⁻¹)(z) = f⁻¹(g⁻¹(z)) = f⁻¹(a) = 3. Now check (g ∘ f)⁻¹ by reversing g ∘ f: 1↦x ⇒ x↦1, 2↦y ⇒ y↦2, 3↦z ⇒ z↦3. These match exactly.

(g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹ : x ↦ 1, y ↦ 2, z ↦ 3 ✓

SECTION 7

Strengths, Limitations, and Common Pitfalls

Property / Feature	Composition (g ∘ f)	Inverse (f⁻¹)
When defined	Whenever codomain of f ⊆ domain of g	Only when f is bijective (for two-sided inverse)
Associativity	Always associative: h ∘ (g ∘ f) = (h ∘ g) ∘ f	N/A (single operation, not chained in the same sense)
Commutativity	Generally NOT commutative	Involution: (f⁻¹)⁻¹ = f
Preserves structure	Preserves injectivity, surjectivity, bijectivity	Inverse of a bijection is a bijection
Common pitfall	Confusing g ∘ f with f ∘ g (order matters!)	Attempting to invert non-injective or non-surjective functions
Finite-set computation	O(\|A\|) — evaluate f then g for each element	O(\|A\|) — reverse all pairs in the function table

Comparison of composition and inverse properties

✦

KEY TAKEAWAY

Composition and inversion together give functions an algebraic structure analogous to multiplication and division in arithmetic. Composition builds complexity by chaining; inversion deconstructs it. The identity function plays the role of '1' (the multiplicative identity), and a bijection's inverse plays the role of a reciprocal. This analogy is not merely informal—it is made precise in group theory, where the set of all bijections on a set forms a group under composition, with the identity function as the neutral element and function inverses as group inverses.

SECTION 8

Connections to Advanced Theory

Function composition and inverses serve as the gateway to several advanced mathematical structures. In group theory, the set of all bijections from a set to itself forms the symmetric group Sₙ, where the group operation is composition and every element has an inverse. In category theory, composition of morphisms is the fundamental operation, and isomorphisms are precisely the morphisms with two-sided inverses. In cryptography, encryption and decryption are modeled as a function and its inverse—the security of RSA depends on the computational difficulty of inverting certain one-way functions.

Concept in This Lesson	Advanced Generalization	Where It Appears
Composition g ∘ f	Morphism composition in categories	Category theory, algebraic topology
Identity function id_A	Identity morphism, neutral element of a monoid/group	Abstract algebra, monoid theory
Bijection with inverse	Isomorphism / group element	Group theory (Sₙ), ring isomorphisms
Socks-and-shoes rule	(AB)⁻¹ = B⁻¹A⁻¹ in matrix groups	Linear algebra, Lie groups
Left / right inverse	Section / retraction in category theory	Homotopy theory, homological algebra

From discrete functions to advanced structures

As you continue in discrete mathematics and theoretical computer science, you will encounter these ideas repeatedly. Permutation groups underpin combinatorics and coding theory. The lambda calculus—built entirely on function abstraction and application (composition)—is the theoretical foundation of functional programming languages like Haskell and ML. Understanding composition and inversion at the set-theoretic level gives you the vocabulary and intuition needed to move fluently through these more advanced settings.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Let f : A → B and g : B → C. If g ∘ f is injective, must f be injective? Must g be injective? Justify your answers.

Show answer

Yes, f must be injective. Suppose f(a₁) = f(a₂); then g(f(a₁)) = g(f(a₂)), so (g ∘ f)(a₁) = (g ∘ f)(a₂). Since g ∘ f is injective, a₁ = a₂. However, g need not be injective—it only needs to be injective on the range of f (which is a subset of B). For example, let A = {1}, B = {a, b}, C = {x}, with f(1) = a, g(a) = g(b) = x. Then g ∘ f is trivially injective (only one element in domain), but g is not injective because g(a) = g(b).

Question 2: BASIC CALCULATION

Let A = {1, 2, 3, 4}, and define f : A → A by f(1) = 3, f(2) = 1, f(3) = 4, f(4) = 2. Compute f ∘ f (i.e., f²), and determine f⁻¹.

Show answer

For f ∘ f: (f ∘ f)(1) = f(f(1)) = f(3) = 4; (f ∘ f)(2) = f(f(2)) = f(1) = 3; (f ∘ f)(3) = f(f(3)) = f(4) = 2; (f ∘ f)(4) = f(f(4)) = f(2) = 1. So f² : 1↦4, 2↦3, 3↦2, 4↦1. Since f is a bijection (each element of A appears exactly once in the range), f⁻¹ exists. Reversing pairs: f⁻¹(1) = 2, f⁻¹(2) = 4, f⁻¹(3) = 1, f⁻¹(4) = 3. One can verify f⁻¹ ∘ f = id_A.

Question 3: INTERMEDIATE

Let f : ℤ → ℤ be defined by f(n) = 2n + 1. Show that f is injective but not surjective. Find a left inverse for f and explain why no right inverse exists.

Show answer

Injective: suppose f(n₁) = f(n₂), so 2n₁ + 1 = 2n₂ + 1, giving n₁ = n₂. Surjective fails because f always outputs odd integers; for example, 4 ∈ ℤ is even and has no preimage (2n + 1 = 4 gives n = 3/2 ∉ ℤ). A left inverse g : ℤ → ℤ can be defined by g(m) = (m − 1)/2 when m is odd, and g(m) = 0 (or any fixed integer) when m is even. Then for all n ∈ ℤ, g(f(n)) = g(2n+1) = (2n+1−1)/2 = n, confirming g ∘ f = id_ℤ. No right inverse h : ℤ → ℤ can satisfy f ∘ h = id_ℤ because that would require every integer (including even ones) to be in the range of f, contradicting the fact that f is not surjective.

Question 4: APPLIED

In a simple substitution cipher, each letter of the alphabet is replaced by another via a bijection σ : {A,…,Z} → {A,…,Z}. Encrypting a message is applying σ; decrypting is applying σ⁻¹. Suppose you encrypt a message with σ and then encrypt the result again with another bijection τ. Write the combined encryption as a single function, and express the decryption function. Which letter-substitution do you undo first when decrypting?

Show answer

The combined encryption is the composition τ ∘ σ, which maps each plaintext letter first through σ, then through τ. By the socks-and-shoes rule, the decryption function is (τ ∘ σ)⁻¹ = σ⁻¹ ∘ τ⁻¹. When decrypting, you undo τ first (apply τ⁻¹) and then undo σ (apply σ⁻¹). This mirrors the general principle: the last encryption applied is the first one reversed. This is directly analogous to how composed transformations are inverted in any algebraic or cryptographic system.

Question 5: CRITICAL THINKING

Prove that if f : A → B has both a left inverse g (so g ∘ f = id_A) and a right inverse h (so f ∘ h = id_B), then g = h, and this common function is the unique two-sided inverse of f.

Show answer

Start with the left inverse g and the right inverse h. Consider g = g ∘ id_B = g ∘ (f ∘ h) = (g ∘ f) ∘ h = id_A ∘ h = h, where the third equality uses associativity of composition. So g = h. Now g is both a left and right inverse: g ∘ f = id_A and f ∘ g = f ∘ h = id_B. For uniqueness, suppose g' is another two-sided inverse. Then g' = g' ∘ id_B = g' ∘ (f ∘ g) = (g' ∘ f) ∘ g = id_A ∘ g = g. Therefore the two-sided inverse is unique. This proof relies only on associativity of composition and the identity-function property, illustrating why these structural axioms are so powerful.

SUMMARY

Lesson Summary

Summary

Function composition (g ∘ f)(x) = g(f(x)) chains two functions by feeding the output of f into g, producing a new function whose domain matches f's and whose codomain matches g's. Composition is associative but generally not commutative, and it preserves injectivity, surjectivity, and bijectivity. The identity function id serves as the neutral element for composition.

An inverse function f⁻¹ satisfies f⁻¹ ∘ f = id and f ∘ f⁻¹ = id, and exists if and only if f is a bijection. The socks-and-shoes rule states (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹—invert in reverse order. Left inverses require injectivity, right inverses require surjectivity, and when both exist they are equal and unique. These concepts form the algebraic bedrock of group theory, category theory, and cryptography.