Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Enumeration and computation preservation for a permanent follower

Proved
FriedbergMuchnik.priority_permanent_follower_safety

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

computability-theoryfriedberg-muchnikpriority-construction

Consider the fixed priority construction. Let q,a,x∈Nq,a,x\in\mathbb Nq,a,x∈N and let bbb be a Boolean flag. Assume that q<aq<aq<a and that the entry for requirement qqq at every stage s≥as\ge as≥a is exactly the same pair (x,b)(x,b)(x,b). Put i=side⁡(q)i=\operatorname{side}(q)i=side(q), let cqc_qcq​ be the program with index ⌊q/2⌋\lfloor q/2\rfloor⌊q/2⌋, and write Ai=⋃sLi,sA_i=\bigcup_s L_{i,s}Ai​=⋃s​Li,s​ for the limit sets. Then

x∈A1−i⟺b=true.x\in A_{1-i}\quad\Longleftrightarrow\quad b=\mathrm{true}.x∈A1−i​⟺b=true.

Moreover, if the permanent flag is true, there is a stage t<at<at<a with

EtχLi,t(cq,x)=some⁡(0)andLi,t∩[0,t)=Ai∩[0,t).E_t^{\chi_{L_{i,t}}}(c_q,x)=\operatorname{some}(0) \quad\text{and}\quad L_{i,t}\cap[0,t)=A_i\cap[0,t).EtχLi,t​​​(cq​,x)=some(0)andLi,t​∩[0,t)=Ai​∩[0,t).

Here EtE_tEt​ is the bounded oracle interpreter and χLi,t\chi_{L_{i,t}}χLi,t​​ is the characteristic function of the finite stage list. The result classifies a specified permanent follower and supplies a preserved finite computation for an acted flag. It does not assert existence of a permanent follower or correctness of unbounded oracle evaluation.

Preamble
import Definitions.Def_FriedbergMuchnik_Priority
Formal statement
namespace FriedbergMuchnik

theorem priority_permanent_follower_safety (q a x : ℕ) (b : Bool)
    (hqa : q < a)
    (hstable : ∀ s : ℕ, a ≤ s →
      (priorityStage s).2[q]?.getD (0, false) = (x, b)) :
    (x ∈ limitSet (!(side q)) ↔ b = true) ∧
    (b = true → ∃ t : ℕ, t < a ∧
      oracleEvaln (stateOracle (priorityStage t) (side q)) t
        (Denumerable.ofNat Program (q / 2)) x = some 0 ∧
      ∀ n : ℕ, n < t →
        (n ∈ stageList (side q) t ↔ n ∈ limitSet (side q))) := 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. Verification cases (a) and (b) on pp. 53–54: distinct, unrepeated follower values and protection of the acted computation by appointing lower priority followers above its use. This conditional interface concerns the actual priorityStage entries and stageList unions. The activation hypothesis and stability of both follower and flag are explicit; prefix preservation uses the interpreter's bound on oracle queries. The combinatorial invariants are now proved directly in Lean: pairing-based follower freshness, monotone appointment stages, exact acted-flag membership, and preservation of the historical oracle prefix.

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