Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · ParametrizedLimits · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_ParametrizedLimits

by liuyao · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

ca-fd889115-k1

Private dependency for the Distribution Theory mission. Module ComputableAnalysis/ParametrizedLimits.lean from the frozen computable-analysis foundation with kernel-checked rational decision proofs.

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_PowerSeries

set_option autoImplicit true

/-! Parametrized, covered rational enclosures and their exact limit laws. -/
namespace ComputableAnalysis
namespace RawLimit

/-- Exact membership of a valid represented value in a rational interval. -/
def InInterval (y : RealCompute) (I : QInterval) : Prop :=
  (RealCompute.ofRat I.lo).Le y ∧ y.Le (RealCompute.ofRat I.hi)

/-- A sequence of valid represented values converges to a valid represented
value. The positive allowance handles degenerate and one-sided target names. -/
def TendsTo (u : Nat → RealCompute) (x : RealCompute) : Prop :=
  x.Valid ∧ (∀ n, (u n).Valid) ∧
  ∀ m (eps : QPos), ∃ N, ∀ n, N ≤ n →
    InInterval (u n) (QInterval.expand (x.compute m) eps.val)

/-- Explicit two-index view: `n` selects a represented value and `k` refines
that value. Every row is valid; the covered-diagonal compatibility theorem is below. -/
def BisequenceTendsTo (Q : Nat → Nat → QInterval) (x : RealCompute) : Prop :=
  TendsTo (fun n => { compute := Q n }) x

set_option maxHeartbeats 1000000

theorem unique {u : Nat → RealCompute} {x y : RealCompute}
    (hx : TendsTo u x) (hy : TendsTo u y) : x.Equiv y := by
  apply RealCompute.allStagesOverlap_equiv
  intro m k
  apply (RealCompute.compareAt_overlap_iff x y m k).2
  have cross : ∀ X Y : RealCompute, TendsTo u X → TendsTo u Y →
      ∀ i j, (X.compute i).lo ≤ (Y.compute j).hi := by
    intro X Y hX hY i j
    by_cases hgood : (X.compute i).lo ≤ (Y.compute j).hi
    · exact hgood
    exfalso
    have hp : 0 < (X.compute i).lo-(Y.compute j).hi := by grind
    let eps : QPos := ⟨((X.compute i).lo-(Y.compute j).hi)/4,
      by rw [Rat.div_def]; exact Rat.mul_pos hp (Rat.inv_pos.mpr (by decide +kernel))⟩
    obtain ⟨N,hN⟩ := hX.2.2 i eps
    obtain ⟨M,hM⟩ := hY.2.2 j eps
    let n := max N M
    have hlo := (hN n (Nat.le_max_left N M)).1
    have hhi := (hM n (Nat.le_max_right N M)).2
    have hc := RealCompute.le_trans (hX.2.1 n) hlo hhi 0 0
    change (X.compute i).lo-eps.val ≤ (Y.compute j).hi+eps.val at hc
    dsimp [eps] at hc
    grind only [Rat.div_def]
  exact ⟨cross x y hx hy m k,cross y x hy hx k m⟩

theorem congr_target {u : Nat → RealCompute} {x y : RealCompute}
    (h : TendsTo u x) (hy : y.Valid) (hxy : x.Equiv y) : TendsTo u y := by
  refine ⟨hy,h.2.1,?_⟩
  intro m eps
  let half : QPos := ⟨eps.val/2,by rw [Rat.div_def]; exact Rat.mul_pos eps.property (Rat.inv_pos.mpr (by decide +kernel))⟩
  obtain ⟨k,hk⟩ := h.1.2.2 half
  have hw := hk k (Nat.le_refl k)
  have hov := (RealCompute.compareAt_overlap_iff x y k m).1
    (RealCompute.allStagesOverlap_of_equiv h.1 hy hxy k m)
  unfold QInterval.Overlaps at hov
  obtain ⟨N,hN⟩ := h.2.2 k half
  refine ⟨N,fun n hn => ?_⟩
  have hu := hN n hn
  constructor
  · intro i j
    have hl := hu.1 0 j
    change (x.compute k).lo-half.val ≤ ((u n).compute j).hi at hl
    change (y.compute m).lo-eps.val ≤ ((u n).compute j).hi
    dsimp [half] at hw hl
    grind only [QInterval.width, Rat.div_def]
  · intro i j
    have hh := hu.2 i 0
    change ((u n).compute i).lo ≤ (x.compute k).hi+half.val at hh
    change ((u n).compute i).lo ≤ (y.compute m).hi+eps.val
    dsimp [half] at hw hh
    grind only [QInterval.width, Rat.div_def]

