AFTD Auto-Formalizing Theoretical Domains

finite_family_lexicographic_cover_critical_expansion

theoremverified

For a finite set family and covers H and C, suppose C has minimum cardinality and, among minimum covers, minimizes the number of points outside H. Every nonempty subset X of C outside H has strictly more than |X| points of H among those family members whose C-points all belong to X.

Statement

theorem finite_family_lexicographic_cover_critical_expansion
    {α : Type*} [DecidableEq α] (F : Finset (Finset α)) (H C : Finset α)
    (hH : ∀ t ∈ F, ¬ Disjoint H t)
    (hC : ∀ t ∈ F, ¬ Disjoint C t)
    (hlex : ∀ D : Finset α, (∀ t ∈ F, ¬ Disjoint D t) →
      C.card ≤ D.card ∧ (D.card = C.card → (C \ H).card ≤ (D \ H).card)) :
    ∀ X : Finset α, X ⊆ C \ H → X.Nonempty →
      X.card < (H ∩ ((F.filter (fun t => t ∩ C ⊆ X)).biUnion id)).card
Source
Elementary transversal exchange, the multi-point form of the private-member argument.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by constructing an alternative cover D = (C \\ X) ∪ N, where N consists of those points of H belonging to edges whose intersection with C lies entirely inside X. Any edge either contains a vertex of C \\ X ⊆ D, or intersects C only within X and therefore contains a vertex of N ⊆ D, ensuring D is indeed a cover. If |X| ≥ |N|, then |D| ≤ |C|, so D must achieve the minimum cover cardinality |C|. However, D \\ H = (C \\ H) \\ X has strictly fewer elements outside H than C does (since X is nonempty), violating the secondary minimality of C.

  1. Fix a nonempty subset X ⊆ C \\ H, and define the set N ⊆ H of relevant points of H.

    Assume classical logic. Let X be a nonempty subset of C \\ H, and define N as the set of points in H that belong to some hyperedge t ∈ F whose intersection with C is entirely contained in X. Every point of X belongs to C (so X ⊆ C), and by construction every point of N belongs to H (so N ⊆ H).

    lines 9–13

    uses Finset.mem_sdiff.mp, Finset.inter_subset_left

      classical
      intro X hX hXne
      let N : Finset α := H ∩ ((F.filter (fun t => t ∩ C ⊆ X)).biUnion id)
      have hXC : X ⊆ C := fun x hx => (Finset.mem_sdiff.mp (hX hx)).1
      have hNH : N ⊆ H := Finset.inter_subset_left
  2. C and N are disjoint.

    Suppose some point a belongs to both C and N. Since a ∈ N, a must belong to H and to some edge t ∈ F with t ∩ C ⊆ X. Since a ∈ C and a ∈ t, it follows that a ∈ t ∩ C ⊆ X. But X ⊆ C \\ H, which means a ∉ H, contradicting a ∈ H.

    lines 14–21

    uses Finset.disjoint_left.mpr, Finset.mem_biUnion.mp, Finset.mem_inter.mp, Finset.mem_filter.mp, Finset.mem_inter.mpr, Finset.mem_sdiff.mp

      have hCN : Disjoint C N := by
        apply Finset.disjoint_left.mpr
        intro a haC haN
        have haH : a ∈ H := hNH haN
        obtain ⟨t, htF, hat⟩ := Finset.mem_biUnion.mp (Finset.mem_inter.mp haN).2
        have htX : t ∩ C ⊆ X := (Finset.mem_filter.mp htF).2
        have haX : a ∈ X := htX (Finset.mem_inter.mpr ⟨hat, haC⟩)
        exact (Finset.mem_sdiff.mp (hX haX)).2 haH
  3. Define the candidate cover D = (C \\ X) ∪ N, where C \\ X and N are disjoint.

    We form D by removing X from C and adding N. Because C and N are disjoint, the subset C \\ X is also disjoint from N.

    lines 22–23

    uses Finset.sdiff_subset

      let D := (C \ X) ∪ N
      have hDN : Disjoint (C \ X) N := hCN.mono_left Finset.sdiff_subset
  4. D is a cover of F, meaning every edge t ∈ F intersects D.

    Suppose for contradiction that some edge t ∈ F is disjoint from D. Every element in t ∩ C must belong to X, because any element in (t ∩ C) \\ X would lie in C \\ X ⊆ D, a contradiction. Hence t ∩ C ⊆ X. Because H covers F, t contains some point a ∈ H. But any point in H belonging to an edge t with t ∩ C ⊆ X belongs to N ⊆ D by definition, which again contradicts the disjointness of D and t.

    lines 24–36

    uses Finset.mem_inter.mp, Finset.mem_union_left, Finset.mem_sdiff.mpr, Finset.disjoint_left.mp, Finset.not_disjoint_iff.mp, Finset.mem_inter.mpr, Finset.mem_biUnion.mpr, Finset.mem_filter.mpr, Finset.mem_union_right

      have hDcover : ∀ t ∈ F, ¬ Disjoint D t := by
        intro t ht hdis
        have htX : t ∩ C ⊆ X := by
          intro a ha
          have hat := (Finset.mem_inter.mp ha).1
          have haC := (Finset.mem_inter.mp ha).2
          by_contra haX
          have haD : a ∈ D := Finset.mem_union_left N (Finset.mem_sdiff.mpr ⟨haC, haX⟩)
          exact (Finset.disjoint_left.mp hdis) haD hat
        obtain ⟨a, haH, hat⟩ := Finset.not_disjoint_iff.mp (hH t ht)
        have haN : a ∈ N := Finset.mem_inter.mpr ⟨haH,
          Finset.mem_biUnion.mpr ⟨t, Finset.mem_filter.mpr ⟨ht, htX⟩, hat⟩⟩
        exact (Finset.disjoint_left.mp hdis) (Finset.mem_union_right _ haN) hat
  5. The cardinality of D is |C| - |X| + |N|.

    Since C \\ X and N are disjoint, the cardinality of their union is |C \\ X| + |N|. Because X ⊆ C, |C \\ X| = |C| - |X|.

    lines 37–39

    uses Finset.card_union_of_disjoint, Finset.card_sdiff_of_subset

      have hDcard : D.card = C.card - X.card + N.card := by
        rw [show D = (C \ X) ∪ N from rfl, Finset.card_union_of_disjoint hDN,
          Finset.card_sdiff_of_subset hXC]
  6. The points of D outside H are exactly (C \\ H) \\ X, with cardinality |C \\ H| - |X|.

    An element belongs to D \\ H if and only if it belongs to ((C \\ X) ∪ N) \\ H. Because N ⊆ H, no element of N survives removing H, so this reduces to (C \\ X) \\ H = (C \\ H) \\ X. Since X ⊆ C \\ H, the cardinality of this difference is |C \\ H| - |X|.

    lines 40–46

    uses Finset.mem_sdiff, Finset.mem_union, Finset.card_sdiff_of_subset

      have hDoutside : D \ H = (C \ H) \ X := by
        ext a
        simp only [D, Finset.mem_sdiff, Finset.mem_union]
        have ha : a ∈ N → a ∈ H := fun h => hNH h
        aesop
      have hDoutsidecard : (D \ H).card = (C \ H).card - X.card := by
        rw [hDoutside, Finset.card_sdiff_of_subset hX]
  7. Strict expansion holds: |X| < |N|.

    By the lexicographic minimality of C, any cover D satisfies |C| ≤ |D|, with |C \\ H| ≤ |D \\ H| whenever |D| = |C|. If we had |X| ≥ |N|, then |D| = |C| - |X| + |N| ≤ |C|, which forces |D| = |C|. The secondary condition then gives |C \\ H| ≤ |D \\ H| = |C \\ H| - |X|, which implies |X| ≤ 0. But X is assumed nonempty, so |X| > 0, a contradiction.

    lines 47–55

    uses Finset.card_pos.mpr, Finset.card_le_card

      obtain ⟨hminimum, hsecondary⟩ := hlex D hDcover
      have hXpos : 0 < X.card := Finset.card_pos.mpr hXne
      have hle : X.card ≤ C.card := Finset.card_le_card hXC
      have hle2 : X.card ≤ (C \ H).card := Finset.card_le_card hX
      change X.card < N.card
      by_contra hbad
      have heq : D.card = C.card := by omega
      have hh := hsecondary heq
      omega
