Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4 (a)–(c) — v_δ is the unique fixed point of H_δ, ρ(v_δ, v) ≤ ρ(H_δ v, v)N/(1 − c), and E exists and has modulus c

Proved
DenardoDP.NStage.theorem4_abc

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

contraction-mappingdynamic-programmingmonotone-operatorp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Work in Denardo's model under the monotonicity and N-stage contraction assumptions: there are a positive integer NNN and c<1c<1c<1 such that every HδNH_\delta^NHδN​ has modulus ccc or less and every HδH_\deltaHδ​ has modulus 111 or less. For each policy δ\deltaδ let vδv_\deltavδ​ be the fixed point of the contraction HδNH_\delta^NHδN​, HδNvδ=vδH_\delta^Nv_\delta=v_\deltaHδN​vδ​=vδ​. Then:

  1. (a) vδv_\deltavδ​ is the unique fixed point of HδH_\deltaHδ​: Hδvδ=vδH_\delta v_\delta=v_\deltaHδ​vδ​=vδ​, and Hδw=wH_\delta w=wHδ​w=w implies w=vδw=v_\deltaw=vδ​;
  2. (b) for every δ\deltaδ and every v∈Vv\in Vv∈V,
ρ(vδ,v)≤ρ(Hδv,v) N1−c;\rho(v_\delta,v)\le\frac{\rho(H_\delta v,v)\,N}{1-c};ρ(vδ​,v)≤1−cρ(Hδ​v,v)N​;
  1. (c) the operator EEE, (Ev)(x)=sup⁡δ(HδNv)(x)(Ev)(x)=\sup_\delta(H_\delta^Nv)(x)(Ev)(x)=supδ​(HδN​v)(x), maps VVV into VVV and has modulus ccc or less;
  2. the optimal return f(x)=sup⁡δvδ(x)f(x)=\sup_\delta v_\delta(x)f(x)=supδ​vδ​(x) is finite at every point and bounded, i.e. f∈Vf\in Vf∈V.

These are the statements the paper establishes in the text of §5 before stating Theorem 4 ("Parts (a)–(c) of the following theorem have just been established"). They are the first half of Theorem 4; the second half identifies fff as the unique fixed point of EEE and of AAA.

Formalization Note The paper defines vδv_\deltavδ​ as the unique fixed point of HδNH_\delta^NHδN​; here vvv is a family of elements of VVV with HδNvδ=vδH_\delta^Nv_\delta=v_\deltaHδN​vδ​=vδ​ for each δ\deltaδ (which exists and is unique by the Banach fixed-point theorem), and Hδvδ=vδH_\delta v_\delta=v_\deltaHδ​vδ​=vδ​ is a conclusion, not a hypothesis. Part (c) is stated existentially: there is an operator E:V→VE:V\to VE:V→V whose value at each point is the least upper bound of {(HδNv)(x)}δ\{(H_\delta^Nv)(x)\}_\delta{(HδN​v)(x)}δ​, and it has modulus ccc or less. The last clause asserts that {vδ(x)}δ\{v_\delta(x)\}_\delta{vδ​(x)}δ​ has a least upper bound at each point and that these form an element of VVV.

Preamble
import Mathlib
import Definitions.Def_DenardoDP_NStage_Model
Formal statement
namespace DenardoDP.NStage

theorem theorem4_abc {Ω : Type*} {D : Ω → Type*}
    (h : (x : Ω) → D x → DenardoDP.Contraction.BFun Ω → ℝ) (H : ((x : Ω) → D x) → DenardoDP.Contraction.BFun Ω → DenardoDP.Contraction.BFun Ω)
    (A : DenardoDP.Contraction.BFun Ω → DenardoDP.Contraction.BFun Ω) (v : ((x : Ω) → D x) → DenardoDP.Contraction.BFun Ω) (N : ℕ) (c : ℝ)
    (hH : DenardoDP.Contraction.IsPolicyOperator h H) (hA : DenardoDP.Contraction.IsMaxOperator h A)
    (hmono : DenardoDP.Contraction.MonotonicityAssumption H) (hN : NStageContractionAssumption H N c)
    (hv : ∀ δ, (H δ)^[N] (v δ) = v δ) :
    (∀ δ, H δ (v δ) = v δ ∧ ∀ w, H δ w = w → w = v δ) ∧
    (∀ δ w, dist (v δ) w ≤ dist (H δ w) w * N / (1 - c)) ∧
    (∃ E : DenardoDP.Contraction.BFun Ω → DenardoDP.Contraction.BFun Ω, IsNStageSupOperator H N E ∧ DenardoDP.Contraction.ModulusLE E c) ∧
    (∃ f : DenardoDP.Contraction.BFun Ω, DenardoDP.Contraction.IsOptimalReturn v f) := by sorry

end DenardoDP.NStage
Source
Denardo, Contraction Mappings in the Theory Underlying Dynamic Programming, SIAM Review 9(2) (1967), p. 169, §5 text preceding Theorem 4, and Theorem 4 (a)–(c)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me