op_979_fort_transversal_number_empty_graph
For the edgeless graph (the empty graph bot) on a finite vertex set V with decidable equality, the fort transversal number equals the number of vertices Fintype.card V.
Statement
theorem op_979_fort_transversal_number_empty_graph {V : Type*} [Fintype V] [DecidableEq V] : simple_graph_fort_transversal_number (⊥ : SimpleGraph V) = Fintype.card V
- Formalizes
- arXiv:2611.01102 Sec. 6, Example 6.2
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simple_graph_fort_transversal_numberThe fort transversal number T(G) of a finite simple graph G on a finite type V with decidable equality is the supremum of the transversal…
- is_compatible_collectionFor an arbitrary type V with decidable equality, a finite collection C of finite subsets of V (C : Finset (Finset V)) is compatible if for…
- 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…
- simple_graph_is_fortFor a simple graph G on an arbitrary type V, a subset F of V is a fort if F is nonempty and for every vertex v not in F, it is not the…
- Used by 1
- op_979_csym_max_nullity_eq_fort_transversal_number_of_edgelessFor the edgeless graph bot on a finite vertex set V with decidable equality, the combinatorially symmetric maximum nullity equals the fort…
Read back from the Lean
For any finite type $V$ with decidable equality, the fort transversal number of the empty graph on $V$ (the simple graph $\bot$ with no edges) equals the cardinality of $V$ (Fintype.card V).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To determine the fort transversal number of the edgeless graph ⊥, we show that the supremum of transversal numbers across all compatible collections of forts equals |V|. First, the collection of all singleton sets is a compatible collection of forts with transversal number |V|, showing that |V| is achievable. Second, because every fort is nonempty, the entire vertex set V intersects every member of any fort collection, meaning no collection can have a transversal number exceeding |V|. Together, these bounds imply that the fort transversal number is exactly |V|.
Every singleton set {v} is a fort in the edgeless graph ⊥.
A subset F of vertices is a fort if it is nonempty and no vertex outside F has exactly one neighbor in F. For any singleton {v}, it is nonempty (containing v). Because the graph ⊥ has no edges, no vertex outside {v} has any neighbors at all, so the condition that no vertex has a unique neighbor in {v} holds vacuously.
uses
Finset.mem_image,Finset.coe_singletonintro F hF rw [Finset.mem_image] at hF obtain ⟨v, _, rfl⟩ := hF rw [Finset.coe_singleton] constructor · exact ⟨v, rfl⟩ · intro u _ simp
The collection of all singleton sets is compatible.
A collection of sets is compatible if for any two distinct members C₁ and C₂ and any x ∈ C₁ ∩ C₂, there is a third member contained in (C₁ ∪ C₂) \ {x}. For any two distinct singletons {v} and {w}, an element x ∈ {v} ∩ {w} would imply v = x = w and therefore {v} = {w}, contradicting that they are distinct. Thus their intersection is empty and the condition holds vacuously.
uses
Finset.mem_image,Finset.mem_inter,Finset.mem_singletonunfold is_compatible_collection intro C1 h1 C2 h2 hne x hx rw [Finset.mem_image] at h1 h2 obtain ⟨v, _, rfl⟩ := h1 obtain ⟨w, _, rfl⟩ := h2 rw [Finset.mem_inter, Finset.mem_singleton, Finset.mem_singleton] at hx exact absurd (by rw [show v = w from hx.1.symm.trans hx.2]) hne
The transversal number of the collection of all singletons is at most |V|.
The transversal number is the infimum of the cardinalities of all transversals (sets intersecting every member of the collection). The universal set V intersects every singleton {v} at v, so V is a transversal. Since |V| = Finset.card_univ, the infimum is at most |V| by Nat.sInf_le.
uses
le_antisymm,Nat.sInf_le,Finset.card_univ,Finset.mem_image,Finset.univ_inter,Finset.mem_singleton.mprclassical unfold finset_transversal_number apply le_antisymm · apply Nat.sInf_le refine ⟨Finset.univ, ?_, Finset.card_univ⟩ intro S hS rw [Finset.mem_image] at hS obtain ⟨v, _, rfl⟩ := hS rw [Finset.univ_inter] exact ⟨v, Finset.mem_singleton.mpr rfl⟩
The transversal number of the collection of all singletons is at least |V|, and therefore equals |V|.
By le_csInf, it suffices to show that any transversal T has cardinality at least |V|. Because T must intersect every singleton {v}, it follows that v ∈ T for every vertex v ∈ V. Thus T equals the entire vertex set V (by Finset.eq_univ_of_forall), so |T| = |V|. Together with the upper bound, this proves the transversal number of the singletons collection is |V|.
uses
le_csInf,Finset.card_univ,Finset.mem_image,Finset.univ_inter,Finset.mem_singleton.mpr,Finset.eq_univ_of_forall,Finset.mem_image.mpr,Finset.mem_univ,Finset.Nonempty,Finset.mem_inter,Finset.mem_singleton· apply le_csInf · refine ⟨Fintype.card V, Finset.univ, ?_, Finset.card_univ⟩ intro S hS rw [Finset.mem_image] at hS obtain ⟨v, _, rfl⟩ := hS rw [Finset.univ_inter] exact ⟨v, Finset.mem_singleton.mpr rfl⟩ · intro k hk obtain ⟨T, hT, rfl⟩ := hk have hTeq : T = Finset.univ := by apply Finset.eq_univ_of_forall intro v have hmem : ({v} : Finset V) ∈ Finset.univ.image (fun v : V => ({v} : Finset V)) := Finset.mem_image.mpr ⟨v, Finset.mem_univ v, rfl⟩ have := hT _ hmem rw [Finset.Nonempty] at this obtain ⟨x, hx⟩ := this rw [Finset.mem_inter, Finset.mem_singleton] at hx rw [← hx.2] exact hx.1 rw [hTeq, Finset.card_univ]
The vertex count |V| is an achievable fort transversal number, so |V| ∈ S.
The fort transversal number is defined as the supremum of the set S of transversal numbers of compatible collections of forts. By the three preceding helper lemmas, the collection C₀ of all singletons is a compatible collection of forts with transversal number |V|. Hence C₀ witnesses that |V| ∈ S.
uses
op_979_fort_transversal_number_empty_graph_singletons_fort,op_979_fort_transversal_number_empty_graph_singletons_compatible,op_979_fort_transversal_number_empty_graph_singletons_transversalclassical unfold simple_graph_fort_transversal_number set C0 : Finset (Finset V) := Finset.univ.image (fun v : V => ({v} : Finset V)) with hC0 have hC0_fort : ∀ F ∈ C0, simple_graph_is_fort (⊥ : SimpleGraph V) (F : Set V) := by rw [hC0]; exact op_979_fort_transversal_number_empty_graph_singletons_fort have hC0_compat : is_compatible_collection C0 := by rw [hC0]; exact op_979_fort_transversal_number_empty_graph_singletons_compatible have hC0_trans : finset_transversal_number C0 = Fintype.card V := by rw [hC0]; exact op_979_fort_transversal_number_empty_graph_singletons_transversal set S : Set ℕ := { k : ℕ | ∃ C : Finset (Finset V), (∀ F ∈ C, simple_graph_is_fort (⊥ : SimpleGraph V) (F : Set V)) ∧ is_compatible_collection C ∧ finset_transversal_number C = k } with hS have hmem : Fintype.card V ∈ S := ⟨C0, hC0_fort, hC0_compat, hC0_trans⟩
Every achievable fort transversal number k ∈ S satisfies k ≤ |V|.
Let k ∈ S be the transversal number of a compatible collection C of forts. Since every member of C is a fort, each member is nonempty. Therefore, the universal set V intersects every set in C, which makes V a transversal of C. Hence the minimal size of a transversal, k, cannot exceed |V| = Finset.card_univ by Nat.sInf_le.
uses
Nat.sInf_le,Finset.card_univ,Finset.univ_interhave hbdd : ∀ k ∈ S, k ≤ Fintype.card V := by intro k hk obtain ⟨C, hCf, hCc, hCt⟩ := hk rw [← hCt] apply Nat.sInf_le refine ⟨Finset.univ, ?_, Finset.card_univ⟩ intro T hT rw [Finset.univ_inter] exact (hCf T hT).1
The fort transversal number of the edgeless graph equals |V|.
Since S is nonempty and bounded above by |V|, its supremum is at most |V| by csSup_le. Conversely, because |V| ∈ S, the supremum is at least |V| by le_csSup. By antisymmetry (le_antisymm), the supremum is |V|.
uses
le_antisymm,csSup_le,le_csSupapply le_antisymm · apply csSup_le · exact ⟨Fintype.card V, hmem⟩ · exact hbdd · exact le_csSup ⟨Fintype.card V, hbdd⟩ hmem
Finset.mem_singleton.mpr- If an element a equals b, then a belongs to the singleton set {b}.
Finset.mem_image.mpr- If an element is the image of some element in a finite set under f, it belongs to the image of the set under f.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.Nonempty- The property that a finite set has at least one element.
Finset.mem_image- An element is in the image of a finite set under f if and only if it is the image of some element in the set.
Finset.coe_singleton- The coercion of a singleton finset to a set is the singleton set.
Finset.mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.mem_singleton- An element belongs to a singleton set {a} if and only if it equals a.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any member of that set.
Finset.card_univ- The cardinality of the universal finset is the number of elements in the finite type.
Finset.univ_inter- The intersection of the universal finset with any finite set s is s.
le_csInf- For a nonempty set in a conditionally complete lattice, any lower bound is less than or equal to the infimum.
Finset.eq_univ_of_forall- A finite subset containing every element of the type is the universal finset.
op_979_fort_transversal_number_empty_graph_singletons_fort- Every singleton subset of vertices is a fort in the edgeless graph ⊥.
op_979_fort_transversal_number_empty_graph_singletons_compatible- The collection of all vertex singleton sets is a compatible collection.
op_979_fort_transversal_number_empty_graph_singletons_transversal- The transversal number of the collection of all vertex singletons equals |V|.
csSup_le- For a nonempty set in a conditionally complete lattice, the supremum is less than or equal to any upper bound.
le_csSup- In a conditionally complete lattice, any element of a set bounded above is less than or equal to the supremum of the 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.
private lemma op_979_fort_transversal_number_empty_graph_singletons_fort {V : Type*} [Fintype V] [DecidableEq V] : ∀ F ∈ Finset.univ.image (fun v : V => ({v} : Finset V)), simple_graph_is_fort (⊥ : SimpleGraph V) (F : Set V) := by intro F hF rw [Finset.mem_image] at hF obtain ⟨v, _, rfl⟩ := hF rw [Finset.coe_singleton] constructor · exact ⟨v, rfl⟩ · intro u _ simpprivate lemma op_979_fort_transversal_number_empty_graph_singletons_compatible {V : Type*} [Fintype V] [DecidableEq V] : is_compatible_collection (Finset.univ.image (fun v : V => ({v} : Finset V))) := by unfold is_compatible_collection intro C1 h1 C2 h2 hne x hx rw [Finset.mem_image] at h1 h2 obtain ⟨v, _, rfl⟩ := h1 obtain ⟨w, _, rfl⟩ := h2 rw [Finset.mem_inter, Finset.mem_singleton, Finset.mem_singleton] at hx exact absurd (by rw [show v = w from hx.1.symm.trans hx.2]) hneprivate lemma op_979_fort_transversal_number_empty_graph_singletons_transversal {V : Type*} [Fintype V] [DecidableEq V] : finset_transversal_number (Finset.univ.image (fun v : V => ({v} : Finset V))) = Fintype.card V := by classical unfold finset_transversal_number apply le_antisymm · apply Nat.sInf_le refine ⟨Finset.univ, ?_, Finset.card_univ⟩ intro S hS rw [Finset.mem_image] at hS obtain ⟨v, _, rfl⟩ := hS rw [Finset.univ_inter] exact ⟨v, Finset.mem_singleton.mpr rfl⟩ · apply le_csInf · refine ⟨Fintype.card V, Finset.univ, ?_, Finset.card_univ⟩ intro S hS rw [Finset.mem_image] at hS obtain ⟨v, _, rfl⟩ := hS rw [Finset.univ_inter] exact ⟨v, Finset.mem_singleton.mpr rfl⟩ · intro k hk obtain ⟨T, hT, rfl⟩ := hk have hTeq : T = Finset.univ := by apply Finset.eq_univ_of_forall intro v have hmem : ({v} : Finset V) ∈ Finset.univ.image (fun v : V => ({v} : Finset V)) := Finset.mem_image.mpr ⟨v, Finset.mem_univ v, rfl⟩ have := hT _ hmem rw [Finset.Nonempty] at this obtain ⟨x, hx⟩ := this rw [Finset.mem_inter, Finset.mem_singleton] at hx rw [← hx.2] exact hx.1 rw [hTeq, Finset.card_univ]/-- For the edgeless graph on a finite vertex set V, T(⊥) = |V|. -/theorem op_979_fort_transversal_number_empty_graph {V : Type*} [Fintype V] [DecidableEq V] : simple_graph_fort_transversal_number (⊥ : SimpleGraph V) = Fintype.card V := by classical unfold simple_graph_fort_transversal_number set C0 : Finset (Finset V) := Finset.univ.image (fun v : V => ({v} : Finset V)) with hC0 have hC0_fort : ∀ F ∈ C0, simple_graph_is_fort (⊥ : SimpleGraph V) (F : Set V) := by rw [hC0]; exact op_979_fort_transversal_number_empty_graph_singletons_fort have hC0_compat : is_compatible_collection C0 := by rw [hC0]; exact op_979_fort_transversal_number_empty_graph_singletons_compatible have hC0_trans : finset_transversal_number C0 = Fintype.card V := by rw [hC0]; exact op_979_fort_transversal_number_empty_graph_singletons_transversal set S : Set ℕ := { k : ℕ | ∃ C : Finset (Finset V), (∀ F ∈ C, simple_graph_is_fort (⊥ : SimpleGraph V) (F : Set V)) ∧ is_compatible_collection C ∧ finset_transversal_number C = k } with hS have hmem : Fintype.card V ∈ S := ⟨C0, hC0_fort, hC0_compat, hC0_trans⟩ have hbdd : ∀ k ∈ S, k ≤ Fintype.card V := by intro k hk obtain ⟨C, hCf, hCc, hCt⟩ := hk rw [← hCt] apply Nat.sInf_le refine ⟨Finset.univ, ?_, Finset.card_univ⟩ intro T hT rw [Finset.univ_inter] exact (hCf T hT).1 apply le_antisymm · apply csSup_le · exact ⟨Fintype.card V, hmem⟩ · exact hbdd · exact le_csSup ⟨Fintype.card V, hbdd⟩ hmem