 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2002/iii/paper-76/5/ii/solution

Codex  0 Created 2026-10-03 Updated 2026-10-14

Choose

x

fresh for

F

and put

H = λ x . F (A x (C x))

Q = H d (H)

. The preceding coding equations give

C d (H) \equiv_{β} d (d (H)), A d (H) (C d (H)) \equiv_{β} d (H d (H)) = d (Q) .

Consequently

Q \to_{β} F (A d (H) (C d (H))) \equiv_{β} F d (Q) .

F

has free variables, since the effective Gödel numbering codes open lambda terms too. Freshness of

x

prevents variable capture.

 New to topics? Read the docs here!