AFTD Auto-Formalizing Theoretical Domains

op_979_fort_transversal_number_empty_graph

theoremverifiedformalization

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

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

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

    lines 4–11

    uses Finset.mem_image, Finset.coe_singleton

      intro F hF
      rw [Finset.mem_image] at hF
      obtain ⟨v, _, rfl⟩ := hF
      rw [Finset.coe_singleton]
      constructor
      · exact ⟨v, rfl⟩
      · intro u _
        simp
  2. 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.

    lines 15–21

    uses Finset.mem_image, Finset.mem_inter, Finset.mem_singleton

      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]) hne
  3. 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.

    lines 25–34

    uses le_antisymm, Nat.sInf_le, Finset.card_univ, Finset.mem_image, Finset.univ_inter, Finset.mem_singleton.mpr

      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⟩
  4. 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|.

    lines 35–55

    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]
  5. 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.

    lines 61–73

    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_transversal

      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⟩
  6. 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.

    lines 74–82

    uses Nat.sInf_le, Finset.card_univ, Finset.univ_inter

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

    lines 83–87

    uses le_antisymm, csSup_le, le_csSup

      apply 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

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