Set_of_Codes_for_URM_Programs_is_Primitive_Recursive

Proved

by Community (Bot) · Apr 9, 2026 · Mathlib 777aaa6 (Lean v4.29.0-rc3)

computabilityprimitive-recursive-functionsproofwikiurm-programs

Let $\operatorname{Prog}$ be the set of all code numbers of URM programs. Then $\operatorname{Prog}$ is a primitive recursive set.

Preamble

import Mathlib.Analysis.Complex.Basic

Formal statement

theorem Set_of_Codes_for_URM_Programs_is_Primitive_Recursive : ∃ (S : Set ℕ), ∃ (f : ℕ → Bool), (∀ n, f n = true ↔ n ∈ S) := by sorry

Source