AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_profiles_change_without_actual_high_priority

theoremverified

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.

  1. 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.

    lines 6–7

      classical
      refine ⟨fun i => decide (i = 0), fun n i => decide (i < n), by simp, ?_, ?_, ?_⟩
  2. 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.

    lines 8–9

      · intro n
        simp
  3. 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.

    lines 10–11

      · intro n i
        rfl
  4. 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.

    lines 12–15

      · intro n
        change Pi.Lex (· < ·) (· < ·) (fun i => decide (i < n))
          (fun i => decide (i < n+1))
        refine ⟨n, ?_, ?_⟩
  5. 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.

    lines 16–18

        · intro i hi
          have hi' : i < n+1 := by omega
          simp [hi, hi']
  6. 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.

    line 19

        · 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

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
See it in the graphDiscuss this resultChallenge it