| 1 |
Require Import CoRN.algebra.RSetoid. |
| 2 |
Require Import CoRN.metric2.Metric. |
| 3 |
Require Import CoRN.metric2.UniformContinuity. |
| 4 |
Require |
| 5 |
MathClasses.implementations.stdlib_rationals MathClasses.implementations.positive_semiring_elements. |
| 6 |
From Coq Require Import Program. |
| 7 |
Require Import CoRN.model.totalorder.QposMinMax |
| 8 |
MathClasses.misc.workaround_tactics |
| 9 |
CoRN.stdlib_omissions.Q CoRN.util.Qdlog CoRN.model.metric2.Qmetric. |
| 10 |
From Coq Require Import Qabs. |
| 11 |
Require Import CoRN.classes.Qclasses CoRN.model.totalorder.QMinMax |
| 12 |
CoRN.algebra.RSetoid CoRN.metric2.MetricMorphisms |
| 13 |
MathClasses.orders.minmax MathClasses.orders.dec_fields MathClasses.theory.abs MathClasses.theory.shiftl MathClasses.theory.int_pow. |
| 14 |
Require Export |
| 15 |
MathClasses.interfaces.abstract_algebra MathClasses.interfaces.additional_operations MathClasses.interfaces.orders. |
| 16 |
|
| 17 |
(* We describe the approximate rationals as a ring that is dense in the rationals *) |
| 18 |
|
| 19 |
(* Because [Q] is ``hard-wired'' nearly everywhere in CoRN, we take the easy |
| 20 |
way and require all operations to be sound with respect to [Q]. *) |
| 21 |
Class AppDiv AQ := app_div : AQ → AQ → Z → AQ. |
| 22 |
Class AppApprox AQ := app_approx : AQ → Z → AQ. |
| 23 |
|
| 24 |
Class AppRationals AQ {e plus mult zero one inv} `{Apart AQ} `{Le AQ} `{Lt AQ} |
| 25 |
{AQtoQ : Cast AQ Q_as_MetricSpace} |
| 26 |
`{!AppInverse AQtoQ} {ZtoAQ : Cast Z AQ} `{!AppDiv AQ} `{!AppApprox AQ} |
| 27 |
`{!Abs AQ} `{!Pow AQ N} `{!ShiftL AQ Z} |
| 28 |
`{∀ x y : AQ, Decision (x = y)} `{∀ x y : AQ, Decision (x ≤ y)} : Prop := { |
| 29 |
aq_ring :: @Ring AQ e plus mult zero one inv ; |
| 30 |
aq_trivial_apart :: TrivialApart AQ ; |
| 31 |
aq_order_embed :: OrderEmbedding AQtoQ ; |
| 32 |
aq_strict_order_embed :: StrictOrderEmbedding AQtoQ ; |
| 33 |
aq_ring_morphism :: SemiRing_Morphism AQtoQ ; |
| 34 |
aq_dense_embedding :: DenseEmbedding AQtoQ ; |
| 35 |
aq_div : ∀ x y k, ball (2 ^ k) ('app_div x y k) ('x / 'y) ; |
| 36 |
aq_compress : ∀ x k, ball (2 ^ k) ('app_approx x k) ('x) ; |
| 37 |
aq_shift :: ShiftLSpec AQ Z (≪) ; |
| 38 |
aq_nat_pow :: NatPowSpec AQ N (^) ; |
| 39 |
aq_ints_mor :: SemiRing_Morphism ZtoAQ |
| 40 |
}. |
| 41 |
|
| 42 |
Lemma order_embedding_iff `{OrderEmbedding A B f} x y : |
| 43 |
x ≤ y ↔ f x ≤ f y. |
| 44 |
Proof. firstorder. Qed. |
| 45 |
|
| 46 |
|
| 47 |
Lemma strict_order_embedding_iff `{StrictOrderEmbedding A B f} x y : |
| 48 |
x < y ↔ f x < f y. |
| 49 |
Proof. firstorder. Qed. |
| 50 |
|
| 51 |
Section approximate_rationals_more. |
| 52 |
Context `{AppRationals AQ}. |
| 53 |
|
| 54 |
Lemma AQtoQ_ZtoAQ (x : Z) : cast AQ Q (cast Z AQ x) = cast Z Q x. |
| 55 |
Proof. now apply (integers.to_ring_twice _ _ _). Qed. |
| 56 |
|
| 57 |
Global Instance: Injective (cast AQ Q). |
| 58 |
Proof. |
| 59 |
destruct dense_injective. |
| 60 |
split. 2: apply _. |
| 61 |
intros. apply (injective x y). |
| 62 |
unfold equiv. simpl. |
| 63 |
rewrite H5. reflexivity. |
| 64 |
Qed. |
| 65 |
|
| 66 |
Global Instance: StrongSetoid AQ. |
| 67 |
Proof strong_setoids.dec_strong_setoid. |
| 68 |
|
| 69 |
Global Instance: StrongSetoid_Morphism (cast AQ Q). |
| 70 |
Proof strong_setoids.dec_strong_morphism (cast AQ Q). |
| 71 |
|
| 72 |
Global Instance: StrongInjective (cast AQ Q). |
| 73 |
Proof strong_setoids.dec_strong_injective (cast AQ Q). |
| 74 |
|
| 75 |
Global Instance: Injective (cast Z AQ). |
| 76 |
Proof. |
| 77 |
split; try apply _. |
| 78 |
intros x y E. |
| 79 |
apply (injective (cast Z Q)). |
| 80 |
rewrite <-2!AQtoQ_ZtoAQ. |
| 81 |
now rewrite E. |
| 82 |
Qed. |
| 83 |
|
| 84 |
Global Instance: FullPseudoSemiRingOrder (_ : Le AQ) (_ : Lt AQ). |
| 85 |
Proof. |
| 86 |
apply (projected_full_pseudo_ring_order (cast AQ Q)). |
| 87 |
apply order_embedding_iff. |
| 88 |
apply strict_order_embedding_iff. |
| 89 |
Qed. |
| 90 |
|
| 91 |
Lemma aq_opp : forall (x : AQ), '(-x) = -'x. |
| 92 |
Proof. |
| 93 |
intro x. |
| 94 |
apply (Qplus_inj_l _ _ ('x)). |
| 95 |
rewrite Qplus_opp_r. |
| 96 |
assert ('zero0 = 0%Q) by (apply rings.preserves_0). |
| 97 |
rewrite <- H5. |
| 98 |
destruct aq_ring_morphism. |
| 99 |
destruct semiringmor_plus_mor. |
| 100 |
destruct monmor_sgmor. |
| 101 |
rewrite <- preserves_sg_op. |
| 102 |
destruct sgmor_setmor. |
| 103 |
apply sm_proper. |
| 104 |
unfold equiv. |
| 105 |
destruct aq_ring, ring_group. |
| 106 |
destruct abgroup_group. |
| 107 |
apply negate_r. |
| 108 |
Qed. |
| 109 |
|
| 110 |
Lemma aq_shift_correct (x : AQ) (k : Z) : '(x ≪ k) = 'x * 2 ^ k. |
| 111 |
Proof. rewrite preserves_shiftl. apply shiftl_int_pow. Qed. |
| 112 |
|
| 113 |
Lemma aq_shift_1_correct (k : Z) : '((1:AQ) ≪ k) = 2 ^ k. |
| 114 |
Proof. now rewrite aq_shift_correct, rings.preserves_1, rings.mult_1_l. Qed. |
| 115 |
|
| 116 |
Lemma aq_shift_opp_1 (x : AQ) : '(x ≪ (-1 : Z)) = 'x / 2. |
| 117 |
Proof. now rewrite aq_shift_correct. Qed. |
| 118 |
|
| 119 |
Lemma aq_shift_opp_2 (x : AQ) : '(x ≪ (-2 : Z)) = 'x / 4. |
| 120 |
Proof. now rewrite aq_shift_correct. Qed. |
| 121 |
|
| 122 |
Lemma aq_div_dlog2 (x y : AQ) (ε : Q₊) : |
| 123 |
ball (proj1_sig ε) ('app_div x y (Qdlog2 ('ε))) ('x / 'y). |
| 124 |
Proof. |
| 125 |
eapply ball_weak_le. |
| 126 |
now apply Qpos_dlog2_spec. |
| 127 |
now apply aq_div. |
| 128 |
Qed. |
| 129 |
|
| 130 |
Lemma aq_approx_dlog2 (x : AQ) (ε : Q₊) : |
| 131 |
ball (proj1_sig ε) ('app_approx x (Qdlog2 ('ε))) ('x). |
| 132 |
Proof. |
| 133 |
eapply ball_weak_le. |
| 134 |
now apply Qpos_dlog2_spec. |
| 135 |
now apply aq_compress. |
| 136 |
Qed. |
| 137 |
|
| 138 |
Definition app_div_above (x y : AQ) (k : Z) : AQ := app_div x y k + 1 ≪ k. |
| 139 |
|
| 140 |
Lemma aq_div_above (x y : AQ) (k : Z) : ('x / 'y : Q) ≤ 'app_div_above x y k. |
| 141 |
Proof. |
| 142 |
unfold app_div_above. |
| 143 |
pose proof (aq_div x y k) as P. |
| 144 |
apply in_Qball in P. destruct P as [_ P]. |
| 145 |
rewrite rings.preserves_plus. |
| 146 |
rewrite aq_shift_correct. |
| 147 |
now rewrite rings.preserves_1, left_identity. |
| 148 |
Qed. |
| 149 |
|
| 150 |
Global Instance: IntegralDomain AQ. |
| 151 |
Proof. |
| 152 |
split; try apply _. |
| 153 |
intros E. |
| 154 |
destruct (rings.is_ne_0 (1%mc:Q)). |
| 155 |
rewrite <-(rings.preserves_1 (f:=cast AQ Q)). |
| 156 |
rewrite <-(rings.preserves_0 (f:=cast AQ Q)). |
| 157 |
now rewrite E. |
| 158 |
intros x [? [y [? E]]]. |
| 159 |
destruct (no_zero_divisors ('x : Q)). split. |
| 160 |
now apply rings.injective_ne_0. |
| 161 |
exists ('y : Q). split. |
| 162 |
now apply rings.injective_ne_0. |
| 163 |
rewrite <-rings.preserves_mult, E. |
| 164 |
apply rings.preserves_0. |
| 165 |
Qed. |
| 166 |
|
| 167 |
Lemma aq_lt_mid (x y : Q) : (x < y)%Q → { z : AQ | (x < 'z ∧ 'z < y)%Q }. |
| 168 |
Proof with auto with qarith. |
| 169 |
intros E. |
| 170 |
destruct (Qpos_sub _ _ E) as [γ Eγ]. |
| 171 |
(* We need to pick a rational [x] such that [x < 1#2]. Since we do not |
| 172 |
use this lemma for computations yet, we just pick [1#3]. However, |
| 173 |
whenever we will it might be worth to reconsider. *) |
| 174 |
exists (app_inverse (cast AQ Q) ((1#2) * (x + y)) ((1#3) * γ)%Qpos)%Q. |
| 175 |
split. |
| 176 |
apply Qlt_le_trans with (x + (1#6) * proj1_sig γ)%Q. |
| 177 |
rewrite <-(rings.plus_0_r x) at 1. |
| 178 |
apply Qplus_lt_r... |
| 179 |
assert (Qeq (x + (1 # 6) * ` γ) |
| 180 |
((1 # 2) * (x + y) - proj1_sig ((1 # 3) * γ)%Qpos)%Q). |
| 181 |
{ rewrite Eγ. simpl. ring. } |
| 182 |
rewrite H5. clear H5. |
| 183 |
simpl. |
| 184 |
apply (in_Qball (proj1_sig ((1#3)*γ)%Qpos)), ball_sym, dense_inverse. |
| 185 |
apply Qle_lt_trans with (y - (1#6) * proj1_sig γ)%Q. |
| 186 |
assert (Qeq (y - (1 # 6) * ` γ) |
| 187 |
((1 # 2) * (x + y) + proj1_sig ((1 # 3) * γ)%Qpos)). |
| 188 |
{ rewrite Eγ. simpl. ring. } |
| 189 |
rewrite H5. clear H5. simpl. |
| 190 |
apply (in_Qball (proj1_sig ((1#3)*γ)%Qpos)), ball_sym, dense_inverse. |
| 191 |
apply (Qlt_le_trans _ (y-0)). |
| 192 |
apply Qplus_lt_r. |
| 193 |
apply Qopp_Qlt_0_r... |
| 194 |
unfold Qminus. rewrite Qplus_0_r. apply Qle_refl. |
| 195 |
Defined. |
| 196 |
|
| 197 |
Instance: MeetSemiLattice_Morphism (cast AQ Q). |
| 198 |
Proof. |
| 199 |
split; try apply _; apply lattices.order_preserving_meet_sl_mor. |
| 200 |
Qed. |
| 201 |
|
| 202 |
Instance: JoinSemiLattice_Morphism (cast AQ Q). |
| 203 |
Proof. |
| 204 |
split; try apply _; apply lattices.order_preserving_join_sl_mor. |
| 205 |
Qed. |
| 206 |
|
| 207 |
Lemma aq_preserves_min x y : '(x ⊓ y) = Qmin ('x) ('y). |
| 208 |
Proof. |
| 209 |
rewrite lattices.preserves_meet; symmetry; apply Qmin_coincides. |
| 210 |
Qed. |
| 211 |
|
| 212 |
Lemma aq_preserves_max x y : '(x ⊔ y) = Qmax ('x) ('y). |
| 213 |
Proof. |
| 214 |
rewrite lattices.preserves_join; symmetry; apply Qmax_coincides. |
| 215 |
Qed. |
| 216 |
|
| 217 |
Global Program Instance AQposAsQ: Cast (AQ₊) Q := cast AQ Q ∘ cast (AQ₊) AQ. |
| 218 |
|
| 219 |
Global Program Instance AQposAsQpos: Cast (AQ₊) (Q₊) := λ x, ('x : Q). |
| 220 |
Next Obligation. |
| 221 |
destruct x as [x Ex]. simpl. |
| 222 |
posed_rewrite <-(rings.preserves_0 (f:=cast AQ Q)). |
| 223 |
now apply (strictly_order_preserving (cast AQ Q)). |
| 224 |
Qed. |
| 225 |
|
| 226 |
Lemma AQposAsQpos_preserves_1 : cast (AQ₊) (Q₊) 1 = 1. |
| 227 |
Proof. change (cast AQ Q 1 = 1). apply rings.preserves_1. Qed. |
| 228 |
|
| 229 |
Lemma AQposAsQpos_preserves_4 : cast (AQ₊) (Q₊) 4 = 4. |
| 230 |
Proof. change (cast AQ Q 4 = 4). apply rings.preserves_4. Qed. |
| 231 |
End approximate_rationals_more. |