AFTD Auto-Formalizing Theoretical Domains

finset_transversal_number

def

The 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 set S in C.

Statement

noncomputable def finset_transversal_number {V : Type*} [Fintype V] [DecidableEq V]
    (C : Finset (Finset V)) : ℕ
Defined in
arXiv:2611.01102 Sec. 2, line 138
Verified
03 Nov 2026
Axioms
none listed
Used by 5

Read back from the Lean

For a finite type V with decidable equality, and a finite collection of finite subsets of V, C : Finset (Finset V), finset_transversal_number C is defined as the infimum (sInf) in ℕ of the set of natural numbers k such that there exists a finite subset T : Finset V of cardinality k with the property that for every S ∈ C, T ∩ S is nonempty (i.e., T is a transversal / hitting set of C).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The transversal number of a collection of subsets is the minimum cardinality of a set intersecting each member. -/
noncomputable def finset_transversal_number {V : Type*} [Fintype V] [DecidableEq V]
    (C : Finset (Finset V)) : ℕ := sInf { k : ℕ | ∃ T : Finset V, (∀ S ∈ C, (T ∩ S).Nonempty) ∧ T.card = k }
See it in the graphDiscuss this resultChallenge it