| 1 |
Require Import CoRN.metric2.Metric. |
| 2 |
Require Import CoRN.metric2.UniformContinuity. |
| 3 |
From Coq Require Import Program Ring. |
| 4 |
Require Import CoRN.util.Qdlog |
| 5 |
CoRN.model.totalorder.QposMinMax |
| 6 |
CoRN.metric2.Complete CoRN.metric2.Prelength CoRN.model.metric2.Qmetric CoRN.model.metric2.CRmetric CoRN.metric2.MetricMorphisms. |
| 7 |
Require Export |
| 8 |
CoRN.reals.faster.ApproximateRationals. |
| 9 |
|
| 10 |
Section AQmetric. |
| 11 |
Context `{AppRationals AQ}. |
| 12 |
|
| 13 |
Add Ring AQ : (rings.stdlib_ring_theory AQ). |
| 14 |
|
| 15 |
Local Open Scope uc_scope. |
| 16 |
|
| 17 |
(* To ensure the definitions below don't use sg_setoid instead *) |
| 18 |
Existing Instance strong_setoids.Setoid_instance_0. |
| 19 |
Definition AQ_as_MetricSpace := Emetric (cast AQ Q_as_MetricSpace). |
| 20 |
Definition AQPrelengthSpace := EPrelengthSpace QPrelengthSpace (cast AQ Q_as_MetricSpace). |
| 21 |
Definition AQLocated : locatedMetric AQ_as_MetricSpace. |
| 22 |
Proof. |
| 23 |
intros e1 e2 x y lte. |
| 24 |
apply (@locatedQ e1 e2 (AQtoQ x) (AQtoQ y) lte). |
| 25 |
Defined. |
| 26 |
|
| 27 |
Definition AR := Complete AQ_as_MetricSpace. |
| 28 |
|
| 29 |
Definition AQtoQ_uc : AQ_as_MetricSpace --> Q_as_MetricSpace := metric_embed_uc (cast AQ Q_as_MetricSpace). |
| 30 |
|
| 31 |
Definition ARtoCR_uc : AR --> CR := Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace). |
| 32 |
Global Instance ARtoCR: Cast AR CR := ARtoCR_uc. |
| 33 |
Definition CRtoAR_uc : CR --> AR := Eembed_inverse QPrelengthSpace (cast AQ Q_as_MetricSpace). |
| 34 |
Global Instance CRtoAR: Cast CR AR := CRtoAR_uc. |
| 35 |
|
| 36 |
Global Instance inject_AQ_AR: Cast AQ AR := (@Cunit AQ_as_MetricSpace). |
| 37 |
Global Instance: Proper ((=) ==> (@msp_eq _)) inject_AQ_AR. |
| 38 |
Proof. |
| 39 |
intros x y xyeq. |
| 40 |
apply (uc_wd (@Cunit AQ_as_MetricSpace)). |
| 41 |
simpl. |
| 42 |
rewrite xyeq. reflexivity. |
| 43 |
Qed. |
| 44 |
|
| 45 |
Lemma ARtoCR_approx : forall (d : QposInf) (x : AR), |
| 46 |
approximate (ARtoCR x) d ≡ AQtoQ (approximate x d). |
| 47 |
Proof. intros. destruct d; reflexivity. Qed. |
| 48 |
|
| 49 |
Lemma inject_Q_AR_prf : |
| 50 |
forall (q:Q), is_RegularFunction (@ball AQ_as_MetricSpace) |
| 51 |
(fun e:QposInf => |
| 52 |
match e with |
| 53 |
| Qpos2QposInf d => app_inverse (cast AQ Q) q d |
| 54 |
| QposInfinity => 0 |
| 55 |
end). |
| 56 |
Proof. |
| 57 |
intros q e1 e2. simpl. |
| 58 |
destruct aq_dense_embedding. |
| 59 |
simpl in dense_inverse. |
| 60 |
unfold cast. |
| 61 |
apply (ball_triangle _ _ _ _ q). |
| 62 |
apply dense_inverse. |
| 63 |
apply ball_sym, dense_inverse. |
| 64 |
Qed. |
| 65 |
|
| 66 |
Definition inject_Q_AR (q : Q) : AR |
| 67 |
:= Build_RegularFunction (inject_Q_AR_prf q). |
| 68 |
|
| 69 |
(* inject_Q_AR is twice faster than the cast *) |
| 70 |
Lemma inject_Q_AR_CR : forall (q : Q), |
| 71 |
inject_Q_AR q = cast CR AR (inject_Q_CR q). |
| 72 |
Proof. |
| 73 |
intro q. |
| 74 |
rewrite <- doubleSpeed_Eq. |
| 75 |
intros e1 e2. |
| 76 |
rewrite Qplus_0_r. |
| 77 |
pose proof (regFun_prf (cast CR AR (inject_Q_CR q)) e1 e2) as H5. |
| 78 |
apply H5. |
| 79 |
Qed. |
| 80 |
|
| 81 |
Lemma inject_Q_AR_uc : is_UniformlyContinuousFunction |
| 82 |
inject_Q_AR Qpos2QposInf. |
| 83 |
Proof. |
| 84 |
intros d e1 e2 bd x y. |
| 85 |
simpl. unfold cast. |
| 86 |
unfold MetricMorphisms.app_inverse. |
| 87 |
destruct aq_dense_embedding. |
| 88 |
unfold MetricMorphisms.app_inverse in dense_inverse. |
| 89 |
rewrite <- (Qplus_assoc (`x) (`d) (`y)). |
| 90 |
apply ball_triangle with (b:=e1). |
| 91 |
apply dense_inverse. |
| 92 |
apply ball_triangle with (b:=e2). |
| 93 |
apply bd. |
| 94 |
apply ball_sym, dense_inverse. |
| 95 |
Qed. |
| 96 |
|
| 97 |
Lemma CRAR_id : forall x : CR, |
| 98 |
msp_eq (cast AR CR (cast CR AR x)) x. |
| 99 |
Proof. |
| 100 |
intro x. |
| 101 |
apply (surjective (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace)) x x). |
| 102 |
reflexivity. |
| 103 |
Qed. |
| 104 |
|
| 105 |
Lemma AQball_fold ε (x y : AQ_as_MetricSpace) : ball ε x y → Qball ε ('x) ('y). |
| 106 |
Proof. easy. Qed. |
| 107 |
|
| 108 |
Lemma AQball_abs (ε : Q) (x y : AQ_as_MetricSpace) : |
| 109 |
ball ε x y ↔ 'abs (x - y) ≤ ε. |
| 110 |
Proof. |
| 111 |
simpl. rewrite Qball_Qabs. |
| 112 |
now rewrite abs.preserves_abs, rings.preserves_minus. |
| 113 |
Qed. |
| 114 |
|
| 115 |
Definition AQball_bool (k : Z) (x y : AQ) : bool |
| 116 |
:= bool_decide_rel (≤) (abs (x - y)) (1 ≪ k). |
| 117 |
|
| 118 |
Lemma AQball_bool_true (k : Z) (x y : AQ_as_MetricSpace) : |
| 119 |
AQball_bool k x y ≡ true ↔ ball (2 ^ k) x y. |
| 120 |
Proof. |
| 121 |
rewrite AQball_abs. |
| 122 |
unfold AQball_bool. rewrite bool_decide_rel_true. |
| 123 |
transitivity ('abs (x - y) ≤ ('(1 ≪ k) : Q)). |
| 124 |
split; intros. |
| 125 |
now apply (order_preserving _). |
| 126 |
now apply (order_reflecting (cast AQ Q)). |
| 127 |
now rewrite aq_shift_correct, rings.preserves_1, left_identity. |
| 128 |
Qed. |
| 129 |
|
| 130 |
Global Instance: Proper ((=) ==> (=) ==> (=) ==> (≡)) AQball_bool | 1. |
| 131 |
Proof. |
| 132 |
intros ε1 ε2 E1 x1 x2 E2 y1 y2 E3. |
| 133 |
case_eq (AQball_bool ε2 x2 y2). |
| 134 |
intro. apply AQball_bool_true. rewrite E1, E2, E3. now apply AQball_bool_true. |
| 135 |
rewrite <-2!not_true_iff_false. intros E4 ?. apply E4. |
| 136 |
apply AQball_bool_true. rewrite <-E1, <-E2, <-E3. now apply AQball_bool_true. |
| 137 |
Qed. |
| 138 |
|
| 139 |
Lemma AQball_bool_true_eps (ε : Qpos) (x y : AQ_as_MetricSpace) : |
| 140 |
AQball_bool (Qdlog2 (proj1_sig ε)) x y ≡ true |
| 141 |
→ ball (proj1_sig ε) x y. |
| 142 |
Proof. |
| 143 |
intros E. |
| 144 |
apply AQball_abs. |
| 145 |
transitivity (2 ^ (Qdlog2 (proj1_sig ε)) : Q). |
| 146 |
apply AQball_bool_true in E. |
| 147 |
now apply AQball_abs in E. |
| 148 |
now apply (Qpos_dlog2_spec ε). |
| 149 |
Qed. |
| 150 |
|
| 151 |
Lemma AQball_plus (ε1 ε2 : Qpos) (x1 x2 y1 y2 : AQ_as_MetricSpace) : |
| 152 |
ball (proj1_sig ε1) x1 y1 |
| 153 |
→ ball (proj1_sig ε2) x2 y2 → ball (proj1_sig ε1 + proj1_sig ε2) (x1 + x2) (y1 + y2). |
| 154 |
Proof. |
| 155 |
intros. |
| 156 |
apply ball_triangle with (x2 + y1); apply AQball_abs. |
| 157 |
setoid_replace (x1 + x2 - (x2 + y1)) with (x1 - y1) by (simpl; ring). |
| 158 |
now apply AQball_abs. |
| 159 |
setoid_replace (x2 + y1 - (y1 + y2)) with (x2 - y2) by (simpl; ring). |
| 160 |
now apply AQball_abs. |
| 161 |
Qed. |
| 162 |
|
| 163 |
Lemma AQball_plus_l (ε : Qpos) (x y z : AQ_as_MetricSpace) : |
| 164 |
ball (proj1_sig ε) x y → ball (proj1_sig ε) (z + x) (z + y). |
| 165 |
Proof. |
| 166 |
intros E. |
| 167 |
apply AQball_abs. |
| 168 |
setoid_replace (z + x - (z + y)) with (x - y) by (simpl; ring). |
| 169 |
now apply AQball_abs. |
| 170 |
Qed. |
| 171 |
|
| 172 |
Lemma AQball_plus_r (ε : Qpos) (x y z : AQ_as_MetricSpace) : |
| 173 |
ball (proj1_sig ε) x y → ball (proj1_sig ε) (x + z) (y + z). |
| 174 |
Proof. |
| 175 |
intros E. |
| 176 |
apply AQball_abs. |
| 177 |
setoid_replace (x + z - (y + z)) with (x - y) by (simpl; ring). |
| 178 |
now apply AQball_abs. |
| 179 |
Qed. |
| 180 |
|
| 181 |
Lemma AQball_opp (ε : Qpos) (x y : AQ_as_MetricSpace) : |
| 182 |
ball (proj1_sig ε) x y → ball (proj1_sig ε) (-x) (-y). |
| 183 |
Proof. |
| 184 |
intros. |
| 185 |
apply AQball_abs. |
| 186 |
setoid_replace (-x - -y) with (y - x) by (simpl; ring). |
| 187 |
apply AQball_abs. |
| 188 |
now apply ball_sym. |
| 189 |
Qed. |
| 190 |
End AQmetric. |