Composition

Builds on

Required prerequisites, all the way down: 7

You will learn to

• Compute composites g ∘ f of functions given by formulas, tables and arrow diagrams, and determine when g ∘ f is defined.
• Show by example that g ∘ f and f ∘ g can differ, and prove that composition is associative with identity functions as two-sided units.
• Prove that composites of injections, surjections and bijections are injections, surjections and bijections, and that (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹.
• Explain why sets with functions, composition and identity functions satisfy the axioms that later define a category.

Definition

• For f : A → B and g : B → C, the composite g ∘ f : A → C is defined by (g ∘ f)(a) = g(f(a)).
• The identity function id_A : A → A is defined by id_A(a) = a.
• f : A → B has an inverse if there is g : B → A with g ∘ f = id_A and f ∘ g = id_B.

Theorem

• Associativity: h ∘ (g ∘ f) = (h ∘ g) ∘ f whenever the composites are defined.
• Identity laws: f ∘ id_A = f = id_B ∘ f for every f : A → B.
• Composites of injective (surjective, bijective) functions are injective (surjective, bijective).
• If g ∘ f is injective then f is injective; if g ∘ f is surjective then g is surjective.
• (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹ when f and g are bijections.

Common misconceptions

• Reading g ∘ f as 'do g first'; in g ∘ f, the function f is applied first.
• Assuming composition is commutative.
• Thinking that g ∘ f injective forces g to be injective; it forces only f to be injective.
• Composing functions whose codomain and domain do not match.

Leads to

Optional discoveries

• Categories Sets and functions, with composition and identity functions, are the motivating example of a category: the category Set.Wonder Trail →
• Functors A functor sends objects to objects and arrows to arrows, preserving composition and identities.Wonder Trail →
• ∞-categories In an ∞-category, composites exist and are unique only up to a contractible space of choices, so associativity holds up to coherent homotopy rather than strictly.Wonder Trail →
• Universal properties Universal properties describe objects by how arrows compose with them; for example, a product is characterised by the maps into it.Wonder Trail →
• Algebraic structures: monoids, groups and rings The functions from a set to itself form a monoid under composition, and the bijections form a group.
• ← Doing and undoing
• ← One thing after another
• ← Function machines in sequence
• ← Functions and their graphs (precalculus)

Learning pathways

• Accelerated secondary progression
• Adult beginner pathway

Further reading

• F. William Lawvere and Stephen H. Schanuel, Conceptual Mathematics: A First Introduction to Categories (1997)
• Eugenia Cheng, The Joy of Abstraction (2022)