Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The explicit priority construction meets every diagonal requirement

Proved
FriedbergMuchnik.priority_requirements_met

by tomasz · Sep 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

computability-theoryfriedberg-muchnikpriority-construction

Let Ai=⋃sLi,sA_i=\bigcup_s L_{i,s}Ai​=⋃s​Li,s​ be the two sets produced by the fixed priority construction. For every side i∈{0,1}i\in\{0,1\}i∈{0,1} and every oracle program ccc, there is an input x∈Nx\in\mathbb Nx∈N such that

(x∈A1−i ∧ eval⁡χAi(c,x)↓=0)∨(x∉A1−i ∧ eval⁡χAi(c,x)↓̸=0).\bigl(x\in A_{1-i}\ \land\ \operatorname{eval}^{\chi_{A_i}}(c,x)\downarrow=0\bigr)\quad\lor\quad\bigl(x\notin A_{1-i}\ \land\ \operatorname{eval}^{\chi_{A_i}}(c,x)\not\downarrow=0\bigr).(x∈A1−i​ ∧ evalχAi​​(c,x)↓=0)∨(x∈/A1−i​ ∧ evalχAi​​(c,x)↓=0).

Here χAi\chi_{A_i}χAi​​ is the total membership oracle of AiA_iAi​. The notation ↓̸=0\not\downarrow=0↓=0 includes both divergence and convergence to any nonzero natural number. In either alternative, the program fails to compute the characteristic function of A1−iA_{1-i}A1−i​ at xxx.

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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me