AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_alternating_priority_no_two_relabel

theoremverified

The alternating acceptance pattern false, true, false on three priorities cannot be represented for all recurrent-priority sets by any fixed relabelling into two priorities and any two acceptance values.

Statement

theorem prioritized_borel_alternating_priority_no_two_relabel :
    ¬ ∃ (f : Fin 3 → Fin 2) (w : Fin 2 → Bool),
      w (f 0) = false ∧ w (f 1) = true ∧ w (f 2) = false ∧
      w (max (f 0) (f 1)) = true ∧ w (max (f 1) (f 2)) = false
Source
Structural step related to arXiv:2611.10136, Conjecture 19.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem asserts that no relabelling of three priorities into two can preserve the alternating acceptance condition $\{0 \mapsto \mathrm{false}, 1 \mapsto \mathrm{true}, 2 \mapsto \mathrm{false}\}$ together with the acceptance of the pairwise maximum combinations $\{0, 1\}$ and $\{1, 2\}$. Because the function types $\mathrm{Fin}\ 3 \to \mathrm{Fin}\ 2$ and $\mathrm{Fin}\ 2 \to \mathrm{Bool}$ are finite, the statement is a decidable bounded search over 32 candidate pairs $(f, w)$. The proof delegates this exhaustive case check directly to the Lean kernel via `decide +kernel`.

  1. There exist no relabelling $f : \mathrm{Fin}\ 3 \to \mathrm{Fin}\ 2$ and acceptance assignment $w : \mathrm{Fin}\ 2 \to \mathrm{Bool}$ satisfying the alternating priority conditions. automation

    The search space is finite: there are only $2^3 = 8$ functions $f : \mathrm{Fin}\ 3 \to \mathrm{Fin}\ 2$ and $2^2 = 4$ predicates $w : \mathrm{Fin}\ 2 \to \mathrm{Bool}$, for a total of 32 possible pairs $(f, w)$. The tactic `decide +kernel` runs the decision procedure for finite existential quantification inside the Lean kernel, exhaustively verifying that none of the 32 pairs satisfies all five equations. (Mathematically, $w(f(1)) = \mathrm{true}$ and $w(f(2)) = \mathrm{false}$ implies $\{f(1), f(2)\} = \{0, 1\}$, so $\max(f(1), f(2)) = 1$ and $w(1) = \mathrm{false}$; this forces $f(1) = 0$, $w(0) = \mathrm{true}$, and $f(0) = 1$, which makes $\max(f(0), f(1)) = 1$ and thus $w(\max(f(0), f(1))) = w(1) = \mathrm{false}$, contradicting the requirement that it be $\mathrm{true}$.)

    line 5

      decide +kernel

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_alternating_priority_no_two_relabel :    ¬ ∃ (f : Fin 3 → Fin 2) (w : Fin 2 → Bool),      w (f 0) = false ∧ w (f 1) = true ∧ w (f 2) = false ∧      w (max (f 0) (f 1)) = true ∧ w (max (f 1) (f 2)) = false := by  decide +kernel
See it in the graphDiscuss this resultChallenge it