AFTD Auto-Formalizing Theoretical Domains

condorcet_six_balanced_has_winning_three_set

theoremverified

Open sub-problem: every six-candidate election with at least one voter in which every three-candidate set contains the top choice of at most half of the voters has a Condorcet winning set of size at most three.

Statement

theorem condorcet_six_balanced_has_winning_three_set (n : ℕ) (P : Fin n → Equiv.Perm (Fin 6))
    (hn : 0 < n)
    (hbal : ∀ S : Finset (Fin 6), S.card = 3 →
      2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by norm_num⟩ ∈ S).card ≤ n) :
    ∃ S : Finset (Fin 6), S.card ≤ 3 ∧ is_condorcet_winning_set P S
Source
step towards condorcet_dimension_le_three
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • condorcet_six_balanced_top_structureWith six candidates, if every three-candidate set contains the top choice of at most half of the voters, then the top-choice profile is…
  • is_condorcet_winning_setWith n voters holding strict rankings of m candidates, S is a Condorcet winning set if for every candidate a ∉ S, strictly fewer than n/2…

The proof, explained

We prove by contradiction that a Condorcet winning set of size at most three must exist. Under the balanced condition, an existing structural lemma shows that all six candidates are top-ranked by an equal number of voters, k = n / 6. If no three-candidate set were Condorcet winning, every such set A would be dominated on all 3k voters outside A's top choices by some external candidate a; this implies a strict pairing property forcing any two voters with distinct top choices to have one's second choice equal the other's top choice. Finally, selecting a voter top-ranking 0 alongside two voters top-ranking distinct non-zero candidates violates this pairing property, yielding a contradiction.

  1. Every candidate is the top choice of exactly n / 6 voters.

    Line 5 verifies 0 < 6 to form the top-rank index 0. We define top(v) and snd(v) to be the candidates ranked at positions 0 and 1 by voter v. Applying the lemma condorcet_six_balanced_top_structure to the balanced regime hypothesis shows that the number of voters top-ranking candidate c satisfies 6 * |{v | top(v) = c}| = n for every candidate c.

    lines 5–13

    uses condorcet_six_balanced_top_structure

          2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by norm_num⟩ ∈ S).card ≤ n) :
        ∃ S : Finset (Fin 6), S.card ≤ 3 ∧ is_condorcet_winning_set P S := by
      classical
      set top : Fin n → Fin 6 := fun v => (P v).symm ⟨0, by norm_num⟩ with htopdef
      set snd : Fin n → Fin 6 := fun v => (P v).symm ⟨1, by norm_num⟩ with hsnddef
      have hstr : ∀ c : Fin 6, 6 * (Finset.univ.filter fun v => top v = c).card = n := by
        intro c
        have := condorcet_six_balanced_top_structure n P hbal c
        simpa only [htopdef] using this
  2. Setting k = n / 6, we have n = 6k with k > 0, every candidate is top-ranked by exactly k voters, and no voter's first and second choices coincide.

    Defining k as the number of voters who top-rank candidate 0, we have n = 6k. By Nat.eq_of_mul_eq_mul_left, every candidate c is the top choice of exactly k voters. Since n > 0, k is strictly positive, so by Finset.card_pos.mp every candidate appears as the top choice of at least one voter. Furthermore, snd(v) ≠ top(v) because their ranks under P(v) are 1 and 0 respectively.

    lines 14–37

    uses Nat.eq_of_mul_eq_mul_left, Finset.card_pos.mp

      set k : ℕ := (Finset.univ.filter fun v => top v = 0).card with hkdef
      have hn6 : n = 6 * k := by
        have h0 := hstr 0
        rw [← hkdef] at h0
        omega
      have hkc : ∀ c : Fin 6, (Finset.univ.filter fun v => top v = c).card = k := by
        intro c
        have h := hstr c
        have hgoal : 6 * (Finset.univ.filter fun v => top v = c).card = 6 * k := by omega
        exact Nat.eq_of_mul_eq_mul_left (n := 6) (by norm_num) hgoal
      have hkpos : 0 < k := by omega
      have htop_exists : ∀ c : Fin 6, ∃ v, top v = c := by
        intro c
        have hpos : 0 < (Finset.univ.filter fun v => top v = c).card := by
          rw [hkc c]; exact hkpos
        obtain ⟨v, hv⟩ := Finset.card_pos.mp hpos
        exact ⟨v, by simpa using hv⟩
      have hpos_top : ∀ v, P v (top v) = 0 := by intro v; simp [top]
      have hpos_snd : ∀ v, P v (snd v) = 1 := by intro v; simp [snd]
      have hsnd_ne_top : ∀ v, snd v ≠ top v := by
        intro v h
        have h1 := hpos_snd v
        rw [h, hpos_top v] at h1
        simp at h1
  3. We may assume, for contradiction, that no three-candidate set is a Condorcet winning set.

    We perform a case split on whether there exists a three-candidate Condorcet winning set. If one exists, the existential goal is immediately witnessed by it. Thus we assume the negative: every three-candidate set fails to be a Condorcet winning set.

    lines 38–44

      by_cases hwin : ∃ A : Finset (Fin 6), A.card = 3 ∧ is_condorcet_winning_set P A
      · obtain ⟨A, hAc, hw⟩ := hwin
        exact ⟨A, by omega, hw⟩
      · exfalso
        have hwin' : ∀ A : Finset (Fin 6), A.card = 3 → ¬ is_condorcet_winning_set P A := by
          intro A hA hw
          exact hwin ⟨A, hA, hw⟩
  4. For any three-candidate set A, exactly 3k voters have their top choice outside A.

    The voters whose top choice is in A form a disjoint union over the elements of A (by Finset.card_biUnion and Finset.disjoint_left). Since each candidate is top-ranked by k voters, exactly 3k voters have their top choice in A (using Finset.sum_const). Subtracting this from the total of n = 6k voters (via Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, and Fintype.card_fin) leaves exactly 6k - 3k = 3k voters whose top choice is not in A.

    lines 45–69

    uses Finset.disjoint_left, Finset.card_biUnion, Finset.sum_const, Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Fintype.card_fin

        have hA0card : ∀ A : Finset (Fin 6), A.card = 3 →
            (Finset.univ.filter fun v => top v ∉ A).card = 3 * k := by
          intro A hA
          have hdisj : ∀ c ∈ A, ∀ d ∈ A, c ≠ d →
              Disjoint (Finset.univ.filter fun v => top v = c)
                (Finset.univ.filter fun v => top v = d) := by
            intro c _ d _ hcd
            rw [Finset.disjoint_left]
            intro v hv hv'
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv hv'
            exact hcd (hv.symm.trans hv')
          have hbij : (Finset.univ.filter fun v => top v ∈ A)
              = A.biUnion (fun c => Finset.univ.filter fun v => top v = c) := by
            ext v
            simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and]
            exact ⟨fun hv => ⟨top v, hv, rfl⟩, fun ⟨c, hc, hvc⟩ => hvc ▸ hc⟩
          have hIn : (Finset.univ.filter fun v => top v ∈ A).card = 3 * k := by
            rw [hbij, Finset.card_biUnion hdisj,
              Finset.sum_congr rfl (fun c (_ : c ∈ A) => hkc c), Finset.sum_const, hA]
            simp
          have hcompl : (Finset.univ.filter fun v => top v ∉ A)
              = Finset.univ \ (Finset.univ.filter fun v => top v ∈ A) := by
            ext v; simp
          rw [hcompl, Finset.card_sdiff, Finset.inter_univ, hIn, Finset.card_univ, Fintype.card_fin]
          omega
  5. For any three-candidate set A, some candidate a ∉ A beats every member of A in the eyes of all 3k voters whose top choice is outside A.

    Because A is not a Condorcet winning set, there is some external candidate a ∉ A preferred to all elements of A by at least n / 2 = 3k voters. But no voter v whose top choice lies in A can prefer a to top(v), since top(v) has the minimal rank 0 (Fin.zero_le, not_lt.mpr). Hence the voters who prefer a to all of A form a subset of the 3k voters with top choice outside A. Having cardinality at least 3k, this subset must equal the entire set of 3k outside voters (Finset.eq_of_subset_of_card_le).

    lines 70–105

    uses Fin.zero_le, not_lt.mpr, Finset.eq_of_subset_of_card_le

        have hwit : ∀ A : Finset (Fin 6), A.card = 3 → ∃ a, a ∉ A ∧
            ∀ v, top v ∉ A → ∀ b ∈ A, P v a < P v b := by
          intro A hA
          have hnot := hwin' A hA
          have hA0c : (Finset.univ.filter fun v => top v ∉ A).card = 3 * k := hA0card A hA
          have hbadIn : ∀ a, (Finset.univ.filter fun v => ∀ b ∈ A, P v a < P v b)
              ⊆ (Finset.univ.filter fun v => top v ∉ A) := by
            intro a v hv
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢
            intro htopA
            have h1 : P v a < P v (top v) := hv (top v) htopA
            rw [hpos_top v] at h1
            exact absurd h1 (not_lt.mpr (Fin.zero_le (P v a)))
          have hex : ∃ a, a ∉ A ∧
              n ≤ 2 * (Finset.univ.filter fun v => ∀ b ∈ A, P v a < P v b).card := by
            by_contra hc
            apply hnot
            unfold is_condorcet_winning_set
            intro a ha
            by_contra hlt
            exact hc ⟨a, ha, by omega⟩
          obtain ⟨a, haA, hge⟩ := hex
          refine ⟨a, haA, ?_⟩
          have hcard : (Finset.univ.filter fun v => top v ∉ A).card ≤
              (Finset.univ.filter fun v => ∀ b ∈ A, P v a < P v b).card := by
            rw [hA0c]; omega
          have heq : (Finset.univ.filter fun v => ∀ b ∈ A, P v a < P v b)
              = (Finset.univ.filter fun v => top v ∉ A) :=
            Finset.eq_of_subset_of_card_le (hbadIn a) hcard
          intro v hv b hb
          have hmem : v ∈ Finset.univ.filter (fun w => ∀ b ∈ A, P w a < P w b) := by
            rw [heq]
            simp only [Finset.mem_filter, Finset.mem_univ, true_and]
            exact hv
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hmem
          exact hmem b hb
  6. If candidate a dominates A on all outside voters, and a voter v has top choice outside A and second choice in A, then a must be v's top choice.

    Since snd(v) ∈ A and top(v) ∉ A, voter v prefers a to snd(v), which means P(v)(a) < P(v)(snd(v)) = 1 (Fin.lt_def). The only rank strictly less than 1 is 0 (Fin.ext), so P(v)(a) = 0 = P(v)(top(v)). Permutation injectivity then forces a = top(v).

    lines 106–120

    uses Fin.lt_def, Fin.ext

        have hkey1 : ∀ (A : Finset (Fin 6)) (a : Fin 6), A.card = 3 → a ∉ A →
            (∀ v, top v ∉ A → ∀ b ∈ A, P v a < P v b) →
            ∀ v, top v ∉ A → snd v ∈ A → a = top v := by
          intro A a hAc haA hdom v htv hsv
          have h1 : P v a < P v (snd v) := hdom v htv (snd v) hsv
          rw [hpos_snd v] at h1
          have hval : ((P v a) : ℕ) = 0 := by
            have h2 : ((P v a) : ℕ) < 1 := by
              have h3 := h1
              rw [Fin.lt_def] at h3
              simpa using h3
            omega
          have h0 : P v a = 0 := Fin.ext (by simpa using hval)
          refine (P v).injective ?_
          rw [h0, hpos_top v]
  7. For any two voters v and w with different top choices, either v's second choice is w's top choice, or w's second choice is v's top choice.

    Suppose neither holds. The set B of candidates other than top(v) and top(w) has size 4 (Finset.card_sdiff). Both snd(v) and snd(w) belong to B, and since |{snd(v), snd(w)}| ≤ 2 < 4 (Finset.card_insert_le, Finset.card_insert_of_notMem), there exists some candidate c ∈ B \ {snd(v), snd(w)} (Finset.exists_mem_notMem_of_card_lt_card). Removing c yields a three-candidate set A = B \ {c} (Finset.card_erase_of_mem) that contains both snd(v) and snd(w) but neither top(v) nor top(w). The dominating candidate a for A must then equal top(v) (from voter v) and top(w) (from voter w), forcing top(v) = top(w), which contradicts top(v) ≠ top(w).

    lines 121–173

    uses Finset.card_insert_of_notMem, Finset.card_insert_le, Finset.exists_mem_notMem_of_card_lt_card, Finset.card_erase_of_mem

        have hpair : ∀ v w : Fin n, top v ≠ top w → snd v = top w ∨ snd w = top v := by
          intro v w hne
          by_contra hcon
          push_neg at hcon
          obtain ⟨hvw, hwv⟩ := hcon
          have hs1 : snd v ≠ top v := hsnd_ne_top v
          have hs2 : snd w ≠ top w := hsnd_ne_top w
          set B : Finset (Fin 6) := Finset.univ \ {top v, top w} with hBdef
          have hBcard : B.card = 4 := by
            have h2 : ({top v, top w} : Finset (Fin 6)).card = 2 := by
              rw [Finset.card_insert_of_notMem (by simpa using hne)]
              simp
            rw [hBdef, Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Fintype.card_fin, h2]
          have hsB : snd v ∈ B := by
            rw [hBdef]
            simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton,
              not_or, true_and]
            exact ⟨hs1, hvw⟩
          have hwB : snd w ∈ B := by
            rw [hBdef]
            simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton,
              not_or, true_and]
            exact ⟨hwv, hs2⟩
          have hsmall : ({snd v, snd w} : Finset (Fin 6)).card < B.card := by
            have h2 : ({snd v, snd w} : Finset (Fin 6)).card ≤ 2 := by
              have h3 := Finset.card_insert_le (snd v) ({snd w} : Finset (Fin 6))
              simpa using h3
            omega
          obtain ⟨c, hcB, hc2⟩ := Finset.exists_mem_notMem_of_card_lt_card hsmall
          have hcv : snd v ≠ c := by
            intro h
            apply hc2
            rw [← h]
            exact Finset.mem_insert_self (snd v) {snd w}
          have hcw : snd w ≠ c := by
            intro h
            apply hc2
            rw [← h]
            exact Finset.mem_insert_of_mem (Finset.mem_singleton_self (snd w))
          have htvB : top v ∉ B := by rw [hBdef]; simp
          have htwB : top w ∉ B := by rw [hBdef]; simp
          have hAcard : (B.erase c).card = 3 := by
            rw [Finset.card_erase_of_mem hcB, hBcard]
          obtain ⟨a, haA, hdom⟩ := hwit (B.erase c) hAcard
          have htvA : top v ∉ B.erase c := fun h => htvB (Finset.erase_subset c B h)
          have htwA : top w ∉ B.erase c := fun h => htwB (Finset.erase_subset c B h)
          have hsvA : snd v ∈ B.erase c := by
            rw [Finset.mem_erase]; exact ⟨hcv, hsB⟩
          have hswA : snd w ∈ B.erase c := by
            rw [Finset.mem_erase]; exact ⟨hcw, hwB⟩
          have hav : a = top v := hkey1 (B.erase c) a hAcard haA hdom v htvA hsvA
          have haw : a = top w := hkey1 (B.erase c) a hAcard haA hdom w htwA hswA
          exact hne (hav.symm.trans haw)
  8. The pairing property leads to a contradiction, concluding that a winning three-candidate set exists.

    Let v₀ be a voter top-ranking 0. Excluding {0, snd(v₀)} leaves 4 candidates, from which we choose two distinct candidates t', t'' (Finset.card_insert_of_notMem, Finset.one_lt_card.mp). Let w', w'' be voters top-ranking t' and t''. The pairing property between v₀ and w' forces snd(w') = 0 because t' ≠ snd(v₀). Similarly, pairing v₀ with w'' forces snd(w'') = 0. But then pairing w' and w'' (whose top choices t' ≠ t'' differ) forces either snd(w') = t'' (hence 0 = t'') or snd(w'') = t' (hence 0 = t'), both contradicting that t', t'' ≠ 0.

    lines 174–210

    uses Finset.card_insert_of_notMem, Finset.one_lt_card.mp

        obtain ⟨v0, hv0⟩ := htop_exists 0
        have hs0ne : snd v0 ≠ 0 := by
          have h := hsnd_ne_top v0
          rwa [hv0] at h
        obtain ⟨t', t'', ht'0, ht'2, ht''0, ht''2, ht'ne⟩ : ∃ t' t'' : Fin 6,
            t' ≠ 0 ∧ t' ≠ snd v0 ∧ t'' ≠ 0 ∧ t'' ≠ snd v0 ∧ t' ≠ t'' := by
          have hBc : ((Finset.univ : Finset (Fin 6)) \ {0, snd v0}).card = 4 := by
            have h2 : ({0, snd v0} : Finset (Fin 6)).card = 2 := by
              rw [Finset.card_insert_of_notMem (by simpa using hs0ne.symm)]
              simp
            rw [Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Fintype.card_fin, h2]
          have h2 : 1 < ((Finset.univ : Finset (Fin 6)) \ {0, snd v0}).card := by
            rw [hBc]; norm_num
          obtain ⟨t', ht', t'', ht'', hne⟩ := Finset.one_lt_card.mp h2
          simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton,
            not_or, true_and] at ht' ht''
          exact ⟨t', t'', ht'.1, ht'.2, ht''.1, ht''.2, hne⟩
        obtain ⟨w', hw'⟩ := htop_exists t'
        obtain ⟨w'', hw''⟩ := htop_exists t''
        have hw'0 : snd w' = 0 := by
          have hne : top v0 ≠ top w' := by rw [hv0, hw']; exact ht'0.symm
          rcases hpair v0 w' hne with h | h
          · rw [hw'] at h
            exact absurd h.symm ht'2
          · rwa [hv0] at h
        have hw''0 : snd w'' = 0 := by
          have hne : top v0 ≠ top w'' := by rw [hv0, hw'']; exact ht''0.symm
          rcases hpair v0 w'' hne with h | h
          · rw [hw''] at h
            exact absurd h.symm ht''2
          · rwa [hv0] at h
        have hne' : top w' ≠ top w'' := by rw [hw', hw'']; exact ht'ne
        rcases hpair w' w'' hne' with h | h
        · rw [hw'0, hw''] at h
          exact ht''0 h.symm
        · rw [hw''0, hw'] at h
          exact ht'0 h.symm
condorcet_six_balanced_top_structure
If every 3-candidate set contains the top choice of at most half the voters in a 6-candidate election, then each candidate is the top choice of exactly n / 6 voters.
Nat.eq_of_mul_eq_mul_left
If n > 0 and n * m = n * k for natural numbers, then m = k.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.disjoint_left
Two sets are disjoint if and only if no element of the first belongs to the second.
Finset.card_biUnion
The cardinality of a union of pairwise disjoint finite sets is the sum of their individual cardinalities.
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set multiplied by that constant.
Finset.card_sdiff
The cardinality of the set difference t \ s is |t| - |s ∩ t|.
Finset.inter_univ
The intersection of any finite set with the universal set is the set itself.
Finset.card_univ
The cardinality of the universal set of a finite type equals the cardinality of that type.
Fintype.card_fin
The cardinality of Fin n is n.
Fin.zero_le
In Fin n, 0 is less than or equal to any element.
not_lt.mpr
If b ≤ a, then a < b is false.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.
Fin.lt_def
An element of Fin n is strictly less than another if and only if their underlying natural numbers satisfy the strict inequality.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.card_insert_of_notMem
Inserting an element not already in a finite set increases its cardinality by 1.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1.
Finset.exists_mem_notMem_of_card_lt_card
If |s| < |t| for finite sets, there exists an element in t that is not in s.
Finset.card_erase_of_mem
Removing an element from a finite set containing it decreases its cardinality by 1.
Finset.one_lt_card.mp
A finite set with cardinality greater than 1 contains at least two distinct elements.

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

/-- First genuine instance of the balanced regime: six candidates. -/theorem condorcet_six_balanced_has_winning_three_set (n : ℕ) (P : Fin n → Equiv.Perm (Fin 6))    (hn : 0 < n)    (hbal : ∀ S : Finset (Fin 6), S.card = 3 →      2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by norm_num⟩ ∈ S).card ≤ n) :    ∃ S : Finset (Fin 6), S.card ≤ 3 ∧ is_condorcet_winning_set P S := by  classical  set top : Fin n → Fin 6 := fun v => (P v).symm ⟨0, by norm_num⟩ with htopdef  set snd : Fin n → Fin 6 := fun v => (P v).symm ⟨1, by norm_num⟩ with hsnddef  have hstr : ∀ c : Fin 6, 6 * (Finset.univ.filter fun v => top v = c).card = n := by    intro c    have := condorcet_six_balanced_top_structure n P hbal c    simpa only [htopdef] using this  set k : ℕ := (Finset.univ.filter fun v => top v = 0).card with hkdef  have hn6 : n = 6 * k := by    have h0 := hstr 0    rw [← hkdef] at h0    omega  have hkc : ∀ c : Fin 6, (Finset.univ.filter fun v => top v = c).card = k := by    intro c    have h := hstr c    have hgoal : 6 * (Finset.univ.filter fun v => top v = c).card = 6 * k := by omega    exact Nat.eq_of_mul_eq_mul_left (n := 6) (by norm_num) hgoal  have hkpos : 0 < k := by omega  have htop_exists : ∀ c : Fin 6, ∃ v, top v = c := by    intro c    have hpos : 0 < (Finset.univ.filter fun v => top v = c).card := by      rw [hkc c]; exact hkpos    obtain ⟨v, hv⟩ := Finset.card_pos.mp hpos    exact ⟨v, by simpa using hv⟩  have hpos_top : ∀ v, P v (top v) = 0 := by intro v; simp [top]  have hpos_snd : ∀ v, P v (snd v) = 1 := by intro v; simp [snd]  have hsnd_ne_top : ∀ v, snd v ≠ top v := by    intro v h    have h1 := hpos_snd v    rw [h, hpos_top v] at h1    simp at h1  by_cases hwin : ∃ A : Finset (Fin 6), A.card = 3 ∧ is_condorcet_winning_set P A  · obtain ⟨A, hAc, hw⟩ := hwin    exact ⟨A, by omega, hw⟩  · exfalso    have hwin' : ∀ A : Finset (Fin 6), A.card = 3 → ¬ is_condorcet_winning_set P A := by      intro A hA hw      exact hwin ⟨A, hA, hw⟩    have hA0card : ∀ A : Finset (Fin 6), A.card = 3 →        (Finset.univ.filter fun v => top v ∉ A).card = 3 * k := by      intro A hA      have hdisj : ∀ c ∈ A, ∀ d ∈ A, c ≠ d →          Disjoint (Finset.univ.filter fun v => top v = c)            (Finset.univ.filter fun v => top v = d) := by        intro c _ d _ hcd        rw [Finset.disjoint_left]        intro v hv hv'        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv hv'        exact hcd (hv.symm.trans hv')      have hbij : (Finset.univ.filter fun v => top v ∈ A)          = A.biUnion (fun c => Finset.univ.filter fun v => top v = c) := by        ext v        simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and]        exact ⟨fun hv => ⟨top v, hv, rfl⟩, fun ⟨c, hc, hvc⟩ => hvc ▸ hc⟩      have hIn : (Finset.univ.filter fun v => top v ∈ A).card = 3 * k := by        rw [hbij, Finset.card_biUnion hdisj,          Finset.sum_congr rfl (fun c (_ : c ∈ A) => hkc c), Finset.sum_const, hA]        simp      have hcompl : (Finset.univ.filter fun v => top v ∉ A)          = Finset.univ \ (Finset.univ.filter fun v => top v ∈ A) := by        ext v; simp      rw [hcompl, Finset.card_sdiff, Finset.inter_univ, hIn, Finset.card_univ, Fintype.card_fin]      omega    have hwit : ∀ A : Finset (Fin 6), A.card = 3 → ∃ a, a ∉ A ∧        ∀ v, top v ∉ A → ∀ b ∈ A, P v a < P v b := by      intro A hA      have hnot := hwin' A hA      have hA0c : (Finset.univ.filter fun v => top v ∉ A).card = 3 * k := hA0card A hA      have hbadIn : ∀ a, (Finset.univ.filter fun v => ∀ b ∈ A, P v a < P v b)          ⊆ (Finset.univ.filter fun v => top v ∉ A) := by        intro a v hv        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢        intro htopA        have h1 : P v a < P v (top v) := hv (top v) htopA        rw [hpos_top v] at h1        exact absurd h1 (not_lt.mpr (Fin.zero_le (P v a)))      have hex : ∃ a, a ∉ A ∧          n ≤ 2 * (Finset.univ.filter fun v => ∀ b ∈ A, P v a < P v b).card := by        by_contra hc        apply hnot        unfold is_condorcet_winning_set        intro a ha        by_contra hlt        exact hc ⟨a, ha, by omega⟩      obtain ⟨a, haA, hge⟩ := hex      refine ⟨a, haA, ?_⟩      have hcard : (Finset.univ.filter fun v => top v ∉ A).card ≤          (Finset.univ.filter fun v => ∀ b ∈ A, P v a < P v b).card := by        rw [hA0c]; omega      have heq : (Finset.univ.filter fun v => ∀ b ∈ A, P v a < P v b)          = (Finset.univ.filter fun v => top v ∉ A) :=        Finset.eq_of_subset_of_card_le (hbadIn a) hcard      intro v hv b hb      have hmem : v ∈ Finset.univ.filter (fun w => ∀ b ∈ A, P w a < P w b) := by        rw [heq]        simp only [Finset.mem_filter, Finset.mem_univ, true_and]        exact hv      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hmem      exact hmem b hb    have hkey1 : ∀ (A : Finset (Fin 6)) (a : Fin 6), A.card = 3 → a ∉ A →        (∀ v, top v ∉ A → ∀ b ∈ A, P v a < P v b) →        ∀ v, top v ∉ A → snd v ∈ A → a = top v := by      intro A a hAc haA hdom v htv hsv      have h1 : P v a < P v (snd v) := hdom v htv (snd v) hsv      rw [hpos_snd v] at h1      have hval : ((P v a) : ℕ) = 0 := by        have h2 : ((P v a) : ℕ) < 1 := by          have h3 := h1          rw [Fin.lt_def] at h3          simpa using h3        omega      have h0 : P v a = 0 := Fin.ext (by simpa using hval)      refine (P v).injective ?_      rw [h0, hpos_top v]    have hpair : ∀ v w : Fin n, top v ≠ top w → snd v = top w ∨ snd w = top v := by      intro v w hne      by_contra hcon      push_neg at hcon      obtain ⟨hvw, hwv⟩ := hcon      have hs1 : snd v ≠ top v := hsnd_ne_top v      have hs2 : snd w ≠ top w := hsnd_ne_top w      set B : Finset (Fin 6) := Finset.univ \ {top v, top w} with hBdef      have hBcard : B.card = 4 := by        have h2 : ({top v, top w} : Finset (Fin 6)).card = 2 := by          rw [Finset.card_insert_of_notMem (by simpa using hne)]          simp        rw [hBdef, Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Fintype.card_fin, h2]      have hsB : snd v ∈ B := by        rw [hBdef]        simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton,          not_or, true_and]        exact ⟨hs1, hvw⟩      have hwB : snd w ∈ B := by        rw [hBdef]        simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton,          not_or, true_and]        exact ⟨hwv, hs2⟩      have hsmall : ({snd v, snd w} : Finset (Fin 6)).card < B.card := by        have h2 : ({snd v, snd w} : Finset (Fin 6)).card ≤ 2 := by          have h3 := Finset.card_insert_le (snd v) ({snd w} : Finset (Fin 6))          simpa using h3        omega      obtain ⟨c, hcB, hc2⟩ := Finset.exists_mem_notMem_of_card_lt_card hsmall      have hcv : snd v ≠ c := by        intro h        apply hc2        rw [← h]        exact Finset.mem_insert_self (snd v) {snd w}      have hcw : snd w ≠ c := by        intro h        apply hc2        rw [← h]        exact Finset.mem_insert_of_mem (Finset.mem_singleton_self (snd w))      have htvB : top v ∉ B := by rw [hBdef]; simp      have htwB : top w ∉ B := by rw [hBdef]; simp      have hAcard : (B.erase c).card = 3 := by        rw [Finset.card_erase_of_mem hcB, hBcard]      obtain ⟨a, haA, hdom⟩ := hwit (B.erase c) hAcard      have htvA : top v ∉ B.erase c := fun h => htvB (Finset.erase_subset c B h)      have htwA : top w ∉ B.erase c := fun h => htwB (Finset.erase_subset c B h)      have hsvA : snd v ∈ B.erase c := by        rw [Finset.mem_erase]; exact ⟨hcv, hsB⟩      have hswA : snd w ∈ B.erase c := by        rw [Finset.mem_erase]; exact ⟨hcw, hwB⟩      have hav : a = top v := hkey1 (B.erase c) a hAcard haA hdom v htvA hsvA      have haw : a = top w := hkey1 (B.erase c) a hAcard haA hdom w htwA hswA      exact hne (hav.symm.trans haw)    obtain ⟨v0, hv0⟩ := htop_exists 0    have hs0ne : snd v0 ≠ 0 := by      have h := hsnd_ne_top v0      rwa [hv0] at h    obtain ⟨t', t'', ht'0, ht'2, ht''0, ht''2, ht'ne⟩ : ∃ t' t'' : Fin 6,        t' ≠ 0 ∧ t' ≠ snd v0 ∧ t'' ≠ 0 ∧ t'' ≠ snd v0 ∧ t' ≠ t'' := by      have hBc : ((Finset.univ : Finset (Fin 6)) \ {0, snd v0}).card = 4 := by        have h2 : ({0, snd v0} : Finset (Fin 6)).card = 2 := by          rw [Finset.card_insert_of_notMem (by simpa using hs0ne.symm)]          simp        rw [Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Fintype.card_fin, h2]      have h2 : 1 < ((Finset.univ : Finset (Fin 6)) \ {0, snd v0}).card := by        rw [hBc]; norm_num      obtain ⟨t', ht', t'', ht'', hne⟩ := Finset.one_lt_card.mp h2      simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton,        not_or, true_and] at ht' ht''      exact ⟨t', t'', ht'.1, ht'.2, ht''.1, ht''.2, hne⟩    obtain ⟨w', hw'⟩ := htop_exists t'    obtain ⟨w'', hw''⟩ := htop_exists t''    have hw'0 : snd w' = 0 := by      have hne : top v0 ≠ top w' := by rw [hv0, hw']; exact ht'0.symm      rcases hpair v0 w' hne with h | h      · rw [hw'] at h        exact absurd h.symm ht'2      · rwa [hv0] at h    have hw''0 : snd w'' = 0 := by      have hne : top v0 ≠ top w'' := by rw [hv0, hw'']; exact ht''0.symm      rcases hpair v0 w'' hne with h | h      · rw [hw''] at h        exact absurd h.symm ht''2      · rwa [hv0] at h    have hne' : top w' ≠ top w'' := by rw [hw', hw'']; exact ht'ne    rcases hpair w' w'' hne' with h | h    · rw [hw'0, hw''] at h      exact ht''0 h.symm    · rw [hw''0, hw'] at h      exact ht'0 h.symm
See it in the graphDiscuss this resultChallenge it