condorcet_six_balanced_has_winning_three_set
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.
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.
uses
condorcet_six_balanced_top_structure2 * (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
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.
uses
Nat.eq_of_mul_eq_mul_left,Finset.card_pos.mpset 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
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.
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⟩
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.
uses
Finset.disjoint_left,Finset.card_biUnion,Finset.sum_const,Finset.card_sdiff,Finset.inter_univ,Finset.card_univ,Fintype.card_finhave 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
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).
uses
Fin.zero_le,not_lt.mpr,Finset.eq_of_subset_of_card_lehave 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
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).
uses
Fin.lt_def,Fin.exthave 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]
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).
uses
Finset.card_insert_of_notMem,Finset.card_insert_le,Finset.exists_mem_notMem_of_card_lt_card,Finset.card_erase_of_memhave 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)
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.
uses
Finset.card_insert_of_notMem,Finset.one_lt_card.mpobtain ⟨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.
- In this formalization, a voter's preference ranking is given by a permutation where smaller numerical values represent higher preference: rank 0 is the top choice, rank 1 is the second choice, and P v a < P v b means voter v prefers candidate a over candidate b.
- Line 5 contains an embedded proof tactic (by norm_num) verifying that 0 < 6 to construct the candidate rank index 0 in Fin 6 within the theorem statement.
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.
/-- 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