Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · StrictMonotoneInverse · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_StrictMonotoneInverse

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Calculus
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Numbers

set_option autoImplicit true

/-!
# Constructive inversion from strict increase

The primary function is sampled on rationals. Continuity means that a supplied
interval extension sends every valid input name to a valid output name. Its
coverage law connects that extension to the primary samples; no uniform
continuity modulus or inverse-separation schedule is requested.

Two interior rational points avoid deciding equality with the target. Strict
increase proves that a decidable separation search terminates. The resulting
nested intervals construct the preimage, including for irrational targets.
-/
namespace ComputableAnalysis.StrictMonotoneInverse

def Source (F : FunctionOnInterval) (x : RealCompute) : Prop :=
  ∀ n, subintervalOf (x.compute n) F.lower F.upper

def sample (F : FunctionOnInterval) (q : Rat)
    (hq : inDomainInterval F.lower F.upper q) : RealCompute where
  compute := F.compute q hq

theorem sample_valid (F : FunctionOnInterval) (q : Rat)
    (hq : inDomainInterval F.lower F.upper q) : (sample F q hq).Valid :=
  F.valid_on q (F.defined_on q hq)

/-- Strict order of the rational samples, as an exact represented inequality.
The witness is only a proof of eventual separation, not a supplied schedule. -/
def StrictlyIncreasing (F : FunctionOnInterval) : Prop :=
  ∀ (p q : Rat) (hp : inDomainInterval F.lower F.upper p)
    (hq : inDomainInterval F.lower F.upper q), p < q →
    ∃ n, (F.compute p hp n).hi < (F.compute q hq n).lo

/-- An interval extension with justified rational coverage. The stage is
implementation data explaining which input enclosure an output encloses. -/
structure Extension (F : FunctionOnInterval) where
  eval : (x : RealCompute) → x.Valid → Source F x → RealCompute
  stage : (x : RealCompute) → x.Valid → Source F x → Nat → Nat
  encloses : ∀ x hx hs n q hq,
    (x.compute (stage x hx hs n)).lo ≤ q →
    q ≤ (x.compute (stage x hx hs n)).hi →
    ((eval x hx hs).compute n).ContainsInterval (F.compute q hq n)

/-- The validity-based continuity requirement, without a chosen modulus. -/
def Extension.Continuous {F : FunctionOnInterval} (E : Extension F) : Prop :=
  ∀ x hx hs, (E.eval x hx hs).Valid

/-- Membership of the source interval is a value-level condition; early name
intervals need not already lie in the source interval. -/
def InSource (F : FunctionOnInterval) (x : RealCompute) : Prop :=
  (RealCompute.ofRat F.lower).Le x ∧ x.Le (RealCompute.ofRat F.upper)

private def ratMax (a b : Rat) : Rat := if a ≤ b then b else a
private def ratMin (a b : Rat) : Rat := if a ≤ b then a else b

/-- Repair a supplied name to the closed source interval, including endpoints. -/
def clip (F : FunctionOnInterval) (x : RealCompute) : RealCompute where
  compute n := ⟨ratMax F.lower (x.compute n).lo,ratMin F.upper (x.compute n).hi⟩

theorem clip_source {F : FunctionOnInterval} (hab : F.lower ≤ F.upper)
    (x : RealCompute) (hx : x.Valid) (hs : InSource F x) : Source F (clip F x) := by
  intro n
  have hlo := hs.1 0 n
  have hhi := hs.2 n 0
  have ho := RealCompute.interval_order_of_valid x hx n
  change F.lower ≤ (x.compute n).hi at hlo
  change (x.compute n).lo ≤ F.upper at hhi
  dsimp [clip,subintervalOf,ratMax,ratMin]
  split <;> split <;> grind

