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