condorcet_minimal_private_obstruction_no_half_cover
The explicit eight-vertex globally minimal averaging obstruction has no integer acyclic half-cover with a positive number of sets. Its failure concerns the uniform averaging construction only.
Statement
theorem condorcet_minimal_private_obstruction_no_half_cover (n : ℕ) (U : Fin n → Finset (Fin 8)) (hn : 0 < n) (hU : ∀ v, WellFounded (fun a b : {a : Fin 8 // a ∈ U v} => condorcet_minimal_private_relation a.val b.val)) : ¬ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ U v).card)
- Source
- IN-362 scope check for the eight-vertex minimum-core averaging diagnostic in OP-19. No new election bound or research advance.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- condorcet_minimal_private_averaging_obstructionThere exist an irreflexive directed relation R on eight vertices, nonempty complete families F(a) of private three-element sets at each…
- 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…
- Used by 1
- condorcet_stationary_policy_strict_unrestricted_gapFor the existing integer weights [1,1,1,1,4,1,3,4] of total16 on the explicit eight-vertex relation, every induced acyclic subset has at…
The proof, explained
The theorem proves that an explicit eight-vertex relation admits no acyclic half-cover by n > 0 sets, meaning no family of acyclic subsets can cover each vertex at least n/2 times. The proof uses an explicit separator weight vector w = (1, 1, 1, 1, 4, 1, 3, 4) with total weight 16. Exhaustive finite verification shows that every 2-cycle-free (and hence every acyclic) subset has weight at most 6, which implies that twice its weight is strictly less than the total weight 16. By a double-counting argument (the weighted half-cover exclusion principle), a half-cover would force the average weight of the subsets to be at least half the total weight, contradicting the strict upper bound.
Every subset of the eight vertices containing no 2-cycles under condorcet_minimal_private_relation has separator weight at most 6. automation
The ground set has 8 vertices, so there are 2^8 = 256 subsets. The decide tactic checks each subset by exhaustive finite computation, verifying that whenever a subset contains no mutually opposing directed edges, the sum of weights from the vector (1, 1, 1, 1, 4, 1, 3, 4) is at most 6.
(∑ a ∈ A, condorcet_minimal_private_separator_weight a) ≤ 6 := by decide
For any subset A on which the relation is well-founded, the sum of separator weights of elements in A is at most 6.
A well-founded relation is asymmetric, so no two vertices in A can form a 2-cycle. Thus the premise of condorcet_minimal_private_separator_check is satisfied on A, yielding ∑ a ∈ A, w(a) ≤ 6.
uses
condorcet_minimal_private_separator_checkhave hbound := condorcet_minimal_private_separator_check A (by intro a ha b hb ⟨hab,hba⟩ exact hA.asymmetric (a := ⟨a,ha⟩) (b := ⟨b,hb⟩) hab hba)
The separator weight of any acyclic subset A is at most 6 in ℝ, and the total separator weight of all eight vertices is 16.
Casting the inequality ∑ a ∈ A, w(a) ≤ 6 to the reals gives the upper bound in ℝ. Separately, summing the explicit weights (1, 1, 1, 1, 4, 1, 3, 4) over all 8 vertices evaluates to 16 by finite computation (decide), which is also cast to ℝ.
have hreal : (∑ a ∈ A, (condorcet_minimal_private_separator_weight a : ℝ)) ≤ 6 := by exact_mod_cast hbound have htotal : (∑ a : Fin 8, condorcet_minimal_private_separator_weight a) = 16 := by decide have htotalR : (∑ a : Fin 8, (condorcet_minimal_private_separator_weight a : ℝ)) = 16 := by exact_mod_cast htotal
For any acyclic subset A, twice its separator weight is strictly less than the total weight: 2 * ∑ a ∈ A, w(a) < ∑ a, w(a).
Rewriting the total weight as 16, linear arithmetic (linarith) concludes that 2 * ∑ a ∈ A, w(a) ≤ 2 * 6 = 12 < 16.
rw [htotalR] linarith
Assume for contradiction that the family of acyclic sets (U v) forms a half-cover.
Assuming the negation introduces the hypothesis hhalf that every vertex a is contained in at least n/2 of the sets U v (that is, n ≤ 2 * #{v | a ∈ U v}). Classical reasoning is enabled to allow decidability of set memberships.
classical intro hhalfA contradiction is reached, proving that no acyclic half-cover can exist.
The finite weighted half-cover exclusion principle condorcet_half_cover_finite_weighted_half_cover_exclusion derives False from the positive size n > 0, the half-cover hypothesis hhalf, the non-negativity of weights via Nat.cast_nonneg, and the strict weight bound 2 * ∑ a ∈ U v, w(a) < ∑ a, w(a) established by condorcet_minimal_private_acyclic_weight_bound for each acyclic set U v.
uses
condorcet_half_cover_finite_weighted_half_cover_exclusion,Nat.cast_nonneg,condorcet_minimal_private_acyclic_weight_boundexact condorcet_half_cover_finite_weighted_half_cover_exclusion 8 n hn U hhalf (fun a => (condorcet_minimal_private_separator_weight a : ℝ)) (fun a => Nat.cast_nonneg _) (fun v => condorcet_minimal_private_acyclic_weight_bound _ (hU v))
condorcet_minimal_private_separator_check- For any subset A of {0, ..., 7}, if A contains no 2-cycles under the relation, then the sum of the separator weights of elements in A is at most 6.
condorcet_half_cover_finite_weighted_half_cover_exclusion- If a finite family of n > 0 subsets forms a half-cover of an m-element set, then there cannot exist non-negative weights on the ground set such that twice the weight of each subset is strictly less than the total weight.
Nat.cast_nonneg- The cast of any natural number into an ordered semiring or ring (such as ℝ) is non-negative.
condorcet_minimal_private_acyclic_weight_bound- If the restriction of the relation to a subset A of {0, ..., 7} is well-founded, then twice the separator weight of A is strictly less than the total separator weight of all 8 vertices.
- The lemma condorcet_minimal_private_separator_check (line 11) is proved entirely by kernel evaluation (decide), which tests all 256 subsets of Fin 8 by brute force.
- The total weight calculation ∑ a : Fin 8, condorcet_minimal_private_separator_weight a = 16 (line 23) is likewise discharged by decide.
- The transitions between natural numbers and real numbers (lines 21-25) are formal type casts handled by exact_mod_cast.
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 maxHeartbeats 4000000set_option maxRecDepth 10000def condorcet_minimal_private_separator_weight : Fin 8 → ℕ := ![1,1,1,1,4,1,3,4]theorem condorcet_minimal_private_separator_check : ∀ A : Finset (Fin 8), (∀ a ∈ A, ∀ b ∈ A, ¬ (condorcet_minimal_private_relation a b ∧ condorcet_minimal_private_relation b a)) → (∑ a ∈ A, condorcet_minimal_private_separator_weight a) ≤ 6 := by decidetheorem condorcet_minimal_private_acyclic_weight_bound (A : Finset (Fin 8)) (hA : WellFounded (fun a b : {a : Fin 8 // a ∈ A} => condorcet_minimal_private_relation a.val b.val)) : 2 * (∑ a ∈ A, (condorcet_minimal_private_separator_weight a : ℝ)) < ∑ a : Fin 8, (condorcet_minimal_private_separator_weight a : ℝ) := by have hbound := condorcet_minimal_private_separator_check A (by intro a ha b hb ⟨hab,hba⟩ exact hA.asymmetric (a := ⟨a,ha⟩) (b := ⟨b,hb⟩) hab hba) have hreal : (∑ a ∈ A, (condorcet_minimal_private_separator_weight a : ℝ)) ≤ 6 := by exact_mod_cast hbound have htotal : (∑ a : Fin 8, condorcet_minimal_private_separator_weight a) = 16 := by decide have htotalR : (∑ a : Fin 8, (condorcet_minimal_private_separator_weight a : ℝ)) = 16 := by exact_mod_cast htotal rw [htotalR] linariththeorem condorcet_minimal_private_obstruction_no_half_cover (n : ℕ) (U : Fin n → Finset (Fin 8)) (hn : 0 < n) (hU : ∀ v, WellFounded (fun a b : {a : Fin 8 // a ∈ U v} => condorcet_minimal_private_relation a.val b.val)) : ¬ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ U v).card) := by classical intro hhalf exact condorcet_half_cover_finite_weighted_half_cover_exclusion 8 n hn U hhalf (fun a => (condorcet_minimal_private_separator_weight a : ℝ)) (fun a => Nat.cast_nonneg _) (fun v => condorcet_minimal_private_acyclic_weight_bound _ (hU v))