Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2007/iii/paper-87/3/b/solution
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 87 3 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Choose mutually inverse maps and . This is an extensional reflexive object in the Cartesian closed category. Define its application morphismFor endomorphisms , application in the underlying set is .
It is useful to define term interpretation uniformly over any context object . An environment assigns each free variable a morphism . Variables are interpreted by their assigned maps, and application is interpreted by and pairing. For lambda abstraction, lift the old environment along , interpret the new variable by , and let interpret the body. Then setTaking gives interpretations in the requested set of endomorphisms. Other context objects are needed in the recursive definition to handle bound variables correctly.
The beta reduction rule follows from and the evaluation identity for currying. Applying the interpreted abstraction to a map givesInduction on terms identifies this with interpretation of the capture-avoiding substitution of the argument for .
For eta conversion, suppose is not free in and write for the interpretation of . The body on is the uncurried form of . HenceThus beta-eta-equivalent terms have equal interpretations in . The full isomorphism, rather than just a retract of the function object, provides the inverse law used in the eta step.
New to topics? Read the docs here!