finite_family_lexicographic_cover_critical_expansion
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.
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).
uses
Finset.mem_sdiff.mp,Finset.inter_subset_leftclassical 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
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.
uses
Finset.disjoint_left.mpr,Finset.mem_biUnion.mp,Finset.mem_inter.mp,Finset.mem_filter.mp,Finset.mem_inter.mpr,Finset.mem_sdiff.mphave 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
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.
uses
Finset.sdiff_subsetlet D := (C \ X) ∪ N have hDN : Disjoint (C \ X) N := hCN.mono_left Finset.sdiff_subset
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.
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_righthave 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
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|.
uses
Finset.card_union_of_disjoint,Finset.card_sdiff_of_subsethave 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]
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|.
uses
Finset.mem_sdiff,Finset.mem_union,Finset.card_sdiff_of_subsethave 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]
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.
uses
Finset.card_pos.mpr,Finset.card_le_cardobtain ⟨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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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