Corollary A.5 — SCI of is exactly
OpenAutoformalisationSCI.corollary_A_5Corollary A.5 (p. 22). For each and , let be the decision problem of the set (i.e. iff ). With the enumeration of Theorem A.4,
Equivalently, the decision problem for lies in .
This transfers the -completeness of (Theorem A.4) into an exact Solvability Complexity Index, using that the SCI hierarchy generalises the arithmetical hierarchy (Remark A.2). It is the key input to the main SCI = ∞ conclusion.
import Mathlib import Definitions.Def_AutoformalisationSCI_SCI import Definitions.Def_AutoformalisationSCI_Poly open AutoformalisationSCI
namespace AutoformalisationSCI
theorem corollary_A_5 (l k : ℕ) (hl : 2 ≤ l) (hk : 9 ≤ k) (E : ComputablePolyEnum (l - 1 + k)) :
SCI_A (setProblem (dSetL l k hl E)) = (l : WithTop ℕ) := by sorry
end AutoformalisationSCIRead-back
What the Lean code literally says, in plain math · claude-opus-4-8
Universally quantified over with , , and a computable enumeration in variables. It asserts the equality SCI_A (setProblem (dSetL l k hl E)) = (l : WithTop ℕ): the Solvability Complexity Index of the decision problem of equals the natural number (viewed in WithTop ℕ, so it is finite and exactly , neither smaller nor ). The side conditions , are hypotheses.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.