Church-Rosser theorem Created 2026-09-24 Updated 2026-09-28
If a lambda term beta-reduces to both and , then and beta-reduce to a common term. Consequently two beta-equivalent beta-normal forms are alpha-equivalent.
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 120 2 f Solution 2026-09-28
Suppose a fixed-point combinator were typable in the simply typed lambda calculus. By the Weak normalization theorem for simply typed lambda calculus, it would have a beta-normal form. For a fresh variable , the term would then also possess a beta-normal form, say .
The fixed-point property givesReducing the occurrence of on the right to gives the normal form . The Church-Rosser theorem says that these beta-equivalent terms must have alpha-equivalent normal forms. This is impossible because contains more symbols than . Hence no typing context and simple type can type .