AFTD Auto-Formalizing Theoretical Domains

tournament_exists_family_length_eq_inversion_number

theoremverified

For a finite tournament D, the inversion number is attained: some decycling family of D has exactly inv(D) sets.

Statement

theorem tournament_exists_family_length_eq_inversion_number (V : Type) [Fintype V]
    (D : Digraph V) (h : digraph_is_tournament D) :
    ∃ Xs : List (Set V), Xs.length = digraph_inversion_number D ∧
      digraph_is_acyclic (Xs.foldl digraph_invert D)
Source
Helper for the bounds on inversion numbers of dijoins in arXiv:2610.13798 (Sec. 1 and Sec. 4): the infimum defining inv(D) is a minimum.
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • tournament_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
  • digraph_inversion_numberThe inversion number inv(D): the least number p of vertex sets X₁, …, X_p whose successive inversions turn D into an acyclic digraph (0 by…
  • digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
  • digraph_is_acyclicA digraph is acyclic when it has no directed cycle: no vertex reaches itself by a nonempty directed walk. For a tournament this means it…
  • digraph_invertThe inversion of a vertex set X in a digraph D: the digraph obtained by reversing every arc with both endpoints in X and keeping every…
Used by 5

The proof, explained

The inversion number of a tournament D is defined as the infimum of the lengths of all decycling families for D. By `tournament_exists_decycling_family`, every finite tournament admits at least one decycling family, which implies that the set of such lengths is nonempty. Since any nonempty set of natural numbers contains its infimum (`Nat.sInf_mem`), the inversion number is attained by some decycling family.

  1. The set of lengths of decycling families of D is nonempty.

    By `tournament_exists_decycling_family`, there exists at least one decycling family Xs for the tournament D. Taking the length of Xs as a witness, the set of lengths of decycling families of D is nonempty (hne).

    lines 5–7

    uses tournament_exists_decycling_family

      obtain ⟨Xs, hXs⟩ := tournament_exists_decycling_family V D h
      have hne : Set.Nonempty {p | ∃ Xs : List (Set V), Xs.length = p ∧
          digraph_is_acyclic (Xs.foldl digraph_invert D)} := ⟨Xs.length, Xs, rfl, hXs⟩
  2. There exists a decycling family of D whose length equals the inversion number of D.

    By definition, the inversion number of D is the infimum of the set of lengths of decycling families. Applying `Nat.sInf_mem` to the nonempty set established in the previous step guarantees that this infimum belongs to the set, which means there exists a decycling family achieving this minimal length.

    line 8

    uses Nat.sInf_mem

      exact Nat.sInf_mem hne
tournament_exists_decycling_family
Every finite tournament admits a decycling family (a list of vertex sets whose sequential inversion yields an acyclic digraph).
Nat.sInf_mem
Any nonempty set of natural numbers contains its infimum (minimum).

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

theorem tournament_exists_family_length_eq_inversion_number (V : Type) [Fintype V]    (D : Digraph V) (h : digraph_is_tournament D) :    ∃ Xs : List (Set V), Xs.length = digraph_inversion_number D ∧      digraph_is_acyclic (Xs.foldl digraph_invert D) := by  obtain ⟨Xs, hXs⟩ := tournament_exists_decycling_family V D h  have hne : Set.Nonempty {p | ∃ Xs : List (Set V), Xs.length = p ∧      digraph_is_acyclic (Xs.foldl digraph_invert D)} := ⟨Xs.length, Xs, rfl, hXs⟩  exact Nat.sInf_mem hne
See it in the graphDiscuss this resultChallenge it