AFTD Auto-Formalizing Theoretical Domains

tournament_inversion_number_reverse

theoremverifiedformalization

For a finite tournament D: inv(D̄) = inv(D), where D̄ is D with every arc reversed.

Statement

theorem tournament_inversion_number_reverse (V : Type) [Fintype V] (D : Digraph V)
    (h : digraph_is_tournament D) :
    digraph_inversion_number (digraph_reverse D) = digraph_inversion_number D
Formalizes
arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 4 ("a set of inversions decycle D if and only if they decycle D̄, so inv(D) = inv(D̄)").
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

The proof, explained

The equality is proved by establishing the mutual bounds inv(D̄) ≤ inv(D) and inv(D) ≤ inv(D̄) via antisymmetry. Each direction applies an existing lemma stating that an arc-reversing vertex map from a digraph into a tournament bounds the inversion number; the identity map gives the required reversal in both directions, using the fact that reversing a tournament produces another tournament.

  1. To show inv(D̄) = inv(D), it suffices to prove inv(D̄) ≤ inv(D) and inv(D) ≤ inv(D̄).

    By the antisymmetry of the partial order on natural numbers (le_antisymm), an equality follows from proving inequalities in both directions.

    line 4

    uses le_antisymm

      apply le_antisymm
  2. inv(D̄) ≤ inv(D)

    We apply the comparison lemma digraph_inversion_number_le_of_adj_iff_reverse with G = D̄, E = D, and the identity map. The hypothesis that D is a tournament is given by h, and the adjacency-reversal condition (D̄.Adj x y ↔ D.Adj y x) holds definitionally by reflexivity of equivalence (Iff.rfl).

    line 5

    uses digraph_inversion_number_le_of_adj_iff_reverse, Iff.rfl

      · exact digraph_inversion_number_le_of_adj_iff_reverse _ D id h (fun x y => Iff.rfl)
  3. inv(D) ≤ inv(D̄)

    We apply the same comparison lemma in the opposite direction, with G = D, E = D̄, and the identity map. The requirement that D̄ is a tournament is supplied by digraph_reverse_is_tournament, and the adjacency condition (D.Adj x y ↔ D̄.Adj y x) again holds definitionally by reflexivity (Iff.rfl).

    lines 6–7

    uses digraph_inversion_number_le_of_adj_iff_reverse, digraph_reverse_is_tournament, Iff.rfl

      · exact digraph_inversion_number_le_of_adj_iff_reverse D (digraph_reverse D) id
          (digraph_reverse_is_tournament D h) (fun x y => Iff.rfl)
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
digraph_inversion_number_le_of_adj_iff_reverse
If E is a finite tournament and f reverses adjacencies between G and E (that is, G.Adj x y ↔ E.Adj (f y) (f x)), then digraph_inversion_number G ≤ digraph_inversion_number E.
digraph_reverse_is_tournament
The reversal of any tournament is also a tournament.
Iff.rfl
Any proposition is logically equivalent to itself (P ↔ P).

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_inversion_number_reverse (V : Type) [Fintype V] (D : Digraph V)    (h : digraph_is_tournament D) :    digraph_inversion_number (digraph_reverse D) = digraph_inversion_number D := by  apply le_antisymm  · exact digraph_inversion_number_le_of_adj_iff_reverse _ D id h (fun x y => Iff.rfl)  · exact digraph_inversion_number_le_of_adj_iff_reverse D (digraph_reverse D) id      (digraph_reverse_is_tournament D h) (fun x y => Iff.rfl)
See it in the graphDiscuss this resultChallenge it