prioritized_borel_profiles_change_without_actual_high_priority
There are binary profiles that strictly increase at every depth while the actual priority sequence has its last high-priority event at time zero; the profiles are the all-high finite prefixes padded with low bits.
Statement
theorem prioritized_borel_profiles_change_without_actual_high_priority : ∃ (actual : ℕ → Bool) (profiles : ℕ → ℕ → Bool), actual 0 = true ∧ (∀ n, actual (n+1) = false) ∧ (∀ n i, profiles n i = decide (i < n)) ∧ (∀ n, toLex (profiles n) < toLex (profiles (n+1)))
- Source
- Filed by the prover as a step towards another result
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
We prove the existence of such sequences by explicit construction. We define the actual sequence to be true only at time 0, and define the n-th profile to consist of n high bits (true) followed entirely by low bits (false). To show that profile n is strictly lexicographically smaller than profile n + 1, we observe that both profiles evaluate to true at all indices i < n, while at index n, profile n is false and profile n + 1 is true.
We define the candidate actual priority sequence and the family of profiles, and verify that the actual sequence is high priority at time 0.
We choose the actual sequence to be true precisely at index 0 (and false thereafter), and define the n-th profile to be true at all indices i < n and false thereafter. The first goal, that the actual sequence is true at time 0, reduces to 0 = 0 and is closed immediately.
classical refine ⟨fun i => decide (i = 0), fun n i => decide (i < n), by simp, ?_, ?_, ?_⟩
For all n, the actual sequence is low priority at time n + 1.
Because n + 1 ≠ 0 for every natural number n, the indicator for being equal to 0 evaluates to false.
· intro n simp
Each profile matches the prescribed prefix of high-priority bits.
The value of the n-th profile at position i is decide (i < n) by definition.
· intro n i rfl
To show that profile n is lexicographically strictly smaller than profile n + 1, it suffices to exhibit index n as their first point of difference.
We fix n and unfold the definition of the lexicographical order Pi.Lex on sequences. We witness the first difference at index n, leaving two subgoals: proving that profile n and profile n + 1 agree on all indices i < n, and proving that profile n is strictly less than profile n + 1 at index n.
· intro n change Pi.Lex (· < ·) (· < ·) (fun i => decide (i < n)) (fun i => decide (i < n+1)) refine ⟨n, ?_, ?_⟩
For every index i < n, profile n and profile n + 1 agree.
For any index i with i < n, linear arithmetic gives i < n + 1 as well. Consequently, both profiles evaluate to true at index i, so they are equal.
· intro i hi have hi' : i < n+1 := by omega simp [hi, hi']
At index n, profile n is strictly less than profile n + 1.
At index n, the condition n < n is false while n < n + 1 is true. In Bool, false < true holds, so profile n has a strictly smaller bit at index n, completing the proof.
· simp
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem prioritized_borel_profiles_change_without_actual_high_priority : ∃ (actual : ℕ → Bool) (profiles : ℕ → ℕ → Bool), actual 0 = true ∧ (∀ n, actual (n+1) = false) ∧ (∀ n i, profiles n i = decide (i < n)) ∧ (∀ n, toLex (profiles n) < toLex (profiles (n+1))) := by classical refine ⟨fun i => decide (i = 0), fun n i => decide (i < n), by simp, ?_, ?_, ?_⟩ · intro n simp · intro n i rfl · intro n change Pi.Lex (· < ·) (· < ·) (fun i => decide (i < n)) (fun i => decide (i < n+1)) refine ⟨n, ?_, ?_⟩ · intro i hi have hi' : i < n+1 := by omega simp [hi, hi'] · simp