AFTD Auto-Formalizing Theoretical Domains

finite_maximum_packing_conflicts_satisfy_hall

theoremverified

Given a maximum packing P and any packing W of a finite set family, every subpacking X of W meets at least |X| members of P. Thus the bipartite intersection graph from W to P satisfies the matching condition.

Statement

theorem finite_maximum_packing_conflicts_satisfy_hall
    {α : Type*} [DecidableEq α] (F P W : Finset (Finset α))
    (hnonempty : ∀ t ∈ F, t.Nonempty)
    (hPF : P ⊆ F) (hWF : W ⊆ F)
    (hPdis : (P : Set (Finset α)).Pairwise Disjoint)
    (hWdis : (W : Set (Finset α)).Pairwise Disjoint)
    (hmax : ∀ Q : Finset (Finset α), Q ⊆ F →
      (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card) :
    ∀ X : Finset (Finset α), X ⊆ W →
      X.card ≤ (P.filter fun s => ¬ Disjoint s (X.biUnion id)).card
Source
Elementary packing exchange and matching condition; related to the packing definitions in arXiv:2610.15539, Section 1.
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To verify Hall's marriage condition for any subpacking X ⊆ W, we partition the maximum packing P into the subfamily P₀ of sets disjoint from ⋃ X and the neighborhood N of sets intersecting ⋃ X. The combined family P₀ ∪ X is shown to be a valid packing in F because P₀ and X are internally disjoint and cross-disjoint, and they share no common elements since all sets in F are nonempty. By the maximality of P, |P₀| + |X| = |P₀ ∪ X| ≤ |P| = |P₀| + |N|, which after cancelling |P₀| gives |X| ≤ |N|.

  1. For any subpacking X ⊆ W, partitioning P into sets disjoint from and intersecting ⋃ X yields a candidate family P₀ ∪ X ⊆ F.

    We fix an arbitrary subpacking X ⊆ W and partition P into P₀ (the elements of P disjoint from ⋃ X) and N (the elements intersecting ⋃ X). Since P ⊆ F and W ⊆ F, both P₀ and X are subfamilies of F, and therefore their union P₀ ∪ X is also contained in F.

    lines 11–18

    uses filter_subset, union_subset

      open Finset in
      intro X hXW
      let p := fun s : Finset α => Disjoint s (X.biUnion id)
      let P0 := P.filter p
      let N := P.filter (fun s => ¬ p s)
      have hP0F : P0 ⊆ F := (filter_subset p P).trans hPF
      have hXF : X ⊆ F := hXW.trans hWF
      have hQF : P0 ∪ X ⊆ F := union_subset hP0F hXF
  2. The subfamilies P₀ and X are disjoint (P₀ ∩ X = ∅).

    Suppose for contradiction that some set t belongs to both P₀ and X. By membership in P₀, t is disjoint from the union ⋃ X. By membership in X, t is a subset of ⋃ X. Being disjoint from a superset of itself implies that t is disjoint from itself, so t = ∅. But t ∈ X ⊆ F, and every member of F is assumed to be nonempty, a contradiction.

    lines 19–28

    uses disjoint_left, subset_biUnion_of_mem, Disjoint.mono_right, disjoint_self.mp

      have hdisj : Disjoint P0 X := by
        rw [disjoint_left]
        intro t htP0 htX
        have h1 : Disjoint t (X.biUnion id) := (mem_filter.mp htP0).2
        have h2 : t ⊆ X.biUnion id := subset_biUnion_of_mem id htX
        have h3 : Disjoint t t := Disjoint.mono_right h2 h1
        have h4 : t = ∅ := disjoint_self.mp h3
        have h5 : t ∈ F := hXF htX
        have h6 : t.Nonempty := hnonempty t h5
        exact h6.ne_empty h4
  3. Every set in P₀ is disjoint from every set in X.

    Given any a ∈ P₀ and b ∈ X, a is disjoint from the union ⋃ X by definition of P₀. Since b ⊆ ⋃ X, monotonicity of disjointness implies that a and b are disjoint.

    lines 29–32

    uses subset_biUnion_of_mem, Disjoint.mono_right

      have hcross : ∀ a ∈ P0, ∀ b ∈ X, Disjoint a b := by
        intro a ha b hb
        have ha' : Disjoint a (X.biUnion id) := (mem_filter.mp ha).2
        exact Disjoint.mono_right (subset_biUnion_of_mem id hb) ha'
  4. The family P₀ ∪ X is a packing of pairwise disjoint sets.

    Because P₀ ⊆ P and X ⊆ W, each subfamily consists of pairwise disjoint sets. For any two distinct members a, b ∈ P₀ ∪ X, if both belong to P₀ or both belong to X, they are disjoint by hypothesis; if one belongs to P₀ and the other to X, they are disjoint by the cross-disjointness established in the previous step.

    lines 33–44

    uses Set.Pairwise.mono, mem_coe, mem_union

      have hP0_pair : (P0 : Set (Finset α)).Pairwise Disjoint :=
        Set.Pairwise.mono (coe_subset.mpr (filter_subset p P)) hPdis
      have hX_pair : (X : Set (Finset α)).Pairwise Disjoint :=
        Set.Pairwise.mono (coe_subset.mpr hXW) hWdis
      have hQ_pair : ((P0 ∪ X : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by
        intro a ha b hb hab
        rw [mem_coe, mem_union] at ha hb
        rcases ha with ha | ha <;> rcases hb with hb | hb
        · exact hP0_pair ha hb hab
        · exact hcross a ha b hb
        · exact (hcross b hb a ha).symm
        · exact hX_pair ha hb hab
  5. The size of X is at most the number of sets in P that intersect ⋃ X.

    Since P₀ and X are disjoint families, the cardinality of their union is |P₀| + |X|. Because P₀ ∪ X is a packing in F and P is a maximum packing, |P₀| + |X| ≤ |P|. Since P is partitioned into P₀ and N, we also have |P| = |P₀| + |N|. Substituting this into the inequality gives |P₀| + |X| ≤ |P₀| + |N|, and cancelling |P₀| yields |X| ≤ |N|.

    lines 45–52

    uses card_union_of_disjoint, card_filter_add_card_filter_not, Nat.le_of_add_le_add_left

      have hQ_card : (P0 ∪ X).card = P0.card + X.card := card_union_of_disjoint hdisj
      have hle : (P0 ∪ X).card ≤ P.card := hmax (P0 ∪ X) hQF hQ_pair
      have hP_split : P0.card + N.card = P.card := by
        have := @card_filter_add_card_filter_not (Finset α) P p _ _
        exact this
      rw [hQ_card] at hle
      rw [← hP_split] at hle
      exact Nat.le_of_add_le_add_left hle
filter_subset
Filtering a finite set by a predicate produces a subset of the original set.
union_subset
If two finite sets are both subsets of a third set, their union is also a subset of that set.
disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
subset_biUnion_of_mem
For any element x of a finite set s, the set u(x) is a subset of the union of all u(y) for y ∈ s.
Disjoint.mono_right
If a is disjoint from c and b is a subset of c, then a is disjoint from b.
disjoint_self.mp
A set disjoint from itself is empty.
Set.Pairwise.mono
A relation that holds pairwise on a set also holds pairwise on any subset.
mem_coe
An element belongs to a finite set viewed as a set if and only if it belongs to the finite set.
mem_union
An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
card_filter_add_card_filter_not
The number of elements in a finite set satisfying a predicate plus the number not satisfying it equals the total cardinality of the set.
Nat.le_of_add_le_add_left
For natural numbers, a + b ≤ a + c implies b ≤ c.

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_maximum_packing_conflicts_satisfy_hall    {α : Type*} [DecidableEq α] (F P W : Finset (Finset α))    (hnonempty : ∀ t ∈ F, t.Nonempty)    (hPF : P ⊆ F) (hWF : W ⊆ F)    (hPdis : (P : Set (Finset α)).Pairwise Disjoint)    (hWdis : (W : Set (Finset α)).Pairwise Disjoint)    (hmax : ∀ Q : Finset (Finset α), Q ⊆ F →      (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card) :    ∀ X : Finset (Finset α), X ⊆ W →      X.card ≤ (P.filter fun s => ¬ Disjoint s (X.biUnion id)).card := by  open Finset in  intro X hXW  let p := fun s : Finset α => Disjoint s (X.biUnion id)  let P0 := P.filter p  let N := P.filter (fun s => ¬ p s)  have hP0F : P0 ⊆ F := (filter_subset p P).trans hPF  have hXF : X ⊆ F := hXW.trans hWF  have hQF : P0 ∪ X ⊆ F := union_subset hP0F hXF  have hdisj : Disjoint P0 X := by    rw [disjoint_left]    intro t htP0 htX    have h1 : Disjoint t (X.biUnion id) := (mem_filter.mp htP0).2    have h2 : t ⊆ X.biUnion id := subset_biUnion_of_mem id htX    have h3 : Disjoint t t := Disjoint.mono_right h2 h1    have h4 : t = ∅ := disjoint_self.mp h3    have h5 : t ∈ F := hXF htX    have h6 : t.Nonempty := hnonempty t h5    exact h6.ne_empty h4  have hcross : ∀ a ∈ P0, ∀ b ∈ X, Disjoint a b := by    intro a ha b hb    have ha' : Disjoint a (X.biUnion id) := (mem_filter.mp ha).2    exact Disjoint.mono_right (subset_biUnion_of_mem id hb) ha'  have hP0_pair : (P0 : Set (Finset α)).Pairwise Disjoint :=    Set.Pairwise.mono (coe_subset.mpr (filter_subset p P)) hPdis  have hX_pair : (X : Set (Finset α)).Pairwise Disjoint :=    Set.Pairwise.mono (coe_subset.mpr hXW) hWdis  have hQ_pair : ((P0 ∪ X : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by    intro a ha b hb hab    rw [mem_coe, mem_union] at ha hb    rcases ha with ha | ha <;> rcases hb with hb | hb    · exact hP0_pair ha hb hab    · exact hcross a ha b hb    · exact (hcross b hb a ha).symm    · exact hX_pair ha hb hab  have hQ_card : (P0 ∪ X).card = P0.card + X.card := card_union_of_disjoint hdisj  have hle : (P0 ∪ X).card ≤ P.card := hmax (P0 ∪ X) hQF hQ_pair  have hP_split : P0.card + N.card = P.card := by    have := @card_filter_add_card_filter_not (Finset α) P p _ _    exact this  rw [hQ_card] at hle  rw [← hP_split] at hle  exact Nat.le_of_add_le_add_left hle
See it in the graphDiscuss this resultChallenge it