AFTD Auto-Formalizing Theoretical Domains

tournament_dijoin_inversion_number_le_add

theoremverifiedformalization

For finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂), by inverting an optimal family of D₁ and then one of D₂.

Statement

theorem tournament_dijoin_inversion_number_le_add
    (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W)
    (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) :
    digraph_inversion_number (digraph_dijoin D₁ D₂) ≤
      digraph_inversion_number D₁ + digraph_inversion_number D₂
Formalizes
arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 1 ("it is easy to see that inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂)").
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • 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…
  • 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_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
  • digraph_dijoinThe dijoin D₁ → D₂: disjoint copies of D₁ and D₂ together with every arc from a vertex of D₁ to a vertex of D₂.
  • 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…
  • tournament_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
  • digraph_is_acyclic_dijoinThe dijoin of two acyclic digraphs is acyclic: a directed walk never comes back from the D₂ side to the D₁ side.
  • tournament_exists_family_length_eq_inversion_numberFor a finite tournament D, the inversion number is attained: some decycling family of D has exactly inv(D) sets.
Used by 3

The proof, explained

The inversion number of a tournament is the minimum number of subset inversions needed to make it acyclic. We obtain optimal inverting families Xs for D₁ and Ys for D₂ of lengths inv(D₁) and inv(D₂). Because inverting a subset lying entirely within one component leaves all cross-edges and the other component intact, successively inverting the embedded family Xs and then the embedded family Ys produces the dijoin of the two acyclic graphs. Since the dijoin of acyclic graphs is acyclic, this concatenated family witnesses that inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂).

  1. There exist optimal inverting families Xs for D₁ and Ys for D₂ of lengths inv(D₁) and inv(D₂), respectively, that render each tournament acyclic.

    Applying tournament_exists_family_length_eq_inversion_number to tournaments D₁ and D₂ yields an inverting list Xs of length inv(D₁) making D₁ acyclic, and an inverting list Ys of length inv(D₂) making D₂ acyclic.

    lines 6–7

    uses tournament_exists_family_length_eq_inversion_number

      obtain ⟨Xs, hXl, hXa⟩ := tournament_exists_family_length_eq_inversion_number V D₁ h₁
      obtain ⟨Ys, hYl, hYa⟩ := tournament_exists_family_length_eq_inversion_number W D₂ h₂
  2. Inverting the dijoin E₁ → E₂ by a subset X ⊆ V (embedded via Sum.inl) inverts only the left digraph E₁ and preserves the rest of the dijoin (stepL).

    We verify that the adjacency relations agree for all vertex pairs (x, y) in V ⊕ W. By case analysis on whether x and y belong to V or W, cross-edges from V to W as well as edges within W never have both endpoints in Sum.inl '' X, so they are not inverted. For pairs both in V, both endpoints lie in Sum.inl '' X if and only if they lie in X, which matches the inversion of E₁ by X.

    lines 8–21

    uses Or.inl, Or.inr

      have stepL : ∀ (E₁ : Digraph V) (E₂ : Digraph W) (X : Set V),
          digraph_invert (digraph_dijoin E₁ E₂) (Sum.inl '' X) =
            digraph_dijoin (digraph_invert E₁ X) E₂ := by
        intro E₁ E₂ X
        ext x y
        rcases x with a | a <;> rcases y with b | b <;>
          simp [digraph_invert, digraph_dijoin]
        constructor
        · rintro (h | ⟨h1, h2⟩)
          · exact Or.inl h
          · exact Or.inr ⟨fun ha hb => h1 _ ha rfl _ hb rfl, h2⟩
        · rintro (h | ⟨h1, h2⟩)
          · exact Or.inl h
          · exact Or.inr ⟨fun x hx hxa y hy hyb => h1 (hxa ▸ hx) (hyb ▸ hy), h2⟩
  3. Inverting the dijoin E₁ → E₂ by a subset Y ⊆ W (embedded via Sum.inr) inverts only the right digraph E₂ and preserves the rest of the dijoin (stepR).

    Symmetrically to stepL, only pairs of vertices with both endpoints in W can both belong to Sum.inr '' Y. Thus, edges within V and cross-edges from V to W are unchanged, while edges within W are inverted precisely when both endpoints lie in Y.

    lines 22–35

    uses Or.inl, Or.inr

      have stepR : ∀ (E₁ : Digraph V) (E₂ : Digraph W) (Y : Set W),
          digraph_invert (digraph_dijoin E₁ E₂) (Sum.inr '' Y) =
            digraph_dijoin E₁ (digraph_invert E₂ Y) := by
        intro E₁ E₂ Y
        ext x y
        rcases x with a | a <;> rcases y with b | b <;>
          simp [digraph_invert, digraph_dijoin]
        constructor
        · rintro (h | ⟨h1, h2⟩)
          · exact Or.inl h
          · exact Or.inr ⟨fun ha hb => h1 _ ha rfl _ hb rfl, h2⟩
        · rintro (h | ⟨h1, h2⟩)
          · exact Or.inl h
          · exact Or.inr ⟨fun x hx hxa y hy hyb => h1 (hxa ▸ hx) (hyb ▸ hy), h2⟩
  4. Iterating inversions along a list Xs of subsets of V (embedded via Sum.inl) transforms the dijoin E₁ → E₂ into (foldl invert E₁ Xs) → E₂ (foldL).

    This is proved by induction on the list Xs. The empty list case holds by definition. In the induction step, folding across X :: Xs simplifies using List.map_cons, List.foldl_cons, the single-step lemma stepL, and the induction hypothesis.

    lines 36–42

    uses List.map_cons, List.foldl_cons

      have foldL : ∀ (Xs : List (Set V)) (E₁ : Digraph V) (E₂ : Digraph W),
          (Xs.map (Sum.inl '' ·)).foldl digraph_invert (digraph_dijoin E₁ E₂) =
            digraph_dijoin (Xs.foldl digraph_invert E₁) E₂ := by
        intro Xs
        induction Xs with
        | nil => intro E₁ E₂; rfl
        | cons X Xs ih => intro E₁ E₂; simp only [List.map_cons, List.foldl_cons, stepL, ih]
  5. Iterating inversions along a list Ys of subsets of W (embedded via Sum.inr) transforms the dijoin E₁ → E₂ into E₁ → (foldl invert E₂ Ys) (foldR).

    This is proved by induction on the list Ys. The empty list case holds by definition. In the induction step, folding across Y :: Ys simplifies using List.map_cons, List.foldl_cons, the single-step lemma stepR, and the induction hypothesis.

    lines 43–49

    uses List.map_cons, List.foldl_cons

      have foldR : ∀ (Ys : List (Set W)) (E₁ : Digraph V) (E₂ : Digraph W),
          (Ys.map (Sum.inr '' ·)).foldl digraph_invert (digraph_dijoin E₁ E₂) =
            digraph_dijoin E₁ (Ys.foldl digraph_invert E₂) := by
        intro Ys
        induction Ys with
        | nil => intro E₁ E₂; rfl
        | cons Y Ys ih => intro E₁ E₂; simp only [List.map_cons, List.foldl_cons, stepR, ih]
  6. The inversion number of the dijoin D₁ → D₂ is at most inv(D₁) + inv(D₂).

    The inversion number is defined as the infimum of lengths of families whose successive inversions produce an acyclic digraph. By Nat.sInf_le, it suffices to exhibit one such family. We concatenate the embedded lists Xs and Ys; its length is inv(D₁) + inv(D₂). Folding over this concatenation splits by List.foldl_append, foldL, and foldR into the dijoin of the two individually inverted tournaments. Since both components are acyclic, their dijoin is acyclic by digraph_is_acyclic_dijoin.

    lines 50–53

    uses Nat.sInf_le, List.foldl_append, digraph_is_acyclic_dijoin

      apply Nat.sInf_le
      refine ⟨Xs.map (Sum.inl '' ·) ++ Ys.map (Sum.inr '' ·), by simp [hXl, hYl], ?_⟩
      rw [List.foldl_append, foldL, foldR]
      exact digraph_is_acyclic_dijoin _ _ hXa hYa
