AFTD Auto-Formalizing Theoretical Domains

digraph_directed_triangle_not_acyclic

theoremverified

The directed triangle 0 → 1 → 2 → 0 is not acyclic.

Statement

theorem digraph_directed_triangle_not_acyclic :
    ¬ digraph_is_acyclic (⟨fun x y : ZMod 3 => y = x + 1⟩ : Digraph (ZMod 3))
Source
Sanity lemma for digraph_is_acyclic (arXiv:2610.13798).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…

The proof, explained

The proof proceeds by contradiction: assuming the directed graph on ZMod 3 with edges y = x + 1 is acyclic, no vertex can have a non-empty path to itself. Applying this to vertex 0, it suffices to construct a cycle from 0 to 0. The cycle is explicitly given by the three consecutive edges 0 → 1, 1 → 2, and 2 → 0 in ZMod 3.

  1. To reach a contradiction, it suffices to find a directed walk from 0 to 0.

    Assume for contradiction that the graph is acyclic (intro h). By definition, acyclicity means that no vertex admits a non-empty directed walk back to itself. Instantiating this at vertex 0 (apply h 0), producing a walk from 0 to 0 yields False.

    lines 3–4

      intro h
      apply h 0
  2. There is a directed walk from 0 to 0 in the directed triangle graph.

    In ZMod 3 with edges defined by y = x + 1, we build the walk 0 → 1 → 2 → 0 step by step: Relation.TransGen.single rfl establishes the edge 0 → 1, the inner Relation.TransGen.tail extends it with 1 → 2, and the outer Relation.TransGen.tail extends it with 2 → 0 back to 0. Each individual edge holds by reflexivity (rfl).

    line 5

    uses Relation.TransGen.tail, Relation.TransGen.single

      exact Relation.TransGen.tail (Relation.TransGen.tail (Relation.TransGen.single rfl) rfl) rfl
Relation.TransGen.single
A single relation step r a b implies the transitive closure Relation.TransGen r a b.
Relation.TransGen.tail
A path in the transitive closure from a to b extended by a single step r b c yields a path from a to c in the transitive closure.

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 digraph_directed_triangle_not_acyclic :    ¬ digraph_is_acyclic (⟨fun x y : ZMod 3 => y = x + 1⟩ : Digraph (ZMod 3)) := by  intro h  apply h 0  exact Relation.TransGen.tail (Relation.TransGen.tail (Relation.TransGen.single rfl) rfl) rfl
See it in the graphDiscuss this resultChallenge it