Debian Codegraph @

reals/faster/AQmetric.v

raw
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.