helm/software/matita/dama/infsup.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 include "sandwich_corollary.ma".
  16
  17 (* 3.19 *)
  18 definition supremum ≝
  19   λR.λml:mlattice R.λxn:sequence ml.λx:ml.
  20     increasing ? xn → upper_bound ? xn x ∧ xn ⇝ x.
  21
  22 definition infimum ≝
  23   λR.λml:mlattice R.λxn:sequence ml.λx:ml.
  24     decreasing ? xn → lower_bound ? xn x ∧ xn ⇝ x.
  25
  26 (* 3.20 *)
  27 lemma supremum_uniq:
  28   ∀R.∀ml:mlattice R.∀xn:sequence ml.increasing ? xn →
  29    ∀x,y:ml.supremum ?? xn x → supremum ?? xn y → δ x y ≈ 0.
  30 intros (R ml xn Hxn x y Sx Sy);
  31 elim (Sx Hxn) (_ Hx); elim (Sy Hxn) (_ Hy);
  32 apply (tends_uniq ?? xn ?? Hx Hy);
  33 qed.
  34
  35 definition shift : ∀R.∀ml:mlattice R.∀xn:sequence ml.nat → sequence ml ≝
  36  λR.λml:mlattice R.λxn:sequence ml.λm:nat.λn.xn (n+m).
  37
  38 definition ank ≝
  39   λR.λml:mlattice R.λxn:sequence ml.λk:nat.
  40     let rec ank_aux (i : nat) ≝
  41       match i with
  42       [ O ⇒ (shift ?? xn k) O
  43       | S n1 ⇒ (shift ?? xn k) (S n1) ∧ ank_aux n1]
  44     in ank_aux.
  45
  46 notation < "'a'\sup k" non associative with precedence 50 for
  47  @{ 'ank $x $k }.
  48
  49 interpretation "ank" 'ank x k =
  50  (cic:/matita/infsup/ank.con _ _ x k).
  51
  52 notation < "'a'(k \atop n)" non associative with precedence 50 for
  53  @{ 'ank2 $x $k $n }.
  54
  55 interpretation "ank2" 'ank2 x k n =
  56  (cic:/matita/infsup/ank.con _ _ x k n).
  57
  58 definition bnk ≝
  59   λR.λml:mlattice R.λxn:sequence ml.λk:nat.
  60     let rec bnk_aux (i : nat) ≝
  61       match i with
  62       [ O ⇒ (shift ?? xn k) O
  63       | S n1 ⇒ (shift ?? xn k) (S n1) ∨ bnk_aux n1]
  64     in bnk_aux.
  65
  66 lemma ank_decreasing:
  67   ∀R.∀ml:mlattice R.∀xn:sequence ml.∀k.decreasing ? (ank ?? xn k).
  68 intros (R ml xn k); unfold; intro n; simplify; apply lem;
  69 qed.
  70
  71 (* 3.26 *)
  72 lemma ankS:
  73   ∀R.∀ml:mlattice R.∀xn:sequence ml.∀k,n:nat.
  74    ((ank ?? xn k) (S n)) ≈ (xn k ∧ ank ?? xn (S k) n).
  75 intros (R ml xn k n); elim n; simplify; [apply meet_comm]
  76 simplify in H; apply (Eq≈ ? (feq_ml ???? (H))); clear H;
  77 apply (Eq≈ ? (meet_assoc ????));
  78 apply (Eq≈ ?? (eq_sym ??? (meet_assoc ????)));
  79 apply feq_mr; rewrite > sym_plus in ⊢ (? ? ? (? ? ? (? (? %))));
  80 simplify; rewrite > sym_plus in ⊢ (? ? ? (? ? ? (? (? %))));
  81 apply meet_comm;
  82 qed.
  83
  84 lemma le_asnk_ansk:
  85   ∀R.∀ml:mlattice R.∀xn:sequence ml.∀k,n.
  86    (ank ?? xn k (S n)) ≤ (ank ?? xn (S k) n).
  87 intros (R ml xn k n);
  88 apply (Le≪ (xn k ∧ ank ?? xn (S k) n) (ankS ?????)); apply lem;
  89 qed.
  90
  91 (* 3.27 *)
  92 lemma sup_increasing:
  93   ∀R.∀ml:mlattice R.∀xn:sequence ml.
  94    ∀alpha:sequence ml. (∀k.strong_inf ml (ank ?? xn k) (alpha k)) →
  95      increasing ml alpha.
  96 intros (R ml xn alpha H); unfold strong_inf in H; unfold lower_bound in H; unfold;
  97 intro r;
  98 elim (H r) (H1r H2r);
  99 elim (H (S r)) (H1sr H2sr); clear H H2r H1sr;
 100 intro e; cases (H2sr ? e) (w Hw); clear e H2sr;
 101 lapply (H1r (S w)) as Hsw; clear H1r;
 102 lapply (le_transitive ???? Hsw (le_asnk_ansk ?????)) as H;
 103 cases (H Hw);
 104 qed.
 105
 106