prioritized_borel_alternating_priority_no_two_relabel
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`.
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}$.)
decide +kernel
- The proof is carried out entirely via computational reflection in the Lean kernel (`decide +kernel`), exhaustively checking all 32 candidate pairs rather than writing out a paper-style deduction.
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_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