AFTD Auto-Formalizing Theoretical Domains

condorcet_minimal_private_obstruction_no_half_cover

theoremverified

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
Used by 1

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.

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

    line 11

        (∑ a ∈ A, condorcet_minimal_private_separator_weight a) ≤ 6 := by decide
  2. 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.

    lines 18–20

    uses condorcet_minimal_private_separator_check

      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)
  3. 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 ℝ.

    lines 21–25

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

    lines 26–27

      rw [htotalR]
      linarith
  5. 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.

    lines 34–35

      classical
      intro hhalf
  6. A 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.

    lines 36–38

    uses condorcet_half_cover_finite_weighted_half_cover_exclusion, Nat.cast_nonneg, condorcet_minimal_private_acyclic_weight_bound

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

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