# HG changeset patch # User huffman # Date 1243576637 25200 # Node ID e17f13cd1280788120aa610d595f0049fc9997b3 # Parent 198eae6f5a35db06eb62e9e9cde336bbea2142ee generalize constants in SEQ.thy to class metric_space diff -r 198eae6f5a35 -r e17f13cd1280 src/HOL/Deriv.thy --- a/src/HOL/Deriv.thy Thu May 28 22:54:57 2009 -0700 +++ b/src/HOL/Deriv.thy Thu May 28 22:57:17 2009 -0700 @@ -577,7 +577,7 @@ apply (drule not_P_Bolzano_bisect', assumption+) apply (rename_tac "l") apply (drule_tac x = l in spec, clarify) -apply (simp add: LIMSEQ_def) +apply (simp add: LIMSEQ_iff) apply (drule_tac P = "%r. 0 ?Q r" and x = "d/2" in spec) apply (drule_tac P = "%r. 0 ?Q r" and x = "d/2" in spec) apply (drule real_less_half_sum, auto) diff -r 198eae6f5a35 -r e17f13cd1280 src/HOL/Integration.thy --- a/src/HOL/Integration.thy Thu May 28 22:54:57 2009 -0700 +++ b/src/HOL/Integration.thy Thu May 28 22:57:17 2009 -0700 @@ -430,7 +430,7 @@ lemma Cauchy_iff2: "Cauchy X = (\j. (\M. \m \ M. \n \ M. \X m - X n\ < inverse(real (Suc j))))" -apply (simp add: Cauchy_def, auto) +apply (simp add: Cauchy_iff, auto) apply (drule reals_Archimedean, safe) apply (drule_tac x = n in spec, auto) apply (rule_tac x = M in exI, auto) diff -r 198eae6f5a35 -r e17f13cd1280 src/HOL/Lim.thy --- a/src/HOL/Lim.thy Thu May 28 22:54:57 2009 -0700 +++ b/src/HOL/Lim.thy Thu May 28 22:57:17 2009 -0700 @@ -700,7 +700,7 @@ } then have "(\no. \n. no \ n \ norm (X (?F n) - L) \ r)" by simp with rdef have "\e>0. (\no. \n. no \ n \ norm (X (?F n) - L) \ e)" by auto - thus ?thesis by (unfold LIMSEQ_def, auto simp add: linorder_not_less) + thus ?thesis by (unfold LIMSEQ_iff, auto simp add: linorder_not_less) qed ultimately show False by simp qed diff -r 198eae6f5a35 -r e17f13cd1280 src/HOL/Log.thy --- a/src/HOL/Log.thy Thu May 28 22:54:57 2009 -0700 +++ b/src/HOL/Log.thy Thu May 28 22:57:17 2009 -0700 @@ -248,7 +248,7 @@ qed lemma LIMSEQ_neg_powr: "0 < s ==> (%x. (real x) powr - s) ----> 0" - apply (unfold LIMSEQ_def) + apply (unfold LIMSEQ_iff) apply clarsimp apply (rule_tac x = "natfloor(r powr (1 / - s)) + 1" in exI) apply clarify diff -r 198eae6f5a35 -r e17f13cd1280 src/HOL/SEQ.thy --- a/src/HOL/SEQ.thy Thu May 28 22:54:57 2009 -0700 +++ b/src/HOL/SEQ.thy Thu May 28 22:57:17 2009 -0700 @@ -18,18 +18,18 @@ [code del]: "Zseq X = (\r>0. \no. \n\no. norm (X n) < r)" definition - LIMSEQ :: "[nat => 'a::real_normed_vector, 'a] => bool" + LIMSEQ :: "[nat \ 'a::metric_space, 'a] \ bool" ("((_)/ ----> (_))" [60, 60] 60) where --{*Standard definition of convergence of sequence*} - [code del]: "X ----> L = (\r. 0 < r --> (\no. \n. no \ n --> norm (X n - L) < r))" + [code del]: "X ----> L = (\r>0. \no. \n\no. dist (X n) L < r)" definition - lim :: "(nat => 'a::real_normed_vector) => 'a" where + lim :: "(nat \ 'a::real_normed_vector) \ 'a" where --{*Standard definition of limit using choice operator*} "lim X = (THE L. X ----> L)" definition - convergent :: "(nat => 'a::real_normed_vector) => bool" where + convergent :: "(nat \ 'a::metric_space) \ bool" where --{*Standard definition of convergence*} "convergent X = (\L. X ----> L)" @@ -62,9 +62,9 @@ [code del]: "subseq f = (\m. \n>m. (f m) < (f n))" definition - Cauchy :: "(nat => 'a::real_normed_vector) => bool" where + Cauchy :: "(nat \ 'a::metric_space) \ bool" where --{*Standard definition of the Cauchy condition*} - [code del]: "Cauchy X = (\e>0. \M. \m \ M. \n \ M. norm (X m - X n) < e)" + [code del]: "Cauchy X = (\e>0. \M. \m \ M. \n \ M. dist (X m) (X n) < e)" subsection {* Bounded Sequences *} @@ -302,28 +302,46 @@ subsection {* Limits of Sequences *} lemma LIMSEQ_iff: - "(X ----> L) = (\r>0. \no. \n \ no. norm (X n - L) < r)" -by (rule LIMSEQ_def) + fixes L :: "'a::real_normed_vector" + shows "(X ----> L) = (\r>0. \no. \n \ no. norm (X n - L) < r)" +unfolding LIMSEQ_def dist_norm .. lemma LIMSEQ_Zseq_iff: "((\n. X n) ----> L) = Zseq (\n. X n - L)" -by (simp only: LIMSEQ_def Zseq_def) +by (simp only: LIMSEQ_iff Zseq_def) + +lemma metric_LIMSEQ_I: + "(\r. 0 < r \ \no. \n\no. dist (X n) L < r) \ X ----> L" +by (simp add: LIMSEQ_def) + +lemma metric_LIMSEQ_D: + "\X ----> L; 0 < r\ \ \no. \n\no. dist (X n) L < r" +by (simp add: LIMSEQ_def) lemma LIMSEQ_I: - "(\r. 0 < r \ \no. \n\no. norm (X n - L) < r) \ X ----> L" -by (simp add: LIMSEQ_def) + fixes L :: "'a::real_normed_vector" + shows "(\r. 0 < r \ \no. \n\no. norm (X n - L) < r) \ X ----> L" +by (simp add: LIMSEQ_iff) lemma LIMSEQ_D: - "\X ----> L; 0 < r\ \ \no. \n\no. norm (X n - L) < r" -by (simp add: LIMSEQ_def) + fixes L :: "'a::real_normed_vector" + shows "\X ----> L; 0 < r\ \ \no. \n\no. norm (X n - L) < r" +by (simp add: LIMSEQ_iff) lemma LIMSEQ_const: "(\n. k) ----> k" by (simp add: LIMSEQ_def) -lemma LIMSEQ_const_iff: "(\n. k) ----> l = (k = l)" -by (simp add: LIMSEQ_Zseq_iff Zseq_const_iff) +lemma LIMSEQ_const_iff: "(\n. k) ----> l \ k = l" +apply (safe intro!: LIMSEQ_const) +apply (rule ccontr) +apply (drule_tac r="dist k l" in metric_LIMSEQ_D) +apply (simp add: zero_less_dist_iff) +apply auto +done -lemma LIMSEQ_norm: "X ----> a \ (\n. norm (X n)) ----> norm a" -apply (simp add: LIMSEQ_def, safe) +lemma LIMSEQ_norm: + fixes a :: "'a::real_normed_vector" + shows "X ----> a \ (\n. norm (X n)) ----> norm a" +apply (simp add: LIMSEQ_iff, safe) apply (drule_tac x="r" in spec, safe) apply (rule_tac x="no" in exI, safe) apply (drule_tac x="n" in spec, safe) @@ -332,8 +350,8 @@ lemma LIMSEQ_ignore_initial_segment: "f ----> a \ (\n. f (n + k)) ----> a" -apply (rule LIMSEQ_I) -apply (drule (1) LIMSEQ_D) +apply (rule metric_LIMSEQ_I) +apply (drule (1) metric_LIMSEQ_D) apply (erule exE, rename_tac N) apply (rule_tac x=N in exI) apply simp @@ -341,8 +359,8 @@ lemma LIMSEQ_offset: "(\n. f (n + k)) ----> a \ f ----> a" -apply (rule LIMSEQ_I) -apply (drule (1) LIMSEQ_D) +apply (rule metric_LIMSEQ_I) +apply (drule (1) metric_LIMSEQ_D) apply (erule exE, rename_tac N) apply (rule_tac x="N + k" in exI) apply clarify @@ -374,20 +392,36 @@ shows "(- a) - (- b) = - (a - b)" by simp -lemma LIMSEQ_add: "\X ----> a; Y ----> b\ \ (\n. X n + Y n) ----> a + b" +lemma LIMSEQ_add: + fixes a b :: "'a::real_normed_vector" + shows "\X ----> a; Y ----> b\ \ (\n. X n + Y n) ----> a + b" by (simp only: LIMSEQ_Zseq_iff add_diff_add Zseq_add) -lemma LIMSEQ_minus: "X ----> a \ (\n. - X n) ----> - a" +lemma LIMSEQ_minus: + fixes a :: "'a::real_normed_vector" + shows "X ----> a \ (\n. - X n) ----> - a" by (simp only: LIMSEQ_Zseq_iff minus_diff_minus Zseq_minus) -lemma LIMSEQ_minus_cancel: "(\n. - X n) ----> - a \ X ----> a" +lemma LIMSEQ_minus_cancel: + fixes a :: "'a::real_normed_vector" + shows "(\n. - X n) ----> - a \ X ----> a" by (drule LIMSEQ_minus, simp) -lemma LIMSEQ_diff: "\X ----> a; Y ----> b\ \ (\n. X n - Y n) ----> a - b" +lemma LIMSEQ_diff: + fixes a b :: "'a::real_normed_vector" + shows "\X ----> a; Y ----> b\ \ (\n. X n - Y n) ----> a - b" by (simp add: diff_minus LIMSEQ_add LIMSEQ_minus) lemma LIMSEQ_unique: "\X ----> a; X ----> b\ \ a = b" -by (drule (1) LIMSEQ_diff, simp add: LIMSEQ_const_iff) +apply (rule ccontr) +apply (drule_tac r="dist a b / 2" in metric_LIMSEQ_D, simp add: zero_less_dist_iff) +apply (drule_tac r="dist a b / 2" in metric_LIMSEQ_D, simp add: zero_less_dist_iff) +apply (clarify, rename_tac M N) +apply (subgoal_tac "dist a b < dist a b / 2 + dist a b / 2", simp) +apply (subgoal_tac "dist a b \ dist (X (max M N)) a + dist (X (max M N)) b") +apply (erule le_less_trans, rule add_strict_mono, simp, simp) +apply (subst dist_commute, rule dist_triangle) +done lemma (in bounded_linear) LIMSEQ: "X ----> a \ (\n. f (X n)) ----> f a" @@ -492,6 +526,7 @@ by (induct m) (simp_all add: LIMSEQ_const LIMSEQ_mult) lemma LIMSEQ_setsum: + fixes L :: "'a \ 'b::real_normed_vector" assumes n: "\n. n \ S \ X n ----> L n" shows "(\m. \n\S. X n m) ----> (\n\S. L n)" proof (cases "finite S") @@ -534,39 +569,40 @@ by (simp add: setprod_def LIMSEQ_const) qed -lemma LIMSEQ_add_const: "f ----> a ==> (%n.(f n + b)) ----> a + b" +lemma LIMSEQ_add_const: + fixes a :: "'a::real_normed_vector" + shows "f ----> a ==> (%n.(f n + b)) ----> a + b" by (simp add: LIMSEQ_add LIMSEQ_const) (* FIXME: delete *) lemma LIMSEQ_add_minus: - "[| X ----> a; Y ----> b |] ==> (%n. X n + -Y n) ----> a + -b" + fixes a b :: "'a::real_normed_vector" + shows "[| X ----> a; Y ----> b |] ==> (%n. X n + -Y n) ----> a + -b" by (simp only: LIMSEQ_add LIMSEQ_minus) -lemma LIMSEQ_diff_const: "f ----> a ==> (%n.(f n - b)) ----> a - b" +lemma LIMSEQ_diff_const: + fixes a b :: "'a::real_normed_vector" + shows "f ----> a ==> (%n.(f n - b)) ----> a - b" by (simp add: LIMSEQ_diff LIMSEQ_const) -lemma LIMSEQ_diff_approach_zero: - "g ----> L ==> (%x. f x - g x) ----> 0 ==> - f ----> L" - apply (drule LIMSEQ_add) - apply assumption - apply simp -done +lemma LIMSEQ_diff_approach_zero: + fixes L :: "'a::real_normed_vector" + shows "g ----> L ==> (%x. f x - g x) ----> 0 ==> f ----> L" +by (drule (1) LIMSEQ_add, simp) -lemma LIMSEQ_diff_approach_zero2: - "f ----> L ==> (%x. f x - g x) ----> 0 ==> - g ----> L"; - apply (drule LIMSEQ_diff) - apply assumption - apply simp -done +lemma LIMSEQ_diff_approach_zero2: + fixes L :: "'a::real_normed_vector" + shows "f ----> L ==> (%x. f x - g x) ----> 0 ==> g ----> L"; +by (drule (1) LIMSEQ_diff, simp) text{*A sequence tends to zero iff its abs does*} -lemma LIMSEQ_norm_zero: "((\n. norm (X n)) ----> 0) = (X ----> 0)" -by (simp add: LIMSEQ_def) +lemma LIMSEQ_norm_zero: + fixes X :: "nat \ 'a::real_normed_vector" + shows "((\n. norm (X n)) ----> 0) \ (X ----> 0)" +by (simp add: LIMSEQ_iff) lemma LIMSEQ_rabs_zero: "((%n. \f n\) ----> 0) = (f ----> (0::real))" -by (simp add: LIMSEQ_def) +by (simp add: LIMSEQ_iff) lemma LIMSEQ_imp_rabs: "f ----> (l::real) ==> (%n. \f n\) ----> \l\" by (drule LIMSEQ_norm, simp) @@ -653,7 +689,9 @@ lemma convergent_LIMSEQ_iff: "convergent X = (X ----> lim X)" by (auto intro: theI LIMSEQ_unique simp add: convergent_def lim_def) -lemma convergent_minus_iff: "(convergent X) = (convergent (%n. -(X n)))" +lemma convergent_minus_iff: + fixes X :: "nat \ 'a::real_normed_vector" + shows "convergent X \ convergent (\n. - X n)" apply (simp add: convergent_def) apply (auto dest: LIMSEQ_minus) apply (drule LIMSEQ_minus, auto) @@ -1119,20 +1157,35 @@ subsection {* Cauchy Sequences *} -lemma CauchyI: - "(\e. 0 < e \ \M. \m\M. \n\M. norm (X m - X n) < e) \ Cauchy X" +lemma metric_CauchyI: + "(\e. 0 < e \ \M. \m\M. \n\M. dist (X m) (X n) < e) \ Cauchy X" +by (simp add: Cauchy_def) + +lemma metric_CauchyD: + "\Cauchy X; 0 < e\ \ \M. \m\M. \n\M. dist (X m) (X n) < e" by (simp add: Cauchy_def) +lemma Cauchy_iff: + fixes X :: "nat \ 'a::real_normed_vector" + shows "Cauchy X \ (\e>0. \M. \m\M. \n\M. norm (X m - X n) < e)" +unfolding Cauchy_def dist_norm .. + +lemma CauchyI: + fixes X :: "nat \ 'a::real_normed_vector" + shows "(\e. 0 < e \ \M. \m\M. \n\M. norm (X m - X n) < e) \ Cauchy X" +by (simp add: Cauchy_iff) + lemma CauchyD: - "\Cauchy X; 0 < e\ \ \M. \m\M. \n\M. norm (X m - X n) < e" -by (simp add: Cauchy_def) + fixes X :: "nat \ 'a::real_normed_vector" + shows "\Cauchy X; 0 < e\ \ \M. \m\M. \n\M. norm (X m - X n) < e" +by (simp add: Cauchy_iff) lemma Cauchy_subseq_Cauchy: "\ Cauchy X; subseq f \ \ Cauchy (X o f)" -apply (auto simp add: Cauchy_def) -apply (drule_tac x=e in spec, clarify) -apply (rule_tac x=M in exI, clarify) -apply (blast intro: seq_suble le_trans dest!: spec) +apply (auto simp add: Cauchy_def) +apply (drule_tac x=e in spec, clarify) +apply (rule_tac x=M in exI, clarify) +apply (blast intro: le_trans [OF _ seq_suble] dest!: spec) done subsubsection {* Cauchy Sequences are Bounded *} @@ -1149,7 +1202,7 @@ done lemma Cauchy_Bseq: "Cauchy X ==> Bseq X" -apply (simp add: Cauchy_def) +apply (simp add: Cauchy_iff) apply (drule spec, drule mp, rule zero_less_one, safe) apply (drule_tac x="M" in spec, simp) apply (drule lemmaCauchy) @@ -1167,22 +1220,21 @@ theorem LIMSEQ_imp_Cauchy: assumes X: "X ----> a" shows "Cauchy X" -proof (rule CauchyI) +proof (rule metric_CauchyI) fix e::real assume "0 < e" hence "0 < e/2" by simp - with X have "\N. \n\N. norm (X n - a) < e/2" by (rule LIMSEQ_D) - then obtain N where N: "\n\N. norm (X n - a) < e/2" .. - show "\N. \m\N. \n\N. norm (X m - X n) < e" + with X have "\N. \n\N. dist (X n) a < e/2" by (rule metric_LIMSEQ_D) + then obtain N where N: "\n\N. dist (X n) a < e/2" .. + show "\N. \m\N. \n\N. dist (X m) (X n) < e" proof (intro exI allI impI) fix m assume "N \ m" - hence m: "norm (X m - a) < e/2" using N by fast + hence m: "dist (X m) a < e/2" using N by fast fix n assume "N \ n" - hence n: "norm (X n - a) < e/2" using N by fast - have "norm (X m - X n) = norm ((X m - a) - (X n - a))" by simp - also have "\ \ norm (X m - a) + norm (X n - a)" - by (rule norm_triangle_ineq4) - also from m n have "\ < e" by(simp add:field_simps) - finally show "norm (X m - X n) < e" . + hence n: "dist (X n) a < e/2" using N by fast + have "dist (X m) (X n) \ dist (X m) a + dist (X n) a" + by (rule dist_triangle2) + also from m n have "\ < e" by simp + finally show "dist (X m) (X n) < e" . qed qed @@ -1311,7 +1363,7 @@ lemma convergent_subseq_convergent: fixes X :: "nat \ 'a::banach" shows "\ convergent X; subseq f \ \ convergent (X o f)" - by (simp add: Cauchy_subseq_Cauchy Cauchy_convergent_iff [symmetric]) + by (simp add: Cauchy_subseq_Cauchy Cauchy_convergent_iff [symmetric]) subsection {* Power Sequences *} diff -r 198eae6f5a35 -r e17f13cd1280 src/HOL/Series.thy --- a/src/HOL/Series.thy Thu May 28 22:54:57 2009 -0700 +++ b/src/HOL/Series.thy Thu May 28 22:57:17 2009 -0700 @@ -160,7 +160,7 @@ lemma series_zero: "(\m. n \ m --> f(m) = 0) ==> f sums (setsum f {0.. (%n. setsum f {n*k.. f ----> 0" apply (drule summable_convergent_sumr_iff [THEN iffD1]) apply (drule convergent_Cauchy) -apply (simp only: Cauchy_def LIMSEQ_def, safe) +apply (simp only: Cauchy_iff LIMSEQ_iff, safe) apply (drule_tac x="r" in spec, safe) apply (rule_tac x="M" in exI, safe) apply (drule_tac x="Suc n" in spec, simp) @@ -371,7 +371,7 @@ lemma summable_Cauchy: "summable (f::nat \ 'a::banach) = (\e > 0. \N. \m \ N. \n. norm (setsum f {m..