AFTD Auto-Formalizing Theoretical Domains

ejr_greedy_cohesive_pair_aux

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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 ℓ.

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

    lines 10–12

    uses Finset.strongInduction

      classical
      induction S using Finset.strongInduction with
      | H S ih =>
  2. 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.

    lines 13–18

    uses Finset.card_le_univ, Nat.mul_le_mul_left, Nat.sub_le

        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⟩
  3. 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.

    lines 19–27

    uses Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_powerset

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

    lines 28–40

    uses Nat.mul_pos, Finset.nonempty_iff_ne_empty, Finset.card_empty, zero_mul, Finset.sdiff_ssubset, Finset.exists_subset_card_eq

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

    lines 41–50

    uses Finset.card_sdiff_add_card_eq_card, Finset.card_union_le, Nat.mul_le_mul_right, Nat.add_le_add, Nat.add_mul

          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, ?_, ?_⟩
  6. 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.

    lines 51–65

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

    lines 66–80

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

    lines 81–101

    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_right

            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⟩
  9. 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}.

    lines 102–141

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

    lines 142–146

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

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

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