AFTD Auto-Formalizing Theoretical Domains

finset_transversal_number_mono

theoremverified

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

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

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

    lines 5–7

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

    lines 8–12

    uses Finset.univ_inter

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

    lines 13–14

    uses Nat.sInf_mem

      have hmem : sInf S2 ∈ S2 := Nat.sInf_mem hS2_nonempty
      rcases hmem with ⟨T, hT, hTcard⟩
  4. 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.

    lines 15–18

      have hmem1 : sInf S2 ∈ S1 := by
        refine ⟨T, ?_, hTcard⟩
        intro S hS
        exact hT S (h hS)
  5. 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.

    line 19

    uses Nat.sInf_le

      exact 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

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