AFTD Auto-Formalizing Theoretical Domains

digraph_reach_within_zero_iff

theoremverified

Sanity: a directed walk of length at most 0 from u to v exists iff u = v.

Statement

theorem digraph_reach_within_zero_iff {V : Type*} (D : Digraph V) (u v : V) :
    digraph_reach_within D 0 u v ↔ u = v
Source
sanity lemma for digraph_reach_within
Verified
25 Oct 2026
Axioms
none — Lean reports it depends on no axioms
Built on 1
  • digraph_reach_withindigraph_reach_within D k u v: there is a directed walk of length at most k from u to v in the digraph D (equivalently, the directed…

The proof, explained

By definition of `digraph_reach_within`, reaching a vertex $v$ from $u$ within $0$ steps is identical to $u = v$. Because both sides of the equivalence are definitionally the same proposition, the statement holds immediately by reflexivity of `↔`.

  1. `digraph_reach_within D 0 u v` is equivalent to `u = v`

    By definition, reachability within $0$ steps (`digraph_reach_within D 0 u v`) is defined directly as equality $u = v$. Because the left-hand side reduces definitionally to the right-hand side, the equivalence holds by the reflexivity of `↔` (`Iff.rfl`).

    line 2

    uses Iff.rfl

        digraph_reach_within D 0 u v ↔ u = v := Iff.rfl
Iff.rfl
Any proposition is equivalent to itself: $P \leftrightarrow P$.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem digraph_reach_within_zero_iff {V : Type*} (D : Digraph V) (u v : V) :    digraph_reach_within D 0 u v ↔ u = v := Iff.rfl
See it in the graphDiscuss this resultChallenge it