theorem congr_target_iff {u : Nat → RealCompute} {x y : RealCompute}
    (hx : x.Valid) (hy : y.Valid) (hxy : x.Equiv y) :
    TendsTo u x ↔ TendsTo u y :=
  ⟨fun h => congr_target h hy hxy,
   fun h => congr_target h hx (RealCompute.equiv_symm hxy)⟩

theorem bisequence_unique {Q : Nat → Nat → QInterval} {x y : RealCompute}
    (hx : BisequenceTendsTo Q x) (hy : BisequenceTendsTo Q y) : x.Equiv y :=
  unique hx hy

theorem bisequence_congr_target {Q : Nat → Nat → QInterval} {x y : RealCompute}
    (hx : x.Valid) (hy : y.Valid) (hxy : x.Equiv y) :
    BisequenceTendsTo Q x ↔ BisequenceTendsTo Q y :=
  congr_target_iff hx hy hxy

theorem congr_sequence {u v : Nat → RealCompute} {x : RealCompute}
    (h : TendsTo u x) (hv : ∀ n, (v n).Valid)
    (huv : ∀ n, (u n).Equiv (v n)) : TendsTo v x := by
  refine ⟨h.1,hv,?_⟩
  intro m eps
  obtain ⟨N,hN⟩ := h.2.2 m eps
  refine ⟨N,fun n hn => ?_⟩
  have hb := hN n hn
  exact ⟨RealCompute.le_trans (h.2.1 n) hb.1
    (RealCompute.le_of_equiv (h.2.1 n) (hv n) (huv n)),
    RealCompute.le_trans (h.2.1 n)
      (RealCompute.le_of_equiv (hv n) (h.2.1 n) (RealCompute.equiv_symm (huv n))) hb.2⟩

/-- Removing a finite prefix from a convergent represented sequence preserves
its limit. -/
theorem shift {u : Nat → RealCompute} {x : RealCompute} (h : TendsTo u x) :
    TendsTo (fun n => u (n+1)) x := by
  refine ⟨h.1,fun n => h.2.1 (n+1),?_⟩
  intro m eps
  obtain ⟨N,hN⟩ := h.2.2 m eps
  refine ⟨N,fun n hn => hN (n+1) (Nat.le_trans hn (Nat.le_succ n))⟩

/-- The (n)-th rational enclosure taken from the (n)-th member of a
sequence. Prefix stabilization turns this diagonal of candidate algorithms
into one raw-real computation. -/
def iterateCandidate (u : Nat → RealCompute) : RealCompute where
  compute n := (u n).compute n

/-- Explicit future enclosures construct the represented limit of a sequence.
The runtime limit is the finite-prefix intersection `prefixStabilize`; the
future-containment and shrinking-radius proofs certify it and show convergence.
This is the constructive completeness step used by the fixed-point theorem. -/
theorem tendsTo_iterateCandidate_stabilization
    {u : Nat → RealCompute} {radius : Nat → Rat}
    (hu : ∀ n, (u n).Valid)
    (hdiagonalShrinks : RealCompute.WidthsShrinkToZero (iterateCandidate u).compute)
    (hfuture : ∀ k n, k ≤ n →
      (QInterval.expand ((iterateCandidate u).compute k) (radius k)).ContainsInterval
        ((iterateCandidate u).compute n))
    (hradius : ShrinksToZero radius) :
    TendsTo u (RealCompute.prefixStabilize (iterateCandidate u) radius) := by
  have hordered : ∀ n,
      ((iterateCandidate u).compute n).lo ≤ ((iterateCandidate u).compute n).hi := by
    intro n
    have hn := hu n
    exact (hn.2.1 n n (Nat.le_refl n)).2.1
  have hlimit := RealCompute.prefixStabilize_valid_of_future_containment
    hordered hdiagonalShrinks hfuture hradius
  refine ⟨hlimit,hu,?_⟩
  intro m eps
  refine ⟨m,fun n hmn => ?_⟩
  have hcontain := RealCompute.prefixStabilize_contains_future_candidate
    hfuture m n hmn
  have hinside : InInterval (u n)
      ((RealCompute.prefixStabilize (iterateCandidate u) radius).compute m) := by
    constructor
    · intro i j
      have hleft := hcontain.1
      have hself := RealCompute.le_refl (u n) (hu n) n j
      change ((RealCompute.prefixStabilize (iterateCandidate u) radius).compute m).lo ≤
        ((u n).compute j).hi
      change ((RealCompute.prefixStabilize (iterateCandidate u) radius).compute m).lo ≤
        ((u n).compute n).lo at hleft
      change ((u n).compute n).lo ≤ ((u n).compute j).hi at hself
      exact Rat.le_trans hleft hself
    · intro i j
      have hright := hcontain.2
      have hself := RealCompute.le_refl (u n) (hu n) i n
      change ((u n).compute i).lo ≤
        ((RealCompute.prefixStabilize (iterateCandidate u) radius).compute m).hi
      change ((u n).compute n).hi ≤
        ((RealCompute.prefixStabilize (iterateCandidate u) radius).compute m).hi at hright
      change ((u n).compute i).lo ≤ ((u n).compute n).hi at hself
      exact Rat.le_trans hself hright
  constructor
  · intro i j
    have h := hinside.1 i j
    change ((RealCompute.prefixStabilize (iterateCandidate u) radius).compute m).lo - eps.val ≤
      ((u n).compute j).hi
    have he := eps.property
    change ((RealCompute.prefixStabilize (iterateCandidate u) radius).compute m).lo ≤
      ((u n).compute j).hi at h
    grind only
  · intro i j
    have h := hinside.2 i j
    change ((u n).compute i).lo ≤
      ((RealCompute.prefixStabilize (iterateCandidate u) radius).compute m).hi + eps.val
    have he := eps.property
    change ((u n).compute i).lo ≤
      ((RealCompute.prefixStabilize (iterateCandidate u) radius).compute m).hi at h
    grind only

