| 1 |
Require Import CoRN.algebra.RSetoid. |
| 2 |
Require Import CoRN.metric2.Metric. |
| 3 |
Require Import CoRN.metric2.UniformContinuity. |
| 4 |
From Coq Require Import Program Ring Qabs. |
| 5 |
Require Import CoRN.stdlib_omissions.Q MathClasses.misc.workaround_tactics |
| 6 |
CoRN.model.totalorder.QMinMax CoRN.model.totalorder.QposMinMax CoRN.util.Qdlog |
| 7 |
CoRN.metric2.Complete CoRN.metric2.Prelength CoRN.model.metric2.Qmetric CoRN.metric2.MetricMorphisms |
| 8 |
CoRN.reals.fast.CRArith CoRN.reals.fast.CRpower |
| 9 |
MathClasses.implementations.stdlib_binary_naturals MathClasses.orders.minmax MathClasses.implementations.positive_semiring_elements. |
| 10 |
Require Export |
| 11 |
CoRN.reals.faster.ApproximateRationals |
| 12 |
CoRN.reals.faster.AQmetric. |
| 13 |
|
| 14 |
Section ARarith. |
| 15 |
Context `{AppRationals AQ}. |
| 16 |
|
| 17 |
Add Ring AQ : (rings.stdlib_ring_theory AQ). |
| 18 |
Add Ring Z : (rings.stdlib_ring_theory Z). |
| 19 |
|
| 20 |
Local Open Scope uc_scope. |
| 21 |
Local Opaque regFunEq. |
| 22 |
|
| 23 |
Hint Rewrite (rings.preserves_0 (f:=cast AQ Q)) : aq_preservation. |
| 24 |
Hint Rewrite (rings.preserves_1 (f:=cast AQ Q)) : aq_preservation. |
| 25 |
Hint Rewrite (rings.preserves_plus (f:=cast AQ Q)) : aq_preservation. |
| 26 |
Hint Rewrite (rings.preserves_mult (f:=cast AQ Q)) : aq_preservation. |
| 27 |
Hint Rewrite (rings.preserves_negate (f:=cast AQ Q)) : aq_preservation. |
| 28 |
Hint Rewrite aq_preserves_max : aq_preservation. |
| 29 |
Hint Rewrite aq_preserves_min : aq_preservation. |
| 30 |
Hint Rewrite (abs.preserves_abs (f:=cast AQ Q)): aq_preservation. |
| 31 |
Ltac aq_preservation := autorewrite with aq_preservation; try reflexivity. |
| 32 |
Local Obligation Tactic := program_simpl; aq_preservation. |
| 33 |
|
| 34 |
(* Compress *) |
| 35 |
Lemma aq_approx_regular_prf (x : AQ) : |
| 36 |
is_RegularFunction_noInf _ (λ ε : Qpos, app_approx x (Qdlog2 (proj1_sig ε)) |
| 37 |
: AQ_as_MetricSpace). |
| 38 |
Proof. |
| 39 |
intros ε1 ε2. simpl. |
| 40 |
eapply ball_triangle. |
| 41 |
apply aq_approx_dlog2. |
| 42 |
apply ball_sym, aq_approx_dlog2. |
| 43 |
Qed. |
| 44 |
|
| 45 |
Definition AQcompress (x : AQ_as_MetricSpace) : AR := |
| 46 |
mkRegularFunction (0 : AQ_as_MetricSpace) (aq_approx_regular_prf x). |
| 47 |
|
| 48 |
Lemma AQcompress_uc_prf : is_UniformlyContinuousFunction AQcompress Qpos2QposInf. |
| 49 |
Proof. |
| 50 |
intros ε x y E δ1 δ2. simpl in *. |
| 51 |
eapply ball_triangle. |
| 52 |
2: apply ball_sym, aq_approx_dlog2. |
| 53 |
eapply ball_triangle; eauto. |
| 54 |
apply aq_approx_dlog2. |
| 55 |
Qed. |
| 56 |
|
| 57 |
Definition AQcompress_uc := Build_UniformlyContinuousFunction AQcompress_uc_prf. |
| 58 |
|
| 59 |
Definition ARcompress : AR --> AR := Cbind AQPrelengthSpace AQcompress_uc. |
| 60 |
|
| 61 |
Lemma ARcompress_correct (x : AR) : ARcompress x = x. |
| 62 |
Proof. |
| 63 |
apply regFunEq_equiv, regFunEq_e. intros ε. |
| 64 |
assert (QposEq (ε + ε) ((1#2) * ε + ((1#2) * ε + ε))) |
| 65 |
by (unfold QposEq; simpl; ring). |
| 66 |
apply (ball_wd _ H5 _ _ (reflexivity _) _ _ (reflexivity _)). clear H5. |
| 67 |
eapply ball_triangle. |
| 68 |
apply_simplified (aq_approx_dlog2 (approximate x ((1 # 2) * ε)%Qpos) ((1#2) * ε)%Qpos). |
| 69 |
apply regFun_prf. |
| 70 |
Qed. |
| 71 |
|
| 72 |
(* Constants *) |
| 73 |
Global Instance inject_PosAQ_AR: Cast (AQ₊) AR := (cast AQ AR ∘ cast (AQ₊) AQ)%prg. |
| 74 |
Global Instance inject_Z_AR: Cast Z AR := (cast AQ AR ∘ cast Z AQ)%prg. |
| 75 |
|
| 76 |
Lemma ARtoCR_inject (x : AQ) : cast AR CR (cast AQ AR x) = cast Q CR (cast AQ Q x). |
| 77 |
Proof. |
| 78 |
apply regFunEq_equiv, regFunEq_e. intros ε. apply ball_refl. |
| 79 |
apply (Qpos_nonneg (ε + ε)). |
| 80 |
Qed. |
| 81 |
|
| 82 |
Global Instance AR0: Zero AR := cast AQ AR 0. |
| 83 |
Lemma ARtoCR_preserves_0 : cast AR CR 0 = 0. |
| 84 |
Proof. unfold "0", AR0. rewrite ARtoCR_inject. aq_preservation. Qed. |
| 85 |
Hint Rewrite ARtoCR_preserves_0 : ARtoCR. |
| 86 |
|
| 87 |
Global Instance AR1: One AR := cast AQ AR 1. |
| 88 |
Lemma ARtoCR_preserves_1 : cast AR CR 1 = 1. |
| 89 |
Proof. unfold "1", AR1. rewrite ARtoCR_inject. aq_preservation. Qed. |
| 90 |
Hint Rewrite ARtoCR_preserves_1 : ARtoCR. |
| 91 |
|
| 92 |
(* Plus *) |
| 93 |
Program Definition AQtranslate_uc (x : AQ_as_MetricSpace) := unary_uc |
| 94 |
(cast AQ Q_as_MetricSpace) |
| 95 |
((x +) : AQ_as_MetricSpace → AQ_as_MetricSpace) (Qtranslate_uc ('x)) _. |
| 96 |
Next Obligation. apply Qball_0. apply preserves_sg_op. Qed. |
| 97 |
|
| 98 |
Definition ARtranslate (x : AQ_as_MetricSpace) : AR --> AR := Cmap AQPrelengthSpace (AQtranslate_uc x). |
| 99 |
|
| 100 |
Lemma ARtoCR_preserves_translate x y : 'ARtranslate x y = translate ('x) ('y). |
| 101 |
Proof. apply preserves_unary_fun. Qed. |
| 102 |
Hint Rewrite ARtoCR_preserves_translate : ARtoCR. |
| 103 |
|
| 104 |
Program Definition AQplus_uc := binary_uc |
| 105 |
(cast AQ Q_as_MetricSpace) |
| 106 |
((+) : AQ_as_MetricSpace → AQ_as_MetricSpace → AQ_as_MetricSpace) Qplus_uc _. |
| 107 |
Next Obligation. apply Qball_0. apply preserves_sg_op. Qed. |
| 108 |
|
| 109 |
Definition ARplus_uc : AR --> AR --> AR := Cmap2 AQPrelengthSpace AQPrelengthSpace AQplus_uc. |
| 110 |
Global Instance ARplus: Plus AR := ucFun2 ARplus_uc. |
| 111 |
|
| 112 |
Lemma ARtoCR_preserves_plus x y : cast AR CR (x + y) = 'x + 'y. |
| 113 |
Proof. apply preserves_binary_fun. Qed. |
| 114 |
Hint Rewrite ARtoCR_preserves_plus : ARtoCR. |
| 115 |
|
| 116 |
(* Inverse *) |
| 117 |
Program Definition AQopp_uc := unary_uc (cast AQ Q_as_MetricSpace) ((-) : AQ → AQ) Qopp_uc _. |
| 118 |
Next Obligation. apply Qball_0. aq_preservation. Qed. |
| 119 |
|
| 120 |
Definition ARopp_uc : AR --> AR := Cmap AQPrelengthSpace AQopp_uc. |
| 121 |
Global Instance ARopp: Negate AR := ARopp_uc. |
| 122 |
|
| 123 |
Lemma ARtoCR_preserves_opp x : cast AR CR (-x) = -'x. |
| 124 |
Proof. apply preserves_unary_fun. Qed. |
| 125 |
Hint Rewrite ARtoCR_preserves_opp : ARtoCR. |
| 126 |
|
| 127 |
(* Mult *) |
| 128 |
Program Definition AQboundBelow_uc (x : AQ_as_MetricSpace) : |
| 129 |
AQ_as_MetricSpace --> AQ_as_MetricSpace := |
| 130 |
unary_uc (cast AQ Q_as_MetricSpace) |
| 131 |
((x ⊔) : AQ_as_MetricSpace → AQ_as_MetricSpace) (QboundBelow_uc ('x)) _. |
| 132 |
Next Obligation. apply Qball_0. aq_preservation. Qed. |
| 133 |
|
| 134 |
Definition ARboundBelow (x : AQ_as_MetricSpace) : AR --> AR := Cmap AQPrelengthSpace (AQboundBelow_uc x). |
| 135 |
|
| 136 |
Lemma ARtoCR_preserves_boundBelow x y : 'ARboundBelow x y = boundBelow ('x) ('y). |
| 137 |
Proof. apply preserves_unary_fun. Qed. |
| 138 |
Hint Rewrite ARtoCR_preserves_boundBelow : ARtoCR. |
| 139 |
|
| 140 |
Program Definition AQboundAbove_uc (x : AQ_as_MetricSpace) : |
| 141 |
AQ_as_MetricSpace --> AQ_as_MetricSpace := unary_uc |
| 142 |
(cast AQ Q_as_MetricSpace) |
| 143 |
((x ⊓) : AQ_as_MetricSpace → AQ_as_MetricSpace) (QboundAbove_uc ('x)) _. |
| 144 |
Next Obligation. apply Qball_0. aq_preservation. Qed. |
| 145 |
|
| 146 |
Definition ARboundAbove (x : AQ_as_MetricSpace) : AR --> AR := Cmap AQPrelengthSpace (AQboundAbove_uc x). |
| 147 |
|
| 148 |
Lemma ARtoCR_preserves_boundAbove x y : 'ARboundAbove x y = boundAbove ('x) ('y). |
| 149 |
Proof. apply preserves_unary_fun. Qed. |
| 150 |
Hint Rewrite ARtoCR_preserves_boundAbove : ARtoCR. |
| 151 |
|
| 152 |
Program Definition AQboundAbs_uc (c : AQ₊) : |
| 153 |
AQ_as_MetricSpace --> AQ_as_MetricSpace := unary_uc |
| 154 |
(cast AQ Q_as_MetricSpace) |
| 155 |
(λ x : AQ_as_MetricSpace, (-'c) ⊔ (('c) ⊓ x) : AQ_as_MetricSpace) (QboundAbs ('c)) _. |
| 156 |
Next Obligation. apply Qball_0. aq_preservation. Qed. |
| 157 |
|
| 158 |
Definition ARboundAbs (c : AQ₊) : AR --> AR := Cmap AQPrelengthSpace (AQboundAbs_uc c). |
| 159 |
|
| 160 |
Lemma ARtoCR_preserves_bound_abs c x : 'ARboundAbs c x = CRboundAbs ('c) ('x). |
| 161 |
Proof. apply preserves_unary_fun. Qed. |
| 162 |
Hint Rewrite ARtoCR_preserves_bound_abs : ARtoCR. |
| 163 |
|
| 164 |
Program Definition AQscale_uc (x : AQ_as_MetricSpace) : |
| 165 |
AQ_as_MetricSpace --> AQ_as_MetricSpace := unary_uc |
| 166 |
(cast AQ Q_as_MetricSpace) |
| 167 |
((x *.) : AQ_as_MetricSpace → AQ_as_MetricSpace) (Qscale_uc ('x)) _. |
| 168 |
Next Obligation. apply Qball_0. aq_preservation. Qed. |
| 169 |
|
| 170 |
Definition ARscale (x : AQ_as_MetricSpace) : AR --> AR := Cmap AQPrelengthSpace (AQscale_uc x). |
| 171 |
|
| 172 |
Lemma ARtoCR_preserves_scale x y : 'ARscale x y = scale ('x) ('y). |
| 173 |
Proof. apply preserves_unary_fun. Qed. |
| 174 |
Hint Rewrite ARtoCR_preserves_scale : ARtoCR. |
| 175 |
|
| 176 |
Program Definition AQmult_uc (c : AQ₊) : |
| 177 |
AQ_as_MetricSpace --> AQ_as_MetricSpace --> AQ_as_MetricSpace := binary_uc |
| 178 |
(cast AQ Q_as_MetricSpace) |
| 179 |
(λ x y : AQ_as_MetricSpace, x * AQboundAbs_uc c y : AQ_as_MetricSpace) (Qmult_uc ('c)) _. |
| 180 |
Next Obligation. apply Qball_0. aq_preservation. Qed. |
| 181 |
|
| 182 |
Definition ARmult_bounded (c : AQ₊) : AR --> AR --> AR |
| 183 |
:= Cmap2 AQPrelengthSpace AQPrelengthSpace (AQmult_uc c). |
| 184 |
|
| 185 |
Lemma ARtoCR_preserves_mult_bounded x y c : |
| 186 |
'ARmult_bounded c x y = CRmult_bounded ('c) ('x) ('y). |
| 187 |
Proof. apply @preserves_binary_fun. Qed. |
| 188 |
Hint Rewrite ARtoCR_preserves_mult_bounded : ARtoCR. |
| 189 |
|
| 190 |
Lemma ARtoCR_approximate (x : AR) (ε : Qpos) : '(approximate x ε) = approximate ('x) ε. |
| 191 |
Proof. reflexivity. Qed. |
| 192 |
|
| 193 |
Lemma AR_b_correct (x : AR) : |
| 194 |
cast AQ Q (abs (approximate x (Qpos2QposInf (1#1))) + 1) = Qabs (approximate (cast AR CR x) (Qpos2QposInf (1#1))) + (1#1). |
| 195 |
Proof. aq_preservation. Qed. |
| 196 |
|
| 197 |
Program Definition AR_b (x : AR) : AQ₊ |
| 198 |
:= exist _ (abs (approximate x (Qpos2QposInf (1#1))) + 1) _. |
| 199 |
Next Obligation. |
| 200 |
apply (strictly_order_reflecting (cast AQ Q)). |
| 201 |
rewrite AR_b_correct. aq_preservation. |
| 202 |
apply CR_b_pos. |
| 203 |
Qed. |
| 204 |
|
| 205 |
Global Instance ARmult: Mult AR := λ x y, ARmult_bounded (AR_b y) x y. |
| 206 |
|
| 207 |
Lemma ARtoCR_preserves_mult x y : cast AR CR (x * y) = 'x * 'y. |
| 208 |
Proof. |
| 209 |
unfold "*", ARmult at 1. rewrite ARtoCR_preserves_mult_bounded. |
| 210 |
assert (QposEq ('AR_b y : Qpos) (CR_b (1 # 1) ('y))). |
| 211 |
{ unfold QposEq. simpl. |
| 212 |
now rewrite ARtoCR_approximate, <-AR_b_correct. } |
| 213 |
apply (CRmult_bounded_wd H5). |
| 214 |
Qed. |
| 215 |
|
| 216 |
Lemma ARmult_scale (x : AQ) (y : AR) : |
| 217 |
'x * y = ARscale x y. |
| 218 |
Proof. |
| 219 |
apply (injective (cast AR CR)). |
| 220 |
rewrite ARtoCR_preserves_mult, ARtoCR_preserves_scale, ARtoCR_inject. |
| 221 |
now apply CRmult_scale. |
| 222 |
Qed. |
| 223 |
|
| 224 |
Hint Rewrite ARtoCR_preserves_mult : ARtoCR. |
| 225 |
|
| 226 |
(* The approximate reals form a ring *) |
| 227 |
Instance ARring: Ring AR. |
| 228 |
Proof. |
| 229 |
apply (rings.projected_ring (cast AR CR)). |
| 230 |
exact ARtoCR_preserves_plus. |
| 231 |
exact ARtoCR_preserves_0. |
| 232 |
exact ARtoCR_preserves_mult. |
| 233 |
exact ARtoCR_preserves_1. |
| 234 |
exact ARtoCR_preserves_opp. |
| 235 |
Qed. |
| 236 |
|
| 237 |
Instance: SemiRing_Morphism (cast AR CR). |
| 238 |
Proof. |
| 239 |
split. apply _. apply _. |
| 240 |
split. apply _. apply _. |
| 241 |
split. apply _. apply _. |
| 242 |
split. apply _. apply _. |
| 243 |
apply _. |
| 244 |
exact ARtoCR_preserves_plus. |
| 245 |
exact ARtoCR_preserves_0. |
| 246 |
split. apply _. apply _. |
| 247 |
split. apply _. apply _. |
| 248 |
split. apply _. apply _. |
| 249 |
apply _. |
| 250 |
exact ARtoCR_preserves_mult. |
| 251 |
exact ARtoCR_preserves_1. |
| 252 |
Qed. |
| 253 |
|
| 254 |
Instance: SemiRing_Morphism (cast CR AR). |
| 255 |
Proof. change (SemiRing_Morphism (inverse (cast AR CR))). split; apply _. Qed. |
| 256 |
|
| 257 |
Instance: SemiRing_Morphism (cast AQ AR). |
| 258 |
Proof. |
| 259 |
split. apply _. apply _. |
| 260 |
split. apply _. apply _. |
| 261 |
split. apply _. apply _. |
| 262 |
split. apply _. apply _. |
| 263 |
apply _. |
| 264 |
intros. apply regFunEq_equiv, regFunEq_e. intros ε. apply ball_refl. |
| 265 |
apply (Qpos_nonneg (ε + ε)). |
| 266 |
apply regFunEq_equiv, regFunEq_e. intros ε. |
| 267 |
apply ball_refl. |
| 268 |
apply (Qpos_nonneg (ε + ε)). |
| 269 |
|
| 270 |
split. apply _. apply _. |
| 271 |
split. apply _. apply _. |
| 272 |
split. apply _. apply _. |
| 273 |
apply _. |
| 274 |
intros. rewrite ARmult_scale. apply regFunEq_equiv, regFunEq_e. intros ε. |
| 275 |
apply ball_refl. |
| 276 |
apply (Qpos_nonneg (ε + ε)). |
| 277 |
apply regFunEq_equiv, regFunEq_e. intros ε. |
| 278 |
apply ball_refl. |
| 279 |
apply (Qpos_nonneg (ε + ε)). |
| 280 |
Qed. |
| 281 |
|
| 282 |
Add Ring CR : (rings.stdlib_ring_theory CR). |
| 283 |
Add Ring AR : (rings.stdlib_ring_theory AR). |
| 284 |
|
| 285 |
Lemma ARplus_comm : forall x y : AR, x + y = y + x. |
| 286 |
Proof. |
| 287 |
intros. ring. |
| 288 |
Qed. |
| 289 |
|
| 290 |
Lemma ARplus_assoc : forall u v w : AR, |
| 291 |
(u + v) + w = u + (v + w). |
| 292 |
Proof. |
| 293 |
intros. ring. |
| 294 |
Qed. |
| 295 |
|
| 296 |
Lemma ARplus_opp_r : |
| 297 |
forall x : AR, x - x = 0. |
| 298 |
Proof. |
| 299 |
intros. ring. |
| 300 |
Qed. |
| 301 |
|
| 302 |
Lemma ARmult_comm : forall x y : AR, x * y = y * x. |
| 303 |
Proof. |
| 304 |
intros. ring. |
| 305 |
Qed. |
| 306 |
|
| 307 |
Lemma ARmult_assoc : forall u v w : AR, |
| 308 |
(u * v) * w = u * (v * w). |
| 309 |
Proof. |
| 310 |
intros. ring. |
| 311 |
Qed. |
| 312 |
|
| 313 |
Lemma ARmult_1_l : forall x : AR, 1 * x = x. |
| 314 |
Proof. |
| 315 |
intros. ring. |
| 316 |
Qed. |
| 317 |
|
| 318 |
Lemma ARmult_1_r : forall x : AR, x * 1 = x. |
| 319 |
Proof. |
| 320 |
intros. ring. |
| 321 |
Qed. |
| 322 |
|
| 323 |
Lemma ARopp_mult_distr_r : forall (r1 r2 : AR), |
| 324 |
- (r1 * r2) = r1 * (- r2). |
| 325 |
Proof. |
| 326 |
intros. ring. |
| 327 |
Qed. |
| 328 |
|
| 329 |
Lemma ARopp_involutive : forall (r1 : AR), - - r1 = r1. |
| 330 |
Proof. |
| 331 |
intros. ring. |
| 332 |
Qed. |
| 333 |
|
| 334 |
Lemma ARplus_0_r : forall x : AR, x + 0 = x. |
| 335 |
Proof. |
| 336 |
intros. ring. |
| 337 |
Qed. |
| 338 |
|
| 339 |
(* Non strict order *) |
| 340 |
Definition ARnonNeg (x : AR) : Prop := ∀ ε : Qpos, -cast Qpos Q ε ≤ cast AQ Q (approximate x ε). |
| 341 |
|
| 342 |
Lemma ARtoCR_preserves_nonNeg x : ARnonNeg x ↔ CRnonNeg ('x). |
| 343 |
Proof. reflexivity. Qed. |
| 344 |
Hint Resolve ARtoCR_preserves_nonNeg. |
| 345 |
|
| 346 |
Global Instance: Proper ((=) ==> iff) ARnonNeg. |
| 347 |
Proof. |
| 348 |
intros x1 x2 E. |
| 349 |
split; intros; apply ARtoCR_preserves_nonNeg; [rewrite <-E | rewrite E]; auto. |
| 350 |
Qed. |
| 351 |
|
| 352 |
Global Instance ARle: Le AR := λ x y, ARnonNeg (y - x). |
| 353 |
|
| 354 |
Global Instance ARle_wd: Proper ((=) ==> (=) ==> iff) ARle. |
| 355 |
Proof. unfold ARle. solve_proper. Qed. |
| 356 |
|
| 357 |
Lemma ARtoCR_preserves_le (x y : AR) : x ≤ y ↔ ' x ≤ ' y. |
| 358 |
Proof. |
| 359 |
unfold le, ARle, CRle. |
| 360 |
now rewrite ARtoCR_preserves_nonNeg, rings.preserves_minus. |
| 361 |
Qed. |
| 362 |
|
| 363 |
Instance: PartialOrder ARle. |
| 364 |
Proof. |
| 365 |
apply (maps.projected_partial_order (cast AR CR)). |
| 366 |
apply ARtoCR_preserves_le. |
| 367 |
Qed. |
| 368 |
|
| 369 |
Lemma ARle_trans : forall x y z : AR, |
| 370 |
ARle x y -> ARle y z -> ARle x z. |
| 371 |
Proof. |
| 372 |
intros. |
| 373 |
apply ARtoCR_preserves_le. |
| 374 |
apply (@CRle_trans _ ('y)). |
| 375 |
apply ARtoCR_preserves_le, H5. |
| 376 |
apply ARtoCR_preserves_le, H6. |
| 377 |
Qed. |
| 378 |
|
| 379 |
Lemma ARsquare_pos : forall x : AR, ARle 0 (x*x). |
| 380 |
Proof. |
| 381 |
intros x. |
| 382 |
apply ARtoCR_preserves_le. |
| 383 |
rewrite ARtoCR_preserves_mult. |
| 384 |
rewrite ARtoCR_preserves_0. |
| 385 |
apply CRsquare_pos. |
| 386 |
Qed. |
| 387 |
|
| 388 |
Lemma ARplus_le_compat_l : |
| 389 |
forall x y z : AR, ARle x y -> ARle (z+x) (z+y). |
| 390 |
Proof. |
| 391 |
intros. apply ARtoCR_preserves_le. |
| 392 |
rewrite ARtoCR_preserves_plus. |
| 393 |
rewrite ARtoCR_preserves_plus. |
| 394 |
apply CRArith.CRplus_le_l. |
| 395 |
apply ARtoCR_preserves_le in H5. |
| 396 |
exact H5. |
| 397 |
Qed. |
| 398 |
|
| 399 |
Lemma ARplus_le_compat_r : |
| 400 |
forall x y z : AR, ARle x y -> ARle (x+z) (y+z). |
| 401 |
Proof. |
| 402 |
intros. apply ARtoCR_preserves_le. |
| 403 |
rewrite ARtoCR_preserves_plus. |
| 404 |
rewrite ARtoCR_preserves_plus. |
| 405 |
apply CRArith.CRplus_le_r. |
| 406 |
apply ARtoCR_preserves_le in H5. |
| 407 |
exact H5. |
| 408 |
Qed. |
| 409 |
|
| 410 |
|
| 411 |
Global Instance: OrderEmbedding ARtoCR. |
| 412 |
Proof. repeat (split; try apply _); apply ARtoCR_preserves_le. Qed. |
| 413 |
|
| 414 |
(* Strict order in Type *) |
| 415 |
Global Instance: OrderEmbedding (cast AQ AR). |
| 416 |
Proof. |
| 417 |
repeat (split; try apply _); intros x y E. |
| 418 |
apply (order_reflecting (cast AR CR)). |
| 419 |
rewrite 2!ARtoCR_inject. |
| 420 |
now do 2 apply (order_preserving _). |
| 421 |
apply (order_reflecting (cast AQ Q)). |
| 422 |
apply (order_reflecting (cast Q CR)). |
| 423 |
rewrite <-2!ARtoCR_inject. |
| 424 |
now apply (order_preserving _). |
| 425 |
Qed. |
| 426 |
|
| 427 |
Definition ARpos (x : AR) : Type := sig (λ y : AQ₊, 'y ≤ x). |
| 428 |
|
| 429 |
Program Definition ARpos_char (ε : AQ₊) (x : AR) |
| 430 |
(Pε : 'ε ≤ approximate x ((1#2) * 'ε)%Qpos) : ARpos x := Pos_shiftl ε (-1 : Z) ↾ _. |
| 431 |
Next Obligation. |
| 432 |
intros δ. |
| 433 |
change (-('δ : Q) ≤ '(approximate x ((1 # 2) * δ)%Qpos - ('ε : AQ) ≪ (-1))). |
| 434 |
transitivity (-'((1 # 2) * δ)%Qpos). |
| 435 |
apply rings.flip_le_negate. |
| 436 |
change ((1 # 2) * proj1_sig δ ≤ proj1_sig δ). |
| 437 |
rewrite <-(rings.mult_1_l (proj1_sig δ)) at 2. |
| 438 |
now apply (order_preserving (.* (proj1_sig δ))). |
| 439 |
apply rings.flip_nonneg_minus. |
| 440 |
transitivity (('approximate x ((1#2) * 'ε)%Qpos - 'ε)%mc : Q). |
| 441 |
apply (order_preserving (cast AQ Q)) in Pε. |
| 442 |
now apply rings.flip_nonneg_minus. |
| 443 |
apply rings.flip_le_minus_l. |
| 444 |
transitivity (((1 # 2) * 'ε + (1 # 2) * proj1_sig δ) |
| 445 |
+ 'approximate x ((1 # 2) * δ)%Qpos). |
| 446 |
apply rings.flip_le_minus_l. |
| 447 |
now destruct (regFun_prf x ((1#2) * 'ε)%Qpos ((1#2) * δ)%Qpos). |
| 448 |
rewrite rings.preserves_minus, aq_shift_opp_1. |
| 449 |
apply orders.eq_le. |
| 450 |
change ((1 # 2) * 'ε + (1 # 2) * proj1_sig δ + 'approximate x ((1 # 2) * δ)%Qpos == |
| 451 |
'approximate x ((1 # 2) * δ)%Qpos - 'ε * (1#2) - - ((1 # 2) * proj1_sig δ) + 'ε)%Q. |
| 452 |
ring. |
| 453 |
Qed. |
| 454 |
|
| 455 |
Lemma ARtoCR_preserves_pos x |
| 456 |
: prod (ARpos x -> CRpos ('x)) |
| 457 |
(CRpos ('x) -> ARpos x). |
| 458 |
Proof with auto with qarith. |
| 459 |
split; intros [y E]. |
| 460 |
exists (cast (AQ₊) (Q₊) y). |
| 461 |
change (cast Q CR (cast AQ Q (cast (AQ₊) AQ y)) ≤ cast AR CR x). |
| 462 |
rewrite <-ARtoCR_inject. |
| 463 |
now apply (order_preserving _). |
| 464 |
destruct (aq_lt_mid 0 (proj1_sig y)) as [z [Ez1 Ez2]]... |
| 465 |
assert (0 < z) as F. |
| 466 |
apply (strictly_order_reflecting (cast AQ Q)). now aq_preservation... |
| 467 |
exists (exist _ z F). simpl. |
| 468 |
change (cast AQ AR (cast (AQ₊) AQ (z ↾ F)) ≤ x). |
| 469 |
apply (order_reflecting (cast AR CR)). |
| 470 |
rewrite ARtoCR_inject. |
| 471 |
transitivity (cast Q CR (cast Qpos Q y)); trivial. |
| 472 |
apply CRle_Qle... |
| 473 |
Defined. |
| 474 |
|
| 475 |
Lemma ARpos_wd : ∀ x1 x2, x1 = x2 → ARpos x1 → ARpos x2. |
| 476 |
Proof. |
| 477 |
intros x1 x2 E G. |
| 478 |
destruct G. exists x. |
| 479 |
rewrite <- E. exact l. |
| 480 |
Defined. |
| 481 |
|
| 482 |
Definition ARltT: AR → AR → Type := λ x y, ARpos (y - x). |
| 483 |
|
| 484 |
Lemma ARtoCR_preserves_ltT x y |
| 485 |
: prod (ARltT x y -> CRltT ('x) ('y)) |
| 486 |
(CRltT ('x) ('y) -> ARltT x y). |
| 487 |
Proof. |
| 488 |
split; intros. |
| 489 |
- apply ARtoCR_preserves_pos in X. |
| 490 |
eapply CRpos_wd; eauto. |
| 491 |
now autorewrite with ARtoCR. |
| 492 |
- apply ARtoCR_preserves_pos. |
| 493 |
eapply CRpos_wd; eauto. |
| 494 |
now autorewrite with ARtoCR. |
| 495 |
Defined. |
| 496 |
|
| 497 |
Lemma CRtoAR_preserves_ltT : forall x y, |
| 498 |
prod (CRltT x y -> ARltT (cast CR AR x) (cast CR AR y)) |
| 499 |
(ARltT (cast CR AR x) (cast CR AR y) -> CRltT x y). |
| 500 |
Proof. |
| 501 |
intros x y. |
| 502 |
pose proof (CRAR_id x) as H6. |
| 503 |
pose proof (CRAR_id y) as H7. |
| 504 |
split. |
| 505 |
- intros. symmetry in H6. symmetry in H7. |
| 506 |
pose proof (CRltT_wd H6 H7 H5). |
| 507 |
apply ARtoCR_preserves_ltT in H8. exact H8. |
| 508 |
- intros H5. |
| 509 |
apply (CRltT_wd H6 H7). |
| 510 |
apply ARtoCR_preserves_ltT. exact H5. |
| 511 |
Qed. |
| 512 |
|
| 513 |
Lemma ARltT_wd : ∀ x1 x2 : AR, x1 = x2 → ∀ y1 y2, y1 = y2 → ARltT x1 y1 → ARltT x2 y2. |
| 514 |
Proof. |
| 515 |
intros x1 x2 E y1 y2 F G. |
| 516 |
apply (ARpos_wd (y1 + - x1)). 2: exact G. |
| 517 |
rewrite E, F. reflexivity. |
| 518 |
Defined. |
| 519 |
|
| 520 |
(* Apartness in Type *) |
| 521 |
Definition ARapartT: AR → AR → Type := λ x y, sum (ARltT x y) (ARltT y x). |
| 522 |
|
| 523 |
Lemma ARapartT_wd : forall x y z t : AR, |
| 524 |
msp_eq x y |
| 525 |
-> msp_eq z t |
| 526 |
-> ARapartT x z |
| 527 |
-> ARapartT y t. |
| 528 |
Proof. |
| 529 |
intros. destruct X. |
| 530 |
- left. apply (ARltT_wd _ _ H5 _ _ H6), a. |
| 531 |
- right. apply (ARltT_wd _ _ H6 _ _ H5), a. |
| 532 |
Defined. |
| 533 |
|
| 534 |
Lemma ARtoCR_preserves_apartT x y |
| 535 |
: prod (ARapartT x y -> CRapartT ('x) ('y)) |
| 536 |
(CRapartT ('x) ('y) -> ARapartT x y). |
| 537 |
Proof. split; (intros [|]; [left|right]; now apply ARtoCR_preserves_ltT). Defined. |
| 538 |
|
| 539 |
Lemma ARtoCR_preserves_apartT_0 x |
| 540 |
: prod (ARapartT x 0 -> CRapartT ('x) 0) |
| 541 |
(CRapartT ('x) 0 -> ARapartT x 0). |
| 542 |
Proof. |
| 543 |
split; intros. |
| 544 |
- apply (@CRapartT_wd ('x)%mc _ (reflexivity _) (cast AR CR 0)). |
| 545 |
apply ARtoCR_preserves_0. |
| 546 |
apply ARtoCR_preserves_apartT, X. |
| 547 |
- apply (@CRapartT_wd ('x)%mc _ (reflexivity _) _ (cast AR CR 0)) in H5. |
| 548 |
apply ARtoCR_preserves_apartT in H5. exact H5. |
| 549 |
symmetry; apply ARtoCR_preserves_0. |
| 550 |
Defined. |
| 551 |
|
| 552 |
(* Strict order in Prop *) |
| 553 |
|
| 554 |
(* Yields Gt if x is certainly greater than 2 ^ k, Lt if x is certainly greater than -2 ^ k, |
| 555 |
Eq otherwise. *) |
| 556 |
Definition AR_epsilon_sign_dec (k : Z) (x : AR) : comparison := |
| 557 |
let ε : AQ₊ := Pos_shiftl 1 k in |
| 558 |
let z : AQ := approximate x ((1#2) * 'ε)%Qpos in |
| 559 |
if decide_rel (≤) ('ε) z |
| 560 |
then Gt |
| 561 |
else if decide_rel (≤) z (-'ε) then Datatypes.Lt else Eq. |
| 562 |
|
| 563 |
Program Definition AR_epsilon_sign_dec_pos (x : AR) |
| 564 |
(k : Z) (Pk : AR_epsilon_sign_dec k x ≡ Gt) : ARpos x := ARpos_char (Pos_shiftl 1 k) x _. |
| 565 |
Next Obligation. |
| 566 |
revert Pk. unfold AR_epsilon_sign_dec. |
| 567 |
case (decide_rel (≤)); [ intros; assumption |]. |
| 568 |
case (decide_rel (≤)); discriminate. |
| 569 |
Qed. |
| 570 |
|
| 571 |
Program Definition AR_epsilon_sign_dec_neg (x : AR) |
| 572 |
(k : Z) (Pk : AR_epsilon_sign_dec k x ≡ Datatypes.Lt) : ARpos (-x) := ARpos_char (Pos_shiftl 1 k) (-x) _. |
| 573 |
Next Obligation. |
| 574 |
revert Pk. unfold AR_epsilon_sign_dec. |
| 575 |
case (decide_rel (≤)); [discriminate |]. |
| 576 |
case (decide_rel (≤)); [| discriminate]. |
| 577 |
intros. apply rings.flip_le_negate. |
| 578 |
now rewrite rings.negate_involutive. |
| 579 |
Qed. |
| 580 |
|
| 581 |
Definition AR_epsilon_sign_dec_apartT (x y : AR) |
| 582 |
(k : Z) (Pk : ¬AR_epsilon_sign_dec k (x - y) ≡ Eq) : ARapartT x y. |
| 583 |
Proof. |
| 584 |
revert Pk. |
| 585 |
case_eq (AR_epsilon_sign_dec k (x - y)); intros E ?. |
| 586 |
now destruct Pk. |
| 587 |
left. apply ARpos_wd with (-(x - y)). |
| 588 |
ring. |
| 589 |
now apply AR_epsilon_sign_dec_neg with k. |
| 590 |
right. now apply AR_epsilon_sign_dec_pos with k. |
| 591 |
Defined. |
| 592 |
|
| 593 |
Lemma AR_epsilon_sign_dec_Gt (k : Z) (x : AR) : |
| 594 |
1 ≪ k ≤ approximate x (Qpos_mult (1#2) ('Pos_shiftl (1:AQ₊) k)) → AR_epsilon_sign_dec k x ≡ Gt. |
| 595 |
Proof. |
| 596 |
intros. |
| 597 |
unfold AR_epsilon_sign_dec. |
| 598 |
case (decide_rel _); intuition. |
| 599 |
Qed. |
| 600 |
|
| 601 |
Lemma AR_epsilon_sign_dec_pos_rev (x : AR) (k : Z) : |
| 602 |
cast AQ AR (1 ≪ (1 + k)) ≤ x → AR_epsilon_sign_dec k x ≡ Gt. |
| 603 |
Proof. |
| 604 |
intros E. |
| 605 |
apply AR_epsilon_sign_dec_Gt. |
| 606 |
apply (order_reflecting (+ -1 ≪ (1 + k))). |
| 607 |
transitivity (-1 ≪ k). |
| 608 |
apply orders.eq_le. |
| 609 |
rewrite (commutativity _ k), shiftl.shiftl_exp_plus, shiftl.shiftl_1. |
| 610 |
rewrite rings.plus_mult_distr_r, rings.mult_1_l. |
| 611 |
rewrite rings.negate_plus_distr, associativity, rings.plus_negate_r. simpl. ring. |
| 612 |
apply (order_reflecting (cast AQ Q)). |
| 613 |
rewrite rings.preserves_negate. |
| 614 |
exact (E ('Pos_shiftl (1 : AQ₊) k)). |
| 615 |
Qed. |
| 616 |
|
| 617 |
(* Hack: we write [-1 - cast nat Z n] instead of [cast nat Z n] because |
| 618 |
approximate is not Proper. *) |
| 619 |
Global Instance ARlt: Lt AR := λ x y, |
| 620 |
∃ n : nat, AR_epsilon_sign_dec (-1 - cast nat Z n) (y - x) ≡ Gt. |
| 621 |
|
| 622 |
Lemma AR_lt_ltT x y : prod (x < y -> ARltT x y) |
| 623 |
(ARltT x y -> x < y). |
| 624 |
Proof. |
| 625 |
split. |
| 626 |
- intros E. |
| 627 |
apply ConstructiveEpsilon.constructive_indefinite_description_nat in E. |
| 628 |
destruct E as [n En]. |
| 629 |
now apply AR_epsilon_sign_dec_pos with (-1 - cast nat Z n). |
| 630 |
intros. now apply comparison_eq_dec. |
| 631 |
- intros [ε Eε]. |
| 632 |
exists (Z.nat_of_Z (-Qdlog2 ('ε))). |
| 633 |
apply AR_epsilon_sign_dec_pos_rev. |
| 634 |
transitivity ('ε : AR); [| assumption]. |
| 635 |
rapply (order_preserving (cast AQ AR)). |
| 636 |
apply (order_reflecting (cast AQ Q)). |
| 637 |
rewrite aq_shift_correct, rings.preserves_1, rings.mult_1_l. |
| 638 |
destruct (decide (('ε : Q) ≤ 1)). |
| 639 |
rewrite Z.nat_of_Z_nonneg. |
| 640 |
mc_setoid_replace (1 + (-1 - - Qdlog2 ('ε))) with (Qdlog2 ('ε)) by ring. |
| 641 |
apply Qdlog2_spec. |
| 642 |
apply semirings.preserves_pos. |
| 643 |
now destruct ε. |
| 644 |
change (0 ≤ -Qdlog2 ('ε)). |
| 645 |
apply rings.flip_nonpos_negate. |
| 646 |
now apply Qdlog2_nonpos. |
| 647 |
rewrite Z.nat_of_Z_nonpos. |
| 648 |
now apply orders.le_flip. |
| 649 |
change (-Qdlog2 ('ε) ≤ 0). |
| 650 |
apply rings.flip_nonneg_negate. |
| 651 |
apply Qdlog2_nonneg. |
| 652 |
now apply orders.le_flip. |
| 653 |
Qed. |
| 654 |
|
| 655 |
Instance: Proper ((=) ==> (=) ==> iff) ARlt. |
| 656 |
Proof. split; intro E; apply AR_lt_ltT; apply AR_lt_ltT in E; |
| 657 |
eapply ARltT_wd; eauto; now symmetry. Qed. |
| 658 |
|
| 659 |
(* Apartness in Prop *) |
| 660 |
Global Instance ARapart: Apart AR := λ x y, x < y ∨ y < x. |
| 661 |
|
| 662 |
Lemma ARtoCR_preserves_lt (x y : AR) : x < y ↔ 'x < 'y. |
| 663 |
Proof. |
| 664 |
split; intros E. |
| 665 |
now apply CR_lt_ltT, ARtoCR_preserves_ltT, AR_lt_ltT. |
| 666 |
now apply AR_lt_ltT, ARtoCR_preserves_ltT, CR_lt_ltT. |
| 667 |
Qed. |
| 668 |
|
| 669 |
Lemma AR_apart_apartT x y : prod (x ≶ y -> ARapartT x y) |
| 670 |
(ARapartT x y -> x ≶ y). |
| 671 |
Proof. |
| 672 |
split. |
| 673 |
- intros E. |
| 674 |
set (f (n : nat) := AR_epsilon_sign_dec (-1 - cast nat Z n)). |
| 675 |
assert (∃ n, f n (y - x) ≡ Gt ∨ f n (x - y) ≡ Gt) as E2. |
| 676 |
now destruct E as [[n En] | [n En]]; exists n; [left | right]. |
| 677 |
apply ConstructiveEpsilon.constructive_indefinite_description_nat in E2. |
| 678 |
destruct E2 as [n E2]. |
| 679 |
destruct (comparison_eq_dec (f n (y - x)) Gt) as [En|En]. |
| 680 |
left. now apply AR_epsilon_sign_dec_pos with (-1 - cast nat Z n). |
| 681 |
right. apply AR_epsilon_sign_dec_pos with (-1 - cast nat Z n). |
| 682 |
destruct E2; tauto. |
| 683 |
intros n. |
| 684 |
destruct (comparison_eq_dec (f n (y - x)) Gt); auto. |
| 685 |
destruct (comparison_eq_dec (f n (x - y)) Gt); tauto. |
| 686 |
- intros [E|E]. |
| 687 |
left. now apply AR_lt_ltT. |
| 688 |
right. now apply AR_lt_ltT. |
| 689 |
Qed. |
| 690 |
|
| 691 |
Let ARtoCR_preserves_apart x y : x ≶ y ↔ cast AR CR x ≶ cast AR CR y. |
| 692 |
Proof. |
| 693 |
unfold apart, ARapart, CRapart. |
| 694 |
now rewrite !ARtoCR_preserves_lt. |
| 695 |
Qed. |
| 696 |
|
| 697 |
Instance: StrongSetoid AR. |
| 698 |
Proof. |
| 699 |
apply (strong_setoids.projected_strong_setoid (cast AR CR)). |
| 700 |
split; intros E; [now rewrite E | now apply (injective (cast AR CR))]. |
| 701 |
now apply ARtoCR_preserves_apart. |
| 702 |
Qed. |
| 703 |
|
| 704 |
Instance: StrongSetoid_Morphism (cast AR CR). |
| 705 |
Proof. split; try apply _; now apply ARtoCR_preserves_apart. Qed. |
| 706 |
|
| 707 |
Global Instance: StrongInjective (cast AR CR). |
| 708 |
Proof. split; try apply _; now apply ARtoCR_preserves_apart. Qed. |
| 709 |
|
| 710 |
Global Instance: StrongSemiRing_Morphism (cast AR CR). |
| 711 |
Proof. split; try apply _. Qed. |
| 712 |
|
| 713 |
Global Instance: StrongSemiRing_Morphism (cast AQ AR). |
| 714 |
Proof. |
| 715 |
repeat (split; try apply _). intros. |
| 716 |
apply (strong_extensionality (cast AQ Q)). |
| 717 |
apply (strong_extensionality (cast Q CR)). |
| 718 |
rewrite <-2!ARtoCR_inject. |
| 719 |
now apply (strong_injective _). |
| 720 |
Qed. |
| 721 |
|
| 722 |
Global Instance: StrongInjective (cast AQ AR). |
| 723 |
Proof. |
| 724 |
repeat (split; try apply _). intros. |
| 725 |
apply (strong_extensionality (cast AR CR)). |
| 726 |
rewrite 2!ARtoCR_inject. |
| 727 |
apply (strong_injective _). |
| 728 |
now apply (strong_injective _). |
| 729 |
Qed. |
| 730 |
|
| 731 |
Global Instance ARfpsro: FullPseudoSemiRingOrder ARle ARlt. |
| 732 |
Proof. |
| 733 |
apply (rings.projected_full_pseudo_ring_order (cast AR CR)). |
| 734 |
apply ARtoCR_preserves_le. |
| 735 |
apply ARtoCR_preserves_lt. |
| 736 |
Qed. |
| 737 |
|
| 738 |
Lemma ARle_not_lt (x y: AR): ARle x y <-> (ARltT y x -> False). |
| 739 |
Proof. |
| 740 |
destruct ARfpsro as [_ flip]. |
| 741 |
specialize (flip x y). destruct flip. |
| 742 |
split. |
| 743 |
- intros. apply H5. exact H7. |
| 744 |
apply AR_lt_ltT, X. |
| 745 |
- intros. apply H6. intro abs. apply H7. |
| 746 |
apply AR_lt_ltT, abs. |
| 747 |
Qed. |
| 748 |
|
| 749 |
Global Instance: StrictOrderEmbedding (cast AR CR). |
| 750 |
Proof. repeat (split; try apply _); apply ARtoCR_preserves_lt. Qed. |
| 751 |
|
| 752 |
(* Division *) |
| 753 |
Lemma aq_mult_inv_regular_prf (x : AQ) : |
| 754 |
is_RegularFunction_noInf _ (λ ε : Qpos, app_div 1 x (Qdlog2 (proj1_sig ε)) : AQ_as_MetricSpace). |
| 755 |
Proof. |
| 756 |
intros ε1 ε2. simpl. |
| 757 |
eapply ball_triangle. |
| 758 |
now eapply aq_div_dlog2. |
| 759 |
now eapply ball_sym, aq_div_dlog2. |
| 760 |
Qed. |
| 761 |
|
| 762 |
Definition AQinv (x : AQ) : AR := mkRegularFunction (0 : AQ_as_MetricSpace) (aq_mult_inv_regular_prf x). |
| 763 |
|
| 764 |
Definition AQinv_bounded (c : AQ₊) (x : AQ_as_MetricSpace) : AR := AQinv (('c) ⊔ x). |
| 765 |
|
| 766 |
Lemma AQinv_pos_uc_prf (c : AQ₊) : is_UniformlyContinuousFunction |
| 767 |
(AQinv_bounded c) (Qinv_modulus ('c)). |
| 768 |
Proof. |
| 769 |
intros ε x y E δ1 δ2. simpl in *. |
| 770 |
eapply ball_triangle. |
| 771 |
2: now eapply ball_sym, aq_div_dlog2. |
| 772 |
eapply ball_triangle. |
| 773 |
now eapply aq_div_dlog2. |
| 774 |
simpl. aq_preservation. |
| 775 |
rewrite 2!left_identity. |
| 776 |
pose proof (Qinv_pos_uc_prf (' c) ε (' x) (' y)) as H5. |
| 777 |
simpl in H5. apply H5. |
| 778 |
exact E. |
| 779 |
Qed. |
| 780 |
|
| 781 |
Definition AQinv_pos_uc (c : AQ₊) := Build_UniformlyContinuousFunction (AQinv_pos_uc_prf c). |
| 782 |
|
| 783 |
Definition ARinv_pos (c : AQ₊) : AR --> AR := Cbind AQPrelengthSpace (AQinv_pos_uc c). |
| 784 |
|
| 785 |
Lemma ARtoCR_preserves_inv_pos_aux c (x : AR) : is_RegularFunction_noInf _ |
| 786 |
(λ γ, / Qmax (''c) ('approximate x (Qinv_modulus ('c) γ)) : Q_as_MetricSpace). |
| 787 |
Proof. |
| 788 |
intros ε1 ε2. |
| 789 |
apply_simplified (Qinv_pos_uc_prf ('c) (ε1 + ε2)%Qpos). |
| 790 |
apply AQball_fold. |
| 791 |
setoid_replace (' c * ' c * (` ε1 + ` ε2))%Q |
| 792 |
with (proj1_sig (Qinv_modulus ('c) ε1 + Qinv_modulus ('c) ε2)%Qpos) |
| 793 |
by (unfold equiv, stdlib_rationals.Q_eq; simpl; ring). |
| 794 |
apply regFun_prf. |
| 795 |
Qed. |
| 796 |
|
| 797 |
Lemma ARtoCR_preserves_inv_pos x c : 'ARinv_pos c x = CRinv_pos ('c) ('x). |
| 798 |
Proof. |
| 799 |
apply regFunEq_equiv, regFunEq_e. intros ε. |
| 800 |
simpl. unfold Cjoin_raw. simpl. |
| 801 |
setoid_replace (proj1_sig ε + proj1_sig ε)%Q |
| 802 |
with (proj1_sig ((1#2) * ε + ((1#2) * ε + ε)))%Qpos |
| 803 |
by (unfold equiv, stdlib_rationals.Q_eq; simpl; ring). |
| 804 |
eapply ball_triangle. |
| 805 |
now apply aq_div_dlog2. |
| 806 |
simpl. |
| 807 |
rewrite aq_preserves_max. |
| 808 |
rewrite rings.preserves_1. |
| 809 |
rewrite Qmult_1_l. |
| 810 |
change (Qball ( (1 # 2) * ` ε + ` ε) |
| 811 |
(/ Qmax (' (' c)) (' approximate x (Qinv_modulus (' c) ((1 # 2) ↾ eq_refl * ε))))%mc |
| 812 |
( / Qmax (' c) (' approximate x (Qinv_modulus (' c) ε)))). |
| 813 |
apply (ARtoCR_preserves_inv_pos_aux c x ((1 # 2) * ε)%Qpos). |
| 814 |
Qed. |
| 815 |
Hint Rewrite ARtoCR_preserves_inv_pos : ARtoCR. |
| 816 |
|
| 817 |
Definition ARinvT (x : AR) (x_ : ARapartT x 0) : AR := |
| 818 |
match x_ with |
| 819 |
| inl (exist _ c _) => - ARinv_pos c (- x) |
| 820 |
| inr (exist _ c _) => ARinv_pos c x |
| 821 |
end. |
| 822 |
|
| 823 |
Lemma ARtoCR_preserves_invT x x_ x__: |
| 824 |
'ARinvT x x_ = CRinvT ('x) x__. |
| 825 |
Proof with auto with qarith; try reflexivity. |
| 826 |
unfold ARinvT. |
| 827 |
destruct x_ as [Ec | Ec]. |
| 828 |
assert (CRltT ('x) 0) as Px. |
| 829 |
apply CRltT_wd with ('x) (cast AR CR 0). |
| 830 |
reflexivity. |
| 831 |
now apply rings.preserves_0. |
| 832 |
now apply ARtoCR_preserves_ltT. |
| 833 |
rewrite (CRinvT_irrelevant _ (inl Px)). |
| 834 |
unfold CRinvT. |
| 835 |
destruct Ec as [c Ec], Px as [d Ed]. |
| 836 |
autorewrite with ARtoCR. |
| 837 |
destruct (Qlt_le_dec (proj1_sig d) (proj1_sig ('c : Qpos))). |
| 838 |
rewrite (CRinv_pos_weaken d ('c))... |
| 839 |
change (cast Q CR (cast AQ Q (cast (AQ₊) AQ c)) ≤ -cast AR CR x). |
| 840 |
rewrite <-ARtoCR_inject, <-rings.preserves_negate. |
| 841 |
apply (order_preserving _). |
| 842 |
rewrite <-(rings.plus_0_l (-x))... |
| 843 |
rewrite (CRinv_pos_weaken ('c) d)... |
| 844 |
rewrite <-(rings.plus_0_l (-cast AR CR x))... |
| 845 |
assert (CRltT 0 ('x)) as Px. |
| 846 |
apply CRltT_wd with (cast AR CR 0) ('x). |
| 847 |
now apply rings.preserves_0. |
| 848 |
reflexivity. |
| 849 |
now apply ARtoCR_preserves_ltT. |
| 850 |
rewrite (CRinvT_irrelevant _ (inr Px)). |
| 851 |
unfold CRinvT. |
| 852 |
destruct Ec as [c Ec], Px as [d Ed]. |
| 853 |
autorewrite with ARtoCR. |
| 854 |
destruct (Qlt_le_dec (proj1_sig d) (proj1_sig ('c : Qpos))). |
| 855 |
rewrite (CRinv_pos_weaken d ('c))... |
| 856 |
change (cast Q CR (cast AQ Q (cast (AQ₊) AQ c)) ≤ cast AR CR x). |
| 857 |
rewrite <-ARtoCR_inject. |
| 858 |
apply (order_preserving _). |
| 859 |
setoid_replace x with (x - 0) by ring... |
| 860 |
rewrite (CRinv_pos_weaken ('c) d)... |
| 861 |
rewrite <-(rings.plus_0_r (cast AR CR x))... |
| 862 |
Qed. |
| 863 |
|
| 864 |
Lemma ARtoCR_preserves_invT_l x x_ : {x__ | 'ARinvT x x_ = CRinvT ('x) x__}. |
| 865 |
Proof. |
| 866 |
exists (fst (ARtoCR_preserves_apartT_0 x) x_). |
| 867 |
apply ARtoCR_preserves_invT. |
| 868 |
Qed. |
| 869 |
|
| 870 |
Lemma ARtoCR_preserves_invT_r x x__ : {x_ | 'ARinvT x x_ = CRinvT ('x) x__}. |
| 871 |
Proof. |
| 872 |
exists (snd (ARtoCR_preserves_apartT_0 x) x__). |
| 873 |
apply ARtoCR_preserves_invT. |
| 874 |
Qed. |
| 875 |
|
| 876 |
Lemma AR_inverseT (x : AR) x_ : x * ARinvT x x_ = 1. |
| 877 |
Proof. |
| 878 |
apply (injective (cast AR CR)). |
| 879 |
rewrite rings.preserves_mult, rings.preserves_1. |
| 880 |
destruct (ARtoCR_preserves_invT_l x x_) as [x__ E]. rewrite E. |
| 881 |
apply CRmult_inv_r. |
| 882 |
Qed. |
| 883 |
|
| 884 |
Lemma ARinvT_wd x y x_ y_ : x = y → ARinvT x x_ = ARinvT y y_. |
| 885 |
Proof. |
| 886 |
intros E. |
| 887 |
apply (injective (cast AR CR)). |
| 888 |
destruct (ARtoCR_preserves_invT_l x x_) as [x__ Ex], |
| 889 |
(ARtoCR_preserves_invT_l y y_) as [y__ Ey]. |
| 890 |
rewrite Ex, Ey. |
| 891 |
now apply CRinvT_wd. |
| 892 |
Qed. |
| 893 |
|
| 894 |
Lemma ARinvT_irrelevant x x_ x__ : ARinvT x x_ = ARinvT x x__. |
| 895 |
Proof. now apply ARinvT_wd. Qed. |
| 896 |
|
| 897 |
(* Division with apartness in Prop *) |
| 898 |
Program Instance ARinv: Recip AR := λ x, ARinvT x _. |
| 899 |
Next Obligation. apply AR_apart_apartT. now destruct x. Qed. |
| 900 |
|
| 901 |
Global Instance: Field AR. |
| 902 |
Proof. |
| 903 |
split. apply _. apply _. |
| 904 |
apply _. apply _. |
| 905 |
apply (strong_injective (cast AQ AR)). |
| 906 |
solve_propholds. |
| 907 |
split. apply _. apply _. |
| 908 |
intros [x Px] [y Py] E. |
| 909 |
now refine (ARinvT_wd _ _ _ _ _). |
| 910 |
intros x. |
| 911 |
now apply AR_inverseT. |
| 912 |
Qed. |
| 913 |
|
| 914 |
(* Nat pow *) |
| 915 |
Program Definition AQpower_N_uc (n : N) (c : AQ₊) : |
| 916 |
AQ_as_MetricSpace --> AQ_as_MetricSpace := unary_uc |
| 917 |
(cast AQ Q_as_MetricSpace) |
| 918 |
(λ x : AQ_as_MetricSpace, (AQboundAbs_uc c x) ^ n : AQ_as_MetricSpace) (Qpower_N_uc n ('c)) _. |
| 919 |
Next Obligation. |
| 920 |
assert (∀ y : AQ, cast AQ Q (y ^ n) = 'y ^ 'n) as preserves_pow_pos. |
| 921 |
intros y. |
| 922 |
rewrite nat_pow.preserves_nat_pow. |
| 923 |
now rewrite (int_pow.int_pow_nat_pow (f:=cast N Z)). |
| 924 |
apply Qball_0. |
| 925 |
rewrite preserves_pow_pos. aq_preservation. |
| 926 |
Qed. |
| 927 |
|
| 928 |
Definition ARpower_N_bounded (n : N) (c : AQ₊) : AR --> AR := Cmap AQPrelengthSpace (AQpower_N_uc n c). |
| 929 |
|
| 930 |
Lemma ARtoCR_preserves_power_N_bounded x n c : |
| 931 |
'ARpower_N_bounded n c x = CRpower_N_bounded n ('c) ('x). |
| 932 |
Proof. apply preserves_unary_fun. Qed. |
| 933 |
|
| 934 |
Global Instance ARpower_N: Pow AR N := λ x n, ucFun (ARpower_N_bounded n (AR_b x)) x. |
| 935 |
|
| 936 |
Lemma ARtoCR_preserves_power_N (x : AR) (n : N) : |
| 937 |
cast AR CR (x ^ n) = ('x) ^ n. |
| 938 |
Proof. |
| 939 |
unfold pow, CRpower_N, ARpower_N. |
| 940 |
rewrite ARtoCR_preserves_power_N_bounded. |
| 941 |
apply Cmap_wd. 2: reflexivity. |
| 942 |
assert (QposEq (cast (AQ₊) (Q₊) (AR_b x)) (CR_b (1#1) ('x))). |
| 943 |
{ unfold QposEq. simpl. |
| 944 |
now rewrite ARtoCR_approximate, <-AR_b_correct. } |
| 945 |
rewrite H5. reflexivity. |
| 946 |
Qed. |
| 947 |
|
| 948 |
Hint Rewrite ARtoCR_preserves_power_N : ARtoCR. |
| 949 |
|
| 950 |
Global Instance: NatPowSpec AR N _. |
| 951 |
Proof. |
| 952 |
split. |
| 953 |
intros ? ? Ex ? ? En. |
| 954 |
apply (injective (cast AR CR)). autorewrite with ARtoCR. |
| 955 |
now rewrite Ex, En. |
| 956 |
intros. apply (injective (cast AR CR)). autorewrite with ARtoCR. |
| 957 |
now rewrite nat_pow_0. |
| 958 |
intros. apply (injective (cast AR CR)). autorewrite with ARtoCR. |
| 959 |
now rewrite nat_pow_S. |
| 960 |
Qed. |
| 961 |
|
| 962 |
(* Misc properties *) |
| 963 |
Lemma ARmult_bounded_mult (x y : AR) c : |
| 964 |
-'c ≤ y ≤ 'c → ARmult_bounded c x y = x * y. |
| 965 |
Proof. |
| 966 |
intros. |
| 967 |
apply (injective (cast AR CR)). |
| 968 |
rewrite ARtoCR_preserves_mult, ARtoCR_preserves_mult_bounded. |
| 969 |
destruct c as [c Pc]. |
| 970 |
apply CRmult_bounded_mult. |
| 971 |
change (cast Q CR (-cast AQ Q c) ≤ cast AR CR y). |
| 972 |
rewrite <-rings.preserves_negate. |
| 973 |
rewrite <-ARtoCR_inject. |
| 974 |
apply (order_preserving _). intuition. |
| 975 |
change (cast AR CR y ≤ cast Q CR (cast AQ Q c)). |
| 976 |
rewrite <-ARtoCR_inject. |
| 977 |
apply (order_preserving _). intuition. |
| 978 |
Qed. |
| 979 |
|
| 980 |
Lemma ARpower_N_bounded_N_power (n : N) (x : AR) (c : AQ₊) : |
| 981 |
-'c ≤ x ≤ 'c → ARpower_N_bounded n c x = x ^ n. |
| 982 |
Proof. |
| 983 |
intros. |
| 984 |
apply (injective (cast AR CR)). |
| 985 |
rewrite ARtoCR_preserves_power_N, ARtoCR_preserves_power_N_bounded. |
| 986 |
destruct c as [c Pc]. |
| 987 |
apply CRpower_N_bounded_N_power. split. |
| 988 |
change (cast Q CR (-cast AQ Q c) ≤ cast AR CR x). |
| 989 |
rewrite <-rings.preserves_negate. |
| 990 |
rewrite <-ARtoCR_inject. |
| 991 |
apply (order_preserving _). intuition. |
| 992 |
change (cast AR CR x ≤ cast Q CR (cast AQ Q c)). |
| 993 |
rewrite <-ARtoCR_inject. |
| 994 |
apply (order_preserving _). intuition. |
| 995 |
Qed. |
| 996 |
|
| 997 |
Lemma inject_Q_AR_lt : ∀ q r : Q, q < r → ARltT (inject_Q_AR q) (inject_Q_AR r). |
| 998 |
Proof. |
| 999 |
intros. |
| 1000 |
destruct (ARtoCR_preserves_ltT (' (' q)%CR) (' (' r)%CR)) as [_ a]. |
| 1001 |
pose proof (inject_Q_AR_CR q). |
| 1002 |
pose proof (inject_Q_AR_CR r). |
| 1003 |
symmetry in H6. symmetry in H7. |
| 1004 |
apply (ARltT_wd _ _ H6 _ _ H7). |
| 1005 |
apply a. clear a H6 H7. |
| 1006 |
pose proof (CRAR_id ('q)%CR). pose proof (CRAR_id ('r)%CR). |
| 1007 |
symmetry in H6. symmetry in H7. |
| 1008 |
apply (@CRltT_wd _ _ H6 _ _ H7). |
| 1009 |
apply CRlt_Qlt, H5. |
| 1010 |
Qed. |
| 1011 |
|
| 1012 |
Lemma inject_Q_AR_lt_rev : ∀ q r : Q, ARltT (inject_Q_AR q) (inject_Q_AR r) → q < r. |
| 1013 |
Proof. |
| 1014 |
intros. |
| 1015 |
destruct (ARtoCR_preserves_ltT (' (' q)%CR) (' (' r)%CR)) as [c _]. |
| 1016 |
pose proof (inject_Q_AR_CR q) as H6. |
| 1017 |
pose proof (inject_Q_AR_CR r) as H7. |
| 1018 |
apply (ARltT_wd _ _ H6 _ _ H7) in X. |
| 1019 |
apply c in X. clear c H6 H7. |
| 1020 |
pose proof (CRAR_id ('q)%CR). pose proof (CRAR_id ('r)%CR). |
| 1021 |
apply (@CRltT_wd _ _ H5 _ _ H6) in X. |
| 1022 |
apply Qlt_from_CRlt, X. |
| 1023 |
Qed. |
| 1024 |
|
| 1025 |
Lemma inject_Q_AR_le : ∀ q r : Q, q <= r → ARle (inject_Q_AR q) (inject_Q_AR r). |
| 1026 |
Proof. |
| 1027 |
intros. |
| 1028 |
apply ARle_not_lt. |
| 1029 |
intro abs. |
| 1030 |
apply inject_Q_AR_lt_rev in abs. |
| 1031 |
exact (Qlt_not_le _ _ abs H5). |
| 1032 |
Qed. |
| 1033 |
|
| 1034 |
Lemma inject_Q_AR_plus : ∀ q r : Q, |
| 1035 |
inject_Q_AR (q + r) = inject_Q_AR q + inject_Q_AR r. |
| 1036 |
Proof. |
| 1037 |
intros. |
| 1038 |
apply (injective (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace))). |
| 1039 |
pose proof CRAR_id as H5. |
| 1040 |
unfold cast in H5. |
| 1041 |
unfold ARtoCR, ARtoCR_uc in H5. |
| 1042 |
unfold cast. |
| 1043 |
rewrite (inject_Q_AR_CR (q+r)). |
| 1044 |
rewrite (inject_Q_AR_CR q). |
| 1045 |
rewrite (inject_Q_AR_CR r). |
| 1046 |
unfold cast. unfold cast in H5. |
| 1047 |
rewrite H5. |
| 1048 |
pose proof (ARtoCR_preserves_plus (CRtoAR (' q)%CR) (CRtoAR (' r)%CR)) as H6. |
| 1049 |
rewrite H6. |
| 1050 |
rewrite <- CRplus_Qplus. |
| 1051 |
apply ucFun2_wd. rewrite (H5 ('q)%CR). reflexivity. |
| 1052 |
rewrite (H5 ('r)%CR). reflexivity. |
| 1053 |
Qed. |
| 1054 |
|
| 1055 |
Lemma inject_Q_AR_mult : ∀ q r : Q, |
| 1056 |
inject_Q_AR (q * r) = inject_Q_AR q * inject_Q_AR r. |
| 1057 |
Proof. |
| 1058 |
intros. |
| 1059 |
apply (injective (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace))). |
| 1060 |
pose proof CRAR_id as H5. |
| 1061 |
unfold cast in H5. |
| 1062 |
unfold ARtoCR, ARtoCR_uc in H5. |
| 1063 |
rewrite (inject_Q_AR_CR (q*r)). |
| 1064 |
rewrite (inject_Q_AR_CR q). |
| 1065 |
rewrite (inject_Q_AR_CR r). |
| 1066 |
unfold cast. unfold cast in H5. |
| 1067 |
rewrite H5. |
| 1068 |
pose proof (ARtoCR_preserves_mult (CRtoAR (' q)%CR) (CRtoAR (' r)%CR)) as H6. |
| 1069 |
rewrite H6. |
| 1070 |
rewrite <- CRmult_Qmult. |
| 1071 |
apply CRmult_wd. rewrite (H5 ('q)%CR). reflexivity. |
| 1072 |
rewrite (H5 ('r)%CR). reflexivity. |
| 1073 |
Qed. |
| 1074 |
|
| 1075 |
Lemma inject_Q_AR_1 : inject_Q_AR (1#1) = 1. |
| 1076 |
Proof. |
| 1077 |
Local Transparent regFunEq. |
| 1078 |
intros e1 e2. simpl. |
| 1079 |
destruct aq_dense_embedding. |
| 1080 |
specialize (dense_inverse 1 e1). |
| 1081 |
simpl in dense_inverse. |
| 1082 |
rewrite Qplus_0_r. |
| 1083 |
apply (@ball_weak_le Q_as_MetricSpace (`e1) (`e1+`e2)). |
| 1084 |
apply (Qle_trans _ (`e1 + 0)). |
| 1085 |
rewrite Qplus_0_r. apply Qle_refl. |
| 1086 |
apply Qplus_le_r, Qpos_nonneg. |
| 1087 |
simpl. unfold cast. |
| 1088 |
destruct aq_ring_morphism, semiringmor_mult_mor. |
| 1089 |
rewrite preserves_mon_unit. |
| 1090 |
exact dense_inverse. |
| 1091 |
Qed. |
| 1092 |
|
| 1093 |
Lemma inject_Q_AR_0 : inject_Q_AR (0#1) = 0. |
| 1094 |
Proof. |
| 1095 |
intros e1 e2. simpl. |
| 1096 |
destruct aq_dense_embedding. |
| 1097 |
simpl in dense_inverse. |
| 1098 |
rewrite Qplus_0_r. |
| 1099 |
apply (@ball_weak_le Q_as_MetricSpace (`e1) (`e1+`e2)). |
| 1100 |
apply (Qle_trans _ (`e1 + 0)). |
| 1101 |
rewrite Qplus_0_r. apply Qle_refl. |
| 1102 |
apply Qplus_le_r, Qpos_nonneg. |
| 1103 |
simpl. unfold cast. |
| 1104 |
destruct aq_ring_morphism, semiringmor_plus_mor. |
| 1105 |
rewrite preserves_mon_unit. |
| 1106 |
apply dense_inverse. |
| 1107 |
Qed. |
| 1108 |
|
| 1109 |
|
| 1110 |
Lemma inject_Q_AR_wd : forall q r : Q, |
| 1111 |
q == r -> inject_Q_AR q = inject_Q_AR r. |
| 1112 |
Proof. |
| 1113 |
intros q r qreq e1 e2. |
| 1114 |
simpl. |
| 1115 |
destruct aq_dense_embedding. |
| 1116 |
unfold cast. |
| 1117 |
rewrite Qplus_0_r. |
| 1118 |
apply ball_triangle with (b:=q). |
| 1119 |
apply dense_inverse. |
| 1120 |
simpl. |
| 1121 |
rewrite qreq. |
| 1122 |
change (Qball (` e2) r (AQtoQ (app_inverse AQtoQ r e2))). |
| 1123 |
apply ball_sym. |
| 1124 |
apply dense_inverse. |
| 1125 |
Qed. |
| 1126 |
|
| 1127 |
Lemma AR_mult_0_lt_compat : ∀ x y : AR, |
| 1128 |
ARltT (inject_Q_AR 0) x |
| 1129 |
→ ARltT (inject_Q_AR 0) y |
| 1130 |
→ ARltT (inject_Q_AR 0) (ARmult x y). |
| 1131 |
Proof. |
| 1132 |
intros x y X X0. |
| 1133 |
destruct (ARtoCR_preserves_ltT (inject_Q_AR 0) (ARmult x y)) as [_ a]. |
| 1134 |
apply a. clear a. |
| 1135 |
pose proof (ARtoCR_preserves_mult x y) as H5. |
| 1136 |
unfold mult in H5. |
| 1137 |
symmetry in H5. |
| 1138 |
assert (0 = ARtoCR (inject_Q_AR 0))%CR as H7. |
| 1139 |
{ rewrite <- (CRAR_id 0%CR). |
| 1140 |
unfold cast. |
| 1141 |
rewrite (inject_Q_AR_CR 0). reflexivity. } |
| 1142 |
pose proof (ARtoCR_preserves_mult x y) as H8. |
| 1143 |
symmetry in H8. |
| 1144 |
apply (CRltT_wd H7 H8). clear H8 H5. |
| 1145 |
apply CRmult_lt_0_compat. |
| 1146 |
- destruct (ARtoCR_preserves_ltT (inject_Q_AR 0) x). |
| 1147 |
apply c in X. clear a c. |
| 1148 |
symmetry in H7. |
| 1149 |
apply (CRltT_wd H7 (reflexivity _)). exact X. |
| 1150 |
- destruct (ARtoCR_preserves_ltT (inject_Q_AR 0) y). |
| 1151 |
apply c in X0. clear a c. |
| 1152 |
symmetry in H7. |
| 1153 |
apply (CRltT_wd H7 (reflexivity _)). exact X0. |
| 1154 |
Qed. |
| 1155 |
|
| 1156 |
Lemma AR_mult_0_le_compat : ∀ x y : AR, |
| 1157 |
ARle 0 x |
| 1158 |
→ ARle 0 y |
| 1159 |
→ ARle 0 (x*y). |
| 1160 |
Proof. |
| 1161 |
intros. |
| 1162 |
apply ARtoCR_preserves_le. |
| 1163 |
rewrite ARtoCR_preserves_mult. |
| 1164 |
rewrite ARtoCR_preserves_0. |
| 1165 |
apply (CRmult_le_0_compat ('x) ('y)). |
| 1166 |
rewrite <- ARtoCR_preserves_0. |
| 1167 |
apply ARtoCR_preserves_le, H5. |
| 1168 |
rewrite <- ARtoCR_preserves_0. |
| 1169 |
apply ARtoCR_preserves_le, H6. |
| 1170 |
Qed. |
| 1171 |
|
| 1172 |
|
| 1173 |
End ARarith. |