ejr_greedy_cohesive_pair_aux
For every voter subset S and positive committee parameter K, a greedy cohesive core W has cost at most |S|K/n and satisfies every K-cohesive group in S; if its budget is saturated and W is nonempty, one candidate can be erased while satisfying every (K-1)-cohesive group in S.
Statement
theorem ejr_greedy_cohesive_pair_aux {n m : ℕ}
(A : Fin n → Finset (Fin m)) (K : ℕ) (hn : 0 < n) (hK : 0 < K)
(S : Finset (Fin n)) :
∃ W : Finset (Fin m), W.card * n ≤ S.card * K ∧
(∀ ℓ, 1 ≤ ℓ → ∀ G ⊆ S, is_ejr_cohesive_group A K ℓ G →
∃ i ∈ G, ℓ ≤ (A i ∩ W).card) ∧
(W.card * n = S.card * K → W.Nonempty → ∃ c ∈ W,
∀ ℓ, 1 ≤ ℓ → ∀ G ⊆ S, is_ejr_cohesive_group A (K - 1) ℓ G →
∃ i ∈ G, ℓ ≤ (A i ∩ W.erase c).card)- Source
- Helper for ejr_adjacent_committees_exists (arXiv:2302.01989, Proposition 8, EJR consequence): strengthen the existing greedy cohesive budget argument with a deletion certificate when the budget is exactly saturated.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_ejr_cohesive_groupFor committee size k, a group G of the n voters is ℓ-cohesive if |G| ≥ ℓ·n/k and |∩_{i∈G} A_i| ≥ ℓ.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- ejr_adjacent_committees_existsFor every approval profile with at least one voter and every k smaller than the candidate count, there exist nested committees W subset V…
The proof, explained
The proof proceeds by strong induction on the voter subset S. If no cohesive group exists in S, the empty set trivially satisfies all conditions. Otherwise, we greedily select a K-cohesive group G ⊆ S maximizing its quota ℓ, apply the induction hypothesis to S \\ G to obtain a sub-committee W', and add ℓ candidates commonly approved by G to form W = W' ∪ C. When the total budget is saturated, W' and C must be disjoint and both saturated; we then either erase a candidate from W' using the inductive erasure hypothesis, or—if W' is empty, forcing S ⊆ G—erase any candidate from C, which still satisfies every (K - 1)-cohesive group because its required quota is strictly less than ℓ.
The theorem reduces by strong induction to proving the claim for voter set S assuming it holds for all strict subsets of S.
We enable classical reasoning and proceed by strong induction on the voter set S with respect to strict subset inclusion (Finset.strongInduction). This provides the induction hypothesis ih: for every proper subset t ⊂ S, there exists a suitable committee satisfying the budget, cohesion, and erasure conditions.
uses
Finset.strongInductionclassical induction S using Finset.strongInduction with | H S ih =>
Any cohesive group has quota ℓ ≤ m, and any (K - 1)-cohesive group is also K-cohesive.
For the upper bound on ℓ (hle_m), the set of commonly approved candidates has size at least ℓ and is a subset of the candidate universe Fin m, so ℓ ≤ m (Finset.card_le_univ). For the upgrade lemma, since K - 1 ≤ K (Nat.sub_le), multiplying by |G| (Nat.mul_le_mul_left) shows that ℓ · n ≤ |G| · (K - 1) ≤ |G| · K, so any (K - 1, ℓ)-cohesive group satisfies the quota condition for parameter K as well.
uses
Finset.card_le_univ,Nat.mul_le_mul_left,Nat.sub_lehave hle_m : ∀ ℓ G, is_ejr_cohesive_group A K ℓ G → ℓ ≤ m := fun ℓ G h => h.2.trans ((Finset.card_le_univ _).trans (by simp)) have upgrade : ∀ ℓ G, is_ejr_cohesive_group A (K - 1) ℓ G → is_ejr_cohesive_group A K ℓ G := by intro ℓ G h exact ⟨h.1.trans (Nat.mul_le_mul_left G.card (Nat.sub_le K 1)), h.2⟩
The set P consists of exactly those pairs (ℓ, G) where 1 ≤ ℓ, G ⊆ S, and G is (K, ℓ)-cohesive.
We define P as the set of pairs (ℓ, G) with ℓ ∈ {1, ..., m} (Finset.Icc) and G in the powerset of S (Finset.mem_powerset) such that G is (K, ℓ)-cohesive, using Finset.filter. We prove the membership equivalence hmemP: an element (ℓ, G) belongs to P if and only if 1 ≤ ℓ ≤ m, G ⊆ S, and G is cohesive; the bound ℓ ≤ m is automatically satisfied for any cohesive group by hle_m.
uses
Finset.mem_filter,Finset.mem_product,Finset.mem_Icc,Finset.mem_powersetlet P : Finset (ℕ × Finset (Fin n)) := ((Finset.Icc 1 m) ×ˢ S.powerset).filter fun p => is_ejr_cohesive_group A K p.1 p.2 have hmemP : ∀ ℓ G, (ℓ, G) ∈ P ↔ (1 ≤ ℓ ∧ G ⊆ S ∧ is_ejr_cohesive_group A K ℓ G) := by intro ℓ G simp only [P, Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_powerset] constructor · rintro ⟨⟨⟨h1, -⟩, h2⟩, h3⟩; exact ⟨h1, h2, h3⟩ · rintro ⟨h1, h2, h3⟩; exact ⟨⟨⟨h1, hle_m ℓ G h3⟩, h2⟩, h3⟩
If P is nonempty, there is a cohesive group G ⊆ S with maximal quota ℓ ≥ 1, an inductive committee W' for S \\ G, and a set C of ℓ candidates commonly approved by G.
Assuming P is nonempty, we select a pair (ℓ, G) ∈ P that maximizes the quota ℓ. Because ℓ ≥ 1 and n > 0, ℓ · n > 0 (Nat.mul_pos), which implies G is nonempty (Finset.nonempty_iff_ne_empty, Finset.card_empty, zero_mul) since an empty group would satisfy ℓ · n ≤ 0. Therefore S \\ G is a strict subset of S (Finset.sdiff_ssubset), allowing us to apply the induction hypothesis ih to S \\ G to obtain a committee W'. Furthermore, since G has at least ℓ common approvals, we select a subset C of exactly ℓ such candidates (Finset.exists_subset_card_eq).
uses
Nat.mul_pos,Finset.nonempty_iff_ne_empty,Finset.card_empty,zero_mul,Finset.sdiff_ssubset,Finset.exists_subset_card_eqby_cases hP : P.Nonempty · obtain ⟨⟨ℓ, G⟩, hpP, hmax⟩ := P.exists_max_image Prod.fst hP obtain ⟨hℓ1, hGS, hcoh⟩ := (hmemP ℓ G).1 hpP have hGne : G.Nonempty := by rw [Finset.nonempty_iff_ne_empty] rintro rfl have h := hcoh.1 simp only [Finset.card_empty, zero_mul] at h have : 0 < ℓ * n := Nat.mul_pos hℓ1 hn omega obtain ⟨W', hW'card, hW', hW'pair⟩ := ih (S \ G) (Finset.sdiff_ssubset hGS hGne) obtain ⟨C, hCsub, hCcard⟩ := Finset.exists_subset_card_eq hcoh.2
The committee W' ∪ C satisfies the budget constraint |W' ∪ C| · n ≤ |S| · K.
Since G ⊆ S, the voters partition into S \\ G and G, so |S \\ G| + |G| = |S| (Finset.card_sdiff_add_card_eq_card). The cardinality of W' ∪ C is at most |W'| + |C| = |W'| + ℓ (Finset.card_union_le). Multiplying by n (Nat.mul_le_mul_right), we bound |W'| · n ≤ |S \\ G| · K using the inductive core W' and ℓ · n ≤ |G| · K using the cohesion of G. Adding these bounds (Nat.add_le_add) and factoring out K (Nat.add_mul) gives (|S \\ G| + |G|) · K = |S| · K.
uses
Finset.card_sdiff_add_card_eq_card,Finset.card_union_le,Nat.mul_le_mul_right,Nat.add_le_add,Nat.add_mulhave hsum : (S \ G).card + G.card = S.card := Finset.card_sdiff_add_card_eq_card hGS have hbudget : (W' ∪ C).card * n ≤ S.card * K := by have h1 : (W' ∪ C).card ≤ W'.card + ℓ := (Finset.card_union_le _ _).trans (by rw [hCcard]) calc (W' ∪ C).card * n ≤ (W'.card + ℓ) * n := Nat.mul_le_mul_right _ h1 _ = W'.card * n + ℓ * n := by ring _ ≤ (S \ G).card * K + G.card * K := Nat.add_le_add hW'card hcoh.1 _ = S.card * K := by rw [← Nat.add_mul, hsum] refine ⟨W' ∪ C, hbudget, ?_, ?_⟩
Every (K, ℓ')-cohesive group H ⊆ S with ℓ' ≥ 1 has a voter who approves at least ℓ' candidates in W' ∪ C.
Given H ⊆ S, we case split on whether H is disjoint from G: (1) If H and G are disjoint, then H ⊆ S \\ G. By the inductive property of W', some voter i ∈ H approves at least ℓ' candidates in W', hence at least ℓ' in W' ∪ C since W' ⊆ W' ∪ C (Finset.subset_union_left, Finset.inter_subset_inter_left, Finset.card_le_card). (2) If H and G intersect, let i ∈ H ∩ G. Maximality of ℓ in P ensures ℓ' ≤ ℓ. Since i ∈ G, voter i approves all candidates in C (Finset.mem_union_right), so C ⊆ A(i) ∩ (W' ∪ C), providing at least |C| = ℓ ≥ ℓ' approved candidates.
uses
Finset.card_le_card,Finset.subset_union_left,Finset.inter_subset_inter_left,Finset.mem_union_right· intro ℓ' hℓ' H hHS hHcoh by_cases hHG : Disjoint H G · have hHsub : H ⊆ S \ G := fun x hx => Finset.mem_sdiff.2 ⟨hHS hx, Finset.disjoint_left.1 hHG hx⟩ obtain ⟨i, hi, hle⟩ := hW' ℓ' hℓ' H hHsub hHcoh exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left Finset.subset_union_left))⟩ · obtain ⟨i, hiH, hiG⟩ := Finset.not_disjoint_iff.1 hHG have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, hHcoh⟩) refine ⟨i, hiH, hℓ'le.trans ?_⟩ rw [← hCcard] apply Finset.card_le_card intro c hc exact Finset.mem_inter.2 ⟨(Finset.mem_filter.1 (hCsub hc)).2 i hiG, Finset.mem_union_right _ hc⟩
When W' ∪ C saturates the total budget, W' and G both saturate their individual budgets, and W' is disjoint from C.
Assume |W' ∪ C| · n = |S| · K. Since |W' ∪ C| ≤ |W'| + ℓ (Finset.card_union_le, Nat.mul_le_mul_right) while |W'| · n ≤ |S \\ G| · K and ℓ · n ≤ |G| · K sum to |S| · K (Nat.add_mul), linear arithmetic forces both equalities |W'| · n = |S \\ G| · K and ℓ · n = |G| · K, as well as |W' ∪ C| = |W'| + |C|. Inclusion-exclusion |W' ∪ C| + |W' ∩ C| = |W'| + |C| (Finset.card_union_add_card_inter) then implies |W' ∩ C| = 0, so W' and C are disjoint.
uses
Finset.card_union_le,Nat.mul_le_mul_right,Nat.add_mul,Finset.card_union_add_card_inter· intro hfull hne have hcardU : (W' ∪ C).card ≤ W'.card + ℓ := (Finset.card_union_le _ _).trans (by rw [hCcard]) have hmulU := Nat.mul_le_mul_right n hcardU have hsumK : (S \ G).card * K + G.card * K = S.card * K := by rw [← Nat.add_mul, hsum] have hW'full : W'.card * n = (S \ G).card * K := by nlinarith [hcoh.1] have hGfull : ℓ * n = G.card * K := by nlinarith [hcoh.1] have hcardEq : (W' ∪ C).card = W'.card + C.card := by rw [hCcard] have heq : (W' ∪ C).card * n = (W'.card + ℓ) * n := by nlinarith nlinarith have hdisj : Disjoint W' C := Finset.disjoint_iff_inter_eq_empty.mpr (Finset.card_eq_zero.mp (by have := Finset.card_union_add_card_inter W' C omega))
If W' is nonempty, erasing the candidate c ∈ W' provided by induction from W' ∪ C satisfies every (K - 1)-cohesive group in S.
Because W' saturates its budget and is nonempty, induction on S \\ G gives c ∈ W' (Finset.mem_union_left) whose removal from W' satisfies all (K - 1)-cohesive groups in S \\ G. Since W' and C are disjoint, c ∉ C. For any (K - 1, ℓ')-cohesive group H ⊆ S: if H is disjoint from G, then H ⊆ S \\ G and the induction hypothesis applies (Finset.card_le_card, Finset.inter_subset_inter_left, Finset.erase_subset_erase, Finset.subset_union_left); if H intersects G at some voter i, then H is also K-cohesive by the upgrade lemma, so ℓ' ≤ ℓ by maximality of ℓ. Since c ∉ C, all candidates in C remain in (W' ∪ C) \\ {c} (Finset.mem_union_right), and voter i ∈ G approves all of C, giving |C| = ℓ ≥ ℓ' approvals.
uses
Finset.mem_union_left,Finset.card_le_card,Finset.inter_subset_inter_left,Finset.erase_subset_erase,Finset.subset_union_left,Finset.mem_union_rightby_cases hW'ne : W'.Nonempty · obtain ⟨c, hc, hcpair⟩ := hW'pair hW'full hW'ne refine ⟨c, Finset.mem_union_left _ hc, ?_⟩ have hcC : c ∉ C := Finset.disjoint_left.mp hdisj hc intro ℓ' hℓ' H hHS hHcoh by_cases hHG : Disjoint H G · have hHsub : H ⊆ S \ G := fun x hx => Finset.mem_sdiff.2 ⟨hHS hx, Finset.disjoint_left.1 hHG hx⟩ obtain ⟨i, hi, hle⟩ := hcpair ℓ' hℓ' H hHsub hHcoh exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left (Finset.erase_subset_erase c Finset.subset_union_left)))⟩ · obtain ⟨i, hiH, hiG⟩ := Finset.not_disjoint_iff.1 hHG have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, upgrade ℓ' H hHcoh⟩) refine ⟨i, hiH, hℓ'le.trans ?_⟩ rw [← hCcard] apply Finset.card_le_card intro d hd refine Finset.mem_inter.2 ⟨(Finset.mem_filter.1 (hCsub hd)).2 i hiG, ?_⟩ exact Finset.mem_erase.mpr ⟨fun he => hcC (he ▸ hd), Finset.mem_union_right _ hd⟩
If W' is empty, erasing any candidate c ∈ C from W' ∪ C satisfies every (K - 1)-cohesive group in S.
When W' = ∅, |W'| · n = |S \\ G| · K = 0 forces |S \\ G| = 0, so S ⊆ G. Since W' ∪ C is nonempty, C is nonempty (Finset.card_pos), so we may pick any candidate c ∈ C (Finset.mem_union_right). For any (K - 1, ℓ')-cohesive group H ⊆ S ⊆ G: (1) Since |H| ≤ |G| (Finset.card_le_card) and G is nonempty, ℓ' · n ≤ |H| · (K - 1) ≤ |G| · (K - 1) < |G| · K = ℓ · n (Nat.mul_le_mul_right, Nat.mul_lt_mul_of_pos_left), which strictly forces ℓ' < ℓ, so ℓ' ≤ ℓ - 1. (2) Since ℓ' ≥ 1, H is nonempty (Nat.mul_pos, Finset.card_pos). Any voter i ∈ H ⊆ G approves all of C, and erasing c leaves |C \\ {c}| = ℓ - 1 candidates (Finset.card_erase_of_mem). Since ℓ - 1 ≥ ℓ', voter i approves at least ℓ' candidates in (W' ∪ C) \\ {c}.
uses
Finset.card_pos,Finset.mem_union_right,Finset.card_le_card,Nat.mul_le_mul_right,Nat.mul_lt_mul_of_pos_left,Nat.mul_pos,Finset.card_erase_of_mem· have hW'empty : W' = ∅ := Finset.not_nonempty_iff_eq_empty.mp hW'ne have hrem0 : (S \ G).card = 0 := by have hzero : (S \ G).card * K = 0 := by simpa [hW'empty] using hW'full.symm rcases Nat.mul_eq_zero.mp hzero with h | h · exact h · omega have hSG : S ⊆ G := Finset.sdiff_eq_empty_iff_subset.mp (Finset.card_eq_zero.mp hrem0) have hCne : C.Nonempty := Finset.card_pos.mp (by omega) obtain ⟨c, hc⟩ := hCne refine ⟨c, Finset.mem_union_right _ hc, ?_⟩ intro ℓ' hℓ' H hHS hHcoh have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, upgrade ℓ' H hHcoh⟩) have hHcard : H.card ≤ G.card := Finset.card_le_card (hHS.trans hSG) have hGpos : 0 < G.card := Finset.card_pos.mpr hGne have hmulH := Nat.mul_le_mul_right (K - 1) hHcard have hstrict : G.card * (K - 1) < G.card * K := Nat.mul_lt_mul_of_pos_left (by omega) hGpos have hℓ'lt : ℓ' < ℓ := by by_contra hnot have heq : ℓ' = ℓ := by omega have hsize := hHcoh.1 rw [heq] at hsize omega have hHne : H.Nonempty := by rw [← Finset.card_pos] have hsize := hHcoh.1 have hpos : 0 < ℓ' * n := Nat.mul_pos hℓ' hn nlinarith obtain ⟨i, hi⟩ := hHne refine ⟨i, hi, ?_⟩ have hCerase : (C.erase c).card = ℓ - 1 := by rw [Finset.card_erase_of_mem hc, hCcard] have hsub : C.erase c ⊆ A i ∩ (W' ∪ C).erase c := by intro d hd obtain ⟨hdc, hdC⟩ := Finset.mem_erase.mp hd exact Finset.mem_inter.mpr ⟨(Finset.mem_filter.mp (hCsub hdC)).2 i (hSG (hHS hi)), Finset.mem_erase.mpr ⟨hdc, Finset.mem_union_right _ hdC⟩⟩ have := Finset.card_le_card hsub omega
If P is empty, the empty committee W = ∅ satisfies all conditions.
When P is empty, no (K, ℓ)-cohesive group exists in S with ℓ ≥ 1. The empty set W = ∅ trivially satisfies the budget constraint |∅| · n = 0 ≤ |S| · K. The cohesion condition holds vacuously because any counterexample would define a member of P. The erasure condition holds vacuously because the empty set is not nonempty.
· refine ⟨∅, by simp, ?_, ?_⟩ · intro ℓ hℓ G hGS hcoh exact absurd ⟨(ℓ, G), (hmemP ℓ G).2 ⟨hℓ, hGS, hcoh⟩⟩ hP · intro _ hne simp at hne
Finset.strongInduction- A principle of well-founded induction on finite sets: to prove a property for all finite sets, it suffices to show that it holds for any set s assuming it holds for all proper subsets t ⊂ s.
Finset.card_le_univ- The cardinality of any finite set of elements from a finite type is at most the cardinality of the whole type.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a factor on the left preserves the inequality: if n ≤ m then k * n ≤ k * m.
Nat.sub_le- Subtracting a natural number from another never increases its value: n - m ≤ n.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the filtering predicate.
Finset.mem_product- An ordered pair belongs to the Cartesian product of two finite sets if and only if its first coordinate belongs to the first set and its second coordinate belongs to the second set.
Finset.mem_Icc- A number belongs to the closed discrete interval [a, b] if and only if it is between a and b inclusive.
Finset.mem_powerset- A finite set belongs to the powerset of another finite set if and only if it is a subset of that set.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not the empty set.
Finset.card_empty- The cardinality of the empty set is zero.
zero_mul- Multiplying zero by any element gives zero.
Finset.sdiff_ssubset- Removing a nonempty subset from a set leaves a strictly smaller (proper) subset.
Finset.exists_subset_card_eq- Any finite set with cardinality at least n contains a subset of cardinality exactly n.
Finset.card_sdiff_add_card_eq_card- If s is a subset of t, then the cardinality of the difference t \\ s plus the cardinality of s equals the cardinality of t.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their individual cardinalities.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers by a factor on the right preserves the inequality: if n ≤ m then n * k ≤ m * k.
Nat.add_le_add- Adding two inequalities of natural numbers preserves the inequality: if a ≤ b and c ≤ d then a + c ≤ b + d.
Nat.add_mul- Multiplication of natural numbers distributes over addition on the right: (n + m) * k = n * k + m * k.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to that of the other.
Finset.subset_union_left- Every set is a subset of its union with another set: s₁ ⊆ s₁ ∪ s₂.
Finset.inter_subset_inter_left- If one set is contained in another, intersecting both with a third set preserves the containment: if t ⊆ u then s ∩ t ⊆ s ∩ u.
Finset.mem_union_right- If an element belongs to the second set, it belongs to the union of the two sets: if a ∈ t then a ∈ s ∪ t.
Finset.card_union_add_card_inter- The inclusion-exclusion formula for two finite sets: |s ∪ t| + |s ∩ t| = |s| + |t|.
Finset.mem_union_left- If an element belongs to the first set, it belongs to the union of the two sets: if a ∈ s then a ∈ s ∪ t.
Finset.erase_subset_erase- Erasing a given element from two sets preserves the subset inclusion between them: if s ⊆ t then s.erase a ⊆ t.erase a.
Finset.card_pos- A finite set has strictly positive cardinality if and only if it is nonempty.
Nat.mul_lt_mul_of_pos_left- Multiplying a strict inequality of natural numbers by a strictly positive factor preserves strict inequality: if n < m and k > 0 then k * n < k * m.
Finset.card_erase_of_mem- Erasing an element from a finite set that contains it reduces its cardinality by one: |s.erase a| = |s| - 1.
- Linear arithmetic over the natural numbers (in particular, deducing that sub-budgets are saturated from saturation of the total budget, and that W' and C are disjoint) is handled automatically by nlinarith and omega.
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.
theorem ejr_greedy_cohesive_pair_aux {n m : ℕ} (A : Fin n → Finset (Fin m)) (K : ℕ) (hn : 0 < n) (hK : 0 < K) (S : Finset (Fin n)) : ∃ W : Finset (Fin m), W.card * n ≤ S.card * K ∧ (∀ ℓ, 1 ≤ ℓ → ∀ G ⊆ S, is_ejr_cohesive_group A K ℓ G → ∃ i ∈ G, ℓ ≤ (A i ∩ W).card) ∧ (W.card * n = S.card * K → W.Nonempty → ∃ c ∈ W, ∀ ℓ, 1 ≤ ℓ → ∀ G ⊆ S, is_ejr_cohesive_group A (K - 1) ℓ G → ∃ i ∈ G, ℓ ≤ (A i ∩ W.erase c).card) := by classical induction S using Finset.strongInduction with | H S ih => have hle_m : ∀ ℓ G, is_ejr_cohesive_group A K ℓ G → ℓ ≤ m := fun ℓ G h => h.2.trans ((Finset.card_le_univ _).trans (by simp)) have upgrade : ∀ ℓ G, is_ejr_cohesive_group A (K - 1) ℓ G → is_ejr_cohesive_group A K ℓ G := by intro ℓ G h exact ⟨h.1.trans (Nat.mul_le_mul_left G.card (Nat.sub_le K 1)), h.2⟩ let P : Finset (ℕ × Finset (Fin n)) := ((Finset.Icc 1 m) ×ˢ S.powerset).filter fun p => is_ejr_cohesive_group A K p.1 p.2 have hmemP : ∀ ℓ G, (ℓ, G) ∈ P ↔ (1 ≤ ℓ ∧ G ⊆ S ∧ is_ejr_cohesive_group A K ℓ G) := by intro ℓ G simp only [P, Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_powerset] constructor · rintro ⟨⟨⟨h1, -⟩, h2⟩, h3⟩; exact ⟨h1, h2, h3⟩ · rintro ⟨h1, h2, h3⟩; exact ⟨⟨⟨h1, hle_m ℓ G h3⟩, h2⟩, h3⟩ by_cases hP : P.Nonempty · obtain ⟨⟨ℓ, G⟩, hpP, hmax⟩ := P.exists_max_image Prod.fst hP obtain ⟨hℓ1, hGS, hcoh⟩ := (hmemP ℓ G).1 hpP have hGne : G.Nonempty := by rw [Finset.nonempty_iff_ne_empty] rintro rfl have h := hcoh.1 simp only [Finset.card_empty, zero_mul] at h have : 0 < ℓ * n := Nat.mul_pos hℓ1 hn omega obtain ⟨W', hW'card, hW', hW'pair⟩ := ih (S \ G) (Finset.sdiff_ssubset hGS hGne) obtain ⟨C, hCsub, hCcard⟩ := Finset.exists_subset_card_eq hcoh.2 have hsum : (S \ G).card + G.card = S.card := Finset.card_sdiff_add_card_eq_card hGS have hbudget : (W' ∪ C).card * n ≤ S.card * K := by have h1 : (W' ∪ C).card ≤ W'.card + ℓ := (Finset.card_union_le _ _).trans (by rw [hCcard]) calc (W' ∪ C).card * n ≤ (W'.card + ℓ) * n := Nat.mul_le_mul_right _ h1 _ = W'.card * n + ℓ * n := by ring _ ≤ (S \ G).card * K + G.card * K := Nat.add_le_add hW'card hcoh.1 _ = S.card * K := by rw [← Nat.add_mul, hsum] refine ⟨W' ∪ C, hbudget, ?_, ?_⟩ · intro ℓ' hℓ' H hHS hHcoh by_cases hHG : Disjoint H G · have hHsub : H ⊆ S \ G := fun x hx => Finset.mem_sdiff.2 ⟨hHS hx, Finset.disjoint_left.1 hHG hx⟩ obtain ⟨i, hi, hle⟩ := hW' ℓ' hℓ' H hHsub hHcoh exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left Finset.subset_union_left))⟩ · obtain ⟨i, hiH, hiG⟩ := Finset.not_disjoint_iff.1 hHG have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, hHcoh⟩) refine ⟨i, hiH, hℓ'le.trans ?_⟩ rw [← hCcard] apply Finset.card_le_card intro c hc exact Finset.mem_inter.2 ⟨(Finset.mem_filter.1 (hCsub hc)).2 i hiG, Finset.mem_union_right _ hc⟩ · intro hfull hne have hcardU : (W' ∪ C).card ≤ W'.card + ℓ := (Finset.card_union_le _ _).trans (by rw [hCcard]) have hmulU := Nat.mul_le_mul_right n hcardU have hsumK : (S \ G).card * K + G.card * K = S.card * K := by rw [← Nat.add_mul, hsum] have hW'full : W'.card * n = (S \ G).card * K := by nlinarith [hcoh.1] have hGfull : ℓ * n = G.card * K := by nlinarith [hcoh.1] have hcardEq : (W' ∪ C).card = W'.card + C.card := by rw [hCcard] have heq : (W' ∪ C).card * n = (W'.card + ℓ) * n := by nlinarith nlinarith have hdisj : Disjoint W' C := Finset.disjoint_iff_inter_eq_empty.mpr (Finset.card_eq_zero.mp (by have := Finset.card_union_add_card_inter W' C omega)) by_cases hW'ne : W'.Nonempty · obtain ⟨c, hc, hcpair⟩ := hW'pair hW'full hW'ne refine ⟨c, Finset.mem_union_left _ hc, ?_⟩ have hcC : c ∉ C := Finset.disjoint_left.mp hdisj hc intro ℓ' hℓ' H hHS hHcoh by_cases hHG : Disjoint H G · have hHsub : H ⊆ S \ G := fun x hx => Finset.mem_sdiff.2 ⟨hHS hx, Finset.disjoint_left.1 hHG hx⟩ obtain ⟨i, hi, hle⟩ := hcpair ℓ' hℓ' H hHsub hHcoh exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left (Finset.erase_subset_erase c Finset.subset_union_left)))⟩ · obtain ⟨i, hiH, hiG⟩ := Finset.not_disjoint_iff.1 hHG have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, upgrade ℓ' H hHcoh⟩) refine ⟨i, hiH, hℓ'le.trans ?_⟩ rw [← hCcard] apply Finset.card_le_card intro d hd refine Finset.mem_inter.2 ⟨(Finset.mem_filter.1 (hCsub hd)).2 i hiG, ?_⟩ exact Finset.mem_erase.mpr ⟨fun he => hcC (he ▸ hd), Finset.mem_union_right _ hd⟩ · have hW'empty : W' = ∅ := Finset.not_nonempty_iff_eq_empty.mp hW'ne have hrem0 : (S \ G).card = 0 := by have hzero : (S \ G).card * K = 0 := by simpa [hW'empty] using hW'full.symm rcases Nat.mul_eq_zero.mp hzero with h | h · exact h · omega have hSG : S ⊆ G := Finset.sdiff_eq_empty_iff_subset.mp (Finset.card_eq_zero.mp hrem0) have hCne : C.Nonempty := Finset.card_pos.mp (by omega) obtain ⟨c, hc⟩ := hCne refine ⟨c, Finset.mem_union_right _ hc, ?_⟩ intro ℓ' hℓ' H hHS hHcoh have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, upgrade ℓ' H hHcoh⟩) have hHcard : H.card ≤ G.card := Finset.card_le_card (hHS.trans hSG) have hGpos : 0 < G.card := Finset.card_pos.mpr hGne have hmulH := Nat.mul_le_mul_right (K - 1) hHcard have hstrict : G.card * (K - 1) < G.card * K := Nat.mul_lt_mul_of_pos_left (by omega) hGpos have hℓ'lt : ℓ' < ℓ := by by_contra hnot have heq : ℓ' = ℓ := by omega have hsize := hHcoh.1 rw [heq] at hsize omega have hHne : H.Nonempty := by rw [← Finset.card_pos] have hsize := hHcoh.1 have hpos : 0 < ℓ' * n := Nat.mul_pos hℓ' hn nlinarith obtain ⟨i, hi⟩ := hHne refine ⟨i, hi, ?_⟩ have hCerase : (C.erase c).card = ℓ - 1 := by rw [Finset.card_erase_of_mem hc, hCcard] have hsub : C.erase c ⊆ A i ∩ (W' ∪ C).erase c := by intro d hd obtain ⟨hdc, hdC⟩ := Finset.mem_erase.mp hd exact Finset.mem_inter.mpr ⟨(Finset.mem_filter.mp (hCsub hdC)).2 i (hSG (hHS hi)), Finset.mem_erase.mpr ⟨hdc, Finset.mem_union_right _ hdC⟩⟩ have := Finset.card_le_card hsub omega · refine ⟨∅, by simp, ?_, ?_⟩ · intro ℓ hℓ G hGS hcoh exact absurd ⟨(ℓ, G), (hmemP ℓ G).2 ⟨hℓ, hGS, hcoh⟩⟩ hP · intro _ hne simp at hne