Theorem A.3 — -completeness of
OpenAutoformalisationSCI.theorem_A_3Theorem A.3 (p. 19). Fix an integer . For any computable enumeration of all integer-coefficient polynomials in variables, let be the predicate that for every , and let
Then is -complete (under computable many-one reductions). In particular, is not Turing-reducible to the halting problem : no algorithm, even with an oracle for the halting problem, can always determine whether the least number of Example 4.1 is well-defined.
This is the base case of the paper's hierarchy of presupposition-resolution problems and the precise form of the claim that resolving the ambiguity in Example 4.1 is harder than the halting problem.
import Mathlib import Definitions.Def_AutoformalisationSCI_Arith import Definitions.Def_AutoformalisationSCI_Oracle import Definitions.Def_AutoformalisationSCI_Poly open AutoformalisationSCI
namespace AutoformalisationSCI
theorem theorem_A_3 (k : ℕ) (hk : 9 ≤ k) (E : ComputablePolyEnum (k + 1)) :
SigmaComplete 2 (dSet k E) ∧ ¬ SetTuringReducible (dSet k E) (jumpIter 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 a natural number , a proof that , and a computable polynomial enumeration in variables. It asserts the conjunction of two statements about the set built from : (1) SigmaComplete 2 d, i.e. and every set many-one reduces to ; and (2) ¬ SetTuringReducible d (jumpIter 1), i.e. the characteristic function of is not computable relative to the oracle (the halting problem). The hypothesis is required; the enumeration is arbitrary (only the computability/surjectivity packaged in ComputablePolyEnum is assumed).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.