/-- Picard's fixed-point conclusion in represented-real form. The convergence
of the iterates and preservation of their limit by the operator are explicit
hypotheses; either may be supplied by a function-specific quantitative
argument. A Lipschitz estimate is one useful sufficient certificate, not a
global requirement on functions in this foundation. -/
theorem fixedPoint_of_iterates_limit {F : RealCompute → RealCompute}
    {u : Nat → RealCompute} {x : RealCompute}
    (hiterates : TendsTo u x)
    (hpreserves : ∀ {v : Nat → RealCompute} {y : RealCompute},
      TendsTo v y → TendsTo (fun n => F (v n)) (F y))
    (hstep : ∀ n, (F (u n)).Equiv (u (n+1))) :
    (F x).Equiv x := by
  have hFx : TendsTo (fun n => F (u n)) (F x) := hpreserves hiterates
  have hshift : TendsTo (fun n => u (n+1)) x := shift hiterates
  have hsame : TendsTo (fun n => F (u n)) x :=
    congr_sequence hshift hFx.2.1 (fun n => RealCompute.equiv_symm (hstep n))
  exact unique hFx hsame

/-- A fully represented-real fixed point from explicit rational Cauchy data
for the iterates. Besides the computable recurrence `F (u n) ≃ u (n+1)`, the
caller supplies the diagonal enclosure and its future-containment/tail
certificates. The fixed point itself is constructed by finite interval
intersections, without assuming a complete function space. -/
theorem fixedPoint_of_cauchy_iterates {F : RealCompute → RealCompute}
    {u : Nat → RealCompute} {radius : Nat → Rat}
    (hu : ∀ n, (u n).Valid)
    (hdiagonalShrinks : RealCompute.WidthsShrinkToZero (iterateCandidate u).compute)
    (hfuture : ∀ k n, k ≤ n →
      (QInterval.expand ((iterateCandidate u).compute k) (radius k)).ContainsInterval
        ((iterateCandidate u).compute n))
    (hradius : ShrinksToZero radius)
    (hpreserves : ∀ {v : Nat → RealCompute} {y : RealCompute},
      TendsTo v y → TendsTo (fun n => F (v n)) (F y))
    (hstep : ∀ n, (F (u n)).Equiv (u (n+1))) :
    (F (RealCompute.prefixStabilize (iterateCandidate u) radius)).Equiv
      (RealCompute.prefixStabilize (iterateCandidate u) radius) :=
  fixedPoint_of_iterates_limit
    (tendsTo_iterateCandidate_stabilization hu hdiagonalShrinks hfuture hradius)
    hpreserves hstep

theorem constant (x : RealCompute) (hx : x.Valid) : TendsTo (fun _ => x) x := by
  refine ⟨hx,fun _ => hx,fun m eps => ⟨0,fun _ _ => ?_⟩⟩
  constructor
  · intro i j
    have h := RealCompute.le_refl x hx m j
    change (x.compute m).lo-eps.val ≤ (x.compute j).hi
    have := eps.property
    grind
  · intro i j
    have h := RealCompute.le_refl x hx i m
    change (x.compute i).lo ≤ (x.compute m).hi+eps.val
    have := eps.property
    grind

