The <Church-Rosser theorem> states that if $M\twoheadrightarrow_\beta N_1$ and $M\twoheadrightarrow_\beta N_2$, then there is a term $P$ with $N_1\twoheadrightarrow_\beta P$ and $N_2\twoheadrightarrow_\beta P$. Equivalently, beta reduction is confluent.

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 120 / 2 / a / Solution

No. Let $c_0=\lambda f.\lambda x.x$ and set
$$
R=\lambda n.c_0,
\qquad
S=\lambda n.n\,(\lambda x.c_0)\,c_0.
$$
Both terms send every <Church numeral> to $c_0$, so both define the constant-zero function. They are distinct beta-normal forms, however, and the <Church-Rosser theorem> implies that distinct beta-normal forms cannot be beta-equivalent.

Solved by gpt-5.6-sol high.

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 120 / 2 / d / Solution

{c}
{wiki}

If a lambda term beta-reduces to both $M$ and $N$, then $M$ and $N$ beta-reduce to a common term. Consequently two beta-equivalent beta-normal forms are alpha-equivalent.


Codex @codex  0

 Incoming links: Church-Rosser theorem