]> matita.cs.unibo.it Git - helm.git/blob - matita/dama/ordered_sets.ma
fix dependences for matita
[helm.git] / matita / dama / ordered_sets.ma
1 (**************************************************************************)
2 (*       ___                                                              *)
3 (*      ||M||                                                             *)
4 (*      ||A||       A project by Andrea Asperti                           *)
5 (*      ||T||                                                             *)
6 (*      ||I||       Developers:                                           *)
7 (*      ||T||         The HELM team.                                      *)
8 (*      ||A||         http://helm.cs.unibo.it                             *)
9 (*      \   /                                                             *)
10 (*       \ /        This file is distributed under the terms of the       *)
11 (*        v         GNU General Public License Version 2                  *)
12 (*                                                                        *)
13 (**************************************************************************)
14
15 set "baseuri" "cic:/matita/ordered_sets/".
16
17 include "higher_order_defs/relations.ma".
18 include "nat/plus.ma".
19 include "constructive_connectives.ma".
20
21 definition cotransitive ≝
22  λC:Type.λle:C→C→Prop.∀x,y,z:C. le x y → le x z ∨ le z y. 
23
24 definition antisimmetric ≝
25  λC:Type.λle:C→C→Prop.∀x,y:C. le x y → le y x → x=y.
26
27 record is_order_relation (C:Type) (le:C→C→Prop) : Type ≝
28  { or_reflexive: reflexive ? le;
29    or_transitive: transitive ? le;
30    or_antisimmetric: antisimmetric ? le
31  }.
32
33 record ordered_set: Type ≝
34  { os_carrier:> Type;
35    os_le: os_carrier → os_carrier → Prop;
36    os_order_relation_properties:> is_order_relation ? os_le
37  }.
38
39 interpretation "Ordered Sets le" 'leq a b =
40  (cic:/matita/ordered_sets/os_le.con _ a b).
41
42 theorem antisimmetric_to_cotransitive_to_transitive:
43  ∀C.∀le:relation C. antisimmetric ? le → cotransitive ? le →
44   transitive ? le.
45  intros;
46  unfold transitive;
47  intros;
48  elim (c ? ? z H1);
49   [ assumption
50   | rewrite < (H ? ? H2 t);
51     assumption
52   ].
53 qed.
54
55 definition is_increasing ≝ λO:ordered_set.λa:nat→O.∀n:nat.a n ≤ a (S n).
56 definition is_decreasing ≝ λO:ordered_set.λa:nat→O.∀n:nat.a (S n) ≤ a n.
57
58 definition is_upper_bound ≝ λO:ordered_set.λa:nat→O.λu:O.∀n:nat.a n ≤ u.
59 definition is_lower_bound ≝ λO:ordered_set.λa:nat→O.λu:O.∀n:nat.u ≤ a n.
60
61 record is_sup (O:ordered_set) (a:nat→O) (u:O) : Prop ≝
62  { sup_upper_bound: is_upper_bound O a u; 
63    sup_least_upper_bound: ∀v:O. is_upper_bound O a v → u≤v
64  }.
65
66 record is_inf (O:ordered_set) (a:nat→O) (u:O) : Prop ≝
67  { inf_lower_bound: is_lower_bound O a u; 
68    inf_greatest_lower_bound: ∀v:O. is_lower_bound O a v → v≤u
69  }.
70
71 record is_bounded_below (O:ordered_set) (a:nat→O) : Type ≝
72  { ib_lower_bound: O;
73    ib_lower_bound_is_lower_bound: is_lower_bound ? a ib_lower_bound
74  }.
75
76 record is_bounded_above (O:ordered_set) (a:nat→O) : Type ≝
77  { ib_upper_bound: O;
78    ib_upper_bound_is_upper_bound: is_upper_bound ? a ib_upper_bound
79  }.
80
81 record is_bounded (O:ordered_set) (a:nat→O) : Type ≝
82  { ib_bounded_below:> is_bounded_below ? a;
83    ib_bounded_above:> is_bounded_above ? a
84  }.
85
86 record bounded_below_sequence (O:ordered_set) : Type ≝
87  { bbs_seq:1> nat→O;
88    bbs_is_bounded_below:> is_bounded_below ? bbs_seq
89  }.
90
91 record bounded_above_sequence (O:ordered_set) : Type ≝
92  { bas_seq:1> nat→O;
93    bas_is_bounded_above:> is_bounded_above ? bas_seq
94  }.
95
96 record bounded_sequence (O:ordered_set) : Type ≝
97  { bs_seq:1> nat → O;
98    bs_is_bounded_below: is_bounded_below ? bs_seq;
99    bs_is_bounded_above: is_bounded_above ? bs_seq
100  }.
101
102 definition bounded_below_sequence_of_bounded_sequence ≝
103  λO:ordered_set.λb:bounded_sequence O.
104   mk_bounded_below_sequence ? b (bs_is_bounded_below ? b).
105
106 coercion cic:/matita/ordered_sets/bounded_below_sequence_of_bounded_sequence.con.
107
108 definition bounded_above_sequence_of_bounded_sequence ≝
109  λO:ordered_set.λb:bounded_sequence O.
110   mk_bounded_above_sequence ? b (bs_is_bounded_above ? b).
111
112 coercion cic:/matita/ordered_sets/bounded_above_sequence_of_bounded_sequence.con.
113
114 definition lower_bound ≝
115  λO:ordered_set.λb:bounded_below_sequence O.
116   ib_lower_bound ? b (bbs_is_bounded_below ? b).
117
118 lemma lower_bound_is_lower_bound:
119  ∀O:ordered_set.∀b:bounded_below_sequence O.
120   is_lower_bound ? b (lower_bound ? b).
121  intros;
122  unfold lower_bound;
123  apply ib_lower_bound_is_lower_bound.
124 qed.
125
126 definition upper_bound ≝
127  λO:ordered_set.λb:bounded_above_sequence O.
128   ib_upper_bound ? b (bas_is_bounded_above ? b).
129
130 lemma upper_bound_is_upper_bound:
131  ∀O:ordered_set.∀b:bounded_above_sequence O.
132   is_upper_bound ? b (upper_bound ? b).
133  intros;
134  unfold upper_bound;
135  apply ib_upper_bound_is_upper_bound.
136 qed.
137
138 record is_dedekind_sigma_complete (O:ordered_set) : Type ≝
139  { dsc_inf: ∀a:nat→O.∀m:O. is_lower_bound ? a m → ex ? (λs:O.is_inf O a s);
140    dsc_inf_proof_irrelevant:
141     ∀a:nat→O.∀m,m':O.∀p:is_lower_bound ? a m.∀p':is_lower_bound ? a m'.
142      (match dsc_inf a m p with [ ex_intro s _ ⇒ s ]) =
143      (match dsc_inf a m' p' with [ ex_intro s' _ ⇒ s' ]); 
144    dsc_sup: ∀a:nat→O.∀m:O. is_upper_bound ? a m → ex ? (λs:O.is_sup O a s);
145    dsc_sup_proof_irrelevant:
146     ∀a:nat→O.∀m,m':O.∀p:is_upper_bound ? a m.∀p':is_upper_bound ? a m'.
147      (match dsc_sup a m p with [ ex_intro s _ ⇒ s ]) =
148      (match dsc_sup a m' p' with [ ex_intro s' _ ⇒ s' ])    
149  }.
150
151 record dedekind_sigma_complete_ordered_set : Type ≝
152  { dscos_ordered_set:> ordered_set;
153    dscos_dedekind_sigma_complete_properties:>
154     is_dedekind_sigma_complete dscos_ordered_set
155  }.
156
157 definition inf:
158  ∀O:dedekind_sigma_complete_ordered_set.
159   bounded_below_sequence O → O.
160  intros;
161  elim
162   (dsc_inf O (dscos_dedekind_sigma_complete_properties O) b);
163   [ apply a
164   | apply (lower_bound ? b)
165   | apply lower_bound_is_lower_bound
166   ]
167 qed.
168
169 lemma inf_is_inf:
170  ∀O:dedekind_sigma_complete_ordered_set.
171   ∀a:bounded_below_sequence O.
172    is_inf ? a (inf ? a).
173  intros;
174  unfold inf;
175  simplify;
176  elim (dsc_inf O (dscos_dedekind_sigma_complete_properties O) a
177 (lower_bound O a) (lower_bound_is_lower_bound O a));
178  simplify;
179  assumption.
180 qed.
181
182 lemma inf_proof_irrelevant:
183  ∀O:dedekind_sigma_complete_ordered_set.
184   ∀a,a':bounded_below_sequence O.
185    bbs_seq ? a = bbs_seq ? a' →
186     inf ? a = inf ? a'.
187  intros 3;
188  elim a 0;
189  elim a';
190  simplify in H;
191  generalize in match i1;
192  clear i1;
193  rewrite > H;
194  intro;
195  simplify;
196  rewrite < (dsc_inf_proof_irrelevant O O f (ib_lower_bound ? f i)
197   (ib_lower_bound ? f i2) (ib_lower_bound_is_lower_bound ? f i)
198   (ib_lower_bound_is_lower_bound ? f i2));
199  reflexivity.
200 qed.
201
202 definition sup:
203  ∀O:dedekind_sigma_complete_ordered_set.
204   bounded_above_sequence O → O.
205  intros;
206  elim
207   (dsc_sup O (dscos_dedekind_sigma_complete_properties O) b);
208   [ apply a
209   | apply (upper_bound ? b)
210   | apply upper_bound_is_upper_bound
211   ].
212 qed.
213
214 lemma sup_is_sup:
215  ∀O:dedekind_sigma_complete_ordered_set.
216   ∀a:bounded_above_sequence O.
217    is_sup ? a (sup ? a).
218  intros;
219  unfold sup;
220  simplify;
221  elim (dsc_sup O (dscos_dedekind_sigma_complete_properties O) a
222 (upper_bound O a) (upper_bound_is_upper_bound O a));
223  simplify;
224  assumption.
225 qed.
226
227 lemma sup_proof_irrelevant:
228  ∀O:dedekind_sigma_complete_ordered_set.
229   ∀a,a':bounded_above_sequence O.
230    bas_seq ? a = bas_seq ? a' →
231     sup ? a = sup ? a'.
232  intros 3;
233  elim a 0;
234  elim a';
235  simplify in H;
236  generalize in match i1;
237  clear i1;
238  rewrite > H;
239  intro;
240  simplify;
241  rewrite < (dsc_sup_proof_irrelevant O O f (ib_upper_bound ? f i2)
242   (ib_upper_bound ? f i) (ib_upper_bound_is_upper_bound ? f i2)
243   (ib_upper_bound_is_upper_bound ? f i));
244  reflexivity.
245 qed.
246
247 axiom daemon: False.
248
249 theorem inf_le_sup:
250  ∀O:dedekind_sigma_complete_ordered_set.
251   ∀a:bounded_sequence O. inf ? a ≤ sup ? a.
252  intros (O');
253  apply (or_transitive ? ? O' ? (a O));
254   [ elim daemon (*apply (inf_lower_bound ? ? ? ? (inf_is_inf ? ? a))*)
255   | elim daemon (*apply (sup_upper_bound ? ? ? ? (sup_is_sup ? ? a))*)
256   ].
257 qed.
258
259 lemma inf_respects_le:
260  ∀O:dedekind_sigma_complete_ordered_set.
261   ∀a:bounded_below_sequence O.∀m:O.
262    is_upper_bound ? a m → inf ? a ≤ m.
263  intros (O');
264  apply (or_transitive ? ? O' ? (sup ? (mk_bounded_sequence ? a ? ?)));
265   [ apply (bbs_is_bounded_below ? a)
266   | apply (mk_is_bounded_above ? ? m H)
267   | apply inf_le_sup 
268   | apply
269      (sup_least_upper_bound ? ? ?
270       (sup_is_sup ? (mk_bounded_sequence O' a a
271         (mk_is_bounded_above O' a m H))));
272     assumption
273   ].
274 qed. 
275
276 definition is_sequentially_monotone ≝
277  λO:ordered_set.λf:O→O.
278   ∀a:nat→O.∀p:is_increasing ? a.
279    is_increasing ? (λi.f (a i)).
280
281 record is_order_continuous
282  (O:dedekind_sigma_complete_ordered_set) (f:O→O) : Prop
283
284  { ioc_is_sequentially_monotone: is_sequentially_monotone ? f;
285    ioc_is_upper_bound_f_sup:
286     ∀a:bounded_above_sequence O.
287      is_upper_bound ? (λi.f (a i)) (f (sup ? a));
288    ioc_respects_sup:
289     ∀a:bounded_above_sequence O.
290      is_increasing ? a →
291       f (sup ? a) =
292        sup ? (mk_bounded_above_sequence ? (λi.f (a i))
293         (mk_is_bounded_above ? ? (f (sup ? a))
294          (ioc_is_upper_bound_f_sup a)));
295    ioc_is_lower_bound_f_inf:
296     ∀a:bounded_below_sequence O.
297      is_lower_bound ? (λi.f (a i)) (f (inf ? a));
298    ioc_respects_inf:
299     ∀a:bounded_below_sequence O.
300      is_decreasing ? a →
301       f (inf ? a) =
302        inf ? (mk_bounded_below_sequence ? (λi.f (a i))
303         (mk_is_bounded_below ? ? (f (inf ? a))
304          (ioc_is_lower_bound_f_inf a)))   
305  }.
306
307 theorem tail_inf_increasing:
308  ∀O:dedekind_sigma_complete_ordered_set.
309   ∀a:bounded_below_sequence O.
310    let y ≝ λi.mk_bounded_below_sequence ? (λj.a (i+j)) ? in
311    let x ≝ λi.inf ? (y i) in
312     is_increasing ? x.
313  [ apply (mk_is_bounded_below ? ? (ib_lower_bound ? a a));
314    simplify;
315    intro;
316    apply (ib_lower_bound_is_lower_bound ? a a)
317  | intros;
318    unfold is_increasing;
319    intro;
320    unfold x in ⊢ (? ? ? %);
321    apply (inf_greatest_lower_bound ? ? ? (inf_is_inf ? (y (S n))));
322    change with (is_lower_bound ? (y (S n)) (inf ? (y n)));
323    unfold is_lower_bound;
324    intro;
325    generalize in match (inf_lower_bound ? ? ? (inf_is_inf ? (y n)) (S n1));
326    (*CSC: coercion per FunClass inserita a mano*)
327    suppose (inf ? (y n) ≤ bbs_seq ? (y n) (S n1)) (H);
328    cut (bbs_seq ? (y n) (S n1) = bbs_seq ? (y (S n)) n1);
329     [ rewrite < Hcut;
330       assumption
331     | unfold y;
332       simplify;
333       auto paramodulation library
334     ]
335  ].
336 qed.
337
338 definition is_liminf:
339  ∀O:dedekind_sigma_complete_ordered_set.
340   bounded_below_sequence O → O → Prop.
341  intros;
342  apply
343   (is_sup ? (λi.inf ? (mk_bounded_below_sequence ? (λj.b (i+j)) ?)) t);
344  apply (mk_is_bounded_below ? ? (ib_lower_bound ? b b));
345  simplify;
346  intros;
347  apply (ib_lower_bound_is_lower_bound ? b b).
348 qed.  
349
350 definition liminf:
351  ∀O:dedekind_sigma_complete_ordered_set.
352   bounded_sequence O → O.
353  intros;
354  apply
355   (sup ?
356    (mk_bounded_above_sequence ?
357      (λi.inf ?
358        (mk_bounded_below_sequence ?
359          (λj.b (i+j)) ?)) ?));
360   [ apply (mk_is_bounded_below ? ? (ib_lower_bound ? b b));
361     simplify;
362     intros;
363     apply (ib_lower_bound_is_lower_bound ? b b)
364   | apply (mk_is_bounded_above ? ? (ib_upper_bound ? b b));
365     unfold is_upper_bound;
366     intro;
367     change with
368      (inf O
369   (mk_bounded_below_sequence O (\lambda j:nat.b (n+j))
370    (mk_is_bounded_below O (\lambda j:nat.b (n+j)) (ib_lower_bound O b b)
371     (\lambda j:nat.ib_lower_bound_is_lower_bound O b b (n+j))))
372 \leq ib_upper_bound O b b);
373     apply (inf_respects_le O);
374     simplify;
375     intro;
376     apply (ib_upper_bound_is_upper_bound ? b b)
377   ].
378 qed.
379
380 definition reverse_ordered_set: ordered_set → ordered_set.
381  intros;
382  apply mk_ordered_set;
383   [2:apply (λx,y:o.y ≤ x)
384   | skip
385   | apply mk_is_order_relation;
386      [ simplify;
387        intros;
388        apply (or_reflexive ? ? o)
389      | simplify;
390        intros;
391        apply (or_transitive ? ? o);
392         [2: apply H1
393         | skip
394         | assumption
395         ] 
396      | simplify;
397        intros;
398        apply (or_antisimmetric ? ? o);
399        assumption
400      ]
401   ].
402 qed.
403  
404 interpretation "Ordered set ge" 'geq a b =
405  (cic:/matita/ordered_sets/os_le.con _
406   (cic:/matita/ordered_sets/os_pre_ordered_set.con _
407    (cic:/matita/ordered_sets/reverse_ordered_set.con _ _)) a b).
408
409 lemma is_lower_bound_reverse_is_upper_bound:
410  ∀O:ordered_set.∀a:nat→O.∀l:O.
411   is_lower_bound O a l → is_upper_bound (reverse_ordered_set O) a l.
412  intros;
413  unfold;
414  intro;
415  unfold;
416  unfold reverse_ordered_set;
417  simplify;
418  apply H.
419 qed.
420
421 lemma is_upper_bound_reverse_is_lower_bound:
422  ∀O:ordered_set.∀a:nat→O.∀l:O.
423   is_upper_bound O a l → is_lower_bound (reverse_ordered_set O) a l.
424  intros;
425  unfold;
426  intro;
427  unfold;
428  unfold reverse_ordered_set;
429  simplify;
430  apply H.
431 qed.
432
433 lemma reverse_is_lower_bound_is_upper_bound:
434  ∀O:ordered_set.∀a:nat→O.∀l:O.
435   is_lower_bound (reverse_ordered_set O) a l → is_upper_bound O a l.
436  intros;
437  unfold in H;
438  unfold reverse_ordered_set in H;
439  apply H.
440 qed.
441
442 lemma reverse_is_upper_bound_is_lower_bound:
443  ∀O:ordered_set.∀a:nat→O.∀l:O.
444   is_upper_bound (reverse_ordered_set O) a l → is_lower_bound O a l.
445  intros;
446  unfold in H;
447  unfold reverse_ordered_set in H;
448  apply H.
449 qed.
450
451
452 lemma is_inf_to_reverse_is_sup:
453  ∀O:ordered_set.∀a:bounded_below_sequence O.∀l:O.
454   is_inf O a l → is_sup (reverse_ordered_set O) a l.
455  intros;
456  apply (mk_is_sup (reverse_ordered_set O));
457   [ apply is_lower_bound_reverse_is_upper_bound;
458     apply inf_lower_bound;
459     assumption
460   | intros;
461     change in v with (os_carrier O);
462     change with (v ≤ l);
463     apply (inf_greatest_lower_bound ? ? ? H);
464     apply reverse_is_upper_bound_is_lower_bound;
465     assumption
466   ].
467 qed.
468  
469 lemma is_sup_to_reverse_is_inf:
470  ∀O:ordered_set.∀a:bounded_above_sequence O.∀l:O.
471   is_sup O a l → is_inf (reverse_ordered_set O) a l.
472  intros;
473  apply (mk_is_inf (reverse_ordered_set O));
474   [ apply is_upper_bound_reverse_is_lower_bound;
475     apply sup_upper_bound;
476     assumption
477   | intros;
478     change in v with (os_carrier O);
479     change with (l ≤ v);
480     apply (sup_least_upper_bound ? ? ? H);
481     apply reverse_is_lower_bound_is_upper_bound;
482     assumption
483   ].
484 qed.
485
486 lemma reverse_is_sup_to_is_inf:
487  ∀O:ordered_set.∀a:bounded_above_sequence O.∀l:O.
488   is_sup (reverse_ordered_set O) a l → is_inf O a l.
489  intros;
490  apply mk_is_inf;
491   [ apply reverse_is_upper_bound_is_lower_bound;
492     change in l with (os_carrier (reverse_ordered_set O));
493     apply sup_upper_bound;
494     assumption
495   | intros;
496     change in l with (os_carrier (reverse_ordered_set O));
497     change in v with (os_carrier (reverse_ordered_set O));
498     change with (os_le (reverse_ordered_set O) l v);
499     apply (sup_least_upper_bound ? ? ? H);
500     change in v with (os_carrier O);
501     apply is_lower_bound_reverse_is_upper_bound;
502     assumption
503   ].
504 qed.
505
506 lemma reverse_is_inf_to_is_sup:
507  ∀O:ordered_set.∀a:bounded_above_sequence O.∀l:O.
508   is_inf (reverse_ordered_set O) a l → is_sup O a l.
509  intros;
510  apply mk_is_sup;
511   [ apply reverse_is_lower_bound_is_upper_bound;
512     change in l with (os_carrier (reverse_ordered_set O));
513     apply (inf_lower_bound ? ? ? H)
514   | intros;
515     change in l with (os_carrier (reverse_ordered_set O));
516     change in v with (os_carrier (reverse_ordered_set O));
517     change with (os_le (reverse_ordered_set O) v l);
518     apply (inf_greatest_lower_bound ? ? ? H);
519     change in v with (os_carrier O);
520     apply is_upper_bound_reverse_is_lower_bound;
521     assumption
522   ].
523 qed.
524
525
526 definition reverse_dedekind_sigma_complete_ordered_set:
527  dedekind_sigma_complete_ordered_set → dedekind_sigma_complete_ordered_set.
528  intros;
529  apply mk_dedekind_sigma_complete_ordered_set;
530   [ apply (reverse_ordered_set d)
531   | elim daemon
532     (*apply mk_is_dedekind_sigma_complete;
533      [ intros;
534        elim (dsc_sup ? ? d a m) 0;
535         [ generalize in match H; clear H;
536           generalize in match m; clear m;
537           elim d;
538           simplify in a1;
539           simplify;
540           change in a1 with (Type_OF_ordered_set ? (reverse_ordered_set ? o)); 
541           apply (ex_intro ? ? a1);
542           simplify in H1;
543           change in m with (Type_OF_ordered_set ? o);
544           apply (is_sup_to_reverse_is_inf ? ? ? ? H1)
545         | generalize in match H; clear H;
546           generalize in match m; clear m;
547           elim d;
548           simplify;
549           change in t with (Type_OF_ordered_set ? o);
550           simplify in t;
551           apply reverse_is_lower_bound_is_upper_bound;
552           assumption
553         ]
554      | apply is_sup_reverse_is_inf;
555      | apply m
556      | 
557      ]*)
558   ].
559 qed.
560
561 definition reverse_bounded_sequence:
562  ∀O:dedekind_sigma_complete_ordered_set.
563   bounded_sequence O →
564    bounded_sequence (reverse_dedekind_sigma_complete_ordered_set O).
565  intros;
566  apply mk_bounded_sequence;
567   [ apply bs_seq;
568     unfold reverse_dedekind_sigma_complete_ordered_set;
569     simplify;
570     elim daemon
571   | elim daemon
572   | elim daemon
573   ].
574 qed.
575
576 definition limsup ≝
577  λO:dedekind_sigma_complete_ordered_set.
578   λa:bounded_sequence O.
579    liminf (reverse_dedekind_sigma_complete_ordered_set O)
580     (reverse_bounded_sequence O a).
581
582 notation "hvbox(〈a〉)"
583  non associative with precedence 45
584 for @{ 'hide_everything_but $a }.
585
586 interpretation "mk_bounded_above_sequence" 'hide_everything_but a
587 = (cic:/matita/ordered_sets/bounded_above_sequence.ind#xpointer(1/1/1) _ _ a _).
588
589 interpretation "mk_bounded_below_sequence" 'hide_everything_but a
590 = (cic:/matita/ordered_sets/bounded_below_sequence.ind#xpointer(1/1/1) _ _ a _).
591
592 theorem eq_f_sup_sup_f:
593  ∀O':dedekind_sigma_complete_ordered_set.
594   ∀f:O'→O'. ∀H:is_order_continuous ? f.
595    ∀a:bounded_above_sequence O'.
596     ∀p:is_increasing ? a.
597      f (sup ? a) = sup ? (mk_bounded_above_sequence ? (λi.f (a i)) ?).
598  [ apply (mk_is_bounded_above ? ? (f (sup ? a))); 
599    apply ioc_is_upper_bound_f_sup;
600    assumption
601  | intros;
602    apply ioc_respects_sup;
603    assumption
604  ].
605 qed.
606
607 theorem eq_f_sup_sup_f':
608  ∀O':dedekind_sigma_complete_ordered_set.
609   ∀f:O'→O'. ∀H:is_order_continuous ? f.
610    ∀a:bounded_above_sequence O'.
611     ∀p:is_increasing ? a.
612      ∀p':is_bounded_above ? (λi.f (a i)).
613       f (sup ? a) = sup ? (mk_bounded_above_sequence ? (λi.f (a i)) p').
614  intros;
615  rewrite > (eq_f_sup_sup_f ? f H a H1);
616  apply sup_proof_irrelevant;
617  reflexivity.
618 qed.
619
620 theorem eq_f_liminf_sup_f_inf:
621  ∀O':dedekind_sigma_complete_ordered_set.
622   ∀f:O'→O'. ∀H:is_order_continuous ? f.
623    ∀a:bounded_sequence O'.
624    let p1 := ? in
625     f (liminf ? a) =
626      sup ?
627       (mk_bounded_above_sequence ?
628         (λi.f (inf ?
629           (mk_bounded_below_sequence ?
630             (λj.a (i+j))
631             ?)))
632         p1).
633  [ apply (mk_is_bounded_below ? ? (ib_lower_bound ? a a));
634    simplify;
635    intro;
636    apply (ib_lower_bound_is_lower_bound ? a a)
637  | apply (mk_is_bounded_above ? ? (f (sup ? a)));
638    unfold is_upper_bound;
639    intro;
640    apply (or_transitive ? ? O' ? (f (a n)));
641     [ generalize in match (ioc_is_lower_bound_f_inf ? ? H);
642       intro H1;
643       simplify in H1;
644       rewrite > (plus_n_O n) in ⊢ (? ? ? (? (? ? ? %)));
645       apply (H1 (mk_bounded_below_sequence O' (\lambda j:nat.a (n+j))
646 (mk_is_bounded_below O' (\lambda j:nat.a (n+j)) (ib_lower_bound O' a a)
647  (\lambda j:nat.ib_lower_bound_is_lower_bound O' a a (n+j)))) O);
648     | elim daemon (*apply (ioc_is_upper_bound_f_sup ? ? ? H)*)
649     ]
650  | intros;
651    unfold liminf;
652    clearbody p1;
653    generalize in match (\lambda n:nat
654 .inf_respects_le O'
655  (mk_bounded_below_sequence O' (\lambda j:nat.a (plus n j))
656   (mk_is_bounded_below O' (\lambda j:nat.a (plus n j))
657    (ib_lower_bound O' a a)
658    (\lambda j:nat.ib_lower_bound_is_lower_bound O' a a (plus n j))))
659  (ib_upper_bound O' a a)
660  (\lambda n1:nat.ib_upper_bound_is_upper_bound O' a a (plus n n1)));
661    intro p2;
662    apply (eq_f_sup_sup_f' ? f H (mk_bounded_above_sequence O'
663 (\lambda i:nat
664  .inf O'
665   (mk_bounded_below_sequence O' (\lambda j:nat.a (plus i j))
666    (mk_is_bounded_below O' (\lambda j:nat.a (plus i j))
667     (ib_lower_bound O' a a)
668     (\lambda n:nat.ib_lower_bound_is_lower_bound O' a a (plus i n)))))
669 (mk_is_bounded_above O'
670  (\lambda i:nat
671   .inf O'
672    (mk_bounded_below_sequence O' (\lambda j:nat.a (plus i j))
673     (mk_is_bounded_below O' (\lambda j:nat.a (plus i j))
674      (ib_lower_bound O' a a)
675      (\lambda n:nat.ib_lower_bound_is_lower_bound O' a a (plus i n)))))
676  (ib_upper_bound O' a a) p2)));
677    unfold bas_seq;
678    change with
679     (is_increasing ? (\lambda i:nat
680 .inf O'
681  (mk_bounded_below_sequence O' (\lambda j:nat.a (plus i j))
682   (mk_is_bounded_below O' (\lambda j:nat.a (plus i j))
683    (ib_lower_bound O' a a)
684    (\lambda n:nat.ib_lower_bound_is_lower_bound O' a a (plus i n))))));
685    apply tail_inf_increasing
686  ].
687 qed.
688
689
690
691
692 definition lt ≝ λO:ordered_set.λa,b:O.a ≤ b ∧ a ≠ b.
693
694 interpretation "Ordered set lt" 'lt a b =
695  (cic:/matita/ordered_sets/lt.con _ a b).