theorem clip_valid {F : FunctionOnInterval} (hab : F.lower ≤ F.upper)
    (x : RealCompute) (hx : x.Valid) (hs : InSource F x) : (clip F x).Valid := by
  refine ⟨?_,?_,?_⟩
  · intro n
    have ho := (clip_source hab x hx hs n).2.1
    dsimp [QInterval.width]; grind
  · intro n m hnm
    have hm := clip_source hab x hx hs m
    have hnest := hx.2.1 n m hnm
    refine ⟨?_,hm.2.1,?_⟩
    · dsimp [clip,ratMax]
      split <;> split <;> grind
    · dsimp [clip,ratMin]
      split <;> split <;> grind
  · intro eps
    obtain ⟨N,hN⟩ := hx.2.2 eps
    refine ⟨N,?_⟩
    intro n hn
    have hw := hN n hn
    dsimp [clip,QInterval.width,ratMax,ratMin]
    split <;> split <;> dsimp [QInterval.width] at hw <;> grind

theorem clip_equiv {F : FunctionOnInterval} (_hab : F.lower ≤ F.upper)
    (x : RealCompute) (hx : x.Valid) (hs : InSource F x) : (clip F x).Equiv x := by
  apply RealCompute.sameStageOverlap_equiv
  intro n
  apply (RealCompute.compareAt_overlap_iff _ _ n n).mpr
  have hlo := hs.1 0 n
  have hhi := hs.2 n 0
  have ho := RealCompute.interval_order_of_valid x hx n
  change F.lower ≤ (x.compute n).hi at hlo
  change (x.compute n).lo ≤ F.upper at hhi
  dsimp [clip,QInterval.Overlaps,ratMax,ratMin]
  split <;> split <;> grind

/-- Evaluation on the full mathematical source interval. Clipping is internal. -/
def Extension.evalOn {F : FunctionOnInterval} (E : Extension F)
    (hab : F.lower ≤ F.upper) (x : RealCompute) (hx : x.Valid) (hs : InSource F x) : RealCompute :=
  E.eval (clip F x) (clip_valid hab x hx hs) (clip_source hab x hx hs)

