AFTD Auto-Formalizing Theoretical Domains

Relation.RelatesInSteps.apply_le_apply_add

theoremverifiedformalizationimported Lean

If h : α → ℕ increases by at most 1 on each step of r, then the value of h at the output is at most h at the input plus the number of steps.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
variable {α : Type*} {r : α → α → Prop} {a b c : α} in
lemma Relation.RelatesInSteps.apply_le_apply_add {a b : α} {m : ℕ} (hevals : RelatesInSteps r a b m)
    (h : α → ℕ) (h_step : ∀ a b, r a b → h b ≤ h a + 1) :
    h b ≤ h a + m
Formalizes
CSLib, `Relation.RelatesInSteps.apply_le_apply_add`
Lean proof
By Bolton Bailey, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2025 Bolton Bailey. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • Relation.RelatesInStepsA relation r relates two elements of α in n steps if there is a chain of n pairs (t_i, t_{i+1}) such that r t_i t_{i+1} for…
Used by 1

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true invariable {α : Type*} {r : α → α → Prop} {a b c : α} in/-- If `h : α → ℕ` increases by at most 1 on each step of `r`, then the value of `h` at the output is at most `h` at the input plus the number of steps. -/lemma Relation.RelatesInSteps.apply_le_apply_add {a b : α} {m : ℕ} (hevals : RelatesInSteps r a b m)    (h : α → ℕ) (h_step : ∀ a b, r a b → h b ≤ h a + 1) :    h b ≤ h a + m := by  induction hevals with  | refl => simp  | tail t' t'' k _ hstep ih =>    have h_step' := h_step t' t'' hstep    lia
See it in the graphDiscuss this resultChallenge it