Module mathcomp.reals.reals
From HB Require Import structures.
From mathcomp Require Import all_ssreflect_compat all_algebra.
#[warning="-warn-library-file-internal-analysis"]
From mathcomp Require Import unstable.
From mathcomp Require Import mathcomp_extra boolp classical_sets set_interval.
Declare Scope real_scope.
Set SsrOldRewriteGoalsOrder.
Set Implicit Arguments.
Unset Strict Implicit.
Unset Printing Implicit Defensive.
Import Order.TTheory GRing.Theory Num.Theory.
Delimit Scope real_scope with real.
Local Open Scope classical_set_scope.
Local Open Scope ring_scope.
Section subr_image.
Variable : numDomainType.
Implicit Types (E : set R) (x : R).
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
End subr_image.
Section has_bound_lemmas.
Variable : realDomainType.
Implicit Types E : set R.
Implicit Types x : R.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
~ has_sup E <-> (forall , exists2 , E y & x < y).
Proof.
End has_bound_lemmas.
.
Source code
Source code
Source code
Source code
sup_upper_bound_subdef : forall : set R,
has_sup E -> ubound E (supremum 0 E) ;
sup_adherent_subdef : forall ( : set R) (
Source code
0 < eps -> has_sup E -> exists2 : R, E e & (supremum 0 E - eps) < e
}.
Source code
Source code
.
Source code
Source code
Source code
& Num.ArchiRealField R & Num.RealClosedField R}.
Bind Scope ring_scope with Real.sort.
Definition
Source code
Definition
Source code
Lemma
Source code
has_sup E -> ubound E (sup E).
Proof.
Lemma
Source code
Source code
has_sup E -> exists2 : R, E e & (sup E - eps) < e.
Proof.
Section IsInt.
Context { : realFieldType}.
Definition
Source code
Arguments Rint_pred _ /.
Definition
Source code
Lemma
Source code
Proof.
Lemma
Source code
Lemma
Source code
Proof.
Lemma
Source code
Lemma
Source code
Hint Resolve Rint0 Rint1 RintC : core.
Lemma
Source code
Proof.
.
Source code
Source code
Source code
Rint_subring_closed.
Lemma
Source code
(x + 1 <= y) = (x < y).
Proof.
Lemma
Source code
(x < y + 1) = (x <= y).
Proof.
End IsInt.
Arguments Rint_pred _ _ /.
Section ToInt.
Context { : realType}.
Implicit Types x y : R.
Definition
Source code
if insub x : {? | x \is a Rint} is Some Px then
xchoose (asboolP _ (tagged Px))
else 0.
Lemma
Source code
Proof.
Lemma
Source code
Lemma
Source code
Lemma
Source code
Lemma
Source code
End ToInt.
Section RealDerivedOps.
Variable : realType.
Implicit Types x y : R.
Definition
Source code
Definition
Source code
Definition
Source code
Definition
sup : forall {R : realType}, set R -> R sup is not universe polymorphic Arguments sup {R} A%classical_set_scope sup is transparent Expands to: Constant mathcomp.reals.reals.sup Declared in library mathcomp.reals.reals, line 136, characters 11-14
Source code
End RealDerivedOps.
Section RealLemmas.
Variables ( : realType).
Implicit Types E : set R.
Implicit Types x : R.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
by apply/ubP/sup_upper_bound=> //; split; first by exists x.
Qed.
Lemma
Source code
~ E (sup E) -> E `<=` [set | r < sup E].
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
have Dz: 2%:R * z = x + y by rewrite mulrC divfK// pnatr_eq0.
have ubE : has_sup E by split => //; exists x.
have [/downP [t Et lezt] | leyz] := sup_total z ubE.
rewrite -(lerD2l x) -Dz -mulr2n -[leRHS]mulr_natl.
rewrite ler_pM2l ?ltr0Sn //; apply/(le_trans lezt).
by move/ubP : leEx; exact.
rewrite -(lerD2r y) -Dz -mulr2n -[leLHS]mulr_natl.
by rewrite ler_pM2l ?ltr0Sn.
Qed.
Lemma
Source code
(forall , A a -> B b -> a <= b) -> sup (A `|` B) = sup B.
Proof.
- apply: ge_sup => [|x [Ax|]]; first by apply: subset_nonempty B0 => ?; right.
by case: B0 => b Bb; rewrite (le_trans (AB _ _ Ax Bb))// ub_le_sup//; exists l.
- by move=> Bx; rewrite ub_le_sup //; exists l.
- apply: ge_sup => // b Bb; apply: ub_le_sup; last by right.
by exists l => x [Ax|Bx]; [rewrite (le_trans (AB _ _ Ax Bb)) // Bl|exact: Bl].
Qed.
Lemma
Source code
(x < sup S -> exists2 , S y & x < y)%R.
Proof.
End RealLemmas.
#[deprecated(since="mathcomp-analysis 1.14.0", note="Renamed `ub_le_sup`.")]
Notation
Source code
#[deprecated(since="mathcomp-analysis 1.14.0", note="Renamed `ge_sup`.")]
Notation
Source code
Section sup_sum.
Context { : realType}.
Lemma
Source code
has_sup A -> has_sup B -> sup [set x + y | in A & in B] = sup A + sup B.
Proof.
have ABsup : has_sup [set x + y | in A & in B].
split; first by exists (a + b), a => //; exists b.
case: ubA ubB => p up [q uq]; exists (p + q) => ? [r Ar [s Bs] <-].
by apply: lerD; [exact: up | exact: uq].
apply: le_anti; apply/andP; split.
apply: ge_sup; first by case: ABsup.
by move=> ? [p Ap [q Bq] <-]; apply: lerD; exact: ub_le_sup.
rewrite leNgt -subr_gt0; apply/negP.
set eps := (_ + _ - _) => epos.
have e2pos : 0 < eps / 2%:R by rewrite divr_gt0// ltr0n.
have [r Ar supBr] := sup_adherent e2pos supA.
have [s Bs supAs] := sup_adherent e2pos supB.
have := ltrD supBr supAs.
rewrite -addrACA -opprD -splitr subKr; apply/negP; rewrite -leNgt.
by apply: sup_upper_bound => //; exists r => //; exists s.
Qed.
Lemma
Source code
has_inf A -> has_inf B -> inf [set x + y | in A & in B] = inf A + inf B.
Proof.
rewrite [X in - sup X = _](_ : _ =
[set x + y | in [set - x | in A ] & in [set - x | in B]]).
by rewrite sup_sumE // -opprD.
rewrite eqEsubset; split => /= t [] /= x []a Aa.
case => b Bb <- <-; exists (- a); first by exists a.
by exists (- b); [exists b|rewrite opprD].
move=> <- [y] [b Bb] <- <-; exists (a + b); last by rewrite opprD.
by exists a => //; exists b.
Qed.
End sup_sum.
Section InfTheory.
Variables ( : realType).
Implicit Types E : set R.
Implicit Types x : R.
Lemma
Source code
Source code
has_inf E -> exists2 , E e & e < inf E + eps.
Proof.
exists (- e); first by case: NEx => x Ex <-{}; rewrite opprK.
by rewrite ltrNl -mulN1r mulrDr !mulN1r opprK.
Qed.
Lemma
Source code
Proof.
exact/has_inf_supN.
Qed.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
~ E (inf E) -> E `<=` [set | inf E < r].
Proof.
Lemma
Source code
Lemma
Source code
~ has_inf E <-> (forall , exists2 , E y & y < x).
Proof.
Lemma
Source code
(forall , A a -> B b -> a <= b) -> inf (A `|` B) = inf A.
Proof.
rewrite image_setU setUC sup_setU //; first exact/has_inf_supN.
by move=> _ _ [] b Bb <-{} [] a Aa <-{}; rewrite lerNl opprK; apply AB.
Qed.
Lemma
Source code
(inf S < x -> exists2 , S y & y < x)%R.
Proof.
End InfTheory.
#[deprecated(since="mathcomp-analysis 1.14.0", note="Renamed `ge_inf`.")]
Notation
Source code
Section FloorTheory.
Variable : realType.
Implicit Types (x y : R) (i : int).
Lemma
Source code
Proof.
rewrite /floor_set/mkset rpredN rpred_int /= lerNl.
case: (ger0P (-x)) => [/archi_boundP/ltW//|].
by move/ltW/le_trans; apply; rewrite ler0z.
apply/ubP=> y /andP[_] /le_trans; apply.
case: (ger0P x)=> [/archi_boundP/ltW|] //.
by move/ltW/le_trans; apply; rewrite ler0z.
Qed.
Lemma
Source code
Proof.
have /sup_upper_bound /ubP /(_ _ Fy) := has_sup_floor_set x.
rewrite le_eqVlt=> /orP[/eqP<-//| lt_yFx].
rewrite ltrBlDr -ltrBlDl => lt1_FxBy.
pose e := sup (floor_set x) - y; have := has_sup_floor_set x.
move/sup_adherent=> -/(_ e) []; first by rewrite subr_gt0.
move=> z Fz; rewrite /= subKr => lt_yz.
have /sup_upper_bound /ubP /(_ _ Fz) := has_sup_floor_set x.
rewrite -(lerD2r (-y)) => /le_lt_trans /(_ lt1_FxBy).
case/andP: Fy Fz lt_yz=> /RintP[yi -> _].
case/andP=> /RintP[zi -> _]; rewrite -rmorphB /= ltrz1 ltr_int.
rewrite lt_neqAle => /andP[ne_yz le_yz].
rewrite -[_-_]gez0_abs ?subr_ge0 // ltz_nat ltnS leqn0.
by rewrite absz_eq0 subr_eq0 eq_sym (negbTE ne_yz).
Qed.
Lemma
Source code
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Lemma
Source code
Proof.
Lemma
Source code
Lemma
Source code
Lemma
Source code
Lemma
Source code
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Lemma
Source code
Proof.
Lemma
Source code
Proof.
End FloorTheory.
Section CeilTheory.
Variable : realType.
Implicit Types x y : R.
Lemma
Source code
Lemma
Source code
Lemma
Source code
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
End CeilTheory.
Section Sup.
Context { : realType}.
Implicit Types A B : set R.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
Lemma
Source code
Proof.
case: nzA => x /downP[y yS le_xy]; split; first by exists y.
case: nzubA=> u /ubP ubA; exists u; apply/ubP=> z zS.
by apply/ubA; apply/downP; exists z.
case: nzA => x xA; split; first by exists x; apply/le_down.
case: nzubA => u /ubP ubA; exists u; apply/ubP=> y /downP [].
by move=> z zA /le_trans; apply; apply/ubA.
Qed.
Lemma
Source code
sup A <= sup B.
Proof.
split=> //; case: hs_B => _ [x ubx].
exists x; apply/ubP=> y /le_AB /downP[z zB le_yz].
by apply/(le_trans le_yz); move/ubP: ubx; apply.
rewrite leNgt -subr_gt0; apply/negP => lt_sup.
case: (sup_adherent lt_sup hs_A )=> x /le_AB xdB.
rewrite subKr => lt_Bx; case/downP: xdB => z zB.
move/(lt_le_trans lt_Bx); rewrite ltNge.
by move/ubP : (sup_upper_bound hs_B) => ->.
Qed.
Lemma
Source code
inf A <= inf B.
Proof.
Lemma
Source code
Proof.
Lemma
Source code
has_sup [set | exists , y = F x] ->
l < sup [set | exists , y = F x] ->
exists2 , l < F x & F x <= sup [set | exists , y = F x].
Proof.
move=> /sup_adherent/(_ hs)[_ [x ->]]; rewrite subKr=> lt_lFx.
by exists x => //; move/ubP : (sup_upper_bound hs) => -> //; exists x.
Qed.
Lemma
Source code
has_inf [set | exists , y = F x] ->
inf [set | exists , y = F x] < l ->
exists2 , F x < l & inf [set | exists , y = F x] <= F x.
Proof.
End Sup.
#[deprecated(since="mathcomp-analysis 1.14.0", note="Renamed `inf_le`.")]
Notation
Source code
#[deprecated(since="mathcomp-analysis 1.14.0", note="Renamed `sup_le`.")]
Notation
Source code
Lemma
Source code
exists , B j /\ forall , B k -> j <= k.
Proof.
by exists `|i0 - i|%N; rewrite gez0_abs // subr_ge0; exact: lbBi.
elim: n i lbBi i0in => [i lbBi /eqP|n ih i lbBi i0in1].
by rewrite subr_eq0 => /eqP i0i; exists i0; split =>// k Bk; rewrite i0i lbBi.
have i0i1n : i0 - (i + 1) = n by rewrite opprD addrA i0in1 -addn1 PoszD addrK.
have [?|/not_forallP] := pselect (lbound B (i + 1)); first exact: (ih (i + 1)).
move=> /contrapT[x /not_implyP[Bx i1x]]; exists x; split => // k Bk.
rewrite (le_trans _ (lbBi _ Bk)) //.
by move/negP : i1x; rewrite -ltNge ltzD1.
Qed.
Lemma
Source code
exists , A j /\ forall , A k -> (j <= k)%N.
Proof.
Section rat_in_itvoo.
Let
Source code
if y < 0 then 0%N else Num.bound (y / x).
Let
Source code
0 < x -> y < x *+ bound_div x y.
Proof.
rewrite /bound_div (ltNge y 0) y0/= -mulr_natl -ltr_pdivrMr//.
by rewrite archi_boundP// (divr_ge0 _(ltW _)).
Qed.
Lemma
Source code
x < y -> exists , ratr q \in `]x, y[.
Proof.
move=> /(archi_bound_divP 1); set n := bound_div _ _ => nyx.
have [m1 m1nx] : exists , m1.+1%:~R > x *+ n.
have := archi_bound_divP (x *+ n) ltr01; set p := bound_div _ _ => nxp.
have [x0|x0] := ltP 0 x.
exists p.-1; rewrite prednK // lt0n; apply: contraPN nxp => /eqP ->.
by apply/negP; rewrite -leNgt mulrn_wge0 // ltW.
by exists 0%N; rewrite (le_lt_trans _ ltr01) // mulrn_wle0.
have [m2 m2nx] : exists , m2.+1%:~R > - x *+ n.
have := archi_bound_divP (- x *+ n) ltr01; set p := bound_div _ _ => nxp.
have [x0|x0] := ltP 0 x.
by exists O; rewrite (le_lt_trans _ ltr01) // nmulrn_rle0// oppr_lt0.
exists p.-1; rewrite prednK // -(ltr_nat R) (le_lt_trans _ nxp) //.
by rewrite mulrn_wge0 // oppr_ge0.
have : exists , -(m2.+1 : int) <= m <= m1.+1 /\ m%:~R - 1 <= x *+ n < m%:~R.
have m2m1 : - (m2.+1 : int) < m1.+1.
by rewrite -(ltr_int R) (lt_trans _ m1nx)// rmorphN /= ltrNl // -mulNrn.
pose B := [set : int | m%:~R > x *+ n].
have m1B : B m1.+1 by [].
have m2B : lbound B (- m2.+1%:~R).
move=> i; rewrite /B /= -(opprK (x *+ n)) -ltrNl -mulNrn => nxi.
rewrite -(mulN1r m2.+1%:~R) mulN1r -lerNl.
by have := lt_trans nxi m2nx; rewrite intz -mulrNz ltr_int => /ltW.
have [m [Bm infB]] := int_lbound_has_minimum (ex_intro _ _ m1B) m2B.
have mN1B : ~ B (m - 1).
by move=> /infB; apply/negP; rewrite -ltNge ltrBlDr ltzD1.
exists m; split; [apply/andP; split|apply/andP; split] => //.
- by move: m2B; rewrite /lbound /= => /(_ _ Bm); rewrite intz.
- exact: infB.
- by rewrite leNgt; apply/negP; rewrite /B /= intrD in mN1B.
move=> [m [/andP[m2m mm1] /andP[mnx nxm]]].
have [/andP[a b] c] : x *+ n < m%:~R <= 1 + x *+ n /\ 1 + x *+ n < y *+ n.
split; [apply/andP; split|] => //; first by rewrite -lerBlDl.
by move: nyx; rewrite mulrnDl -ltrBrDr mulNrn.
have n_gt0 : n != 0%N by apply: contraTN nyx => /eqP ->; rewrite mulr0n ltr10.
exists (m%:Q / n%:Q); rewrite in_itv /= fmorph_div/= ratr_nat ratr_int.
rewrite ltr_pdivlMr ?ltr_pdivrMr ?ltr0n ?lt0n// !mulr_natr nxm/=.
apply: (le_lt_trans b c).
Qed.
End rat_in_itvoo.
Section rational.
Context { : realType}.
Definition
inf : forall {R : realType}, set R -> R inf is not universe polymorphic Arguments inf {R} E%classical_set_scope inf is transparent Expands to: Constant mathcomp.reals.reals.inf Declared in library mathcomp.reals.reals, line 137, characters 11-14 Rint_pred : forall {R : realFieldType}, R -> bool Rint_pred is not universe polymorphic Arguments Rint_pred {R} x%ring_scope / The reduction tactics unfold Rint_pred when applied to 2 arguments Rint_pred is transparent Expands to: Constant mathcomp.reals.reals.Rint_pred Declared in library mathcomp.reals.reals, line 152, characters 11-20 Rint : forall {R : realFieldType}, qualifier 1 R Rint is not universe polymorphic Arguments Rint {R} Rint is transparent Expands to: Constant mathcomp.reals.reals.Rint Declared in library mathcomp.reals.reals, line 154, characters 11-15
Source code
Lemma
Source code
rational r <-> exists ( : int) ( : nat), r = a%:~R / b%:R.
Proof.
Definition
Rtoint : forall {R : realType}, R -> int Rtoint is not universe polymorphic Arguments Rtoint {R} x%ring_scope Rtoint is transparent Expands to: Constant mathcomp.reals.reals.Rtoint Declared in library mathcomp.reals.reals, line 207, characters 11-17
Source code
Lemma
Source code
Proof.
by apply: (rE q Logic.I) => /=; exists q.
by apply: contra_not rE => -[_ -> <-{r}]; exists q.
Qed.
End rational.