condorcet_qr23_selector_trans_lo
For the first 886 triples, each transition's member list is the old triple with the evicted member replaced by the challenger (as sets of members).
Statement
theorem condorcet_qr23_selector_trans_lo : ∀ i : Fin 1771, i.val < 886 →
∀ k : Fin 3,
(∀ m : Fin 3, condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m = condorcet_qr23_selector_challenger i ∨ (condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m ≠ condorcet_qr23_selector_member i k ∧
(condorcet_qr23_selector_member i 0 = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m ∨ condorcet_qr23_selector_member i 1 = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m ∨ condorcet_qr23_selector_member i 2 = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m))) ∧
(condorcet_qr23_selector_challenger i = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 0 ∨ condorcet_qr23_selector_challenger i = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 1 ∨ condorcet_qr23_selector_challenger i = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 2) ∧
(∀ m : Fin 3, m ≠ k → (condorcet_qr23_selector_member i m = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 0 ∨ condorcet_qr23_selector_member i m = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 1 ∨ condorcet_qr23_selector_member i m = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 2))- Source
- Certificate data for condorcet_tournament_stationary_restriction_obstruction (restriction diagnostic for OP-19 on the quadratic-residue tournament modulo 23; potential from experiment 8584, recomputed by CP-SAT). Related definition from Condorcet winning sets, Social Choice and Welfare 44(3):493-517 (2015).
- Verified
- 29 Oct 2026
- Axioms
propext- Built on 3
- condorcet_qr23_selector_memberThe k-th smallest member of the i-th three-element subset of Fin 23 in lexicographic order (stored as lookup tables).
- condorcet_qr23_selector_challengerThe outside challenger of the i-th triple: the first candidate cyclically before its minimum that beats all three members in the…
- condorcet_qr23_selector_nextThe index of the triple obtained from the i-th triple by evicting its k-th smallest member and inserting its challenger.
- Used by 1
- condorcet_tournament_stationary_restriction_obstructionThere is a complete outside-challenger selector on all1771 three-element subsets of23 candidates such that every challenger dominates…
The proof, explained
The theorem states that for each of the first 886 triples and each choice of evicted member index k ∈ {0, 1, 2}, the transition to the next triple replaces member k with the challenger while retaining the other two members. Because the state space is finite and all selector functions are computable, the proposition is decidable. The theorem is proved by exhaustive kernel evaluation across all cases.
For each state index i < 886 and member slot k ∈ {0, 1, 2}, the transition replaces member k with the challenger and preserves the other two members. automation
Because the domain is finite (886 states, 3 transition choices per state, and 3 member positions) and all lookup functions on Fin 1771 and Fin 3 are computationally defined, the universal quantification and boolean conditions constitute a decidable proposition. The `decide +kernel` tactic delegates the exhaustive evaluation of all 2658 cases directly to Lean's kernel.
decide +kernel
- The proof contains no manual deduction steps; it relies entirely on Lean's kernel evaluating the decidable proposition across all 886 × 3 = 2658 transitions by table lookup.
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 condorcet_qr23_selector_trans_lo : ∀ i : Fin 1771, i.val < 886 → ∀ k : Fin 3, (∀ m : Fin 3, condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m = condorcet_qr23_selector_challenger i ∨ (condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m ≠ condorcet_qr23_selector_member i k ∧ (condorcet_qr23_selector_member i 0 = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m ∨ condorcet_qr23_selector_member i 1 = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m ∨ condorcet_qr23_selector_member i 2 = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) m))) ∧ (condorcet_qr23_selector_challenger i = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 0 ∨ condorcet_qr23_selector_challenger i = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 1 ∨ condorcet_qr23_selector_challenger i = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 2) ∧ (∀ m : Fin 3, m ≠ k → (condorcet_qr23_selector_member i m = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 0 ∨ condorcet_qr23_selector_member i m = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 1 ∨ condorcet_qr23_selector_member i m = condorcet_qr23_selector_member (condorcet_qr23_selector_next i k) 2)) := by decide +kernel