AFTD Auto-Formalizing Theoretical Domains

op869_many_shared_colors

theoremverified

If |B| < |A| and every element of A meets at least d elements of B, then at least d elements of B lie in at least two of the sets.

Statement

theorem op869_many_shared_colors {α β : Type} [DecidableEq β]
    (A : Finset α) (B : Finset β) (E : α → Finset β) (d : ℕ)
    (hE : ∀ x ∈ A, E x ⊆ B) (hd : ∀ x ∈ A, d ≤ (E x).card) (hab : B.card < A.card) :
    d ≤ (B.filter (fun u => 2 ≤ (A.filter (fun x => u ∈ E x)).card)).card
Source
arXiv:2610.41516, Lemma 2.2 (the case i = 2)
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • op869_double_countDouble counting in a bipartite incidence: if every element x of A meets at least d elements of B, then for i ≤ |A|, |A|·d ≤ |B|·(i-1) +…
  • 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…

The proof, explained

The theorem is proved by applying a double-counting inequality with threshold i = 2. The case d = 0 is trivial, while d > 0 together with |B| < |A| implies |A| ≥ 2, validating the double-counting bound |A| · d ≤ |B| + (|A| - 1) · b₂, where b₂ counts the elements of B shared by at least two sets. Assuming for contradiction that fewer than d elements are shared, algebraic rearrangement leads to |A| ≤ |B|, which directly contradicts |B| < |A|.

  1. The inequality holds trivially when d = 0.

    We split into cases based on whether d = 0 or d > 0 using Nat.eq_zero_or_pos. When d = 0, the inequality 0 ≤ |{u ∈ B | 2 ≤ |{x ∈ A | u ∈ E(x)}|}| holds immediately because cardinalities are non-negative.

    lines 5–6

    uses Nat.eq_zero_or_pos

      rcases Nat.eq_zero_or_pos d with hd0 | hd0
      · omega
  2. The cardinality of A is at least 2.

    When d > 0, since |B| < |A|, the set A must have positive cardinality and is therefore nonempty by Finset.card_pos.mp. Picking an element x ∈ A, we have 1 ≤ d ≤ |E(x)| by le_trans. Because E(x) ⊆ B, Finset.card_le_card gives |E(x)| ≤ |B|, so 1 ≤ |B|. Combining this with |B| < |A| yields |A| ≥ 2.

    lines 7–11

    uses Finset.card_pos.mp, le_trans, Finset.card_le_card

      have hA2 : 2 ≤ A.card := by
        obtain ⟨x, hx⟩ : A.Nonempty := Finset.card_pos.mp (by omega)
        have h1 : 1 ≤ (E x).card := le_trans hd0 (hd x hx)
        have h2 := Finset.card_le_card (hE x hx)
        omega
  3. The double-counting inequality applies for threshold i = 2.

    We apply the helper theorem op869_double_count with threshold i = 2, which is valid because 2 ≤ |A|. Abbreviating the number of elements of B that belong to at least two of the sets E(x) as b₂, the lemma yields |A| · d ≤ |B| · (2 - 1) + (|A| - 2 + 1) · b₂.

    lines 12–13

    uses op869_double_count

      have h := op869_double_count A B E d 2 hE hd hA2
      set b2 := (B.filter (fun u => 2 ≤ (A.filter (fun x => u ∈ E x)).card)).card
  4. Assuming b₂ < d for contradiction, re-index |A| and d to simplify the double-counting bound.

    We argue by contradiction and suppose b₂ < d. Since |A| ≥ 2 and d ≥ 1, we can write |A| = a' + 2 and d = d' + 1 for natural numbers a' and d'. Substituting these representations into the double-counting bound and simplifying (a' + 2) - 2 to a' with Nat.add_sub_cancel gives (a' + 2)(d' + 1) ≤ |B| + (a' + 1) · b₂, while the contradiction hypothesis becomes b₂ ≤ d'.

    lines 14–20

    uses Nat.add_sub_cancel

      by_contra hlt
      push Not at hlt
      obtain ⟨a', ha'⟩ : ∃ a', A.card = a' + 2 := ⟨A.card - 2, by omega⟩
      obtain ⟨d', hd'⟩ : ∃ d', d = d' + 1 := ⟨d - 1, by omega⟩
      rw [ha', hd'] at h
      rw [hd'] at hlt
      simp only [Nat.add_sub_cancel] at h
  5. The assumption b₂ < d implies |A| ≤ |B|, contradicting |B| < |A|.

    From b₂ ≤ d', multiplying both sides by a' + 1 with Nat.mul_le_mul_left gives (a' + 1) · b₂ ≤ (a' + 1) · d'. Combined with the simplified double-counting inequality, this yields (a' + 2)(d' + 1) ≤ |B| + (a' + 1) · d'. Expanding the left-hand side as (a' + 1) · d' + a' + d' + 2 and canceling (a' + 1) · d' shows that |A| + d' = a' + d' + 2 ≤ |B|. Since d' ≥ 0, this forces |A| ≤ |B|, directly contradicting the hypothesis |B| < |A|.

    lines 21–22

    uses Nat.mul_le_mul_left

      have h3 : (a' + 1) * b2 ≤ (a' + 1) * d' := Nat.mul_le_mul_left _ (by omega)
      nlinarith
Nat.eq_zero_or_pos
Every natural number is either zero or strictly positive.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most that of the other.
op869_double_count
If each subset E(x) ⊆ B has size at least d, then |A| · d ≤ |B|(i - 1) + (|A| - i + 1) · |{u ∈ B | |{x ∈ A | u ∈ E(x)}| ≥ i}| for any i ≤ |A|.
Nat.add_sub_cancel
Subtracting a number that was just added yields the original number: (n + m) - m = n.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers by a factor preserves the inequality.

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 op869_many_shared_colors {α β : Type} [DecidableEq β]    (A : Finset α) (B : Finset β) (E : α → Finset β) (d : ℕ)    (hE : ∀ x ∈ A, E x ⊆ B) (hd : ∀ x ∈ A, d ≤ (E x).card) (hab : B.card < A.card) :    d ≤ (B.filter (fun u => 2 ≤ (A.filter (fun x => u ∈ E x)).card)).card := by  rcases Nat.eq_zero_or_pos d with hd0 | hd0  · omega  have hA2 : 2 ≤ A.card := by    obtain ⟨x, hx⟩ : A.Nonempty := Finset.card_pos.mp (by omega)    have h1 : 1 ≤ (E x).card := le_trans hd0 (hd x hx)    have h2 := Finset.card_le_card (hE x hx)    omega  have h := op869_double_count A B E d 2 hE hd hA2  set b2 := (B.filter (fun u => 2 ≤ (A.filter (fun x => u ∈ E x)).card)).card  by_contra hlt  push Not at hlt  obtain ⟨a', ha'⟩ : ∃ a', A.card = a' + 2 := ⟨A.card - 2, by omega⟩  obtain ⟨d', hd'⟩ : ∃ d', d = d' + 1 := ⟨d - 1, by omega⟩  rw [ha', hd'] at h  rw [hd'] at hlt  simp only [Nat.add_sub_cancel] at h  have h3 : (a' + 1) * b2 ≤ (a' + 1) * d' := Nat.mul_le_mul_left _ (by omega)  nlinarith
See it in the graphDiscuss this resultChallenge it