condorcet_complete_private_averaging_obstruction
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.
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.
¬condorcet_complete_private_relation a a := by decide
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.
condorcet_complete_private_relation r c := by decide
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).
uses
List.mem_toFinset.mp,of_decide_eq_true,List.all_eq_true.mphave 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)
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.
uses
condorcet_complete_private_members,mem_insert,mem_singletonhave 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
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.
{a,b,c} ∈ condorcet_complete_private_family r := by decideFor 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).
uses
condorcet_complete_private_complete_forward,condorcet_complete_private_complete_backwardintro 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
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.
if b ∈ J then condorcet_complete_private_occupation a else 0 := by decide
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.
2 * (∑ a ∈ condorcet_complete_private_set, condorcet_complete_private_weight a) := by decide
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).
condorcet_complete_private_order a < condorcet_complete_private_order b := by decide
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.
uses
measure,condorcet_complete_private_orderedrefine (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
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.
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.2refine ⟨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.
- Several steps (irreflexivity, the S_3 common predecessor property, private list validity, backward completeness, flow conservation, weight computations, and edge monotonicity) are proved by Lean's decider tactic (`decide`), which verifies the finite combinatorial properties via exhaustive computational evaluation.
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.
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