Finset.card_pos.mpr
A finite set has strictly positive cardinality if and only if it is nonempty.
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.card_sdiff_of_subset
If s is a subset of t, then the cardinality of t \\ s is |t| - |s|.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.disjoint_left.mp
If s and t are disjoint, no element belongs to both.
Finset.disjoint_left.mpr
If no element of s belongs to t, then s and t are disjoint.
Finset.inter_subset_left
The intersection of two sets is a subset of the first set.
Finset.mem_biUnion.mp
An element belongs to a bounded union of a family of sets if and only if it belongs to one of the sets in the family.
Finset.mem_biUnion.mpr
If an element belongs to some set in a family, it belongs to the bounded union of that family.
Finset.mem_filter.mp
An element belongs to the filtered subset if and only if it belongs to the set and satisfies the predicate.
Finset.mem_filter.mpr
If an element belongs to a set and satisfies the predicate, it belongs to the filtered subset.
Finset.mem_inter.mp
An element belongs to the intersection of two sets only if it belongs to both sets.
Finset.mem_inter.mpr
An element belongs to the intersection of two sets if it belongs to both sets.
Finset.mem_sdiff
An element belongs to s \\ t if and only if it belongs to s and does not belong to t.
Finset.mem_sdiff.mp
If an element belongs to s \\ t, then it belongs to s and does not belong to t.
Finset.mem_sdiff.mpr
If an element belongs to s and does not belong to t, then it belongs to s \\ t.
Finset.mem_union
An element belongs to the union of two sets if and only if it belongs to at least one of them.
Finset.mem_union_left
An element belonging to the left set belongs to the union.
Finset.mem_union_right
An element belonging to the right set belongs to the union.
Finset.not_disjoint_iff.mp
Two sets are not disjoint if and only if there is an element belonging to both.
Finset.sdiff_subset
The difference s \\ t is always a subset of s.

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_family_lexicographic_cover_critical_expansion    {α : Type*} [DecidableEq α] (F : Finset (Finset α)) (H C : Finset α)    (hH : ∀ t ∈ F, ¬ Disjoint H t)    (hC : ∀ t ∈ F, ¬ Disjoint C t)    (hlex : ∀ D : Finset α, (∀ t ∈ F, ¬ Disjoint D t) →      C.card ≤ D.card ∧ (D.card = C.card → (C \ H).card ≤ (D \ H).card)) :    ∀ X : Finset α, X ⊆ C \ H → X.Nonempty →      X.card < (H ∩ ((F.filter (fun t => t ∩ C ⊆ X)).biUnion id)).card := by  classical  intro X hX hXne  let N : Finset α := H ∩ ((F.filter (fun t => t ∩ C ⊆ X)).biUnion id)  have hXC : X ⊆ C := fun x hx => (Finset.mem_sdiff.mp (hX hx)).1  have hNH : N ⊆ H := Finset.inter_subset_left  have hCN : Disjoint C N := by    apply Finset.disjoint_left.mpr    intro a haC haN    have haH : a ∈ H := hNH haN    obtain ⟨t, htF, hat⟩ := Finset.mem_biUnion.mp (Finset.mem_inter.mp haN).2    have htX : t ∩ C ⊆ X := (Finset.mem_filter.mp htF).2    have haX : a ∈ X := htX (Finset.mem_inter.mpr ⟨hat, haC⟩)    exact (Finset.mem_sdiff.mp (hX haX)).2 haH  let D := (C \ X) ∪ N  have hDN : Disjoint (C \ X) N := hCN.mono_left Finset.sdiff_subset  have hDcover : ∀ t ∈ F, ¬ Disjoint D t := by    intro t ht hdis    have htX : t ∩ C ⊆ X := by      intro a ha      have hat := (Finset.mem_inter.mp ha).1      have haC := (Finset.mem_inter.mp ha).2      by_contra haX      have haD : a ∈ D := Finset.mem_union_left N (Finset.mem_sdiff.mpr ⟨haC, haX⟩)      exact (Finset.disjoint_left.mp hdis) haD hat    obtain ⟨a, haH, hat⟩ := Finset.not_disjoint_iff.mp (hH t ht)    have haN : a ∈ N := Finset.mem_inter.mpr ⟨haH,      Finset.mem_biUnion.mpr ⟨t, Finset.mem_filter.mpr ⟨ht, htX⟩, hat⟩⟩    exact (Finset.disjoint_left.mp hdis) (Finset.mem_union_right _ haN) hat  have hDcard : D.card = C.card - X.card + N.card := by    rw [show D = (C \ X) ∪ N from rfl, Finset.card_union_of_disjoint hDN,      Finset.card_sdiff_of_subset hXC]  have hDoutside : D \ H = (C \ H) \ X := by    ext a    simp only [D, Finset.mem_sdiff, Finset.mem_union]    have ha : a ∈ N → a ∈ H := fun h => hNH h    aesop  have hDoutsidecard : (D \ H).card = (C \ H).card - X.card := by    rw [hDoutside, Finset.card_sdiff_of_subset hX]  obtain ⟨hminimum, hsecondary⟩ := hlex D hDcover  have hXpos : 0 < X.card := Finset.card_pos.mpr hXne  have hle : X.card ≤ C.card := Finset.card_le_card hXC  have hle2 : X.card ≤ (C \ H).card := Finset.card_le_card hX  change X.card < N.card  by_contra hbad  have heq : D.card = C.card := by omega  have hh := hsecondary heq  omega
See it in the graphDiscuss this resultChallenge it