tournament_exists_family_length_eq_inversion_number
Every finite tournament has a sequence of subset inversions of length equal to its inversion number that makes it acyclic.
Or.inl
From a proof of P, deduce P ∨ Q.
Or.inr
From a proof of Q, deduce P ∨ Q.
List.map_cons
Mapping a function over a non-empty list a :: l yields f(a) :: map(f, l).
List.foldl_cons
Left-folding over a non-empty list a :: l from accumulator b equals left-folding over l from f(b, a).
Nat.sInf_le
If a natural number m belongs to a set s of natural numbers, then the infimum of s is at most m.
List.foldl_append
Left-folding over the concatenation l ++ l' equals left-folding over l' starting from the result of folding over l.
digraph_is_acyclic_dijoin
The dijoin of two acyclic directed graphs is acyclic.

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_dijoin_inversion_number_le_add    (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W)    (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) :    digraph_inversion_number (digraph_dijoin D₁ D₂) ≤      digraph_inversion_number D₁ + digraph_inversion_number D₂ := by  obtain ⟨Xs, hXl, hXa⟩ := tournament_exists_family_length_eq_inversion_number V D₁ h₁  obtain ⟨Ys, hYl, hYa⟩ := tournament_exists_family_length_eq_inversion_number W D₂ h₂  have stepL : ∀ (E₁ : Digraph V) (E₂ : Digraph W) (X : Set V),      digraph_invert (digraph_dijoin E₁ E₂) (Sum.inl '' X) =        digraph_dijoin (digraph_invert E₁ X) E₂ := by    intro E₁ E₂ X    ext x y    rcases x with a | a <;> rcases y with b | b <;>      simp [digraph_invert, digraph_dijoin]    constructor    · rintro (h | ⟨h1, h2⟩)      · exact Or.inl h      · exact Or.inr ⟨fun ha hb => h1 _ ha rfl _ hb rfl, h2⟩    · rintro (h | ⟨h1, h2⟩)      · exact Or.inl h      · exact Or.inr ⟨fun x hx hxa y hy hyb => h1 (hxa ▸ hx) (hyb ▸ hy), h2⟩  have stepR : ∀ (E₁ : Digraph V) (E₂ : Digraph W) (Y : Set W),      digraph_invert (digraph_dijoin E₁ E₂) (Sum.inr '' Y) =        digraph_dijoin E₁ (digraph_invert E₂ Y) := by    intro E₁ E₂ Y    ext x y    rcases x with a | a <;> rcases y with b | b <;>      simp [digraph_invert, digraph_dijoin]    constructor    · rintro (h | ⟨h1, h2⟩)      · exact Or.inl h      · exact Or.inr ⟨fun ha hb => h1 _ ha rfl _ hb rfl, h2⟩    · rintro (h | ⟨h1, h2⟩)      · exact Or.inl h      · exact Or.inr ⟨fun x hx hxa y hy hyb => h1 (hxa ▸ hx) (hyb ▸ hy), h2⟩  have foldL : ∀ (Xs : List (Set V)) (E₁ : Digraph V) (E₂ : Digraph W),      (Xs.map (Sum.inl '' ·)).foldl digraph_invert (digraph_dijoin E₁ E₂) =        digraph_dijoin (Xs.foldl digraph_invert E₁) E₂ := by    intro Xs    induction Xs with    | nil => intro E₁ E₂; rfl    | cons X Xs ih => intro E₁ E₂; simp only [List.map_cons, List.foldl_cons, stepL, ih]  have foldR : ∀ (Ys : List (Set W)) (E₁ : Digraph V) (E₂ : Digraph W),      (Ys.map (Sum.inr '' ·)).foldl digraph_invert (digraph_dijoin E₁ E₂) =        digraph_dijoin E₁ (Ys.foldl digraph_invert E₂) := by    intro Ys    induction Ys with    | nil => intro E₁ E₂; rfl    | cons Y Ys ih => intro E₁ E₂; simp only [List.map_cons, List.foldl_cons, stepR, ih]  apply Nat.sInf_le  refine ⟨Xs.map (Sum.inl '' ·) ++ Ys.map (Sum.inr '' ·), by simp [hXl, hYl], ?_⟩  rw [List.foldl_append, foldL, foldR]  exact digraph_is_acyclic_dijoin _ _ hXa hYa
See it in the graphDiscuss this resultChallenge it