condorcet_qr23_selector_trans_hi
For the last 885 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_hi : ∀ i : Fin 1771, 886 ≤ i.val →
∀ 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 asserts that for the second half of triples (indices 886 through 1770) in the QR(23) Condorcet tournament selector, each transition replaces the chosen member of the triple with the challenger while preserving the other two members. Because the quantification is over finite ranges and all functions are concrete finite-table lookups, the proposition is decidable. The proof is completed by full computational evaluation in Lean's kernel using `decide +kernel`.
For each triple index i with 886 ≤ i < 1771 and eviction index k ∈ {0, 1, 2}, the next triple condorcet_qr23_selector_next i k contains the challenger and the two non-evicted members of triple i, and no other elements. automation
The statement is a bounded universal quantifier over finite types (Fin 1771 restricted to i.val ≥ 886, and Fin 3 for indices k and m). Because all functions (condorcet_qr23_selector_member, condorcet_qr23_selector_next, and condorcet_qr23_selector_challenger) are defined by computable table lookups and modular arithmetic, the entire proposition is decidable. The `decide +kernel` tactic evaluates the decision procedure for all 2,655 combinations of i and k directly inside the Lean kernel to close the goal.
decide +kernel
- The proof is purely computational: Lean's kernel exhaustively checks all 885 × 3 = 2,655 transition cases by evaluating the underlying lookup tables and boolean conditions, with no intermediate mathematical steps.
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_hi : ∀ i : Fin 1771, 886 ≤ i.val → ∀ 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