theorem sample_mono {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    {p q : Rat} (hp : inDomainInterval F.lower F.upper p)
    (hq : inDomainInterval F.lower F.upper q) (hpq : p ≤ q) :
    (sample F p hp).Le (sample F q hq) := by
  by_cases heq : p = q
  · subst q
    exact RealCompute.le_refl (sample F p hp) (sample_valid F p hp)
  · have hlt : p < q := by grind
    obtain ⟨k, hk⟩ := hstrict p q hp hq hlt
    intro n m
    have ha := RealCompute.le_refl (sample F p hp) (sample_valid F p hp) n k
    have hb := RealCompute.le_refl (sample F q hq) (sample_valid F q hq) k m
    change (F.compute p hp n).lo ≤ (F.compute q hq m).hi
    change (F.compute p hp n).lo ≤ (F.compute p hp k).hi at ha
    change (F.compute q hq k).lo ≤ (F.compute q hq m).hi at hb
    grind

private def next (p : Nat → Prop) (m n : Nat) : Prop := m = n+1 ∧ ¬ p n

private theorem accessible (p : Nat → Prop) (d n : Nat)
    (h : p (n+d)) : Acc (next p) n := by
  induction d generalizing n with
  | zero =>
    apply Acc.intro
    intro m hm
    exact False.elim (hm.2 (by simpa using h))
  | succ d ih =>
    apply Acc.intro
    intro m hm
    rcases hm with ⟨rfl, _⟩
    apply ih
    simpa [Nat.add_assoc, Nat.add_comm, Nat.add_left_comm] using h

private def searchFrom (p : Nat → Prop) [DecidablePred p]
    (n : Nat) (h : Acc (next p) n) : {k // p k} :=
  Acc.rec (motive := fun _ _ => {k // p k})
    (fun n _ recurse => if hn : p n then ⟨n,hn⟩ else recurse (n+1) ⟨rfl,hn⟩) h

private theorem searchAccessible (p : Nat → Prop) (h : ∃ n, p n) : Acc (next p) 0 := by
  rcases h with ⟨n,hn⟩
  exact accessible p n 0 (by simpa using hn)

/-- Executable search: the existential proof justifies termination and is
erased. No arbitrary witness is extracted from that proof. -/
private def search (p : Nat → Prop) [DecidablePred p]
    (h : ∃ n,p n) : {n // p n} := searchFrom p 0 (searchAccessible p h)

structure Bracket (F : FunctionOnInterval) (y : RealCompute) where
  interval : QInterval
  inside : subintervalOf interval F.lower F.upper
  lower_le : (sample F interval.lo ⟨inside.1, by grind [inside.2.1, inside.2.2]⟩).Le y
  le_upper : y.Le (sample F interval.hi ⟨by grind [inside.1, inside.2.1], inside.2.2⟩)

private def leftThird (I : QInterval) : Rat := (2*I.lo+I.hi)/3
private def rightThird (I : QInterval) : Rat := (I.lo+2*I.hi)/3

private theorem thirds {I : QInterval} (h : I.lo < I.hi) :
    I.lo ≤ leftThird I ∧ leftThird I < rightThird I ∧ rightThird I ≤ I.hi := by
  dsimp [leftThird,rightThird]
  grind

private theorem separated_decision {F : FunctionOnInterval}
    (hstrict : StrictlyIncreasing F) (y : RealCompute) (hy : y.Valid)
    (l r : Rat) (hl : inDomainInterval F.lower F.upper l)
    (hr : inDomainInterval F.lower F.upper r) (hlr : l < r) :
    ∃ k, (F.compute l hl k).hi < (y.compute k).lo ∨
      (y.compute k).hi < (F.compute r hr k).lo := by
  obtain ⟨j,hj⟩ := hstrict l r hl hr hlr
  let eps : QPos := ⟨((F.compute r hr j).lo-(F.compute l hl j).hi)/2, by grind⟩
  obtain ⟨N,hN⟩ := hy.2.2 eps
  let k := max N j
  have hw := hN k (Nat.le_max_left _ _)
  have hleft := (sample_valid F l hl).2.1 j k (Nat.le_max_right _ _)
  have hright := (sample_valid F r hr).2.1 j k (Nat.le_max_right _ _)
  refine ⟨k, ?_⟩
  dsimp [sample] at hleft hright
  dsimp [eps, QInterval.width] at hw
  grind

private theorem strict_separation_le {x y : RealCompute} (hx : x.Valid) (hy : y.Valid)
    {k : Nat} (h : (x.compute k).hi < (y.compute k).lo) : x.Le y := by
  intro n m
  have ha := RealCompute.le_refl x hx n k
  have hb := RealCompute.le_refl y hy k m
  grind

def step {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    (y : RealCompute) (hy : y.Valid) (B : Bracket F y) : Bracket F y := by
  by_cases hpos : B.interval.lo < B.interval.hi
  · let l := leftThird B.interval
    let r := rightThird B.interval
    have ht := thirds hpos
    have hb := B.inside
    dsimp [subintervalOf] at hb
    have hl : inDomainInterval F.lower F.upper l := by
      dsimp [inDomainInterval]
      exact ⟨by grind, by grind⟩
    have hr : inDomainInterval F.lower F.upper r := by
      dsimp [inDomainInterval]
      exact ⟨by grind, by grind⟩
    let k := search (fun k => (F.compute l hl k).hi < (y.compute k).lo ∨
      (y.compute k).hi < (F.compute r hr k).lo)
      (separated_decision hstrict y hy l r hl hr ht.2.1)
    if hleft : (F.compute l hl k.val).hi < (y.compute k.val).lo then
      exact {
        interval := ⟨l,B.interval.hi⟩
        inside := ⟨hl.1, by grind, B.inside.2.2⟩
        lower_le := strict_separation_le (sample_valid F l hl) hy hleft
        le_upper := B.le_upper }
    else
      exact {
        interval := ⟨B.interval.lo,r⟩
        inside := ⟨B.inside.1, by grind, hr.2⟩
        lower_le := B.lower_le
        le_upper := strict_separation_le hy (sample_valid F r hr)
          (k.property.resolve_left hleft) }
  · exact B

theorem step_bounds {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    (y : RealCompute) (hy : y.Valid) (B : Bracket F y) :
    B.interval.lo ≤ (step hstrict y hy B).interval.lo ∧
    (step hstrict y hy B).interval.hi ≤ B.interval.hi ∧
    3*(step hstrict y hy B).interval.width ≤ 2*B.interval.width := by
  unfold step
  split
  · dsimp only
    split
    · dsimp [leftThird,QInterval.width]
      grind
    · dsimp [rightThird,QInterval.width]
      grind
  · have ho := B.inside.2.1
    dsimp [QInterval.width]
    grind

def initial {F : FunctionOnInterval} (hab : F.lower ≤ F.upper)
    (y : RealCompute)
    (ha : (sample F F.lower ⟨Rat.le_refl,hab⟩).Le y)
    (hb : y.Le (sample F F.upper ⟨hab,Rat.le_refl⟩)) : Bracket F y where
  interval := ⟨F.lower,F.upper⟩
  inside := ⟨Rat.le_refl,hab,Rat.le_refl⟩
  lower_le := ha
  le_upper := hb

def iterate {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    (y : RealCompute) (hy : y.Valid) (B : Bracket F y) : Nat → Bracket F y
  | 0 => B
  | n+1 => step hstrict y hy (iterate hstrict y hy B n)

theorem iterate_nested {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    (y : RealCompute) (hy : y.Valid) (B : Bracket F y) (n m : Nat) (hnm : n ≤ m) :
    (iterate hstrict y hy B n).interval.lo ≤ (iterate hstrict y hy B m).interval.lo ∧
    (iterate hstrict y hy B m).interval.hi ≤ (iterate hstrict y hy B n).interval.hi := by
  induction m with
  | zero =>
    have : n=0 := by omega
    subst n
    exact ⟨Rat.le_refl,Rat.le_refl⟩
  | succ m ih =>
    by_cases h : n ≤ m
    · have hi := ih h
      have hs := step_bounds hstrict y hy (iterate hstrict y hy B m)
      exact ⟨Rat.le_trans hi.1 hs.1,Rat.le_trans hs.2.1 hi.2⟩
    · have : n=m+1 := by omega
      subst n
      exact ⟨Rat.le_refl,Rat.le_refl⟩

theorem iterate_weighted_width {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    (y : RealCompute) (hy : y.Valid) (B : Bracket F y) (n : Nat) :
    ((n:Rat)+2)*(iterate hstrict y hy B n).interval.width ≤ 2*B.interval.width := by
  induction n with
  | zero => change ((0:Rat)+2)*B.interval.width ≤ 2*B.interval.width; grind
  | succ n ih =>
    have hs := (step_bounds hstrict y hy (iterate hstrict y hy B n)).2.2
    have ho := (iterate hstrict y hy B n).inside.2.1
    have hw : 0 ≤ (iterate hstrict y hy B n).interval.width := by
      dsimp [QInterval.width]; grind
    have hn : (0:Rat) ≤ n := Rat.natCast_nonneg
    have hm := Rat.mul_le_mul_of_nonneg_left hs (by grind : (0:Rat) ≤ (n:Rat)+3)
    have hp := Rat.mul_nonneg hn hw
    simp only [Rat.natCast_add]
    change (((n:Rat)+1)+2)*(step hstrict y hy (iterate hstrict y hy B n)).interval.width ≤ _
    grind

private theorem div_bound {u v d : Rat} (hd : 0 < d) (h : d*u ≤ v) : u ≤ v/d := by
  have hc := Rat.inv_mul_cancel d (by grind : d≠0)
  have hm := Rat.mul_le_mul_of_nonneg_left h (Rat.le_of_lt (Rat.inv_pos.mpr hd))
  calc
    u = d⁻¹*(d*u) := by rw [← Rat.mul_assoc, hc, Rat.one_mul]
    _ ≤ d⁻¹*v := hm
    _ = v/d := by rw [Rat.div_def, Rat.mul_comm]

theorem iterate_valid {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    (y : RealCompute) (hy : y.Valid) (B : Bracket F y) :
    RealCompute.ValidCompute (fun n => (iterate hstrict y hy B n).interval) := by
  refine ⟨?_,?_,?_⟩
  · intro n
    have ho := (iterate hstrict y hy B n).inside.2.1
    dsimp [QInterval.width]; grind
  · intro n m hnm
    have hn := iterate_nested hstrict y hy B n m hnm
    exact ⟨hn.1,(iterate hstrict y hy B m).inside.2.1,hn.2⟩
  · apply shrinksToZero_of_ratOverSuccBound (C := 2*B.interval.width)
    intro n
    have hw := iterate_weighted_width hstrict y hy B n
    have ho := (iterate hstrict y hy B n).inside.2.1
    have hn : (0:Rat) < ((n+1:Nat):Rat) := Rat.natCast_pos.mpr (by omega)
    apply div_bound hn
    simp only [Rat.natCast_add]
    dsimp [QInterval.width] at *
    grind

/-- Interval coverage and rational order imply order of the derived evaluations,
even for different implementations of the extension. -/
theorem Extension.eval_mono {F : FunctionOnInterval} (E G : Extension F)
    (hstrict : StrictlyIncreasing F) (x z : RealCompute) (hx : x.Valid) (hz : z.Valid)
    (hsx : Source F x) (hsz : Source F z) (h : x.Le z) :
    (E.eval x hx hsx).Le (G.eval z hz hsz) := by
  intro n m
  let i := E.stage x hx hsx n
  let j := G.stage z hz hsz m
  let a := (x.compute i).lo
  let b := (z.compute j).hi
  have hxi := hsx i
  have hzj := hsz j
  have ha : inDomainInterval F.lower F.upper a :=
    ⟨hxi.1,Rat.le_trans hxi.2.1 hxi.2.2⟩
  have hb : inDomainInterval F.lower F.upper b :=
    ⟨Rat.le_trans hzj.1 hzj.2.1,hzj.2.2⟩
  have he := E.encloses x hx hsx n a ha Rat.le_refl hxi.2.1
  have hg := G.encloses z hz hsz m b hb hzj.2.1 Rat.le_refl
  have hm := sample_mono hstrict ha hb (h i j) n m
  exact Rat.le_trans he.1 (Rat.le_trans hm hg.2)

/-- Equivalent names, and alternate covered extensions, give the same value. -/
theorem Extension.eval_equiv {F : FunctionOnInterval} (E G : Extension F)
    (hstrict : StrictlyIncreasing F) (x z : RealCompute) (hx : x.Valid) (hz : z.Valid)
    (hsx : Source F x) (hsz : Source F z) (h : x.Equiv z) :
    (E.eval x hx hsx).Equiv (G.eval z hz hsz) := by
  apply RealCompute.le_antisymm
  · exact E.eval_mono G hstrict x z hx hz hsx hsz (RealCompute.le_of_equiv hx hz h)
  · exact G.eval_mono E hstrict z x hz hx hsz hsx
      (RealCompute.le_of_equiv hz hx (RealCompute.equiv_symm h))

private theorem Extension.eval_le_sample {F : FunctionOnInterval} (E : Extension F)
    (hstrict : StrictlyIncreasing F) (x : RealCompute) (hx : x.Valid) (hs : Source F x)
    (q : Rat) (hq : inDomainInterval F.lower F.upper q)
    (hbound : ∀ k, (x.compute k).lo ≤ q) :
    (E.eval x hx hs).Le (sample F q hq) := by
  intro n m
  let i := E.stage x hx hs n
  have hi := hs i
  have ha : inDomainInterval F.lower F.upper (x.compute i).lo :=
    ⟨hi.1,Rat.le_trans hi.2.1 hi.2.2⟩
  have he := E.encloses x hx hs n _ ha Rat.le_refl hi.2.1
  exact Rat.le_trans he.1 (sample_mono hstrict ha hq (hbound i) n m)

private theorem Extension.sample_le_eval {F : FunctionOnInterval} (E : Extension F)
    (hstrict : StrictlyIncreasing F) (x : RealCompute) (hx : x.Valid) (hs : Source F x)
    (q : Rat) (hq : inDomainInterval F.lower F.upper q)
    (hbound : ∀ k, q ≤ (x.compute k).hi) :
    (sample F q hq).Le (E.eval x hx hs) := by
  intro n m
  let i := E.stage x hx hs m
  have hi := hs i
  have hb : inDomainInterval F.lower F.upper (x.compute i).hi :=
    ⟨Rat.le_trans hi.1 hi.2.1,hi.2.2⟩
  have he := E.encloses x hx hs m _ hb hi.2.1 Rat.le_refl
  exact Rat.le_trans (sample_mono hstrict hq hb (hbound i) n m) he.2

/-- Strict increase survives passage from rational samples to valid inputs.
Equality of evaluated values therefore determines a unique source value. -/
theorem Extension.injective {F : FunctionOnInterval} (E : Extension F)
    (hcontinuous : E.Continuous) (hstrict : StrictlyIncreasing F)
    (x z : RealCompute) (hx : x.Valid) (hz : z.Valid)
    (hsx : Source F x) (hsz : Source F z)
    (heq : (E.eval x hx hsx).Equiv (E.eval z hz hsz)) : x.Equiv z := by
  have direction : ∀ (u v : RealCompute) (hu : u.Valid) (hv : v.Valid)
      (hsu : Source F u) (hsv : Source F v),
      (E.eval u hu hsu).Le (E.eval v hv hsv) → u.Le v := by
    intro u v hu hv hsu hsv huv n m
    by_cases hnot : (u.compute n).lo ≤ (v.compute m).hi
    · exact hnot
    exfalso
    have hlt : (v.compute m).hi < (u.compute n).lo := by grind
    have hn := hsu n
    have hm := hsv m
    have hp : inDomainInterval F.lower F.upper (v.compute m).hi :=
      ⟨Rat.le_trans hm.1 hm.2.1,hm.2.2⟩
    have hq : inDomainInterval F.lower F.upper (u.compute n).lo :=
      ⟨hn.1,Rat.le_trans hn.2.1 hn.2.2⟩
    have hqle := E.sample_le_eval hstrict u hu hsu _ hq
      (fun k => RealCompute.le_refl u hu n k)
    have hple := E.eval_le_sample hstrict v hv hsv _ hp
      (fun k => RealCompute.le_refl v hv k m)
    have hreverse := RealCompute.le_trans (hcontinuous v hv hsv)
      (RealCompute.le_trans (hcontinuous u hu hsu) hqle huv) hple
    obtain ⟨k,hk⟩ := hstrict _ _ hp hq hlt
    have hcontra := hreverse k k
    change (F.compute _ hq k).lo ≤ (F.compute _ hp k).hi at hcontra
    grind
  exact RealCompute.le_antisymm
    (direction x z hx hz hsx hsz
      (RealCompute.le_of_equiv (hcontinuous x hx hsx) (hcontinuous z hz hsz) heq))
    (direction z x hz hx hsz hsx
      (RealCompute.le_of_equiv (hcontinuous z hz hsz) (hcontinuous x hx hsx)
        (RealCompute.equiv_symm heq)))

def InRange (F : FunctionOnInterval) (hab : F.lower ≤ F.upper) (y : RealCompute) : Prop :=
  (sample F F.lower ⟨Rat.le_refl,hab⟩).Le y ∧
    y.Le (sample F F.upper ⟨hab,Rat.le_refl⟩)

/-- The preimage algorithm. It needs strict rational order and endpoint range;
continuity is used separately to identify its forward value. -/
def inverse {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (y : RealCompute) (hy : y.Valid) (hr : InRange F hab y) :
    RealCompute where
  compute := fun n => (iterate hstrict y hy (initial hab y hr.1 hr.2) n).interval

theorem inverse_valid {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (y : RealCompute) (hy : y.Valid) (hr : InRange F hab y) :
    (inverse hstrict hab y hy hr).Valid :=
  iterate_valid hstrict y hy (initial hab y hr.1 hr.2)

theorem inverse_source {F : FunctionOnInterval} (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (y : RealCompute) (hy : y.Valid) (hr : InRange F hab y) :
    Source F (inverse hstrict hab y hy hr) :=
  fun n => (iterate hstrict y hy (initial hab y hr.1 hr.2) n).inside

/-- Exact constructive intermediate value theorem, for every valid represented
target in the endpoint range. The constructed name is the witness. -/
theorem inverse_target {F : FunctionOnInterval} (E : Extension F)
    (hcontinuous : E.Continuous) (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (y : RealCompute) (hy : y.Valid) (hr : InRange F hab y) :
    (E.eval (inverse hstrict hab y hy hr)
      (inverse_valid hstrict hab y hy hr)
      (inverse_source hstrict hab y hy hr)).Equiv y := by
  let x := inverse hstrict hab y hy hr
  let hx := inverse_valid hstrict hab y hy hr
  let hs := inverse_source hstrict hab y hy hr
  have hov : ∀ n, ((E.eval x hx hs).compute n).Overlaps (y.compute n) := by
    intro n
    let k := E.stage x hx hs n
    let B := iterate hstrict y hy (initial hab y hr.1 hr.2) k
    have hlo := E.encloses x hx hs n B.interval.lo
      ⟨B.inside.1,Rat.le_trans B.inside.2.1 B.inside.2.2⟩ Rat.le_refl B.inside.2.1
    have hhi := E.encloses x hx hs n B.interval.hi
      ⟨Rat.le_trans B.inside.1 B.inside.2.1,B.inside.2.2⟩ B.inside.2.1 Rat.le_refl
    exact ⟨Rat.le_trans hlo.1 (B.lower_le n n),Rat.le_trans (B.le_upper n n) hhi.2⟩
  exact RealCompute.le_antisymm
    (RealCompute.le_of_sameStage (hcontinuous x hx hs) hy (fun n => (hov n).1))
    (RealCompute.le_of_sameStage hy (hcontinuous x hx hs) (fun n => (hov n).2))

/-- Every supplied valid solution in the interval equals the constructed one. -/
theorem inverse_unique {F : FunctionOnInterval} (E : Extension F)
    (hcontinuous : E.Continuous) (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (y : RealCompute) (hy : y.Valid) (hr : InRange F hab y)
    (z : RealCompute) (hz : z.Valid) (hsz : Source F z)
    (hsolution : (E.eval z hz hsz).Equiv y) :
    (inverse hstrict hab y hy hr).Equiv z := by
  apply E.injective hcontinuous hstrict _ z (inverse_valid hstrict hab y hy hr) hz
    (inverse_source hstrict hab y hy hr) hsz
  exact RealCompute.equiv_trans
    (hcontinuous _ (inverse_valid hstrict hab y hy hr) (inverse_source hstrict hab y hy hr))
    hy (hcontinuous z hz hsz)
    (inverse_target E hcontinuous hstrict hab y hy hr) (RealCompute.equiv_symm hsolution)

/-- Equivalent target names produce equivalent inverse names. -/
theorem inverse_congr {F : FunctionOnInterval} (E : Extension F)
    (hcontinuous : E.Continuous) (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (y z : RealCompute) (hy : y.Valid) (hz : z.Valid)
    (hry : InRange F hab y) (hrz : InRange F hab z) (heq : y.Equiv z) :
    (inverse hstrict hab y hy hry).Equiv (inverse hstrict hab z hz hrz) := by
  apply inverse_unique E hcontinuous hstrict hab y hy hry _
    (inverse_valid hstrict hab z hz hrz) (inverse_source hstrict hab z hz hrz)
  exact RealCompute.equiv_trans
    (hcontinuous _ (inverse_valid hstrict hab z hz hrz) (inverse_source hstrict hab z hz hrz))
    hz hy (inverse_target E hcontinuous hstrict hab z hz hrz) (RealCompute.equiv_symm heq)

theorem Extension.eval_inRange {F : FunctionOnInterval} (E : Extension F)
    (hstrict : StrictlyIncreasing F) (hab : F.lower ≤ F.upper)
    (x : RealCompute) (hx : x.Valid) (hs : Source F x) :
    InRange F hab (E.eval x hx hs) := by
  constructor
  · exact E.sample_le_eval hstrict x hx hs _ ⟨Rat.le_refl,hab⟩
      (fun k => Rat.le_trans (hs k).1 (hs k).2.1)
  · exact E.eval_le_sample hstrict x hx hs _ ⟨hab,Rat.le_refl⟩
      (fun k => Rat.le_trans (hs k).2.1 (hs k).2.2)

/-- The other inverse law holds for every valid source name in the interval. -/
theorem inverse_eval {F : FunctionOnInterval} (E : Extension F)
    (hcontinuous : E.Continuous) (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (x : RealCompute) (hx : x.Valid) (hs : Source F x) :
    (inverse hstrict hab (E.eval x hx hs) (hcontinuous x hx hs)
      (E.eval_inRange hstrict hab x hx hs)).Equiv x :=
  inverse_unique E hcontinuous hstrict hab _ (hcontinuous x hx hs)
    (E.eval_inRange hstrict hab x hx hs) x hx hs
    (RealCompute.equiv_refl _ (hcontinuous x hx hs))

/-- The inverse law on every valid name of a source value. Callers supply only
value membership, not a pre-clipped name or an internal precision schedule. -/
theorem inverse_evalOn {F : FunctionOnInterval} (E : Extension F)
    (hcontinuous : E.Continuous) (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (x : RealCompute) (hx : x.Valid) (hs : InSource F x) :
    (inverse hstrict hab (E.evalOn hab x hx hs)
      (hcontinuous _ (clip_valid hab x hx hs) (clip_source hab x hx hs))
      (E.eval_inRange hstrict hab _ (clip_valid hab x hx hs) (clip_source hab x hx hs))).Equiv x :=
  RealCompute.equiv_trans
    (inverse_valid hstrict hab _
      (hcontinuous _ (clip_valid hab x hx hs) (clip_source hab x hx hs))
      (E.eval_inRange hstrict hab _ (clip_valid hab x hx hs) (clip_source hab x hx hs)))
    (clip_valid hab x hx hs) hx
    (inverse_eval E hcontinuous hstrict hab _ (clip_valid hab x hx hs) (clip_source hab x hx hs))
    (clip_equiv hab x hx hs)

/-- The endpoint range as a predicate on mathematical real values. -/
def ValueInRange (F : FunctionOnInterval) (hab : F.lower ≤ F.upper)
    (y : ComputableAnalysis.Real) : Prop :=
  RealComputeQuotient.ofRaw (sample F F.lower ⟨Rat.le_refl,hab⟩)
    (sample_valid F F.lower ⟨Rat.le_refl,hab⟩) ≤ y ∧
  y ≤ RealComputeQuotient.ofRaw (sample F F.upper ⟨hab,Rat.le_refl⟩)
    (sample_valid F F.upper ⟨hab,Rat.le_refl⟩)

/-- The inverse on quotient values is executable by quotient lifting. Its
computation uses the supplied target name, with no representative choice. -/
def inverseValue {F : FunctionOnInterval} (E : Extension F)
    (hcontinuous : E.Continuous) (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (y : ComputableAnalysis.Real) (hr : ValueInRange F hab y) :
    ComputableAnalysis.Real := by
  refine Quotient.pliftOn y (fun c hc => ?_) ?_
  · have hr' : InRange F hab c.val := by
      change ValueInRange F hab (RealComputeQuotient.ofRaw c.val c.property)
      have hc' : y = RealComputeQuotient.ofRaw c.val c.property := hc
      rw [← hc']
      exact hr
    exact RealComputeQuotient.ofRaw (inverse hstrict hab c.val c.property hr')
      (inverse_valid hstrict hab c.val c.property hr')
  · intro a b ha hb hequiv
    apply RealComputeQuotient.ofRaw_eq_ofRaw
    exact inverse_congr E hcontinuous hstrict hab a.val b.val a.property b.property _ _ hequiv

@[simp] theorem inverseValue_ofRaw {F : FunctionOnInterval} (E : Extension F)
    (hcontinuous : E.Continuous) (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (y : RealCompute) (hy : y.Valid) (hr : InRange F hab y) :
    inverseValue E hcontinuous hstrict hab (RealComputeQuotient.ofRaw y hy) hr =
      RealComputeQuotient.ofRaw (inverse hstrict hab y hy hr)
        (inverse_valid hstrict hab y hy hr) := rfl

/-- The exact target law also holds as equality of mathematical real values. -/
theorem inverse_value_target {F : FunctionOnInterval} (E : Extension F)
    (hcontinuous : E.Continuous) (hstrict : StrictlyIncreasing F)
    (hab : F.lower ≤ F.upper) (y : RealCompute) (hy : y.Valid) (hr : InRange F hab y) :
    RealComputeQuotient.ofRaw
      (E.eval (inverse hstrict hab y hy hr) (inverse_valid hstrict hab y hy hr)
        (inverse_source hstrict hab y hy hr))
      (hcontinuous _ (inverse_valid hstrict hab y hy hr) (inverse_source hstrict hab y hy hr)) =
      RealComputeQuotient.ofRaw y hy :=
  RealComputeQuotient.ofRaw_eq_ofRaw (inverse_target E hcontinuous hstrict hab y hy hr)

end ComputableAnalysis.StrictMonotoneInverse

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