AFTD Auto-Formalizing Theoretical Domains

condorcet_complete_private_averaging_obstruction

theoremverified

There exist an irreflexive directed relation R on16 vertices with a common predecessor for every ordered triple, a nonempty finite family F(a) of private three-element sets at every root a, natural occupations q, and an induced acyclic subset U. Every member of F(a) excludes a and has a as its unique common predecessor. Completeness is checked for every increasing triple a<b<c: its set belongs to F(r) if and only if r is its unique common predecessor, so all private three-element sets are present. With w(a)=card(F(a))*q(a), the exact identity 3*w(b)=sum over a and J in F(a) containing b of q(a) holds. These weights therefore obey stationarity for uniform averaging over all private triples at each root, then uniformly over their three vertices. Total weight is2876598259756430344, while U has weight1447017722375641758, strictly above half. This is a counterexample to this particular averaging construction.

Statement

theorem condorcet_complete_private_averaging_obstruction :
    ∃ (R : Fin 16 → Fin 16 → Prop)
      (F : Fin 16 → Finset (Finset (Fin 16))) (q : Fin 16 → ℕ)
      (U : Finset (Fin 16)),
      (∀ a, ¬ R a a) ∧
      (∀ a b c, ∃ r, R r a ∧ R r b ∧ R r c) ∧
      (∀ a, (F a).Nonempty ∧ ∀ J ∈ F a,
        J.card = 3 ∧ a ∉ J ∧ (∀ b ∈ J, R a b) ∧
        ∀ r, (∀ b ∈ J, R r b) → r = a) ∧
      (∀ r a b c, a < b → b < c →
        ({a,b,c} ∈ F r ↔ R r a ∧ R r b ∧ R r c ∧
          ∀ s, (R s a ∧ R s b ∧ R s c) → s = r)) ∧
      (∀ b, 3 * ((F b).card * q b) =
        ∑ a, ∑ J ∈ F a, if b ∈ J then q a else 0) ∧
      (∑ a, (F a).card * q a) = 2876598259756430344 ∧
      (∑ a ∈ U, (F a).card * q a) = 1447017722375641758 ∧
      0 < (∑ a, (F a).card * q a) ∧
      (∑ a, (F a).card * q a) < 2 * (∑ a ∈ U, (F a).card * q a) ∧
      WellFounded (fun a b : {a : Fin 16 // a ∈ U} => R a.val b.val)
Source
IN-357 method diagnostic for OP-19, search8929 and exact integer audit8932. It concerns the complete-private-triple averaging rule, which is distinct from arbitrary chosen private triples and from the older all-committee eviction rule. This is no election counterexample, no obstruction to optimized vertex weights, and no research advance. Reciprocal arrows are allowed; no oriented/tournament conclusion is asserted.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem proves the existence of a counterexample to a private-triple averaging conjecture on tournaments by constructing an explicit 16-vertex directed graph. The relation is irreflexive and every triple has a common predecessor, with private 3-element sets at each root containing all triples that uniquely identify that root. Given explicit integer occupation numbers, the induced vertex weights satisfy the exact stationary balance equations for two-stage uniform averaging. Finally, an explicit 8-vertex subset is proved acyclic via a strict topological ranking, yet carries strictly more than half of the total stationary weight.

  1. The directed relation R is irreflexive on Fin 16. automation

    Checked by finite exhaustive evaluation over all 16 vertices using the bitmask definitions of the relation.

    line 19

        ¬condorcet_complete_private_relation a a := by decide
  2. Every triple of vertices has a common predecessor in R. automation

    Verified by finite exhaustive search: for each of the 16³ ordered triples (a, b, c), there exists a vertex r dominating all three.

    line 24

          condorcet_complete_private_relation r c := by decide
  3. For every vertex a, the family F(a) is nonempty, and every member J is a 3-element set disjoint from a, dominated by a, and having a as its unique common predecessor.

    We decide nonemptiness of each list in the table and verify that all list elements satisfy the required four conjunctions. Converting finset membership to list membership using List.mem_toFinset.mp and applying List.all_eq_true.mp via of_decide_eq_true establishes the properties for every member J ∈ F(a).

    lines 32–43

    uses List.mem_toFinset.mp, of_decide_eq_true, List.all_eq_true.mp

      have hnonempty : ∀ a, (condorcet_complete_private_family a).Nonempty := by decide
      have hcheck : ∀ a, (condorcet_complete_private_list a).all (fun J =>
          decide (J.card = 3 ∧ a ∉ J ∧
            (∀ b ∈ J, condorcet_complete_private_relation a b) ∧
            ∀ r, (∀ b ∈ J, condorcet_complete_private_relation r b) → r = a)) = true := by
        decide
      intro a
      refine ⟨hnonempty a, ?_⟩
      intro J hJ
      have hm : J ∈ condorcet_complete_private_list a := by
        exact List.mem_toFinset.mp hJ
      exact of_decide_eq_true (List.all_eq_true.mp (hcheck a) J hm)
  4. If a triple {a, b, c} belongs to F(r), then r dominates a, b, and c, and r is their unique common predecessor.

    By the private family membership properties, r dominates each element of the triple {a, b, c}. Given any vertex s dominating a, b, and c, unpacking the finset membership of {a, b, c} via mem_insert and mem_singleton shows that s dominates every element of {a, b, c}, which implies s = r by the uniqueness property.

    lines 53–62

    uses condorcet_complete_private_members, mem_insert, mem_singleton

      have hmem := (condorcet_complete_private_members r).2 {a, b, c} hJ
      refine ⟨hmem.2.2.1 a (by simp), hmem.2.2.1 b (by simp), hmem.2.2.1 c (by simp), ?_⟩
      intro s ⟨hsa, hsb, hsc⟩
      apply hmem.2.2.2 s
      intro x hx
      simp only [mem_insert, mem_singleton] at hx
      rcases hx with rfl | rfl | rfl
      · exact hsa
      · exact hsb
      · exact hsc
  5. For every ordered triple a < b < c, if r is the unique common predecessor of {a, b, c}, then {a, b, c} belongs to F(r). automation

    Verified by exhaustive evaluation of all increasing triples and potential roots against the table of private families.

    line 71

        {a,b,c} ∈ condorcet_complete_private_family r := by decide
  6. For every ordered triple a < b < c, {a, b, c} belongs to F(r) if and only if r is the unique common predecessor of a, b, and c.

    Combines the forward direction (condorcet_complete_private_complete_forward) and the backward direction (condorcet_complete_private_complete_backward).

    lines 82–85

    uses condorcet_complete_private_complete_forward, condorcet_complete_private_complete_backward

      intro r a b c hab hbc
      constructor
      · exact condorcet_complete_private_complete_forward r a b c
      · exact condorcet_complete_private_complete_backward a b c hab hbc r
  7. The stationary flow identity 3 * w(b) = sum over a and J in F(a) containing b of q(a) holds for every vertex b. automation

    Checked by exhaustive arithmetic evaluation of both sides of the balance equation for each of the 16 vertices.

    line 90

            if b ∈ J then condorcet_complete_private_occupation a else 0 := by decide
  8. The total weight is 2876598259756430344, the weight of U is 1447017722375641758, the total weight is positive, and U has strictly more than half the total weight. automation

    Computed directly by summing the weights w(a) = |F(a)| * q(a) across all vertices and across U, and checking the strict inequality 2 * 1447017722375641758 > 2876598259756430344.

    line 97

          2 * (∑ a ∈ condorcet_complete_private_set, condorcet_complete_private_weight a) := by decide
  9. The ranking function strictly increases along every directed edge between vertices in U. automation

    Verified by checking the strict inequality order(a) < order(b) for all pairs a, b in U such that R(a, b).

    line 102

          condorcet_complete_private_order a < condorcet_complete_private_order b := by decide
  10. The relation R restricted to the subset U is well-founded, hence acyclic.

    We use measure to pull back the well-founded natural number ordering along the ranking function condorcet_complete_private_order, which is strictly increasing on edges in U by condorcet_complete_private_ordered.

    lines 107–110

    uses measure, condorcet_complete_private_ordered

      refine (measure (fun a : {a : Fin 16 // a ∈ condorcet_complete_private_set} =>
        condorcet_complete_private_order a.val)).wf.mono ?_
      intro a b hab
      exact condorcet_complete_private_ordered a.val b.val a.property b.property hab
  11. There exist an irreflexive relation R, private families F, occupations q, and an acyclic set U satisfying all conditions of the averaging obstruction theorem.

    We provide the explicit witnesses R, F, q, U and instantiate the ten conjuncts using the established lemmas for irreflexivity, common predecessors, family member properties, completeness, flow conservation, the four mass equalities and inequalities, and well-foundedness of U.

    lines 131–139

    uses condorcet_complete_private_irreflexive, condorcet_complete_private_s3, condorcet_complete_private_members, condorcet_complete_private_complete, condorcet_complete_private_flow, condorcet_complete_private_wellFounded, condorcet_complete_private_mass.1, condorcet_complete_private_mass.2.1, condorcet_complete_private_mass.2.2.1, condorcet_complete_private_mass.2.2.2

      refine ⟨condorcet_complete_private_relation, condorcet_complete_private_family,
        condorcet_complete_private_occupation, condorcet_complete_private_set,
        condorcet_complete_private_irreflexive, condorcet_complete_private_s3,
        condorcet_complete_private_members, condorcet_complete_private_complete,
        condorcet_complete_private_flow, ?_, ?_, ?_, ?_, condorcet_complete_private_wellFounded⟩
      · exact condorcet_complete_private_mass.1
      · exact condorcet_complete_private_mass.2.1
      · exact condorcet_complete_private_mass.2.2.1
      · exact condorcet_complete_private_mass.2.2.2
List.mem_toFinset.mp
An element belongs to the list underlying a finset if it belongs to the finset.
of_decide_eq_true
If a boolean decision procedure evaluates to true, the corresponding proposition holds.
List.all_eq_true.mp
If a boolean test succeeds on all elements of a list, it holds for each member of the list.
condorcet_complete_private_members
For every root a, the family F(a) is nonempty, and every J in F(a) has cardinality 3, excludes a, is dominated by a, and has a as its unique common predecessor.
mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
mem_singleton
An element belongs to {a} if and only if it equals a.
condorcet_complete_private_complete_forward
If {a, b, c} belongs to F(r), then r dominates a, b, and c, and any common predecessor of all three must be r.
condorcet_complete_private_complete_backward
For any ordered triple a < b < c, if r is the unique common predecessor of a, b, and c, then {a, b, c} belongs to F(r).
measure
Constructs a well-founded relation by pulling back the natural number order through a measure function.
condorcet_complete_private_ordered
The ranking function strictly increases along every directed edge in the set U.
condorcet_complete_private_irreflexive
The relation R is irreflexive.
condorcet_complete_private_s3
Every triple of vertices has a common predecessor in R.
condorcet_complete_private_complete
For any ordered triple a < b < c, {a, b, c} belongs to F(r) if and only if r is the unique common predecessor of a, b, and c.
condorcet_complete_private_flow
The stationary flow equation 3 * w(b) = sum over a and J in F(a) containing b of q(a) holds for all vertices b.
condorcet_complete_private_wellFounded
The relation R restricted to the subset U is well-founded.
condorcet_complete_private_mass.1
The total stationary weight across all vertices equals 2876598259756430344.
condorcet_complete_private_mass.2.1
The total stationary weight of the subset U equals 1447017722375641758.
condorcet_complete_private_mass.2.2.1
The total stationary weight is strictly positive.
condorcet_complete_private_mass.2.2.2
The total stationary weight is strictly less than twice the weight of U, so U holds strictly more than half the mass.

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

open Finsetopen scoped BigOperatorsdef condorcet_complete_private_pred : Fin 16 → ℕ := ![38834,43481,10976,31008,36456,20296,19120,17272,15584,3376,2988,26173,28102,3184,3937,31314]def condorcet_complete_private_relation (a b : Fin 16) : Prop :=  (condorcet_complete_private_pred b).testBit a.val = trueinstance : DecidableRel condorcet_complete_private_relation := fun a b =>  inferInstanceAs (Decidable ((condorcet_complete_private_pred b).testBit a.val = true))def condorcet_complete_private_list : Fin 16 → List (Finset (Fin 16)) := ![[{1,11,14}],[{0,12,15}],[{10,11,12}],[{1,4,11},{1,5,11},{1,10,11}],[{0,1,11},{0,1,13},{0,1,15},{0,9,15},{0,13,15},{1,6,7},{1,6,11},{1,9,11},{1,11,13},{7,9,15},{9,11,15},{11,13,15}],[{0,2,3},{0,2,9},{0,2,13},{0,3,4},{0,3,6},{0,3,11},{0,3,13},{0,7,8},{0,10,13},{2,3,7},{2,7,9},{2,9,11},{2,11,13},{3,4,7},{3,4,11},{3,7,8},{3,7,13},{3,9,11},{3,10,11},{3,11,13},{3,11,14},{4,7,9},{6,7,8},{6,8,11},{7,8,9},{7,8,10},{7,8,11},{7,10,13},{8,10,11},{9,10,11},{10,11,13}],[{1,2,7},{1,7,8},{2,7,12},{4,7,12},{5,7,8},{5,7,13},{7,8,12},{7,8,15},{7,12,13}],[{0,1,2},{0,1,8},{0,2,12},{0,6,12}],[{0,1,3},{0,1,5},{0,1,14},{0,3,5},{0,3,12},{0,7,12},{1,3,7},{5,7,9},{7,9,12},{7,10,12}],[{0,2,5},{0,2,15},{0,4,15},{0,5,6},{0,5,15},{0,10,15},{0,14,15},{2,5,11},{4,11,15},{7,10,15},{10,11,15},{11,14,15}],[{0,4,12},{0,5,8},{0,5,13},{0,11,12},{0,12,13},{4,11,12},{5,8,11},{5,9,11},{5,11,13},{9,11,12},{11,12,13},{11,12,14}],[{1,2,9},{1,3,4},{1,3,6},{1,3,13},{1,4,6},{1,4,9},{1,5,6},{1,6,14},{1,8,9},{1,10,13},{1,10,15},{2,3,5},{2,5,9},{2,9,12},{2,9,15},{3,4,5},{3,4,12},{3,4,15},{3,5,8},{3,5,13},{3,9,15},{3,10,15},{3,12,13},{3,13,15},{3,14,15},{4,6,12},{4,9,15},{4,10,12},{5,6,8},{5,6,9},{5,6,13},{5,8,10},{5,9,15},{5,10,13},{6,8,15},{6,9,12},{6,12,13},{6,12,14},{8,9,15},{8,10,15},{9,10,15},{9,12,15},{9,14,15},{10,12,13},{10,12,15},{10,13,15}],[{0,3,15},{0,8,15}],[{1,2,11},{1,3,11},{1,8,11},{1,11,12},{2,11,12},{8,11,15}],[{3,5,11},{3,7,15},{6,7,12},{6,11,12},{7,11,12}],[{0,1,4}]]def condorcet_complete_private_family (a : Fin 16) : Finset (Finset (Fin 16)) :=  (condorcet_complete_private_list a).toFinsetdef condorcet_complete_private_occupation : Fin 16 → ℕ := ![446845983201704302,410053001074363439,53104951062296765,44040360322123860,13435306768598744,2847193144423017,8111824930189959,24287979033766593,10039264993826346,5930674449492833,6211566117902783,7155402591528509,138138318586479658,10507928470947514,33761797781530410,331446981381001084]def condorcet_complete_private_weight (a : Fin 16) : ℕ :=  (condorcet_complete_private_family a).card * condorcet_complete_private_occupation adef condorcet_complete_private_order : Fin 16 → ℕ := ![7,0,3,5,0,0,1,0,0,0,0,0,4,2,0,6]def condorcet_complete_private_set : Finset (Fin 16) := {9,6,13,2,12,3,15,0}theorem condorcet_complete_private_irreflexive : ∀ a,    ¬condorcet_complete_private_relation a a := by decidetheorem condorcet_complete_private_s3 : ∀ a b c : Fin 16,    ∃ r, condorcet_complete_private_relation r a ∧      condorcet_complete_private_relation r b ∧      condorcet_complete_private_relation r c := by decidetheorem condorcet_complete_private_members : ∀ a,    (condorcet_complete_private_family a).Nonempty ∧    ∀ J ∈ condorcet_complete_private_family a,      J.card = 3 ∧ a ∉ J ∧      (∀ b ∈ J, condorcet_complete_private_relation a b) ∧      ∀ r, (∀ b ∈ J, condorcet_complete_private_relation r b) → r = a := by  have hnonempty : ∀ a, (condorcet_complete_private_family a).Nonempty := by decide  have hcheck : ∀ a, (condorcet_complete_private_list a).all (fun J =>      decide (J.card = 3 ∧ a ∉ J ∧        (∀ b ∈ J, condorcet_complete_private_relation a b) ∧        ∀ r, (∀ b ∈ J, condorcet_complete_private_relation r b) → r = a)) = true := by    decide  intro a  refine ⟨hnonempty a, ?_⟩  intro J hJ  have hm : J ∈ condorcet_complete_private_list a := by    exact List.mem_toFinset.mp hJ  exact of_decide_eq_true (List.all_eq_true.mp (hcheck a) J hm)theorem condorcet_complete_private_complete_forward (r a b c : Fin 16)    (hJ : {a, b, c} ∈ condorcet_complete_private_family r) :    condorcet_complete_private_relation r a ∧    condorcet_complete_private_relation r b ∧    condorcet_complete_private_relation r c ∧    ∀ s, (condorcet_complete_private_relation s a ∧      condorcet_complete_private_relation s b ∧      condorcet_complete_private_relation s c) → s = r := by  have hmem := (condorcet_complete_private_members r).2 {a, b, c} hJ  refine ⟨hmem.2.2.1 a (by simp), hmem.2.2.1 b (by simp), hmem.2.2.1 c (by simp), ?_⟩  intro s ⟨hsa, hsb, hsc⟩  apply hmem.2.2.2 s  intro x hx  simp only [mem_insert, mem_singleton] at hx  rcases hx with rfl | rfl | rfl  · exact hsa  · exact hsb  · exact hsctheorem condorcet_complete_private_complete_backward : ∀ a b c : Fin 16, a < b → b < c → ∀ r,    (condorcet_complete_private_relation r a ∧     condorcet_complete_private_relation r b ∧     condorcet_complete_private_relation r c ∧     ∀ s, (condorcet_complete_private_relation s a ∧           condorcet_complete_private_relation s b ∧           condorcet_complete_private_relation s c) → s = r) →    {a,b,c} ∈ condorcet_complete_private_family r := by decidetheorem condorcet_complete_private_complete : ∀ r a b c : Fin 16,    a < b → b < c →    ({a,b,c} ∈ condorcet_complete_private_family r ↔      condorcet_complete_private_relation r a ∧      condorcet_complete_private_relation r b ∧      condorcet_complete_private_relation r c ∧      ∀ s, (condorcet_complete_private_relation s a ∧        condorcet_complete_private_relation s b ∧        condorcet_complete_private_relation s c) → s = r) := by  intro r a b c hab hbc  constructor  · exact condorcet_complete_private_complete_forward r a b c  · exact condorcet_complete_private_complete_backward a b c hab hbc rtheorem condorcet_complete_private_flow : ∀ b : Fin 16,    3 * condorcet_complete_private_weight b =      ∑ a : Fin 16, ∑ J ∈ condorcet_complete_private_family a,        if b ∈ J then condorcet_complete_private_occupation a else 0 := by decidetheorem condorcet_complete_private_mass :    (∑ a : Fin 16, condorcet_complete_private_weight a) = 2876598259756430344 ∧    (∑ a ∈ condorcet_complete_private_set, condorcet_complete_private_weight a) = 1447017722375641758 ∧    0 < (∑ a : Fin 16, condorcet_complete_private_weight a) ∧    (∑ a : Fin 16, condorcet_complete_private_weight a) <      2 * (∑ a ∈ condorcet_complete_private_set, condorcet_complete_private_weight a) := by decidetheorem condorcet_complete_private_ordered : ∀ a b : Fin 16,    a ∈ condorcet_complete_private_set → b ∈ condorcet_complete_private_set →    condorcet_complete_private_relation a b →      condorcet_complete_private_order a < condorcet_complete_private_order b := by decidetheorem condorcet_complete_private_wellFounded :    WellFounded (fun a b : {a : Fin 16 // a ∈ condorcet_complete_private_set} =>      condorcet_complete_private_relation a.val b.val) := by  refine (measure (fun a : {a : Fin 16 // a ∈ condorcet_complete_private_set} =>    condorcet_complete_private_order a.val)).wf.mono ?_  intro a b hab  exact condorcet_complete_private_ordered a.val b.val a.property b.property habtheorem condorcet_complete_private_averaging_obstruction :    ∃ (R : Fin 16 → Fin 16 → Prop)      (F : Fin 16 → Finset (Finset (Fin 16))) (q : Fin 16 → ℕ)      (U : Finset (Fin 16)),      (∀ a, ¬ R a a) ∧      (∀ a b c, ∃ r, R r a ∧ R r b ∧ R r c) ∧      (∀ a, (F a).Nonempty ∧ ∀ J ∈ F a,        J.card = 3 ∧ a ∉ J ∧ (∀ b ∈ J, R a b) ∧        ∀ r, (∀ b ∈ J, R r b) → r = a) ∧      (∀ r a b c, a < b → b < c →        ({a,b,c} ∈ F r ↔ R r a ∧ R r b ∧ R r c ∧          ∀ s, (R s a ∧ R s b ∧ R s c) → s = r)) ∧      (∀ b, 3 * ((F b).card * q b) =        ∑ a, ∑ J ∈ F a, if b ∈ J then q a else 0) ∧      (∑ a, (F a).card * q a) = 2876598259756430344 ∧      (∑ a ∈ U, (F a).card * q a) = 1447017722375641758 ∧      0 < (∑ a, (F a).card * q a) ∧      (∑ a, (F a).card * q a) < 2 * (∑ a ∈ U, (F a).card * q a) ∧      WellFounded (fun a b : {a : Fin 16 // a ∈ U} => R a.val b.val) := by  refine ⟨condorcet_complete_private_relation, condorcet_complete_private_family,    condorcet_complete_private_occupation, condorcet_complete_private_set,    condorcet_complete_private_irreflexive, condorcet_complete_private_s3,    condorcet_complete_private_members, condorcet_complete_private_complete,    condorcet_complete_private_flow, ?_, ?_, ?_, ?_, condorcet_complete_private_wellFounded⟩  · exact condorcet_complete_private_mass.1  · exact condorcet_complete_private_mass.2.1  · exact condorcet_complete_private_mass.2.2.1  · exact condorcet_complete_private_mass.2.2.2
See it in the graphDiscuss this resultChallenge it