AFTD Auto-Formalizing Theoretical Domains

tournament_of_symm_matrix_is_tournament

theoremverified

T(G) is a tournament for every matrix G over F₂ (only the entries above the diagonal are read).

Statement

theorem tournament_of_symm_matrix_is_tournament {n : ℕ} (G : Matrix (Fin n) (Fin n) (ZMod 2)) :
    digraph_is_tournament (tournament_of_symm_matrix G)
Source
Sanity lemma for tournament_of_symm_matrix (arXiv:2610.13798).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • tournament_of_symm_matrixThe tournament T(G) of a symmetric n × n matrix G over F₂, on vertices 1, …, n: for i < j the arc goes i → j if G_ij = 0 and j → i if G_ij…
  • digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

The proof, explained

To show that the graph defined by G is a tournament, the proof checks that there are no self-loops and that between any two distinct vertices exactly one directed edge is present. The absence of self-loops holds because adjacency requires a strict inequality between vertex indices, which is impossible for a vertex and itself. For distinct vertices i ≠ j, trichotomy divides into the cases i < j and j < i; in each case, whether the corresponding matrix entry is 0 or 1 uniquely determines which of the two directed edges is present.

  1. Every element of ℤ/2ℤ is either 0 or 1.

    Since ℤ/2ℤ has only two elements, the disjunction a = 0 ∨ a = 1 holds for all elements by finite exhaustion, verified by decide.

    line 3

      have two : ∀ a : ZMod 2, a = 0 ∨ a = 1 := by decide
  2. To show that the constructed graph is a tournament, it suffices to prove that it has no self-loops and that between any two distinct vertices there is a directed edge in exactly one direction.

    By definition, a directed graph is a tournament (digraph_is_tournament) if no vertex has a self-loop (∀ i, ¬ Adj i i) and for all distinct pairs i ≠ j, having an edge from i to j is equivalent to not having an edge from j to i (Adj i j ↔ ¬ Adj j i). We split the proof into these two independent goals.

    line 4

      refine ⟨fun i => ?_, fun i j hij => ?_⟩
  3. The graph contains no self-loops.

    By definition of tournament_of_symm_matrix, an edge from i to j requires either i < j or j < i. When i = j, the strict inequality i < i is false in both disjuncts, so ¬ Adj i i holds immediately.

    line 5

      · simp [tournament_of_symm_matrix]
  4. For distinct vertices i ≠ j, it suffices to consider separately the cases i < j and j < i.

    Unfolding the definition of adjacency between i and j, we must show that (i < j ∧ G i j = 0 ∨ j < i ∧ G j i = 1) is equivalent to ¬ (j < i ∧ G j i = 0 ∨ i < j ∧ G i j = 1). Since i ≠ j, totality of the linear order on Fin n gives either i < j or j < i.

    lines 6–7

    uses lt_or_gt_of_ne

      · simp only [tournament_of_symm_matrix]
        rcases lt_or_gt_of_ne hij with h | h
  5. When i < j, exactly one directed edge connects i and j.

    Since i < j, the reverse inequality j < i is false (by not_lt_of_gt). The matrix entry G i j must be either 0 or 1: if G i j = 0, then the directed edge (i, j) exists and (j, i) does not; if G i j = 1, then (i, j) does not exist and (j, i) does. In both cases, the equivalence holds.

    line 8

    uses not_lt_of_gt

        · rcases two (G i j) with h0 | h0 <;> simp [h, h0, not_lt_of_gt h]
  6. When j < i, exactly one directed edge connects i and j.

    Symmetrically, since j < i, the reverse inequality i < j is false (by not_lt_of_gt). The matrix entry G j i is either 0 or 1: if G j i = 0, the edge (j, i) exists and (i, j) does not; if G j i = 1, the edge (i, j) exists and (j, i) does not. In both cases, the equivalence holds.

    line 9

    uses not_lt_of_gt

        · rcases two (G j i) with h0 | h0 <;> simp [h, h0, not_lt_of_gt h]
lt_or_gt_of_ne
In a linear order, any two distinct elements satisfy a < b or b < a.
not_lt_of_gt
In a preorder, if a < b then b < a is false.

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_of_symm_matrix_is_tournament {n : ℕ} (G : Matrix (Fin n) (Fin n) (ZMod 2)) :    digraph_is_tournament (tournament_of_symm_matrix G) := by  have two : ∀ a : ZMod 2, a = 0 ∨ a = 1 := by decide  refine ⟨fun i => ?_, fun i j hij => ?_⟩  · simp [tournament_of_symm_matrix]  · simp only [tournament_of_symm_matrix]    rcases lt_or_gt_of_ne hij with h | h    · rcases two (G i j) with h0 | h0 <;> simp [h, h0, not_lt_of_gt h]    · rcases two (G j i) with h0 | h0 <;> simp [h, h0, not_lt_of_gt h]
See it in the graphDiscuss this resultChallenge it