/-- An independently valid sequence trapped in shrinking boxes of the target
has that limit. It need not use a prescribed convergence rate. -/
theorem of_enclosures {u : Nat → RealCompute} {x : RealCompute}
    (hx : x.Valid) (hu : ∀ n, (u n).Valid)
    (hb : ∀ n, InInterval (u n) (x.compute n)) : TendsTo u x := by
  refine ⟨hx,hu,fun m eps => ⟨m,fun n hn => ?_⟩⟩
  have nest := hx.2.1 m n hn
  have bound := hb n
  constructor
  · intro i j
    have h := bound.1 0 j
    change (x.compute n).lo ≤ ((u n).compute j).hi at h
    change (x.compute m).lo-eps.val ≤ ((u n).compute j).hi
    have := eps.property
    grind
  · intro i j
    have h := bound.2 i 0
    change ((u n).compute i).lo ≤ (x.compute n).hi at h
    change ((u n).compute i).lo ≤ (x.compute m).hi+eps.val
    have := eps.property
    grind

def allowance (n : Nat) : Rat := ((1:Rat)/2)^n

theorem allowance_pos (n : Nat) : 0 < allowance n :=
  Rat.pow_pos (by decide +kernel)

theorem allowance_antitone {n m : Nat} (h : n≤m) : allowance m≤allowance n := by
  obtain ⟨k,rfl⟩ := Nat.exists_eq_add_of_le h
  induction k with
  | zero => exact Rat.le_refl
  | succ k ih =>
    change ((1:Rat)/2)^(n+k+1) ≤ ((1:Rat)/2)^n
    rw [Rat.pow_succ]
    have hn : 0≤((1:Rat)/2)^(n+k) := Rat.pow_nonneg (by decide +kernel)
    have hm := Rat.mul_le_mul_of_nonneg_left (by decide +kernel : (1:Rat)/2≤1) hn
    exact Rat.le_trans (by simpa only [Rat.mul_one, allowance] using hm) (ih (by omega))

theorem allowance_shrinks (eps : QPos) : ∃ N, ∀ n, N≤n → allowance n≤eps.val := by
  refine ⟨RationalMajorant.halfDecayShift 1 eps,fun n hn => ?_⟩
  have h := RationalMajorant.halfDecayShift_spec_of_le (by decide +kernel : (0:Rat)≤1) eps hn
  simpa only [Rat.one_mul,allowance] using h

def enlarged (x : RealCompute) : RealCompute where
  compute n := QInterval.expand (x.compute n) (allowance n)

theorem enlarged_valid {x : RealCompute} (hx : x.Valid) : (enlarged x).Valid := by
  refine ⟨?_,?_,?_⟩
  · intro n
    have ho := hx.1 n
    have hp := allowance_pos n
    change 0≤(x.compute n).hi+allowance n-((x.compute n).lo-allowance n)
    grind only [QInterval.width]
  · intro n m hnm
    have hn := hx.2.1 n m hnm
    have hd := allowance_antitone hnm
    have hp := allowance_pos m
    change (x.compute n).lo-allowance n≤(x.compute m).lo-allowance m ∧
      (x.compute m).lo-allowance m≤(x.compute m).hi+allowance m ∧
      (x.compute m).hi+allowance m≤(x.compute n).hi+allowance n
    constructor
    · grind only
    constructor <;> grind only
  · intro eps
    let e : QPos := ⟨eps.val/4,by rw [Rat.div_def]; exact Rat.mul_pos eps.property (Rat.inv_pos.mpr (by decide +kernel))⟩
    obtain ⟨N,hN⟩ := hx.2.2 e
    obtain ⟨M,hM⟩ := allowance_shrinks e
    refine ⟨max N M,fun n hn => ?_⟩
    have h1 := hN n (Nat.le_trans (Nat.le_max_left N M) hn)
    have h2 := hM n (Nat.le_trans (Nat.le_max_right N M) hn)
    change (x.compute n).hi+allowance n-((x.compute n).lo-allowance n)≤eps.val
    dsimp [e] at h1 h2
    have := eps.property
    grind only [QInterval.width,Rat.div_def]

