src/HOL/Hyperreal/SEQ.thy
changeset 20563 44eda2314aab
parent 20552 2c31dd358c21
child 20653 24cda2c5fd40
equal deleted inserted replaced
20562:c2f672be8522 20563:44eda2314aab
    15 definition
    15 definition
    16 
    16 
    17   LIMSEQ :: "[nat => 'a::real_normed_vector, 'a] => bool"
    17   LIMSEQ :: "[nat => 'a::real_normed_vector, 'a] => bool"
    18     ("((_)/ ----> (_))" [60, 60] 60)
    18     ("((_)/ ----> (_))" [60, 60] 60)
    19     --{*Standard definition of convergence of sequence*}
    19     --{*Standard definition of convergence of sequence*}
    20   "X ----> L = (\<forall>r. 0 < r --> (\<exists>no. \<forall>n. no \<le> n --> norm (X n + -L) < r))"
    20   "X ----> L = (\<forall>r. 0 < r --> (\<exists>no. \<forall>n. no \<le> n --> norm (X n - L) < r))"
    21 
    21 
    22   NSLIMSEQ :: "[nat => 'a::real_normed_vector, 'a] => bool"
    22   NSLIMSEQ :: "[nat => 'a::real_normed_vector, 'a] => bool"
    23     ("((_)/ ----NS> (_))" [60, 60] 60)
    23     ("((_)/ ----NS> (_))" [60, 60] 60)
    24     --{*Nonstandard definition of convergence of sequence*}
    24     --{*Nonstandard definition of convergence of sequence*}
    25   "X ----NS> L = (\<forall>N \<in> HNatInfinite. ( *f* X) N \<approx> star_of L)"
    25   "X ----NS> L = (\<forall>N \<in> HNatInfinite. ( *f* X) N \<approx> star_of L)"
    56     --{*Definition of subsequence*}
    56     --{*Definition of subsequence*}
    57   "subseq f = (\<forall>m. \<forall>n>m. (f m) < (f n))"
    57   "subseq f = (\<forall>m. \<forall>n>m. (f m) < (f n))"
    58 
    58 
    59   Cauchy :: "(nat => 'a::real_normed_vector) => bool"
    59   Cauchy :: "(nat => 'a::real_normed_vector) => bool"
    60     --{*Standard definition of the Cauchy condition*}
    60     --{*Standard definition of the Cauchy condition*}
    61   "Cauchy X = (\<forall>e>0. \<exists>M. \<forall>m \<ge> M. \<forall>n \<ge> M. norm((X m) + -(X n)) < e)"
    61   "Cauchy X = (\<forall>e>0. \<exists>M. \<forall>m \<ge> M. \<forall>n \<ge> M. norm (X m - X n) < e)"
    62 
    62 
    63   NSCauchy :: "(nat => 'a::real_normed_vector) => bool"
    63   NSCauchy :: "(nat => 'a::real_normed_vector) => bool"
    64     --{*Nonstandard definition*}
    64     --{*Nonstandard definition*}
    65   "NSCauchy X = (\<forall>M \<in> HNatInfinite. \<forall>N \<in> HNatInfinite. ( *f* X) M \<approx> ( *f* X) N)"
    65   "NSCauchy X = (\<forall>M \<in> HNatInfinite. \<forall>N \<in> HNatInfinite. ( *f* X) M \<approx> ( *f* X) N)"
    66 
    66 
    80 
    80 
    81 
    81 
    82 subsection{*LIMSEQ and NSLIMSEQ*}
    82 subsection{*LIMSEQ and NSLIMSEQ*}
    83 
    83 
    84 lemma LIMSEQ_iff:
    84 lemma LIMSEQ_iff:
    85       "(X ----> L) = (\<forall>r>0. \<exists>no. \<forall>n \<ge> no. norm (X n + -L) < r)"
    85       "(X ----> L) = (\<forall>r>0. \<exists>no. \<forall>n \<ge> no. norm (X n - L) < r)"
    86 by (simp add: LIMSEQ_def)
    86 by (simp add: LIMSEQ_def)
    87 
    87 
    88 lemma NSLIMSEQ_iff:
    88 lemma NSLIMSEQ_iff:
    89     "(X ----NS> L) = (\<forall>N \<in> HNatInfinite. ( *f* X) N \<approx> star_of L)"
    89     "(X ----NS> L) = (\<forall>N \<in> HNatInfinite. ( *f* X) N \<approx> star_of L)"
    90 by (simp add: NSLIMSEQ_def)
    90 by (simp add: NSLIMSEQ_def)
    96 apply (simp add: LIMSEQ_def NSLIMSEQ_def, safe)
    96 apply (simp add: LIMSEQ_def NSLIMSEQ_def, safe)
    97 apply (rule_tac x = N in star_cases)
    97 apply (rule_tac x = N in star_cases)
    98 apply (simp add: HNatInfinite_FreeUltrafilterNat_iff)
    98 apply (simp add: HNatInfinite_FreeUltrafilterNat_iff)
    99 apply (rule approx_minus_iff [THEN iffD2])
    99 apply (rule approx_minus_iff [THEN iffD2])
   100 apply (auto simp add: starfun mem_infmal_iff [symmetric] star_of_def
   100 apply (auto simp add: starfun mem_infmal_iff [symmetric] star_of_def
   101               star_n_minus star_n_add Infinitesimal_FreeUltrafilterNat_iff)
   101               star_n_diff Infinitesimal_FreeUltrafilterNat_iff)
   102 apply (drule_tac x = u in spec, safe)
   102 apply (drule_tac x = u in spec, safe)
   103 apply (drule_tac x = no in spec)
   103 apply (drule_tac x = no in spec)
   104 apply (erule ultra, simp add: less_imp_le)
   104 apply (erule ultra, simp add: less_imp_le)
   105 done
   105 done
   106 
   106 
   155      "{n. X (f n) + - L = Y n} Int {n. norm (Y n) < r} \<le>
   155      "{n. X (f n) + - L = Y n} Int {n. norm (Y n) < r} \<le>
   156       {n. norm (X (f n) + - L) < r}"
   156       {n. norm (X (f n) + - L) < r}"
   157 by auto
   157 by auto
   158 
   158 
   159 lemma lemmaLIM2:
   159 lemma lemmaLIM2:
   160   "{n. norm (X (f n) + - L) < r} Int {n. r \<le> norm (X (f n) + - L)} = {}"
   160   "{n. norm (X (f n) - L) < r} Int {n. r \<le> norm (X (f n) - L)} = {}"
   161 by auto
   161 by auto
   162 
   162 
   163 lemma lemmaLIM3: "[| 0 < r; \<forall>n. r \<le> norm (X (f n) + - L);
   163 lemma lemmaLIM3: "[| 0 < r; \<forall>n. r \<le> norm (X (f n) - L);
   164            ( *f* X) (star_n f) +
   164            ( *f* X) (star_n f)
   165            - star_of L \<approx> 0 |] ==> False"
   165            - star_of L \<approx> 0 |] ==> False"
   166 apply (auto simp add: starfun mem_infmal_iff [symmetric] star_of_def star_n_minus star_n_add Infinitesimal_FreeUltrafilterNat_iff)
   166 apply (auto simp add: starfun mem_infmal_iff [symmetric] star_of_def star_n_diff Infinitesimal_FreeUltrafilterNat_iff)
   167 apply (drule_tac x = r in spec, safe)
   167 apply (drule_tac x = r in spec, safe)
   168 apply (drule FreeUltrafilterNat_all)
   168 apply (drule FreeUltrafilterNat_all)
   169 apply (drule FreeUltrafilterNat_Int, assumption)
   169 apply (drule FreeUltrafilterNat_Int, assumption)
   170 apply (simp add: lemmaLIM2)
   170 apply (simp add: lemmaLIM2)
   171 done
   171 done
   772 apply (auto simp add: HNatInfinite_FreeUltrafilterNat_iff)
   772 apply (auto simp add: HNatInfinite_FreeUltrafilterNat_iff)
   773 apply (drule_tac x = M in spec, ultra)
   773 apply (drule_tac x = M in spec, ultra)
   774 done
   774 done
   775 
   775 
   776 lemma lemmaCauchy2:
   776 lemma lemmaCauchy2:
   777      "{n. \<forall>m n. M \<le> m & M \<le> (n::nat) --> norm (X m + - X n) < u} Int
   777      "{n. \<forall>m n. M \<le> m & M \<le> (n::nat) --> norm (X m - X n) < u} Int
   778       {n. M \<le> xa n} Int {n. M \<le> x n} \<le>
   778       {n. M \<le> xa n} Int {n. M \<le> x n} \<le>
   779       {n. norm (X (xa n) + - X (x n)) < u}"
   779       {n. norm (X (xa n) - X (x n)) < u}"
   780 by blast
   780 by blast
   781 
   781 
   782 lemma Cauchy_NSCauchy: "Cauchy X ==> NSCauchy X"
   782 lemma Cauchy_NSCauchy: "Cauchy X ==> NSCauchy X"
   783 apply (simp add: Cauchy_def NSCauchy_def, safe)
   783 apply (simp add: Cauchy_def NSCauchy_def, safe)
   784 apply (rule_tac x = M in star_cases)
   784 apply (rule_tac x = M in star_cases)
   785 apply (rule_tac x = N in star_cases)
   785 apply (rule_tac x = N in star_cases)
   786 apply (rule approx_minus_iff [THEN iffD2])
   786 apply (rule approx_minus_iff [THEN iffD2])
   787 apply (rule mem_infmal_iff [THEN iffD1])
   787 apply (rule mem_infmal_iff [THEN iffD1])
   788 apply (auto simp add: starfun star_n_minus star_n_add Infinitesimal_FreeUltrafilterNat_iff)
   788 apply (auto simp add: starfun star_n_diff Infinitesimal_FreeUltrafilterNat_iff)
   789 apply (drule spec, auto)
   789 apply (drule spec, auto)
   790 apply (drule_tac M = M in lemmaCauchy1)
   790 apply (drule_tac M = M in lemmaCauchy1)
   791 apply (drule_tac M = M in lemmaCauchy1)
   791 apply (drule_tac M = M in lemmaCauchy1)
   792 apply (rule_tac x1 = Xaa in lemmaCauchy2 [THEN [2] FreeUltrafilterNat_subset])
   792 apply (rule_tac x1 = Xaa in lemmaCauchy2 [THEN [2] FreeUltrafilterNat_subset])
   793 apply (rule FreeUltrafilterNat_Int)
   793 apply (rule FreeUltrafilterNat_Int)
   804 apply (drule bspec, assumption)
   804 apply (drule bspec, assumption)
   805 apply (drule_tac x = "star_n fa" in bspec); 
   805 apply (drule_tac x = "star_n fa" in bspec); 
   806 apply (auto simp add: starfun)
   806 apply (auto simp add: starfun)
   807 apply (drule approx_minus_iff [THEN iffD1])
   807 apply (drule approx_minus_iff [THEN iffD1])
   808 apply (drule mem_infmal_iff [THEN iffD2])
   808 apply (drule mem_infmal_iff [THEN iffD2])
   809 apply (auto simp add: star_n_minus star_n_add Infinitesimal_FreeUltrafilterNat_iff)
   809 apply (auto simp add: star_n_diff Infinitesimal_FreeUltrafilterNat_iff)
   810 done
   810 done
   811 
   811 
   812 
   812 
   813 theorem NSCauchy_Cauchy_iff: "NSCauchy X = Cauchy X"
   813 theorem NSCauchy_Cauchy_iff: "NSCauchy X = Cauchy X"
   814 by (blast intro!: NSCauchy_Cauchy Cauchy_NSCauchy)
   814 by (blast intro!: NSCauchy_Cauchy Cauchy_NSCauchy)
   815 
   815 
   816 text{*A Cauchy sequence is bounded -- this is the standard
   816 text{*A Cauchy sequence is bounded -- this is the standard
   817   proof mechanization rather than the nonstandard proof*}
   817   proof mechanization rather than the nonstandard proof*}
   818 
   818 
   819 lemma lemmaCauchy: "\<forall>n \<ge> M. norm (X M + - X n) < (1::real)
   819 lemma lemmaCauchy: "\<forall>n \<ge> M. norm (X M - X n) < (1::real)
   820           ==>  \<forall>n \<ge> M. norm (X n :: 'a::real_normed_vector) < 1 + norm (X M)"
   820           ==>  \<forall>n \<ge> M. norm (X n :: 'a::real_normed_vector) < 1 + norm (X M)"
   821 apply (clarify, drule spec, drule (1) mp)
   821 apply (clarify, drule spec, drule (1) mp)
   822 apply (fold diff_def, simp only: norm_minus_commute)
   822 apply (simp only: norm_minus_commute)
   823 apply (drule order_le_less_trans [OF norm_triangle_ineq2])
   823 apply (drule order_le_less_trans [OF norm_triangle_ineq2])
   824 apply simp
   824 apply simp
   825 done
   825 done
   826 
   826 
   827 lemma less_Suc_cancel_iff: "(n < Suc M) = (n \<le> M)"
   827 lemma less_Suc_cancel_iff: "(n < Suc M) = (n \<le> M)"