src/HOL/Hyperreal/SEQ.ML
changeset 10919 144ede948e58
parent 10834 a7897aebbffc
child 11701 3d51fbf81c17
equal deleted inserted replaced
10918:9679326489cd 10919:144ede948e58
     9    whose term with an hypernatural suffix is an infinitesimal i.e. 
     9    whose term with an hypernatural suffix is an infinitesimal i.e. 
    10    the whn'nth term of the hypersequence is a member of Infinitesimal 
    10    the whn'nth term of the hypersequence is a member of Infinitesimal 
    11  -------------------------------------------------------------------------- *)
    11  -------------------------------------------------------------------------- *)
    12 
    12 
    13 Goalw [hypnat_omega_def] 
    13 Goalw [hypnat_omega_def] 
    14       "(*fNat* (%n::nat. inverse(real_of_nat(Suc n)))) whn : Infinitesimal";
    14       "(*fNat* (%n::nat. inverse(real(Suc n)))) whn : Infinitesimal";
    15 by (auto_tac (claset(),
    15 by (auto_tac (claset(),
    16       simpset() addsimps [Infinitesimal_FreeUltrafilterNat_iff,starfunNat]));
    16       simpset() addsimps [Infinitesimal_FreeUltrafilterNat_iff,starfunNat]));
    17 by (rtac bexI 1 THEN rtac lemma_hyprel_refl 2);
    17 by (rtac bexI 1 THEN rtac lemma_hyprel_refl 2);
    18 by (auto_tac (claset(),
    18 by (auto_tac (claset(),
    19               simpset() addsimps [real_of_nat_Suc_gt_zero, abs_eqI2,
    19               simpset() addsimps [real_of_nat_Suc_gt_zero, abs_eqI2,
    22 
    22 
    23 (*--------------------------------------------------------------------------
    23 (*--------------------------------------------------------------------------
    24                   Rules for LIMSEQ and NSLIMSEQ etc.
    24                   Rules for LIMSEQ and NSLIMSEQ etc.
    25  --------------------------------------------------------------------------*)
    25  --------------------------------------------------------------------------*)
    26 
    26 
    27 (*** LIMSEQ ***)
       
    28 Goalw [LIMSEQ_def] 
       
    29       "X ----> L ==> \
       
    30 \      ALL r. #0 < r --> (EX no. ALL n. no <= n --> abs(X n + -L) < r)";
       
    31 by (Asm_simp_tac 1);
       
    32 qed "LIMSEQD1";
       
    33 
       
    34 Goalw [LIMSEQ_def] 
       
    35       "[| X ----> L; #0 < r|] ==> \
       
    36 \      EX no. ALL n. no <= n --> abs(X n + -L) < r";
       
    37 by (Asm_simp_tac 1);
       
    38 qed "LIMSEQD2";
       
    39 
       
    40 Goalw [LIMSEQ_def] 
       
    41       "ALL r. #0 < r --> (EX no. ALL n. \
       
    42 \      no <= n --> abs(X n + -L) < r) ==> X ----> L";
       
    43 by (Asm_simp_tac 1);
       
    44 qed "LIMSEQI";
       
    45 
       
    46 Goalw [LIMSEQ_def] 
    27 Goalw [LIMSEQ_def] 
    47       "(X ----> L) = \
    28       "(X ----> L) = \
    48 \      (ALL r. #0 <r --> (EX no. ALL n. no <= n --> abs(X n + -L) < r))";
    29 \      (ALL r. #0 <r --> (EX no. ALL n. no <= n --> abs(X n + -L) < r))";
    49 by (Simp_tac 1);
    30 by (Simp_tac 1);
    50 qed "LIMSEQ_iff";
    31 qed "LIMSEQ_iff";
    51 
       
    52 (*** NSLIMSEQ ***)
       
    53 Goalw [NSLIMSEQ_def] 
       
    54      "X ----NS> L ==> ALL N: HNatInfinite. (*fNat* X) N @= hypreal_of_real L";
       
    55 by (Asm_simp_tac 1);
       
    56 qed "NSLIMSEQD1";
       
    57 
       
    58 Goalw [NSLIMSEQ_def] 
       
    59     "[| X ----NS> L; N: HNatInfinite |] ==> (*fNat* X) N @= hypreal_of_real L";
       
    60 by (Asm_simp_tac 1);
       
    61 qed "NSLIMSEQD2";
       
    62 
       
    63 Goalw [NSLIMSEQ_def] 
       
    64      "ALL N: HNatInfinite. (*fNat* X) N @= hypreal_of_real L ==> X ----NS> L";
       
    65 by (Asm_simp_tac 1);
       
    66 qed "NSLIMSEQI";
       
    67 
    32 
    68 Goalw [NSLIMSEQ_def] 
    33 Goalw [NSLIMSEQ_def] 
    69     "(X ----NS> L) = (ALL N: HNatInfinite. (*fNat* X) N @= hypreal_of_real L)";
    34     "(X ----NS> L) = (ALL N: HNatInfinite. (*fNat* X) N @= hypreal_of_real L)";
    70 by (Simp_tac 1);
    35 by (Simp_tac 1);
    71 qed "NSLIMSEQ_iff";
    36 qed "NSLIMSEQ_iff";
    76 Goalw [LIMSEQ_def,NSLIMSEQ_def] 
    41 Goalw [LIMSEQ_def,NSLIMSEQ_def] 
    77       "X ----> L ==> X ----NS> L";
    42       "X ----> L ==> X ----NS> L";
    78 by (auto_tac (claset(),simpset() addsimps 
    43 by (auto_tac (claset(),simpset() addsimps 
    79     [HNatInfinite_FreeUltrafilterNat_iff]));
    44     [HNatInfinite_FreeUltrafilterNat_iff]));
    80 by (res_inst_tac [("z","N")] eq_Abs_hypnat 1);
    45 by (res_inst_tac [("z","N")] eq_Abs_hypnat 1);
    81 by (rtac (inf_close_minus_iff RS iffD2) 1);
    46 by (rtac (approx_minus_iff RS iffD2) 1);
    82 by (auto_tac (claset(),simpset() addsimps [starfunNat,
    47 by (auto_tac (claset(),simpset() addsimps [starfunNat,
    83     mem_infmal_iff RS sym,hypreal_of_real_def,
    48     mem_infmal_iff RS sym,hypreal_of_real_def,
    84     hypreal_minus,hypreal_add,
    49     hypreal_minus,hypreal_add,
    85     Infinitesimal_FreeUltrafilterNat_iff]));
    50     Infinitesimal_FreeUltrafilterNat_iff]));
    86 by (EVERY[rtac bexI 1, rtac lemma_hyprel_refl 2, Step_tac 1]);
    51 by (EVERY[rtac bexI 1, rtac lemma_hyprel_refl 2, Step_tac 1]);
   177 by (rtac ccontr 1 THEN Asm_full_simp_tac 1);
   142 by (rtac ccontr 1 THEN Asm_full_simp_tac 1);
   178 by (Step_tac 1);
   143 by (Step_tac 1);
   179 (* skolemization step *)
   144 (* skolemization step *)
   180 by (dtac choice 1 THEN Step_tac 1);
   145 by (dtac choice 1 THEN Step_tac 1);
   181 by (dres_inst_tac [("x","Abs_hypnat(hypnatrel``{f})")] bspec 1);
   146 by (dres_inst_tac [("x","Abs_hypnat(hypnatrel``{f})")] bspec 1);
   182 by (dtac (inf_close_minus_iff RS iffD1) 2);
   147 by (dtac (approx_minus_iff RS iffD1) 2);
   183 by (fold_tac [real_le_def]);
   148 by (fold_tac [real_le_def]);
   184 by (blast_tac (claset() addIs [HNatInfinite_NSLIMSEQ]) 1);
   149 by (blast_tac (claset() addIs [HNatInfinite_NSLIMSEQ]) 1);
   185 by (blast_tac (claset() addIs [rename_numerals lemmaLIM3]) 1);
   150 by (blast_tac (claset() addIs [rename_numerals lemmaLIM3]) 1);
   186 qed "NSLIMSEQ_LIMSEQ";
   151 qed "NSLIMSEQ_LIMSEQ";
   187 
   152 
   201 by (Auto_tac);
   166 by (Auto_tac);
   202 qed "LIMSEQ_const";
   167 qed "LIMSEQ_const";
   203 
   168 
   204 Goalw [NSLIMSEQ_def]
   169 Goalw [NSLIMSEQ_def]
   205       "[| X ----NS> a; Y ----NS> b |] ==> (%n. X n + Y n) ----NS> a + b";
   170       "[| X ----NS> a; Y ----NS> b |] ==> (%n. X n + Y n) ----NS> a + b";
   206 by (auto_tac (claset() addIs [inf_close_add],
   171 by (auto_tac (claset() addIs [approx_add],
   207     simpset() addsimps [starfunNat_add RS sym]));
   172     simpset() addsimps [starfunNat_add RS sym]));
   208 qed "NSLIMSEQ_add";
   173 qed "NSLIMSEQ_add";
   209 
   174 
   210 Goal "[| X ----> a; Y ----> b |] ==> (%n. X n + Y n) ----> a + b";
   175 Goal "[| X ----> a; Y ----> b |] ==> (%n. X n + Y n) ----> a + b";
   211 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff,
   176 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff,
   212                                            NSLIMSEQ_add]) 1);
   177                                            NSLIMSEQ_add]) 1);
   213 qed "LIMSEQ_add";
   178 qed "LIMSEQ_add";
   214 
   179 
   215 Goalw [NSLIMSEQ_def]
   180 Goalw [NSLIMSEQ_def]
   216       "[| X ----NS> a; Y ----NS> b |] ==> (%n. X n * Y n) ----NS> a * b";
   181       "[| X ----NS> a; Y ----NS> b |] ==> (%n. X n * Y n) ----NS> a * b";
   217 by (auto_tac (claset() addSIs [inf_close_mult_HFinite],
   182 by (auto_tac (claset() addSIs [approx_mult_HFinite],
   218     simpset() addsimps [hypreal_of_real_mult, starfunNat_mult RS sym]));
   183     simpset() addsimps [hypreal_of_real_mult, starfunNat_mult RS sym]));
   219 qed "NSLIMSEQ_mult";
   184 qed "NSLIMSEQ_mult";
   220 
   185 
   221 Goal "[| X ----> a; Y ----> b |] ==> (%n. X n * Y n) ----> a * b";
   186 Goal "[| X ----> a; Y ----> b |] ==> (%n. X n * Y n) ----> a * b";
   222 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff,
   187 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff,
   272      "[| X ----NS> a;  a ~= #0 |] ==> (%n. inverse(X n)) ----NS> inverse(a)";
   237      "[| X ----NS> a;  a ~= #0 |] ==> (%n. inverse(X n)) ----NS> inverse(a)";
   273 by (Clarify_tac 1);
   238 by (Clarify_tac 1);
   274 by (dtac bspec 1);
   239 by (dtac bspec 1);
   275 by (auto_tac (claset(), 
   240 by (auto_tac (claset(), 
   276               simpset() addsimps [starfunNat_inverse RS sym, 
   241               simpset() addsimps [starfunNat_inverse RS sym, 
   277                                   hypreal_of_real_inf_close_inverse]));  
   242                                   hypreal_of_real_approx_inverse]));  
   278 qed "NSLIMSEQ_inverse";
   243 qed "NSLIMSEQ_inverse";
   279 
   244 
   280 
   245 
   281 (*------ Standard version of theorem -------*)
   246 (*------ Standard version of theorem -------*)
   282 Goal "[| X ----> a; a ~= #0 |] ==> (%n. inverse(X n)) ----> inverse(a)";
   247 Goal "[| X ----> a; a ~= #0 |] ==> (%n. inverse(X n)) ----> inverse(a)";
   299             Uniqueness of limit
   264             Uniqueness of limit
   300  ----------------------------------------------*)
   265  ----------------------------------------------*)
   301 Goalw [NSLIMSEQ_def] 
   266 Goalw [NSLIMSEQ_def] 
   302      "[| X ----NS> a; X ----NS> b |] ==> a = b";
   267      "[| X ----NS> a; X ----NS> b |] ==> a = b";
   303 by (REPEAT(dtac (HNatInfinite_whn RSN (2,bspec)) 1));
   268 by (REPEAT(dtac (HNatInfinite_whn RSN (2,bspec)) 1));
   304 by (auto_tac (claset() addDs [inf_close_trans3], simpset()));
   269 by (auto_tac (claset() addDs [approx_trans3], simpset()));
   305 qed "NSLIMSEQ_unique";
   270 qed "NSLIMSEQ_unique";
   306 
   271 
   307 Goal "[| X ----> a; X ----> b |] ==> a = b";
   272 Goal "[| X ----> a; X ----> b |] ==> a = b";
   308 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff,
   273 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff,
   309     NSLIMSEQ_unique]) 1);
   274     NSLIMSEQ_unique]) 1);
   365 (*-------------------------------------------------------------------
   330 (*-------------------------------------------------------------------
   366          Subsequence (alternative definition) (e.g. Hoskins)
   331          Subsequence (alternative definition) (e.g. Hoskins)
   367  ------------------------------------------------------------------*)
   332  ------------------------------------------------------------------*)
   368 Goalw [subseq_def] "subseq f = (ALL n. (f n) < (f (Suc n)))";
   333 Goalw [subseq_def] "subseq f = (ALL n. (f n) < (f (Suc n)))";
   369 by (auto_tac (claset() addSDs [less_imp_Suc_add], simpset()));
   334 by (auto_tac (claset() addSDs [less_imp_Suc_add], simpset()));
   370 by (nat_ind_tac "k" 1);
   335 by (induct_tac "k" 1);
   371 by (auto_tac (claset() addIs [less_trans], simpset()));
   336 by (auto_tac (claset() addIs [less_trans], simpset()));
   372 qed "subseq_Suc_iff";
   337 qed "subseq_Suc_iff";
   373 
   338 
   374 (*-------------------------------------------------------------------
   339 (*-------------------------------------------------------------------
   375                    Monotonicity
   340                    Monotonicity
   419       "[| #0 < K; ALL n. abs(X n) <= K |] ==> Bseq X";
   384       "[| #0 < K; ALL n. abs(X n) <= K |] ==> Bseq X";
   420 by (Blast_tac 1);
   385 by (Blast_tac 1);
   421 qed "BseqI";
   386 qed "BseqI";
   422 
   387 
   423 Goal "(EX K. #0 < K & (ALL n. abs(X n) <= K)) = \
   388 Goal "(EX K. #0 < K & (ALL n. abs(X n) <= K)) = \
   424 \     (EX N. ALL n. abs(X n) <= real_of_nat(Suc N))";
   389 \     (EX N. ALL n. abs(X n) <= real(Suc N))";
   425 by Auto_tac;
   390 by Auto_tac;
   426 by (cut_inst_tac [("x","K")] reals_Archimedean2 1);
   391 by (cut_inst_tac [("x","K")] reals_Archimedean2 1);
   427 by (Clarify_tac 1); 
   392 by (Clarify_tac 1); 
   428 by (res_inst_tac [("x","n")] exI 1); 
   393 by (res_inst_tac [("x","n")] exI 1); 
   429 by (Clarify_tac 1); 
   394 by (Clarify_tac 1); 
   430 by (dres_inst_tac [("x","na")] spec 1); 
   395 by (dres_inst_tac [("x","na")] spec 1); 
   431 by (auto_tac (claset(), simpset() addsimps [real_of_nat_Suc]));  
   396 by (auto_tac (claset(), simpset() addsimps [real_of_nat_Suc]));  
   432 qed "lemma_NBseq_def";
   397 qed "lemma_NBseq_def";
   433 
   398 
   434 (* alternative definition for Bseq *)
   399 (* alternative definition for Bseq *)
   435 Goalw [Bseq_def] "Bseq X = (EX N. ALL n. abs(X n) <= real_of_nat(Suc N))";
   400 Goalw [Bseq_def] "Bseq X = (EX N. ALL n. abs(X n) <= real(Suc N))";
   436 by (simp_tac (simpset() addsimps [lemma_NBseq_def]) 1);
   401 by (simp_tac (simpset() addsimps [lemma_NBseq_def]) 1);
   437 qed "Bseq_iff";
   402 qed "Bseq_iff";
   438 
   403 
   439 Goal "(EX K. #0 < K & (ALL n. abs(X n) <= K)) = \
   404 Goal "(EX K. #0 < K & (ALL n. abs(X n) <= K)) = \
   440 \     (EX N. ALL n. abs(X n) < real_of_nat(Suc N))";
   405 \     (EX N. ALL n. abs(X n) < real(Suc N))";
   441 by (stac lemma_NBseq_def 1); 
   406 by (stac lemma_NBseq_def 1); 
   442 by Auto_tac;
   407 by Auto_tac;
   443 by (res_inst_tac [("x","Suc N")] exI 1); 
   408 by (res_inst_tac [("x","Suc N")] exI 1); 
   444 by (res_inst_tac [("x","N")] exI 2); 
   409 by (res_inst_tac [("x","N")] exI 2); 
   445 by (auto_tac (claset(), simpset() addsimps [real_of_nat_Suc]));  
   410 by (auto_tac (claset(), simpset() addsimps [real_of_nat_Suc]));  
   447 by (dres_inst_tac [("x","n")] spec 1); 
   412 by (dres_inst_tac [("x","n")] spec 1); 
   448 by (Asm_simp_tac 1); 
   413 by (Asm_simp_tac 1); 
   449 qed "lemma_NBseq_def2";
   414 qed "lemma_NBseq_def2";
   450 
   415 
   451 (* yet another definition for Bseq *)
   416 (* yet another definition for Bseq *)
   452 Goalw [Bseq_def] "Bseq X = (EX N. ALL n. abs(X n) < real_of_nat(Suc N))";
   417 Goalw [Bseq_def] "Bseq X = (EX N. ALL n. abs(X n) < real(Suc N))";
   453 by (simp_tac (simpset() addsimps [lemma_NBseq_def2]) 1);
   418 by (simp_tac (simpset() addsimps [lemma_NBseq_def2]) 1);
   454 qed "Bseq_iff1a";
   419 qed "Bseq_iff1a";
   455 
   420 
   456 Goalw [NSBseq_def]
   421 Goalw [NSBseq_def]
   457      "[| NSBseq X;  N: HNatInfinite |] ==> (*fNat* X) N : HFinite";
   422      "[| NSBseq X;  N: HNatInfinite |] ==> (*fNat* X) N : HFinite";
   495    o/w we would be stuck with a skolem function f :: real=>nat which
   460    o/w we would be stuck with a skolem function f :: real=>nat which
   496    is not what we want (read useless!)
   461    is not what we want (read useless!)
   497  -------------------------------------------------------------------*)
   462  -------------------------------------------------------------------*)
   498  
   463  
   499 Goal "ALL K. #0 < K --> (EX n. K < abs (X n)) \
   464 Goal "ALL K. #0 < K --> (EX n. K < abs (X n)) \
   500 \          ==> ALL N. EX n. real_of_nat(Suc N) < abs (X n)";
   465 \          ==> ALL N. EX n. real(Suc N) < abs (X n)";
   501 by (Step_tac 1);
   466 by (Step_tac 1);
   502 by (cut_inst_tac [("n","N")] real_of_nat_Suc_gt_zero 1);
   467 by (cut_inst_tac [("n","N")] real_of_nat_Suc_gt_zero 1);
   503 by (Blast_tac 1);
   468 by (Blast_tac 1);
   504 val lemmaNSBseq = result();
   469 val lemmaNSBseq = result();
   505 
   470 
   506 Goal "ALL K. #0 < K --> (EX n. K < abs (X n)) \
   471 Goal "ALL K. #0 < K --> (EX n. K < abs (X n)) \
   507 \         ==> EX f. ALL N. real_of_nat(Suc N) < abs (X (f N))";
   472 \         ==> EX f. ALL N. real(Suc N) < abs (X (f N))";
   508 by (dtac lemmaNSBseq 1);
   473 by (dtac lemmaNSBseq 1);
   509 by (dtac choice 1);
   474 by (dtac choice 1);
   510 by (Blast_tac 1);
   475 by (Blast_tac 1);
   511 val lemmaNSBseq2 = result();
   476 val lemmaNSBseq2 = result();
   512 
   477 
   513 Goal "ALL N. real_of_nat(Suc N) < abs (X (f N)) \
   478 Goal "ALL N. real(Suc N) < abs (X (f N)) \
   514 \         ==>  Abs_hypreal(hyprel``{X o f}) : HInfinite";
   479 \         ==>  Abs_hypreal(hyprel``{X o f}) : HInfinite";
   515 by (auto_tac (claset(),
   480 by (auto_tac (claset(),
   516               simpset() addsimps [HInfinite_FreeUltrafilterNat_iff,o_def]));
   481               simpset() addsimps [HInfinite_FreeUltrafilterNat_iff,o_def]));
   517 by (EVERY[rtac bexI 1, rtac lemma_hyprel_refl 2, Step_tac 1]);
   482 by (EVERY[rtac bexI 1, rtac lemma_hyprel_refl 2, Step_tac 1]);
   518 by (cut_inst_tac [("u","u")] FreeUltrafilterNat_nat_gt_real 1);
   483 by (cut_inst_tac [("u","u")] FreeUltrafilterNat_nat_gt_real 1);
   524 (*-----------------------------------------------------------------------------
   489 (*-----------------------------------------------------------------------------
   525      Now prove that we can get out an infinite hypernatural as well 
   490      Now prove that we can get out an infinite hypernatural as well 
   526      defined using the skolem function f::nat=>nat above
   491      defined using the skolem function f::nat=>nat above
   527  ----------------------------------------------------------------------------*)
   492  ----------------------------------------------------------------------------*)
   528 
   493 
   529 Goal "{n. f n <= Suc u & real_of_nat(Suc n) < abs (X (f n))} <= \
   494 Goal "{n. f n <= Suc u & real(Suc n) < abs (X (f n))} <= \
   530 \         {n. f n <= u & real_of_nat(Suc n) < abs (X (f n))} \
   495 \         {n. f n <= u & real(Suc n) < abs (X (f n))} \
   531 \         Un {n. real_of_nat(Suc n) < abs (X (Suc u))}";
   496 \         Un {n. real(Suc n) < abs (X (Suc u))}";
   532 by (auto_tac (claset() addSDs [le_imp_less_or_eq], simpset()));
   497 by (auto_tac (claset() addSDs [le_imp_less_or_eq], simpset()));
   533 val lemma_finite_NSBseq = result();
   498 val lemma_finite_NSBseq = result();
   534 
   499 
   535 Goal "finite {n. f n <= (u::nat) &  real_of_nat(Suc n) < abs(X(f n))}";
   500 Goal "finite {n. f n <= (u::nat) &  real(Suc n) < abs(X(f n))}";
   536 by (induct_tac "u" 1);
   501 by (induct_tac "u" 1);
   537 by (res_inst_tac [("B","{n. real_of_nat(Suc n) < abs(X 0)}")] finite_subset 1);
   502 by (res_inst_tac [("B","{n. real(Suc n) < abs(X 0)}")] finite_subset 1);
   538 by (Force_tac 1); 
   503 by (Force_tac 1); 
   539 by (rtac (lemma_finite_NSBseq RS finite_subset) 2);
   504 by (rtac (lemma_finite_NSBseq RS finite_subset) 2);
   540 by (auto_tac (claset() addIs [finite_real_of_nat_less_real], 
   505 by (auto_tac (claset() addIs [finite_real_of_nat_less_real], 
   541               simpset() addsimps [real_of_nat_Suc, real_less_diff_eq RS sym]));
   506               simpset() addsimps [real_of_nat_Suc, real_less_diff_eq RS sym]));
   542 val lemma_finite_NSBseq2 = result();
   507 val lemma_finite_NSBseq2 = result();
   543 
   508 
   544 Goal "ALL N. real_of_nat(Suc N) < abs (X (f N)) \
   509 Goal "ALL N. real(Suc N) < abs (X (f N)) \
   545 \     ==> Abs_hypnat(hypnatrel``{f}) : HNatInfinite";
   510 \     ==> Abs_hypnat(hypnatrel``{f}) : HNatInfinite";
   546 by (auto_tac (claset(),
   511 by (auto_tac (claset(),
   547               simpset() addsimps [HNatInfinite_FreeUltrafilterNat_iff]));
   512               simpset() addsimps [HNatInfinite_FreeUltrafilterNat_iff]));
   548 by (EVERY[rtac bexI 1, rtac lemma_hypnatrel_refl 2, Step_tac 1]);
   513 by (EVERY[rtac bexI 1, rtac lemma_hypnatrel_refl 2, Step_tac 1]);
   549 by (rtac ccontr 1 THEN dtac FreeUltrafilterNat_Compl_mem 1);
   514 by (rtac ccontr 1 THEN dtac FreeUltrafilterNat_Compl_mem 1);
   552 \   = {n. f n <= u}" [le_def]]) 1);
   517 \   = {n. f n <= u}" [le_def]]) 1);
   553 by (dtac FreeUltrafilterNat_all 1);
   518 by (dtac FreeUltrafilterNat_all 1);
   554 by (dtac FreeUltrafilterNat_Int 1 THEN assume_tac 1);
   519 by (dtac FreeUltrafilterNat_Int 1 THEN assume_tac 1);
   555 by (auto_tac (claset(), 
   520 by (auto_tac (claset(), 
   556      simpset() addsimps 
   521      simpset() addsimps 
   557     [CLAIM "({n. f n <= u} Int {n. real_of_nat(Suc n) < abs(X(f n))}) = \
   522     [CLAIM "({n. f n <= u} Int {n. real(Suc n) < abs(X(f n))}) = \
   558 \          {n. f n <= (u::nat) &  real_of_nat(Suc n) < abs(X(f n))}",
   523 \          {n. f n <= (u::nat) &  real(Suc n) < abs(X(f n))}",
   559      lemma_finite_NSBseq2 RS FreeUltrafilterNat_finite]));
   524      lemma_finite_NSBseq2 RS FreeUltrafilterNat_finite]));
   560 qed "HNatInfinite_skolem_f";
   525 qed "HNatInfinite_skolem_f";
   561 
   526 
   562 Goalw [Bseq_def,NSBseq_def] 
   527 Goalw [Bseq_def,NSBseq_def] 
   563       "NSBseq X ==> Bseq X";
   528       "NSBseq X ==> Bseq X";
   584  -----------------------------------------------------------------------*)
   549  -----------------------------------------------------------------------*)
   585 (* easier --- nonstandard version - no existential as usual *)
   550 (* easier --- nonstandard version - no existential as usual *)
   586 Goalw [NSconvergent_def,NSBseq_def,NSLIMSEQ_def] 
   551 Goalw [NSconvergent_def,NSBseq_def,NSLIMSEQ_def] 
   587           "NSconvergent X ==> NSBseq X";
   552           "NSconvergent X ==> NSBseq X";
   588 by (blast_tac (claset() addDs [HFinite_hypreal_of_real RS 
   553 by (blast_tac (claset() addDs [HFinite_hypreal_of_real RS 
   589                (inf_close_sym RSN (2,inf_close_HFinite))]) 1);
   554                (approx_sym RSN (2,approx_HFinite))]) 1);
   590 qed "NSconvergent_NSBseq";
   555 qed "NSconvergent_NSBseq";
   591 
   556 
   592 (* standard version - easily now proved using *)
   557 (* standard version - easily now proved using *)
   593 (* equivalence of NS and standard definitions *)
   558 (* equivalence of NS and standard definitions *)
   594 Goal "convergent X ==> Bseq X";
   559 Goal "convergent X ==> Bseq X";
   711 by (case_tac "EX m. X m = U" 1 THEN Auto_tac);
   676 by (case_tac "EX m. X m = U" 1 THEN Auto_tac);
   712 by (blast_tac (claset() addDs [lemma_converg1,
   677 by (blast_tac (claset() addDs [lemma_converg1,
   713     Bmonoseq_LIMSEQ]) 1);
   678     Bmonoseq_LIMSEQ]) 1);
   714 (* second case *)
   679 (* second case *)
   715 by (res_inst_tac [("x","U")] exI 1);
   680 by (res_inst_tac [("x","U")] exI 1);
   716 by (rtac LIMSEQI 1 THEN Step_tac 1);
   681 by (stac LIMSEQ_iff 1 THEN Step_tac 1);
   717 by (forward_tac [lemma_converg2] 1 THEN assume_tac 1);
   682 by (forward_tac [lemma_converg2] 1 THEN assume_tac 1);
   718 by (dtac lemma_converg4 1 THEN Auto_tac);
   683 by (dtac lemma_converg4 1 THEN Auto_tac);
   719 by (res_inst_tac [("x","m")] exI 1 THEN Step_tac 1);
   684 by (res_inst_tac [("x","m")] exI 1 THEN Step_tac 1);
   720 by (subgoal_tac "X m <= X n" 1 THEN Fast_tac 2);
   685 by (subgoal_tac "X m <= X n" 1 THEN Fast_tac 2);
   721 by (rotate_tac 3 1 THEN dres_inst_tac [("x","n")] spec 1);
   686 by (rotate_tac 3 1 THEN dres_inst_tac [("x","n")] spec 1);
   812 Goalw [Cauchy_def,NSCauchy_def] 
   777 Goalw [Cauchy_def,NSCauchy_def] 
   813       "Cauchy X ==> NSCauchy X";
   778       "Cauchy X ==> NSCauchy X";
   814 by (Step_tac 1);
   779 by (Step_tac 1);
   815 by (res_inst_tac [("z","M")] eq_Abs_hypnat 1);
   780 by (res_inst_tac [("z","M")] eq_Abs_hypnat 1);
   816 by (res_inst_tac [("z","N")] eq_Abs_hypnat 1);
   781 by (res_inst_tac [("z","N")] eq_Abs_hypnat 1);
   817 by (rtac (inf_close_minus_iff RS iffD2) 1);
   782 by (rtac (approx_minus_iff RS iffD2) 1);
   818 by (rtac (mem_infmal_iff RS iffD1) 1);
   783 by (rtac (mem_infmal_iff RS iffD1) 1);
   819 by (auto_tac (claset(),
   784 by (auto_tac (claset(),
   820               simpset() addsimps [starfunNat, hypreal_minus,hypreal_add,
   785               simpset() addsimps [starfunNat, hypreal_minus,hypreal_add,
   821                                   Infinitesimal_FreeUltrafilterNat_iff]));
   786                                   Infinitesimal_FreeUltrafilterNat_iff]));
   822 by (EVERY[rtac bexI 1, Auto_tac]);
   787 by (EVERY[rtac bexI 1, Auto_tac]);
   843     step_tac (claset() addSDs [all_conj_distrib RS iffD1]) 1);
   808     step_tac (claset() addSDs [all_conj_distrib RS iffD1]) 1);
   844 by (REPEAT(dtac HNatInfinite_NSLIMSEQ 1));
   809 by (REPEAT(dtac HNatInfinite_NSLIMSEQ 1));
   845 by (dtac bspec 1 THEN assume_tac 1);
   810 by (dtac bspec 1 THEN assume_tac 1);
   846 by (dres_inst_tac [("x","Abs_hypnat (hypnatrel `` {fa})")] bspec 1 
   811 by (dres_inst_tac [("x","Abs_hypnat (hypnatrel `` {fa})")] bspec 1 
   847     THEN auto_tac (claset(), simpset() addsimps [starfunNat]));
   812     THEN auto_tac (claset(), simpset() addsimps [starfunNat]));
   848 by (dtac (inf_close_minus_iff RS iffD1) 1);
   813 by (dtac (approx_minus_iff RS iffD1) 1);
   849 by (dtac (mem_infmal_iff RS iffD2) 1);
   814 by (dtac (mem_infmal_iff RS iffD2) 1);
   850 by (auto_tac (claset(), simpset() addsimps [hypreal_minus,
   815 by (auto_tac (claset(), simpset() addsimps [hypreal_minus,
   851     hypreal_add,Infinitesimal_FreeUltrafilterNat_iff]));
   816     hypreal_add,Infinitesimal_FreeUltrafilterNat_iff]));
   852 by (dres_inst_tac [("x","e")] spec 1 THEN Auto_tac);
   817 by (dres_inst_tac [("x","e")] spec 1 THEN Auto_tac);
   853 by (dtac FreeUltrafilterNat_Int 1 THEN assume_tac 1);
   818 by (dtac FreeUltrafilterNat_Int 1 THEN assume_tac 1);
   994  -----------------------------------------------------------------*)
   959  -----------------------------------------------------------------*)
   995 Goalw [NSconvergent_def,NSLIMSEQ_def]
   960 Goalw [NSconvergent_def,NSLIMSEQ_def]
   996       "NSCauchy X = NSconvergent X";
   961       "NSCauchy X = NSconvergent X";
   997 by (Step_tac 1);
   962 by (Step_tac 1);
   998 by (forward_tac [NSCauchy_NSBseq] 1);
   963 by (forward_tac [NSCauchy_NSBseq] 1);
   999 by (auto_tac (claset() addIs [inf_close_trans2], 
   964 by (auto_tac (claset() addIs [approx_trans2], 
  1000     simpset() addsimps 
   965     simpset() addsimps 
  1001     [NSBseq_def,NSCauchy_def]));
   966     [NSBseq_def,NSCauchy_def]));
  1002 by (dtac (HNatInfinite_whn RSN (2,bspec)) 1);
   967 by (dtac (HNatInfinite_whn RSN (2,bspec)) 1);
  1003 by (dtac (HNatInfinite_whn RSN (2,bspec)) 1);
   968 by (dtac (HNatInfinite_whn RSN (2,bspec)) 1);
  1004 by (auto_tac (claset() addSDs [st_part_Ex], simpset() 
   969 by (auto_tac (claset() addSDs [st_part_Ex], simpset() 
  1005               addsimps [SReal_iff]));
   970               addsimps [SReal_iff]));
  1006 by (blast_tac (claset() addIs [inf_close_trans3]) 1);
   971 by (blast_tac (claset() addIs [approx_trans3]) 1);
  1007 qed "NSCauchy_NSconvergent_iff";
   972 qed "NSCauchy_NSconvergent_iff";
  1008 
   973 
  1009 (* Standard proof for free *)
   974 (* Standard proof for free *)
  1010 Goal "Cauchy X = convergent X";
   975 Goal "Cauchy X = convergent X";
  1011 by (simp_tac (simpset() addsimps [NSCauchy_Cauchy_iff RS sym,
   976 by (simp_tac (simpset() addsimps [NSCauchy_Cauchy_iff RS sym,
  1075 by (auto_tac (claset(), 
  1040 by (auto_tac (claset(), 
  1076      simpset() addsimps [NSCauchy_def, NSLIMSEQ_def,starfunNat_shift_one]));
  1041      simpset() addsimps [NSCauchy_def, NSLIMSEQ_def,starfunNat_shift_one]));
  1077 by (dtac bspec 1 THEN assume_tac 1);
  1042 by (dtac bspec 1 THEN assume_tac 1);
  1078 by (dtac bspec 1 THEN assume_tac 1);
  1043 by (dtac bspec 1 THEN assume_tac 1);
  1079 by (dtac (SHNat_one RSN (2,HNatInfinite_SHNat_add)) 1);
  1044 by (dtac (SHNat_one RSN (2,HNatInfinite_SHNat_add)) 1);
  1080 by (blast_tac (claset() addIs [inf_close_trans3]) 1);
  1045 by (blast_tac (claset() addIs [approx_trans3]) 1);
  1081 qed "NSLIMSEQ_Suc";
  1046 qed "NSLIMSEQ_Suc";
  1082 
  1047 
  1083 (* standard version *)
  1048 (* standard version *)
  1084 Goal "f ----> l ==> (%n. f(Suc n)) ----> l";
  1049 Goal "f ----> l ==> (%n. f(Suc n)) ----> l";
  1085 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff,
  1050 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff,
  1093       simpset() addsimps [NSCauchy_def, NSLIMSEQ_def,starfunNat_shift_one]));
  1058       simpset() addsimps [NSCauchy_def, NSLIMSEQ_def,starfunNat_shift_one]));
  1094 by (dtac bspec 1 THEN assume_tac 1);
  1059 by (dtac bspec 1 THEN assume_tac 1);
  1095 by (dtac bspec 1 THEN assume_tac 1);
  1060 by (dtac bspec 1 THEN assume_tac 1);
  1096 by (ftac (SHNat_one RSN (2,HNatInfinite_SHNat_diff)) 1);
  1061 by (ftac (SHNat_one RSN (2,HNatInfinite_SHNat_diff)) 1);
  1097 by (rotate_tac 2 1);
  1062 by (rotate_tac 2 1);
  1098 by (auto_tac (claset() addSDs [bspec] addIs [inf_close_trans3],
  1063 by (auto_tac (claset() addSDs [bspec] addIs [approx_trans3],
  1099     simpset()));
  1064     simpset()));
  1100 qed "NSLIMSEQ_imp_Suc";
  1065 qed "NSLIMSEQ_imp_Suc";
  1101 
  1066 
  1102 Goal "(%n. f(Suc n)) ----> l ==> f ----> l";
  1067 Goal "(%n. f(Suc n)) ----> l ==> f ----> l";
  1103 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff]) 1);
  1068 by (asm_full_simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff]) 1);
  1136     Also we have for a general limit 
  1101     Also we have for a general limit 
  1137         (NS proof much easier)
  1102         (NS proof much easier)
  1138  ---------------------------------------*)
  1103  ---------------------------------------*)
  1139 Goalw [NSLIMSEQ_def] 
  1104 Goalw [NSLIMSEQ_def] 
  1140        "f ----NS> l ==> (%n. abs(f n)) ----NS> abs(l)";
  1105        "f ----NS> l ==> (%n. abs(f n)) ----NS> abs(l)";
  1141 by (auto_tac (claset() addIs [inf_close_hrabs], simpset() 
  1106 by (auto_tac (claset() addIs [approx_hrabs], simpset() 
  1142     addsimps [starfunNat_rabs,hypreal_of_real_hrabs RS sym]));
  1107     addsimps [starfunNat_rabs,hypreal_of_real_hrabs RS sym]));
  1143 qed "NSLIMSEQ_imp_rabs";
  1108 qed "NSLIMSEQ_imp_rabs";
  1144 
  1109 
  1145 (* standard version *)
  1110 (* standard version *)
  1146 Goal "f ----> l ==> (%n. abs(f n)) ----> abs(l)";
  1111 Goal "f ----> l ==> (%n. abs(f n)) ----> abs(l)";
  1176 
  1141 
  1177 (*--------------------------------------------------------------
  1142 (*--------------------------------------------------------------
  1178              Sequence  1/n --> 0 as n --> infinity 
  1143              Sequence  1/n --> 0 as n --> infinity 
  1179  -------------------------------------------------------------*)
  1144  -------------------------------------------------------------*)
  1180 
  1145 
  1181 Goal "(%n. inverse(real_of_nat(Suc n))) ----> #0";
  1146 Goal "(%n. inverse(real(Suc n))) ----> #0";
  1182 by (rtac LIMSEQ_inverse_zero 1 THEN Step_tac 1);
  1147 by (rtac LIMSEQ_inverse_zero 1 THEN Step_tac 1);
  1183 by (cut_inst_tac [("x","y")] reals_Archimedean2 1);
  1148 by (cut_inst_tac [("x","y")] reals_Archimedean2 1);
  1184 by (Step_tac 1 THEN res_inst_tac [("x","n")] exI 1);
  1149 by (Step_tac 1 THEN res_inst_tac [("x","n")] exI 1);
  1185 by (auto_tac (claset(), simpset() addsimps [real_of_nat_Suc]));  
  1150 by (auto_tac (claset(), simpset() addsimps [real_of_nat_Suc]));  
  1186 by (subgoal_tac "y < real_of_nat na" 1);
  1151 by (subgoal_tac "y < real na" 1);
  1187 by (Asm_simp_tac 1);
  1152 by (Asm_simp_tac 1);
  1188 by (blast_tac (claset() addIs [order_less_le_trans]) 1);  
  1153 by (blast_tac (claset() addIs [order_less_le_trans]) 1);  
  1189 qed "LIMSEQ_inverse_real_of_nat";
  1154 qed "LIMSEQ_inverse_real_of_nat";
  1190 
  1155 
  1191 Goal "(%n. inverse(real_of_nat(Suc n))) ----NS> #0";
  1156 Goal "(%n. inverse(real(Suc n))) ----NS> #0";
  1192 by (simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff RS sym,
  1157 by (simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff RS sym,
  1193     LIMSEQ_inverse_real_of_nat]) 1);
  1158     LIMSEQ_inverse_real_of_nat]) 1);
  1194 qed "NSLIMSEQ_inverse_real_of_nat";
  1159 qed "NSLIMSEQ_inverse_real_of_nat";
  1195 
  1160 
  1196 (*--------------------------------------------
  1161 (*--------------------------------------------
  1197     Sequence  r + 1/n --> r as n --> infinity 
  1162     Sequence  r + 1/n --> r as n --> infinity 
  1198     now easily proved
  1163     now easily proved
  1199  --------------------------------------------*)
  1164  --------------------------------------------*)
  1200 Goal "(%n. r + inverse(real_of_nat(Suc n))) ----> r";
  1165 Goal "(%n. r + inverse(real(Suc n))) ----> r";
  1201 by (cut_facts_tac
  1166 by (cut_facts_tac
  1202     [ [LIMSEQ_const,LIMSEQ_inverse_real_of_nat] MRS LIMSEQ_add ] 1);
  1167     [ [LIMSEQ_const,LIMSEQ_inverse_real_of_nat] MRS LIMSEQ_add ] 1);
  1203 by Auto_tac;
  1168 by Auto_tac;
  1204 qed "LIMSEQ_inverse_real_of_posnat_add";
  1169 qed "LIMSEQ_inverse_real_of_posnat_add";
  1205 
  1170 
  1206 Goal "(%n. r + inverse(real_of_nat(Suc n))) ----NS> r";
  1171 Goal "(%n. r + inverse(real(Suc n))) ----NS> r";
  1207 by (simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff RS sym,
  1172 by (simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff RS sym,
  1208     LIMSEQ_inverse_real_of_posnat_add]) 1);
  1173     LIMSEQ_inverse_real_of_posnat_add]) 1);
  1209 qed "NSLIMSEQ_inverse_real_of_posnat_add";
  1174 qed "NSLIMSEQ_inverse_real_of_posnat_add";
  1210 
  1175 
  1211 (*--------------
  1176 (*--------------
  1212     Also...
  1177     Also...
  1213  --------------*)
  1178  --------------*)
  1214 
  1179 
  1215 Goal "(%n. r + -inverse(real_of_nat(Suc n))) ----> r";
  1180 Goal "(%n. r + -inverse(real(Suc n))) ----> r";
  1216 by (cut_facts_tac [[LIMSEQ_const,LIMSEQ_inverse_real_of_nat]
  1181 by (cut_facts_tac [[LIMSEQ_const,LIMSEQ_inverse_real_of_nat]
  1217                    MRS LIMSEQ_add_minus] 1);
  1182                    MRS LIMSEQ_add_minus] 1);
  1218 by (Auto_tac);
  1183 by (Auto_tac);
  1219 qed "LIMSEQ_inverse_real_of_posnat_add_minus";
  1184 qed "LIMSEQ_inverse_real_of_posnat_add_minus";
  1220 
  1185 
  1221 Goal "(%n. r + -inverse(real_of_nat(Suc n))) ----NS> r";
  1186 Goal "(%n. r + -inverse(real(Suc n))) ----NS> r";
  1222 by (simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff RS sym,
  1187 by (simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff RS sym,
  1223     LIMSEQ_inverse_real_of_posnat_add_minus]) 1);
  1188     LIMSEQ_inverse_real_of_posnat_add_minus]) 1);
  1224 qed "NSLIMSEQ_inverse_real_of_posnat_add_minus";
  1189 qed "NSLIMSEQ_inverse_real_of_posnat_add_minus";
  1225 
  1190 
  1226 Goal "(%n. r*( #1 + -inverse(real_of_nat(Suc n)))) ----> r";
  1191 Goal "(%n. r*( #1 + -inverse(real(Suc n)))) ----> r";
  1227 by (cut_inst_tac [("b","#1")] ([LIMSEQ_const,
  1192 by (cut_inst_tac [("b","#1")] ([LIMSEQ_const,
  1228     LIMSEQ_inverse_real_of_posnat_add_minus] MRS LIMSEQ_mult) 1);
  1193     LIMSEQ_inverse_real_of_posnat_add_minus] MRS LIMSEQ_mult) 1);
  1229 by (Auto_tac);
  1194 by (Auto_tac);
  1230 qed "LIMSEQ_inverse_real_of_posnat_add_minus_mult";
  1195 qed "LIMSEQ_inverse_real_of_posnat_add_minus_mult";
  1231 
  1196 
  1232 Goal "(%n. r*( #1 + -inverse(real_of_nat(Suc n)))) ----NS> r";
  1197 Goal "(%n. r*( #1 + -inverse(real(Suc n)))) ----NS> r";
  1233 by (simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff RS sym,
  1198 by (simp_tac (simpset() addsimps [LIMSEQ_NSLIMSEQ_iff RS sym,
  1234     LIMSEQ_inverse_real_of_posnat_add_minus_mult]) 1);
  1199     LIMSEQ_inverse_real_of_posnat_add_minus_mult]) 1);
  1235 qed "NSLIMSEQ_inverse_real_of_posnat_add_minus_mult";
  1200 qed "NSLIMSEQ_inverse_real_of_posnat_add_minus_mult";
  1236 
  1201 
  1237 (*---------------------------------------------------------------
  1202 (*---------------------------------------------------------------
  1283 by (forward_tac [HNatInfinite_add_one] 1);
  1248 by (forward_tac [HNatInfinite_add_one] 1);
  1284 by (dtac bspec 1 THEN assume_tac 1);
  1249 by (dtac bspec 1 THEN assume_tac 1);
  1285 by (dtac bspec 1 THEN assume_tac 1);
  1250 by (dtac bspec 1 THEN assume_tac 1);
  1286 by (dres_inst_tac [("x","N + 1hn")] bspec 1 THEN assume_tac 1);
  1251 by (dres_inst_tac [("x","N + 1hn")] bspec 1 THEN assume_tac 1);
  1287 by (asm_full_simp_tac (simpset() addsimps [hyperpow_add]) 1);
  1252 by (asm_full_simp_tac (simpset() addsimps [hyperpow_add]) 1);
  1288 by (dtac inf_close_mult_subst_SReal 1 THEN assume_tac 1);
  1253 by (dtac approx_mult_subst_SReal 1 THEN assume_tac 1);
  1289 by (dtac inf_close_trans3 1 THEN assume_tac 1);
  1254 by (dtac approx_trans3 1 THEN assume_tac 1);
  1290 by (auto_tac (claset(),
  1255 by (auto_tac (claset(),
  1291               simpset() delsimps [hypreal_of_real_mult]
  1256               simpset() delsimps [hypreal_of_real_mult]
  1292 			addsimps [hypreal_of_real_mult RS sym]));
  1257 			addsimps [hypreal_of_real_mult RS sym]));
  1293 qed "NSLIMSEQ_realpow_zero";
  1258 qed "NSLIMSEQ_realpow_zero";
  1294 
  1259