condorcet_qr23_selector_complete
Every three-element subset of Fin 23 is the member set of some indexed triple.
Statement
theorem condorcet_qr23_selector_complete : ∀ T : Finset (Fin 23), T.card = 3 →
∃ i, ({condorcet_qr23_selector_member i 0, condorcet_qr23_selector_member i 1, condorcet_qr23_selector_member i 2} : Finset (Fin 23)) = T- 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
Classical.choiceQuot.soundpropext- 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).
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- 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
To show that every three-element subset T of Fin 23 is the member set of some indexed triple, the proof first establishes that any strictly sorted triple a < b < c is selected by an explicit ranking formula, verified exhaustively by kernel evaluation (`decide +kernel`). The set T is decomposed into three distinct elements {x, y, z}, and trichotomy on each pair produces eight cases. Two cases form cyclic orderings that contradict transitivity, while the remaining six cases correspond to permutations of {x, y, z}, each reduced to the sorted key lemma by transposing adjacent elements.
The helper function `condorcet_qr23_selector_complete_rank` maps triples of elements of Fin 23 to an index in Fin 1771. automation
The function computes a polynomial ranking formula modulo 1771. The proof that the result is strictly less than 1771 uses `Nat.mod_lt` together with decision procedure automation (`decide`) verifying 0 < 1771.
uses
Nat.mod_ltprivate def condorcet_qr23_selector_complete_rank (a b c : Fin 23) : Fin 1771 := ⟨(1771 - (23 - a.val) * (22 - a.val) * (21 - a.val) / 6 + (22 - a.val) * (21 - a.val) / 2 - (23 - b.val) * (22 - b.val) / 2 + c.val - b.val - 1) % 1771, Nat.mod_lt _ (by decide)⟩
For any strictly increasing triple a < b < c in Fin 23, the selector evaluated at the rank of (a, b, c) at indices 0, 1, and 2 recovers a, b, and c. automation
Since Fin 23 is a finite type, the universally quantified statement over all triples is decidable by exhaustive finite checking, which the Lean kernel executes directly via `decide +kernel`.
private theorem condorcet_qr23_selector_complete_rank_spec : ∀ a b c : Fin 23, a < b → b < c → condorcet_qr23_selector_member (condorcet_qr23_selector_complete_rank a b c) 0 = a ∧ condorcet_qr23_selector_member (condorcet_qr23_selector_complete_rank a b c) 1 = b ∧ condorcet_qr23_selector_member (condorcet_qr23_selector_complete_rank a b c) 2 = c := by decide +kernel
For any sorted triple a < b < c in Fin 23, there exists an index i such that the selector members of i form the set {a, b, c}.
We introduce T and its cardinality hypothesis, then prove the key helper lemma: given a < b < c, `condorcet_qr23_selector_complete_rank_spec` provides the three coordinate equalities for the rank of (a, b, c), and rewriting by them establishes that the set of members is {a, b, c}.
uses
condorcet_qr23_selector_complete_rank_spectheorem condorcet_qr23_selector_complete : ∀ T : Finset (Fin 23), T.card = 3 → ∃ i, ({condorcet_qr23_selector_member i 0, condorcet_qr23_selector_member i 1, condorcet_qr23_selector_member i 2} : Finset (Fin 23)) = T := by intro T hT have key : ∀ a b c : Fin 23, a < b → b < c → ∃ i, ({condorcet_qr23_selector_member i 0, condorcet_qr23_selector_member i 1, condorcet_qr23_selector_member i 2} : Finset (Fin 23)) = {a, b, c} := by intro a b c hab hbc obtain ⟨h0, h1, h2⟩ := condorcet_qr23_selector_complete_rank_spec a b c hab hbc exact ⟨_, by rw [h0, h1, h2]⟩
The set T consists of three pairwise distinct elements x, y, z, and three-element sets are invariant under transpositions of adjacent elements.
Applying `Finset.card_eq_three.mp` to |T| = 3 decomposes T into {x, y, z} with x ≠ y, x ≠ z, and y ≠ z. We then prove two set permutation identities: e1 swaps the last two elements using `Finset.pair_comm`, and e2 swaps the first two elements using `Finset.insert_comm`.
uses
Finset.card_eq_three.mp,Finset.pair_comm,Finset.insert_commobtain ⟨x, y, z, hxy, hxz, hyz, rfl⟩ := Finset.card_eq_three.mp hT have e1 : ∀ p q r : Fin 23, ({p, q, r} : Finset (Fin 23)) = {p, r, q} := fun p q r => by rw [Finset.pair_comm] have e2 : ∀ p q r : Fin 23, ({p, q, r} : Finset (Fin 23)) = {q, p, r} := fun p q r => Finset.insert_comm p q {r}
The relative order of the three elements x, y, z is partitioned into eight cases.
Applying `lt_or_gt_of_ne` to each inequality x ≠ y, x ≠ z, and y ≠ z splits the possibilities into 2³ = 8 cases based on the pairwise comparisons.
uses
lt_or_gt_of_nercases lt_or_gt_of_ne hxy with h1 | h1 <;> rcases lt_or_gt_of_ne hxz with h2 | h2 <;> rcases lt_or_gt_of_ne hyz with h3 | h3
In the case x < y < z, the triple is sorted and matches the selector directly.
Applying the key lemma to x < y and y < z provides an index i whose member set is {x, y, z}.
· obtain ⟨i, hi⟩ := key x y z h1 h3; exact ⟨i, hi⟩
In the case x < z < y, the selector yields {x, z, y}, which equals {x, y, z}.
Applying the key lemma to x < z and z < y gives an index whose member set is {x, z, y}, and rewriting via e1 yields {x, y, z}.
· obtain ⟨i, hi⟩ := key x z y h2 h3; exact ⟨i, hi.trans (e1 x z y)⟩
The case x < y, z < x, and y < z is contradictory.
Transitivity of < implies x < z from x < y and y < z, which directly contradicts z < x via `not_lt.mpr`.
uses
not_lt.mpr· exact absurd (h1.trans h3) (not_lt.mpr h2.le)In the case z < x < y, the selector yields {z, x, y}, which equals {x, y, z}.
Applying the key lemma to z < x and x < y gives an index with member set {z, x, y}. Transposing the first two elements via e2 and then the last two via e1 reorders {z, x, y} to {x, y, z}.
· obtain ⟨i, hi⟩ := key z x y h2 h1 exact ⟨i, hi.trans ((e2 z x y).trans (e1 x z y))⟩
In the case y < x < z, the selector yields {y, x, z}, which equals {x, y, z}.
Applying the key lemma to y < x and x < z gives an index with member set {y, x, z}. Transposing the first two elements via e2 yields {x, y, z}.
· obtain ⟨i, hi⟩ := key y x z h1 h2; exact ⟨i, hi.trans (e2 y x z)⟩
The case y < x, x < z, and z < y is contradictory.
Transitivity of < implies z < x from z < y and y < x, contradicting x < z via `not_lt.mpr`.
uses
not_lt.mpr· exact absurd (h3.trans h1) (not_lt.mpr h2.le)In the case y < z < x, the selector yields {y, z, x}, which equals {x, y, z}.
Applying the key lemma to y < z and z < x gives an index with member set {y, z, x}. Transposing the last two elements via e1 and then the first two via e2 yields {x, y, z}.
· obtain ⟨i, hi⟩ := key y z x h3 h2 exact ⟨i, hi.trans ((e1 y z x).trans (e2 y x z))⟩
In the case z < y < x, the selector yields {z, y, x}, which equals {x, y, z}.
Applying the key lemma to z < y and y < x gives an index with member set {z, y, x}. Applying e2, e1, and e2 in succession reverses the order to yield {x, y, z}.
· obtain ⟨i, hi⟩ := key z y x h3 h1 exact ⟨i, hi.trans ((e2 z y x).trans ((e1 y z x).trans (e2 y x z)))⟩
Nat.mod_lt- For any positive natural number y, the remainder x % y is strictly less than y.
condorcet_qr23_selector_complete_rank_spec- For any strictly increasing triple a < b < c in Fin 23, evaluating the selector at the rank of (a, b, c) at indices 0, 1, 2 recovers a, b, c respectively.
Finset.card_eq_three.mp- A finite set has cardinality 3 if and only if it consists of three pairwise distinct elements.
Finset.pair_comm- Unordered pairs are symmetric: {a, b} = {b, a}.
Finset.insert_comm- Element insertion into a finite set is commutative: insert a (insert b s) = insert b (insert a s).
lt_or_gt_of_ne- In a linear order, any two distinct elements satisfy a < b or b < a.
not_lt.mpr- If b ≤ a, then it is not the case that a < b.
- The specification lemma `condorcet_qr23_selector_complete_rank_spec` is proved entirely by kernel evaluation (`decide +kernel`), which exhaustively verifies all 1771 strictly increasing triples.
- The proof sorts the elements x, y, z by branching on all eight possible combinations of pairwise strict comparisons (`lt_or_gt_of_ne`), eliminating the two cyclic combinations via transitivity.
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.
private def condorcet_qr23_selector_complete_rank (a b c : Fin 23) : Fin 1771 := ⟨(1771 - (23 - a.val) * (22 - a.val) * (21 - a.val) / 6 + (22 - a.val) * (21 - a.val) / 2 - (23 - b.val) * (22 - b.val) / 2 + c.val - b.val - 1) % 1771, Nat.mod_lt _ (by decide)⟩private theorem condorcet_qr23_selector_complete_rank_spec : ∀ a b c : Fin 23, a < b → b < c → condorcet_qr23_selector_member (condorcet_qr23_selector_complete_rank a b c) 0 = a ∧ condorcet_qr23_selector_member (condorcet_qr23_selector_complete_rank a b c) 1 = b ∧ condorcet_qr23_selector_member (condorcet_qr23_selector_complete_rank a b c) 2 = c := by decide +kerneltheorem condorcet_qr23_selector_complete : ∀ T : Finset (Fin 23), T.card = 3 → ∃ i, ({condorcet_qr23_selector_member i 0, condorcet_qr23_selector_member i 1, condorcet_qr23_selector_member i 2} : Finset (Fin 23)) = T := by intro T hT have key : ∀ a b c : Fin 23, a < b → b < c → ∃ i, ({condorcet_qr23_selector_member i 0, condorcet_qr23_selector_member i 1, condorcet_qr23_selector_member i 2} : Finset (Fin 23)) = {a, b, c} := by intro a b c hab hbc obtain ⟨h0, h1, h2⟩ := condorcet_qr23_selector_complete_rank_spec a b c hab hbc exact ⟨_, by rw [h0, h1, h2]⟩ obtain ⟨x, y, z, hxy, hxz, hyz, rfl⟩ := Finset.card_eq_three.mp hT have e1 : ∀ p q r : Fin 23, ({p, q, r} : Finset (Fin 23)) = {p, r, q} := fun p q r => by rw [Finset.pair_comm] have e2 : ∀ p q r : Fin 23, ({p, q, r} : Finset (Fin 23)) = {q, p, r} := fun p q r => Finset.insert_comm p q {r} rcases lt_or_gt_of_ne hxy with h1 | h1 <;> rcases lt_or_gt_of_ne hxz with h2 | h2 <;> rcases lt_or_gt_of_ne hyz with h3 | h3 · obtain ⟨i, hi⟩ := key x y z h1 h3; exact ⟨i, hi⟩ · obtain ⟨i, hi⟩ := key x z y h2 h3; exact ⟨i, hi.trans (e1 x z y)⟩ · exact absurd (h1.trans h3) (not_lt.mpr h2.le) · obtain ⟨i, hi⟩ := key z x y h2 h1 exact ⟨i, hi.trans ((e2 z x y).trans (e1 x z y))⟩ · obtain ⟨i, hi⟩ := key y x z h1 h2; exact ⟨i, hi.trans (e2 y x z)⟩ · exact absurd (h3.trans h1) (not_lt.mpr h2.le) · obtain ⟨i, hi⟩ := key y z x h3 h2 exact ⟨i, hi.trans ((e1 y z x).trans (e2 y x z))⟩ · obtain ⟨i, hi⟩ := key z y x h3 h1 exact ⟨i, hi.trans ((e2 z y x).trans ((e1 y z x).trans (e2 y x z)))⟩