savitch_midpoint_mono
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
- 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
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.
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.
uses
Or.inlinduction k with | zero => dsimp [SavitchMidpoint] exact Or.inl rfl
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.
| succ k ih => dsimp [SavitchMidpoint] exact ⟨v, ih, ih⟩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.
uses
savitch_midpoint_mono_refldsimp [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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