The explicit priority construction meets every diagonal requirement
ProvedFriedbergMuchnik.priority_requirements_metcomputability-theoryfriedberg-muchnikpriority-construction
Let be the two sets produced by the fixed priority construction. For every side and every oracle program , there is an input such that
Here is the total membership oracle of . The notation includes both divergence and convergence to any nonzero natural number. In either alternative, the program fails to compute the characteristic function of at .
This is a property of the explicitly defined construction, quantified over all its programs. It assumes neither that a pair of incomparable sets already exists nor that the priority requirements have been satisfied.
Preamble
import Definitions.Def_FriedbergMuchnik_Priority
Formal statement
namespace FriedbergMuchnik
theorem priority_requirements_met (i : Bool) (c : Program) :
∃ x : ℕ,
(x ∈ limitSet (!i) ∧
0 ∈ oracleEval (Computability.setOracle (limitSet i)) c x) ∨
(x ∉ limitSet (!i) ∧
0 ∉ oracleEval (Computability.setOracle (limitSet i)) c x) := by sorry
end FriedbergMuchnik
Source
Arnold W. Miller, Lecture notes in Recursion Theory, December 3, 2008, Section 26, Theorem 26.2, pp. 51–54, https://people.math.wisc.edu/~awmille1/old/m773-07/recthy.pdf#page=51, pp. 53–54, Verification claim and its two permanent-follower outcomes (a) and (b). This statement records the resulting pointwise diagonal witness for FriedbergMuchnik.priorityStage.