AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_rooted_triangle_unsafe

theoremverified

Every directed triangle through zero in the displayed graph has an outside vertex pointing to all three of its vertices.

Statement

theorem digraph_safe17_rooted_triangle_unsafe :
    ∀ a b : Fin 17,
      digraph_safe17_graph.Adj 0 a → digraph_safe17_graph.Adj a b →
      digraph_safe17_graph.Adj b 0 → ∃ x : Fin 17,
      x ≠ 0 ∧ x ≠ a ∧ x ≠ b ∧
      digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧
      digraph_safe17_graph.Adj x b
Source
Finite safe-cycle obstruction for OP-110; experiment 13260.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The proof proceeds by exhaustive finite verification. First, it registers a decidability instance for the adjacency relation of the 17-vertex tournament. With decidability established, the theorem—a bounded first-order sentence over Fin 17—is closed automatically by the decide tactic via direct computational evaluation over all vertex tuples.

  1. Adjacency in digraph_safe17_graph is decidable for all pairs of vertices.

    We fix two arbitrary vertices u and v in Fin 17, unfold the definition of the graph to expose the edge condition (v - u).val ∈ {1, 2, 3, 5, 6, 7, 13}, and invoke Lean's typeclass synthesis (infer_instance) to conclude decidability of membership in this explicit finite set of natural numbers.

    lines 2–4

      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. Every directed triangle through 0 has an external common predecessor pointing to all three vertices. automation

    Because Fin 17 is a finite domain and all relations and connectives in the statement are decidable, the proposition is decidable by exhaustive computation. The decide tactic verifies all 289 pairs (a, b) in Fin 17 × Fin 17: whenever 0 → a → b → 0 forms a directed triangle, it finds a suitable vertex x ∉ {0, a, b} pointing to 0, a, and b.

    line 13

      decide

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

private instance in504_safe17_decAdj_1 : DecidableRel digraph_safe17_graph.Adj := by  intro u v  unfold digraph_safe17_graph  infer_instancetheorem digraph_safe17_rooted_triangle_unsafe :    ∀ a b : Fin 17,      digraph_safe17_graph.Adj 0 a → digraph_safe17_graph.Adj a b →      digraph_safe17_graph.Adj b 0 → ∃ x : Fin 17,      x ≠ 0 ∧ x ≠ a ∧ x ≠ b ∧      digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧      digraph_safe17_graph.Adj x b := by  decide
See it in the graphDiscuss this resultChallenge it