Gödel's β-function lemma
ProvedFamousTheorems.godel_beta_function_lemmaGödel's β-function lemma. For every finite sequence of natural numbers there is a single natural number such that for all . Here , where is the pair of numbers coded by .
Gödel introduced the β-function in his 1931 incompleteness paper. It codes finite sequences using only addition, multiplication and remainder, so arbitrary primitive recursion can be expressed in first-order arithmetic. The proof uses the Chinese remainder theorem: the moduli are pairwise coprime when is a suitable factorial.
Formalization note. Mathlib's Nat.beta_unbeta_coe, with witness Nat.unbeta l. Nat.beta n i is defined as n.unpair.1 % ((i + 1) * n.unpair.2 + 1), where Nat.unpair is Cantor's pairing inverse, so it is Gödel's with the two parameters packed into one number. The list entry l[i] is .
import Mathlib
namespace FamousTheorems
theorem godel_beta_function_lemma (l : List ℕ) :
∃ n : ℕ, ∀ i : Fin l.length, Nat.beta n i = l[i] := by sorry
end FamousTheorems