AFTD Auto-Formalizing Theoretical Domains

finite_single_outside_sets_biunion_card_le

theoremverified

For a finite family of sets each containing at most one point outside S, their union contains at most one such point per set.

Statement

theorem finite_single_outside_sets_biunion_card_le {V : Type*} [DecidableEq V]
    (S : Finset V) (R : Finset (Finset V))
    (houtside : ∀ t ∈ R, (t \ S).card ≤ 1) :
    ((R.biUnion id) \ S).card ≤ R.card
Source
Counting forbidden vertices in simple_graph_triangle_packing_pair_deletion_forcing_quadratic_kernel; state/campaigns/triangle_reductions/quadratic_kernel_in687.md.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof distributes the set difference over the union to establish the inclusion (⋃_{t ∈ R} t) \ S ⊆ ⋃_{t ∈ R} (t \ S). Monotonicity of cardinality then bounds |(⋃ R) \ S| by the cardinality of ⋃_{t ∈ R} (t \ S). Because each set in R contains at most one element outside S, the union of these differences has size at most |R| * 1 = |R|. Chaining these inequalities gives the desired bound.

  1. (⋃_{t ∈ R} t) \ S ⊆ ⋃_{t ∈ R} (t \ S)

    To show that the difference of the union is contained in the union of differences, let v ∈ (⋃ R) \ S. Unfolding the definition of set difference (Finset.mem_sdiff.mp) gives v ∈ ⋃ R and v ∉ S. Membership in the union (Finset.mem_biUnion.mp) yields some set t ∈ R with v ∈ t. Since v ∉ S as well, v ∈ t \ S (Finset.mem_sdiff.mpr), which witnesses that v ∈ ⋃_{t ∈ R} (t \ S) (Finset.mem_biUnion.mpr).

    lines 5–10

    uses Finset.mem_sdiff.mp, Finset.mem_biUnion.mp, Finset.mem_biUnion.mpr, Finset.mem_sdiff.mpr

      classical
      have hs : (R.biUnion id) \ S ⊆ R.biUnion (fun t => t \ S) := by
        intro v hv
        obtain ⟨hvr,hvs⟩ := Finset.mem_sdiff.mp hv
        obtain ⟨t,ht,hvt⟩ := Finset.mem_biUnion.mp hvr
        exact Finset.mem_biUnion.mpr ⟨t,ht,Finset.mem_sdiff.mpr ⟨hvt,hvs⟩⟩
  2. The cardinality of (⋃_{t ∈ R} t) \ S is at most |R|.

    Applying monotonicity of cardinality (Finset.card_le_card) to the inclusion from the previous step yields |(⋃ R) \ S| ≤ |⋃_{t ∈ R} (t \ S)|. Since each set t ∈ R satisfies |t \ S| ≤ 1 by hypothesis, the union of these |R| sets has cardinality at most |R| * 1 (Finset.card_biUnion_le_card_mul), which simplifies to |R| (Nat.mul_one). Finally, linear arithmetic (omega) combines these two inequalities by transitivity to conclude |(⋃ R) \ S| ≤ |R|.

    lines 11–14

    uses Finset.card_le_card, Finset.card_biUnion_le_card_mul, Nat.mul_one

      have hc := Finset.card_le_card hs
      have hB := Finset.card_biUnion_le_card_mul R (fun t => t \ S) 1 houtside
      simp only [Nat.mul_one] at hB
      omega
Finset.mem_sdiff.mp
An element belongs to a set difference A \ B only if it belongs to A and does not belong to B.
Finset.mem_biUnion.mp
An element belongs to a union of sets indexed by a family only if it belongs to at least one set in the family.
Finset.mem_biUnion.mpr
If an element belongs to some set in an indexed family, it belongs to the union of that family.
Finset.mem_sdiff.mpr
If an element belongs to A and does not belong to B, then it belongs to the set difference A \ B.
Finset.card_le_card
If a finite set s is a subset of a finite set t, then |s| ≤ |t|.
Finset.card_biUnion_le_card_mul
The cardinality of a union of a family of sets s, each having cardinality at most n, is at most |s| * n.
Nat.mul_one
For any natural number n, n * 1 = n.

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 finite_single_outside_sets_biunion_card_le {V : Type*} [DecidableEq V]    (S : Finset V) (R : Finset (Finset V))    (houtside : ∀ t ∈ R, (t \ S).card ≤ 1) :    ((R.biUnion id) \ S).card ≤ R.card := by  classical  have hs : (R.biUnion id) \ S ⊆ R.biUnion (fun t => t \ S) := by    intro v hv    obtain ⟨hvr,hvs⟩ := Finset.mem_sdiff.mp hv    obtain ⟨t,ht,hvt⟩ := Finset.mem_biUnion.mp hvr    exact Finset.mem_biUnion.mpr ⟨t,ht,Finset.mem_sdiff.mpr ⟨hvt,hvs⟩⟩  have hc := Finset.card_le_card hs  have hB := Finset.card_biUnion_le_card_mul R (fun t => t \ S) 1 houtside  simp only [Nat.mul_one] at hB  omega
See it in the graphDiscuss this resultChallenge it