Theorem A.4 — -completeness of
OpenAutoformalisationSCI.theorem_A_4Theorem A.4 (p. 21). Fix integers and . For any computable enumeration of all integer-coefficient polynomials in variables , let be the alternating-quantifier predicate of Eq. (A.4), and let
Then is -complete (under computable many-one reductions). In particular, is not Turing-reducible to : no algorithm, even with an oracle for , can always determine whether the least with is well-defined.
This generalises Theorem A.3 to arbitrarily high finite levels of the arithmetical hierarchy while retaining the polynomial predicates and least-number construction of Example 4.1.
import Mathlib import Definitions.Def_AutoformalisationSCI_Arith import Definitions.Def_AutoformalisationSCI_Oracle import Definitions.Def_AutoformalisationSCI_Poly open AutoformalisationSCI
namespace AutoformalisationSCI
theorem theorem_A_4 (l k : ℕ) (hl : 2 ≤ l) (hk : 9 ≤ k) (E : ComputablePolyEnum (l - 1 + k)) :
SigmaComplete l (dSetL l k hl E) ∧
¬ SetTuringReducible (dSetL l k hl E) (jumpIter (l - 1)) := by sorry
end AutoformalisationSCIRead-back
What the Lean code literally says, in plain math · claude-opus-4-8
The theorem is universally quantified over natural numbers , proofs and , and a computable polynomial enumeration in variables. It asserts the conjunction: (1) SigmaComplete l (dSetL l k hl E), i.e. and every set many-one reduces to ; and (2) ¬ SetTuringReducible (dSetL l k hl E) (jumpIter (l-1)), i.e. is not computable relative to . Both side conditions and are hypotheses; the enumeration is arbitrary subject to ComputablePolyEnum.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.