AFTD Auto-Formalizing Theoretical Domains

SavitchMidpoint

def

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
See it in the graphDiscuss this resultChallenge it