src/HOL/Hyperreal/HyperNat.ML
changeset 10797 028d22926a41
parent 10784 27e4d90b35b5
child 10834 a7897aebbffc
equal deleted inserted replaced
10796:c0bcea781b3a 10797:028d22926a41
    63 qed "equiv_hypnatrel";
    63 qed "equiv_hypnatrel";
    64 
    64 
    65 val equiv_hypnatrel_iff =
    65 val equiv_hypnatrel_iff =
    66     [UNIV_I, UNIV_I] MRS (equiv_hypnatrel RS eq_equiv_class_iff);
    66     [UNIV_I, UNIV_I] MRS (equiv_hypnatrel RS eq_equiv_class_iff);
    67 
    67 
    68 Goalw  [hypnat_def,hypnatrel_def,quotient_def] "hypnatrel^^{x}:hypnat";
    68 Goalw  [hypnat_def,hypnatrel_def,quotient_def] "hypnatrel```{x}:hypnat";
    69 by (Blast_tac 1);
    69 by (Blast_tac 1);
    70 qed "hypnatrel_in_hypnat";
    70 qed "hypnatrel_in_hypnat";
    71 
    71 
    72 Goal "inj_on Abs_hypnat hypnat";
    72 Goal "inj_on Abs_hypnat hypnat";
    73 by (rtac inj_on_inverseI 1);
    73 by (rtac inj_on_inverseI 1);
    83 Goal "inj(Rep_hypnat)";
    83 Goal "inj(Rep_hypnat)";
    84 by (rtac inj_inverseI 1);
    84 by (rtac inj_inverseI 1);
    85 by (rtac Rep_hypnat_inverse 1);
    85 by (rtac Rep_hypnat_inverse 1);
    86 qed "inj_Rep_hypnat";
    86 qed "inj_Rep_hypnat";
    87 
    87 
    88 Goalw [hypnatrel_def] "x: hypnatrel ^^ {x}";
    88 Goalw [hypnatrel_def] "x: hypnatrel ``` {x}";
    89 by (Step_tac 1);
    89 by (Step_tac 1);
    90 by Auto_tac;
    90 by Auto_tac;
    91 qed "lemma_hypnatrel_refl";
    91 qed "lemma_hypnatrel_refl";
    92 
    92 
    93 Addsimps [lemma_hypnatrel_refl];
    93 Addsimps [lemma_hypnatrel_refl];
   119 by (rtac ccontr 1 THEN rotate_tac 1 1);
   119 by (rtac ccontr 1 THEN rotate_tac 1 1);
   120 by Auto_tac;
   120 by Auto_tac;
   121 qed "inj_hypnat_of_nat";
   121 qed "inj_hypnat_of_nat";
   122 
   122 
   123 val [prem] = Goal
   123 val [prem] = Goal
   124     "(!!x. z = Abs_hypnat(hypnatrel^^{x}) ==> P) ==> P";
   124     "(!!x. z = Abs_hypnat(hypnatrel```{x}) ==> P) ==> P";
   125 by (res_inst_tac [("x1","z")] 
   125 by (res_inst_tac [("x1","z")] 
   126     (rewrite_rule [hypnat_def] Rep_hypnat RS quotientE) 1);
   126     (rewrite_rule [hypnat_def] Rep_hypnat RS quotientE) 1);
   127 by (dres_inst_tac [("f","Abs_hypnat")] arg_cong 1);
   127 by (dres_inst_tac [("f","Abs_hypnat")] arg_cong 1);
   128 by (res_inst_tac [("x","x")] prem 1);
   128 by (res_inst_tac [("x","x")] prem 1);
   129 by (asm_full_simp_tac (simpset() addsimps [Rep_hypnat_inverse]) 1);
   129 by (asm_full_simp_tac (simpset() addsimps [Rep_hypnat_inverse]) 1);
   131 
   131 
   132 (*-----------------------------------------------------------
   132 (*-----------------------------------------------------------
   133    Addition for hyper naturals: hypnat_add 
   133    Addition for hyper naturals: hypnat_add 
   134  -----------------------------------------------------------*)
   134  -----------------------------------------------------------*)
   135 Goalw [congruent2_def]
   135 Goalw [congruent2_def]
   136      "congruent2 hypnatrel (%X Y. hypnatrel^^{%n. X n + Y n})";
   136      "congruent2 hypnatrel (%X Y. hypnatrel```{%n. X n + Y n})";
   137 by Safe_tac;
   137 by Safe_tac;
   138 by (ALLGOALS(Fuf_tac));
   138 by (ALLGOALS(Fuf_tac));
   139 qed "hypnat_add_congruent2";
   139 qed "hypnat_add_congruent2";
   140 
   140 
   141 Goalw [hypnat_add_def]
   141 Goalw [hypnat_add_def]
   142   "Abs_hypnat(hypnatrel^^{%n. X n}) + Abs_hypnat(hypnatrel^^{%n. Y n}) = \
   142   "Abs_hypnat(hypnatrel```{%n. X n}) + Abs_hypnat(hypnatrel```{%n. Y n}) = \
   143 \  Abs_hypnat(hypnatrel^^{%n. X n + Y n})";
   143 \  Abs_hypnat(hypnatrel```{%n. X n + Y n})";
   144 by (asm_simp_tac
   144 by (asm_simp_tac
   145     (simpset() addsimps [[equiv_hypnatrel, hypnat_add_congruent2] 
   145     (simpset() addsimps [[equiv_hypnatrel, hypnat_add_congruent2] 
   146      MRS UN_equiv_class2]) 1);
   146      MRS UN_equiv_class2]) 1);
   147 qed "hypnat_add";
   147 qed "hypnat_add";
   148 
   148 
   184 
   184 
   185 (*-----------------------------------------------------------
   185 (*-----------------------------------------------------------
   186    Subtraction for hyper naturals: hypnat_minus
   186    Subtraction for hyper naturals: hypnat_minus
   187  -----------------------------------------------------------*)
   187  -----------------------------------------------------------*)
   188 Goalw [congruent2_def]
   188 Goalw [congruent2_def]
   189     "congruent2 hypnatrel (%X Y. hypnatrel^^{%n. X n - Y n})";
   189     "congruent2 hypnatrel (%X Y. hypnatrel```{%n. X n - Y n})";
   190 by Safe_tac;
   190 by Safe_tac;
   191 by (ALLGOALS(Fuf_tac));
   191 by (ALLGOALS(Fuf_tac));
   192 qed "hypnat_minus_congruent2";
   192 qed "hypnat_minus_congruent2";
   193  
   193  
   194 Goalw [hypnat_minus_def]
   194 Goalw [hypnat_minus_def]
   195   "Abs_hypnat(hypnatrel^^{%n. X n}) - Abs_hypnat(hypnatrel^^{%n. Y n}) = \
   195   "Abs_hypnat(hypnatrel```{%n. X n}) - Abs_hypnat(hypnatrel```{%n. Y n}) = \
   196 \  Abs_hypnat(hypnatrel^^{%n. X n - Y n})";
   196 \  Abs_hypnat(hypnatrel```{%n. X n - Y n})";
   197 by (asm_simp_tac
   197 by (asm_simp_tac
   198     (simpset() addsimps [[equiv_hypnatrel, hypnat_minus_congruent2] 
   198     (simpset() addsimps [[equiv_hypnatrel, hypnat_minus_congruent2] 
   199      MRS UN_equiv_class2]) 1);
   199      MRS UN_equiv_class2]) 1);
   200 qed "hypnat_minus";
   200 qed "hypnat_minus";
   201 
   201 
   271 
   271 
   272 (*-----------------------------------------------------------
   272 (*-----------------------------------------------------------
   273    Multiplication for hyper naturals: hypnat_mult
   273    Multiplication for hyper naturals: hypnat_mult
   274  -----------------------------------------------------------*)
   274  -----------------------------------------------------------*)
   275 Goalw [congruent2_def]
   275 Goalw [congruent2_def]
   276     "congruent2 hypnatrel (%X Y. hypnatrel^^{%n. X n * Y n})";
   276     "congruent2 hypnatrel (%X Y. hypnatrel```{%n. X n * Y n})";
   277 by Safe_tac;
   277 by Safe_tac;
   278 by (ALLGOALS(Fuf_tac));
   278 by (ALLGOALS(Fuf_tac));
   279 qed "hypnat_mult_congruent2";
   279 qed "hypnat_mult_congruent2";
   280 
   280 
   281 Goalw [hypnat_mult_def]
   281 Goalw [hypnat_mult_def]
   282   "Abs_hypnat(hypnatrel^^{%n. X n}) * Abs_hypnat(hypnatrel^^{%n. Y n}) = \
   282   "Abs_hypnat(hypnatrel```{%n. X n}) * Abs_hypnat(hypnatrel```{%n. Y n}) = \
   283 \  Abs_hypnat(hypnatrel^^{%n. X n * Y n})";
   283 \  Abs_hypnat(hypnatrel```{%n. X n * Y n})";
   284 by (asm_simp_tac
   284 by (asm_simp_tac
   285     (simpset() addsimps [[equiv_hypnatrel,hypnat_mult_congruent2] MRS
   285     (simpset() addsimps [[equiv_hypnatrel,hypnat_mult_congruent2] MRS
   286      UN_equiv_class2]) 1);
   286      UN_equiv_class2]) 1);
   287 qed "hypnat_mult";
   287 qed "hypnat_mult";
   288 
   288 
   473 
   473 
   474 (*----- hypnat less iff less a.e -----*)
   474 (*----- hypnat less iff less a.e -----*)
   475 (* See comments in HYPER for corresponding thm *)
   475 (* See comments in HYPER for corresponding thm *)
   476 
   476 
   477 Goalw [hypnat_less_def]
   477 Goalw [hypnat_less_def]
   478       "(Abs_hypnat(hypnatrel^^{%n. X n}) < \
   478       "(Abs_hypnat(hypnatrel```{%n. X n}) < \
   479 \           Abs_hypnat(hypnatrel^^{%n. Y n})) = \
   479 \           Abs_hypnat(hypnatrel```{%n. Y n})) = \
   480 \      ({n. X n < Y n} : FreeUltrafilterNat)";
   480 \      ({n. X n < Y n} : FreeUltrafilterNat)";
   481 by (auto_tac (claset() addSIs [lemma_hypnatrel_refl],simpset()));
   481 by (auto_tac (claset() addSIs [lemma_hypnatrel_refl],simpset()));
   482 by (Fuf_tac 1);
   482 by (Fuf_tac 1);
   483 qed "hypnat_less";
   483 qed "hypnat_less";
   484 
   484 
   525 qed "hypnat_mult_order";
   525 qed "hypnat_mult_order";
   526 
   526 
   527 (*---------------------------------------------------------------------------------
   527 (*---------------------------------------------------------------------------------
   528                    Trichotomy of the hyper naturals
   528                    Trichotomy of the hyper naturals
   529   --------------------------------------------------------------------------------*)
   529   --------------------------------------------------------------------------------*)
   530 Goalw [hypnatrel_def] "EX x. x: hypnatrel ^^ {%n. 0}";
   530 Goalw [hypnatrel_def] "EX x. x: hypnatrel ``` {%n. 0}";
   531 by (res_inst_tac [("x","%n. 0")] exI 1);
   531 by (res_inst_tac [("x","%n. 0")] exI 1);
   532 by (Step_tac 1);
   532 by (Step_tac 1);
   533 by Auto_tac;
   533 by Auto_tac;
   534 qed "lemma_hypnatrel_0_mem";
   534 qed "lemma_hypnatrel_0_mem";
   535 
   535 
   618                             Properties of <=
   618                             Properties of <=
   619  ----------------------------------------------------------------------------*)
   619  ----------------------------------------------------------------------------*)
   620 
   620 
   621 (*------ hypnat le iff nat le a.e ------*)
   621 (*------ hypnat le iff nat le a.e ------*)
   622 Goalw [hypnat_le_def,le_def]
   622 Goalw [hypnat_le_def,le_def]
   623       "(Abs_hypnat(hypnatrel^^{%n. X n}) <= \
   623       "(Abs_hypnat(hypnatrel```{%n. X n}) <= \
   624 \           Abs_hypnat(hypnatrel^^{%n. Y n})) = \
   624 \           Abs_hypnat(hypnatrel```{%n. Y n})) = \
   625 \      ({n. X n <= Y n} : FreeUltrafilterNat)";
   625 \      ({n. X n <= Y n} : FreeUltrafilterNat)";
   626 by (auto_tac (claset() addSDs [FreeUltrafilterNat_Compl_mem],
   626 by (auto_tac (claset() addSDs [FreeUltrafilterNat_Compl_mem],
   627     simpset() addsimps [hypnat_less]));
   627     simpset() addsimps [hypnat_less]));
   628 by (Fuf_tac 1 THEN Fuf_empty_tac 1);
   628 by (Fuf_tac 1 THEN Fuf_empty_tac 1);
   629 qed "hypnat_le";
   629 qed "hypnat_le";
   831 
   831 
   832 (*---------------------------------------------------------------------------------
   832 (*---------------------------------------------------------------------------------
   833               Existence of infinite hypernatural number
   833               Existence of infinite hypernatural number
   834  ---------------------------------------------------------------------------------*)
   834  ---------------------------------------------------------------------------------*)
   835 
   835 
   836 Goal "hypnatrel^^{%n::nat. n} : hypnat";
   836 Goal "hypnatrel```{%n::nat. n} : hypnat";
   837 by Auto_tac;
   837 by Auto_tac;
   838 qed "hypnat_omega";
   838 qed "hypnat_omega";
   839 
   839 
   840 Goalw [hypnat_omega_def] "Rep_hypnat(whn) : hypnat";
   840 Goalw [hypnat_omega_def] "Rep_hypnat(whn) : hypnat";
   841 by (rtac Rep_hypnat 1);
   841 by (rtac Rep_hypnat 1);
  1064 (*** alternative definition ***)
  1064 (*** alternative definition ***)
  1065 Goalw [HNatInfinite_def,SHNat_def,hypnat_of_nat_def] 
  1065 Goalw [HNatInfinite_def,SHNat_def,hypnat_of_nat_def] 
  1066      "HNatInfinite = {N. ALL n:SNat. n < N}";
  1066      "HNatInfinite = {N. ALL n:SNat. n < N}";
  1067 by (Step_tac 1);
  1067 by (Step_tac 1);
  1068 by (dres_inst_tac [("x","Abs_hypnat \
  1068 by (dres_inst_tac [("x","Abs_hypnat \
  1069 \        (hypnatrel ^^ {%n. N})")] bspec 2);
  1069 \        (hypnatrel ``` {%n. N})")] bspec 2);
  1070 by (res_inst_tac [("z","x")] eq_Abs_hypnat 1);
  1070 by (res_inst_tac [("z","x")] eq_Abs_hypnat 1);
  1071 by (res_inst_tac [("z","n")] eq_Abs_hypnat 1);
  1071 by (res_inst_tac [("z","n")] eq_Abs_hypnat 1);
  1072 by (auto_tac (claset(),simpset() addsimps [hypnat_less_iff]));
  1072 by (auto_tac (claset(),simpset() addsimps [hypnat_less_iff]));
  1073 by (auto_tac (claset() addSIs [exI] addEs 
  1073 by (auto_tac (claset() addSIs [exI] addEs 
  1074     [HNatInfinite_FreeUltrafilterNat_lemma],
  1074     [HNatInfinite_FreeUltrafilterNat_lemma],
  1213 
  1213 
  1214 (*---------------------------------------------------------------
  1214 (*---------------------------------------------------------------
  1215     Embedding of the hypernaturals into the hyperreal
  1215     Embedding of the hypernaturals into the hyperreal
  1216  --------------------------------------------------------------*)
  1216  --------------------------------------------------------------*)
  1217 
  1217 
  1218 Goal "(Ya : hyprel ^^{%n. f(n)}) = \
  1218 Goal "(Ya : hyprel ```{%n. f(n)}) = \
  1219 \     ({n. f n = Ya n} : FreeUltrafilterNat)";
  1219 \     ({n. f n = Ya n} : FreeUltrafilterNat)";
  1220 by Auto_tac;
  1220 by Auto_tac;
  1221 qed "lemma_hyprel_FUFN";
  1221 qed "lemma_hyprel_FUFN";
  1222 
  1222 
  1223 Goalw [hypreal_of_hypnat_def]
  1223 Goalw [hypreal_of_hypnat_def]
  1224       "hypreal_of_hypnat (Abs_hypnat(hypnatrel^^{%n. X n})) = \
  1224       "hypreal_of_hypnat (Abs_hypnat(hypnatrel```{%n. X n})) = \
  1225 \         Abs_hypreal(hyprel ^^ {%n. real_of_nat (X n)})";
  1225 \         Abs_hypreal(hyprel ``` {%n. real_of_nat (X n)})";
  1226 by (res_inst_tac [("f","Abs_hypreal")] arg_cong 1);
  1226 by (res_inst_tac [("f","Abs_hypreal")] arg_cong 1);
  1227 by (auto_tac (claset()
  1227 by (auto_tac (claset()
  1228                   addEs [FreeUltrafilterNat_Int RS FreeUltrafilterNat_subset],
  1228                   addEs [FreeUltrafilterNat_Int RS FreeUltrafilterNat_subset],
  1229               simpset() addsimps [lemma_hyprel_FUFN]));
  1229               simpset() addsimps [lemma_hyprel_FUFN]));
  1230 qed "hypreal_of_hypnat";
  1230 qed "hypreal_of_hypnat";