op_639_transversal_four_singleton_nonempty
For any minimal transversal T of size 4 in a hypergraph with covering number at least 4, and any element x in T, there exists an edge e in F such that e ∩ T = {x}.
Statement
theorem op_639_transversal_four_singleton_nonempty {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (htau_ge : ∀ T : Finset V, T.card < 4 → ∃ e ∈ F, Disjoint e T) (T : Finset V) (hT : T.card = 4) (hT_trans : ∀ e ∈ F, ¬Disjoint e T) (x : V) (hx : x ∈ T) : ∃ e ∈ F, e ∩ T = {x}
- Source
- step towards op_639_intersecting_four_uniform_covering_four_card_le_forty_two
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_639_sum_triple_fibers_card_le_twelveIn a 4-uniform intersecting family with tau >= 4 and a transversal T of size 4, the sum of sizes of edges whose intersection with T has…
The proof, explained
Removing x from T leaves a subset of size 3. By the hypothesis that the hypergraph has covering number at least 4, this 3-element set cannot cover all edges, so there exists an edge e ∈ F disjoint from T \setminus {x}. Since T is a transversal, e must still intersect T, and because it avoids every element of T other than x, that intersection must be precisely {x}.
|T \setminus {x}| < 4
Since x ∈ T and |T| = 4, removing x leaves a set of cardinality 4 - 1 = 3, which is strictly less than 4.
uses
Finset.card_erase_of_memhave hcard : (T.erase x).card < 4 := by rw [Finset.card_erase_of_mem hx, hT] norm_num
There exists an edge e ∈ F that is disjoint from T \setminus {x}
Applying the assumption that the covering number is at least 4 (htau_ge) to the 3-element set T \setminus {x} yields an edge e ∈ F disjoint from it.
obtain ⟨e, heF, he_disj⟩ := htau_ge (T.erase x) hcardEvery element in e ∩ T is equal to x
Suppose for contradiction that some y ∈ e ∩ T is not equal to x. Then y ∈ T \setminus {x}, which contradicts the fact that e is disjoint from T \setminus {x}. Therefore, any y ∈ e ∩ T must be x.
uses
Finset.mem_inter,Finset.mem_erase.mpr,Finset.disjoint_left.mphave huniq : ∀ y, y ∈ e ∩ T → y = x := by intro y hy rw [Finset.mem_inter] at hy by_contra hne have hyerase : y ∈ T.erase x := Finset.mem_erase.mpr ⟨hne, hy.2⟩ exact (Finset.disjoint_left.mp he_disj hy.1) hyerase
The intersection e ∩ T is nonempty, and x ∈ e ∩ T
Because T is a transversal, the edge e must intersect T, so e ∩ T is nonempty. Choosing any witness y ∈ e ∩ T, the uniqueness property from the previous step implies y = x, which shows that x ∈ e ∩ T.
uses
Finset.not_disjoint_iff_nonempty_inter.mphave hnonempty : (e ∩ T).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp (hT_trans e heF) obtain ⟨y, hy⟩ := hnonempty have hxy : x ∈ e ∩ T := by simpa [huniq y hy] using hy
The edge e satisfies e ∩ T = {x}
Since x ∈ e ∩ T and every element in e ∩ T equals x, the intersection is exactly the singleton {x}.
uses
Finset.eq_singleton_iff_unique_mem.mprrefine ⟨e, heF, ?_⟩ exact Finset.eq_singleton_iff_unique_mem.mpr ⟨hxy, huniq⟩
Finset.card_erase_of_mem- Removing an element belonging to a finite set decreases its cardinality by 1.
Finset.mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.mem_erase.mpr- An element belongs to the set obtained by erasing a if it is distinct from a and belongs to the original set.
Finset.disjoint_left.mp- If two sets are disjoint, any element of the first set cannot belong to the second set.
Finset.not_disjoint_iff_nonempty_inter.mp- If two sets are not disjoint, their intersection is nonempty.
Finset.eq_singleton_iff_unique_mem.mpr- A finite set equals the singleton {a} if a belongs to the set and every element in the set equals a.
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.
/-- For any minimal transversal T of size 4 in a hypergraph with tau >= 4, and any x in T, there is an edge meeting T in {x}. -/theorem op_639_transversal_four_singleton_nonempty {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (htau_ge : ∀ T : Finset V, T.card < 4 → ∃ e ∈ F, Disjoint e T) (T : Finset V) (hT : T.card = 4) (hT_trans : ∀ e ∈ F, ¬Disjoint e T) (x : V) (hx : x ∈ T) : ∃ e ∈ F, e ∩ T = {x} := by have hcard : (T.erase x).card < 4 := by rw [Finset.card_erase_of_mem hx, hT] norm_num obtain ⟨e, heF, he_disj⟩ := htau_ge (T.erase x) hcard have huniq : ∀ y, y ∈ e ∩ T → y = x := by intro y hy rw [Finset.mem_inter] at hy by_contra hne have hyerase : y ∈ T.erase x := Finset.mem_erase.mpr ⟨hne, hy.2⟩ exact (Finset.disjoint_left.mp he_disj hy.1) hyerase have hnonempty : (e ∩ T).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp (hT_trans e heF) obtain ⟨y, hy⟩ := hnonempty have hxy : x ∈ e ∩ T := by simpa [huniq y hy] using hy refine ⟨e, heF, ?_⟩ exact Finset.eq_singleton_iff_unique_mem.mpr ⟨hxy, huniq⟩