finite_linear_cover_omit_two_unforced_in_one_triple
Let the union U of a packing cover a linear set family. If two points x,y of the same three-element packed set are not the sole U-point of any family member, then removing x and y from U leaves a cover.
Statement
theorem finite_linear_cover_omit_two_unforced_in_one_triple {α : Type*} [DecidableEq α] (F P : Finset (Finset α)) (hsub : P ⊆ F) (hlinear : (F : Set (Finset α)).Pairwise (fun a b => (a ∩ b).card ≤ 1)) (hcover : ∀ t ∈ F, ¬ Disjoint (P.biUnion id) t) (p : Finset α) (hp : p ∈ P) (hp3 : p.card = 3) (x y : α) (hx : x ∈ p) (hy : y ∈ p) (hne : x ≠ y) (hxunforced : ∀ t ∈ F, t ∩ P.biUnion id ≠ {x}) (hyunforced : ∀ t ∈ F, t ∩ P.biUnion id ≠ {y}) : ∀ t ∈ F, ¬ Disjoint ((P.biUnion id) \ {x,y}) t
- Source
- Elementary linear-family exchange in the triangle packing-cover campaign.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
We argue by contradiction: suppose some family member t ∈ F is disjoint from U \ {x, y}. Since U covers F, t must meet U, and by disjointness from U \ {x, y}, any intersection point must be x or y, so t contains at least one of x or y. Furthermore, t cannot contain both: if t = p, then the third element of p lies in (U \ {x, y}) ∩ t, while if t ≠ p, then |t ∩ p| ≥ 2 violates linearity. Hence t contains exactly one of x or y, which forces t ∩ U to be a singleton ({x} or {y}), contradicting the hypothesis that neither point is forced.
Assume for contradiction that some t ∈ F is disjoint from U \ {x, y}; since U covers F, t must meet U at some element a.
We suppose for contradiction that some set t ∈ F is disjoint from U \ {x, y}, where U is the union of the packing P. The points x and y both belong to U because they belong to p ∈ P. Since U covers every set in F, the set t is not disjoint from U, so there exists some common point a ∈ t ∩ U.
uses
Finset.mem_biUnion.mpr,Finset.not_disjoint_iff.mpintro t ht hdisj have hxU : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨p, hp, hx⟩ have hyU : y ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨p, hp, hy⟩ obtain ⟨a, haU, hat⟩ := Finset.not_disjoint_iff.mp (hcover t ht)
The common element a must be x or y, so t contains at least one of x or y.
If a were neither x nor y, then a would belong to U \ {x, y}. But a also belongs to t, contradicting the assumption that U \ {x, y} and t are disjoint. Hence a = x or a = y. Since a ∈ t, it follows that x ∈ t or y ∈ t.
uses
Finset.mem_sdiff,Finset.disjoint_left.mp,Or.inl,Or.inrhave haxy : a = x ∨ a = y := by by_contra h push_neg at h have ha : a ∈ (P.biUnion id) \ {x,y} := by rw [Finset.mem_sdiff] exact ⟨haU, by simp [h.1, h.2]⟩ exact (Finset.disjoint_left.mp hdisj ha) hat have hxy_mem : x ∈ t ∨ y ∈ t := by rcases haxy with rfl | rfl · exact Or.inl hat · exact Or.inr hat
The set t cannot contain both x and y.
Suppose for contradiction that both x ∈ t and y ∈ t. We split into two cases based on whether t = p or t ≠ p. If t = p, then {x, y} ⊆ p. Since |p| = 3 and x ≠ y, the difference p \ {x, y} has cardinality 3 - 2 = 1, so it contains some element z. This z lies in p ⊆ U and outside {x, y}, hence z ∈ (U \ {x, y}) ∩ t, contradicting the disjointness of U \ {x, y} and t. If instead t ≠ p, then linearity of F implies |t ∩ p| ≤ 1. But both distinct elements x and y belong to t ∩ p, so {x, y} ⊆ t ∩ p, which implies 2 ≤ |t ∩ p|, a contradiction. Therefore t cannot contain both x and y.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.card_sdiff_of_subset,Finset.card_pair,Finset.nonempty_iff_ne_empty,Finset.mem_sdiff,Finset.mem_biUnion.mpr,Finset.disjoint_left.mp,Finset.mem_inter.mpr,Finset.card_le_cardhave hnot_both : ¬ (x ∈ t ∧ y ∈ t) := by rintro ⟨hxt, hyt⟩ by_cases htp : t = p · subst t have hsubxy : ({x,y} : Finset α) ⊆ p := by intro z hz simp only [Finset.mem_insert, Finset.mem_singleton] at hz rcases hz with rfl | rfl · exact hx · exact hy have hcard_sdiff : (p \ {x,y}).card = 1 := by rw [Finset.card_sdiff_of_subset hsubxy, hp3, Finset.card_pair hne] have hnonempty : (p \ {x,y}).Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro h rw [h] at hcard_sdiff simp at hcard_sdiff obtain ⟨z, hzmem⟩ := hnonempty rw [Finset.mem_sdiff] at hzmem obtain ⟨hzp, hzxy⟩ := hzmem have hzU : z ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨p, hp, hzp⟩ have hz' : z ∈ (P.biUnion id) \ {x,y} := by rw [Finset.mem_sdiff] exact ⟨hzU, hzxy⟩ exact (Finset.disjoint_left.mp hdisj hz') hzp · have hcard := hlinear ht (hsub hp) htp have hsubset : ({x,y} : Finset α) ⊆ t ∩ p := by intro z hz simp only [Finset.mem_insert, Finset.mem_singleton] at hz rcases hz with rfl | rfl · exact Finset.mem_inter.mpr ⟨hxt, hx⟩ · exact Finset.mem_inter.mpr ⟨hyt, hy⟩ have hcard2 : 2 ≤ (t ∩ p).card := by calc 2 = ({x,y} : Finset α).card := (Finset.card_pair hne).symm _ ≤ (t ∩ p).card := Finset.card_le_card hsubset omega
The case x ∈ t leads to t ∩ U = {x}, contradicting that x is unforced.
Since x ∈ t and t cannot contain both x and y, we have y ∉ t. For any element z ∈ t ∩ U, disjointness of t and U \ {x, y} requires z = x or z = y. Because y ∉ t, we cannot have z = y, so z = x. Conversely, x ∈ t and x ∈ U, so x ∈ t ∩ U. This shows t ∩ U = {x}, which contradicts the hypothesis that x is unforced (t ∩ U ≠ {x} for all t ∈ F).
uses
Finset.mem_inter,Finset.mem_sdiff,Finset.disjoint_left.mp,False.elim,Finset.mem_singleton,Finset.mem_inter.mprrcases hxy_mem with hxt | hyt · have hyt : y ∉ t := fun h => hnot_both ⟨hxt, h⟩ have hInter : t ∩ (P.biUnion id) = {x} := by ext z constructor · intro hz rw [Finset.mem_inter] at hz obtain ⟨hzt, hzU⟩ := hz have hzxy : z = x ∨ z = y := by by_contra h push_neg at h have hz' : z ∈ (P.biUnion id) \ {x,y} := by rw [Finset.mem_sdiff] exact ⟨hzU, by simp [h.1, h.2]⟩ exact (Finset.disjoint_left.mp hdisj hz') hzt rcases hzxy with rfl | rfl · simp · exact False.elim (hyt hzt) · intro hz rw [Finset.mem_singleton] at hz subst z exact Finset.mem_inter.mpr ⟨hxt, hxU⟩ exact hxunforced t ht hInter
The case y ∈ t leads to t ∩ U = {y}, contradicting that y is unforced.
Symmetrically, since y ∈ t and t cannot contain both x and y, we have x ∉ t. For any z ∈ t ∩ U, disjointness of t and U \ {x, y} forces z ∈ {x, y}, and since x ∉ t, we must have z = y. Thus t ∩ U = {y}, contradicting the hypothesis that y is unforced (t ∩ U ≠ {y} for all t ∈ F). Both cases having yielded a contradiction, the proof is complete.
uses
Finset.mem_inter,Finset.mem_sdiff,Finset.disjoint_left.mp,False.elim,Finset.mem_singleton,Finset.mem_inter.mpr· have hxt : x ∉ t := fun h => hnot_both ⟨h, hyt⟩ have hInter : t ∩ (P.biUnion id) = {y} := by ext z constructor · intro hz rw [Finset.mem_inter] at hz obtain ⟨hzt, hzU⟩ := hz have hzxy : z = x ∨ z = y := by by_contra h push_neg at h have hz' : z ∈ (P.biUnion id) \ {x,y} := by rw [Finset.mem_sdiff] exact ⟨hzU, by simp [h.1, h.2]⟩ exact (Finset.disjoint_left.mp hdisj hz') hzt rcases hzxy with rfl | rfl · exact False.elim (hxt hzt) · simp · intro hz rw [Finset.mem_singleton] at hz subst z exact Finset.mem_inter.mpr ⟨hyt, hyU⟩ exact hyunforced t ht hInter
False.elim- From a contradiction, any proposition follows (ex falso quodlibet).
Finset.disjoint_left.mp- If two sets are disjoint, any element in the first set cannot belong to the second set.
Finset.mem_biUnion.mpr- If an element belongs to a constituent set of a union, it belongs to the union.
Finset.mem_insert- An element belongs to an insert {a} ∪ s if and only if it equals a or belongs to s.
Finset.mem_inter- An element belongs to the intersection of two sets if and only if it belongs to both sets.
Finset.mem_inter.mpr- If an element belongs to both sets, it belongs to their intersection.
Finset.mem_sdiff- An element belongs to the difference s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Finset.not_disjoint_iff.mp- If two sets are not disjoint, they share at least one element.
Finset.card_sdiff_of_subset- If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.card_pair- A set of two distinct elements has cardinality 2.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not the empty set.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Or.inl- From a proposition A, deduces the disjunction A ∨ B.
Or.inr- From a proposition B, deduces the disjunction A ∨ B.
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_linear_cover_omit_two_unforced_in_one_triple {α : Type*} [DecidableEq α] (F P : Finset (Finset α)) (hsub : P ⊆ F) (hlinear : (F : Set (Finset α)).Pairwise (fun a b => (a ∩ b).card ≤ 1)) (hcover : ∀ t ∈ F, ¬ Disjoint (P.biUnion id) t) (p : Finset α) (hp : p ∈ P) (hp3 : p.card = 3) (x y : α) (hx : x ∈ p) (hy : y ∈ p) (hne : x ≠ y) (hxunforced : ∀ t ∈ F, t ∩ P.biUnion id ≠ {x}) (hyunforced : ∀ t ∈ F, t ∩ P.biUnion id ≠ {y}) : ∀ t ∈ F, ¬ Disjoint ((P.biUnion id) \ {x,y}) t := by intro t ht hdisj have hxU : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨p, hp, hx⟩ have hyU : y ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨p, hp, hy⟩ obtain ⟨a, haU, hat⟩ := Finset.not_disjoint_iff.mp (hcover t ht) have haxy : a = x ∨ a = y := by by_contra h push_neg at h have ha : a ∈ (P.biUnion id) \ {x,y} := by rw [Finset.mem_sdiff] exact ⟨haU, by simp [h.1, h.2]⟩ exact (Finset.disjoint_left.mp hdisj ha) hat have hxy_mem : x ∈ t ∨ y ∈ t := by rcases haxy with rfl | rfl · exact Or.inl hat · exact Or.inr hat have hnot_both : ¬ (x ∈ t ∧ y ∈ t) := by rintro ⟨hxt, hyt⟩ by_cases htp : t = p · subst t have hsubxy : ({x,y} : Finset α) ⊆ p := by intro z hz simp only [Finset.mem_insert, Finset.mem_singleton] at hz rcases hz with rfl | rfl · exact hx · exact hy have hcard_sdiff : (p \ {x,y}).card = 1 := by rw [Finset.card_sdiff_of_subset hsubxy, hp3, Finset.card_pair hne] have hnonempty : (p \ {x,y}).Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro h rw [h] at hcard_sdiff simp at hcard_sdiff obtain ⟨z, hzmem⟩ := hnonempty rw [Finset.mem_sdiff] at hzmem obtain ⟨hzp, hzxy⟩ := hzmem have hzU : z ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨p, hp, hzp⟩ have hz' : z ∈ (P.biUnion id) \ {x,y} := by rw [Finset.mem_sdiff] exact ⟨hzU, hzxy⟩ exact (Finset.disjoint_left.mp hdisj hz') hzp · have hcard := hlinear ht (hsub hp) htp have hsubset : ({x,y} : Finset α) ⊆ t ∩ p := by intro z hz simp only [Finset.mem_insert, Finset.mem_singleton] at hz rcases hz with rfl | rfl · exact Finset.mem_inter.mpr ⟨hxt, hx⟩ · exact Finset.mem_inter.mpr ⟨hyt, hy⟩ have hcard2 : 2 ≤ (t ∩ p).card := by calc 2 = ({x,y} : Finset α).card := (Finset.card_pair hne).symm _ ≤ (t ∩ p).card := Finset.card_le_card hsubset omega rcases hxy_mem with hxt | hyt · have hyt : y ∉ t := fun h => hnot_both ⟨hxt, h⟩ have hInter : t ∩ (P.biUnion id) = {x} := by ext z constructor · intro hz rw [Finset.mem_inter] at hz obtain ⟨hzt, hzU⟩ := hz have hzxy : z = x ∨ z = y := by by_contra h push_neg at h have hz' : z ∈ (P.biUnion id) \ {x,y} := by rw [Finset.mem_sdiff] exact ⟨hzU, by simp [h.1, h.2]⟩ exact (Finset.disjoint_left.mp hdisj hz') hzt rcases hzxy with rfl | rfl · simp · exact False.elim (hyt hzt) · intro hz rw [Finset.mem_singleton] at hz subst z exact Finset.mem_inter.mpr ⟨hxt, hxU⟩ exact hxunforced t ht hInter · have hxt : x ∉ t := fun h => hnot_both ⟨h, hyt⟩ have hInter : t ∩ (P.biUnion id) = {y} := by ext z constructor · intro hz rw [Finset.mem_inter] at hz obtain ⟨hzt, hzU⟩ := hz have hzxy : z = x ∨ z = y := by by_contra h push_neg at h have hz' : z ∈ (P.biUnion id) \ {x,y} := by rw [Finset.mem_sdiff] exact ⟨hzU, by simp [h.1, h.2]⟩ exact (Finset.disjoint_left.mp hdisj hz') hzt rcases hzxy with rfl | rfl · exact False.elim (hxt hzt) · simp · intro hz rw [Finset.mem_singleton] at hz subst z exact Finset.mem_inter.mpr ⟨hyt, hyU⟩ exact hyunforced t ht hInter