Debian Codegraph @

reals/stdlib/ConstructivePartialFunctions.v

raw
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
13 (*
14 Partial functions between two sets X and Y. They have domains of
15 definition which are subsets of X.
16 *)
17
18 From Coq Require Import List.
19 From Coq Require Import ZArith.
20 From Coq Require Import QArith.
21 From Coq Require Import ConstructiveReals.
22 From Coq Require Import ConstructiveAbs.
23 From Coq Require Import ConstructiveMinMax.
24 From Coq Require Import ConstructiveSum.
25 From Coq Require Import ConstructiveLimits.
26 From Coq Require Import ConstructiveRcomplete.
27
28 Local Open Scope ConstructiveReals.
29
30
31 (*
32 The type of real-valued partial functions on X. Partial means the
33 functions are defined only on subsets D of X, called their domains.
34
35 In classical logic, partial functions are useless for the theory
36 of integration, because a partial function X -> R can be extended
37 to all X by zeroes, with the same integral. However, in constructive
38 mathematics a function R -> R must be undefined at its points of
39 discontinuity.
40
41 Besides, we will prove that the domain of an integrable function
42 X -> R has full measure in X, ie it is the complement of a null
43 set of X.
44 *)
45 Record PartialFunctionXY {X Y : Set} {Yeq : Y -> Y -> Prop} : Type :=
46 {
47 Domain : X -> Set;
48 partialApply : forall x : X, Domain x -> Y;
49 DomainProp : forall (x : X) (p q : Domain x),
50 Yeq (partialApply x p) (partialApply x q);
51 }.
52
53 Definition PartialFunction {R : ConstructiveReals} (X : Set) : Type
54 := @PartialFunctionXY X (CRcarrier R) (CReq R).
55
56 Definition TotalizeFunc {R : ConstructiveReals} (X : Set)
57 (f : PartialFunction X)
58 (domainTotal : forall x:X, Domain f x)
59 : X -> CRcarrier R
60 := fun x => partialApply f x (domainTotal x).
61
62 Definition PartializeFunc {R : ConstructiveReals} (X : Set)
63 (f : X -> CRcarrier R) : PartialFunction X
64 := Build_PartialFunctionXY
65 X (CRcarrier R) (CReq R) (fun x:X => True) (fun x _ => f x)
66 (fun x _ _ => CReq_refl (f x)).
67
68 Record CommonPointFunSeq {R : ConstructiveReals}
69 (X : Set) (f : @PartialFunction R X)
70 (fn : nat -> @PartialFunction R X) : Set
71 := {
72 cpx : X;
73 cpxF : Domain f cpx;
74 cpxFn : forall n:nat, Domain (fn n) cpx;
75 }.
76
77 (* We have a major use of the sort Set for integration, that could not be
78 done with Ensemble X : the domain of the pointwise limit of a
79 sequence of functions. The limit is stored at each point in sort Set,
80 so that we can form the (partial) limit function. *)
81 Definition XpointwiseLimit {R : ConstructiveReals}
82 {X : Set} (fn : nat -> @PartialFunction R X)
83 : @PartialFunction R X.
84 Proof.
85 apply (Build_PartialFunctionXY
86 X (CRcarrier R) (CReq R)
87 (* x is in all domains and the sequence converges *)
88 (fun x:X => { xnlim : (forall n:nat, Domain (fn n) x)
89 & CR_cauchy _ (fun n:nat => partialApply (fn n) x (xnlim n)) })
90 (fun x p
91 => let (xnlim, cau) := p in
92 let (c,d) := CR_complete R _ cau in c)).
93 intros. destruct p,q.
94 destruct (CR_complete R (fun n : nat => partialApply (fn n) x (x0 n)) c).
95 destruct (CR_complete R (fun n : nat => partialApply (fn n) x (x1 n)) c0).
96 apply (CR_cv_unique (fun n : nat => partialApply (fn n) x (x0 n))).
97 exact c1. apply (CR_cv_eq _ (fun n : nat => partialApply (fn n) x (x1 n))).
98 2: exact c2. intro n. apply DomainProp.
99 Defined.
100
101 Lemma applyPointwiseLimit
102 : forall {R : ConstructiveReals} {X : Set}
103 (fn : nat -> PartialFunction X)
104 (x : X)
105 (xD : Domain (XpointwiseLimit fn) x)
106 (a : CRcarrier R),
107 prod (partialApply (XpointwiseLimit fn) x xD == a
108 -> CR_cv _ (fun n => partialApply (fn n) x
109 (let (xn, _) := xD in xn n))
110 a)
111 (CR_cv _ (fun n => partialApply (fn n) x
112 (let (xn, _) := xD in xn n))
113 a
114 -> partialApply (XpointwiseLimit fn) x xD == a).
115 Proof.
116 intros. simpl. destruct xD.
117 destruct (CR_complete R (fun n : nat => partialApply (fn n) x (x0 n)) c).
118 split.
119 - intros. exact (CR_cv_proper _ x1 a c0 H).
120 - intros.
121 apply (CR_cv_unique (fun n : nat => partialApply (fn n) x (x0 n))).
122 exact c0. exact H.
123 Qed.
124
125 Definition XinfiniteSumAbs {R : ConstructiveReals} {X : Set}
126 (fn : nat -> @PartialFunction R X)
127 : @PartialFunction R X.
128 Proof.
129 apply (Build_PartialFunctionXY
130 X (CRcarrier R) (CReq R)
131 (* x is in all domains and the series converges *)
132 (fun x:X => { xnlim : (forall n:nat, Domain (fn n) x)
133 & CR_cauchy _ (CRsum (fun n:nat => CRabs _ (partialApply (fn n) x (xnlim n)))) })
134 (fun x p
135 => let (xnlim, cau) := p in
136 let (c,d) := series_cv_abs _ cau in c)).
137 intros. destruct p,q.
138 destruct (series_cv_abs (fun n : nat => partialApply (fn n) x (x0 n)) c).
139 destruct (series_cv_abs (fun n : nat => partialApply (fn n) x (x1 n)) c0).
140 apply (CR_cv_unique (CRsum (fun n : nat => partialApply (fn n) x (x0 n)))).
141 exact s. apply (series_cv_eq (fun n : nat => partialApply (fn n) x (x1 n))).
142 2: exact s0. intro n. apply DomainProp.
143 Defined.
144
145 Definition domainInfiniteSumAbsInc {R : ConstructiveReals} {X : Set}
146 (fn : nat -> PartialFunction X)
147 (x : X)
148 (xnD : forall n:nat, Domain (fn n) x)
149 (lim : CRcarrier R)
150 : series_cv (fun n => CRabs _ (partialApply (fn n) x (xnD n))) lim
151 -> Domain (XinfiniteSumAbs fn) x.
152 Proof.
153 intros cvlim. exists xnD.
154 apply (Rcv_cauchy_mod _ lim cvlim).
155 Qed.
156
157 Definition domainInfiniteSumAbsIncReverse
158 {R : ConstructiveReals} {X : Set} (fn : nat -> @PartialFunction R X) (x : X)
159 : Domain (XinfiniteSumAbs fn) x
160 -> forall n:nat, Domain (fn n) x
161 := fun xD n => let (xn, _) := xD in xn n.
162
163 Lemma applyInfiniteSumAbs
164 : forall {R : ConstructiveReals} (X : Set)
165 (fn : nat -> PartialFunction X)
166 (x : X)
167 (xD : Domain (XinfiniteSumAbs fn) x)
168 (a : CRcarrier R),
169 prod (partialApply (XinfiniteSumAbs fn) x xD == a
170 -> series_cv (fun n => partialApply (fn n) x
171 (domainInfiniteSumAbsIncReverse fn x xD n))
172 a)
173 (series_cv (fun n => partialApply (fn n) x
174 (domainInfiniteSumAbsIncReverse fn x xD n))
175 a
176 -> partialApply (XinfiniteSumAbs fn) x xD == a).
177 Proof.
178 intros. unfold domainInfiniteSumAbsIncReverse.
179 destruct xD. simpl.
180 destruct (series_cv_abs (fun n : nat => partialApply (fn n) x (x0 n))).
181 split.
182 - intros. exact (CR_cv_proper _ _ _ s H).
183 - intros.
184 apply (series_cv_unique (fun n : nat => partialApply (fn n) x (x0 n))); assumption.
185 Qed.
186
187 Definition DomainInclusion {R : ConstructiveReals} {X : Set}
188 (f g : @PartialFunction R X)
189 : Set (* Prop-like *)
190 := forall x:X, Domain f x -> Domain g x.
191
192 Definition PartialRestriction {R : ConstructiveReals} {X : Set}
193 (f g : @PartialFunction R X) : Type
194 := prod (DomainInclusion f g)
195 (forall (x : X) (xD : Domain f x) (xG : Domain g x),
196 partialApply f x xD == partialApply g x xG).
197
198 Definition PartialRestriction_refl
199 : forall {R : ConstructiveReals} (X : Set) (f : @PartialFunction R X),
200 PartialRestriction f f.
201 Proof.
202 split.
203 - exact (fun x a => a).
204 - intros. apply DomainProp.
205 Qed.
206
207 Definition PartialRestriction_trans
208 : forall {R : ConstructiveReals} (X : Set) (f g h : @PartialFunction R X),
209 PartialRestriction f g
210 -> PartialRestriction g h
211 -> PartialRestriction f h.
212 Proof.
213 intros R X f g h H H0. split.
214 - intros x H1. apply H0, H, H1.
215 - intros. destruct H, H0. rewrite <- (c0 x (d x xD)), <- (c x xD).
216 reflexivity.
217 Qed.
218
219 Definition PartialFunExtEq {R : ConstructiveReals} {X : Set}
220 (f g : @PartialFunction R X) : Set
221 := (DomainInclusion f g)
222 * (DomainInclusion g f)
223 * (forall (x : X) (xD : Domain f x) (xG : Domain g x),
224 partialApply f x xD == partialApply g x xG).
225
226 Definition Xconst {R : ConstructiveReals} (X : Set) (c : CRcarrier R)
227 : PartialFunction X
228 := Build_PartialFunctionXY
229 X (CRcarrier R) (CReq R) (fun x => True) (fun x _ => c)
230 (fun _ _ _ => CReq_refl c).
231
232 Definition XopXY (X Y : Set) (Yeq : Y -> Y -> Prop)
233 (f : @PartialFunctionXY X Y Yeq) (op : Y -> Y)
234 : (forall x y : Y, Yeq x y -> Yeq (op x) (op y))
235 -> @PartialFunctionXY X Y Yeq
236 := fun H => Build_PartialFunctionXY
237 X Y Yeq (Domain f) (fun x p => op (partialApply f x p))
238 (fun x p q => H _ _ (DomainProp f x p q)).
239
240 Definition Xop {R : ConstructiveReals} (X : Set) (f : PartialFunction X)
241 (op : CRcarrier R -> CRcarrier R)
242 : (forall x y : CRcarrier R, x == y -> op x == op y)
243 -> PartialFunction X
244 := fun H => Build_PartialFunctionXY
245 X (CRcarrier R) (CReq R) (Domain f) (fun x p => op (partialApply f x p))
246 (fun x p q => H _ _ (DomainProp f x p q)).
247
248 Definition Xabs {R : ConstructiveReals} {X : Set} (f : @PartialFunction R X)
249 : @PartialFunction R X
250 := Xop X f (CRabs R) (CRabs_morph_prop R).
251
252 Lemma applyXabs : forall {R : ConstructiveReals} {X : Set}
253 (f : PartialFunction X)
254 (x : X)
255 (xD : Domain f x),
256 partialApply (Xabs f) x xD
257 = CRabs R (partialApply f x xD).
258 Proof.
259 reflexivity.
260 Qed.
261
262 Definition Xscale {R : ConstructiveReals} {X : Set} (a : CRcarrier R)
263 (f : PartialFunction X) : PartialFunction X
264 := Xop X f (fun x => a * x)
265 (CRmult_morph R a a (CReq_refl a)).
266
267 Lemma applyXscale : forall {R : ConstructiveReals} {X : Set}
268 (f : PartialFunction X)
269 (a : CRcarrier R)
270 (x : X)
271 (xD : Domain f x),
272 partialApply (Xscale a f) x xD
273 = a * (partialApply f x xD).
274 Proof.
275 reflexivity.
276 Qed.
277
278 (* To intersect the domains of a sequence of functions,
279 we build the zero function on that intersection. *)
280 Definition Domain_intersect_countable {R : ConstructiveReals} {X : Set}
281 (fn : nat -> @PartialFunction R X)
282 : PartialFunction X
283 := XinfiniteSumAbs(fun n => Xscale 0 (fn n)).
284
285
286 Definition XbinOpXY (X Y : Set) (Yeq : Y -> Y -> Prop)
287 (f g : @PartialFunctionXY X Y Yeq) (op : Y -> Y -> Y)
288 : (forall x y z t : Y, Yeq x y -> Yeq z t -> Yeq (op x z) (op y t))
289 -> @PartialFunctionXY X Y Yeq.
290 Proof.
291 intros.
292 apply (Build_PartialFunctionXY
293 X Y Yeq
294 (fun x => prod (Domain f x) (Domain g x))
295 (fun x xD => let (a,b) := xD in op (partialApply f x a) (partialApply g x b))).
296 intros. destruct p,q. apply H.
297 - apply DomainProp.
298 - apply DomainProp.
299 Defined.
300
301 Definition XbinOp {R : ConstructiveReals} {X : Set} (f g : PartialFunction X)
302 (op : CRcarrier R -> CRcarrier R -> CRcarrier R)
303 (opEq : forall x y z t : CRcarrier R, x == y -> z == t -> op x z == op y t)
304 : PartialFunction X
305 := XbinOpXY X (CRcarrier R) (CReq R) f g op opEq.
306
307 (* This definition of the sum of partial functions will have
308 a major consequence on measure theory : all integrable
309 functions are defined almost everywhere. Otherwise the
310 intersection of domains could reduce the integral of the
311 sum of 2 functions. For example, if an integrable function
312 has R+ for domain, then the measure of R- is zero. *)
313 Definition Xplus {R : ConstructiveReals} {X : Set} (f g : PartialFunction X)
314 : PartialFunction X
315 := XbinOp f g (CRplus R)
316 (fun x y z t Hxy => CRplus_morph R x y Hxy z t).
317
318 Lemma applyXplus : forall {R : ConstructiveReals} {X : Set}
319 (f g : @PartialFunction R X)
320 (x : X)
321 (xdf : Domain f x)
322 (xdg : Domain g x),
323 partialApply (Xplus f g) x (pair xdf xdg)
324 == partialApply f x xdf + partialApply g x xdg.
325 Proof.
326 reflexivity.
327 Qed.
328
329 Definition Xminus {R : ConstructiveReals} {X : Set}
330 (f g : PartialFunction X) : PartialFunction X
331 := Xplus f (Xscale (CRopp R 1) g).
332
333 Lemma applyXminus : forall {R : ConstructiveReals} {X : Set}
334 (f g : @PartialFunction R X)
335 (x : X)
336 (xdf : Domain f x)
337 (xdg : Domain g x),
338 partialApply (Xminus f g) x (pair xdf xdg)
339 == partialApply f x xdf - partialApply g x xdg.
340 Proof.
341 intros. apply CRplus_morph. reflexivity.
342 rewrite applyXscale. rewrite <- CRopp_mult_distr_l.
343 rewrite CRmult_1_l. reflexivity.
344 Qed.
345
346 Definition Xmult {R : ConstructiveReals} {X : Set}
347 (f g : PartialFunction X) : PartialFunction X
348 := XbinOp f g (CRmult R)
349 (fun x y z t Hxy => CRmult_morph R x y Hxy z t).
350
351 Lemma applyXmult : forall {R : ConstructiveReals} {X : Set}
352 (f g : @PartialFunction R X)
353 (x : X)
354 (xdf : Domain f x)
355 (xdg : Domain g x),
356 partialApply (Xmult f g) x (pair xdf xdg)
357 == partialApply f x xdf * partialApply g x xdg.
358 Proof.
359 reflexivity.
360 Qed.
361
362 Definition XminConst {R : ConstructiveReals} {X : Set}
363 (f : @PartialFunction R X) (a : CRcarrier R) : PartialFunction X
364 := Xop X f (fun x => CRmin x a)
365 (fun x y Hxy => CRmin_morph _ x y Hxy a a (CReq_refl a)).
366
367 Lemma applyXminConst : forall {R : ConstructiveReals} {X : Set}
368 (f : PartialFunction X)
369 (a : CRcarrier R)
370 (x : X)
371 (xD : Domain f x),
372 partialApply (XminConst f a) x xD
373 = CRmin (partialApply f x xD) a.
374 Proof.
375 reflexivity.
376 Qed.
377
378 Definition XmaxConst {R : ConstructiveReals} {X : Set}
379 (f : @PartialFunction R X) (a : CRcarrier R) : PartialFunction X
380 := Xop X f (fun x => CRmax x a)
381 (fun x y Hxy => CRmax_morph _ x y Hxy a a (CReq_refl a)).
382
383 Lemma applyXmaxConst : forall {R : ConstructiveReals} {X : Set}
384 (f : PartialFunction X)
385 (a : CRcarrier R)
386 (x : X)
387 (xD : Domain f x),
388 partialApply (XmaxConst f a) x xD
389 = CRmax (partialApply f x xD) a.
390 Proof.
391 reflexivity.
392 Qed.
393
394 (* This definition is biased in favor of integrable functions,
395 ie functions defined almost everywhere.
396 Literally it means that f <= g on the intersection of their domains. *)
397 Definition partialFuncLe {R : ConstructiveReals} {X : Set}
398 (f g : @PartialFunction R X) : Prop
399 := forall (x : X) (xdf : Domain f x) (xdg : Domain g x),
400 partialApply f x xdf <= partialApply g x xdg.
401
402 Definition nonNegFunc {R : ConstructiveReals} {X : Set}
403 (f : @PartialFunction R X) : Prop
404 := forall (x : X) (xdf : Domain f x), 0 <= partialApply f x xdf.
405
406 Lemma zeroNonNeg : forall {R : ConstructiveReals},
407 nonNegFunc (@Xconst R (CRcarrier R) 0).
408 Proof.
409 intros R x xdf. apply CRle_refl.
410 Qed.
411
412 Lemma nonNegFuncPlus {R : ConstructiveReals} {X : Set}
413 (f g : @PartialFunction R X)
414 : nonNegFunc f
415 -> nonNegFunc g
416 -> nonNegFunc (Xplus f g).
417 Proof.
418 intros H H0 x xdf. destruct xdf; simpl.
419 apply (CRle_trans _ (partialApply f x d + 0)).
420 rewrite CRplus_0_r. apply H. apply CRplus_le_compat_l.
421 apply H0.
422 Qed.
423
424 Fixpoint Xsum {R : ConstructiveReals} {X : Set}
425 (fn : nat -> PartialFunction X) (n : nat)
426 : @PartialFunction R X :=
427 match n with
428 | O => fn O
429 | S i => (Xplus (Xsum fn i) (fn (S i)))
430 end.
431
432 Definition XsumList {R : ConstructiveReals} {X : Set}
433 : list (@PartialFunction R X) -> PartialFunction X
434 := fold_right Xplus
435 (* empty list means zero function defined everywhere *)
436 (Xconst _ 0).
437
438 Lemma nonNegSumFunc {R : ConstructiveReals} {X : Set}
439 (fn : nat -> @PartialFunction R X)
440 : (forall n:nat, nonNegFunc (fn n))
441 -> (forall n:nat, nonNegFunc (Xsum fn n)).
442 Proof.
443 intros. induction n.
444 - intros x. simpl. apply H.
445 - intros x. simpl. apply nonNegFuncPlus. assumption. apply H.
446 Qed.
447
448 Lemma Nat_le_succ_r_dec : forall n m : nat,
449 le n (S m) -> { le n m } + { n = S m }.
450 Proof.
451 intros. destruct (Nat.eq_dec n (S m)). right. assumption.
452 left. destruct (Nat.le_succ_r n m) as [H0 _]. destruct H0.
453 assumption. assumption. contradiction.
454 Qed.
455
456 Definition domainXsumInc {R : ConstructiveReals} {X : Set}
457 (fn : nat -> @PartialFunction R X)
458 (x : X)
459 (xn : forall n:nat, Domain (fn n) x)
460 : forall n:nat, Domain (Xsum fn n) x.
461 Proof.
462 induction n.
463 - exact (xn O).
464 - simpl. split. apply IHn. apply xn.
465 Qed.
466
467 Definition domainXsumIncReverse
468 : forall {R : ConstructiveReals} {X : Set}
469 (fn : nat -> @PartialFunction R X)
470 (k n : nat)
471 (x : X)
472 (xD : Domain (Xsum fn n) x),
473 le k n -> Domain (fn k) x.
474 Proof.
475 induction n.
476 - intros. replace k with O. exact xD.
477 inversion H. reflexivity.
478 - intros. apply Nat_le_succ_r_dec in H. simpl in xD. destruct H.
479 + specialize (IHn x (fst xD) l).
480 exact IHn.
481 + subst k. exact (snd xD).
482 Qed.
483
484 (* Simplification of the previous lemma to avoid proof irrelevance. *)
485 Definition domainXsumIncLast
486 : forall {X : Set} {R : ConstructiveReals}
487 (fn : nat -> @PartialFunction R X)
488 (n : nat)
489 (x : X)
490 (xD : Domain (Xsum fn n) x),
491 Domain (fn n) x.
492 Proof.
493 intros. destruct n.
494 - assumption.
495 - simpl in xD. exact (snd xD).
496 Defined.
497
498 Lemma applyXsum
499 : forall {X : Set} {R : ConstructiveReals}
500 (fn : nat -> @PartialFunction R X)
501 (n : nat)
502 (x : X)
503 (xD : Domain (Xsum fn n) x)
504 (xn : forall n:nat, Domain (fn n) x),
505 partialApply (Xsum fn n) x xD
506 == CRsum (fun k:nat => partialApply (fn k) x (xn k)) n.
507 Proof.
508 induction n.
509 - intros x xD xn. simpl. apply DomainProp.
510 - intros x xD xn. simpl.
511 rewrite <- (IHn x (fst xD)). clear IHn. destruct xD.
512 apply CRplus_morph. reflexivity.
513 apply DomainProp.
514 Qed.
515
516 Lemma Xsum_assoc : forall {X : Set} {R : ConstructiveReals}
517 (u : nat -> @PartialFunction R X)
518 (n p : nat)
519 (x : X)
520 (xd : Domain (Xsum u (S n + p)) x)
521 (y : Domain (Xsum u n) x)
522 (z : Domain (Xsum (fun k => u (S n + k)%nat) p) x),
523 partialApply (Xsum u (S n + p)) x xd
524 == partialApply (Xsum u n) x y
525 + partialApply (Xsum (fun k => u (S n + k)%nat) p) x z.
526 Proof.
527 induction p.
528 - intros. simpl in z. simpl. destruct xd.
529 remember (n + 0)%nat as sn. rewrite Nat.add_0_r in Heqsn. subst sn.
530 apply CRplus_morph. apply DomainProp. apply DomainProp.
531 - intros. simpl. destruct xd. simpl in z.
532 remember (n + S p)%nat as sn. rewrite Nat.add_succ_r in Heqsn. subst sn.
533 rewrite (IHp x _ y (fst z)). clear IHp.
534 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
535 destruct z. apply CRplus_morph. reflexivity.
536 apply DomainProp.
537 Qed.
538
539 Lemma Xsum_assocMinus : forall {X : Set} {R : ConstructiveReals}
540 (u : nat -> @PartialFunction R X)
541 (n p : nat)
542 (x : X)
543 (px : Domain (Xminus (Xsum u (S n + p)) (Xsum u n)) x)
544 (pxD : Domain (Xsum (fun k => u (S n + k)%nat) p) x),
545 partialApply (Xminus (Xsum u (S n + p)) (Xsum u n)) x px
546 == partialApply (Xsum (fun k => u (S n + k)%nat) p) x pxD.
547 Proof.
548 induction p.
549 - intros. simpl in px, pxD.
550 transitivity (partialApply (u (S n + 0)%nat) x pxD).
551 2: reflexivity. simpl (S n + 0)%nat.
552 remember (n + 0)%nat. rewrite Nat.add_0_r in Heqn0. subst n0.
553 destruct px. rewrite applyXminus.
554 rewrite <- (CRplus_0_r (partialApply (u (S n)) x pxD)). unfold CRminus.
555 destruct p. simpl.
556 rewrite (CRplus_comm (partialApply (Xsum u n) x d0)).
557 rewrite CRplus_assoc. apply CRplus_morph.
558 apply DomainProp. rewrite (DomainProp _ _ d0 d).
559 rewrite CRplus_opp_r. reflexivity.
560 - intros. destruct px.
561 rewrite (applyXminus (Xsum u (S n + S p)) (Xsum u n) x d d0).
562 simpl. simpl in d. destruct d, pxD. simpl in d3.
563 remember (n + S p)%nat. rewrite Nat.add_succ_r in Heqn0. subst n0.
564 specialize (IHp x (pair d d0) d2). rewrite <- IHp.
565 rewrite (applyXminus (Xsum u (S n + p)) (Xsum u n)).
566 unfold CRminus. rewrite (DomainProp _ x d1 d3).
567 do 2 rewrite CRplus_assoc.
568 apply CRplus_morph. reflexivity.
569 rewrite CRplus_comm. reflexivity.
570 Qed.
571
572 Definition XposPart {R : ConstructiveReals} {X : Set}
573 (f : @PartialFunction R X) : PartialFunction X
574 := Xscale (CR_of_Q _ (1#2)) (Xplus f (Xabs f)).
575
576 Lemma applyXposPartNonNeg : forall {X : Set} {R : ConstructiveReals}
577 (f : @PartialFunction R X),
578 nonNegFunc (XposPart f).
579 Proof.
580 intros. intros x xdf. unfold XposPart.
581 rewrite applyXscale.
582 rewrite <- (CRmult_0_r (CR_of_Q _ (1#2))). apply CRmult_le_compat_l_half.
583 apply CR_of_Q_pos. reflexivity.
584 destruct f,xdf; simpl.
585 rewrite <- (CRplus_opp_r (partialApply0 x d)). apply CRplus_le_compat_l.
586 setoid_replace (partialApply0 x d0) with (partialApply0 x d).
587 rewrite <- CRabs_opp. apply CRle_abs.
588 apply DomainProp0.
589 Qed.
590
591 Lemma applyXposPart : forall {X : Set} {R : ConstructiveReals}
592 (f : @PartialFunction R X)
593 (x : X)
594 (xD : Domain f x),
595 partialApply (XposPart f) x (pair xD xD)
596 == CRmax 0 (partialApply f x xD).
597 Proof.
598 intros. rewrite CRposPartAbsMax. unfold XposPart.
599 rewrite applyXscale. rewrite CRmult_comm.
600 apply CRmult_morph. 2: reflexivity.
601 destruct f; simpl. reflexivity.
602 Qed.
603
604 (* This definition is L-stable, whereas XminConst f 0 is not. *)
605 Definition XnegPart {X : Set} {R : ConstructiveReals}
606 (f : @PartialFunction R X) : PartialFunction X
607 := Xscale (CR_of_Q R (1#2)) (Xminus (Xabs f) f).
608
609 Lemma applyXnegPartNonNeg : forall {X : Set} {R : ConstructiveReals}
610 (f : @PartialFunction R X),
611 nonNegFunc (XnegPart f).
612 Proof.
613 intros. intros y ydf. unfold XnegPart.
614 rewrite applyXscale.
615 rewrite <- (CRmult_0_r (CR_of_Q _ (1#2))). apply CRmult_le_compat_l_half.
616 apply CR_of_Q_pos. reflexivity. destruct ydf; simpl.
617 rewrite <- CRopp_mult_distr_l, CRmult_1_l.
618 rewrite <- (CRplus_opp_r (partialApply f y d0)).
619 apply CRplus_le_compat_r. rewrite (DomainProp f y d0 d).
620 apply CRle_abs.
621 Qed.
622
623 Lemma XnegPartAbsMax : forall {R : ConstructiveReals} (x : CRcarrier R),
624 CRmax 0 (-x) == (CRabs _ x - x) * (CR_of_Q _ (1#2)).
625 Proof.
626 intros. rewrite CRposPartAbsMax. rewrite CRabs_opp.
627 apply CRmult_morph. rewrite CRplus_comm. reflexivity. reflexivity.
628 Qed.
629
630 Lemma applyXnegPart : forall {R : ConstructiveReals} {X : Set}
631 (f : @PartialFunction R X)
632 (x : X)
633 (xD : Domain f x),
634 partialApply (XnegPart f) x (pair xD xD)
635 == CRmax 0 (- partialApply f x xD).
636 Proof.
637 intros. rewrite XnegPartAbsMax. unfold XnegPart.
638 rewrite applyXscale, CRmult_comm. apply CRmult_morph. 2: reflexivity.
639 rewrite (applyXminus (Xabs f) f). apply CRplus_morph.
640 rewrite applyXabs. apply CRabs_morph. apply DomainProp.
641 reflexivity.
642 Qed.
643
644 Lemma applyXnegPartMin : forall {X : Set} {R : ConstructiveReals}
645 (f : @PartialFunction R X)
646 (x : X)
647 (xD : Domain f x),
648 partialApply (XnegPart f) x (pair xD xD)
649 == - CRmin 0 (partialApply f x xD).
650 Proof.
651 intros. rewrite CRnegPartAbsMin. unfold XnegPart.
652 rewrite applyXscale, CRmult_comm.
653 rewrite CRopp_mult_distr_l. apply CRmult_morph. 2: reflexivity.
654 rewrite (applyXminus (Xabs f) f). unfold CRminus.
655 rewrite CRopp_plus_distr, CRopp_involutive, CRplus_comm.
656 apply CRplus_morph. reflexivity.
657 rewrite applyXabs. apply CRabs_morph. apply DomainProp.
658 Qed.
659
660 Lemma XnegPartNonNeg : forall {R : ConstructiveReals} {X : Set}
661 (f : @PartialFunction R X),
662 nonNegFunc (XnegPart f).
663 Proof.
664 intros. intros x xdf. destruct xdf.
665 rewrite (DomainProp (XnegPart f) x _ (pair d d)).
666 rewrite (applyXnegPart f x d). apply CRmax_l.
667 Qed.
668
669 Lemma SplitPosNegParts : forall {X : Set} {R : ConstructiveReals}
670 (f : @PartialFunction R X)
671 (x : X)
672 (xdf : Domain f x)
673 (xdp : Domain (XposPart f) x)
674 (xdn : Domain (XnegPart f) x),
675 partialApply (XposPart f) x xdp - partialApply (XnegPart f) x xdn == partialApply f x xdf.
676 Proof.
677 intros. unfold XposPart, XnegPart, CRminus.
678 do 2 rewrite applyXscale.
679 destruct xdp. rewrite (applyXplus f (Xabs f)).
680 destruct xdn. rewrite (applyXminus (Xabs f) f). rewrite CRplus_comm.
681 unfold CRminus. rewrite (DomainProp f x _ xdf), (DomainProp (Xabs f) x _ xdf).
682 rewrite CRopp_mult_distr_r, <- CRmult_plus_distr_l.
683 rewrite (DomainProp f x d xdf), (DomainProp (Xabs f) x d0 xdf).
684 setoid_replace (- (partialApply (Xabs f) x xdf + - partialApply f x xdf) +
685 (partialApply f x xdf + partialApply (Xabs f) x xdf))
686 with (partialApply f x xdf + partialApply f x xdf).
687 rewrite <- (CRmult_1_l (partialApply f x xdf)), <- CRmult_plus_distr_r.
688 rewrite <- CRmult_assoc, CRmult_1_l, <- CR_of_Q_plus.
689 rewrite <- CR_of_Q_mult.
690 setoid_replace ((1 # 2) * (1+1))%Q with 1%Q.
691 apply CRmult_1_l.
692 reflexivity. rewrite CRplus_comm, CRplus_assoc.
693 apply CRplus_morph. reflexivity.
694 rewrite CRopp_plus_distr. rewrite CRopp_involutive.
695 rewrite <- CRplus_assoc, CRplus_opp_r, CRplus_0_l. reflexivity.
696 Qed.
697
698 Definition Xmin {R : ConstructiveReals} {X : Set}
699 (f g : @PartialFunction R X) : PartialFunction X
700 := Xminus g (XnegPart (Xminus f g)).
701
702 Lemma applyXmin : forall {X : Set} {R : ConstructiveReals}
703 (f g : @PartialFunction R X)
704 (x : X)
705 (xdf : Domain f x)
706 (xdg : Domain g x)
707 (xdp : Domain (Xmin f g) x),
708 partialApply (Xmin f g) x xdp
709 == CRmin (partialApply f x xdf) (partialApply g x xdg).
710 Proof.
711 intros. unfold Xmin.
712 destruct xdp. rewrite (applyXminus g (XnegPart (Xminus f g))).
713 assert (Domain (Xminus f g) x).
714 { destruct f,g; split. exact xdf. exact xdg. }
715 simpl in d0. unfold CRminus.
716 rewrite (DomainProp (XnegPart (Xminus f g)) x _ (fst d0, fst d0)),
717 applyXnegPartMin.
718 destruct d0,p. unfold fst. rewrite (applyXminus f g).
719 destruct f, g; simpl.
720 rewrite CRopp_involutive. unfold CRminus.
721 rewrite (DomainProp1 x d1 d), (DomainProp1 x xdg d), (DomainProp0 x _ xdf).
722 rewrite CRmin_plus, CRplus_0_r, (CRplus_comm (partialApply0 x xdf)).
723 rewrite <- CRplus_assoc, CRplus_opp_r, CRplus_0_l.
724 apply CRmin_sym.
725 Qed.
726
727 Definition Xmax {R : ConstructiveReals} {X : Set}
728 (f g : @PartialFunction R X) : PartialFunction X
729 := (Xplus g (XposPart (Xminus f g))).
730
731 Lemma applyXmax : forall {X : Set} {R : ConstructiveReals}
732 (f g : @PartialFunction R X)
733 (x : X)
734 (xdf : Domain f x)
735 (xdg : Domain g x)
736 (xdp : Domain (Xmax f g) x),
737 partialApply (Xmax f g) x xdp
738 == CRmax (partialApply f x xdf) (partialApply g x xdg).
739 Proof.
740 intros. unfold Xmax.
741 destruct xdp. rewrite applyXplus.
742 assert (Domain (Xminus f g) x).
743 { destruct f,g; split. exact xdf. exact xdg. }
744 rewrite (DomainProp (XposPart (Xminus f g)) x _ (fst d0, fst d0)),
745 applyXposPart.
746 destruct d0, d0. unfold fst. rewrite (applyXminus f g).
747 destruct f, g; simpl.
748 rewrite (DomainProp1 x d2 d), (DomainProp1 x xdg d), (DomainProp0 x d0 xdf).
749 unfold CRminus.
750 rewrite CRmax_plus, CRplus_0_r, (CRplus_comm (partialApply0 x xdf)).
751 rewrite <- CRplus_assoc, CRplus_opp_r, CRplus_0_l.
752 apply CRmax_sym.
753 Qed.
754
755 Lemma XminMultPosDistrib :
756 forall {X : Set} {R : ConstructiveReals} (f : PartialFunction X) (a b : CRcarrier R),
757 0 <= a
758 -> PartialFunExtEq (Xscale a (XminConst f b))
759 (XminConst (Xscale a f) (a*b)).
760 Proof.
761 intros. destruct f; simpl; split; unfold DomainInclusion, Domain.
762 - split.
763 + intros x xdf. exact xdf.
764 + intros x xdf. exact xdf.
765 - intros x xdf xg. simpl. rewrite CRmin_mult.
766 rewrite (DomainProp0 x xdf xg). reflexivity. exact H.
767 Qed.
768
769 Lemma XscaleAssoc :
770 forall {R : ConstructiveReals} {X : Set}
771 (f : PartialFunction X) (a b : CRcarrier R),
772 PartialFunExtEq (Xscale a (Xscale b f))
773 (Xscale (a*b) f).
774 Proof.
775 intros. destruct f; simpl; split.
776 - split.
777 + intros x. simpl. exact (fun x => x).
778 + intros x. simpl. exact (fun x => x).
779 - intros. simpl. rewrite (DomainProp0 x xD xG).
780 rewrite CRmult_assoc. reflexivity.
781 Qed.
782
783 Lemma XscaleOne :
784 forall {X : Set} {R : ConstructiveReals} (f : @PartialFunction R X),
785 PartialFunExtEq (Xscale 1 f) f.
786 Proof.
787 intros. split.
788 - split.
789 + intros x H. destruct f; exact H.
790 + intros x H. destruct f; exact H.
791 - intros. rewrite applyXscale, CRmult_1_l.
792 apply DomainProp.
793 Qed.
794
795 Lemma XminMultPosDistribOne
796 : forall {R : ConstructiveReals} {X : Set}
797 (f : PartialFunction X) (a : CRcarrier R) (aPos : 0 < a),
798 PartialFunExtEq (Xscale a (XminConst (Xscale (CRinv _ a (inr aPos)) f) 1))
799 (XminConst f a).
800 Proof.
801 intros. split. split.
802 - intros x xD. destruct f; exact xD.
803 - intros x xD. destruct f; exact xD.
804 - intros. rewrite applyXscale.
805 simpl in xD, xG.
806 rewrite applyXminConst.
807 rewrite applyXminConst. rewrite applyXscale.
808 rewrite (DomainProp _ _ xD xG). rewrite <- CRmin_mult.
809 rewrite <- CRmult_assoc, CRinv_r, CRmult_1_l.
810 rewrite CRmult_1_r. reflexivity.
811 apply CRlt_asym, aPos.
812 Qed.
813
814 Lemma XmultiTriangleIneg : forall {X : Set} {R : ConstructiveReals}
815 (fn : nat -> @PartialFunction R X)
816 (n : nat)
817 (x : X)
818 (xD : Domain (Xabs (Xsum fn n)) x)
819 (y : Domain (Xsum (fun a : nat => Xabs (fn a)) n) x),
820 partialApply (Xabs (Xsum fn n)) x xD
821 <= partialApply (Xsum (fun a : nat => Xabs (fn a)) n) x y.
822 Proof.
823 induction n.
824 - intros. simpl. simpl in xD.
825 rewrite (DomainProp _ _ xD y). apply CRle_refl.
826 - intros. simpl. simpl in x,y,xD.
827 destruct (Xsum fn n), (fn (S n)), (Xsum (fun a : nat => Xabs (fn a)) n),
828 xD, y; simpl; simpl in IHn.
829 apply (CRle_trans _ (CRabs _ (partialApply0 x d) + CRabs _ (partialApply1 x d0))).
830 apply CRabs_triang.
831 apply CRplus_le_compat. apply IHn.
832 rewrite (DomainProp1 x d0 d2). apply CRle_refl.
833 Qed.
834
835 (* For partial functions on a product domain, we can project at
836 any point in any coordinate, possibly by the empty function. *)
837 Definition Xproj1 {R : ConstructiveReals} {X Y : Set}
838 (f : PartialFunction (prod X Y)) (x : X)
839 : PartialFunction Y
840 := Build_PartialFunctionXY
841 Y (CRcarrier R) (CReq R) (fun y:Y => Domain f (x,y))
842 (fun y yD => partialApply f (x,y) yD)
843 (fun y p q => DomainProp f (x,y) p q).
844
845 Definition Xproj2 {R : ConstructiveReals} {X Y : Set}
846 (f : PartialFunction (prod X Y)) (y : Y)
847 : PartialFunction X
848 := Build_PartialFunctionXY
849 X (CRcarrier R) (CReq R) (fun x:X => Domain f (x,y))
850 (fun x xD => partialApply f (x,y) xD)
851 (fun x p q => DomainProp f (x,y) p q).
852
853 Definition Xdiv {R : ConstructiveReals} {X : Set} (f : @PartialFunction R X)
854 : @PartialFunction R X.
855 Proof.
856 apply (Build_PartialFunctionXY
857 X (CRcarrier R) (CReq R)
858 (fun x:X => {xD : Domain f x & partialApply f x xD ≶ 0})
859 (fun x y => let (xD,xnz) := y in CRinv R (partialApply f x xD) xnz)).
860 intros. destruct p,q. apply CRinv_morph, DomainProp.
861 Defined.