helm/software/matita/contribs/dama/dama/property_exhaustivity.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 "ordered_uniform.ma".
  16 include "property_sigma.ma".
  17
  18 lemma h_segment_upperbound:
  19   ∀C:half_ordered_set.
  20    ∀s:segment C.
  21     ∀a:sequence (half_segment_ordered_set C s).
  22       upper_bound ? ⌊n,\fst (a n)⌋ (seg_u C s).
  23 intros 4; simplify; cases (a n); simplify; unfold in H;
  24 cases (wloss_prop C); rewrite < H1 in H; simplify; cases H;
  25 assumption;
  26 qed.
  27
  28 notation "'segment_upperbound'" non associative with precedence 90 for @{'segment_upperbound}.
  29 notation "'segment_lowerbound'" non associative with precedence 90 for @{'segment_lowerbound}.
  30
  31 interpretation "segment_upperbound" 'segment_upperbound = (h_segment_upperbound (os_l _)).
  32 interpretation "segment_lowerbound" 'segment_lowerbound = (h_segment_upperbound (os_r _)).
  33
  34 lemma h_segment_preserves_uparrow:
  35   ∀C:half_ordered_set.∀s:segment C.∀a:sequence (half_segment_ordered_set C s).
  36    ∀x,h. uparrow C ⌊n,\fst (a n)⌋ x → uparrow (half_segment_ordered_set C s) a ≪x,h≫.
  37 intros; cases H (Ha Hx); split;
  38 [ intro n; intro H; apply (Ha n); apply (sx2x ???? H);
  39 | cases Hx; split;
  40   [ intro n; intro H; apply (H1 n);apply (sx2x ???? H);
  41   | intros; cases (H2 (\fst y)); [2: apply (sx2x ???? H3);]
  42     exists [apply w] apply (x2sx ?? (a w) y H4);]]
  43 qed.
  44
  45 notation "'segment_preserves_uparrow'" non associative with precedence 90 for @{'segment_preserves_uparrow}.
  46 notation "'segment_preserves_downarrow'" non associative with precedence 90 for @{'segment_preserves_downarrow}.
  47
  48 interpretation "segment_preserves_uparrow" 'segment_preserves_uparrow = (h_segment_preserves_uparrow (os_l _)).
  49 interpretation "segment_preserves_downarrow" 'segment_preserves_downarrow = (h_segment_preserves_uparrow (os_r _)).
  50
  51 (* Fact 2.18 *)
  52 lemma segment_cauchy:
  53   ∀C:ordered_uniform_space.∀s:‡C.∀a:sequence {[s]}.
  54     a is_cauchy → ⌊n,\fst (a n)⌋ is_cauchy.
  55 intros 6;
  56 alias symbol "pi1" (instance 3) = "pair pi1".
  57 alias symbol "pi2" = "pair pi2".
  58 apply (H (λx:{[s]} squareB.U 〈\fst (\fst x),\fst (\snd x)〉));
  59 (unfold segment_ordered_uniform_space; simplify);
  60 exists [apply U] split; [assumption;]
  61 intro; cases b; intros; simplify; split; intros; assumption;
  62 qed.
  63
  64 (* Definition 3.7 *)
  65 definition exhaustive ≝
  66   λC:ordered_uniform_space.
  67    ∀a,b:sequence C.
  68      (a is_increasing → a is_upper_located → a is_cauchy) ∧
  69      (b is_decreasing → b is_lower_located → b is_cauchy).
  70
  71 STOP
  72
  73 lemma h_uparrow_to_in_segment:
  74   ∀C:half_ordered_set.
  75    ∀s:segment C.
  76      ∀a:sequence C.
  77       (∀i.a i ∈ s) →
  78        ∀x:C. uparrow C a x →
  79          in_segment C s x.
  80 intros (C H a H1 x H2); unfold in H2; cases H2; clear H2;unfold in H3 H4; cases H4; clear H4; unfold in H2;
  81 cases (wloss_prop C) (W W); apply prove_in_segment; unfold;
  82 [ apply (hle_transitive ??? x ? (H2 O)); lapply (H1 O) as K; unfold in K; rewrite <W in K;
  83   cases K; unfold in H4 H6; rewrite <W in H6 H4; simplify in H4 H6; assumption;
  84 | intro; cases (H5 ? H4); clear H5 H4;lapply(H1 w) as K; unfold in K; rewrite<W in K;
  85   cases K; unfold in H5 H4; rewrite<W in H4 H5; simplify in H4 H5; apply (H5 H6);
  86 | apply (hle_transitive ??? x ?  (H2 O)); lapply (H1 0) as K; unfold in K; rewrite <W in K;
  87   cases K; unfold in H4 H6; rewrite <W in H4 H6; simplify in H4 H6; assumption;
  88 | intro; cases (H5 ? H4); clear H5 H4;lapply(H1 w) as K; unfold in K; rewrite<W in K;
  89   cases K; unfold in H5 H4; rewrite<W in H4 H5; simplify in H4 H5; apply (H4 H6);]
  90 qed.
  91
  92 notation "'uparrow_to_in_segment'" non associative with precedence 90 for @{'uparrow_to_in_segment}.
  93 notation "'downarrow_to_in_segment'" non associative with precedence 90 for @{'downarrow_to_in_segment}.
  94
  95 interpretation "uparrow_to_in_segment" 'uparrow_to_in_segment = (h_uparrow_to_in_segment (os_l _)).
  96 interpretation "downarrow_to_in_segment" 'downarrow_to_in_segment = (h_uparrow_to_in_segment (os_r _)).
  97
  98 (* Lemma 3.8 NON DUALIZZATO *)
  99 lemma restrict_uniform_convergence_uparrow:
 100   ∀C:ordered_uniform_space.property_sigma C →
 101     ∀s:segment (os_l C).exhaustive (segment_ordered_uniform_space C s) →
 102      ∀a:sequence (segment_ordered_uniform_space C s).
 103       ∀x:C. ⌊n,\fst (a n)⌋ ↑ x →
 104        in_segment (os_l C) s x ∧ ∀h:x ∈ s.a uniform_converges ≪x,h≫.
 105 intros; split;
 106 [1: apply (uparrow_to_in_segment s ⌊n,\fst (a \sub n)⌋ ? x H2);
 107     simplify; intros; cases (a i); assumption;
 108 |2: intros;
 109     lapply (uparrow_upperlocated a ≪x,h≫) as Ha1;
 110       [2: apply (segment_preserves_uparrow s); assumption;]
 111     lapply (segment_preserves_supremum s a ≪?,h≫ H2) as Ha2;
 112     cases Ha2; clear Ha2;
 113     cases (H1 a a); lapply (H5 H3 Ha1) as HaC;
 114     lapply (segment_cauchy C s ? HaC) as Ha;
 115     lapply (sigma_cauchy ? H  ? x ? Ha); [left; assumption]
 116     apply (restric_uniform_convergence C s ≪x,h≫ a Hletin)]
 117 qed.
 118
 119 lemma hint_mah1:
 120   ∀C. Type_OF_ordered_uniform_space1 C → hos_carr (os_r C).
 121   intros; assumption; qed.
 122
 123 coercion hint_mah1 nocomposites.
 124
 125 lemma hint_mah2:
 126   ∀C. sequence (hos_carr (os_l C)) → sequence (hos_carr (os_r C)).
 127   intros; assumption; qed.
 128
 129 coercion hint_mah2 nocomposites.
 130
 131 lemma hint_mah3:
 132   ∀C. Type_OF_ordered_uniform_space C → hos_carr (os_r C).
 133   intros; assumption; qed.
 134
 135 coercion hint_mah3 nocomposites.
 136
 137 lemma hint_mah4:
 138   ∀C. sequence (hos_carr (os_r C)) → sequence (hos_carr (os_l C)).
 139   intros; assumption; qed.
 140
 141 coercion hint_mah4 nocomposites.
 142
 143 lemma hint_mah5:
 144   ∀C. segment (hos_carr (os_r C)) → segment (hos_carr (os_l C)).
 145   intros; assumption; qed.
 146
 147 coercion hint_mah5 nocomposites.
 148
 149 lemma hint_mah6:
 150   ∀C. segment (hos_carr (os_l C)) → segment (hos_carr (os_r C)).
 151   intros; assumption; qed.
 152
 153 coercion hint_mah6 nocomposites.
 154
 155 lemma restrict_uniform_convergence_downarrow:
 156   ∀C:ordered_uniform_space.property_sigma C →
 157     ∀s:segment (os_l C).exhaustive (segment_ordered_uniform_space C s) →
 158      ∀a:sequence (segment_ordered_uniform_space C s).
 159       ∀x:C. ⌊n,\fst (a n)⌋ ↓ x →
 160        in_segment (os_l C) s x ∧ ∀h:x ∈ s.a uniform_converges ≪x,h≫.
 161 intros; split;
 162 [1: apply (downarrow_to_in_segment s ⌊n,\fst (a n)⌋ ? x); [2: apply H2];
 163     simplify; intros; cases (a i); assumption;
 164 |2: intros;
 165     lapply (downarrow_lowerlocated a ≪x,h≫) as Ha1;
 166       [2: apply (segment_preserves_downarrow s a x h H2);]
 167     lapply (segment_preserves_infimum s a ≪?,h≫ H2) as Ha2;
 168     cases Ha2; clear Ha2;
 169     cases (H1 a a); lapply (H6 H3 Ha1) as HaC;
 170     lapply (segment_cauchy C s ? HaC) as Ha;
 171     lapply (sigma_cauchy ? H  ? x ? Ha); [right; assumption]
 172     apply (restric_uniform_convergence C s ≪x,h≫ a Hletin)]
 173 qed.