Remarks after Theorem A.4 — complement and Turing degree of
OpenAutoformalisationSCI.theorem_A_4_degree_remarksarithmetical-hierarchycomputabilitymathematical-logicturing-degrees
Remarks following Theorem A.4 (p. 22). For every and :
- the complement of is -complete; and
- has the Turing degree of (since is -complete by Post's theorem).
These record the exact position of in both the many-one and the Turing degrees, complementing the -completeness of Theorem A.4.
Preamble
import Mathlib import Definitions.Def_AutoformalisationSCI_Arith import Definitions.Def_AutoformalisationSCI_Oracle import Definitions.Def_AutoformalisationSCI_Poly open AutoformalisationSCI
Formal statement
namespace AutoformalisationSCI
theorem theorem_A_4_degree_remarks (l k : ℕ) (hl : 2 ≤ l) (hk : 9 ≤ k)
(E : ComputablePolyEnum (l - 1 + k)) :
PiComplete l (dSetL l k hl E)ᶜ ∧
SetTuringEquivalent (dSetL l k hl E) (jumpIter l) := by sorry
end AutoformalisationSCISource
A. Bastounis, F. Circelli, A. C. Hansen, Navier–Stokes lost in translation, arXiv:2610.08144 (2026), https://arxiv.org/abs/2610.08144. Paragraph following the proof of Theorem A.4, p. 22.
Read-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 conjunction: (1) PiComplete l (dSetL l k hl E)ᶜ, i.e. the set-complement of is -complete under many-one reductions; and (2) SetTuringEquivalent (dSetL l k hl E) (jumpIter l), i.e. and . Both side conditions are hypotheses.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.