theorem enlarged_equiv {x : RealCompute} (hx : x.Valid) : (enlarged x).Equiv x := by
  intro n
  apply (RealCompute.compareAt_overlap_iff _ _ n n).2
  have h := hx.1 n
  have hp := allowance_pos n
  change (x.compute n).lo-allowance n≤(x.compute n).hi ∧
    (x.compute n).lo≤(x.compute n).hi+allowance n
  constructor <;> grind only [QInterval.width]


/-- Both refinement indices eventually pass every finite stage. Monotonicity
is optional: validity is required of the selected output intervals themselves. -/
def Cofinal (s : Nat → Nat) : Prop :=
  ∀ N, ∃ K, ∀ k, K ≤ k → N ≤ s k

def diagonal (Q : Nat → Nat → QInterval) (n m : Nat → Nat) : RealCompute where
  compute k := Q (n k) (m k)

/-- A selected valid diagonal must cover every observation at the selected
input resolution. `tests` describes whole neighborhoods or complete tails,
never just the one sample selected by the parametrization. -/
def HasEnclosureValue (tests : Nat → RealCompute → Prop) (c : RealCompute) : Prop :=
  c.Valid ∧ ∃ Q n m, Cofinal n ∧ Cofinal m ∧
    (diagonal Q n m).Valid ∧ (diagonal Q n m).Equiv c ∧
    ∀ k y, tests (n k) y → InInterval y ((diagonal Q n m).compute k)

theorem cofinal_id : Cofinal (fun k => k) := fun N => ⟨N, fun _ h => h⟩

theorem cofinal_of_ge (s : Nat → Nat) (h : ∀ k, k ≤ s k) : Cofinal s :=
  fun N => ⟨N, fun k hk => Nat.le_trans hk (h k)⟩

theorem inInterval_congr {y z : RealCompute} {I : QInterval}
    (hy : y.Valid) (hz : z.Valid) (h : y.Equiv z) (hb : InInterval y I) :
    InInterval z I :=
  ⟨RealCompute.le_trans hy hb.1 (RealCompute.le_of_equiv hy hz h),
   RealCompute.le_trans hy (RealCompute.le_of_equiv hz hy (RealCompute.equiv_symm h)) hb.2⟩

/-- Uniqueness compares two arbitrary covered diagonals using a common
observation at a finer input resolution. It constructs no canonical value. -/
theorem HasEnclosureValue.unique {tests : Nat → RealCompute → Prop} {c d : RealCompute}
    (antitone : ∀ i j, i ≤ j → ∀ y, tests j y → tests i y)
    (inhabited : ∀ i, ∃ y, y.Valid ∧ tests i y)
    (hc : HasEnclosureValue tests c) (hd : HasEnclosureValue tests d) : c.Equiv d := by
  obtain ⟨vc,Q,n,m,_,_,vC,eC,bC⟩ := hc
  obtain ⟨vd,R,p,q,_,_,vD,eD,bD⟩ := hd
  have eq : (diagonal Q n m).Equiv (diagonal R p q) := by
    intro k
    obtain ⟨y,vy,hy⟩ := inhabited (max (n k) (p k))
    have a := bC k y (antitone _ _ (Nat.le_max_left _ _) y hy)
    have b := bD k y (antitone _ _ (Nat.le_max_right _ _) y hy)
    apply (RealCompute.compareAt_overlap_iff _ _ k k).2
    exact ⟨RealCompute.le_trans vy a.1 b.2 0 0,
      RealCompute.le_trans vy b.1 a.2 0 0⟩
  exact RealCompute.equiv_trans vc vC vd (RealCompute.equiv_symm eC)
    (RealCompute.equiv_trans vC vD vd eq eD)

theorem HasEnclosureValue.congr_value {tests : Nat → RealCompute → Prop} {c d : RealCompute}
    (h : HasEnclosureValue tests c) (hd : d.Valid) (hcd : c.Equiv d) :
    HasEnclosureValue tests d := by
  obtain ⟨hc,Q,n,m,hn,hm,hC,hCc,hcover⟩ := h
  exact ⟨hd,Q,n,m,hn,hm,hC,RealCompute.equiv_trans hC hc hd hCc hcd,hcover⟩

/-- A sequence limit has a covered diagonal for the entire remaining tail. -/
def HasParametrizedLimit (u : Nat → RealCompute) (c : RealCompute) : Prop :=
  (∀ j, (u j).Valid) ∧ HasEnclosureValue (fun n y => ∃ j, n ≤ j ∧ y = u j) c

