Debian Codegraph @

reals/fast/ContinuousCorrect.v

raw
1 (*
2 Copyright © 2006-2008 Russell O’Connor
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this proof and associated documentation files (the "Proof"), to deal in
6 the Proof without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8 the Proof, and to permit persons to whom the Proof is furnished to do so,
9 subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Proof.
13
14 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
20 *)
21 Require Import CoRN.algebra.RSetoid.
22 Require Import CoRN.metric2.Metric.
23 Require Import CoRN.metric2.UniformContinuity.
24 Require Export CoRN.reals.Q_in_CReals.
25 Require Export CoRN.ftc.MoreIntervals.
26 Require Export CoRN.reals.fast.CRIR.
27 Require Import CoRN.tactics.CornTac.
28 Require Export CoRN.model.metric2.Qmetric.
29 Require Export CoRN.model.totalorder.QposMinMax.
30
31 Opaque CR inj_Q.
32
33 Set Implicit Arguments.
34
35 Local Open Scope uc_scope.
36 (**
37 ** Correctness of continuous functions.
38 We show that if two functions, one on IR and one on CR, agree on the
39 rational values of some closed interval, and both functions are continuous,
40 then the two functions agree on that entire closed interval.
41
42 This is our main method of proving the corrections of functions defined
43 on CR.
44 *)
45 Lemma Q_dense_in_compact : forall a b (Hab : a[<=]b) x, a[<]b -> Compact Hab x ->
46 forall e, [0][<]e -> {q:Q | Compact Hab (inj_Q IR q) | AbsSmall e (x[-]inj_Q IR q)}.
47 Proof.
48 intros a b Hab x Hab0 Hx e He.
49 set (l:=Max a (x[-]e)).
50 set (r:=Min b (x[+]e)).
51 assert (Hlr:l[<]r).
52 destruct Hx as [Hx0 Hx1].
53 apply less_Min; apply Max_less.
54 assumption.
55 apply shift_minus_less.
56 rstepl (x[+][0]).
57 apply plus_resp_leEq_less; assumption.
58 rstepl (a[+][0]).
59 apply plus_resp_leEq_less; assumption.
60 apply shift_zero_less_minus'.
61 rstepr (e[+]e).
62 apply plus_resp_pos; assumption.
63 destruct (Q_dense_in_CReals' _ _ _ Hlr) as [q Hlq Hqr].
64 exists q; split.
65 eapply leEq_transitive.
66 apply lft_leEq_Max.
67 apply less_leEq; unfold l in Hlq; apply Hlq.
68 eapply leEq_transitive.
69 apply less_leEq;apply Hqr.
70 apply Min_leEq_lft.
71 apply shift_zero_leEq_minus'.
72 rstepr ((x[+]e)[-]inj_Q IR q).
73 apply shift_zero_leEq_minus.
74 eapply leEq_transitive.
75 apply less_leEq.
76 apply Hqr.
77 apply Min_leEq_rht.
78 apply shift_zero_leEq_minus'.
79 rstepr (inj_Q IR q[-](x[-]e)).
80 apply shift_zero_leEq_minus.
81 eapply leEq_transitive.
82 apply rht_leEq_Max.
83 apply less_leEq.
84 unfold l in Hlq; apply Hlq.
85 Qed.
86
87 Section ContinuousCorrect.
88
89 Variable I : interval.
90 Hypothesis HI : proper I.
91
92 Variable f : PartFunct IR.
93 Hypothesis Hf : Continuous I f.
94
95 Variable g : CR --> CR.
96 Hypothesis Hg : forall (q:Q) Hq,
97 I (inj_Q IR q) -> (g (' q) == IRasCR (f (inj_Q IR q) Hq))%CR.
98
99 Lemma ContinuousCorrect : forall (x:IR) Hx,
100 I x -> (IRasCR (f x Hx) == g (IRasCR x))%CR.
101 Proof.
102 intros x Hx H.
103 set (J:=compact_in_interval I HI x H).
104 apply ball_eq.
105 intros e epos.
106 assert (HJ:compact_ J) by apply compact_compact_in_interval.
107 destruct Hf as [Hf1 Hf0].
108 clear Hf.
109 assert (X:Continuous_I (Lend_leEq_Rend J HJ) f).
110 apply Hf0.
111 eapply included_trans;[|apply included_compact_in_interval].
112 unfold J; apply iprop_compact_in_interval_inc1.
113 clear Hf0.
114 destruct X as [_ X].
115 assert (He : [0][<](inj_Q IR (proj1_sig ((1#2)*exist _ _ epos)%Qpos))).
116 stepl (inj_Q IR (nring 0)); [| now apply (inj_Q_nring IR 0)].
117 apply inj_Q_less.
118 apply Qpos_ispos.
119 destruct (X _ He) as [d0 Hd0 Hf].
120 clear X.
121 set (d1:=mu g ((1#2)*exist _ _ epos)).
122 set (Hab := (Lend_leEq_Rend J HJ)) in *.
123 set (a:= (@Lend J HJ)) in *.
124 set (b:= (@Rend J HJ)) in *.
125 assert (HJ':included (Compact Hab) I).
126 eapply included_trans.
127 unfold Hab, a, b, J; apply iprop_compact_in_interval_inc1.
128 apply included_compact_in_interval.
129 assert (Hab0: a[<]b).
130 apply proper_compact_in_interval'.
131 assert (HJx:(Compact Hab) x).
132 apply iprop_compact_in_interval'.
133 clearbody Hab a b.
134 clear J HJ.
135 pose (d:=match d1 with | Qpos2QposInf q => Min (inj_Q IR (proj1_sig q)) d0 | QposInfinity => d0 end).
136 assert (H0d : [0][<]d).
137 destruct d1; try assumption.
138 apply less_Min; try assumption.
139 stepl (inj_Q IR [0]).
140 apply inj_Q_less.
141 apply Qpos_ispos.
142 apply (inj_Q_nring IR 0).
143 destruct (Q_dense_in_compact Hab0 HJx _ H0d) as [q Hq0 Hq1].
144 setoid_replace e
145 with (proj1_sig ((1#2)*exist _ _ epos+(1#2)*exist _ _ epos))%Qpos
146 by (simpl; ring).
147 assert (Hfq : Dom f (inj_Q IR q)).
148 apply Hf1.
149 apply HJ'.
150 assumption.
151 apply ball_triangle with (IRasCR (f (inj_Q IR q) Hfq)).
152 rewrite <- CRAbsSmall_ball.
153 stepr (IRasCR (f x Hx[-]f (inj_Q IR q) Hfq)); [| now (simpl; apply IR_minus_as_CR)].
154 stepl (IRasCR (inj_Q IR (proj1_sig ((1 # 2) * exist _ _ epos)%Qpos))); [| now (simpl; apply IR_inj_Q_as_CR)].
155 rewrite <- IR_AbsSmall_as_CR.
156 apply AbsIR_imp_AbsSmall.
157 apply Hf; try assumption.
158 eapply leEq_transitive.
159 apply AbsSmall_imp_AbsIR.
160 apply Hq1.
161 destruct d1.
162 apply Min_leEq_rht.
163 apply leEq_reflexive.
164 rewrite <- Hg;[|apply HJ';assumption].
165 apply uc_prf.
166 fold d1.
167 destruct d1; try constructor.
168 simpl.
169 rewrite <- IR_inj_Q_as_CR.
170 rewrite <- CRAbsSmall_ball.
171 stepr (IRasCR (inj_Q IR q[-]x)); [| now (simpl; apply IR_minus_as_CR)].
172 stepl (IRasCR (inj_Q IR (proj1_sig q0))); [| now (simpl; apply IR_inj_Q_as_CR)].
173 rewrite <- IR_AbsSmall_as_CR.
174 apply AbsSmall_minus.
175 eapply AbsSmall_leEq_trans;[|apply Hq1].
176 apply Min_leEq_lft.
177 Qed.
178
179 End ContinuousCorrect.