AFTD Auto-Formalizing Theoretical Domains

savitch_midpoint_mono

theoremverified

The Savitch midpoint reachability relation is monotone in the recursion depth: for any relation r on V, any depth k, and any vertices u and v, if SavitchMidpoint r k u v holds, then SavitchMidpoint r (k + 1) u v also holds.

Statement

theorem savitch_midpoint_mono {V : Type*} (r : V → V → Prop) (k : ℕ) {u v : V}
    (h : SavitchMidpoint r k u v) : SavitchMidpoint r (k + 1) u v
Source
Savitch 1970, Section 2; Sipser, Theorem 8.5
Verified
12 Oct 2026
Axioms
none — Lean reports it depends on no axioms
Built on 1
  • SavitchMidpointThe 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…
Used by 1

Read back from the Lean

For any type V, any binary relation r : V → V → Prop, any natural number k : ℕ, and any elements u, v : V, if SavitchMidpoint r k u v holds, then SavitchMidpoint r (k + 1) u v holds.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof establishes that reachability at depth k implies reachability at depth k + 1 by choosing the destination vertex v itself as the intermediate midpoint witness. This reduces the goal to reachability from u to v at depth k (which is the hypothesis) and reachability from v to v at depth k. The required reflexivity property is proved beforehand by induction on k, where the base step holds by reflexivity of equality and the induction step repeatedly takes v as its own midpoint.

  1. In the auxiliary reflexivity lemma, the base case k = 0 holds: SavitchMidpoint r 0 v v.

    By induction on k, we first establish the base case k = 0. Unfolding the definition of SavitchMidpoint r 0 v v yields v = v ∨ r v v, which holds by reflexivity of equality via Or.inl.

    lines 3–6

    uses Or.inl

      induction k with
      | zero =>
        dsimp [SavitchMidpoint]
        exact Or.inl rfl
  2. In the auxiliary reflexivity lemma, the inductive step holds: SavitchMidpoint r (k + 1) v v follows from SavitchMidpoint r k v v.

    Unfolding SavitchMidpoint r (k + 1) v v requires finding an intermediate vertex w such that SavitchMidpoint r k v w and SavitchMidpoint r k w v. Choosing w = v, both conjuncts are provided by the induction hypothesis ih.

    lines 7–9

      | succ k ih =>
        dsimp [SavitchMidpoint]
        exact ⟨v, ih, ih⟩
  3. If SavitchMidpoint r k u v holds, then SavitchMidpoint r (k + 1) u v holds.

    Unfolding SavitchMidpoint r (k + 1) u v requires an intermediate vertex w such that SavitchMidpoint r k u w and SavitchMidpoint r k w v. Taking w = v, the first half is the assumption h, and the second half is reflexivity at depth k provided by savitch_midpoint_mono_refl.

    lines 14–15

    uses savitch_midpoint_mono_refl

      dsimp [SavitchMidpoint]
      exact ⟨v, h, savitch_midpoint_mono_refl r k v⟩
Or.inl
If a proposition a holds, then the disjunction a ∨ b holds.
savitch_midpoint_mono_refl
For any binary relation r, depth k, and vertex v, the relation SavitchMidpoint r k v v holds (reflexivity at depth k).

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

lemma savitch_midpoint_mono_refl {V : Type*} (r : V → V → Prop) (k : ℕ) (v : V) :    SavitchMidpoint r k v v := by  induction k with  | zero =>    dsimp [SavitchMidpoint]    exact Or.inl rfl  | succ k ih =>    dsimp [SavitchMidpoint]    exact ⟨v, ih, ih⟩/-- Savitch midpoint reachability is monotone in recursion depth: R_k(r, u, v) implies R_{k+1}(r, u, v). -/theorem savitch_midpoint_mono {V : Type*} (r : V → V → Prop) (k : ℕ) {u v : V}    (h : SavitchMidpoint r k u v) : SavitchMidpoint r (k + 1) u v := by  dsimp [SavitchMidpoint]  exact ⟨v, h, savitch_midpoint_mono_refl r k v⟩
See it in the graphDiscuss this resultChallenge it