theorem parametrizedLimit_iff {u : Nat → RealCompute} {c : RealCompute} :
    HasParametrizedLimit u c ↔ TendsTo u c := by
  constructor
  · rintro ⟨hu,hc,Q,n,m,hn,hm,hC,hCc,cover⟩
    have h : TendsTo u (diagonal Q n m) := by
      refine ⟨hC,hu,fun k eps => ⟨n k,fun j hj => ?_⟩⟩
      have b := cover k (u j) ⟨j,hj,rfl⟩
      constructor
      · intro i t
        have h := b.1 i t
        have := eps.property
        change (Q (n k) (m k)).lo-eps.val ≤ ((u j).compute t).hi
        change (Q (n k) (m k)).lo ≤ ((u j).compute t).hi at h
        grind only
      · intro i t
        have h := b.2 i t
        have := eps.property
        change ((u j).compute i).lo ≤ (Q (n k) (m k)).hi+eps.val
        change ((u j).compute i).lo ≤ (Q (n k) (m k)).hi at h
        grind only
    exact congr_target h hc hCc
  · intro h
    classical
    let threshold : Nat → Nat := fun k =>
      Classical.choose (h.2.2 k ⟨allowance k,allowance_pos k⟩)
    let n : Nat → Nat := fun k => max k (threshold k)
    refine ⟨h.2.1,h.1,(fun _ k => (enlarged c).compute k),n,(fun k => k),
      cofinal_of_ge n (fun k => Nat.le_max_left _ _),cofinal_id,
      enlarged_valid h.1,enlarged_equiv h.1,?_⟩
    intro k y hy
    obtain ⟨j,hj,rfl⟩ := hy
    exact Classical.choose_spec (h.2.2 k ⟨allowance k,allowance_pos k⟩) j
      (Nat.le_trans (Nat.le_max_right _ _) hj)

theorem HasParametrizedLimit.unique {u : Nat → RealCompute} {c d : RealCompute}
    (hc : HasParametrizedLimit u c) (hd : HasParametrizedLimit u d) : c.Equiv d :=
  RawLimit.unique (parametrizedLimit_iff.mp hc) (parametrizedLimit_iff.mp hd)

/-- Regression against a diagonal that skips every unfavorable sample.
The alternating sequence has valid constant subsequences, but no covered
parametrized limit, for any valid represented target. -/
theorem alternating_no_parametrizedLimit (c : RealCompute) :
    ¬ HasParametrizedLimit (fun j => RealCompute.ofRat (if j % 2 = 0 then 0 else 1)) c := by
  rintro ⟨hu,hc,Q,n,m,hn,hm,hC,hCc,cover⟩
  obtain ⟨K,hK⟩ := hC.2.2 ⟨1/2,by decide +kernel⟩
  have hw := hK K (Nat.le_refl _)
  have he : (2*n K) % 2 = 0 := by omega
  have ho : (2*n K+1) % 2 ≠ 0 := by omega
  have b0 := cover K _ ⟨2*n K,by omega,rfl⟩
  have b1 := cover K _ ⟨2*n K+1,by omega,rfl⟩
  simp only [he,ho,if_pos] at b0 b1
  have lo := b0.1 0 0
  have hi := b1.2 0 0
  change (Q (n K) (m K)).lo ≤ 0 at lo
  change 1 ≤ (Q (n K) (m K)).hi at hi
  change (Q (n K) (m K)).hi-(Q (n K) (m K)).lo ≤ 1/2 at hw
  grind only [Rat.div_def]

theorem inInterval_of_contains_compute {y : RealCompute} {I : QInterval}
    (hy : y.Valid) (k : Nat) (h : I.ContainsInterval (y.compute k)) : InInterval y I := by
  constructor
  · intro i j
    have b := RealCompute.le_refl y hy k j
    change I.lo ≤ (y.compute j).hi
    exact Rat.le_trans h.1 b
  · intro i j
    have b := RealCompute.le_refl y hy i k
    change (y.compute i).lo ≤ I.hi
    exact Rat.le_trans b h.2

