AFTD Auto-Formalizing Theoretical Domains

finite_linear_cover_omit_two_unforced_in_one_triple

theoremverified

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.

  1. 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.

    lines 11–14

    uses Finset.mem_biUnion.mpr, Finset.not_disjoint_iff.mp

      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)
  2. 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.

    lines 15–25

    uses Finset.mem_sdiff, Finset.disjoint_left.mp, Or.inl, Or.inr

      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
  3. 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.

    lines 26–62

    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_card

      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
  4. 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).

    lines 63–85

    uses Finset.mem_inter, Finset.mem_sdiff, Finset.disjoint_left.mp, False.elim, Finset.mem_singleton, Finset.mem_inter.mpr

      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
  5. 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.

    lines 86–107

    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

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
See it in the graphDiscuss this resultChallenge it