| 1 |
(* |
| 2 |
Copyright © 2020 Vincent Semeria |
| 3 |
|
| 4 |
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: |
| 5 |
|
| 6 |
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. |
| 7 |
|
| 8 |
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 9 |
*) |
| 10 |
|
| 11 |
|
| 12 |
(** Proof that CoRN's fast reals implement the standard library's |
| 13 |
interface ConstructiveReals. *) |
| 14 |
|
| 15 |
From Coq Require Import ZArith ConstructiveReals. |
| 16 |
Require Import CoRN.model.metric2.Qmetric. |
| 17 |
Require Import CoRN.model.metric2.CRmetric. |
| 18 |
Require Import CoRN.reals.fast.CRFieldOps. |
| 19 |
Require Import CoRN.reals.fast.CRArith. |
| 20 |
Require Import CoRN.reals.fast.CRabs. |
| 21 |
Require Import CoRN.model.totalorder.QposMinMax. |
| 22 |
From Coq Require Import ConstructiveEpsilon. |
| 23 |
|
| 24 |
Lemma CRltT_linear : @isLinearOrder (RegularFunction Qball) CRltT. |
| 25 |
Proof. |
| 26 |
split. split. |
| 27 |
- intros. apply (CRlt_trans _ _ _ H) in H0. |
| 28 |
apply (CRlt_irrefl x H0). |
| 29 |
- intros. exact (CRlt_trans _ _ _ H H0). |
| 30 |
- apply CRlt_linear. |
| 31 |
Qed. |
| 32 |
|
| 33 |
Lemma CRlt_equiv : forall x y : CR, |
| 34 |
CRlt x y |
| 35 |
<-> exists n:nat, approximate x (Qpos2QposInf (1#Pos.of_nat n)) + (2#Pos.of_nat n) |
| 36 |
< approximate y (Qpos2QposInf (1#Pos.of_nat n)). |
| 37 |
Proof. |
| 38 |
split. |
| 39 |
- intros H. apply CR_lt_ltT in H. destruct H as [q H]. |
| 40 |
destruct q as [q qpos]; unfold proj1_sig in H. |
| 41 |
destruct q as [a b]. destruct a as [|a|a]. |
| 42 |
exfalso; inversion qpos. |
| 43 |
2: exfalso; inversion qpos. clear qpos. |
| 44 |
assert (translate (1#b) x <= y)%CR. |
| 45 |
{ rewrite (CRplus_le_r _ _ x) in H. |
| 46 |
ring_simplify in H. |
| 47 |
rewrite <- CRplus_translate. |
| 48 |
apply (@CRle_trans _ (' (Z.pos a # b) + x)%CR). |
| 49 |
2: exact H. |
| 50 |
apply CRplus_le_r, CRle_Qle. |
| 51 |
change (b <= a*b)%positive. |
| 52 |
apply (Pos.le_trans _ (1*b)). |
| 53 |
apply Pos.le_refl. |
| 54 |
apply Pos.mul_le_mono_r. apply Pos.le_1_l. } |
| 55 |
clear H a. |
| 56 |
exists (Pos.to_nat (5*b)). |
| 57 |
rewrite Pos2Nat.id. |
| 58 |
apply (CRle_trans (lower_CRapproximation (translate (1#b) x) (1#5*b)%Qpos)) |
| 59 |
in H0. |
| 60 |
pose proof (upper_CRapproximation y (1#5*b)%Qpos) as H. |
| 61 |
apply (CRle_trans H0) in H. clear H0. |
| 62 |
apply CRle_Qle in H. simpl in H. |
| 63 |
rewrite Qplus_comm in H. |
| 64 |
unfold Qminus in H. rewrite <- Qplus_assoc in H. |
| 65 |
setoid_replace ((1 # b) + - (1 # b + b~0~0)) |
| 66 |
with ((3#5*b) + (1#5*b)) in H. |
| 67 |
rewrite Qplus_assoc in H. apply Qplus_le_l in H. |
| 68 |
refine (Qlt_le_trans _ _ _ _ H). |
| 69 |
apply Qplus_lt_r. |
| 70 |
apply Pos.mul_lt_mono_r. reflexivity. |
| 71 |
unfold canonical_names.equiv, stdlib_rationals.Q_eq. |
| 72 |
rewrite Qinv_plus_distr. |
| 73 |
setoid_replace (1#b) with (5#5*b) by reflexivity. |
| 74 |
rewrite Qinv_minus_distr. reflexivity. |
| 75 |
- intros [n H]. |
| 76 |
apply CR_lt_ltT. |
| 77 |
apply (@CRle_lt_trans _ _ _ (upper_CRapproximation x (1#Pos.of_nat n)%Qpos)). |
| 78 |
refine (CRlt_le_trans _ _ _ _ (lower_CRapproximation y (1#Pos.of_nat n)%Qpos)). |
| 79 |
apply CRlt_Qlt. simpl. |
| 80 |
apply (Qplus_lt_l _ _ (1# Pos.of_nat n)). |
| 81 |
ring_simplify. |
| 82 |
refine (Qle_lt_trans _ _ _ _ H). |
| 83 |
apply Qplus_le_r. apply Qle_refl. |
| 84 |
Qed. |
| 85 |
|
| 86 |
Lemma CRlt_or_epsilon : (forall a b c d : CR, |
| 87 |
CRlt a b \/ CRlt c d -> (a < b)%CR + (c < d)%CR). |
| 88 |
Proof. |
| 89 |
intros. |
| 90 |
assert (exists n:nat, |
| 91 |
approximate a (Qpos2QposInf (1#Pos.of_nat n)) + (2#Pos.of_nat n) |
| 92 |
< approximate b (Qpos2QposInf (1#Pos.of_nat n)) |
| 93 |
\/ approximate c (Qpos2QposInf (1#Pos.of_nat n)) + (2#Pos.of_nat n) |
| 94 |
< approximate d (Qpos2QposInf (1#Pos.of_nat n))). |
| 95 |
{ destruct H. |
| 96 |
- apply CRlt_equiv in H. destruct H as [n H]. |
| 97 |
exists n. left. exact H. |
| 98 |
- apply CRlt_equiv in H. destruct H as [n H]. |
| 99 |
exists n. right. exact H. } |
| 100 |
apply constructive_indefinite_ground_description_nat in H0. |
| 101 |
- destruct H0 as [n H0]. |
| 102 |
destruct (Qlt_le_dec (approximate a (Qpos2QposInf (1 # Pos.of_nat n)) + (2 # Pos.of_nat n)) |
| 103 |
(approximate b (Qpos2QposInf (1 # Pos.of_nat n)))). |
| 104 |
+ left. apply CR_lt_ltT, CRlt_equiv. |
| 105 |
exists n. exact q. |
| 106 |
+ right. apply CR_lt_ltT, CRlt_equiv. |
| 107 |
exists n. destruct H0. 2: exact H0. exfalso. |
| 108 |
exact (Qlt_not_le _ _ H0 q). |
| 109 |
- intro n. clear H0 H. |
| 110 |
destruct (Qlt_le_dec (approximate a (Qpos2QposInf (1 # Pos.of_nat n)) + (2 # Pos.of_nat n)) |
| 111 |
(approximate b (Qpos2QposInf (1 # Pos.of_nat n)))). |
| 112 |
left. left. exact q. |
| 113 |
destruct (Qlt_le_dec (approximate c (Qpos2QposInf (1 # Pos.of_nat n)) + (2 # Pos.of_nat n)) |
| 114 |
(approximate d (Qpos2QposInf (1 # Pos.of_nat n)))). |
| 115 |
left. right. exact q0. |
| 116 |
right. intros [H|H]. |
| 117 |
exact (Qlt_not_le _ _ H q). |
| 118 |
exact (Qlt_not_le _ _ H q0). |
| 119 |
Qed. |
| 120 |
|
| 121 |
Lemma CReq_nlt : forall a b : CR, |
| 122 |
msp_eq a b |
| 123 |
<-> (fun x y : CR => |
| 124 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\ |
| 125 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) x y) a b. |
| 126 |
Proof. |
| 127 |
split. |
| 128 |
- split. intro abs. |
| 129 |
exact (CRlt_irrefl _ (@CRltT_wd _ _ H b _ (reflexivity _) abs)). |
| 130 |
intro abs. |
| 131 |
exact (CRlt_irrefl _ (@CRltT_wd b _ (reflexivity _) _ _ H abs)). |
| 132 |
- intros [H H0]. apply CRle_antisym. split. |
| 133 |
apply CRle_not_lt in H0. exact H0. |
| 134 |
apply CRle_not_lt in H. exact H. |
| 135 |
Qed. |
| 136 |
|
| 137 |
Lemma inject_Q_CR_plus : forall q r : Q, |
| 138 |
(fun x y : CR => |
| 139 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\ |
| 140 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) x y) |
| 141 |
(' (q + r)%Q)%CR (CRplus (' q)%CR (' r)%CR). |
| 142 |
Proof. |
| 143 |
intros q r. apply CReq_nlt, (CRplus_Qplus q r). |
| 144 |
Qed. |
| 145 |
|
| 146 |
Lemma inject_Q_CR_mult : forall q r : Q, |
| 147 |
(fun x y : CR => |
| 148 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\ |
| 149 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) x y) |
| 150 |
(' (q * r)%Q)%CR (CRmult (' q)%CR (' r)%CR). |
| 151 |
Proof. |
| 152 |
intros q r. |
| 153 |
apply CReq_nlt. symmetry. apply (CRmult_Qmult q r). |
| 154 |
Qed. |
| 155 |
|
| 156 |
Lemma CR_ring_nlt : ring_theory 0%CR 1%CR CRplus CRmult |
| 157 |
(fun x y : CR => CRplus x (- y)%CR) CRopp |
| 158 |
(fun x y : CR => |
| 159 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\ |
| 160 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) x y). |
| 161 |
Proof. |
| 162 |
destruct CR_ring_theory. split. |
| 163 |
- intro x. apply CReq_nlt, Radd_0_l. |
| 164 |
- intros x y. apply CReq_nlt, Radd_comm. |
| 165 |
- intros x y z. apply CReq_nlt, Radd_assoc. |
| 166 |
- intro x. apply CReq_nlt, Rmul_1_l. |
| 167 |
- intros x y. apply CReq_nlt, Rmul_comm. |
| 168 |
- intros x y z. apply CReq_nlt, Rmul_assoc. |
| 169 |
- intros x y z. apply CReq_nlt, Rdistr_l. |
| 170 |
- intros x y. apply CReq_nlt, Rsub_def. |
| 171 |
- intro x. apply CReq_nlt, Ropp_def. |
| 172 |
Qed. |
| 173 |
|
| 174 |
Lemma CR_ring_ext_nlt : ring_eq_ext CRplus CRmult CRopp |
| 175 |
(fun x y : CR => |
| 176 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\ |
| 177 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) x y). |
| 178 |
Proof. |
| 179 |
split. |
| 180 |
- intros x y H z t H0. |
| 181 |
apply CReq_nlt. |
| 182 |
apply CReq_nlt in H. |
| 183 |
apply CReq_nlt in H0. |
| 184 |
rewrite H, H0. reflexivity. |
| 185 |
- intros x y H z t H0. |
| 186 |
apply CReq_nlt. |
| 187 |
apply CReq_nlt in H. |
| 188 |
apply CReq_nlt in H0. |
| 189 |
rewrite H, H0. reflexivity. |
| 190 |
- intros x y H. |
| 191 |
apply CReq_nlt. |
| 192 |
apply CReq_nlt in H. |
| 193 |
rewrite H. reflexivity. |
| 194 |
Qed. |
| 195 |
|
| 196 |
Lemma CRmult_inv_r_nlt : (forall (r : CR) |
| 197 |
(rnz : (fun x y : CR => ((x < y)%CR + (y < x)%CR)%type) r 0%CR), |
| 198 |
(fun x y : CR => |
| 199 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\ |
| 200 |
(fun x0 y0 : CR => (y0 < x0)%CR -> False) x y) |
| 201 |
(CRinvT r rnz * r)%CR 1%CR). |
| 202 |
Proof. |
| 203 |
intros. apply CReq_nlt. |
| 204 |
rewrite CRmult_comm. apply CRmult_inv_r. |
| 205 |
Qed. |
| 206 |
|
| 207 |
Definition CRup (x : CR) |
| 208 |
: {n : positive & (x < ' (Z.pos n # 1))%CR}. |
| 209 |
Proof. |
| 210 |
exists (match Qnum (proj1_sig (CR_b (1#1)%Qpos x)) with |
| 211 |
| Z0 => 1%positive |
| 212 |
| Zpos p => Pos.succ p |
| 213 |
| Zneg p => 1%positive end). |
| 214 |
apply (CRle_lt_trans _ _ _ (CR_b_upperBound (1#1)%Qpos x)). |
| 215 |
apply CRlt_Qlt. |
| 216 |
destruct (CR_b (1 # 1) x), x0. simpl. |
| 217 |
destruct Qnum. |
| 218 |
- reflexivity. |
| 219 |
- change (p*1 < Pos.succ p * Qden)%positive. |
| 220 |
apply (Pos.le_lt_trans _ (p * Qden)). |
| 221 |
apply Pos.mul_le_mono_l. apply Pos.le_1_l. |
| 222 |
apply Pos.mul_lt_mono_r. |
| 223 |
apply Pos.lt_succ_diag_r. |
| 224 |
- reflexivity. |
| 225 |
Qed. |
| 226 |
|
| 227 |
Lemma CRabs_nlt : forall x y : CR, |
| 228 |
(((y < x)%CR -> False) /\ ((y < -x)%CR -> False)) |
| 229 |
<-> ((y < CRabs x)%CR -> False). |
| 230 |
Proof. |
| 231 |
split. |
| 232 |
- intros [H H0] H1. |
| 233 |
apply CRle_not_lt in H1. contradiction. clear H2 H1. |
| 234 |
pose proof (CRdistance_CRle y x 0%CR) as [H2 _]. |
| 235 |
unfold CRdistance in H2. rewrite CRopp_0, CRplus_0_r in H2. |
| 236 |
apply H2. clear H2. split. |
| 237 |
apply (CRplus_le_r _ _ y). |
| 238 |
apply CRle_not_lt in H. |
| 239 |
ring_simplify. exact H. |
| 240 |
apply CRle_not_lt in H0. |
| 241 |
rewrite (CRplus_le_r _ _ x) in H0. |
| 242 |
ring_simplify in H0. exact H0. |
| 243 |
- split. |
| 244 |
apply CRle_not_lt in H. |
| 245 |
apply CRle_not_lt. |
| 246 |
apply (@CRle_trans _ (CRabs x)). 2: exact H. |
| 247 |
apply CRle_abs. |
| 248 |
apply CRle_not_lt in H. |
| 249 |
apply CRle_not_lt. |
| 250 |
apply (@CRle_trans _ (CRabs x)). 2: exact H. |
| 251 |
rewrite <- CRabs_opp. |
| 252 |
apply CRle_abs. |
| 253 |
Qed. |
| 254 |
|
| 255 |
Definition CRcauchy_sequence (xn : nat -> CR) : Set |
| 256 |
:= forall p : positive, |
| 257 |
{n : nat |
| 258 |
| forall i j : nat, |
| 259 |
(n <= i)%nat -> |
| 260 |
(n <= j)%nat -> (' (1 # p) < CRabs (xn i - xn j))%CR -> False}. |
| 261 |
|
| 262 |
Lemma Qarchimedean_le : forall q : Q, { p : positive | q <= Z.pos p # 1 }. |
| 263 |
Proof. |
| 264 |
intros. destruct q as [a b]. destruct a. |
| 265 |
- exists xH. discriminate. |
| 266 |
- exists p. unfold Qle; simpl. |
| 267 |
apply Pos.mul_le_mono_l, Pos.le_1_l. |
| 268 |
- exists xH. discriminate. |
| 269 |
Defined. |
| 270 |
|
| 271 |
Definition CRstandard_modulus (xn : nat -> CR) |
| 272 |
(xncau : CRcauchy_sequence xn) |
| 273 |
(e : QposInf) : CR |
| 274 |
:= match e with |
| 275 |
| Qpos2QposInf q |
| 276 |
=> xn (proj1_sig (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig q))))) |
| 277 |
| QposInfinity => 0%CR |
| 278 |
end. |
| 279 |
|
| 280 |
Lemma CRstandard_regular : forall (xn : nat -> CR) |
| 281 |
(xncau : CRcauchy_sequence xn), |
| 282 |
is_RegularFunction (@ball CR) (CRstandard_modulus xn xncau). |
| 283 |
Proof. |
| 284 |
intros xn xncau e1 e2. |
| 285 |
apply CRabs_ball. unfold CRstandard_modulus. |
| 286 |
destruct (le_ge_dec |
| 287 |
(proj1_sig (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig e1))))) |
| 288 |
(proj1_sig (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig e2)))))). |
| 289 |
- destruct (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig e1)))) as [n H]. |
| 290 |
simpl in l. |
| 291 |
destruct e1 as [e1 e1pos]. |
| 292 |
destruct e2 as [e2 e2pos]. |
| 293 |
unfold proj1_sig. specialize (H n _ (Nat.le_refl _) l). |
| 294 |
apply CRle_not_lt in H. |
| 295 |
apply (CRle_trans H). clear H. |
| 296 |
apply CRle_Qle. unfold proj1_sig. |
| 297 |
destruct (Qarchimedean_le (/ e1)) as [p H]. |
| 298 |
apply (Qle_trans _ (e1+0)). |
| 299 |
2: apply Qplus_le_r, Qlt_le_weak, e2pos. |
| 300 |
rewrite Qplus_0_r. |
| 301 |
apply (Qmult_le_l _ _ e1) in H. 2: exact e1pos. |
| 302 |
rewrite Qmult_inv_r in H. |
| 303 |
change (1#p) with (/(Z.pos p#1)). |
| 304 |
apply Qle_shift_inv_r. reflexivity. |
| 305 |
apply H. |
| 306 |
apply (Qpos_nonzero (exist _ e1 e1pos)). |
| 307 |
- destruct (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig e2)))) as [n H]. |
| 308 |
simpl in g. |
| 309 |
destruct e1 as [e1 e1pos]. |
| 310 |
destruct e2 as [e2 e2pos]. |
| 311 |
unfold proj1_sig. specialize (H _ n g (Nat.le_refl _)). |
| 312 |
apply CRle_not_lt in H. |
| 313 |
apply (CRle_trans H). clear H. |
| 314 |
apply CRle_Qle. unfold proj1_sig. |
| 315 |
destruct (Qarchimedean_le (/ e2)) as [p H]. |
| 316 |
apply (Qle_trans _ (0+e2)). |
| 317 |
2: apply Qplus_le_l, Qlt_le_weak, e1pos. |
| 318 |
rewrite Qplus_0_l. |
| 319 |
apply (Qmult_le_l _ _ e2) in H. 2: exact e2pos. |
| 320 |
rewrite Qmult_inv_r in H. |
| 321 |
change (1#p) with (/(Z.pos p#1)). |
| 322 |
apply Qle_shift_inv_r. reflexivity. |
| 323 |
apply H. |
| 324 |
apply (Qpos_nonzero (exist _ e2 e2pos)). |
| 325 |
Qed. |
| 326 |
|
| 327 |
Lemma CRcauchy_complete : forall xn : nat -> CR, |
| 328 |
CRcauchy_sequence xn -> |
| 329 |
{l : CR & |
| 330 |
forall p : positive, |
| 331 |
{n : nat |
| 332 |
| forall i : nat, |
| 333 |
(n <= i)%nat -> (' (1 # p) < CRabs (xn i - l))%CR -> False}}. |
| 334 |
Proof. |
| 335 |
intros xn xncau. |
| 336 |
exists (Cjoin_fun (Build_RegularFunction (CRstandard_regular xn xncau))). |
| 337 |
intro p. |
| 338 |
exists (proj1_sig (xncau (2*p)%positive)). |
| 339 |
intros i H. apply CRle_not_lt. |
| 340 |
apply (CRle_trans (CRdistance_triangle _ (CRstandard_modulus xn xncau (Qpos2QposInf (1#2*p))) _)). |
| 341 |
apply (@CRle_trans _ ('(1#2*p) + '(1#2*p))%CR). |
| 342 |
apply CRplus_le_compat. |
| 343 |
- simpl. |
| 344 |
destruct (xncau (2*p)%positive) as [n H0] eqn:des. |
| 345 |
apply CRle_not_lt. apply H0. |
| 346 |
exact H. clear H i. |
| 347 |
simpl in des. rewrite des. apply Nat.le_refl. |
| 348 |
- apply CRabs_ball, ball_sym. |
| 349 |
apply (Cjoin_ball (Build_RegularFunction (CRstandard_regular xn xncau)) |
| 350 |
(1#2*p)). |
| 351 |
- rewrite CRplus_Qplus. |
| 352 |
apply CRle_Qle. |
| 353 |
rewrite Qinv_plus_distr. |
| 354 |
apply Z.le_refl. |
| 355 |
Qed. |
| 356 |
|
| 357 |
Definition FastRealsConstructive : ConstructiveReals |
| 358 |
:= Build_ConstructiveReals |
| 359 |
(RegularFunction Qball) |
| 360 |
CRltT CRltT_linear CRlt |
| 361 |
(fun x y => fst (CR_lt_ltT x y)) |
| 362 |
(fun x y => snd (CR_lt_ltT x y)) |
| 363 |
CRlt_or_epsilon |
| 364 |
inject_Q_CR CRlt_Qlt Qlt_from_CRlt |
| 365 |
CRplus CRopp CRmult |
| 366 |
inject_Q_CR_plus inject_Q_CR_mult |
| 367 |
CR_ring_nlt CR_ring_ext_nlt |
| 368 |
(CRlt_Qlt 0 1 eq_refl) |
| 369 |
(fun r r1 r2 => fst (CRplus_lt_l r1 r2 r)) |
| 370 |
(fun r r1 r2 => snd (CRplus_lt_l r1 r2 r)) |
| 371 |
CRmult_lt_0_compat CRinvT |
| 372 |
CRmult_inv_r_nlt CRinv_0_lt_compat |
| 373 |
CRlt_Qmid CRup CRabs CRabs_nlt |
| 374 |
CRcauchy_complete. |