op_639_fiber_full_card_le_one
In a 4-uniform hypergraph, if T has size 4, any edge satisfying e ∩ T = T must equal T, so there is at most 1 such edge.
Statement
theorem op_639_fiber_full_card_le_one {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (hunif : ∀ e ∈ F, e.card = 4) (T : Finset V) (hT : T.card = 4) : (F.filter (fun e => e ∩ T = T)).card ≤ 1
- Source
- step towards op_639_intersecting_four_uniform_covering_four_card_le_forty_two
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
To show that at most one edge e ∈ F satisfies e ∩ T = T, it suffices to show that any two such edges e and f are identical. Because e ∩ T = T implies T ⊆ e, and both e and T have cardinality 4, any such edge must equal T itself. Since both e and f equal T, they must be equal to each other.
To show the filtered set has cardinality at most 1, it suffices to prove that any two edges e, f ∈ F with e ∩ T = T and f ∩ T = T are equal.
By Finset.card_le_one_iff, a finite set has size at most 1 if and only if any two of its elements are identical. Applying Finset.mem_filter to the membership hypotheses for two elements e and f in the filtered set yields that e, f ∈ F, e ∩ T = T, and f ∩ T = T.
uses
Finset.card_le_one_iff,Finset.mem_filterrw [Finset.card_le_one_iff] intro e f he hf simp only [Finset.mem_filter] at he hf
The edge e must equal T.
The condition e ∩ T = T means T ⊆ e by Finset.inter_eq_right. Since F is 4-uniform and T has cardinality 4, we have |e| = 4 and |T| = 4, so |e| ≤ |T|. Because T ⊆ e and |e| ≤ |T|, Finset.eq_of_subset_of_card_le implies T = e, hence e = T.
uses
Finset.inter_eq_right,Finset.eq_of_subset_of_card_lehave hTe : T ⊆ e := by rw [← Finset.inter_eq_right] exact he.2 have he_card : e.card ≤ T.card := by rw [hunif e he.1, hT] have heT : e = T := (Finset.eq_of_subset_of_card_le hTe he_card).symm
The edge f must equal T.
By the exact same reasoning, f ∩ T = T gives T ⊆ f via Finset.inter_eq_right. Because |f| = 4 ≤ |T|, Finset.eq_of_subset_of_card_le implies T = f, so f = T.
uses
Finset.inter_eq_right,Finset.eq_of_subset_of_card_lehave hTf : T ⊆ f := by rw [← Finset.inter_eq_right] exact hf.2 have hf_card : f.card ≤ T.card := by rw [hunif f hf.1, hT] have hfT : f = T := (Finset.eq_of_subset_of_card_le hTf hf_card).symm
The edges e and f are equal, which completes the proof.
Since both e = T and f = T, substituting T for both e and f immediately gives e = f.
rw [heT, hfT]
Finset.card_le_one_iff- A finite set has at most one element if and only if any two elements in it are equal.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.inter_eq_right- The intersection of two sets equals the second set if and only if the second set is a subset of the first.
Finset.eq_of_subset_of_card_le- If a finite set s is a subset of t and the cardinality of t is at most the cardinality of s, then s = t.
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.
/-- At most one edge of a 4-uniform family can satisfy e ∩ T = T for a 4-element transversal T. -/theorem op_639_fiber_full_card_le_one {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (hunif : ∀ e ∈ F, e.card = 4) (T : Finset V) (hT : T.card = 4) : (F.filter (fun e => e ∩ T = T)).card ≤ 1 := by rw [Finset.card_le_one_iff] intro e f he hf simp only [Finset.mem_filter] at he hf have hTe : T ⊆ e := by rw [← Finset.inter_eq_right] exact he.2 have he_card : e.card ≤ T.card := by rw [hunif e he.1, hT] have heT : e = T := (Finset.eq_of_subset_of_card_le hTe he_card).symm have hTf : T ⊆ f := by rw [← Finset.inter_eq_right] exact hf.2 have hf_card : f.card ≤ T.card := by rw [hunif f hf.1, hT] have hfT : f = T := (Finset.eq_of_subset_of_card_le hTf hf_card).symm rw [heT, hfT]