Arithmetical hierarchy and many-one completeness
DefinitionAutoformalisationSCI_ArithThis file defines the arithmetical hierarchy for predicates on the natural numbers and the associated completeness notions, following the standard presentation (Soare, Turing Computability, Ch. 4).
For and a predicate on :
- is the class of computable (decidable) predicates.
- consists of the predicates obtained by projecting a predicate along one extra natural-number coordinate: iff there is a predicate with and , where is a fixed computable pairing of with .
- is the class of complements of predicates, and .
A set is -complete if and every set is many-one reducible to (a total computable with ); -complete is defined analogously. These are the completeness notions used in Theorems A.3 and A.4.
Formalization Note. Many-one reducibility is Mathlib's ManyOneReducible (≤₀). The extra quantified variable is encoded with Nat.pair, a computable bijection , so the classes are the usual arithmetical classes.
import Mathlib.Computability.RE
import Mathlib.Computability.Reduce
open Encodable
namespace AutoformalisationSCI
def ArithSigma : ℕ → (ℕ → Prop) → Prop
| 0, p => ComputablePred p
| n + 1, p => ∃ q : ℕ → Prop, ArithSigma n (fun a => ¬ q a) ∧ ∀ a, p a ↔ ∃ b, q (Nat.pair a b)
def ArithPi (n : ℕ) (p : ℕ → Prop) : Prop := ArithSigma n (fun a => ¬ p a)
def ArithDelta (n : ℕ) (p : ℕ → Prop) : Prop := ArithSigma n p ∧ ArithPi n p
def SigmaComplete (n : ℕ) (A : Set ℕ) : Prop :=
ArithSigma n (fun a => a ∈ A) ∧
∀ C : Set ℕ, ArithSigma n (fun a => a ∈ C) → (fun a => a ∈ C) ≤₀ (fun a => a ∈ A)
def PiComplete (n : ℕ) (A : Set ℕ) : Prop :=
ArithPi n (fun a => a ∈ A) ∧
∀ C : Set ℕ, ArithPi n (fun a => a ∈ C) → (fun a => a ∈ C) ≤₀ (fun a => a ∈ A)
end AutoformalisationSCIRead-back
What the Lean code literally says, in plain math · claude-opus-4-8
The declaration ArithSigma is a function of a natural number and a predicate , defined by recursion on . At it asserts ComputablePred p, i.e. that has a decidable instance whose decision function is computable. At it asserts the existence of a predicate such that (i) ArithSigma n (fun a => ¬ q a) holds, and (ii) for every , is equivalent to the existence of with . ArithPi n p is defined as ArithSigma n (fun a => ¬ p a). ArithDelta n p is the conjunction ArithSigma n p ∧ ArithPi n p. SigmaComplete n A (for a set of naturals) is the conjunction of ArithSigma n (· ∈ A) and the statement that for every set of naturals with ArithSigma n (· ∈ C), the predicate is many-one reducible (≤₀) to . PiComplete n A is the same with ArithPi in place of ArithSigma. No side conditions on or are imposed; and are allowed.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.