Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 7.34 — Borel-measurable ε\varepsilonε-optimal selectors for upper semicontinuous costs

Proved
BertsekasShreve.SemicontSelection.prop7_34_usc_epsilon_selector

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

dynamic-programmingmeasurable-selectionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1semicontinuity

Let XXX be a metrizable space, YYY a separable metrizable space, DDD an open subset of X×YX\times YX×Y, and f:D→R∗f:D\to R^*f:D→R∗ upper semicontinuous (in the relative topology of DDD). For x∈proj⁡X(D)x\in\operatorname{proj}_X(D)x∈projX​(D) let Dx={y∣(x,y)∈D}D_x=\{y\mid (x,y)\in D\}Dx​={y∣(x,y)∈D} and

f∗(x)=inf⁡y∈Dxf(x,y).f^*(x)=\inf_{y\in D_x}f(x,y).f∗(x)=y∈Dx​inf​f(x,y).

Then proj⁡X(D)\operatorname{proj}_X(D)projX​(D) is open in XXX, f∗f^*f∗ is upper semicontinuous, and for every ε>0\varepsilon>0ε>0 there is a Borel-measurable function φε:proj⁡X(D)→Y\varphi_\varepsilon:\operatorname{proj}_X(D)\to Yφε​:projX​(D)→Y with (x,φε(x))∈D(x,\varphi_\varepsilon(x))\in D(x,φε​(x))∈D for all x∈proj⁡X(D)x\in\operatorname{proj}_X(D)x∈projX​(D) and

f(x,φε(x))≤{f∗(x)+εif f∗(x)>−∞,−1/εif f∗(x)=−∞.f\bigl(x,\varphi_\varepsilon(x)\bigr)\le\begin{cases}f^*(x)+\varepsilon&\text{if }f^*(x)>-\infty,\\[2pt]-1/\varepsilon&\text{if }f^*(x)=-\infty.\end{cases}f(x,φε​(x))≤{f∗(x)+ε−1/ε​if f∗(x)>−∞,if f∗(x)=−∞.​

In contrast to the lower semicontinuous case (Proposition 7.33), the infimum need not be attained, and the proposition provides a Borel-measurable control that is optimal up to ε\varepsilonε, with the bound −1/ε-1/\varepsilon−1/ε when the infimum is −∞-\infty−∞.

Formalization Note fff is a function on all of X×YX\times YX×Y whose values off DDD play no role; its upper semicontinuity is UpperSemicontinuousOn f D, and that of f∗f^*f∗ is relative to proj⁡X(D)=\operatorname{proj}_X(D)=projX​(D)= Prod.fst '' D. The two cases of the bound are stated as two implications. When f∗(x)=+∞f^*(x)=+\inftyf∗(x)=+∞ the first case holds trivially, as in the book, since +∞+ε=+∞+\infty+\varepsilon=+\infty+∞+ε=+∞.

Preamble
import Mathlib
Formal statement
namespace BertsekasShreve.SemicontSelection

open TopologicalSpace

/-- Proposition 7.34 (Bertsekas & Shreve, pp. 154–155). Let `X` be metrizable, `Y` separable
metrizable, `D ⊆ X × Y` open, `f : D → R*` upper semicontinuous, and
`f*(x) = inf_{y ∈ D_x} f(x, y)` on `proj_X(D)` (Eq. (67) of Chapter 7). Then `proj_X(D)` is open,
`f*` is upper semicontinuous, and for every `ε > 0` there is a Borel-measurable
`φ_ε : proj_X(D) → Y` with `Gr(φ_ε) ⊆ D` and, for all `x ∈ proj_X(D)`,
`f(x, φ_ε(x)) ≤ f*(x) + ε` if `f*(x) > −∞` and `f(x, φ_ε(x)) ≤ −1/ε` if `f*(x) = −∞`
(Eq. (68)). `f` is given on all of `X × Y`; only its values on `D` matter. -/
theorem prop7_34_usc_epsilon_selector {X Y : Type*}
    [TopologicalSpace X] [MetrizableSpace X] [MeasurableSpace X] [BorelSpace X]
    [TopologicalSpace Y] [MetrizableSpace Y] [SeparableSpace Y] [MeasurableSpace Y] [BorelSpace Y]
    (D : Set (X × Y)) (hD : IsOpen D) (f : X × Y → EReal) (hf : UpperSemicontinuousOn f D) :
    IsOpen (Prod.fst '' D) ∧
    UpperSemicontinuousOn (fun x => ⨅ (y : Y) (_ : (x, y) ∈ D), f (x, y)) (Prod.fst '' D) ∧
    ∀ ε : ℝ, 0 < ε → ∃ φ : (Prod.fst '' D) → Y, Measurable φ ∧
      ∀ x : (Prod.fst '' D), ((x : X), φ x) ∈ D ∧
        ((⨅ (y : Y) (_ : ((x : X), y) ∈ D), f ((x : X), y)) ≠ ⊥ →
          f ((x : X), φ x) ≤ (⨅ (y : Y) (_ : ((x : X), y) ∈ D), f ((x : X), y)) + (ε : EReal)) ∧
        ((⨅ (y : Y) (_ : ((x : X), y) ∈ D), f ((x : X), y)) = ⊥ →
          f ((x : X), φ x) ≤ ((-1 / ε : ℝ) : EReal)) := by sorry

end BertsekasShreve.SemicontSelection
Source
Bertsekas & Shreve, Stochastic Optimal Control: The Discrete-Time Case, Athena Scientific 1996, pp. 154–155, Proposition 7.34 (Eqs. (67)–(68) of Chapter 7)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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