condorcet_product_fixed_point_acyclic_mass_obstruction
There are an irreflexive directed relation on thirteen vertices, a root map on ordered triples, and a seven-vertex induced acyclic subset. Every root is related to each sampled vertex. The map is invariant under permutations of the triple and under the two multiplicity patterns on a two-element underlying set. Each vertex is the root of exactly169 ordered inputs, so uniform iid input has uniform output. The seven-vertex acyclic subset therefore has uniform mass7/13, above half. Nevertheless this same relation has no integer acyclic half-cover for any positive voter count. The relation is allowed to have reciprocal arrows; this theorem makes no oriented or tournament assertion.
Statement
theorem condorcet_product_fixed_point_acyclic_mass_obstruction : ∃ (R : Fin 13 → Fin 13 → Prop) (f : Fin 13 → Fin 13 → Fin 13 → Fin 13) (U : Finset (Fin 13)), (∀ a, ¬ R a a) ∧ (∀ a b c, R (f a b c) a ∧ R (f a b c) b ∧ R (f a b c) c) ∧ (∀ a b c, f a b c = f b a c ∧ f a b c = f a c b) ∧ (∀ a b, f a a b = f a b b) ∧ (∀ r, (univ.filter fun t : Fin 13 × Fin 13 × Fin 13 => f t.1 t.2.1 t.2.2 = r).card = 169) ∧ U.card = 7 ∧ WellFounded (fun a b : {a : Fin 13 // a ∈ U} => R a.val b.val) ∧ (∀ (n : ℕ) (V : Fin n → Finset (Fin 13)), 0 < n → (∀ v, WellFounded (fun a b : {a : Fin 13 // a ∈ V v} => R a.val b.val)) → ¬ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ V v).card))
- Source
- IN-357 method diagnostic for the OP-19 weighted acyclic-separation route. Related product fixed-point construction: https://theorydish.blog/2026/09/11/condorcet-quintets-a-proof-from-the-book/ and https://arxiv.org/html/2609.35186 , Section3. The finite relation is a chain of seven vertices reciprocally joined to a reciprocal clique of six. This is a limitation of an arbitrary product fixed point as a pointwise acyclic separator, not an election counterexample, a limitation on optimizing vertex weights, or a new research-level election result. Computation8895 supplied the set-root assignment; all finite claims are checked by the Lean kernel.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
The proof, explained
The theorem constructs a counterexample showing that having a symmetric product root map whose output distribution assigns majority probability mass to an acyclic set does not imply the existence of an integer acyclic half-cover. On 13 vertices, a directed relation R is defined such that the subset U = {0, ..., 6} of 7 vertices forms a strictly ordered acyclic chain, while any two distinct vertices in {7, ..., 12} share reciprocal directed arrows. An explicit 13 × 13 × 13 table provides a fully symmetric, duplicate-invariant root map whose outputs are uniformly distributed across all 13 vertices, giving U mass 7/13 > 1/2. However, any acyclic set under R can contain at most one vertex from {7, ..., 12}, so assigning unit weights to {7, ..., 12} and zero elsewhere strictly separates the total acyclic weight (≤ 1) from the total population weight (6), which by the weighted half-cover exclusion principle rules out any acyclic half-cover.
For every triple of vertices (a, b, c), the root table output f(a, b, c) is related to a, to b, and to c under R automation
Verified by exhaustive finite evaluation over all 2,197 ordered triples of vertices.
theorem condorcet_acyclic_root_claims : ∀ a b c : Fin 13, condorcet_acyclic_root_relation (condorcet_acyclic_root_table a b c) a ∧ condorcet_acyclic_root_relation (condorcet_acyclic_root_table a b c) b ∧ condorcet_acyclic_root_relation (condorcet_acyclic_root_table a b c) c := by decide
The root table f is symmetric under all permutations of its three arguments automation
Verified by finite evaluation of the two generating transpositions on all triples.
theorem condorcet_acyclic_root_coherent : ∀ a b c : Fin 13, condorcet_acyclic_root_table a b c = condorcet_acyclic_root_table b a c ∧ condorcet_acyclic_root_table a b c = condorcet_acyclic_root_table a c b := by decide
The root table takes the same value on both multiplicity patterns for any two-element set: f(a, a, b) = f(a, b, b) automation
Verified by exhaustive finite evaluation over all 169 pairs of vertices.
theorem condorcet_acyclic_root_duplicates : ∀ a b : Fin 13, condorcet_acyclic_root_table a a b = condorcet_acyclic_root_table a b b := by decide
Every vertex has exactly 169 preimages under the root table, ensuring uniform output from uniform i.i.d. input automation
Since 169 × 13 = 2,197 = 13³, the fibers all have size 169. This is verified by finite counting over all inputs.
theorem condorcet_acyclic_root_uniform : ∀ r : Fin 13, (univ.filter fun t : Fin 13 × Fin 13 × Fin 13 => condorcet_acyclic_root_table t.1 t.2.1 t.2.2 = r).card = 169 := by decide
The relation R restricted to the subset of vertices with value strictly less than 7 is well-founded
Using the natural number value as a measure, if R(a, b) holds between vertices with values below 7, neither value is at least 7, forcing a < b by definition of R. Since the strict order on ℕ is well-founded, the restricted relation is well-founded.
uses
measuretheorem condorcet_acyclic_root_chain_wellFounded : WellFounded (fun a b : {a : Fin 13 // a.val < 7} => condorcet_acyclic_root_relation a.val b.val) := by refine (measure (fun a : {a : Fin 13 // a.val < 7} => a.val.val)).wf.mono ?_ intro a b hab change a.val.val < b.val.val rcases hab with ⟨_, ha | hb | h⟩ · omega · omega · exact h
Any acyclic subset of vertices can contain at most one vertex with value at least 7
If an acyclic set contained two distinct vertices with values at least 7, both directed arrows would exist between them by definition of R, forming a directed 2-cycle and contradicting asymmetry of well-founded relations.
uses
Or.inl,Ne.symmtheorem condorcet_acyclic_root_core_card (A : Finset (Fin 13)) (hA : WellFounded (fun a b : {a : Fin 13 // a ∈ A} => condorcet_acyclic_root_relation a.val b.val)) : (A.filter fun a => 7 ≤ a.val).card ≤ 1 := by classical apply card_le_one.mpr intro a ha b hb have haA := (mem_filter.mp ha).1 have hbA := (mem_filter.mp hb).1 by_contra hab have hr : condorcet_acyclic_root_relation a b := ⟨hab, Or.inl (mem_filter.mp ha).2⟩ have hs : condorcet_acyclic_root_relation b a := ⟨Ne.symm hab, Or.inl (mem_filter.mp hb).2⟩ exact hA.asymmetric (a := ⟨a,haA⟩) (b := ⟨b,hbA⟩) hr hs
For the weight function indicating values at least 7, twice the weight of any acyclic subset is strictly less than the total population weight 6
Any acyclic subset has at most one vertex with value at least 7, giving a subset weight of at most 1. The total weight across all thirteen vertices is 6, so 2 × 1 < 6 by linear arithmetic.
uses
condorcet_acyclic_root_core_card,congrArgtheorem condorcet_acyclic_root_weight_bound (A : Finset (Fin 13)) (hA : WellFounded (fun a b : {a : Fin 13 // a ∈ A} => condorcet_acyclic_root_relation a.val b.val)) : 2 * (∑ a ∈ A, if 7 ≤ a.val then (1 : ℝ) else 0) < ∑ a : Fin 13, if 7 ≤ a.val then (1 : ℝ) else 0 := by classical have hc := condorcet_acyclic_root_core_card A hA have hc' : ((A.filter fun a => 7 ≤ a.val).card : ℝ) ≤ 1 := by exact_mod_cast hc have hsum : (∑ a ∈ A, if 7 ≤ a.val then (1 : ℝ) else 0) = ((A.filter fun a => 7 ≤ a.val).card : ℝ) := by simp [← sum_filter] have hcard : (univ.filter fun a : Fin 13 => 7 ≤ a.val).card = 6 := by decide have htotal : (∑ a : Fin 13, if 7 ≤ a.val then (1 : ℝ) else 0) = 6 := by have h := congrArg (fun z : ℕ => (z : ℝ)) hcard simpa [← sum_filter] using h rw [hsum, htotal] linarith
No positive number of voters can half-cover the vertices with acyclic subsets
Assuming for contradiction that every vertex is contained in at least half the voters' subsets, the weighted half-cover exclusion principle with the indicator weight produces a contradiction from the per-voter weight bound.
uses
condorcet_half_cover_finite_weighted_half_cover_exclusion,condorcet_acyclic_root_weight_boundtheorem condorcet_acyclic_root_no_half_cover (n : ℕ) (V : Fin n → Finset (Fin 13)) (hn : 0 < n) (hV : ∀ v, WellFounded (fun a b : {a : Fin 13 // a ∈ V v} => condorcet_acyclic_root_relation a.val b.val)) : ¬ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ V v).card) := by classical intro hhalf exact condorcet_half_cover_finite_weighted_half_cover_exclusion 13 n hn V hhalf (fun a => if 7 ≤ a.val then (1 : ℝ) else 0) (fun a => by split_ifs <;> positivity) (fun v => condorcet_acyclic_root_weight_bound _ (hV v))
The relation R, root table f, and subset U = {a | a < 7} witness the obstruction, leaving irreflexivity, cardinality 7, and acyclicity of U to check
We instantiate the existential claim with R, f, and U, providing the verified root claims, symmetry, duplicate invariance, uniformity, and acyclic half-cover exclusion.
uses
condorcet_acyclic_root_claims,condorcet_acyclic_root_coherent,condorcet_acyclic_root_duplicates,condorcet_acyclic_root_uniform,condorcet_acyclic_root_no_half_covertheorem condorcet_product_fixed_point_acyclic_mass_obstruction : ∃ (R : Fin 13 → Fin 13 → Prop) (f : Fin 13 → Fin 13 → Fin 13 → Fin 13) (U : Finset (Fin 13)), (∀ a, ¬ R a a) ∧ (∀ a b c, R (f a b c) a ∧ R (f a b c) b ∧ R (f a b c) c) ∧ (∀ a b c, f a b c = f b a c ∧ f a b c = f a c b) ∧ (∀ a b, f a a b = f a b b) ∧ (∀ r, (univ.filter fun t : Fin 13 × Fin 13 × Fin 13 => f t.1 t.2.1 t.2.2 = r).card = 169) ∧ U.card = 7 ∧ WellFounded (fun a b : {a : Fin 13 // a ∈ U} => R a.val b.val) ∧ (∀ (n : ℕ) (V : Fin n → Finset (Fin 13)), 0 < n → (∀ v, WellFounded (fun a b : {a : Fin 13 // a ∈ V v} => R a.val b.val)) → ¬ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ V v).card)) := by let U : Finset (Fin 13) := univ.filter fun a => a.val < 7 refine ⟨condorcet_acyclic_root_relation, condorcet_acyclic_root_table, U, ?_, condorcet_acyclic_root_claims, condorcet_acyclic_root_coherent, condorcet_acyclic_root_duplicates, condorcet_acyclic_root_uniform, ?_, ?_, condorcet_acyclic_root_no_half_cover⟩
The relation R is irreflexive: R(a, a) is false for all vertices
By definition, R(a, a) requires a ≠ a, which simplifies to False.
· intro a simp [condorcet_acyclic_root_relation]
The subset U = {a | a < 7} contains exactly 7 vertices automation
Decided by direct finite counting of vertices strictly less than 7 in Fin 13.
· decideThe subset U is acyclic under R
The subset U is canonically identified with {a : Fin 13 // a.val < 7}. Pulling back the well-founded relation established earlier along this embedding shows well-foundedness on U.
uses
InvImage.wf,condorcet_acyclic_root_chain_wellFounded· let g : {a : Fin 13 // a ∈ U} → {a : Fin 13 // a.val < 7} := fun a => ⟨a.val, (mem_filter.mp a.property).2⟩ exact InvImage.wf g condorcet_acyclic_root_chain_wellFounded
measure- constructs a well-founded relation on a type from a measure function into the natural numbers
Or.inl- proves a disjunction a ∨ b from a proof of the left disjunct a
Ne.symm- symmetry of disequality, deducing b ≠ a from a ≠ b
condorcet_acyclic_root_core_card- any acyclic subset of thirteen vertices contains at most one vertex with value at least 7 under the root relation
congrArg- equality is preserved under applying a function to both sides
condorcet_half_cover_finite_weighted_half_cover_exclusion- forbids any half-cover when there is a non-negative weight function whose value on every voter's subset is strictly less than half the total population weight
condorcet_acyclic_root_weight_bound- for any acyclic subset, twice its weight on vertices with value at least 7 is strictly less than the total weight 6
condorcet_acyclic_root_claims- the root table outputs a vertex that relates to each of the three input vertices under the relation
condorcet_acyclic_root_coherent- the root table is invariant under transpositions of its arguments
condorcet_acyclic_root_duplicates- the root table is invariant under swapping multiplicity patterns on a two-element set
condorcet_acyclic_root_uniform- each vertex appears as the output of the root table for exactly 169 ordered input triples
condorcet_acyclic_root_no_half_cover- no family of acyclic subsets can half-cover the thirteen vertices for any positive number of voters
InvImage.wf- the inverse image of a well-founded relation under a function is well-founded
condorcet_acyclic_root_chain_wellFounded- the root relation restricted to vertices with value strictly less than 7 is well-founded
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 BigOperatorsset_option maxRecDepth 20000set_option maxHeartbeats 12000000def condorcet_acyclic_root_relation (a b : Fin 13) : Prop := a ≠ b ∧ (7 ≤ a.val ∨ 7 ≤ b.val ∨ a.val < b.val)instance : DecidableRel condorcet_acyclic_root_relation := fun a b => inferInstanceAs (Decidable (a ≠ b ∧ (7 ≤ a.val ∨ 7 ≤ b.val ∨ a.val < b.val)))def condorcet_acyclic_root_table : Fin 13 → Fin 13 → Fin 13 → Fin 13 := ![![![7,9,7,7,7,7,7,9,9,7,9,9,9],![9,9,7,7,7,7,7,9,9,10,9,10,10],![7,7,7,7,7,7,7,10,10,10,9,10,10],![7,7,7,7,7,7,7,10,10,10,9,10,10],![7,7,7,7,7,7,8,8,10,10,9,10,10],![7,7,7,7,7,7,7,8,10,10,9,10,10],![7,7,7,7,8,7,7,8,10,10,9,10,11],![9,9,10,10,8,8,8,9,9,8,8,8,8],![9,9,10,10,10,10,10,9,9,7,7,7,7],![7,10,10,10,10,10,10,8,7,7,11,10,11],![9,9,9,9,9,9,9,8,7,11,9,9,11],![9,10,10,10,10,10,10,8,7,10,9,9,10],![9,10,10,10,10,10,11,8,7,11,11,10,9]],![![9,9,7,7,7,7,7,9,9,10,9,10,10],![9,0,9,9,9,9,9,9,9,0,9,9,9],![7,9,9,11,11,11,11,11,11,11,11,10,11],![7,9,11,9,11,11,11,11,11,11,11,12,11],![7,9,11,11,9,12,12,12,12,12,12,12,11],![7,9,11,11,12,9,12,12,12,12,12,12,11],![7,9,11,11,12,12,9,12,12,12,12,12,11],![9,9,11,11,12,12,12,9,0,12,12,12,11],![9,9,11,11,12,12,12,0,9,12,12,12,11],![10,0,11,11,12,12,12,12,12,0,12,12,11],![9,9,11,11,12,12,12,12,12,12,9,12,11],![10,9,10,12,12,12,12,12,12,12,12,9,10],![10,9,11,11,11,11,11,11,11,11,11,10,9]],![![7,7,7,7,7,7,7,10,10,10,9,10,10],![7,9,9,11,11,11,11,11,11,11,11,10,11],![7,9,9,1,1,1,1,9,1,1,1,1,1],![7,11,1,1,1,1,1,8,1,1,1,1,8],![7,11,1,1,1,1,1,8,1,8,8,8,8],![7,11,1,1,1,1,1,8,1,8,8,8,8],![7,11,1,1,1,1,1,8,1,8,8,8,8],![10,11,9,8,8,8,8,9,0,0,0,0,0],![10,11,1,1,1,1,1,0,1,7,7,7,7],![10,11,1,1,8,8,8,0,7,1,0,0,0],![9,11,1,1,8,8,8,0,7,0,1,0,0],![10,10,1,1,8,8,8,0,7,0,0,1,0],![10,11,1,8,8,8,8,0,7,0,0,0,1]],![![7,7,7,7,7,7,7,10,10,10,9,10,10],![7,9,11,9,11,11,11,11,11,11,11,12,11],![7,11,1,1,1,1,1,8,1,1,1,1,8],![7,9,1,10,0,0,0,1,0,2,9,2,2],![7,11,1,0,0,0,0,8,0,2,2,2,2],![7,11,1,0,0,0,0,8,0,2,2,2,2],![7,11,1,0,0,0,0,8,0,2,2,2,2],![10,11,8,1,8,8,8,1,0,0,0,0,0],![10,11,1,0,0,0,0,0,0,2,2,2,2],![10,11,1,2,2,2,2,0,2,2,2,2,2],![9,11,1,9,2,2,2,0,2,2,9,2,2],![10,12,1,2,2,2,2,0,2,2,2,2,2],![10,11,8,2,2,2,2,0,2,2,2,2,2]],![![7,7,7,7,7,7,8,8,10,10,9,10,10],![7,9,11,11,9,12,12,12,12,12,12,12,11],![7,11,1,1,1,1,1,8,1,8,8,8,8],![7,11,1,0,0,0,0,8,0,2,2,2,2],![7,9,1,0,8,3,3,1,2,3,3,3,3],![7,12,1,0,3,3,3,3,2,3,3,3,3],![8,12,1,0,3,3,3,3,2,3,3,3,3],![8,12,8,8,1,3,3,1,3,3,3,3,3],![10,12,1,0,2,2,2,3,2,1,1,1,1],![10,12,8,2,3,3,3,3,1,3,3,3,3],![9,12,8,2,3,3,3,3,1,3,3,3,3],![10,12,8,2,3,3,3,3,1,3,3,3,3],![10,11,8,2,3,3,3,3,1,3,3,3,3]],![![7,7,7,7,7,7,7,8,10,10,9,10,10],![7,9,11,11,12,9,12,12,12,12,12,12,11],![7,11,1,1,1,1,1,8,1,8,8,8,8],![7,11,1,0,0,0,0,8,0,2,2,2,2],![7,12,1,0,3,3,3,3,2,3,3,3,3],![7,9,1,0,3,3,4,4,4,4,4,4,4],![7,12,1,0,3,4,4,4,4,4,4,4,4],![8,12,8,8,3,4,4,4,4,4,4,4,4],![10,12,1,0,2,4,4,4,4,4,4,4,4],![10,12,8,2,3,4,4,4,4,4,4,4,4],![9,12,8,2,3,4,4,4,4,4,4,4,4],![10,12,8,2,3,4,4,4,4,4,4,4,4],![10,11,8,2,3,4,4,4,4,4,4,4,4]],![![7,7,7,7,8,7,7,8,10,10,9,10,11],![7,9,11,11,12,12,9,12,12,12,12,12,11],![7,11,1,1,1,1,1,8,1,8,8,8,8],![7,11,1,0,0,0,0,8,0,2,2,2,2],![8,12,1,0,3,3,3,3,2,3,3,3,3],![7,12,1,0,3,4,4,4,4,4,4,4,4],![7,9,1,0,3,4,11,5,5,5,5,5,5],![8,12,8,8,3,4,5,5,5,5,5,5,5],![10,12,1,0,2,4,5,5,5,5,5,5,5],![10,12,8,2,3,4,5,5,5,5,5,5,5],![9,12,8,2,3,4,5,5,5,5,5,5,5],![10,12,8,2,3,4,5,5,5,5,5,5,5],![11,11,8,2,3,4,5,5,5,5,5,5,5]],![![9,9,10,10,8,8,8,9,9,8,8,8,8],![9,9,11,11,12,12,12,9,0,12,12,12,11],![10,11,9,8,8,8,8,9,0,0,0,0,0],![10,11,8,1,8,8,8,1,0,0,0,0,0],![8,12,8,8,1,3,3,1,3,3,3,3,3],![8,12,8,8,3,4,4,4,4,4,4,4,4],![8,12,8,8,3,4,5,5,5,5,5,5,5],![9,9,9,1,1,4,5,4,5,5,5,6,6],![9,0,0,0,3,4,5,5,5,5,5,5,5],![8,12,0,0,3,4,5,5,5,5,6,6,6],![8,12,0,0,3,4,5,5,5,6,5,6,6],![8,12,0,0,3,4,5,6,5,6,6,6,6],![8,11,0,0,3,4,5,6,5,6,6,6,6]],![![9,9,10,10,10,10,10,9,9,7,7,7,7],![9,9,11,11,12,12,12,0,9,12,12,12,11],![10,11,1,1,1,1,1,0,1,7,7,7,7],![10,11,1,0,0,0,0,0,0,2,2,2,2],![10,12,1,0,2,2,2,3,2,1,1,1,1],![10,12,1,0,2,4,4,4,4,4,4,4,4],![10,12,1,0,2,4,5,5,5,5,5,5,5],![9,0,0,0,3,4,5,5,5,5,5,5,5],![9,9,1,0,2,4,5,5,6,6,6,6,6],![7,12,7,2,1,4,5,5,6,6,6,6,6],![7,12,7,2,1,4,5,5,6,6,6,6,6],![7,12,7,2,1,4,5,5,6,6,6,6,6],![7,11,7,2,1,4,5,5,6,6,6,6,6]],![![7,10,10,10,10,10,10,8,7,7,11,10,11],![10,0,11,11,12,12,12,12,12,0,12,12,11],![10,11,1,1,8,8,8,0,7,1,0,0,0],![10,11,1,2,2,2,2,0,2,2,2,2,2],![10,12,8,2,3,3,3,3,1,3,3,3,3],![10,12,8,2,3,4,4,4,4,4,4,4,4],![10,12,8,2,3,4,5,5,5,5,5,5,5],![8,12,0,0,3,4,5,5,5,5,6,6,6],![7,12,7,2,1,4,5,5,6,6,6,6,6],![7,0,1,2,3,4,5,5,6,12,6,6,6],![11,12,0,2,3,4,5,6,6,6,6,6,6],![10,12,0,2,3,4,5,6,6,6,6,6,6],![11,11,0,2,3,4,5,6,6,6,6,6,6]],![![9,9,9,9,9,9,9,8,7,11,9,9,11],![9,9,11,11,12,12,12,12,12,12,9,12,11],![9,11,1,1,8,8,8,0,7,0,1,0,0],![9,11,1,9,2,2,2,0,2,2,9,2,2],![9,12,8,2,3,3,3,3,1,3,3,3,3],![9,12,8,2,3,4,4,4,4,4,4,4,4],![9,12,8,2,3,4,5,5,5,5,5,5,5],![8,12,0,0,3,4,5,5,5,6,5,6,6],![7,12,7,2,1,4,5,5,6,6,6,6,6],![11,12,0,2,3,4,5,6,6,6,6,6,6],![9,9,1,9,3,4,5,5,6,6,1,6,6],![9,12,0,2,3,4,5,6,6,6,6,6,6],![11,11,0,2,3,4,5,6,6,6,6,6,6]],![![9,10,10,10,10,10,10,8,7,10,9,9,10],![10,9,10,12,12,12,12,12,12,12,12,9,10],![10,10,1,1,8,8,8,0,7,0,0,1,0],![10,12,1,2,2,2,2,0,2,2,2,2,2],![10,12,8,2,3,3,3,3,1,3,3,3,3],![10,12,8,2,3,4,4,4,4,4,4,4,4],![10,12,8,2,3,4,5,5,5,5,5,5,5],![8,12,0,0,3,4,5,6,5,6,6,6,6],![7,12,7,2,1,4,5,5,6,6,6,6,6],![10,12,0,2,3,4,5,6,6,6,6,6,6],![9,12,0,2,3,4,5,6,6,6,6,6,6],![9,9,1,2,3,4,5,6,6,6,6,2,6],![10,10,0,2,3,4,5,6,6,6,6,6,6]],![![9,10,10,10,10,10,11,8,7,11,11,10,9],![10,9,11,11,11,11,11,11,11,11,11,10,9],![10,11,1,8,8,8,8,0,7,0,0,0,1],![10,11,8,2,2,2,2,0,2,2,2,2,2],![10,11,8,2,3,3,3,3,1,3,3,3,3],![10,11,8,2,3,4,4,4,4,4,4,4,4],![11,11,8,2,3,4,5,5,5,5,5,5,5],![8,11,0,0,3,4,5,6,5,6,6,6,6],![7,11,7,2,1,4,5,5,6,6,6,6,6],![11,11,0,2,3,4,5,6,6,6,6,6,6],![11,11,0,2,3,4,5,6,6,6,6,6,6],![10,10,0,2,3,4,5,6,6,6,6,6,6],![9,9,1,2,3,4,5,6,6,6,6,6,5]]]theorem condorcet_acyclic_root_claims : ∀ a b c : Fin 13, condorcet_acyclic_root_relation (condorcet_acyclic_root_table a b c) a ∧ condorcet_acyclic_root_relation (condorcet_acyclic_root_table a b c) b ∧ condorcet_acyclic_root_relation (condorcet_acyclic_root_table a b c) c := by decidetheorem condorcet_acyclic_root_coherent : ∀ a b c : Fin 13, condorcet_acyclic_root_table a b c = condorcet_acyclic_root_table b a c ∧ condorcet_acyclic_root_table a b c = condorcet_acyclic_root_table a c b := by decidetheorem condorcet_acyclic_root_duplicates : ∀ a b : Fin 13, condorcet_acyclic_root_table a a b = condorcet_acyclic_root_table a b b := by decidetheorem condorcet_acyclic_root_uniform : ∀ r : Fin 13, (univ.filter fun t : Fin 13 × Fin 13 × Fin 13 => condorcet_acyclic_root_table t.1 t.2.1 t.2.2 = r).card = 169 := by decidetheorem condorcet_acyclic_root_chain_wellFounded : WellFounded (fun a b : {a : Fin 13 // a.val < 7} => condorcet_acyclic_root_relation a.val b.val) := by refine (measure (fun a : {a : Fin 13 // a.val < 7} => a.val.val)).wf.mono ?_ intro a b hab change a.val.val < b.val.val rcases hab with ⟨_, ha | hb | h⟩ · omega · omega · exact htheorem condorcet_acyclic_root_core_card (A : Finset (Fin 13)) (hA : WellFounded (fun a b : {a : Fin 13 // a ∈ A} => condorcet_acyclic_root_relation a.val b.val)) : (A.filter fun a => 7 ≤ a.val).card ≤ 1 := by classical apply card_le_one.mpr intro a ha b hb have haA := (mem_filter.mp ha).1 have hbA := (mem_filter.mp hb).1 by_contra hab have hr : condorcet_acyclic_root_relation a b := ⟨hab, Or.inl (mem_filter.mp ha).2⟩ have hs : condorcet_acyclic_root_relation b a := ⟨Ne.symm hab, Or.inl (mem_filter.mp hb).2⟩ exact hA.asymmetric (a := ⟨a,haA⟩) (b := ⟨b,hbA⟩) hr hstheorem condorcet_acyclic_root_weight_bound (A : Finset (Fin 13)) (hA : WellFounded (fun a b : {a : Fin 13 // a ∈ A} => condorcet_acyclic_root_relation a.val b.val)) : 2 * (∑ a ∈ A, if 7 ≤ a.val then (1 : ℝ) else 0) < ∑ a : Fin 13, if 7 ≤ a.val then (1 : ℝ) else 0 := by classical have hc := condorcet_acyclic_root_core_card A hA have hc' : ((A.filter fun a => 7 ≤ a.val).card : ℝ) ≤ 1 := by exact_mod_cast hc have hsum : (∑ a ∈ A, if 7 ≤ a.val then (1 : ℝ) else 0) = ((A.filter fun a => 7 ≤ a.val).card : ℝ) := by simp [← sum_filter] have hcard : (univ.filter fun a : Fin 13 => 7 ≤ a.val).card = 6 := by decide have htotal : (∑ a : Fin 13, if 7 ≤ a.val then (1 : ℝ) else 0) = 6 := by have h := congrArg (fun z : ℕ => (z : ℝ)) hcard simpa [← sum_filter] using h rw [hsum, htotal] linariththeorem condorcet_acyclic_root_no_half_cover (n : ℕ) (V : Fin n → Finset (Fin 13)) (hn : 0 < n) (hV : ∀ v, WellFounded (fun a b : {a : Fin 13 // a ∈ V v} => condorcet_acyclic_root_relation a.val b.val)) : ¬ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ V v).card) := by classical intro hhalf exact condorcet_half_cover_finite_weighted_half_cover_exclusion 13 n hn V hhalf (fun a => if 7 ≤ a.val then (1 : ℝ) else 0) (fun a => by split_ifs <;> positivity) (fun v => condorcet_acyclic_root_weight_bound _ (hV v))theorem condorcet_product_fixed_point_acyclic_mass_obstruction : ∃ (R : Fin 13 → Fin 13 → Prop) (f : Fin 13 → Fin 13 → Fin 13 → Fin 13) (U : Finset (Fin 13)), (∀ a, ¬ R a a) ∧ (∀ a b c, R (f a b c) a ∧ R (f a b c) b ∧ R (f a b c) c) ∧ (∀ a b c, f a b c = f b a c ∧ f a b c = f a c b) ∧ (∀ a b, f a a b = f a b b) ∧ (∀ r, (univ.filter fun t : Fin 13 × Fin 13 × Fin 13 => f t.1 t.2.1 t.2.2 = r).card = 169) ∧ U.card = 7 ∧ WellFounded (fun a b : {a : Fin 13 // a ∈ U} => R a.val b.val) ∧ (∀ (n : ℕ) (V : Fin n → Finset (Fin 13)), 0 < n → (∀ v, WellFounded (fun a b : {a : Fin 13 // a ∈ V v} => R a.val b.val)) → ¬ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ V v).card)) := by let U : Finset (Fin 13) := univ.filter fun a => a.val < 7 refine ⟨condorcet_acyclic_root_relation, condorcet_acyclic_root_table, U, ?_, condorcet_acyclic_root_claims, condorcet_acyclic_root_coherent, condorcet_acyclic_root_duplicates, condorcet_acyclic_root_uniform, ?_, ?_, condorcet_acyclic_root_no_half_cover⟩ · intro a simp [condorcet_acyclic_root_relation] · decide · let g : {a : Fin 13 // a ∈ U} → {a : Fin 13 // a.val < 7} := fun a => ⟨a.val, (mem_filter.mp a.property).2⟩ exact InvImage.wf g condorcet_acyclic_root_chain_wellFounded