theorem inInterval_of_sub_bound {y c : RealCompute} (hy : y.Valid) (hc : c.Valid)
    (eps : Rat) (lower : (RealCompute.ofRat (-eps)).Le (RealCompute.sub y c))
    (upper : (RealCompute.sub y c).Le (RealCompute.ofRat eps)) (k : Nat) :
    InInterval y (QInterval.expand (c.compute k) eps) := by
  have cancel := RealCompute.sub_add_cancel_equiv hy hc
  have vz := RealCompute.add_valid (RealCompute.sub_valid hy hc) hc
  have lo := RealCompute.le_add_le_add lower (RealCompute.le_refl c hc)
  have hi := RealCompute.le_add_le_add upper (RealCompute.le_refl c hc)
  have lo' := RealCompute.le_trans vz lo (RealCompute.le_of_equiv vz hy cancel)
  have hi' := RealCompute.le_trans vz (RealCompute.le_of_equiv hy vz (RealCompute.equiv_symm cancel)) hi
  constructor
  · intro i j
    have h := lo' k j
    change (c.compute k).lo-eps ≤ (y.compute j).hi
    change -eps+(c.compute k).lo ≤ (y.compute j).hi at h
    grind only
  · intro i j
    have h := hi' i k
    change (y.compute i).lo ≤ (c.compute k).hi+eps
    change (y.compute i).lo ≤ eps+(c.compute k).hi at h
    grind only

theorem inInterval_intersection {y : RealCompute} {I J : QInterval}
    (hI : InInterval y I) (hJ : InInterval y J) :
    InInterval y (QInterval.intersection I J) := by
  constructor
  · intro i j
    have a := hI.1 i j
    have b := hJ.1 i j
    change max I.lo J.lo ≤ (y.compute j).hi
    change I.lo ≤ (y.compute j).hi at a
    change J.lo ≤ (y.compute j).hi at b
    grind
  · intro i j
    have a := hI.2 i j
    have b := hJ.2 i j
    change (y.compute i).lo ≤ min I.hi J.hi
    change (y.compute i).lo ≤ I.hi at a
    change (y.compute i).lo ≤ J.hi at b
    grind

/-- Finite intersections enforce output nesting without assuming an anchor
value or a pre-existing extension at an irrational input. -/
def prefixCompute (B : Nat → QInterval) : Nat → QInterval
  | 0 => B 0
  | k+1 => QInterval.intersection (prefixCompute B k) (B (k+1))

def prefixRaw (B : Nat → QInterval) : RealCompute where
  compute := prefixCompute B

def runningMax (s : Nat → Nat) : Nat → Nat
  | 0 => s 0
  | k+1 => max (runningMax s k) (s (k+1))

theorem runningMax_ge (s : Nat → Nat) (k : Nat) : s k ≤ runningMax s k := by
  cases k with
  | zero => exact Nat.le_refl _
  | succ k => exact Nat.le_max_right _ _

theorem prefix_cover {tests : Nat → RealCompute → Prop} {s : Nat → Nat} {B : Nat → QInterval}
    (anti : ∀ i j, i ≤ j → ∀ y, tests j y → tests i y)
    (cover : ∀ k y, tests (s k) y → InInterval y (B k)) :
    ∀ k y, tests (runningMax s k) y → InInterval y ((prefixRaw B).compute k) := by
  intro k
  induction k with
  | zero => exact cover 0
  | succ k ih =>
    intro y hy
    exact inInterval_intersection
      (ih y (anti _ _ (Nat.le_max_left _ _) y hy))
      (cover (k+1) y (anti _ _ (Nat.le_max_right _ _) y hy))

theorem prefix_current (B : Nat → QInterval) (k : Nat) :
    (B k).ContainsInterval ((prefixRaw B).compute k) := by
  cases k with
  | zero => exact ⟨Rat.le_refl,Rat.le_refl⟩
  | succ k => exact QInterval.intersection_contained_right _ _

theorem prefix_valid {tests : Nat → RealCompute → Prop} {s : Nat → Nat} {B : Nat → QInterval}
    (anti : ∀ i j, i ≤ j → ∀ y, tests j y → tests i y)
    (inhabited : ∀ i, ∃ y, y.Valid ∧ tests i y)
    (cover : ∀ k y, tests (s k) y → InInterval y (B k))
    (shrinks : RealCompute.WidthsShrinkToZero B) : (prefixRaw B).Valid := by
  have ordered : ∀ k, ((prefixRaw B).compute k).lo ≤ ((prefixRaw B).compute k).hi := by
    intro k
    obtain ⟨y,vy,hy⟩ := inhabited (runningMax s k)
    have h := prefix_cover anti cover k y hy
    exact RealCompute.le_trans vy h.1 h.2 0 0
  refine ⟨fun k => ?_,?_,?_⟩
  · have h := ordered k
    change 0 ≤ ((prefixRaw B).compute k).hi-((prefixRaw B).compute k).lo
    grind only
  · intro k l hkl
    induction hkl with
    | refl => exact ⟨Rat.le_refl,ordered k,Rat.le_refl⟩
    | @step l hkl ih =>
      have h := QInterval.intersection_contained_left (prefixCompute B l) (B (l+1))
      exact ⟨Rat.le_trans ih.1 h.1,ordered _,Rat.le_trans h.2 ih.2.2⟩
  · intro eps
    obtain ⟨N,hN⟩ := shrinks eps
    exact ⟨N,fun k hk => Rat.le_trans (QInterval.width_le_of_contains (prefix_current B k)) (hN k hk)⟩

