AFTD Auto-Formalizing Theoretical Domains

condorcet_qr23_selector_complete

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

  1. 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.

    lines 1–4

    uses Nat.mod_lt

    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)⟩
    
  2. 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`.

    lines 5–9

    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
    
  3. 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}.

    lines 10–17

    uses condorcet_qr23_selector_complete_rank_spec

    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 := 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]⟩
  4. 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`.

    lines 18–22

    uses Finset.card_eq_three.mp, Finset.pair_comm, Finset.insert_comm

      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}
  5. 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.

    lines 23–24

    uses lt_or_gt_of_ne

      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
  6. 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}.

    line 25

      · obtain ⟨i, hi⟩ := key x y z h1 h3; exact ⟨i, hi⟩
  7. 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}.

    line 26

      · obtain ⟨i, hi⟩ := key x z y h2 h3; exact ⟨i, hi.trans (e1 x z y)⟩
  8. 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`.

    line 27

    uses not_lt.mpr

      · exact absurd (h1.trans h3) (not_lt.mpr h2.le)
  9. 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}.

    lines 28–29

      · obtain ⟨i, hi⟩ := key z x y h2 h1
        exact ⟨i, hi.trans ((e2 z x y).trans (e1 x z y))⟩
  10. 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}.

    line 30

      · obtain ⟨i, hi⟩ := key y x z h1 h2; exact ⟨i, hi.trans (e2 y x z)⟩
  11. 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`.

    line 31

    uses not_lt.mpr

      · exact absurd (h3.trans h1) (not_lt.mpr h2.le)
  12. 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}.

    lines 32–33

      · obtain ⟨i, hi⟩ := key y z x h3 h2
        exact ⟨i, hi.trans ((e1 y z x).trans (e2 y x z))⟩
  13. 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}.

    lines 34–35

      · 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.

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

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)))⟩
See it in the graphDiscuss this resultChallenge it