SavitchMidpoint
The Savitch midpoint reachability relation family R_k(r) for a binary relation r on a type V, defined recursively: at step 0, u can reach v if u = v or r u v; at step k + 1, u can reach v if there exists an intermediate vertex w such that u can reach w and w can reach v at step k.
Statement
def SavitchMidpoint {V : Type*} (r : V → V → Prop) : ℕ → V → V → Prop
- Defined in
- Savitch 1970, Section 2; Sipser, Theorem 8.5
- Verified
- 12 Oct 2026
- Axioms
- none listed
- Used by 2
- savitch_midpoint_monoThe Savitch midpoint reachability relation is monotone in the recursion depth: for any relation r on V, any depth k, and any vertices u…
- savitch_depth_topological_potential_boundLet V be a type, r a relation on V, and ℓ : V → ℕ a topological potential such that r u v implies ℓ u < ℓ v. For any vertices s, t with ℓ…
Read back from the Lean
A recursive definition SavitchMidpoint that takes a type V, a binary relation r : V → V → Prop, a natural number, and two elements u, v : V, defined by cases on the natural number:
- At 0, SavitchMidpoint r 0 u v holds if and only if u = v or r u v.
- At k + 1, SavitchMidpoint r (k + 1) u v holds if and only if there exists some w : V such that SavitchMidpoint r k u w holds and SavitchMidpoint r k w v holds.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The k-step Savitch midpoint reachability relation: R_0 is the reflexive closure of r, and R_{k+1} is R_k ∘ R_k. -/ def SavitchMidpoint {V : Type*} (r : V → V → Prop) : ℕ → V → V → Prop | 0, u, v => u = v ∨ r u v | k + 1, u, v => ∃ w, SavitchMidpoint r k u w ∧ SavitchMidpoint r k w v