§5 Prop. 2: over
ProvedBSS.decisionInNP_of_decisionInPProposition 2 of §5 (p. 25): over . The proof is to run the machine witnessing membership in and ignore the guess.
Formally, a decision problem whose yes-instances are contained in its instance space and which lies in over also lies in over . The containment hypothesis is needed: clause (c) of the definition of quantifies over , and a witness for can only be produced from the behaviour of the -machine at admissible inputs.
import Definitions.Def_BSSFeasibility
namespace BSS
theorem decisionInNP_of_decisionInP (Y Yyes : Set (Rinf ℝ)) (hsub : Yyes ⊆ Y)
(hP : DecisionInP Y Yyes) : DecisionInNP Y Yyes := by sorry
end BSS
Read-back
What the Lean code literally says, in plain math · NON-BLIND: written by the drafting agent (Aristotle, Harmonic), not an independent auditor
⚠️ NON-BLIND READ-BACK — NOT INDEPENDENT TESTIMONY. This read-back was not written by an independent blind auditor. It was written by the same agent that drafted this item's Lean statement, at the explicit instruction of the proposal owner. The author therefore already knew what the statement was intended to say, which is exactly the bias a read-back exists to exclude. Treat this text as the author's own rendering of their own code, not as corroborating evidence, and obtain a genuinely independent audit before relying on it.
Let and be arbitrary subsets of .
Hypotheses. ; and is in , that is, there is a machine over which, on every , halts with output value or , outputs exactly when , and whose halting time on is bounded by for some fixed natural numbers .
Conclusion. is in : there are a machine and natural numbers such that , run on the interleaved pair of an instance and a guess, takes only the values and when it halts at an admissible ; answers only at members of ; and for each answers on at least one guess within steps.
The machine is not required to relate to the -machine in any stated way, only to exist. No restriction is placed on or beyond the containment: they are arbitrary sets of points of , of any cardinality, and need not be definable or measurable.