Timings for ConstructiveRealsMorphisms.v
- /home/gitlab-runner/builds/gGKko-aj/0/coq/coq/_bench/opam.OLD/ocaml-OLD/.opam-switch/build/coq-stdlib.dev/_build/default/theories//./Reals/Abstract/ConstructiveRealsMorphisms.timing
- /home/gitlab-runner/builds/gGKko-aj/0/coq/coq/_bench/opam.NEW/ocaml-NEW/.opam-switch/build/coq-stdlib.dev/_build/default/theories//./Reals/Abstract/ConstructiveRealsMorphisms.timing
(************************************************************************)
(* * The Coq Proof Assistant / The Coq Development Team *)
(* v * INRIA, CNRS and contributors - Copyright 1999-2019 *)
(* <O___,, * (see CREDITS file for the list of authors) *)
(* \VV/ **************************************************************)
(* // * This file is distributed under the terms of the *)
(* * GNU Lesser General Public License Version 2.1 *)
(* * (see LICENSE file for the text of the license) *)
(************************************************************************)
(************************************************************************)
(** Morphisms used to transport results from any instance of
ConstructiveReals to any other.
Between any two constructive reals structures R1 and R2,
all morphisms R1 -> R2 are extensionally equal. We will
further show that they exist, and so are isomorphisms.
The difference between two morphisms R1 -> R2 is therefore
the speed of computation.
The canonical isomorphisms we provide here are often very slow,
when a new implementation of constructive reals is added,
it should define its own ad hoc isomorphisms for better speed.
Apart from the speed, those unique isomorphisms also serve as
sanity checks of the interface ConstructiveReals :
it captures a concept with a strong notion of uniqueness.
WARNING: this file is experimental and likely to change in future releases.
*)
Require Import ConstructiveReals.
Require Import ConstructiveLimits.
Require Import ConstructiveAbs.
Local Open Scope ConstructiveReals.
Record ConstructiveRealsMorphism {R1 R2 : ConstructiveReals} : Set :=
{
CRmorph : CRcarrier R1 -> CRcarrier R2;
CRmorph_rat : forall q : Q,
CRmorph (CR_of_Q R1 q) == CR_of_Q R2 q;
CRmorph_increasing : forall x y : CRcarrier R1,
CRlt R1 x y -> CRlt R2 (CRmorph x) (CRmorph y);
}.
Lemma CRmorph_increasing_inv
: forall {R1 R2 : ConstructiveReals}
(f : ConstructiveRealsMorphism)
(x y : CRcarrier R1),
CRlt R2 (CRmorph f x) (CRmorph f y)
-> CRlt R1 x y.
destruct (CR_Q_dense R2 _ _ H) as [q [H0 H1]].
destruct (CR_Q_dense R2 _ _ H0) as [r [H2 H3]].
apply lt_CR_of_Q, (CR_of_Q_lt R1) in H3.
destruct (CRltLinear R1).
apply (CRmorph_increasing f) in c.
destruct (CRmorph_rat f r) as [H4 _].
apply (CRle_lt_trans _ _ _ H4) in c.
exact (CRlt_asym _ _ c H2).
apply (CRlt_trans _ _ _ c).
destruct (CR_Q_dense R2 _ _ H1) as [t [H2 H3]].
apply lt_CR_of_Q, (CR_of_Q_lt R1) in H2.
apply (CRmorph_increasing f) in c.
destruct (CRmorph_rat f t) as [_ H4].
apply (CRlt_le_trans _ _ _ c) in H4.
exact (CRlt_asym _ _ H4 H3).
Lemma CRmorph_unique : forall {R1 R2 : ConstructiveReals}
(f g : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1),
CRmorph f x == CRmorph g x.
destruct (CR_Q_dense R2 _ _ abs) as [q [H H0]].
destruct (CRmorph_rat f q) as [H1 _].
apply (CRlt_le_trans _ _ _ H) in H1.
apply CRmorph_increasing_inv in H1.
destruct (CRmorph_rat g q) as [_ H2].
apply (CRle_lt_trans _ _ _ H2) in H0.
apply CRmorph_increasing_inv in H0.
exact (CRlt_asym _ _ H0 H1).
destruct (CR_Q_dense R2 _ _ abs) as [q [H H0]].
destruct (CRmorph_rat f q) as [_ H1].
apply (CRle_lt_trans _ _ _ H1) in H0.
apply CRmorph_increasing_inv in H0.
destruct (CRmorph_rat g q) as [H2 _].
apply (CRlt_le_trans _ _ _ H) in H2.
apply CRmorph_increasing_inv in H2.
exact (CRlt_asym _ _ H0 H2).
(* The identity is the only endomorphism of constructive reals.
For any ConstructiveReals R1, R2 and any morphisms
f : R1 -> R2 and g : R2 -> R1,
f and g are isomorphisms and are inverses of each other. *)
Lemma Endomorph_id
: forall {R : ConstructiveReals} (f : @ConstructiveRealsMorphism R R)
(x : CRcarrier R),
CRmorph f x == x.
destruct (CR_Q_dense R _ _ abs) as [q [H0 H1]].
destruct (CRmorph_rat f q) as [H _].
apply (CRlt_le_trans _ _ _ H0) in H.
apply CRmorph_increasing_inv in H.
exact (CRlt_asym _ _ H1 H).
destruct (CR_Q_dense R _ _ abs) as [q [H0 H1]].
destruct (CRmorph_rat f q) as [_ H].
apply (CRle_lt_trans _ _ _ H) in H1.
apply CRmorph_increasing_inv in H1.
exact (CRlt_asym _ _ H1 H0).
Lemma CRmorph_proper
: forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x y : CRcarrier R1),
x == y -> CRmorph f x == CRmorph f y.
apply CRmorph_increasing_inv in abs.
apply CRmorph_increasing_inv in abs.
Definition CRmorph_compose {R1 R2 R3 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(g : @ConstructiveRealsMorphism R2 R3)
: @ConstructiveRealsMorphism R1 R3.
apply (Build_ConstructiveRealsMorphism
R1 R3 (fun x:CRcarrier R1 => CRmorph g (CRmorph f x))).
apply (CReq_trans _ (CRmorph g (CR_of_Q R2 q))).
apply CRmorph_increasing.
apply CRmorph_increasing.
Lemma CRmorph_le : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x y : CRcarrier R1),
x <= y -> CRmorph f x <= CRmorph f y.
apply CRmorph_increasing_inv in abs.
Lemma CRmorph_le_inv : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x y : CRcarrier R1),
CRmorph f x <= CRmorph f y -> x <= y.
apply (CRmorph_increasing f) in abs.
Lemma CRmorph_zero : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2),
CRmorph f 0 == 0.
apply (CReq_trans _ (CRmorph f (CR_of_Q R1 0))).
Lemma CRmorph_one : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2),
CRmorph f 1 == 1.
apply (CReq_trans _ (CRmorph f (CR_of_Q R1 1))).
Lemma CRmorph_opp : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1),
CRmorph f (- x) == - CRmorph f x.
destruct (CR_Q_dense R2 _ _ abs) as [q [H H0]].
destruct (CRmorph_rat f q) as [H1 _].
apply (CRlt_le_trans _ _ _ H) in H1.
apply CRmorph_increasing_inv in H1.
apply CRopp_gt_lt_contravar in H0.
destruct (@CR_of_Q_opp R2 q) as [H2 _].
apply (CRlt_le_trans _ _ _ H0) in H2.
pose proof (CRopp_involutive (CRmorph f x)) as [H _].
apply (CRle_lt_trans _ _ _ H) in H2.
destruct (CRmorph_rat f (-q)) as [H _].
apply (CRlt_le_trans _ _ _ H2) in H.
apply CRmorph_increasing_inv in H.
destruct (@CR_of_Q_opp R1 q) as [_ H2].
apply (CRlt_le_trans _ _ _ H) in H2.
apply CRopp_gt_lt_contravar in H2.
pose proof (CRopp_involutive (CR_of_Q R1 q)) as [H _].
apply (CRle_lt_trans _ _ _ H) in H2.
exact (CRlt_asym _ _ H1 H2).
destruct (CR_Q_dense R2 _ _ abs) as [q [H H0]].
destruct (CRmorph_rat f q) as [_ H1].
apply (CRle_lt_trans _ _ _ H1) in H0.
apply CRmorph_increasing_inv in H0.
apply CRopp_gt_lt_contravar in H.
pose proof (CRopp_involutive (CRmorph f x)) as [_ H1].
apply (CRlt_le_trans _ _ _ H) in H1.
destruct (@CR_of_Q_opp R2 q) as [_ H2].
apply (CRle_lt_trans _ _ _ H2) in H1.
destruct (CRmorph_rat f (-q)) as [_ H].
apply (CRle_lt_trans _ _ _ H) in H1.
apply CRmorph_increasing_inv in H1.
destruct (@CR_of_Q_opp R1 q) as [H2 _].
apply (CRle_lt_trans _ _ _ H2) in H1.
apply CRopp_gt_lt_contravar in H1.
pose proof (CRopp_involutive (CR_of_Q R1 q)) as [_ H].
apply (CRlt_le_trans _ _ _ H1) in H.
exact (CRlt_asym _ _ H0 H).
Lemma CRplus_pos_rat_lt : forall {R : ConstructiveReals} (x : CRcarrier R) (q : Q),
Qlt 0 q -> CRlt R x (CRplus R x (CR_of_Q R q)).
apply (CRle_lt_trans _ (CRplus R x 0)).
apply CRplus_lt_compat_l.
apply (CRle_lt_trans _ (CR_of_Q R 0)).
Lemma CRplus_neg_rat_lt : forall {R : ConstructiveReals} (x : CRcarrier R) (q : Q),
Qlt q 0 -> CRlt R (CRplus R x (CR_of_Q R q)) x.
apply (CRlt_le_trans _ (CRplus R x 0)).
apply CRplus_lt_compat_l.
apply (CRlt_le_trans _ (CR_of_Q R 0)).
Lemma CRmorph_plus_rat : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1) (q : Q),
CRmorph f (CRplus R1 x (CR_of_Q R1 q))
== CRplus R2 (CRmorph f x) (CR_of_Q R2 q).
destruct (CR_Q_dense R2 _ _ abs) as [r [H H0]].
destruct (CRmorph_rat f r) as [H1 _].
apply (CRlt_le_trans _ _ _ H) in H1.
apply CRmorph_increasing_inv in H1.
apply (CRlt_asym _ _ H1).
apply (CRplus_lt_reg_r (CRopp R1 (CR_of_Q R1 q))).
apply (CRlt_le_trans _ x).
apply (CRle_lt_trans _ (CR_of_Q R1 (r-q))).
apply (CRle_trans _ (CRplus R1 (CR_of_Q R1 r) (CR_of_Q R1 (-q)))).
apply CRplus_le_compat_l.
destruct (@CR_of_Q_opp R1 q).
destruct (CR_of_Q_plus R1 r (-q)).
apply (CRmorph_increasing_inv f).
apply (CRle_lt_trans _ (CR_of_Q R2 (r - q))).
apply (CRplus_lt_reg_r (CR_of_Q R2 q)).
apply (CRle_lt_trans _ (CR_of_Q R2 r)).
destruct (CR_of_Q_plus R2 (r-q) q) as [H1 _].
apply (CRlt_le_trans _ _ _ H) in H1.
exact (Qlt_not_le _ _ H1 (Qle_refl _)).
apply (CRle_trans
_ (CRplus R1 x (CRplus R1 (CR_of_Q R1 q) (CRopp R1 (CR_of_Q R1 q))))).
apply (CRle_trans _ (CRplus R1 x 0)).
apply CRplus_le_compat_l.
destruct (Ropp_def (CR_of_Q R1 q)).
destruct (Radd_assoc x (CR_of_Q R1 q) (CRopp R1 (CR_of_Q R1 q))).
destruct (CR_Q_dense R2 _ _ abs) as [r [H H0]].
destruct (CRmorph_rat f r) as [_ H1].
apply (CRle_lt_trans _ _ _ H1) in H0.
apply CRmorph_increasing_inv in H0.
apply (CRlt_asym _ _ H0).
apply (CRplus_lt_reg_r (CRopp R1 (CR_of_Q R1 q))).
apply (CRle_lt_trans _ x).
apply (CRle_trans
_ (CRplus R1 x (CRplus R1 (CR_of_Q R1 q) (CRopp R1 (CR_of_Q R1 q))))).
destruct (Radd_assoc x (CR_of_Q R1 q) (CRopp R1 (CR_of_Q R1 q))).
apply (CRle_trans _ (CRplus R1 x 0)).
apply CRplus_le_compat_l.
destruct (Ropp_def (CR_of_Q R1 q)).
apply (CRlt_le_trans _ (CR_of_Q R1 (r-q))).
apply (CRmorph_increasing_inv f).
apply (CRlt_le_trans _ (CR_of_Q R2 (r - q))).
apply (CRplus_lt_reg_r (CR_of_Q R2 q)).
apply (CRlt_le_trans _ _ _ H).
apply (CRle_trans _ (CR_of_Q R2 (r-q+q))).
exact (Qlt_not_le _ _ abs (Qle_refl _)).
destruct (CR_of_Q_plus R2 (r-q) q).
apply (CRle_trans _ (CRplus R1 (CR_of_Q R1 r) (CR_of_Q R1 (-q)))).
destruct (CR_of_Q_plus R1 r (-q)).
apply CRplus_le_compat_l.
destruct (@CR_of_Q_opp R1 q).
Lemma CRmorph_plus : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x y : CRcarrier R1),
CRmorph f (CRplus R1 x y)
== CRplus R2 (CRmorph f x) (CRmorph f y).
assert (forall (x y : CRcarrier R1),
CRplus R2 (CRmorph f x) (CRmorph f y)
<= CRmorph f (CRplus R1 x y)).
destruct (CR_Q_dense R2 _ _ abs) as [r [H H0]].
destruct (CRmorph_rat f r) as [H1 _].
apply (CRlt_le_trans _ _ _ H) in H1.
apply CRmorph_increasing_inv in H1.
apply (CRlt_asym _ _ H1).
destruct (CR_Q_dense R2 _ _ H0) as [q [H2 H3]].
assert (Qlt (r-q) 0) as epsNeg.
apply (Qplus_lt_r _ _ q).
destruct (CR_Q_dense R1 _ _ (CRplus_neg_rat_lt x (r-q) epsNeg))
as [s [H4 H5]].
apply (CRlt_trans _ (CRplus R1 (CR_of_Q R1 s) y)).
2: apply CRplus_lt_compat_r, H5.
apply (CRmorph_increasing_inv f).
apply (CRlt_le_trans _ (CRplus R2 (CR_of_Q R2 s) (CRmorph f y))).
apply (CRmorph_increasing f) in H4.
destruct (CRmorph_plus_rat f x (r-q)) as [H _].
apply (CRle_lt_trans _ _ _ H) in H4.
destruct (CRmorph_rat f s) as [_ H1].
apply (CRlt_le_trans _ _ _ H4) in H1.
apply (CRlt_trans
_ (CRplus R2 (CRplus R2 (CRmorph f x) (CR_of_Q R2 (r - q)))
(CRmorph f y))).
2: apply CRplus_lt_compat_r, H1.
apply (CRlt_le_trans
_ (CRplus R2 (CRplus R2 (CR_of_Q R2 (r - q)) (CRmorph f x))
(CRmorph f y))).
apply (CRlt_le_trans
_ (CRplus R2 (CR_of_Q R2 (r - q))
(CRplus R2 (CRmorph f x) (CRmorph f y)))).
apply (CRle_lt_trans _ (CRplus R2 (CR_of_Q R2 (r - q)) (CR_of_Q R2 q))).
2: apply CRplus_lt_compat_l, H3.
destruct (CR_of_Q_plus R2 (r-q) q) as [_ H4].
apply (CRle_lt_trans _ _ _ H4) in abs.
destruct (CRmorph_rat f r) as [_ H4].
apply (CRlt_le_trans _ _ _ abs) in H4.
exact (Qlt_not_le _ _ H4 (Qle_refl _)).
destruct (CRisRing R2); apply Radd_assoc.
apply CRplus_le_compat_r.
destruct (Radd_comm (CRmorph f x) (CR_of_Q R2 (r - q))).
destruct (CRmorph_plus_rat f y s) as [H _].
apply (CRlt_le_trans _ (CRplus R2 (CR_of_Q R2 s) (CRmorph f y))).
apply (CRle_lt_trans _ (CRmorph f (CRplus R1 (CR_of_Q R1 s) y))).
destruct (CRisRing R1); apply Radd_comm.
destruct (CRisRing R2); apply Radd_comm.
specialize (H (CRplus R1 x y) (CRopp R1 y)).
apply (CRle_lt_trans _ (CRmorph f x)).
apply (CReq_trans _ (CRplus R1 x (CRplus R1 y (CRopp R1 y)))).
apply CReq_sym, Radd_assoc.
apply (CReq_trans _ (CRplus R1 x 0)).
destruct (CRisRingExt R1).
apply (CRplus_lt_reg_r (CRmorph f y)).
apply (CRlt_le_trans _ _ _ abs).
apply (CRle_trans _ (CRplus R2 (CRmorph f (CRplus R1 x y)) 0)).
destruct (CRplus_0_r (CRmorph f (CRplus R1 x y))).
apply (CRle_trans _ (CRplus R2 (CRmorph f (CRplus R1 x y))
(CRplus R2 (CRmorph f (CRopp R1 y)) (CRmorph f y)))).
apply CRplus_le_compat_l.
apply (CRle_trans
_ (CRplus R2 (CRopp R2 (CRmorph f y)) (CRmorph f y))).
destruct (CRplus_opp_l (CRmorph f y)).
apply CRplus_le_compat_r.
destruct (CRmorph_opp f y).
destruct (Radd_assoc (CRmorph f (CRplus R1 x y))
(CRmorph f (CRopp R1 y)) (CRmorph f y)).
Lemma CRmorph_mult_pos : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1) (n : nat),
CRmorph f (CRmult R1 x (CR_of_Q R1 (Z.of_nat n # 1)))
== CRmult R2 (CRmorph f x) (CR_of_Q R2 (Z.of_nat n # 1)).
destruct (CRisRingExt R1).
apply (CReq_trans _ (CRmorph f 0)).
apply (CReq_trans _ (CRmult R1 x 0)).
apply (CReq_trans _ (CRmult R2 (CRmorph f x) 0)).
apply CReq_sym, CRmult_0_r.
destruct (CRisRingExt R2).
destruct (CRisRingExt R1), (CRisRingExt R2).
transitivity (CRmorph f (CRplus R1 x (CRmult R1 x (CR_of_Q R1 (Z.of_nat n # 1))))).
transitivity (CRmult R1 x (CRplus R1 1 (CR_of_Q R1 (Z.of_nat n # 1)))).
transitivity (CR_of_Q R1 (1 + (Z.of_nat n # 1))).
transitivity (CRplus R1 (CRmult R1 x 1)
(CRmult R1 x (CR_of_Q R1 (Z.of_nat n # 1)))).
apply CRmult_plus_distr_l.
apply (CReq_trans
_ (CRplus R2 (CRmorph f x)
(CRmorph f (CRmult R1 x (CR_of_Q R1 (Z.of_nat n # 1)))))).
apply (CReq_trans
_ (CRplus R2 (CRmorph f x)
(CRmult R2 (CRmorph f x) (CR_of_Q R2 (Z.of_nat n # 1))))).
apply (CReq_trans
_ (CRmult R2 (CRmorph f x) (CRplus R2 1 (CR_of_Q R2 (Z.of_nat n # 1))))).
1:apply (CReq_trans
_ (CRplus R2 (CRmult R2 (CRmorph f x) 1)
(CRmult R2 (CRmorph f x) (CR_of_Q R2 (Z.of_nat n # 1))))).
apply CReq_sym, CRmult_1_r.
apply CReq_sym, CRmult_plus_distr_l.
apply (CReq_trans _ (CR_of_Q R2 (1 + (Z.of_nat n # 1)))).
1:apply (CReq_trans _ (CRplus R2 (CR_of_Q R2 1) (CR_of_Q R2 (Z.of_nat n # 1)))).
apply Radd_ext0; reflexivity.
apply CReq_sym, CR_of_Q_plus.
Lemma NatOfZ : forall n : Z, { p : nat | n = Z.of_nat p \/ n = Z.opp (Z.of_nat p) }.
Lemma CRmorph_mult_int : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1) (n : Z),
CRmorph f (CRmult R1 x (CR_of_Q R1 (n # 1)))
== CRmult R2 (CRmorph f x) (CR_of_Q R2 (n # 1)).
destruct (NatOfZ n) as [p [pos|neg]].
apply (CReq_trans
_ (CRopp R2 (CRmorph f (CRmult R1 x (CR_of_Q R1 (Z.of_nat p # 1)))))).
apply (CReq_trans
_ (CRmorph f (CRopp R1 (CRmult R1 x (CR_of_Q R1 (Z.of_nat p # 1)))))).
apply (CReq_trans _ (CRmult R1 x (CR_of_Q R1 (- (Z.of_nat p # 1))))).
destruct (CRisRingExt R1).
apply (CReq_trans _ (CRmult R1 x (CRopp R1 (CR_of_Q R1 (Z.of_nat p # 1))))).
destruct (CRisRingExt R1).
apply CReq_sym, CRopp_mult_distr_r.
apply (CReq_trans
_ (CRopp R2 (CRmult R2 (CRmorph f x) (CR_of_Q R2 (Z.of_nat p # 1))))).
destruct (CRisRingExt R2).
apply (CReq_trans
_ (CRmult R2 (CRmorph f x) (CRopp R2 (CR_of_Q R2 (Z.of_nat p # 1))))).
apply CRopp_mult_distr_r.
destruct (CRisRingExt R2).
apply (CReq_trans _ (CR_of_Q R2 (- (Z.of_nat p # 1)))).
apply CReq_sym, CR_of_Q_opp.
Lemma CRmorph_mult_inv : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1) (p : positive),
CRmorph f (CRmult R1 x (CR_of_Q R1 (1 # p)))
== CRmult R2 (CRmorph f x) (CR_of_Q R2 (1 # p)).
apply (CRmult_eq_reg_r (CR_of_Q R2 (Z.pos p # 1))).
apply (CRle_lt_trans _ (CR_of_Q R2 0)).
apply (CReq_trans _ (CRmorph f x)).
1:apply (CReq_trans
_ (CRmorph f (CRmult R1 (CRmult R1 x (CR_of_Q R1 (1 # p)))
(CR_of_Q R1 (Z.pos p # 1))))).
apply CReq_sym, CRmorph_mult_int.
apply (CReq_trans
_ (CRmult R1 x (CRmult R1 (CR_of_Q R1 (1 # p))
(CR_of_Q R1 (Z.pos p # 1))))).
apply CReq_sym, Rmul_assoc.
apply (CReq_trans _ (CRmult R1 x 1)).
apply (Rmul_ext (CRisRingExt R1)).
apply (CReq_trans _ (CR_of_Q R1 ((1#p) * (Z.pos p # 1)))).
apply CReq_sym, CR_of_Q_mult.
apply (CReq_trans _ (CR_of_Q R1 1)).
apply (CReq_trans
_ (CRmult R2 (CRmorph f x)
(CRmult R2 (CR_of_Q R2 (1 # p)) (CR_of_Q R2 (Z.pos p # 1))))).
2: apply (Rmul_assoc (CRisRing R2)).
apply (CReq_trans _ (CRmult R2 (CRmorph f x) 1)).
apply CReq_sym, CRmult_1_r.
apply (Rmul_ext (CRisRingExt R2)).
apply (CReq_trans _ (CR_of_Q R2 1)).
apply (CReq_trans _ (CR_of_Q R2 ((1#p)*(Z.pos p # 1)))).
Lemma CRmorph_mult_rat : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1) (q : Q),
CRmorph f (CRmult R1 x (CR_of_Q R1 q))
== CRmult R2 (CRmorph f x) (CR_of_Q R2 q).
apply (CReq_trans
_ (CRmult R2 (CRmorph f (CRmult R1 x (CR_of_Q R1 (a # 1))))
(CR_of_Q R2 (1 # b)))).
apply (CReq_trans
_ (CRmorph f (CRmult R1 (CRmult R1 x (CR_of_Q R1 (a # 1)))
(CR_of_Q R1 (1 # b))))).
2: apply CRmorph_mult_inv.
apply (CReq_trans
_ (CRmult R1 x (CRmult R1 (CR_of_Q R1 (a # 1))
(CR_of_Q R1 (1 # b))))).
apply (Rmul_ext (CRisRingExt R1)).
apply (CReq_trans _ (CR_of_Q R1 ((a#1)*(1#b)))).
apply (Rmul_assoc (CRisRing R1)).
apply (CReq_trans
_ (CRmult R2 (CRmult R2 (CRmorph f x) (CR_of_Q R2 (a # 1)))
(CR_of_Q R2 (1 # b)))).
apply (Rmul_ext (CRisRingExt R2)).
apply (CReq_trans
_ (CRmult R2 (CRmorph f x)
(CRmult R2 (CR_of_Q R2 (a # 1)) (CR_of_Q R2 (1 # b))))).
apply CReq_sym, (Rmul_assoc (CRisRing R2)).
apply (Rmul_ext (CRisRingExt R2)).
apply (CReq_trans _ (CR_of_Q R2 ((a#1)*(1#b)))).
apply CReq_sym, CR_of_Q_mult.
Lemma CRmorph_mult_pos_pos_le : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x y : CRcarrier R1),
CRlt R1 0 y
-> CRmult R2 (CRmorph f x) (CRmorph f y)
<= CRmorph f (CRmult R1 x y).
destruct (CR_Q_dense R2 _ _ abs) as [q [H1 H2]].
destruct (CRmorph_rat f q) as [H3 _].
apply (CRlt_le_trans _ _ _ H1) in H3.
apply CRmorph_increasing_inv in H3.
apply (CRlt_asym _ _ H3).
destruct (CR_Q_dense R2 _ _ H2) as [r [H1 H3]].
destruct (CR_archimedean R1 y) as [A Amaj].
assert (/ ((r - q) * (1 # A)) * (q - r) == - (Z.pos A # 1))%Q as diveq.
setoid_replace (q-r)%Q with (-1*(r-q))%Q.
apply Qlt_minus_iff in H1.
destruct (CR_Q_dense R1 (CRplus R1 x (CR_of_Q R1 ((q-r) * (1#A)))) x)
as [s [H4 H5]].
apply (CRlt_le_trans _ (CRplus R1 x 0)).
apply CRplus_lt_compat_l.
apply (CRplus_lt_reg_l R1 (CR_of_Q R1 ((r-q) * (1#A)))).
apply (CRle_lt_trans _ 0).
1:apply (CRle_trans _ (CR_of_Q R1 ((r-q)*(1#A) + (q-r)*(1#A)))).
destruct (CR_of_Q_plus R1 ((r-q)*(1#A)) ((q-r)*(1#A))).
apply (CRle_trans _ (CR_of_Q R1 0)).
apply (CRlt_le_trans _ (CR_of_Q R1 ((r - q) * (1 # A)))).
apply (CRle_lt_trans _ (CR_of_Q R1 0)).
rewrite <- (Qmult_0_r (r-q)).
apply Qlt_minus_iff in H1.
apply (CRmorph_increasing f) in H4.
destruct (CRmorph_plus f x (CR_of_Q R1 ((q-r) * (1#A)))) as [H6 _].
apply (CRle_lt_trans _ _ _ H6) in H4.
destruct (CRmorph_rat f s) as [_ H6].
apply (CRlt_le_trans _ _ _ H4) in H6.
apply (CRmult_lt_compat_r (CRmorph f y)) in H6.
destruct (Rdistr_l (CRisRing R2) (CRmorph f x)
(CRmorph f (CR_of_Q R1 ((q-r) * (1#A))))
(CRmorph f y)) as [H4 _].
apply (CRle_lt_trans _ _ _ H4) in H6.
apply (CRle_lt_trans _ (CRmult R1 (CR_of_Q R1 s) y)).
apply CRmult_lt_compat_r.
apply (CRmorph_le_inv f).
apply (CRle_trans _ (CR_of_Q R2 q)).
destruct (CRmorph_rat f q).
apply (CRle_trans _ (CRmult R2 (CR_of_Q R2 s) (CRmorph f y))).
1:apply (CRle_trans _ (CRplus R2 (CRmult R2 (CRmorph f x) (CRmorph f y))
(CR_of_Q R2 (q-r)))).
1:apply (CRle_trans _ (CRplus R2 (CR_of_Q R2 r) (CR_of_Q R2 (q - r)))).
apply (CRle_trans _ (CR_of_Q R2 (r + (q-r)))).
exact (Qlt_not_le q q H4 (Qle_refl q)).
destruct (CR_of_Q_plus R2 r (q-r)).
apply CRplus_le_compat_r.
apply (CRlt_asym _ _ H3).
apply (CRlt_asym _ _ H4).
apply (CRlt_trans_flip _ _ _ H6).
apply CRplus_lt_compat_l.
apply (CRlt_le_trans
_ (CRmult R2 (CR_of_Q R2 ((q - r) * (1 # A))) (CRmorph f y))).
apply (CRmult_lt_reg_l (CR_of_Q R2 (/((r-q)*(1#A))))).
1:apply (CRle_lt_trans _ (CR_of_Q R2 0)).
apply CR_of_Q_lt, Qinv_lt_0_compat.
rewrite <- (Qmult_0_r (r-q)).
apply Qlt_minus_iff in H1.
apply (CRle_lt_trans _ (CRopp R2 (CR_of_Q R2 (Z.pos A # 1)))).
1:apply (CRle_trans _ (CR_of_Q R2 (-(Z.pos A # 1)))).
1:apply (CRle_trans _ (CR_of_Q R2 ((/ ((r - q) * (1 # A))) * (q - r)))).
destruct (CR_of_Q_mult R2 (/ ((r - q) * (1 # A))) (q - r)).
destruct (CR_of_Q_morph R2 (/ ((r - q) * (1 # A)) * (q - r))
(-(Z.pos A # 1))).
exact (Qlt_not_le _ _ H7 (Qle_refl _)).
destruct (@CR_of_Q_opp R2 (Z.pos A # 1)).
apply (CRlt_le_trans _ (CRopp R2 (CRmorph f y))).
apply CRopp_gt_lt_contravar.
apply (CRlt_le_trans _ (CRmorph f (CR_of_Q R1 (Z.pos A # 1)))).
apply CRmorph_increasing.
destruct (CRmorph_rat f (Z.pos A # 1)).
apply (CRle_trans _ (CRmult R2 (CRopp R2 1) (CRmorph f y))).
1:apply (CRle_trans _ (CRopp R2 (CRmult R2 1 (CRmorph f y)))).
destruct (Ropp_ext (CRisRingExt R2) (CRmorph f y)
(CRmult R2 1 (CRmorph f y))).
apply CReq_sym, (Rmul_1_l (CRisRing R2)).
destruct (CRopp_mult_distr_l 1 (CRmorph f y)).
apply (CRle_trans _ (CRmult R2 (CRmult R2 (CR_of_Q R2 (/ ((r - q) * (1 # A))))
(CR_of_Q R2 ((q - r) * (1 # A))))
(CRmorph f y))).
apply CRmult_le_compat_r_half.
apply (CRle_lt_trans _ (CRmorph f 0)).
apply CRmorph_increasing.
apply (CRle_trans _ (CR_of_Q R2 ((/ ((r - q) * (1 # A)))
* ((q - r) * (1 # A))))).
1:apply (CRle_trans _ (CR_of_Q R2 (-1))).
1:apply (CRle_trans _ (CRopp R2 (CR_of_Q R2 1))).
destruct (Ropp_ext (CRisRingExt R2) 1 (CR_of_Q R2 1)).
destruct (@CR_of_Q_opp R2 1).
destruct (CR_of_Q_morph R2 (-1) (/ ((r - q) * (1 # A)) * ((q - r) * (1 # A)))).
apply Qlt_minus_iff in H1.
destruct (CR_of_Q_mult R2 (/ ((r - q) * (1 # A))) ((q - r) * (1 # A))).
destruct (Rmul_assoc (CRisRing R2) (CR_of_Q R2 (/ ((r - q) * (1 # A))))
(CR_of_Q R2 ((q - r) * (1 # A)))
(CRmorph f y)).
apply CRmult_le_compat_r_half.
apply (CRle_lt_trans _ (CRmorph f 0)).
apply CRmorph_increasing.
destruct (CRmorph_rat f ((q - r) * (1 # A))).
apply (CRle_trans _ (CRmorph f (CRmult R1 y (CR_of_Q R1 s)))).
1:apply (CRle_trans _ (CRmult R2 (CRmorph f y) (CR_of_Q R2 s))).
destruct (Rmul_comm (CRisRing R2) (CRmorph f y) (CR_of_Q R2 s)).
destruct (CRmorph_mult_rat f y s).
destruct (CRmorph_proper f (CRmult R1 y (CR_of_Q R1 s))
(CRmult R1 (CR_of_Q R1 s) y)).
apply (Rmul_comm (CRisRing R1)).
apply (CRle_lt_trans _ (CRmorph f 0)).
apply CRmorph_increasing.
Lemma CRmorph_mult_pos_pos : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x y : CRcarrier R1),
CRlt R1 0 y
-> CRmorph f (CRmult R1 x y)
== CRmult R2 (CRmorph f x) (CRmorph f y).
apply CRmorph_mult_pos_pos_le.
destruct (CR_Q_dense R2 _ _ abs) as [q [H1 H2]].
destruct (CRmorph_rat f q) as [_ H3].
apply (CRle_lt_trans _ _ _ H3) in H2.
apply CRmorph_increasing_inv in H2.
apply (CRlt_asym _ _ H2).
destruct (CR_Q_dense R2 _ _ H1) as [r [H2 H3]].
destruct (CR_archimedean R1 y) as [A Amaj].
destruct (CR_Q_dense R1 x (CRplus R1 x (CR_of_Q R1 ((q-r) * (1#A)))))
as [s [H4 H5]].
apply (CRle_lt_trans _ (CRplus R1 x 0)).
apply CRplus_lt_compat_l.
apply (CRle_lt_trans _ (CR_of_Q R1 0)).
rewrite <- (Qmult_0_r (q-r)).
apply Qlt_minus_iff in H3.
apply (CRmorph_increasing f) in H5.
destruct (CRmorph_plus f x (CR_of_Q R1 ((q-r) * (1#A)))) as [_ H6].
apply (CRlt_le_trans _ _ _ H5) in H6.
destruct (CRmorph_rat f s) as [H5 _ ].
apply (CRle_lt_trans _ _ _ H5) in H6.
apply (CRmult_lt_compat_r (CRmorph f y)) in H6.
apply (CRle_lt_trans _ (CRmorph f 0)).
apply CRmorph_increasing.
apply (CRlt_le_trans _ (CRmult R1 (CR_of_Q R1 s) y)).
apply CRmult_lt_compat_r.
apply (CRmorph_le_inv f).
apply (CRle_trans _ (CR_of_Q R2 q)).
2: destruct (CRmorph_rat f q); exact H0.
apply (CRle_trans _ (CRmult R2 (CR_of_Q R2 s) (CRmorph f y))).
1:apply (CRle_trans _ (CRmorph f (CRmult R1 y (CR_of_Q R1 s)))).
destruct (CRmorph_proper f (CRmult R1 (CR_of_Q R1 s) y)
(CRmult R1 y (CR_of_Q R1 s))).
apply (Rmul_comm (CRisRing R1)).
apply (CRle_trans _ (CRmult R2 (CRmorph f y) (CR_of_Q R2 s))).
exact (proj2 (CRmorph_mult_rat f y s)).
destruct (Rmul_comm (CRisRing R2) (CR_of_Q R2 s) (CRmorph f y)).
apply (CRlt_asym _ _ H5).
apply (CRlt_trans _ _ _ H6).
apply (CRle_lt_trans
_ (CRplus R2
(CRmult R2 (CRmorph f x) (CRmorph f y))
(CRmult R2 (CRmorph f (CR_of_Q R1 ((q - r) * (1 # A))))
(CRmorph f y)))).
apply (Rdistr_l (CRisRing R2)).
apply (CRle_lt_trans
_ (CRplus R2 (CR_of_Q R2 r)
(CRmult R2 (CRmorph f (CR_of_Q R1 ((q - r) * (1 # A))))
(CRmorph f y)))).
apply CRplus_le_compat_r.
apply (CRlt_asym _ _ H5 H2).
apply (CRle_lt_trans
_ (CRplus R2 (CR_of_Q R2 r)
(CRmult R2 (CR_of_Q R2 ((q - r) * (1 # A)))
(CRmorph f y)))).
apply CRplus_le_compat_l, CRmult_le_compat_r_half.
apply (CRle_lt_trans _ (CRmorph f 0)).
apply CRmorph_increasing.
destruct (CRmorph_rat f ((q - r) * (1 # A))).
apply (CRlt_le_trans _ (CRplus R2 (CR_of_Q R2 r)
(CR_of_Q R2 ((q - r))))).
apply CRplus_lt_compat_l.
apply (CRmult_lt_reg_l (CR_of_Q R2 (/((q - r) * (1 # A))))).
apply (CRle_lt_trans _ (CR_of_Q R2 0)).
apply CR_of_Q_lt, Qinv_lt_0_compat.
rewrite <- (Qmult_0_r (q-r)).
apply Qlt_minus_iff in H3.
apply (CRle_lt_trans _ (CRmorph f y)).
apply (CRle_trans _ (CRmult R2 (CRmult R2 (CR_of_Q R2 (/ ((q - r) * (1 # A))))
(CR_of_Q R2 ((q - r) * (1 # A))))
(CRmorph f y))).
exact (proj2 (Rmul_assoc (CRisRing R2) (CR_of_Q R2 (/ ((q - r) * (1 # A))))
(CR_of_Q R2 ((q - r) * (1 # A)))
(CRmorph f y))).
apply (CRle_trans _ (CRmult R2 1 (CRmorph f y))).
apply CRmult_le_compat_r_half.
apply (CRle_lt_trans _ (CRmorph f 0)).
apply CRmorph_increasing.
apply (CRle_trans
_ (CR_of_Q R2 ((/ ((q - r) * (1 # A))) * ((q - r) * (1 # A))))).
exact (proj1 (CR_of_Q_mult R2 (/ ((q - r) * (1 # A))) ((q - r) * (1 # A)))).
apply (CRle_trans _ (CR_of_Q R2 1)).
destruct (CR_of_Q_morph R2 (/ ((q - r) * (1 # A)) * ((q - r) * (1 # A))) 1).
apply Qlt_minus_iff in H3.
destruct (Rmul_1_l (CRisRing R2) (CRmorph f y)).
apply (CRlt_le_trans _ (CR_of_Q R2 (Z.pos A # 1))).
1:apply (CRlt_le_trans _ (CRmorph f (CR_of_Q R1 (Z.pos A # 1)))).
apply CRmorph_increasing.
exact (proj2 (CRmorph_rat f (Z.pos A # 1))).
apply (CRle_trans _ (CR_of_Q R2 ((/ ((q - r) * (1 # A))) * (q - r)))).
2: exact (proj2 (CR_of_Q_mult R2 (/ ((q - r) * (1 # A))) (q - r))).
destruct (CR_of_Q_morph R2 (Z.pos A # 1) (/ ((q - r) * (1 # A)) * (q - r))).
apply Qlt_minus_iff in H3.
apply (CRle_trans _ (CR_of_Q R2 (r + (q-r)))).
exact (proj1 (CR_of_Q_plus R2 r (q-r))).
destruct (CR_of_Q_morph R2 (r + (q-r)) q).
Lemma CRmorph_mult : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x y : CRcarrier R1),
CRmorph f (CRmult R1 x y)
== CRmult R2 (CRmorph f x) (CRmorph f y).
destruct (CR_archimedean R1 (CRopp R1 y)) as [p pmaj].
apply (CRplus_eq_reg_r (CRmult R2 (CRmorph f x)
(CR_of_Q R2 (Z.pos p # 1)))).
apply (CReq_trans _ (CRmorph f (CRmult R1 x (CRplus R1 y (CR_of_Q R1 (Z.pos p # 1)))))).
apply (CReq_trans _ (CRplus R2 (CRmorph f (CRmult R1 x y))
(CRmorph f (CRmult R1 x (CR_of_Q R1 (Z.pos p # 1)))))).
apply (Radd_ext (CRisRingExt R2)).
apply CReq_sym, CRmorph_mult_int.
apply (CReq_trans _ (CRmorph f (CRplus R1 (CRmult R1 x y)
(CRmult R1 x (CR_of_Q R1 (Z.pos p # 1)))))).
apply CReq_sym, CRmorph_plus.
apply CReq_sym, CRmult_plus_distr_l.
apply (CReq_trans _ (CRmult R2 (CRmorph f x)
(CRmorph f (CRplus R1 y (CR_of_Q R1 (Z.pos p # 1)))))).
apply CRmorph_mult_pos_pos.
apply (CRplus_lt_compat_l R1 y) in pmaj.
apply (CRle_lt_trans _ (CRplus R1 y (CRopp R1 y))).
apply (CReq_trans _ (CRmult R2 (CRmorph f x)
(CRplus R2 (CRmorph f y) (CR_of_Q R2 (Z.pos p # 1))))).
apply (Rmul_ext (CRisRingExt R2)).
apply (CReq_trans _ (CRplus R2 (CRmorph f y)
(CRmorph f (CR_of_Q R1 (Z.pos p # 1))))).
apply (Radd_ext (CRisRingExt R2)).
apply CRmult_plus_distr_l.
Lemma CRmorph_appart : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x y : CRcarrier R1)
(app : x ≶ y),
CRmorph f x ≶ CRmorph f y.
apply CRmorph_increasing.
apply CRmorph_increasing.
Lemma CRmorph_appart_zero : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1)
(app : x ≶ 0),
CRmorph f x ≶ 0.
apply (CRlt_le_trans _ (CRmorph f 0)).
apply CRmorph_increasing.
exact (proj2 (CRmorph_zero f)).
apply (CRle_lt_trans _ (CRmorph f 0)).
exact (proj1 (CRmorph_zero f)).
apply CRmorph_increasing.
Lemma CRmorph_inv : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1)
(xnz : x ≶ 0)
(fxnz : CRmorph f x ≶ 0),
CRmorph f ((/ x) xnz)
== (/ CRmorph f x) fxnz.
apply (CRmult_eq_reg_r (CRmorph f x)).
2: apply CReq_sym, CRinv_l.
apply (CReq_trans _ (CRmorph f (CRmult R1 ((/ x) xnz) x))).
apply CReq_sym, CRmorph_mult.
apply (CReq_trans _ (CRmorph f 1)).
Lemma CRmorph_rat_cv
: forall {R1 R2 : ConstructiveReals}
(qn : nat -> Q),
CR_cauchy R1 (fun n => CR_of_Q R1 (qn n))
-> CR_cauchy R2 (fun n => CR_of_Q R2 (qn n)).
destruct (H p) as [n nmaj].
specialize (nmaj i j H0 H1).
rewrite <- CR_of_Q_opp, <- CR_of_Q_plus, CR_of_Q_abs.
rewrite <- CR_of_Q_opp, <- CR_of_Q_plus, CR_of_Q_abs in nmaj.
destruct (Q_dec (Qabs (qn i + - qn j)) (1#p)).
apply (Qlt_not_le _ _ q).
apply (CR_of_Q_lt R1) in q.
Definition CR_Q_limit {R : ConstructiveReals} (x : CRcarrier R) (n:nat)
: { q:Q & x < CR_of_Q R q < x + CR_of_Q R (1 # Pos.of_nat n) }.
apply (CR_Q_dense R x (x + CR_of_Q R (1 # Pos.of_nat n))).
rewrite <- (CRplus_0_r x).
apply CRplus_lt_compat_l.
Lemma CR_Q_limit_cv : forall {R : ConstructiveReals} (x : CRcarrier R),
CR_cv R (fun n => CR_of_Q R (let (q,_) := CR_Q_limit x n in q)) x.
destruct (CR_Q_limit x i).
apply (CRplus_le_reg_r x).
rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_comm.
apply (CRle_trans _ (x + CR_of_Q R (1 # Pos.of_nat i))).
apply CRplus_le_compat_l, CR_of_Q_le.
rewrite Z.mul_1_l, Z.mul_1_l.
apply Pos2Z.pos_le_pos, Pos2Nat.inj_le.
pose proof (Pos2Nat.is_pos p).
rewrite <- (CRplus_opp_r x).
apply CRplus_le_compat_r, CRlt_asym, p0.
(* We call this morphism slow to remind that it should only be used
for proofs, not for computations. *)
Definition SlowMorph {R1 R2 : ConstructiveReals}
: CRcarrier R1 -> CRcarrier R2
:= fun x => let (y,_) := CR_complete R2 _ (CRmorph_rat_cv _ (Rcv_cauchy_mod _ x (CR_Q_limit_cv x)))
in y.
Lemma CauchyMorph_rat : forall {R1 R2 : ConstructiveReals} (q : Q),
SlowMorph (CR_of_Q R1 q) == CR_of_Q R2 q.
destruct (CR_complete R2 _
(CRmorph_rat_cv _
(Rcv_cauchy_mod
(fun n : nat => CR_of_Q R1 (let (q0, _) := CR_Q_limit (CR_of_Q R1 q) n in q0))
(CR_of_Q R1 q) (CR_Q_limit_cv (CR_of_Q R1 q))))).
apply (CR_cv_unique _ _ _ c).
destruct (CR_Q_limit (CR_of_Q R1 q) i).
apply (CRplus_le_reg_r (CR_of_Q R2 q)).
rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_comm.
destruct (Q_dec x0 (q + (1 # p))%Q).
pose proof (CR_of_Q_lt R1 _ _ q0).
apply (CRlt_asym _ _ H0).
apply (CRlt_le_trans _ _ _ (snd p0)).
rewrite Z.mul_1_l, Z.mul_1_l.
apply Pos2Z.pos_le_pos, Pos2Nat.inj_le.
pose proof (Pos2Nat.is_pos p).
rewrite <- (CRplus_opp_r (CR_of_Q R2 q)).
apply CRplus_le_compat_r, CR_of_Q_le.
apply (CRlt_asym _ _ (fst p0)).
(* The increasing property of morphisms, when the left bound is rational. *)
Lemma SlowMorph_increasing_Qr
: forall {R1 R2 : ConstructiveReals} (x : CRcarrier R1) (q : Q),
CR_of_Q R1 q < x -> CR_of_Q R2 q < SlowMorph x.
unfold SlowMorph;
destruct (CR_complete R2 _
(CRmorph_rat_cv _
(Rcv_cauchy_mod (fun n : nat => CR_of_Q R1 (let (q0, _) := CR_Q_limit x n in q0)) x
(CR_Q_limit_cv x)))).
destruct (CR_Q_dense R1 _ _ H) as [r [H0 H1]].
apply (CRlt_le_trans _ (CR_of_Q R2 r)).
assert (forall n:nat, le O n -> CR_of_Q R2 r <= CR_of_Q R2 (let (q0, _) := CR_Q_limit x n in q0)).
destruct (CR_Q_limit x n).
apply (CR_of_Q_lt R1) in q0.
apply (CRlt_asym _ _ q0).
exact (CRlt_trans _ _ _ H1 (fst p)).
exact (CR_cv_bound_down _ _ _ O H2 c).
(* The increasing property of morphisms, when the right bound is rational. *)
Lemma SlowMorph_increasing_Ql
: forall {R1 R2 : ConstructiveReals} (x : CRcarrier R1) (q : Q),
x < CR_of_Q R1 q -> SlowMorph x < CR_of_Q R2 q.
unfold SlowMorph;
destruct (CR_complete R2 _
(CRmorph_rat_cv _
(Rcv_cauchy_mod (fun n : nat => CR_of_Q R1 (let (q0, _) := CR_Q_limit x n in q0)) x
(CR_Q_limit_cv x)))).
assert (CR_cv R1 (fun n => CR_of_Q R1 (let (q0, _) := CR_Q_limit x n in q0)
+ CR_of_Q R1 (1 # Pos.of_nat n)) x).
apply (CR_cv_proper _ (x+0)).
rewrite CRopp_0, CRplus_0_r.
apply Pos2Z.pos_le_pos, Pos2Nat.inj_le.
pose proof (Pos2Nat.is_pos p).
pose proof (CR_cv_open_above _ _ _ H0 H) as [n nmaj].
apply (CRle_lt_trans _ (CR_of_Q R2 (let (q0, _) := CR_Q_limit x n in
q0 + (1 # Pos.of_nat n)))).
apply (CR_cv_bound_up (fun n : nat => CR_of_Q R2 (let (q0, _) := CR_Q_limit x n in q0)) _ _ n).
destruct (CR_Q_limit x n0), (CR_Q_limit x n).
apply CR_of_Q_le, Qlt_le_weak.
apply (CRlt_le_trans _ _ _ (snd p)).
apply (CRle_trans _ (CR_of_Q R1 x2 + CR_of_Q R1 (1 # Pos.of_nat n0))).
apply CRplus_le_compat_r.
apply Pos2Z.pos_le_pos, Pos2Nat.inj_le.
rewrite (Nat2Pos.id (S n0)).
apply -> Nat.succ_le_mono; apply Nat.le_0_l.
rewrite Nat2Pos.id, Nat2Pos.id.
specialize (nmaj n (Nat.le_refl n)).
destruct (CR_Q_limit x n).
rewrite <- CR_of_Q_plus in nmaj.
apply lt_CR_of_Q in nmaj.
Lemma SlowMorph_increasing : forall {R1 R2 : ConstructiveReals} (x y : CRcarrier R1),
x < y -> @SlowMorph R1 R2 x < SlowMorph y.
destruct (CR_Q_dense R1 _ _ H) as [q [H0 H1]].
apply (CRlt_trans _ (CR_of_Q R2 q)).
apply SlowMorph_increasing_Ql.
apply SlowMorph_increasing_Qr.
(* We call this morphism slow to remind that it should only be used
for proofs, not for computations. *)
Definition SlowConstructiveRealsMorphism {R1 R2 : ConstructiveReals}
: @ConstructiveRealsMorphism R1 R2
:= Build_ConstructiveRealsMorphism
R1 R2 SlowMorph CauchyMorph_rat
SlowMorph_increasing.
Lemma CRmorph_abs : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1),
CRabs R2 (CRmorph f x) == CRmorph f (CRabs R1 x).
assert (forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(x : CRcarrier R1),
CRabs R2 (CRmorph f x) <= CRmorph f (CRabs R1 x)).
pose proof (CRabs_def _ x (CRabs R1 x)) as [_ H].
apply (CRle_trans _ (CRmorph f (CRopp R1 x))).
pose proof (CRabs_def _ x (CRabs R1 x)) as [_ H].
apply (CRmorph_le_inv (@SlowConstructiveRealsMorphism R2 R1)).
apply (CRle_trans _ (CRabs R1 x)).
apply (Endomorph_id
(CRmorph_compose f (@SlowConstructiveRealsMorphism R2 R1))).
apply (CRle_trans
_ (CRabs R1 (CRmorph (@SlowConstructiveRealsMorphism R2 R1) (CRmorph f x)))).
apply CReq_sym, (Endomorph_id
(CRmorph_compose f (@SlowConstructiveRealsMorphism R2 R1))).
Lemma CRmorph_cv : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(un : nat -> CRcarrier R1)
(l : CRcarrier R1),
CR_cv R1 un l
-> CR_cv R2 (fun n => CRmorph f (un n)) (CRmorph f l).
specialize (H p) as [n H].
rewrite <- CRmorph_opp, <- CRmorph_plus, CRmorph_abs.
rewrite <- (CRmorph_rat f (1#p)).
Lemma CRmorph_cauchy_reverse : forall {R1 R2 : ConstructiveReals}
(f : @ConstructiveRealsMorphism R1 R2)
(un : nat -> CRcarrier R1),
CR_cauchy R2 (fun n => CRmorph f (un n))
-> CR_cauchy R1 un.
specialize (H p) as [n H].
specialize (H i j H0 H1).
rewrite <- CRmorph_opp, <- CRmorph_plus, CRmorph_abs in H.
rewrite <- (CRmorph_rat f (1#p)) in H.
apply (CRmorph_le_inv f) in H.