author | huffman |
Thu, 21 Sep 2006 03:17:51 +0200 | |
changeset 20653 | 24cda2c5fd40 |
parent 20563 | 44eda2314aab |
child 20682 | cecff1f51431 |
permissions | -rw-r--r-- |
10751 | 1 |
(* Title : SEQ.thy |
2 |
Author : Jacques D. Fleuriot |
|
3 |
Copyright : 1998 University of Cambridge |
|
4 |
Description : Convergence of sequences and series |
|
15082 | 5 |
Conversion to Isar and new proofs by Lawrence C Paulson, 2004 |
16819 | 6 |
Additional contributions by Jeremy Avigad |
15082 | 7 |
*) |
10751 | 8 |
|
17439 | 9 |
header {* Sequences and Series *} |
10 |
||
15131 | 11 |
theory SEQ |
15236
f289e8ba2bb3
Proofs needed to be updated because induction now preserves name of
nipkow
parents:
15229
diff
changeset
|
12 |
imports NatStar |
15131 | 13 |
begin |
10751 | 14 |
|
19765 | 15 |
definition |
10751 | 16 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
17 |
LIMSEQ :: "[nat => 'a::real_normed_vector, 'a] => bool" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
18 |
("((_)/ ----> (_))" [60, 60] 60) |
15082 | 19 |
--{*Standard definition of convergence of sequence*} |
20563 | 20 |
"X ----> L = (\<forall>r. 0 < r --> (\<exists>no. \<forall>n. no \<le> n --> norm (X n - L) < r))" |
10751 | 21 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
22 |
NSLIMSEQ :: "[nat => 'a::real_normed_vector, 'a] => bool" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
23 |
("((_)/ ----NS> (_))" [60, 60] 60) |
15082 | 24 |
--{*Nonstandard definition of convergence of sequence*} |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
25 |
"X ----NS> L = (\<forall>N \<in> HNatInfinite. ( *f* X) N \<approx> star_of L)" |
15082 | 26 |
|
27 |
lim :: "(nat => real) => real" |
|
28 |
--{*Standard definition of limit using choice operator*} |
|
19765 | 29 |
"lim X = (SOME L. (X ----> L))" |
10751 | 30 |
|
15082 | 31 |
nslim :: "(nat => real) => real" |
32 |
--{*Nonstandard definition of limit using choice operator*} |
|
19765 | 33 |
"nslim X = (SOME L. (X ----NS> L))" |
10751 | 34 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
35 |
convergent :: "(nat => 'a::real_normed_vector) => bool" |
15082 | 36 |
--{*Standard definition of convergence*} |
19765 | 37 |
"convergent X = (\<exists>L. (X ----> L))" |
10751 | 38 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
39 |
NSconvergent :: "(nat => 'a::real_normed_vector) => bool" |
15082 | 40 |
--{*Nonstandard definition of convergence*} |
19765 | 41 |
"NSconvergent X = (\<exists>L. (X ----NS> L))" |
15082 | 42 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
43 |
Bseq :: "(nat => 'a::real_normed_vector) => bool" |
15082 | 44 |
--{*Standard definition for bounded sequence*} |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
45 |
"Bseq X = (\<exists>K>0.\<forall>n. norm (X n) \<le> K)" |
10751 | 46 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
47 |
NSBseq :: "(nat => 'a::real_normed_vector) => bool" |
15082 | 48 |
--{*Nonstandard definition for bounded sequence*} |
19765 | 49 |
"NSBseq X = (\<forall>N \<in> HNatInfinite. ( *f* X) N : HFinite)" |
15082 | 50 |
|
51 |
monoseq :: "(nat=>real)=>bool" |
|
52 |
--{*Definition for monotonicity*} |
|
19765 | 53 |
"monoseq X = ((\<forall>m. \<forall>n\<ge>m. X m \<le> X n) | (\<forall>m. \<forall>n\<ge>m. X n \<le> X m))" |
10751 | 54 |
|
15082 | 55 |
subseq :: "(nat => nat) => bool" |
56 |
--{*Definition of subsequence*} |
|
19765 | 57 |
"subseq f = (\<forall>m. \<forall>n>m. (f m) < (f n))" |
10751 | 58 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
59 |
Cauchy :: "(nat => 'a::real_normed_vector) => bool" |
15082 | 60 |
--{*Standard definition of the Cauchy condition*} |
20563 | 61 |
"Cauchy X = (\<forall>e>0. \<exists>M. \<forall>m \<ge> M. \<forall>n \<ge> M. norm (X m - X n) < e)" |
10751 | 62 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
63 |
NSCauchy :: "(nat => 'a::real_normed_vector) => bool" |
15082 | 64 |
--{*Nonstandard definition*} |
19765 | 65 |
"NSCauchy X = (\<forall>M \<in> HNatInfinite. \<forall>N \<in> HNatInfinite. ( *f* X) M \<approx> ( *f* X) N)" |
15082 | 66 |
|
67 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
68 |
declare real_norm_def [simp] |
15082 | 69 |
|
70 |
text{* Example of an hypersequence (i.e. an extended standard sequence) |
|
71 |
whose term with an hypernatural suffix is an infinitesimal i.e. |
|
72 |
the whn'nth term of the hypersequence is a member of Infinitesimal*} |
|
73 |
||
74 |
lemma SEQ_Infinitesimal: |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
75 |
"( *f* (%n::nat. inverse(real(Suc n)))) whn : Infinitesimal" |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
76 |
apply (simp add: hypnat_omega_def starfun star_n_inverse) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
77 |
apply (simp add: Infinitesimal_FreeUltrafilterNat_iff) |
15229 | 78 |
apply (simp add: real_of_nat_Suc_gt_zero FreeUltrafilterNat_inverse_real_of_posnat) |
15082 | 79 |
done |
80 |
||
81 |
||
82 |
subsection{*LIMSEQ and NSLIMSEQ*} |
|
83 |
||
84 |
lemma LIMSEQ_iff: |
|
20563 | 85 |
"(X ----> L) = (\<forall>r>0. \<exists>no. \<forall>n \<ge> no. norm (X n - L) < r)" |
15082 | 86 |
by (simp add: LIMSEQ_def) |
87 |
||
88 |
lemma NSLIMSEQ_iff: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
89 |
"(X ----NS> L) = (\<forall>N \<in> HNatInfinite. ( *f* X) N \<approx> star_of L)" |
15082 | 90 |
by (simp add: NSLIMSEQ_def) |
91 |
||
92 |
||
93 |
text{*LIMSEQ ==> NSLIMSEQ*} |
|
94 |
lemma LIMSEQ_NSLIMSEQ: |
|
95 |
"X ----> L ==> X ----NS> L" |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
96 |
apply (simp add: LIMSEQ_def NSLIMSEQ_def, safe) |
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
97 |
apply (rule_tac x = N in star_cases) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
98 |
apply (simp add: HNatInfinite_FreeUltrafilterNat_iff) |
15082 | 99 |
apply (rule approx_minus_iff [THEN iffD2]) |
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
100 |
apply (auto simp add: starfun mem_infmal_iff [symmetric] star_of_def |
20563 | 101 |
star_n_diff Infinitesimal_FreeUltrafilterNat_iff) |
15082 | 102 |
apply (drule_tac x = u in spec, safe) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
103 |
apply (drule_tac x = no in spec) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
104 |
apply (erule ultra, simp add: less_imp_le) |
15082 | 105 |
done |
106 |
||
107 |
||
108 |
text{*NSLIMSEQ ==> LIMSEQ*} |
|
109 |
||
110 |
lemma lemma_NSLIMSEQ1: "!!(f::nat=>nat). \<forall>n. n \<le> f n |
|
111 |
==> {n. f n = 0} = {0} | {n. f n = 0} = {}" |
|
112 |
apply auto |
|
113 |
apply (drule_tac x = xa in spec) |
|
114 |
apply (drule_tac [2] x = x in spec, auto) |
|
115 |
done |
|
116 |
||
117 |
lemma lemma_NSLIMSEQ2: "{n. f n \<le> Suc u} = {n. f n \<le> u} Un {n. f n = Suc u}" |
|
118 |
by (auto simp add: le_Suc_eq) |
|
119 |
||
120 |
lemma lemma_NSLIMSEQ3: |
|
121 |
"!!(f::nat=>nat). \<forall>n. n \<le> f n ==> {n. f n = Suc u} \<le> {n. n \<le> Suc u}" |
|
122 |
apply auto |
|
123 |
apply (drule_tac x = x in spec, auto) |
|
124 |
done |
|
125 |
||
126 |
text{* the following sequence @{term "f(n)"} defines a hypernatural *} |
|
127 |
lemma NSLIMSEQ_finite_set: |
|
128 |
"!!(f::nat=>nat). \<forall>n. n \<le> f n ==> finite {n. f n \<le> u}" |
|
129 |
apply (induct u) |
|
130 |
apply (auto simp add: lemma_NSLIMSEQ2) |
|
131 |
apply (auto intro: lemma_NSLIMSEQ3 [THEN finite_subset] finite_atMost [unfolded atMost_def]) |
|
132 |
apply (drule lemma_NSLIMSEQ1, safe) |
|
133 |
apply (simp_all (no_asm_simp)) |
|
134 |
done |
|
135 |
||
136 |
lemma Compl_less_set: "- {n. u < (f::nat=>nat) n} = {n. f n \<le> u}" |
|
137 |
by (auto dest: less_le_trans simp add: le_def) |
|
138 |
||
139 |
text{* the index set is in the free ultrafilter *} |
|
140 |
lemma FreeUltrafilterNat_NSLIMSEQ: |
|
141 |
"!!(f::nat=>nat). \<forall>n. n \<le> f n ==> {n. u < f n} : FreeUltrafilterNat" |
|
142 |
apply (rule FreeUltrafilterNat_Compl_iff2 [THEN iffD2]) |
|
143 |
apply (rule FreeUltrafilterNat_finite) |
|
144 |
apply (auto dest: NSLIMSEQ_finite_set simp add: Compl_less_set) |
|
145 |
done |
|
146 |
||
147 |
text{* thus, the sequence defines an infinite hypernatural! *} |
|
148 |
lemma HNatInfinite_NSLIMSEQ: "\<forall>n. n \<le> f n |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
149 |
==> star_n f : HNatInfinite" |
15082 | 150 |
apply (auto simp add: HNatInfinite_FreeUltrafilterNat_iff) |
151 |
apply (erule FreeUltrafilterNat_NSLIMSEQ) |
|
152 |
done |
|
153 |
||
154 |
lemma lemmaLIM: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
155 |
"{n. X (f n) + - L = Y n} Int {n. norm (Y n) < r} \<le> |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
156 |
{n. norm (X (f n) + - L) < r}" |
15082 | 157 |
by auto |
158 |
||
159 |
lemma lemmaLIM2: |
|
20563 | 160 |
"{n. norm (X (f n) - L) < r} Int {n. r \<le> norm (X (f n) - L)} = {}" |
15082 | 161 |
by auto |
162 |
||
20563 | 163 |
lemma lemmaLIM3: "[| 0 < r; \<forall>n. r \<le> norm (X (f n) - L); |
164 |
( *f* X) (star_n f) |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
165 |
- star_of L \<approx> 0 |] ==> False" |
20563 | 166 |
apply (auto simp add: starfun mem_infmal_iff [symmetric] star_of_def star_n_diff Infinitesimal_FreeUltrafilterNat_iff) |
15082 | 167 |
apply (drule_tac x = r in spec, safe) |
168 |
apply (drule FreeUltrafilterNat_all) |
|
169 |
apply (drule FreeUltrafilterNat_Int, assumption) |
|
15539 | 170 |
apply (simp add: lemmaLIM2) |
15082 | 171 |
done |
172 |
||
173 |
lemma NSLIMSEQ_LIMSEQ: "X ----NS> L ==> X ----> L" |
|
174 |
apply (simp add: LIMSEQ_def NSLIMSEQ_def) |
|
175 |
apply (rule ccontr, simp, safe) |
|
176 |
txt{* skolemization step *} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
177 |
apply (drule no_choice, safe) |
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
178 |
apply (drule_tac x = "star_n f" in bspec) |
15082 | 179 |
apply (drule_tac [2] approx_minus_iff [THEN iffD1]) |
180 |
apply (simp_all add: linorder_not_less) |
|
181 |
apply (blast intro: HNatInfinite_NSLIMSEQ) |
|
182 |
apply (blast intro: lemmaLIM3) |
|
183 |
done |
|
184 |
||
185 |
text{* Now, the all-important result is trivially proved! *} |
|
186 |
theorem LIMSEQ_NSLIMSEQ_iff: "(f ----> L) = (f ----NS> L)" |
|
187 |
by (blast intro: LIMSEQ_NSLIMSEQ NSLIMSEQ_LIMSEQ) |
|
188 |
||
189 |
||
190 |
subsection{*Theorems About Sequences*} |
|
191 |
||
192 |
lemma NSLIMSEQ_const: "(%n. k) ----NS> k" |
|
193 |
by (simp add: NSLIMSEQ_def) |
|
194 |
||
195 |
lemma LIMSEQ_const: "(%n. k) ----> k" |
|
196 |
by (simp add: LIMSEQ_def) |
|
197 |
||
198 |
lemma NSLIMSEQ_add: |
|
199 |
"[| X ----NS> a; Y ----NS> b |] ==> (%n. X n + Y n) ----NS> a + b" |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
200 |
by (auto intro: approx_add simp add: NSLIMSEQ_def starfun_add [symmetric]) |
15082 | 201 |
|
202 |
lemma LIMSEQ_add: "[| X ----> a; Y ----> b |] ==> (%n. X n + Y n) ----> a + b" |
|
203 |
by (simp add: LIMSEQ_NSLIMSEQ_iff NSLIMSEQ_add) |
|
204 |
||
16819 | 205 |
lemma LIMSEQ_add_const: "f ----> a ==> (%n.(f n + b)) ----> a + b" |
206 |
apply (subgoal_tac "%n. (f n + b) == %n. (f n + (%n. b) n)") |
|
207 |
apply (subgoal_tac "(%n. b) ----> b") |
|
208 |
apply (auto simp add: LIMSEQ_add LIMSEQ_const) |
|
209 |
done |
|
210 |
||
211 |
lemma NSLIMSEQ_add_const: "f ----NS> a ==> (%n.(f n + b)) ----NS> a + b" |
|
212 |
by (simp add: LIMSEQ_NSLIMSEQ_iff [THEN sym] LIMSEQ_add_const) |
|
213 |
||
15082 | 214 |
lemma NSLIMSEQ_mult: |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
215 |
fixes a b :: "'a::real_normed_algebra" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
216 |
shows "[| X ----NS> a; Y ----NS> b |] ==> (%n. X n * Y n) ----NS> a * b" |
15082 | 217 |
by (auto intro!: approx_mult_HFinite |
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
218 |
simp add: NSLIMSEQ_def starfun_mult [symmetric]) |
15082 | 219 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
220 |
lemma LIMSEQ_mult: |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
221 |
fixes a b :: "'a::real_normed_algebra" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
222 |
shows "[| X ----> a; Y ----> b |] ==> (%n. X n * Y n) ----> a * b" |
15082 | 223 |
by (simp add: LIMSEQ_NSLIMSEQ_iff NSLIMSEQ_mult) |
224 |
||
225 |
lemma NSLIMSEQ_minus: "X ----NS> a ==> (%n. -(X n)) ----NS> -a" |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
226 |
by (auto simp add: NSLIMSEQ_def starfun_minus [symmetric]) |
15082 | 227 |
|
228 |
lemma LIMSEQ_minus: "X ----> a ==> (%n. -(X n)) ----> -a" |
|
229 |
by (simp add: LIMSEQ_NSLIMSEQ_iff NSLIMSEQ_minus) |
|
230 |
||
231 |
lemma LIMSEQ_minus_cancel: "(%n. -(X n)) ----> -a ==> X ----> a" |
|
232 |
by (drule LIMSEQ_minus, simp) |
|
233 |
||
234 |
lemma NSLIMSEQ_minus_cancel: "(%n. -(X n)) ----NS> -a ==> X ----NS> a" |
|
235 |
by (drule NSLIMSEQ_minus, simp) |
|
236 |
||
237 |
lemma NSLIMSEQ_add_minus: |
|
238 |
"[| X ----NS> a; Y ----NS> b |] ==> (%n. X n + -Y n) ----NS> a + -b" |
|
239 |
by (simp add: NSLIMSEQ_add NSLIMSEQ_minus [of Y]) |
|
240 |
||
241 |
lemma LIMSEQ_add_minus: |
|
242 |
"[| X ----> a; Y ----> b |] ==> (%n. X n + -Y n) ----> a + -b" |
|
243 |
by (simp add: LIMSEQ_NSLIMSEQ_iff NSLIMSEQ_add_minus) |
|
244 |
||
245 |
lemma LIMSEQ_diff: "[| X ----> a; Y ----> b |] ==> (%n. X n - Y n) ----> a - b" |
|
246 |
apply (simp add: diff_minus) |
|
247 |
apply (blast intro: LIMSEQ_add_minus) |
|
248 |
done |
|
249 |
||
250 |
lemma NSLIMSEQ_diff: |
|
251 |
"[| X ----NS> a; Y ----NS> b |] ==> (%n. X n - Y n) ----NS> a - b" |
|
252 |
apply (simp add: diff_minus) |
|
253 |
apply (blast intro: NSLIMSEQ_add_minus) |
|
254 |
done |
|
255 |
||
16819 | 256 |
lemma LIMSEQ_diff_const: "f ----> a ==> (%n.(f n - b)) ----> a - b" |
257 |
apply (subgoal_tac "%n. (f n - b) == %n. (f n - (%n. b) n)") |
|
258 |
apply (subgoal_tac "(%n. b) ----> b") |
|
259 |
apply (auto simp add: LIMSEQ_diff LIMSEQ_const) |
|
260 |
done |
|
261 |
||
262 |
lemma NSLIMSEQ_diff_const: "f ----NS> a ==> (%n.(f n - b)) ----NS> a - b" |
|
263 |
by (simp add: LIMSEQ_NSLIMSEQ_iff [THEN sym] LIMSEQ_diff_const) |
|
264 |
||
15082 | 265 |
text{*Proof is like that of @{text NSLIM_inverse}.*} |
266 |
lemma NSLIMSEQ_inverse: |
|
20653
24cda2c5fd40
removed division_by_zero class requirements from several lemmas
huffman
parents:
20563
diff
changeset
|
267 |
fixes a :: "'a::real_normed_div_algebra" |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
268 |
shows "[| X ----NS> a; a ~= 0 |] ==> (%n. inverse(X n)) ----NS> inverse(a)" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
269 |
by (simp add: NSLIMSEQ_def star_of_approx_inverse) |
15082 | 270 |
|
271 |
||
272 |
text{*Standard version of theorem*} |
|
273 |
lemma LIMSEQ_inverse: |
|
20653
24cda2c5fd40
removed division_by_zero class requirements from several lemmas
huffman
parents:
20563
diff
changeset
|
274 |
fixes a :: "'a::real_normed_div_algebra" |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
275 |
shows "[| X ----> a; a ~= 0 |] ==> (%n. inverse(X n)) ----> inverse(a)" |
15082 | 276 |
by (simp add: NSLIMSEQ_inverse LIMSEQ_NSLIMSEQ_iff) |
277 |
||
278 |
lemma NSLIMSEQ_mult_inverse: |
|
20653
24cda2c5fd40
removed division_by_zero class requirements from several lemmas
huffman
parents:
20563
diff
changeset
|
279 |
fixes a b :: "'a::{real_normed_div_algebra,field}" |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
280 |
shows |
15082 | 281 |
"[| X ----NS> a; Y ----NS> b; b ~= 0 |] ==> (%n. X n / Y n) ----NS> a/b" |
282 |
by (simp add: NSLIMSEQ_mult NSLIMSEQ_inverse divide_inverse) |
|
283 |
||
284 |
lemma LIMSEQ_divide: |
|
20653
24cda2c5fd40
removed division_by_zero class requirements from several lemmas
huffman
parents:
20563
diff
changeset
|
285 |
fixes a b :: "'a::{real_normed_div_algebra,field}" |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
286 |
shows "[| X ----> a; Y ----> b; b ~= 0 |] ==> (%n. X n / Y n) ----> a/b" |
15082 | 287 |
by (simp add: LIMSEQ_mult LIMSEQ_inverse divide_inverse) |
288 |
||
289 |
text{*Uniqueness of limit*} |
|
290 |
lemma NSLIMSEQ_unique: "[| X ----NS> a; X ----NS> b |] ==> a = b" |
|
291 |
apply (simp add: NSLIMSEQ_def) |
|
292 |
apply (drule HNatInfinite_whn [THEN [2] bspec])+ |
|
293 |
apply (auto dest: approx_trans3) |
|
294 |
done |
|
295 |
||
296 |
lemma LIMSEQ_unique: "[| X ----> a; X ----> b |] ==> a = b" |
|
297 |
by (simp add: LIMSEQ_NSLIMSEQ_iff NSLIMSEQ_unique) |
|
298 |
||
15312 | 299 |
lemma LIMSEQ_setsum: |
300 |
assumes n: "\<And>n. n \<in> S \<Longrightarrow> X n ----> L n" |
|
301 |
shows "(\<lambda>m. \<Sum>n\<in>S. X n m) ----> (\<Sum>n\<in>S. L n)" |
|
302 |
proof (cases "finite S") |
|
303 |
case True |
|
304 |
thus ?thesis using n |
|
305 |
proof (induct) |
|
306 |
case empty |
|
307 |
show ?case |
|
308 |
by (simp add: LIMSEQ_const) |
|
309 |
next |
|
310 |
case insert |
|
311 |
thus ?case |
|
312 |
by (simp add: LIMSEQ_add) |
|
313 |
qed |
|
314 |
next |
|
315 |
case False |
|
316 |
thus ?thesis |
|
317 |
by (simp add: setsum_def LIMSEQ_const) |
|
318 |
qed |
|
319 |
||
16819 | 320 |
lemma LIMSEQ_setprod: |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
321 |
fixes L :: "'a \<Rightarrow> 'b::{real_normed_algebra,comm_ring_1}" |
16819 | 322 |
assumes n: "\<And>n. n \<in> S \<Longrightarrow> X n ----> L n" |
323 |
shows "(\<lambda>m. \<Prod>n\<in>S. X n m) ----> (\<Prod>n\<in>S. L n)" |
|
324 |
proof (cases "finite S") |
|
325 |
case True |
|
326 |
thus ?thesis using n |
|
327 |
proof (induct) |
|
328 |
case empty |
|
329 |
show ?case |
|
330 |
by (simp add: LIMSEQ_const) |
|
331 |
next |
|
332 |
case insert |
|
333 |
thus ?case |
|
334 |
by (simp add: LIMSEQ_mult) |
|
335 |
qed |
|
336 |
next |
|
337 |
case False |
|
338 |
thus ?thesis |
|
339 |
by (simp add: setprod_def LIMSEQ_const) |
|
340 |
qed |
|
341 |
||
342 |
lemma LIMSEQ_ignore_initial_segment: "f ----> a |
|
343 |
==> (%n. f(n + k)) ----> a" |
|
344 |
apply (unfold LIMSEQ_def) |
|
345 |
apply (clarify) |
|
346 |
apply (drule_tac x = r in spec) |
|
347 |
apply (clarify) |
|
348 |
apply (rule_tac x = "no + k" in exI) |
|
349 |
by auto |
|
350 |
||
351 |
lemma LIMSEQ_offset: "(%x. f (x + k)) ----> a ==> |
|
352 |
f ----> a" |
|
353 |
apply (unfold LIMSEQ_def) |
|
354 |
apply clarsimp |
|
355 |
apply (drule_tac x = r in spec) |
|
356 |
apply clarsimp |
|
357 |
apply (rule_tac x = "no + k" in exI) |
|
358 |
apply clarsimp |
|
359 |
apply (drule_tac x = "n - k" in spec) |
|
360 |
apply (frule mp) |
|
361 |
apply arith |
|
362 |
apply simp |
|
363 |
done |
|
364 |
||
365 |
lemma LIMSEQ_diff_approach_zero: |
|
366 |
"g ----> L ==> (%x. f x - g x) ----> 0 ==> |
|
367 |
f ----> L" |
|
368 |
apply (drule LIMSEQ_add) |
|
369 |
apply assumption |
|
370 |
apply simp |
|
371 |
done |
|
372 |
||
373 |
lemma LIMSEQ_diff_approach_zero2: |
|
374 |
"f ----> L ==> (%x. f x - g x) ----> 0 ==> |
|
375 |
g ----> L"; |
|
376 |
apply (drule LIMSEQ_diff) |
|
377 |
apply assumption |
|
378 |
apply simp |
|
379 |
done |
|
380 |
||
15082 | 381 |
|
382 |
subsection{*Nslim and Lim*} |
|
383 |
||
384 |
lemma limI: "X ----> L ==> lim X = L" |
|
385 |
apply (simp add: lim_def) |
|
386 |
apply (blast intro: LIMSEQ_unique) |
|
387 |
done |
|
388 |
||
389 |
lemma nslimI: "X ----NS> L ==> nslim X = L" |
|
390 |
apply (simp add: nslim_def) |
|
391 |
apply (blast intro: NSLIMSEQ_unique) |
|
392 |
done |
|
393 |
||
394 |
lemma lim_nslim_iff: "lim X = nslim X" |
|
395 |
by (simp add: lim_def nslim_def LIMSEQ_NSLIMSEQ_iff) |
|
396 |
||
397 |
||
398 |
subsection{*Convergence*} |
|
399 |
||
400 |
lemma convergentD: "convergent X ==> \<exists>L. (X ----> L)" |
|
401 |
by (simp add: convergent_def) |
|
402 |
||
403 |
lemma convergentI: "(X ----> L) ==> convergent X" |
|
404 |
by (auto simp add: convergent_def) |
|
405 |
||
406 |
lemma NSconvergentD: "NSconvergent X ==> \<exists>L. (X ----NS> L)" |
|
407 |
by (simp add: NSconvergent_def) |
|
408 |
||
409 |
lemma NSconvergentI: "(X ----NS> L) ==> NSconvergent X" |
|
410 |
by (auto simp add: NSconvergent_def) |
|
411 |
||
412 |
lemma convergent_NSconvergent_iff: "convergent X = NSconvergent X" |
|
413 |
by (simp add: convergent_def NSconvergent_def LIMSEQ_NSLIMSEQ_iff) |
|
414 |
||
415 |
lemma NSconvergent_NSLIMSEQ_iff: "NSconvergent X = (X ----NS> nslim X)" |
|
416 |
by (auto intro: someI simp add: NSconvergent_def nslim_def) |
|
417 |
||
418 |
lemma convergent_LIMSEQ_iff: "convergent X = (X ----> lim X)" |
|
419 |
by (auto intro: someI simp add: convergent_def lim_def) |
|
420 |
||
421 |
text{*Subsequence (alternative definition, (e.g. Hoskins)*} |
|
422 |
||
423 |
lemma subseq_Suc_iff: "subseq f = (\<forall>n. (f n) < (f (Suc n)))" |
|
424 |
apply (simp add: subseq_def) |
|
425 |
apply (auto dest!: less_imp_Suc_add) |
|
426 |
apply (induct_tac k) |
|
427 |
apply (auto intro: less_trans) |
|
428 |
done |
|
429 |
||
430 |
||
431 |
subsection{*Monotonicity*} |
|
432 |
||
433 |
lemma monoseq_Suc: |
|
434 |
"monoseq X = ((\<forall>n. X n \<le> X (Suc n)) |
|
435 |
| (\<forall>n. X (Suc n) \<le> X n))" |
|
436 |
apply (simp add: monoseq_def) |
|
437 |
apply (auto dest!: le_imp_less_or_eq) |
|
438 |
apply (auto intro!: lessI [THEN less_imp_le] dest!: less_imp_Suc_add) |
|
439 |
apply (induct_tac "ka") |
|
440 |
apply (auto intro: order_trans) |
|
18585 | 441 |
apply (erule contrapos_np) |
15082 | 442 |
apply (induct_tac "k") |
443 |
apply (auto intro: order_trans) |
|
444 |
done |
|
445 |
||
15360 | 446 |
lemma monoI1: "\<forall>m. \<forall> n \<ge> m. X m \<le> X n ==> monoseq X" |
15082 | 447 |
by (simp add: monoseq_def) |
448 |
||
15360 | 449 |
lemma monoI2: "\<forall>m. \<forall> n \<ge> m. X n \<le> X m ==> monoseq X" |
15082 | 450 |
by (simp add: monoseq_def) |
451 |
||
452 |
lemma mono_SucI1: "\<forall>n. X n \<le> X (Suc n) ==> monoseq X" |
|
453 |
by (simp add: monoseq_Suc) |
|
454 |
||
455 |
lemma mono_SucI2: "\<forall>n. X (Suc n) \<le> X n ==> monoseq X" |
|
456 |
by (simp add: monoseq_Suc) |
|
457 |
||
458 |
||
459 |
subsection{*Bounded Sequence*} |
|
460 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
461 |
lemma BseqD: "Bseq X ==> \<exists>K. 0 < K & (\<forall>n. norm (X n) \<le> K)" |
15082 | 462 |
by (simp add: Bseq_def) |
463 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
464 |
lemma BseqI: "[| 0 < K; \<forall>n. norm (X n) \<le> K |] ==> Bseq X" |
15082 | 465 |
by (auto simp add: Bseq_def) |
466 |
||
467 |
lemma lemma_NBseq_def: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
468 |
"(\<exists>K > 0. \<forall>n. norm (X n) \<le> K) = |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
469 |
(\<exists>N. \<forall>n. norm (X n) \<le> real(Suc N))" |
15082 | 470 |
apply auto |
471 |
prefer 2 apply force |
|
472 |
apply (cut_tac x = K in reals_Archimedean2, clarify) |
|
473 |
apply (rule_tac x = n in exI, clarify) |
|
474 |
apply (drule_tac x = na in spec) |
|
475 |
apply (auto simp add: real_of_nat_Suc) |
|
476 |
done |
|
477 |
||
478 |
text{* alternative definition for Bseq *} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
479 |
lemma Bseq_iff: "Bseq X = (\<exists>N. \<forall>n. norm (X n) \<le> real(Suc N))" |
15082 | 480 |
apply (simp add: Bseq_def) |
481 |
apply (simp (no_asm) add: lemma_NBseq_def) |
|
482 |
done |
|
483 |
||
484 |
lemma lemma_NBseq_def2: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
485 |
"(\<exists>K > 0. \<forall>n. norm (X n) \<le> K) = (\<exists>N. \<forall>n. norm (X n) < real(Suc N))" |
15082 | 486 |
apply (subst lemma_NBseq_def, auto) |
487 |
apply (rule_tac x = "Suc N" in exI) |
|
488 |
apply (rule_tac [2] x = N in exI) |
|
489 |
apply (auto simp add: real_of_nat_Suc) |
|
490 |
prefer 2 apply (blast intro: order_less_imp_le) |
|
491 |
apply (drule_tac x = n in spec, simp) |
|
492 |
done |
|
493 |
||
494 |
(* yet another definition for Bseq *) |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
495 |
lemma Bseq_iff1a: "Bseq X = (\<exists>N. \<forall>n. norm (X n) < real(Suc N))" |
15082 | 496 |
by (simp add: Bseq_def lemma_NBseq_def2) |
497 |
||
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
498 |
lemma NSBseqD: "[| NSBseq X; N: HNatInfinite |] ==> ( *f* X) N : HFinite" |
15082 | 499 |
by (simp add: NSBseq_def) |
500 |
||
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
501 |
lemma NSBseqI: "\<forall>N \<in> HNatInfinite. ( *f* X) N : HFinite ==> NSBseq X" |
15082 | 502 |
by (simp add: NSBseq_def) |
503 |
||
504 |
text{*The standard definition implies the nonstandard definition*} |
|
505 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
506 |
lemma lemma_Bseq: "\<forall>n. norm (X n) \<le> K ==> \<forall>n. norm(X((f::nat=>nat) n)) \<le> K" |
15082 | 507 |
by auto |
508 |
||
509 |
lemma Bseq_NSBseq: "Bseq X ==> NSBseq X" |
|
510 |
apply (simp add: Bseq_def NSBseq_def, safe) |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
511 |
apply (rule_tac x = N in star_cases) |
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
512 |
apply (auto simp add: starfun HFinite_FreeUltrafilterNat_iff |
15082 | 513 |
HNatInfinite_FreeUltrafilterNat_iff) |
514 |
apply (drule_tac f = Xa in lemma_Bseq) |
|
515 |
apply (rule_tac x = "K+1" in exI) |
|
516 |
apply (drule_tac P="%n. ?f n \<le> K" in FreeUltrafilterNat_all, ultra) |
|
517 |
done |
|
518 |
||
519 |
text{*The nonstandard definition implies the standard definition*} |
|
520 |
||
521 |
(* similar to NSLIM proof in REALTOPOS *) |
|
522 |
||
523 |
text{* We need to get rid of the real variable and do so by proving the |
|
524 |
following, which relies on the Archimedean property of the reals. |
|
525 |
When we skolemize we then get the required function @{term "f::nat=>nat"}. |
|
526 |
Otherwise, we would be stuck with a skolem function @{term "f::real=>nat"} |
|
527 |
which woulid be useless.*} |
|
528 |
||
529 |
lemma lemmaNSBseq: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
530 |
"\<forall>K > 0. \<exists>n. K < norm (X n) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
531 |
==> \<forall>N. \<exists>n. real(Suc N) < norm (X n)" |
15082 | 532 |
apply safe |
533 |
apply (cut_tac n = N in real_of_nat_Suc_gt_zero, blast) |
|
534 |
done |
|
535 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
536 |
lemma lemmaNSBseq2: "\<forall>K > 0. \<exists>n::nat. K < norm (X n) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
537 |
==> \<exists>f. \<forall>N. real(Suc N) < norm (X (f N))" |
15082 | 538 |
apply (drule lemmaNSBseq) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
539 |
apply (drule no_choice, blast) |
15082 | 540 |
done |
541 |
||
542 |
lemma real_seq_to_hypreal_HInfinite: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
543 |
"\<forall>N. real(Suc N) < norm (X (f N)) |
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
544 |
==> star_n (X o f) : HInfinite" |
15082 | 545 |
apply (auto simp add: HInfinite_FreeUltrafilterNat_iff o_def) |
546 |
apply (cut_tac u = u in FreeUltrafilterNat_nat_gt_real) |
|
547 |
apply (drule FreeUltrafilterNat_all) |
|
548 |
apply (erule FreeUltrafilterNat_Int [THEN FreeUltrafilterNat_subset]) |
|
549 |
apply (auto simp add: real_of_nat_Suc) |
|
550 |
done |
|
551 |
||
552 |
text{* Now prove that we can get out an infinite hypernatural as well |
|
553 |
defined using the skolem function @{term "f::nat=>nat"} above*} |
|
554 |
||
555 |
lemma lemma_finite_NSBseq: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
556 |
"{n. f n \<le> Suc u & real(Suc n) < norm (X (f n))} \<le> |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
557 |
{n. f n \<le> u & real(Suc n) < norm (X (f n))} Un |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
558 |
{n. real(Suc n) < norm (X (Suc u))}" |
15082 | 559 |
by (auto dest!: le_imp_less_or_eq) |
560 |
||
561 |
lemma lemma_finite_NSBseq2: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
562 |
"finite {n. f n \<le> (u::nat) & real(Suc n) < norm (X(f n))}" |
15251 | 563 |
apply (induct "u") |
15082 | 564 |
apply (rule_tac [2] lemma_finite_NSBseq [THEN finite_subset]) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
565 |
apply (rule_tac B = "{n. real (Suc n) < norm (X 0) }" in finite_subset) |
15082 | 566 |
apply (auto intro: finite_real_of_nat_less_real |
567 |
simp add: real_of_nat_Suc less_diff_eq [symmetric]) |
|
568 |
done |
|
569 |
||
570 |
lemma HNatInfinite_skolem_f: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
571 |
"\<forall>N. real(Suc N) < norm (X (f N)) |
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
572 |
==> star_n f : HNatInfinite" |
15082 | 573 |
apply (auto simp add: HNatInfinite_FreeUltrafilterNat_iff) |
574 |
apply (rule ccontr, drule FreeUltrafilterNat_Compl_mem) |
|
575 |
apply (rule lemma_finite_NSBseq2 [THEN FreeUltrafilterNat_finite, THEN notE]) |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
576 |
apply (subgoal_tac "{n. f n \<le> u & real (Suc n) < norm (X (f n))} = |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
577 |
{n. f n \<le> u} \<inter> {N. real (Suc N) < norm (X (f N))}") |
15082 | 578 |
apply (erule ssubst) |
579 |
apply (auto simp add: linorder_not_less Compl_def) |
|
580 |
done |
|
581 |
||
582 |
lemma NSBseq_Bseq: "NSBseq X ==> Bseq X" |
|
583 |
apply (simp add: Bseq_def NSBseq_def) |
|
584 |
apply (rule ccontr) |
|
585 |
apply (auto simp add: linorder_not_less [symmetric]) |
|
586 |
apply (drule lemmaNSBseq2, safe) |
|
587 |
apply (frule_tac X = X and f = f in real_seq_to_hypreal_HInfinite) |
|
588 |
apply (drule HNatInfinite_skolem_f [THEN [2] bspec]) |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
589 |
apply (auto simp add: starfun o_def HFinite_HInfinite_iff) |
15082 | 590 |
done |
591 |
||
592 |
text{* Equivalence of nonstandard and standard definitions |
|
593 |
for a bounded sequence*} |
|
594 |
lemma Bseq_NSBseq_iff: "(Bseq X) = (NSBseq X)" |
|
595 |
by (blast intro!: NSBseq_Bseq Bseq_NSBseq) |
|
596 |
||
597 |
text{*A convergent sequence is bounded: |
|
598 |
Boundedness as a necessary condition for convergence. |
|
599 |
The nonstandard version has no existential, as usual *} |
|
600 |
||
601 |
lemma NSconvergent_NSBseq: "NSconvergent X ==> NSBseq X" |
|
602 |
apply (simp add: NSconvergent_def NSBseq_def NSLIMSEQ_def) |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
603 |
apply (blast intro: HFinite_star_of approx_sym approx_HFinite) |
15082 | 604 |
done |
605 |
||
606 |
text{*Standard Version: easily now proved using equivalence of NS and |
|
607 |
standard definitions *} |
|
608 |
lemma convergent_Bseq: "convergent X ==> Bseq X" |
|
609 |
by (simp add: NSconvergent_NSBseq convergent_NSconvergent_iff Bseq_NSBseq_iff) |
|
610 |
||
611 |
||
612 |
subsection{*Upper Bounds and Lubs of Bounded Sequences*} |
|
613 |
||
614 |
lemma Bseq_isUb: |
|
615 |
"!!(X::nat=>real). Bseq X ==> \<exists>U. isUb (UNIV::real set) {x. \<exists>n. X n = x} U" |
|
616 |
by (auto intro: isUbI setleI simp add: Bseq_def abs_le_interval_iff) |
|
617 |
||
618 |
||
619 |
text{* Use completeness of reals (supremum property) |
|
620 |
to show that any bounded sequence has a least upper bound*} |
|
621 |
||
622 |
lemma Bseq_isLub: |
|
623 |
"!!(X::nat=>real). Bseq X ==> |
|
624 |
\<exists>U. isLub (UNIV::real set) {x. \<exists>n. X n = x} U" |
|
625 |
by (blast intro: reals_complete Bseq_isUb) |
|
626 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
627 |
lemma NSBseq_isUb: "NSBseq X ==> \<exists>U::real. isUb UNIV {x. \<exists>n. X n = x} U" |
15082 | 628 |
by (simp add: Bseq_NSBseq_iff [symmetric] Bseq_isUb) |
629 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
630 |
lemma NSBseq_isLub: "NSBseq X ==> \<exists>U::real. isLub UNIV {x. \<exists>n. X n = x} U" |
15082 | 631 |
by (simp add: Bseq_NSBseq_iff [symmetric] Bseq_isLub) |
632 |
||
633 |
||
634 |
subsection{*A Bounded and Monotonic Sequence Converges*} |
|
635 |
||
636 |
lemma lemma_converg1: |
|
15360 | 637 |
"!!(X::nat=>real). [| \<forall>m. \<forall> n \<ge> m. X m \<le> X n; |
15082 | 638 |
isLub (UNIV::real set) {x. \<exists>n. X n = x} (X ma) |
15360 | 639 |
|] ==> \<forall>n \<ge> ma. X n = X ma" |
15082 | 640 |
apply safe |
641 |
apply (drule_tac y = "X n" in isLubD2) |
|
642 |
apply (blast dest: order_antisym)+ |
|
643 |
done |
|
644 |
||
645 |
text{* The best of both worlds: Easier to prove this result as a standard |
|
646 |
theorem and then use equivalence to "transfer" it into the |
|
647 |
equivalent nonstandard form if needed!*} |
|
648 |
||
649 |
lemma Bmonoseq_LIMSEQ: "\<forall>n. m \<le> n --> X n = X m ==> \<exists>L. (X ----> L)" |
|
650 |
apply (simp add: LIMSEQ_def) |
|
651 |
apply (rule_tac x = "X m" in exI, safe) |
|
652 |
apply (rule_tac x = m in exI, safe) |
|
653 |
apply (drule spec, erule impE, auto) |
|
654 |
done |
|
655 |
||
656 |
text{*Now, the same theorem in terms of NS limit *} |
|
15360 | 657 |
lemma Bmonoseq_NSLIMSEQ: "\<forall>n \<ge> m. X n = X m ==> \<exists>L. (X ----NS> L)" |
15082 | 658 |
by (auto dest!: Bmonoseq_LIMSEQ simp add: LIMSEQ_NSLIMSEQ_iff) |
659 |
||
660 |
lemma lemma_converg2: |
|
661 |
"!!(X::nat=>real). |
|
662 |
[| \<forall>m. X m ~= U; isLub UNIV {x. \<exists>n. X n = x} U |] ==> \<forall>m. X m < U" |
|
663 |
apply safe |
|
664 |
apply (drule_tac y = "X m" in isLubD2) |
|
665 |
apply (auto dest!: order_le_imp_less_or_eq) |
|
666 |
done |
|
667 |
||
668 |
lemma lemma_converg3: "!!(X ::nat=>real). \<forall>m. X m \<le> U ==> isUb UNIV {x. \<exists>n. X n = x} U" |
|
669 |
by (rule setleI [THEN isUbI], auto) |
|
670 |
||
671 |
text{* FIXME: @{term "U - T < U"} is redundant *} |
|
672 |
lemma lemma_converg4: "!!(X::nat=> real). |
|
673 |
[| \<forall>m. X m ~= U; |
|
674 |
isLub UNIV {x. \<exists>n. X n = x} U; |
|
675 |
0 < T; |
|
676 |
U + - T < U |
|
677 |
|] ==> \<exists>m. U + -T < X m & X m < U" |
|
678 |
apply (drule lemma_converg2, assumption) |
|
679 |
apply (rule ccontr, simp) |
|
680 |
apply (simp add: linorder_not_less) |
|
681 |
apply (drule lemma_converg3) |
|
682 |
apply (drule isLub_le_isUb, assumption) |
|
683 |
apply (auto dest: order_less_le_trans) |
|
684 |
done |
|
685 |
||
686 |
text{*A standard proof of the theorem for monotone increasing sequence*} |
|
687 |
||
688 |
lemma Bseq_mono_convergent: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
689 |
"[| Bseq X; \<forall>m. \<forall>n \<ge> m. X m \<le> X n |] ==> convergent (X::nat=>real)" |
15082 | 690 |
apply (simp add: convergent_def) |
691 |
apply (frule Bseq_isLub, safe) |
|
692 |
apply (case_tac "\<exists>m. X m = U", auto) |
|
693 |
apply (blast dest: lemma_converg1 Bmonoseq_LIMSEQ) |
|
694 |
(* second case *) |
|
695 |
apply (rule_tac x = U in exI) |
|
696 |
apply (subst LIMSEQ_iff, safe) |
|
697 |
apply (frule lemma_converg2, assumption) |
|
698 |
apply (drule lemma_converg4, auto) |
|
699 |
apply (rule_tac x = m in exI, safe) |
|
700 |
apply (subgoal_tac "X m \<le> X n") |
|
701 |
prefer 2 apply blast |
|
702 |
apply (drule_tac x=n and P="%m. X m < U" in spec, arith) |
|
703 |
done |
|
704 |
||
705 |
text{*Nonstandard version of the theorem*} |
|
706 |
||
707 |
lemma NSBseq_mono_NSconvergent: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
708 |
"[| NSBseq X; \<forall>m. \<forall>n \<ge> m. X m \<le> X n |] ==> NSconvergent (X::nat=>real)" |
15082 | 709 |
by (auto intro: Bseq_mono_convergent |
710 |
simp add: convergent_NSconvergent_iff [symmetric] |
|
711 |
Bseq_NSBseq_iff [symmetric]) |
|
712 |
||
713 |
lemma convergent_minus_iff: "(convergent X) = (convergent (%n. -(X n)))" |
|
714 |
apply (simp add: convergent_def) |
|
715 |
apply (auto dest: LIMSEQ_minus) |
|
716 |
apply (drule LIMSEQ_minus, auto) |
|
717 |
done |
|
718 |
||
719 |
lemma Bseq_minus_iff: "Bseq (%n. -(X n)) = Bseq X" |
|
720 |
by (simp add: Bseq_def) |
|
721 |
||
722 |
text{*Main monotonicity theorem*} |
|
723 |
lemma Bseq_monoseq_convergent: "[| Bseq X; monoseq X |] ==> convergent X" |
|
724 |
apply (simp add: monoseq_def, safe) |
|
725 |
apply (rule_tac [2] convergent_minus_iff [THEN ssubst]) |
|
726 |
apply (drule_tac [2] Bseq_minus_iff [THEN ssubst]) |
|
727 |
apply (auto intro!: Bseq_mono_convergent) |
|
728 |
done |
|
729 |
||
730 |
||
731 |
subsection{*A Few More Equivalence Theorems for Boundedness*} |
|
732 |
||
733 |
text{*alternative formulation for boundedness*} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
734 |
lemma Bseq_iff2: "Bseq X = (\<exists>k > 0. \<exists>x. \<forall>n. norm (X(n) + -x) \<le> k)" |
15082 | 735 |
apply (unfold Bseq_def, safe) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
736 |
apply (rule_tac [2] x = "k + norm x" in exI) |
15360 | 737 |
apply (rule_tac x = K in exI, simp) |
15221 | 738 |
apply (rule exI [where x = 0], auto) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
739 |
apply (erule order_less_le_trans, simp) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
740 |
apply (drule_tac x=n in spec, fold diff_def) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
741 |
apply (drule order_trans [OF norm_triangle_ineq2]) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
742 |
apply simp |
15082 | 743 |
done |
744 |
||
745 |
text{*alternative formulation for boundedness*} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
746 |
lemma Bseq_iff3: "Bseq X = (\<exists>k > 0. \<exists>N. \<forall>n. norm(X(n) + -X(N)) \<le> k)" |
15082 | 747 |
apply safe |
748 |
apply (simp add: Bseq_def, safe) |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
749 |
apply (rule_tac x = "K + norm (X N)" in exI) |
15082 | 750 |
apply auto |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
751 |
apply (erule order_less_le_trans, simp) |
15082 | 752 |
apply (rule_tac x = N in exI, safe) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
753 |
apply (drule_tac x = n in spec) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
754 |
apply (rule order_trans [OF norm_triangle_ineq], simp) |
15082 | 755 |
apply (auto simp add: Bseq_iff2) |
756 |
done |
|
757 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
758 |
lemma BseqI2: "(\<forall>n. k \<le> f n & f n \<le> (K::real)) ==> Bseq f" |
15082 | 759 |
apply (simp add: Bseq_def) |
15221 | 760 |
apply (rule_tac x = " (\<bar>k\<bar> + \<bar>K\<bar>) + 1" in exI, auto) |
20217
25b068a99d2b
linear arithmetic splits certain operators (e.g. min, max, abs)
webertj
parents:
19765
diff
changeset
|
761 |
apply (drule_tac x = n in spec, arith) |
15082 | 762 |
done |
763 |
||
764 |
||
765 |
subsection{*Equivalence Between NS and Standard Cauchy Sequences*} |
|
766 |
||
767 |
subsubsection{*Standard Implies Nonstandard*} |
|
768 |
||
769 |
lemma lemmaCauchy1: |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
770 |
"star_n x : HNatInfinite |
15082 | 771 |
==> {n. M \<le> x n} : FreeUltrafilterNat" |
772 |
apply (auto simp add: HNatInfinite_FreeUltrafilterNat_iff) |
|
773 |
apply (drule_tac x = M in spec, ultra) |
|
774 |
done |
|
775 |
||
776 |
lemma lemmaCauchy2: |
|
20563 | 777 |
"{n. \<forall>m n. M \<le> m & M \<le> (n::nat) --> norm (X m - X n) < u} Int |
15082 | 778 |
{n. M \<le> xa n} Int {n. M \<le> x n} \<le> |
20563 | 779 |
{n. norm (X (xa n) - X (x n)) < u}" |
15082 | 780 |
by blast |
781 |
||
782 |
lemma Cauchy_NSCauchy: "Cauchy X ==> NSCauchy X" |
|
783 |
apply (simp add: Cauchy_def NSCauchy_def, safe) |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
784 |
apply (rule_tac x = M in star_cases) |
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
785 |
apply (rule_tac x = N in star_cases) |
15082 | 786 |
apply (rule approx_minus_iff [THEN iffD2]) |
787 |
apply (rule mem_infmal_iff [THEN iffD1]) |
|
20563 | 788 |
apply (auto simp add: starfun star_n_diff Infinitesimal_FreeUltrafilterNat_iff) |
15082 | 789 |
apply (drule spec, auto) |
790 |
apply (drule_tac M = M in lemmaCauchy1) |
|
791 |
apply (drule_tac M = M in lemmaCauchy1) |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
792 |
apply (rule_tac x1 = Xaa in lemmaCauchy2 [THEN [2] FreeUltrafilterNat_subset]) |
15082 | 793 |
apply (rule FreeUltrafilterNat_Int) |
15539 | 794 |
apply (auto intro: FreeUltrafilterNat_Int) |
15082 | 795 |
done |
796 |
||
797 |
subsubsection{*Nonstandard Implies Standard*} |
|
798 |
||
799 |
lemma NSCauchy_Cauchy: "NSCauchy X ==> Cauchy X" |
|
800 |
apply (auto simp add: Cauchy_def NSCauchy_def) |
|
801 |
apply (rule ccontr, simp) |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
802 |
apply (auto dest!: no_choice HNatInfinite_NSLIMSEQ |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
803 |
simp add: all_conj_distrib) |
15082 | 804 |
apply (drule bspec, assumption) |
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
805 |
apply (drule_tac x = "star_n fa" in bspec); |
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
806 |
apply (auto simp add: starfun) |
15082 | 807 |
apply (drule approx_minus_iff [THEN iffD1]) |
808 |
apply (drule mem_infmal_iff [THEN iffD2]) |
|
20563 | 809 |
apply (auto simp add: star_n_diff Infinitesimal_FreeUltrafilterNat_iff) |
15082 | 810 |
done |
811 |
||
812 |
||
813 |
theorem NSCauchy_Cauchy_iff: "NSCauchy X = Cauchy X" |
|
814 |
by (blast intro!: NSCauchy_Cauchy Cauchy_NSCauchy) |
|
815 |
||
816 |
text{*A Cauchy sequence is bounded -- this is the standard |
|
817 |
proof mechanization rather than the nonstandard proof*} |
|
818 |
||
20563 | 819 |
lemma lemmaCauchy: "\<forall>n \<ge> M. norm (X M - X n) < (1::real) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
820 |
==> \<forall>n \<ge> M. norm (X n :: 'a::real_normed_vector) < 1 + norm (X M)" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
821 |
apply (clarify, drule spec, drule (1) mp) |
20563 | 822 |
apply (simp only: norm_minus_commute) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
823 |
apply (drule order_le_less_trans [OF norm_triangle_ineq2]) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
824 |
apply simp |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
825 |
done |
15082 | 826 |
|
827 |
lemma less_Suc_cancel_iff: "(n < Suc M) = (n \<le> M)" |
|
828 |
by auto |
|
829 |
||
20408 | 830 |
text{* Maximal element in subsequence *} |
831 |
lemma SUP_subseq: |
|
832 |
"\<exists>m \<le> M. \<forall>n \<le> M. (X::nat => 'a::linorder) n \<le> X m" |
|
833 |
apply (induct M, simp) |
|
834 |
apply clarify |
|
835 |
apply (rule_tac x="X (Suc M)" and y="X m" in linorder_le_cases) |
|
836 |
apply (rule_tac x="m" in exI) |
|
837 |
apply (simp add: le_Suc_eq) |
|
838 |
apply (rule_tac x="Suc M" in exI) |
|
839 |
apply (simp add: le_Suc_eq) |
|
840 |
apply (blast intro: order_trans) |
|
841 |
done |
|
842 |
||
15082 | 843 |
lemma SUP_rabs_subseq: |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
844 |
"\<exists>m::nat \<le> M. \<forall>n \<le> M. norm (X n) \<le> norm (X m)" |
20408 | 845 |
by (rule SUP_subseq) |
15082 | 846 |
|
847 |
lemma lemma_Nat_covered: |
|
848 |
"[| \<forall>m::nat. m \<le> M --> P M m; |
|
15360 | 849 |
\<forall>m \<ge> M. P M m |] |
15082 | 850 |
==> \<forall>m. P M m" |
851 |
by (auto elim: less_asym simp add: le_def) |
|
852 |
||
853 |
||
854 |
lemma lemma_trans1: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
855 |
"[| \<forall>n \<le> M. norm ((X::nat=>'a::real_normed_vector) n) \<le> a; a < b |] |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
856 |
==> \<forall>n \<le> M. norm (X n) \<le> b" |
15082 | 857 |
by (blast intro: order_le_less_trans [THEN order_less_imp_le]) |
858 |
||
859 |
lemma lemma_trans2: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
860 |
"[| \<forall>n \<ge> M. norm ((X::nat=>'a::real_normed_vector) n) < a; a < b |] |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
861 |
==> \<forall>n \<ge> M. norm (X n) \<le> b" |
15082 | 862 |
by (blast intro: order_less_trans [THEN order_less_imp_le]) |
863 |
||
864 |
lemma lemma_trans3: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
865 |
"[| \<forall>n \<le> M. norm (X n) \<le> a; a = b |] |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
866 |
==> \<forall>n \<le> M. norm (X n) \<le> b" |
15082 | 867 |
by auto |
868 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
869 |
lemma lemma_trans4: "\<forall>n \<ge> M. norm ((X::nat=>'a::real_normed_vector) n) < a |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
870 |
==> \<forall>n \<ge> M. norm (X n) \<le> a" |
15082 | 871 |
by (blast intro: order_less_imp_le) |
872 |
||
873 |
||
874 |
text{*Proof is more involved than outlines sketched by various authors |
|
875 |
would suggest*} |
|
876 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
877 |
lemma Bseq_Suc_imp_Bseq: "Bseq (\<lambda>n. X (Suc n)) \<Longrightarrow> Bseq X" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
878 |
apply (unfold Bseq_def, clarify) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
879 |
apply (rule_tac x="max K (norm (X 0))" in exI) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
880 |
apply (simp add: order_less_le_trans [OF _ le_maxI1]) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
881 |
apply (clarify, case_tac "n", simp) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
882 |
apply (simp add: order_trans [OF _ le_maxI1]) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
883 |
done |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
884 |
|
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
885 |
lemma Bseq_shift_imp_Bseq: "Bseq (\<lambda>n. X (n + k)) \<Longrightarrow> Bseq X" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
886 |
apply (induct k, simp_all) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
887 |
apply (subgoal_tac "Bseq (\<lambda>n. X (n + k))", simp) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
888 |
apply (rule Bseq_Suc_imp_Bseq, simp) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
889 |
done |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
890 |
|
15082 | 891 |
lemma Cauchy_Bseq: "Cauchy X ==> Bseq X" |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
892 |
apply (simp add: Cauchy_def) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
893 |
apply (drule spec, drule mp, rule zero_less_one, safe) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
894 |
apply (drule_tac x="M" in spec, simp) |
15082 | 895 |
apply (drule lemmaCauchy) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
896 |
apply (rule_tac k="M" in Bseq_shift_imp_Bseq) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
897 |
apply (simp add: Bseq_def) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
898 |
apply (rule_tac x="1 + norm (X M)" in exI) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
899 |
apply (rule conjI, rule order_less_le_trans [OF zero_less_one], simp) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
900 |
apply (simp add: order_less_imp_le) |
15082 | 901 |
done |
902 |
||
903 |
text{*A Cauchy sequence is bounded -- nonstandard version*} |
|
904 |
||
905 |
lemma NSCauchy_NSBseq: "NSCauchy X ==> NSBseq X" |
|
906 |
by (simp add: Cauchy_Bseq Bseq_NSBseq_iff [symmetric] NSCauchy_Cauchy_iff) |
|
907 |
||
908 |
||
909 |
text{*Equivalence of Cauchy criterion and convergence: |
|
910 |
We will prove this using our NS formulation which provides a |
|
911 |
much easier proof than using the standard definition. We do not |
|
912 |
need to use properties of subsequences such as boundedness, |
|
913 |
monotonicity etc... Compare with Harrison's corresponding proof |
|
914 |
in HOL which is much longer and more complicated. Of course, we do |
|
915 |
not have problems which he encountered with guessing the right |
|
916 |
instantiations for his 'espsilon-delta' proof(s) in this case |
|
917 |
since the NS formulations do not involve existential quantifiers.*} |
|
918 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
919 |
lemma NSCauchy_NSconvergent_iff: "NSCauchy X = NSconvergent (X::nat=>real)" |
15082 | 920 |
apply (simp add: NSconvergent_def NSLIMSEQ_def, safe) |
921 |
apply (frule NSCauchy_NSBseq) |
|
922 |
apply (auto intro: approx_trans2 simp add: NSBseq_def NSCauchy_def) |
|
923 |
apply (drule HNatInfinite_whn [THEN [2] bspec]) |
|
924 |
apply (drule HNatInfinite_whn [THEN [2] bspec]) |
|
925 |
apply (auto dest!: st_part_Ex simp add: SReal_iff) |
|
926 |
apply (blast intro: approx_trans3) |
|
927 |
done |
|
928 |
||
929 |
text{*Standard proof for free*} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
930 |
lemma Cauchy_convergent_iff: "Cauchy X = convergent (X::nat=>real)" |
15082 | 931 |
by (simp add: NSCauchy_Cauchy_iff [symmetric] convergent_NSconvergent_iff NSCauchy_NSconvergent_iff) |
932 |
||
933 |
||
934 |
text{*We can now try and derive a few properties of sequences, |
|
935 |
starting with the limit comparison property for sequences.*} |
|
936 |
||
937 |
lemma NSLIMSEQ_le: |
|
938 |
"[| f ----NS> l; g ----NS> m; |
|
15360 | 939 |
\<exists>N. \<forall>n \<ge> N. f(n) \<le> g(n) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
940 |
|] ==> l \<le> (m::real)" |
15082 | 941 |
apply (simp add: NSLIMSEQ_def, safe) |
942 |
apply (drule starfun_le_mono) |
|
943 |
apply (drule HNatInfinite_whn [THEN [2] bspec])+ |
|
944 |
apply (drule_tac x = whn in spec) |
|
945 |
apply (drule bex_Infinitesimal_iff2 [THEN iffD2])+ |
|
946 |
apply clarify |
|
947 |
apply (auto intro: hypreal_of_real_le_add_Infininitesimal_cancel2) |
|
948 |
done |
|
949 |
||
950 |
(* standard version *) |
|
951 |
lemma LIMSEQ_le: |
|
15360 | 952 |
"[| f ----> l; g ----> m; \<exists>N. \<forall>n \<ge> N. f(n) \<le> g(n) |] |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
953 |
==> l \<le> (m::real)" |
15082 | 954 |
by (simp add: LIMSEQ_NSLIMSEQ_iff NSLIMSEQ_le) |
955 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
956 |
lemma LIMSEQ_le_const: "[| X ----> (r::real); \<forall>n. a \<le> X n |] ==> a \<le> r" |
15082 | 957 |
apply (rule LIMSEQ_le) |
958 |
apply (rule LIMSEQ_const, auto) |
|
959 |
done |
|
960 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
961 |
lemma NSLIMSEQ_le_const: "[| X ----NS> (r::real); \<forall>n. a \<le> X n |] ==> a \<le> r" |
15082 | 962 |
by (simp add: LIMSEQ_NSLIMSEQ_iff LIMSEQ_le_const) |
963 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
964 |
lemma LIMSEQ_le_const2: "[| X ----> (r::real); \<forall>n. X n \<le> a |] ==> r \<le> a" |
15082 | 965 |
apply (rule LIMSEQ_le) |
966 |
apply (rule_tac [2] LIMSEQ_const, auto) |
|
967 |
done |
|
968 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
969 |
lemma NSLIMSEQ_le_const2: "[| X ----NS> (r::real); \<forall>n. X n \<le> a |] ==> r \<le> a" |
15082 | 970 |
by (simp add: LIMSEQ_NSLIMSEQ_iff LIMSEQ_le_const2) |
971 |
||
972 |
text{*Shift a convergent series by 1: |
|
973 |
By the equivalence between Cauchiness and convergence and because |
|
974 |
the successor of an infinite hypernatural is also infinite.*} |
|
975 |
||
976 |
lemma NSLIMSEQ_Suc: "f ----NS> l ==> (%n. f(Suc n)) ----NS> l" |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
977 |
apply (unfold NSLIMSEQ_def, safe) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
978 |
apply (drule_tac x="N + 1" in bspec) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
979 |
apply (erule Nats_1 [THEN [2] HNatInfinite_SHNat_add]) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
980 |
apply (simp add: starfun_shift_one) |
15082 | 981 |
done |
982 |
||
983 |
text{* standard version *} |
|
984 |
lemma LIMSEQ_Suc: "f ----> l ==> (%n. f(Suc n)) ----> l" |
|
985 |
by (simp add: LIMSEQ_NSLIMSEQ_iff NSLIMSEQ_Suc) |
|
986 |
||
987 |
lemma NSLIMSEQ_imp_Suc: "(%n. f(Suc n)) ----NS> l ==> f ----NS> l" |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
988 |
apply (unfold NSLIMSEQ_def, safe) |
15082 | 989 |
apply (drule_tac x="N - 1" in bspec) |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
990 |
apply (erule Nats_1 [THEN [2] HNatInfinite_SHNat_diff]) |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
991 |
apply (simp add: starfun_shift_one) |
15082 | 992 |
done |
993 |
||
994 |
lemma LIMSEQ_imp_Suc: "(%n. f(Suc n)) ----> l ==> f ----> l" |
|
995 |
apply (simp add: LIMSEQ_NSLIMSEQ_iff) |
|
996 |
apply (erule NSLIMSEQ_imp_Suc) |
|
997 |
done |
|
998 |
||
999 |
lemma LIMSEQ_Suc_iff: "((%n. f(Suc n)) ----> l) = (f ----> l)" |
|
1000 |
by (blast intro: LIMSEQ_imp_Suc LIMSEQ_Suc) |
|
1001 |
||
1002 |
lemma NSLIMSEQ_Suc_iff: "((%n. f(Suc n)) ----NS> l) = (f ----NS> l)" |
|
1003 |
by (blast intro: NSLIMSEQ_imp_Suc NSLIMSEQ_Suc) |
|
1004 |
||
1005 |
text{*A sequence tends to zero iff its abs does*} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1006 |
lemma LIMSEQ_rabs_zero: "((%n. \<bar>f n\<bar>) ----> 0) = (f ----> (0::real))" |
15082 | 1007 |
by (simp add: LIMSEQ_def) |
1008 |
||
1009 |
text{*We prove the NS version from the standard one, since the NS proof |
|
1010 |
seems more complicated than the standard one above!*} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1011 |
lemma NSLIMSEQ_rabs_zero: "((%n. \<bar>f n\<bar>) ----NS> 0) = (f ----NS> (0::real))" |
15082 | 1012 |
by (simp add: LIMSEQ_NSLIMSEQ_iff [symmetric] LIMSEQ_rabs_zero) |
1013 |
||
1014 |
text{*Generalization to other limits*} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1015 |
lemma NSLIMSEQ_imp_rabs: "f ----NS> (l::real) ==> (%n. \<bar>f n\<bar>) ----NS> \<bar>l\<bar>" |
15082 | 1016 |
apply (simp add: NSLIMSEQ_def) |
1017 |
apply (auto intro: approx_hrabs |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
1018 |
simp add: starfun_abs hypreal_of_real_hrabs [symmetric]) |
15082 | 1019 |
done |
1020 |
||
1021 |
text{* standard version *} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1022 |
lemma LIMSEQ_imp_rabs: "f ----> (l::real) ==> (%n. \<bar>f n\<bar>) ----> \<bar>l\<bar>" |
15082 | 1023 |
by (simp add: LIMSEQ_NSLIMSEQ_iff NSLIMSEQ_imp_rabs) |
1024 |
||
1025 |
text{*An unbounded sequence's inverse tends to 0*} |
|
1026 |
||
1027 |
text{* standard proof seems easier *} |
|
1028 |
lemma LIMSEQ_inverse_zero: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1029 |
"\<forall>y::real. \<exists>N. \<forall>n \<ge> N. y < f(n) ==> (%n. inverse(f n)) ----> 0" |
15082 | 1030 |
apply (simp add: LIMSEQ_def, safe) |
1031 |
apply (drule_tac x = "inverse r" in spec, safe) |
|
1032 |
apply (rule_tac x = N in exI, safe) |
|
1033 |
apply (drule spec, auto) |
|
1034 |
apply (frule positive_imp_inverse_positive) |
|
1035 |
apply (frule order_less_trans, assumption) |
|
1036 |
apply (frule_tac a = "f n" in positive_imp_inverse_positive) |
|
1037 |
apply (simp add: abs_if) |
|
1038 |
apply (rule_tac t = r in inverse_inverse_eq [THEN subst]) |
|
1039 |
apply (auto intro: inverse_less_iff_less [THEN iffD2] |
|
1040 |
simp del: inverse_inverse_eq) |
|
1041 |
done |
|
1042 |
||
1043 |
lemma NSLIMSEQ_inverse_zero: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1044 |
"\<forall>y::real. \<exists>N. \<forall>n \<ge> N. y < f(n) |
15082 | 1045 |
==> (%n. inverse(f n)) ----NS> 0" |
1046 |
by (simp add: LIMSEQ_NSLIMSEQ_iff [symmetric] LIMSEQ_inverse_zero) |
|
1047 |
||
1048 |
text{*The sequence @{term "1/n"} tends to 0 as @{term n} tends to infinity*} |
|
1049 |
||
1050 |
lemma LIMSEQ_inverse_real_of_nat: "(%n. inverse(real(Suc n))) ----> 0" |
|
1051 |
apply (rule LIMSEQ_inverse_zero, safe) |
|
1052 |
apply (cut_tac x = y in reals_Archimedean2) |
|
1053 |
apply (safe, rule_tac x = n in exI) |
|
1054 |
apply (auto simp add: real_of_nat_Suc) |
|
1055 |
done |
|
1056 |
||
1057 |
lemma NSLIMSEQ_inverse_real_of_nat: "(%n. inverse(real(Suc n))) ----NS> 0" |
|
1058 |
by (simp add: LIMSEQ_NSLIMSEQ_iff [symmetric] LIMSEQ_inverse_real_of_nat) |
|
1059 |
||
1060 |
text{*The sequence @{term "r + 1/n"} tends to @{term r} as @{term n} tends to |
|
1061 |
infinity is now easily proved*} |
|
1062 |
||
1063 |
lemma LIMSEQ_inverse_real_of_nat_add: |
|
1064 |
"(%n. r + inverse(real(Suc n))) ----> r" |
|
1065 |
by (cut_tac LIMSEQ_add [OF LIMSEQ_const LIMSEQ_inverse_real_of_nat], auto) |
|
1066 |
||
1067 |
lemma NSLIMSEQ_inverse_real_of_nat_add: |
|
1068 |
"(%n. r + inverse(real(Suc n))) ----NS> r" |
|
1069 |
by (simp add: LIMSEQ_NSLIMSEQ_iff [symmetric] LIMSEQ_inverse_real_of_nat_add) |
|
1070 |
||
1071 |
lemma LIMSEQ_inverse_real_of_nat_add_minus: |
|
1072 |
"(%n. r + -inverse(real(Suc n))) ----> r" |
|
1073 |
by (cut_tac LIMSEQ_add_minus [OF LIMSEQ_const LIMSEQ_inverse_real_of_nat], auto) |
|
1074 |
||
1075 |
lemma NSLIMSEQ_inverse_real_of_nat_add_minus: |
|
1076 |
"(%n. r + -inverse(real(Suc n))) ----NS> r" |
|
1077 |
by (simp add: LIMSEQ_NSLIMSEQ_iff [symmetric] LIMSEQ_inverse_real_of_nat_add_minus) |
|
1078 |
||
1079 |
lemma LIMSEQ_inverse_real_of_nat_add_minus_mult: |
|
1080 |
"(%n. r*( 1 + -inverse(real(Suc n)))) ----> r" |
|
1081 |
by (cut_tac b=1 in |
|
1082 |
LIMSEQ_mult [OF LIMSEQ_const LIMSEQ_inverse_real_of_nat_add_minus], auto) |
|
1083 |
||
1084 |
lemma NSLIMSEQ_inverse_real_of_nat_add_minus_mult: |
|
1085 |
"(%n. r*( 1 + -inverse(real(Suc n)))) ----NS> r" |
|
1086 |
by (simp add: LIMSEQ_NSLIMSEQ_iff [symmetric] LIMSEQ_inverse_real_of_nat_add_minus_mult) |
|
1087 |
||
1088 |
||
1089 |
text{* Real Powers*} |
|
1090 |
||
1091 |
lemma NSLIMSEQ_pow [rule_format]: |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1092 |
fixes a :: "'a::{real_normed_algebra,recpower}" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1093 |
shows "(X ----NS> a) --> ((%n. (X n) ^ m) ----NS> a ^ m)" |
15251 | 1094 |
apply (induct "m") |
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1095 |
apply (auto simp add: power_Suc intro: NSLIMSEQ_mult NSLIMSEQ_const) |
15082 | 1096 |
done |
1097 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1098 |
lemma LIMSEQ_pow: |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1099 |
fixes a :: "'a::{real_normed_algebra,recpower}" |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1100 |
shows "X ----> a ==> (%n. (X n) ^ m) ----> a ^ m" |
15082 | 1101 |
by (simp add: LIMSEQ_NSLIMSEQ_iff NSLIMSEQ_pow) |
1102 |
||
1103 |
text{*The sequence @{term "x^n"} tends to 0 if @{term "0\<le>x"} and @{term |
|
1104 |
"x<1"}. Proof will use (NS) Cauchy equivalence for convergence and |
|
1105 |
also fact that bounded and monotonic sequence converges.*} |
|
1106 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1107 |
lemma Bseq_realpow: "[| 0 \<le> (x::real); x \<le> 1 |] ==> Bseq (%n. x ^ n)" |
15082 | 1108 |
apply (simp add: Bseq_def) |
1109 |
apply (rule_tac x = 1 in exI) |
|
1110 |
apply (simp add: power_abs) |
|
1111 |
apply (auto dest: power_mono intro: order_less_imp_le simp add: abs_if) |
|
1112 |
done |
|
1113 |
||
1114 |
lemma monoseq_realpow: "[| 0 \<le> x; x \<le> 1 |] ==> monoseq (%n. x ^ n)" |
|
1115 |
apply (clarify intro!: mono_SucI2) |
|
1116 |
apply (cut_tac n = n and N = "Suc n" and a = x in power_decreasing, auto) |
|
1117 |
done |
|
1118 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1119 |
lemma convergent_realpow: |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1120 |
"[| 0 \<le> (x::real); x \<le> 1 |] ==> convergent (%n. x ^ n)" |
15082 | 1121 |
by (blast intro!: Bseq_monoseq_convergent Bseq_realpow monoseq_realpow) |
1122 |
||
1123 |
text{* We now use NS criterion to bring proof of theorem through *} |
|
1124 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1125 |
lemma NSLIMSEQ_realpow_zero: |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1126 |
"[| 0 \<le> (x::real); x < 1 |] ==> (%n. x ^ n) ----NS> 0" |
15082 | 1127 |
apply (simp add: NSLIMSEQ_def) |
1128 |
apply (auto dest!: convergent_realpow simp add: convergent_NSconvergent_iff) |
|
1129 |
apply (frule NSconvergentD) |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
1130 |
apply (auto simp add: NSLIMSEQ_def NSCauchy_NSconvergent_iff [symmetric] NSCauchy_def starfun_pow) |
15082 | 1131 |
apply (frule HNatInfinite_add_one) |
1132 |
apply (drule bspec, assumption) |
|
1133 |
apply (drule bspec, assumption) |
|
1134 |
apply (drule_tac x = "N + (1::hypnat) " in bspec, assumption) |
|
1135 |
apply (simp add: hyperpow_add) |
|
1136 |
apply (drule approx_mult_subst_SReal, assumption) |
|
1137 |
apply (drule approx_trans3, assumption) |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
1138 |
apply (auto simp del: star_of_mult simp add: star_of_mult [symmetric]) |
15082 | 1139 |
done |
1140 |
||
1141 |
text{* standard version *} |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1142 |
lemma LIMSEQ_realpow_zero: |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1143 |
"[| 0 \<le> (x::real); x < 1 |] ==> (%n. x ^ n) ----> 0" |
15082 | 1144 |
by (simp add: NSLIMSEQ_realpow_zero LIMSEQ_NSLIMSEQ_iff) |
1145 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1146 |
lemma LIMSEQ_divide_realpow_zero: |
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1147 |
"1 < (x::real) ==> (%n. a / (x ^ n)) ----> 0" |
15082 | 1148 |
apply (cut_tac a = a and x1 = "inverse x" in |
1149 |
LIMSEQ_mult [OF LIMSEQ_const LIMSEQ_realpow_zero]) |
|
1150 |
apply (auto simp add: divide_inverse power_inverse) |
|
1151 |
apply (simp add: inverse_eq_divide pos_divide_less_eq) |
|
1152 |
done |
|
1153 |
||
15102 | 1154 |
text{*Limit of @{term "c^n"} for @{term"\<bar>c\<bar> < 1"}*} |
15082 | 1155 |
|
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1156 |
lemma LIMSEQ_rabs_realpow_zero: "\<bar>c\<bar> < (1::real) ==> (%n. \<bar>c\<bar> ^ n) ----> 0" |
15082 | 1157 |
by (blast intro!: LIMSEQ_realpow_zero abs_ge_zero) |
1158 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1159 |
lemma NSLIMSEQ_rabs_realpow_zero: "\<bar>c\<bar> < (1::real) ==> (%n. \<bar>c\<bar> ^ n) ----NS> 0" |
15082 | 1160 |
by (simp add: LIMSEQ_rabs_realpow_zero LIMSEQ_NSLIMSEQ_iff [symmetric]) |
1161 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1162 |
lemma LIMSEQ_rabs_realpow_zero2: "\<bar>c\<bar> < (1::real) ==> (%n. c ^ n) ----> 0" |
15082 | 1163 |
apply (rule LIMSEQ_rabs_zero [THEN iffD1]) |
1164 |
apply (auto intro: LIMSEQ_rabs_realpow_zero simp add: power_abs) |
|
1165 |
done |
|
1166 |
||
20552
2c31dd358c21
generalized types of many constants to work over arbitrary vector spaces;
huffman
parents:
20408
diff
changeset
|
1167 |
lemma NSLIMSEQ_rabs_realpow_zero2: "\<bar>c\<bar> < (1::real) ==> (%n. c ^ n) ----NS> 0" |
15082 | 1168 |
by (simp add: LIMSEQ_rabs_realpow_zero2 LIMSEQ_NSLIMSEQ_iff [symmetric]) |
1169 |
||
1170 |
subsection{*Hyperreals and Sequences*} |
|
1171 |
||
1172 |
text{*A bounded sequence is a finite hyperreal*} |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
1173 |
lemma NSBseq_HFinite_hypreal: "NSBseq X ==> star_n X : HFinite" |
17298 | 1174 |
by (auto intro!: bexI lemma_starrel_refl |
15082 | 1175 |
intro: FreeUltrafilterNat_all [THEN FreeUltrafilterNat_subset] |
1176 |
simp add: HFinite_FreeUltrafilterNat_iff Bseq_NSBseq_iff [symmetric] |
|
1177 |
Bseq_iff1a) |
|
1178 |
||
1179 |
text{*A sequence converging to zero defines an infinitesimal*} |
|
1180 |
lemma NSLIMSEQ_zero_Infinitesimal_hypreal: |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
1181 |
"X ----NS> 0 ==> star_n X : Infinitesimal" |
15082 | 1182 |
apply (simp add: NSLIMSEQ_def) |
1183 |
apply (drule_tac x = whn in bspec) |
|
1184 |
apply (simp add: HNatInfinite_whn) |
|
17318
bc1c75855f3d
starfun, starset, and other functions on NS types are now polymorphic;
huffman
parents:
17299
diff
changeset
|
1185 |
apply (auto simp add: hypnat_omega_def mem_infmal_iff [symmetric] starfun) |
15082 | 1186 |
done |
1187 |
||
1188 |
(***--------------------------------------------------------------- |
|
1189 |
Theorems proved by Harrison in HOL that we do not need |
|
1190 |
in order to prove equivalence between Cauchy criterion |
|
1191 |
and convergence: |
|
1192 |
-- Show that every sequence contains a monotonic subsequence |
|
1193 |
Goal "\<exists>f. subseq f & monoseq (%n. s (f n))" |
|
1194 |
-- Show that a subsequence of a bounded sequence is bounded |
|
1195 |
Goal "Bseq X ==> Bseq (%n. X (f n))"; |
|
1196 |
-- Show we can take subsequential terms arbitrarily far |
|
1197 |
up a sequence |
|
1198 |
Goal "subseq f ==> n \<le> f(n)"; |
|
1199 |
Goal "subseq f ==> \<exists>n. N1 \<le> n & N2 \<le> f(n)"; |
|
1200 |
---------------------------------------------------------------***) |
|
1201 |
||
10751 | 1202 |
end |