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 (* 3.27 *)
  85 lemma foo:
  86   ∀R.∀ml:mlattice R.∀xn:sequence ml.
  87    ∀alpha:sequence ml. (∀k.strong_inf ml (ank ?? xn k) (alpha k)) →
  88      increasing ml alpha.
  89 intros (R ml xn alpha H); unfold strong_inf in H; unfold lower_bound in H; unfold;
  90 intro n;
  91 letin H2 ≝ (λk.ankS ?? xn k n); clearbody H2;
  92 cut (∀k.((xn k) ∧ (ank ?? xn (S k) n)) ≤ (ank ?? xn (S k) n)) as H3; [2:intro k; apply lem;]
  93 cut (∀k.(ank ?? xn k (S n)) ≤ (ank ?? xn (S k) n)) as H4; [2:
  94   intro k; apply (le_transitive ml ???? (H3 ?));
  95   apply (Le≪ ? (H2 k));
  96
  97 elim (H (S n)) (H4 H5); intro H6; elim (H5 ? H6) (m Hm);
  98 lapply (H4 m) as H7;
  99
 100  clear H5 H6;
 101
 102
 103
 104 lapply (H n) as H1; clear H; elim H1 (LB H); clear H1;
 105 lapply (LB (S n)) as H1; clear LB;
 106 lapply (ankS ?? xn n n) as H2;
 107
 108 lapply (Le≪ (xn n∧ank R ml xn (S n) n) H2);
 109
 110 cases H (LB H1); clear H;
 111
 112
 113
 114
 115
 116