Page 58 - Textos de Matemática Vol. 38

50 PETER KOEPKE
2.4 The G¨odel pairing function
Definition 2.16. Define a well-ordering ≺ on Ord × Ord by
(γ, δ) ≺ (γ′, δ′) iff max(γ, δ) < max(γ′, δ′) ∨
(max(γ, δ) = max(γ′, δ′) ∧ γ < γ′) ∨
(max(γ, δ) = max(γ′, δ′) ∧ γ = γ′ ∧ δ < δ′). Exercise 7. Show that ≺ is a set-like well-ordering of Ord × Ord. Set-like means that
∀γ′, δ′{(γ, δ)|(γ, δ) ≺ (γ′, δ′)} is a set.
Definition 2.17. Define a function G−1 : Ord → Ord × Ord recursively by
G−1(α) = the ≺ -minimal element of Ord × Ord \{G−1(β)|β < α}. Theorem 2.18. G−1 : (Ord, <) → (Ord × Ord, ≺) is an order-isomorphism. Proof. G−1(α) is defined for every α ∈ Ord since ≺ is set-like and so
Ord × Ord \{G−1(β)|β < α} ̸= ∅.
The definition of G−1(α) immediately implies that G−1 is injective. For the surjectivity assume the contrary and let (γ′, δ′) be ≺-minimal such that (γ′, δ′) ̸∈ range(G−1). {(γ, δ)|(γ, δ) ≺ (γ′, δ′)} is a set. By the replacement axiom choose an ordinal α such that
∀(γ, δ) ≺ (γ′, δ′)∃β < αG−1(β) = (γ, δ).
But then the recursive definition of G−1 will imply that G−1(α) = (γ′,δ′). Contradiction.
The recursive definition also implies directly that β < α ↔ G−1(β) ≺ G−1(α).
Exercise 8. Compute G−1(n) for n = 1, . . . , 6. What is G−1(ω)?

Definition 2.19. Let G be the inverse of the function G−1. G : Ord × Ord ↔ Ord is called the Go¨del pairing function for ordinals. Let G0 and G1 the components of G−1, i.e.,
∀αG(G0(α),G1(α)) = α. 3 Register machines
There are many equivalent machine models for defining the class of in- tuitively computable sets. We base our presentation on the unlimited register machine presented in [2].