finset_transversal_number_mono
For any two finite collections C1 ⊆ C2 of nonempty subsets of a finite set V, the transversal number of C1 is at most the transversal number of C2.
Statement
theorem finset_transversal_number_mono {V : Type*} [Fintype V] [DecidableEq V] {C1 C2 : Finset (Finset V)} (h : C1 ⊆ C2) (hne : ∀ S ∈ C2, S.Nonempty) : finset_transversal_number C1 ≤ finset_transversal_number C2
- Source
- step towards op_979_csym_max_nullity_lt_fort_transversal_number
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- finset_transversal_numberThe transversal number of a collection C of subsets of a finite set V is the minimum cardinality of a subset T of V that intersects every…
- Used by 1
- simple_graph_fort_transversal_number_le_all_forts_transversal_numberFor any finite simple graph G, the fort transversal number T(G) is at most the transversal number of the family of all forts of G.
The proof, explained
The transversal number of a hypergraph is defined as the minimum size of a transversal (a set intersecting every hyperedge). Because every edge in C2 is nonempty, the entire ground set V is a transversal, ensuring that C2 possesses a minimum-size transversal T of cardinality τ(C2). Since C1 ⊆ C2, any transversal of C2 is also a transversal of C1, so T witnesses that τ(C2) is among the transversal sizes of C1, which immediately implies τ(C1) ≤ τ(C2).
Unfold the definition of transversal number and set up the sets of transversal sizes S1 and S2.
Unfolding the definition of finset_transversal_number reduces the goal to showing sInf S1 ≤ sInf S2, where S1 and S2 are defined as the sets of sizes k of transversals T for C1 and C2, respectively.
unfold finset_transversal_number set S1 := { k : ℕ | ∃ T : Finset V, (∀ S ∈ C1, (T ∩ S).Nonempty) ∧ T.card = k } set S2 := { k : ℕ | ∃ T : Finset V, (∀ S ∈ C2, (T ∩ S).Nonempty) ∧ T.card = k }
The set S2 of transversal sizes for C2 is nonempty.
The universal set V (Finset.univ) intersects every member S of C2 in V ∩ S = S by Finset.univ_inter. Since every S ∈ C2 is assumed to be nonempty (hne), Finset.univ is a valid transversal for C2, witnessing that |V| ∈ S2.
uses
Finset.univ_interhave hS2_nonempty : S2.Nonempty := by refine ⟨(Finset.univ : Finset V).card, Finset.univ, ?_, rfl⟩ intro S hS rw [Finset.univ_inter] exact hne S hS
There exists a transversal T for C2 of size exactly sInf S2.
Because S2 is a nonempty set of natural numbers, its infimum belongs to S2 by Nat.sInf_mem. Unpacking this membership produces a transversal T of C2 such that |T| = sInf S2.
uses
Nat.sInf_memhave hmem : sInf S2 ∈ S2 := Nat.sInf_mem hS2_nonempty rcases hmem with ⟨T, hT, hTcard⟩
The number sInf S2 belongs to S1.
Since C1 ⊆ C2 (hypothesis h), every set S ∈ C1 also belongs to C2, so the transversal T for C2 also intersects every set in C1. Because |T| = sInf S2, this shows sInf S2 is the size of a transversal for C1, hence sInf S2 ∈ S1.
have hmem1 : sInf S2 ∈ S1 := by refine ⟨T, ?_, hTcard⟩ intro S hS exact hT S (h hS)
sInf S1 ≤ sInf S2.
Because sInf S2 is an element of S1, the infimum of S1 is at most sInf S2 by Nat.sInf_le, closing the goal.
uses
Nat.sInf_leexact Nat.sInf_le hmem1
Finset.univ_inter- The intersection of the universal finset with any finset s is s.
Nat.sInf_mem- If a set of natural numbers is nonempty, its infimum (minimum) is an element of that set.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element of that set.
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.
/-- The transversal number of a subcollection is at most the transversal number of the larger collection, provided every set in the larger collection is nonempty. -/theorem finset_transversal_number_mono {V : Type*} [Fintype V] [DecidableEq V] {C1 C2 : Finset (Finset V)} (h : C1 ⊆ C2) (hne : ∀ S ∈ C2, S.Nonempty) : finset_transversal_number C1 ≤ finset_transversal_number C2 := by unfold finset_transversal_number set S1 := { k : ℕ | ∃ T : Finset V, (∀ S ∈ C1, (T ∩ S).Nonempty) ∧ T.card = k } set S2 := { k : ℕ | ∃ T : Finset V, (∀ S ∈ C2, (T ∩ S).Nonempty) ∧ T.card = k } have hS2_nonempty : S2.Nonempty := by refine ⟨(Finset.univ : Finset V).card, Finset.univ, ?_, rfl⟩ intro S hS rw [Finset.univ_inter] exact hne S hS have hmem : sInf S2 ∈ S2 := Nat.sInf_mem hS2_nonempty rcases hmem with ⟨T, hT, hTcard⟩ have hmem1 : sInf S2 ∈ S1 := by refine ⟨T, ?_, hTcard⟩ intro S hS exact hT S (h hS) exact Nat.sInf_le hmem1