/-- This constructor performs only finite rational intersections. The
inhabited shrinking observations prove validity, rather than assuming it. -/
theorem prefix_hasEnclosureValue {tests : Nat → RealCompute → Prop} {s : Nat → Nat}
    {B : Nat → QInterval}
    (anti : ∀ i j, i ≤ j → ∀ y, tests j y → tests i y)
    (inhabited : ∀ i, ∃ y, y.Valid ∧ tests i y)
    (hs : ∀ k, k ≤ s k)
    (cover : ∀ k y, tests (s k) y → InInterval y (B k))
    (shrinks : RealCompute.WidthsShrinkToZero B) :
    HasEnclosureValue tests (prefixRaw B) := by
  have hv := prefix_valid anti inhabited cover shrinks
  exact ⟨hv,(fun _ m => (prefixRaw B).compute m),runningMax s,(fun k => k),
    cofinal_of_ge _ (fun k => Nat.le_trans (hs k) (runningMax_ge s k)),cofinal_id,
    hv,RealCompute.equiv_refl _ hv,prefix_cover anti cover⟩

/-- Neighborhood convergence is a useful compatibility presentation of the
covered-diagonal definition, without any requested precision schedule. -/
def NeighborhoodTendsTo (tests : Nat → RealCompute → Prop) (c : RealCompute) : Prop :=
  c.Valid ∧ ∀ k (eps : QPos), ∃ N, ∀ y, tests N y →
    InInterval y (QInterval.expand (c.compute k) eps.val)

theorem enclosureValue_iff {tests : Nat → RealCompute → Prop} {c : RealCompute}
    (anti : ∀ i j, i ≤ j → ∀ y, tests j y → tests i y) :
    HasEnclosureValue tests c ↔ NeighborhoodTendsTo tests c := by
  constructor
  · rintro ⟨hc,Q,n,m,hn,hm,hC,hCc,cover⟩
    refine ⟨hc,fun k eps => ?_⟩
    obtain ⟨i,hi⟩ := hC.2.2 eps
    have width := hi i (Nat.le_refl _)
    have ov := (RealCompute.compareAt_overlap_iff _ _ i k).mp
      (RealCompute.allStagesOverlap_of_equiv hC hc hCc i k)
    refine ⟨n i,fun y hy => ?_⟩
    have b := cover i y hy
    constructor
    · intro a t
      have h := b.1 a t
      change (c.compute k).lo-eps.val ≤ (y.compute t).hi
      change (Q (n i) (m i)).lo ≤ (y.compute t).hi at h
      change (Q (n i) (m i)).hi-(Q (n i) (m i)).lo ≤ eps.val at width
      unfold QInterval.Overlaps at ov
      change (Q (n i) (m i)).lo ≤ (c.compute k).hi ∧
        (c.compute k).lo ≤ (Q (n i) (m i)).hi at ov
      grind only
    · intro a t
      have h := b.2 a t
      change (y.compute a).lo ≤ (c.compute k).hi+eps.val
      change (y.compute a).lo ≤ (Q (n i) (m i)).hi at h
      change (Q (n i) (m i)).hi-(Q (n i) (m i)).lo ≤ eps.val at width
      unfold QInterval.Overlaps at ov
      change (Q (n i) (m i)).lo ≤ (c.compute k).hi ∧
        (c.compute k).lo ≤ (Q (n i) (m i)).hi at ov
      grind only
  · intro h
    classical
    let s := fun k => Classical.choose (h.2 k ⟨allowance k,allowance_pos k⟩)
    let n := fun k => max k (s k)
    refine ⟨h.1,(fun _ m => (enlarged c).compute m),n,(fun k => k),
      cofinal_of_ge n (fun k => Nat.le_max_left _ _),cofinal_id,
      enlarged_valid h.1,enlarged_equiv h.1,?_⟩
    intro k y hy
    exact Classical.choose_spec (h.2 k ⟨allowance k,allowance_pos k⟩) y
      (anti _ _ (Nat.le_max_right _ _) y hy)

end RawLimit
end ComputableAnalysis

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