digraph_reach_within_zero_iff
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 `↔`.
`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`).
uses
Iff.rfldigraph_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