src/HOL/Hyperreal/HyperDef.thy
author paulson
Mon Mar 15 10:46:19 2004 +0100 (2004-03-15)
changeset 14468 6be497cacab5
parent 14430 5cb24165a2e1
child 14477 cc61fd03e589
permissions -rw-r--r--
heavy tidying
     1 (*  Title       : HOL/Real/Hyperreal/HyperDef.thy
     2     ID          : $Id$
     3     Author      : Jacques D. Fleuriot
     4     Copyright   : 1998  University of Cambridge
     5     Conversion to Isar and new proofs by Lawrence C Paulson, 2004
     6 *)
     7 
     8 header{*Construction of Hyperreals Using Ultrafilters*}
     9 
    10 theory HyperDef = Filter + Real
    11 files ("fuf.ML"):  (*Warning: file fuf.ML refers to the name Hyperdef!*)
    12 
    13 
    14 constdefs
    15 
    16   FreeUltrafilterNat   :: "nat set set"    ("\<U>")
    17     "FreeUltrafilterNat == (SOME U. U \<in> FreeUltrafilter (UNIV:: nat set))"
    18 
    19   hyprel :: "((nat=>real)*(nat=>real)) set"
    20     "hyprel == {p. \<exists>X Y. p = ((X::nat=>real),Y) &
    21                    {n::nat. X(n) = Y(n)}: FreeUltrafilterNat}"
    22 
    23 typedef hypreal = "UNIV//hyprel" 
    24     by (auto simp add: quotient_def) 
    25 
    26 instance hypreal :: ord ..
    27 instance hypreal :: zero ..
    28 instance hypreal :: one ..
    29 instance hypreal :: plus ..
    30 instance hypreal :: times ..
    31 instance hypreal :: minus ..
    32 instance hypreal :: inverse ..
    33 
    34 
    35 defs (overloaded)
    36 
    37   hypreal_zero_def:
    38   "0 == Abs_hypreal(hyprel``{%n::nat. (0::real)})"
    39 
    40   hypreal_one_def:
    41   "1 == Abs_hypreal(hyprel``{%n::nat. (1::real)})"
    42 
    43   hypreal_minus_def:
    44   "- P == Abs_hypreal(\<Union>X \<in> Rep_hypreal(P). hyprel``{%n::nat. - (X n)})"
    45 
    46   hypreal_diff_def:
    47   "x - y == x + -(y::hypreal)"
    48 
    49   hypreal_inverse_def:
    50   "inverse P == Abs_hypreal(\<Union>X \<in> Rep_hypreal(P).
    51                     hyprel``{%n. if X n = 0 then 0 else inverse (X n)})"
    52 
    53   hypreal_divide_def:
    54   "P / Q::hypreal == P * inverse Q"
    55 
    56 constdefs
    57 
    58   hypreal_of_real  :: "real => hypreal"
    59   "hypreal_of_real r         == Abs_hypreal(hyprel``{%n::nat. r})"
    60 
    61   omega   :: hypreal   (*an infinite number = [<1,2,3,...>] *)
    62   "omega == Abs_hypreal(hyprel``{%n::nat. real (Suc n)})"
    63 
    64   epsilon :: hypreal   (*an infinitesimal number = [<1,1/2,1/3,...>] *)
    65   "epsilon == Abs_hypreal(hyprel``{%n::nat. inverse (real (Suc n))})"
    66 
    67 syntax (xsymbols)
    68   omega   :: hypreal   ("\<omega>")
    69   epsilon :: hypreal   ("\<epsilon>")
    70 
    71 
    72 defs (overloaded)
    73 
    74   hypreal_add_def:
    75   "P + Q == Abs_hypreal(\<Union>X \<in> Rep_hypreal(P). \<Union>Y \<in> Rep_hypreal(Q).
    76                 hyprel``{%n::nat. X n + Y n})"
    77 
    78   hypreal_mult_def:
    79   "P * Q == Abs_hypreal(\<Union>X \<in> Rep_hypreal(P). \<Union>Y \<in> Rep_hypreal(Q).
    80                 hyprel``{%n::nat. X n * Y n})"
    81 
    82   hypreal_le_def:
    83   "P \<le> (Q::hypreal) == \<exists>X Y. X \<in> Rep_hypreal(P) &
    84                                Y \<in> Rep_hypreal(Q) &
    85                                {n::nat. X n \<le> Y n} \<in> FreeUltrafilterNat"
    86 
    87   hypreal_less_def: "(x < (y::hypreal)) == (x \<le> y & x \<noteq> y)"
    88 
    89   hrabs_def:  "abs (r::hypreal) == (if 0 \<le> r then r else -r)"
    90 
    91 
    92 subsection{*The Set of Naturals is not Finite*}
    93 
    94 (*** based on James' proof that the set of naturals is not finite ***)
    95 lemma finite_exhausts [rule_format]:
    96      "finite (A::nat set) --> (\<exists>n. \<forall>m. Suc (n + m) \<notin> A)"
    97 apply (rule impI)
    98 apply (erule_tac F = A in finite_induct)
    99 apply (blast, erule exE)
   100 apply (rule_tac x = "n + x" in exI)
   101 apply (rule allI, erule_tac x = "x + m" in allE)
   102 apply (auto simp add: add_ac)
   103 done
   104 
   105 lemma finite_not_covers [rule_format (no_asm)]:
   106      "finite (A :: nat set) --> (\<exists>n. n \<notin>A)"
   107 by (rule impI, drule finite_exhausts, blast)
   108 
   109 lemma not_finite_nat: "~ finite(UNIV:: nat set)"
   110 by (fast dest!: finite_exhausts)
   111 
   112 
   113 subsection{*Existence of Free Ultrafilter over the Naturals*}
   114 
   115 text{*Also, proof of various properties of @{term FreeUltrafilterNat}: 
   116 an arbitrary free ultrafilter*}
   117 
   118 lemma FreeUltrafilterNat_Ex: "\<exists>U. U: FreeUltrafilter (UNIV::nat set)"
   119 by (rule not_finite_nat [THEN FreeUltrafilter_Ex])
   120 
   121 lemma FreeUltrafilterNat_mem [simp]: 
   122      "FreeUltrafilterNat: FreeUltrafilter(UNIV:: nat set)"
   123 apply (unfold FreeUltrafilterNat_def)
   124 apply (rule FreeUltrafilterNat_Ex [THEN exE])
   125 apply (rule someI2, assumption+)
   126 done
   127 
   128 lemma FreeUltrafilterNat_finite: "finite x ==> x \<notin> FreeUltrafilterNat"
   129 apply (unfold FreeUltrafilterNat_def)
   130 apply (rule FreeUltrafilterNat_Ex [THEN exE])
   131 apply (rule someI2, assumption)
   132 apply (blast dest: mem_FreeUltrafiltersetD1)
   133 done
   134 
   135 lemma FreeUltrafilterNat_not_finite: "x: FreeUltrafilterNat ==> ~ finite x"
   136 by (blast dest: FreeUltrafilterNat_finite)
   137 
   138 lemma FreeUltrafilterNat_empty [simp]: "{} \<notin> FreeUltrafilterNat"
   139 apply (unfold FreeUltrafilterNat_def)
   140 apply (rule FreeUltrafilterNat_Ex [THEN exE])
   141 apply (rule someI2, assumption)
   142 apply (blast dest: FreeUltrafilter_Ultrafilter Ultrafilter_Filter 
   143                    Filter_empty_not_mem)
   144 done
   145 
   146 lemma FreeUltrafilterNat_Int:
   147      "[| X: FreeUltrafilterNat;  Y: FreeUltrafilterNat |]   
   148       ==> X Int Y \<in> FreeUltrafilterNat"
   149 apply (cut_tac FreeUltrafilterNat_mem)
   150 apply (blast dest: FreeUltrafilter_Ultrafilter Ultrafilter_Filter mem_FiltersetD1)
   151 done
   152 
   153 lemma FreeUltrafilterNat_subset:
   154      "[| X: FreeUltrafilterNat;  X \<subseteq> Y |]  
   155       ==> Y \<in> FreeUltrafilterNat"
   156 apply (cut_tac FreeUltrafilterNat_mem)
   157 apply (blast dest: FreeUltrafilter_Ultrafilter Ultrafilter_Filter mem_FiltersetD2)
   158 done
   159 
   160 lemma FreeUltrafilterNat_Compl:
   161      "X: FreeUltrafilterNat ==> -X \<notin> FreeUltrafilterNat"
   162 apply safe
   163 apply (drule FreeUltrafilterNat_Int, assumption, auto)
   164 done
   165 
   166 lemma FreeUltrafilterNat_Compl_mem:
   167      "X\<notin> FreeUltrafilterNat ==> -X \<in> FreeUltrafilterNat"
   168 apply (cut_tac FreeUltrafilterNat_mem [THEN FreeUltrafilter_iff [THEN iffD1]])
   169 apply (safe, drule_tac x = X in bspec)
   170 apply (auto simp add: UNIV_diff_Compl)
   171 done
   172 
   173 lemma FreeUltrafilterNat_Compl_iff1:
   174      "(X \<notin> FreeUltrafilterNat) = (-X: FreeUltrafilterNat)"
   175 by (blast dest: FreeUltrafilterNat_Compl FreeUltrafilterNat_Compl_mem)
   176 
   177 lemma FreeUltrafilterNat_Compl_iff2:
   178      "(X: FreeUltrafilterNat) = (-X \<notin> FreeUltrafilterNat)"
   179 by (auto simp add: FreeUltrafilterNat_Compl_iff1 [symmetric])
   180 
   181 lemma cofinite_mem_FreeUltrafilterNat: "finite (-X) ==> X \<in> FreeUltrafilterNat"
   182 apply (drule FreeUltrafilterNat_finite)  
   183 apply (simp add: FreeUltrafilterNat_Compl_iff2 [symmetric])
   184 done
   185 
   186 lemma FreeUltrafilterNat_UNIV [simp]: "(UNIV::nat set) \<in> FreeUltrafilterNat"
   187 by (rule FreeUltrafilterNat_mem [THEN FreeUltrafilter_Ultrafilter, THEN Ultrafilter_Filter, THEN mem_FiltersetD4])
   188 
   189 lemma FreeUltrafilterNat_Nat_set [simp]: "UNIV \<in> FreeUltrafilterNat"
   190 by auto
   191 
   192 lemma FreeUltrafilterNat_Nat_set_refl [intro]:
   193      "{n. P(n) = P(n)} \<in> FreeUltrafilterNat"
   194 by simp
   195 
   196 lemma FreeUltrafilterNat_P: "{n::nat. P} \<in> FreeUltrafilterNat ==> P"
   197 by (rule ccontr, simp)
   198 
   199 lemma FreeUltrafilterNat_Ex_P: "{n. P(n)} \<in> FreeUltrafilterNat ==> \<exists>n. P(n)"
   200 by (rule ccontr, simp)
   201 
   202 lemma FreeUltrafilterNat_all: "\<forall>n. P(n) ==> {n. P(n)} \<in> FreeUltrafilterNat"
   203 by (auto intro: FreeUltrafilterNat_Nat_set)
   204 
   205 
   206 text{*Define and use Ultrafilter tactics*}
   207 use "fuf.ML"
   208 
   209 method_setup fuf = {*
   210     Method.ctxt_args (fn ctxt =>
   211         Method.METHOD (fn facts =>
   212             fuf_tac (Classical.get_local_claset ctxt,
   213                      Simplifier.get_local_simpset ctxt) 1)) *}
   214     "free ultrafilter tactic"
   215 
   216 method_setup ultra = {*
   217     Method.ctxt_args (fn ctxt =>
   218         Method.METHOD (fn facts =>
   219             ultra_tac (Classical.get_local_claset ctxt,
   220                        Simplifier.get_local_simpset ctxt) 1)) *}
   221     "ultrafilter tactic"
   222 
   223 
   224 text{*One further property of our free ultrafilter*}
   225 lemma FreeUltrafilterNat_Un:
   226      "X Un Y: FreeUltrafilterNat  
   227       ==> X: FreeUltrafilterNat | Y: FreeUltrafilterNat"
   228 apply auto
   229 apply ultra
   230 done
   231 
   232 
   233 subsection{*Properties of @{term hyprel}*}
   234 
   235 text{*Proving that @{term hyprel} is an equivalence relation*}
   236 
   237 lemma hyprel_iff: "((X,Y) \<in> hyprel) = ({n. X n = Y n}: FreeUltrafilterNat)"
   238 by (simp add: hyprel_def)
   239 
   240 lemma hyprel_refl: "(x,x) \<in> hyprel"
   241 by (simp add: hyprel_def)
   242 
   243 lemma hyprel_sym [rule_format (no_asm)]: "(x,y) \<in> hyprel --> (y,x) \<in> hyprel"
   244 by (simp add: hyprel_def eq_commute)
   245 
   246 lemma hyprel_trans: 
   247       "[|(x,y) \<in> hyprel; (y,z) \<in> hyprel|] ==> (x,z) \<in> hyprel"
   248 by (simp add: hyprel_def, ultra)
   249 
   250 lemma equiv_hyprel: "equiv UNIV hyprel"
   251 apply (simp add: equiv_def refl_def sym_def trans_def hyprel_refl)
   252 apply (blast intro: hyprel_sym hyprel_trans) 
   253 done
   254 
   255 (* (hyprel `` {x} = hyprel `` {y}) = ((x,y) \<in> hyprel) *)
   256 lemmas equiv_hyprel_iff =
   257     eq_equiv_class_iff [OF equiv_hyprel UNIV_I UNIV_I, simp] 
   258 
   259 lemma hyprel_in_hypreal [simp]: "hyprel``{x}:hypreal"
   260 by (simp add: hypreal_def hyprel_def quotient_def, blast)
   261 
   262 lemma inj_on_Abs_hypreal: "inj_on Abs_hypreal hypreal"
   263 apply (rule inj_on_inverseI)
   264 apply (erule Abs_hypreal_inverse)
   265 done
   266 
   267 declare inj_on_Abs_hypreal [THEN inj_on_iff, simp] 
   268         Abs_hypreal_inverse [simp]
   269 
   270 declare equiv_hyprel [THEN eq_equiv_class_iff, simp]
   271 
   272 declare hyprel_iff [iff]
   273 
   274 lemmas eq_hyprelD = eq_equiv_class [OF _ equiv_hyprel]
   275 
   276 lemma inj_Rep_hypreal: "inj(Rep_hypreal)"
   277 apply (rule inj_on_inverseI)
   278 apply (rule Rep_hypreal_inverse)
   279 done
   280 
   281 lemma lemma_hyprel_refl [simp]: "x \<in> hyprel `` {x}"
   282 by (simp add: hyprel_def)
   283 
   284 lemma hypreal_empty_not_mem [simp]: "{} \<notin> hypreal"
   285 apply (simp add: hypreal_def)
   286 apply (auto elim!: quotientE equalityCE)
   287 done
   288 
   289 lemma Rep_hypreal_nonempty [simp]: "Rep_hypreal x \<noteq> {}"
   290 by (cut_tac x = x in Rep_hypreal, auto)
   291 
   292 
   293 subsection{*@{term hypreal_of_real}: 
   294             the Injection from @{typ real} to @{typ hypreal}*}
   295 
   296 lemma inj_hypreal_of_real: "inj(hypreal_of_real)"
   297 apply (rule inj_onI)
   298 apply (simp add: hypreal_of_real_def split: split_if_asm)
   299 done
   300 
   301 lemma eq_Abs_hypreal:
   302     "(!!x. z = Abs_hypreal(hyprel``{x}) ==> P) ==> P"
   303 apply (rule_tac x1=z in Rep_hypreal [unfolded hypreal_def, THEN quotientE])
   304 apply (drule_tac f = Abs_hypreal in arg_cong)
   305 apply (force simp add: Rep_hypreal_inverse)
   306 done
   307 
   308 theorem hypreal_cases [case_names Abs_hypreal, cases type: hypreal]:
   309     "(!!x. z = Abs_hypreal(hyprel``{x}) ==> P) ==> P"
   310 by (rule eq_Abs_hypreal [of z], blast)
   311 
   312 
   313 subsection{*Hyperreal Addition*}
   314 
   315 lemma hypreal_add_congruent2: 
   316     "congruent2 hyprel (%X Y. hyprel``{%n. X n + Y n})"
   317 apply (simp add: congruent2_def, auto, ultra)
   318 done
   319 
   320 lemma hypreal_add: 
   321   "Abs_hypreal(hyprel``{%n. X n}) + Abs_hypreal(hyprel``{%n. Y n}) =  
   322    Abs_hypreal(hyprel``{%n. X n + Y n})"
   323 apply (simp add: hypreal_add_def)
   324 apply (simp add: UN_equiv_class2 [OF equiv_hyprel hypreal_add_congruent2])
   325 done
   326 
   327 lemma hypreal_add_commute: "(z::hypreal) + w = w + z"
   328 apply (cases z, cases w)
   329 apply (simp add: add_ac hypreal_add)
   330 done
   331 
   332 lemma hypreal_add_assoc: "((z1::hypreal) + z2) + z3 = z1 + (z2 + z3)"
   333 apply (cases z1, cases z2, cases z3)
   334 apply (simp add: hypreal_add real_add_assoc)
   335 done
   336 
   337 lemma hypreal_add_zero_left: "(0::hypreal) + z = z"
   338 by (cases z, simp add: hypreal_zero_def hypreal_add)
   339 
   340 instance hypreal :: plus_ac0
   341   by (intro_classes,
   342       (assumption | 
   343        rule hypreal_add_commute hypreal_add_assoc hypreal_add_zero_left)+)
   344 
   345 lemma hypreal_add_zero_right [simp]: "z + (0::hypreal) = z"
   346 by (simp add: hypreal_add_zero_left hypreal_add_commute)
   347 
   348 
   349 subsection{*Additive inverse on @{typ hypreal}*}
   350 
   351 lemma hypreal_minus_congruent: 
   352   "congruent hyprel (%X. hyprel``{%n. - (X n)})"
   353 by (force simp add: congruent_def)
   354 
   355 lemma hypreal_minus: 
   356    "- (Abs_hypreal(hyprel``{%n. X n})) = Abs_hypreal(hyprel `` {%n. -(X n)})"
   357 apply (simp add: hypreal_minus_def)
   358 apply (rule_tac f = Abs_hypreal in arg_cong)
   359 apply (simp add: hyprel_in_hypreal [THEN Abs_hypreal_inverse] 
   360                UN_equiv_class [OF equiv_hyprel hypreal_minus_congruent])
   361 done
   362 
   363 lemma hypreal_diff:
   364      "Abs_hypreal(hyprel``{%n. X n}) - Abs_hypreal(hyprel``{%n. Y n}) =  
   365       Abs_hypreal(hyprel``{%n. X n - Y n})"
   366 apply (simp add: hypreal_diff_def hypreal_minus hypreal_add)
   367 done
   368 
   369 lemma hypreal_add_minus [simp]: "z + -z = (0::hypreal)"
   370 apply (simp add: hypreal_zero_def)
   371 apply (rule_tac z = z in eq_Abs_hypreal)
   372 apply (simp add: hypreal_minus hypreal_add)
   373 done
   374 
   375 lemma hypreal_add_minus_left: "-z + z = (0::hypreal)"
   376 by (simp add: hypreal_add_commute hypreal_add_minus)
   377 
   378 
   379 subsection{*Hyperreal Multiplication*}
   380 
   381 lemma hypreal_mult_congruent2: 
   382     "congruent2 hyprel (%X Y. hyprel``{%n. X n * Y n})"
   383 apply (simp add: congruent2_def, auto, ultra)
   384 done
   385 
   386 lemma hypreal_mult: 
   387   "Abs_hypreal(hyprel``{%n. X n}) * Abs_hypreal(hyprel``{%n. Y n}) =  
   388    Abs_hypreal(hyprel``{%n. X n * Y n})"
   389 apply (simp add: hypreal_mult_def)
   390 apply (simp add: UN_equiv_class2 [OF equiv_hyprel hypreal_mult_congruent2])
   391 done
   392 
   393 lemma hypreal_mult_commute: "(z::hypreal) * w = w * z"
   394 apply (cases z, cases w)
   395 apply (simp add: hypreal_mult mult_ac)
   396 done
   397 
   398 lemma hypreal_mult_assoc: "((z1::hypreal) * z2) * z3 = z1 * (z2 * z3)"
   399 apply (cases z1, cases z2, cases z3)
   400 apply (simp add: hypreal_mult mult_assoc)
   401 done
   402 
   403 lemma hypreal_mult_1: "(1::hypreal) * z = z"
   404 apply (simp add: hypreal_one_def)
   405 apply (rule_tac z = z in eq_Abs_hypreal)
   406 apply (simp add: hypreal_mult)
   407 done
   408 
   409 lemma hypreal_add_mult_distrib:
   410      "((z1::hypreal) + z2) * w = (z1 * w) + (z2 * w)"
   411 apply (cases z1, cases z2, cases w)
   412 apply (simp add: hypreal_mult hypreal_add left_distrib)
   413 done
   414 
   415 text{*one and zero are distinct*}
   416 lemma hypreal_zero_not_eq_one: "0 \<noteq> (1::hypreal)"
   417 by (simp add: hypreal_zero_def hypreal_one_def)
   418 
   419 
   420 subsection{*Multiplicative Inverse on @{typ hypreal} *}
   421 
   422 lemma hypreal_inverse_congruent: 
   423   "congruent hyprel (%X. hyprel``{%n. if X n = 0 then 0 else inverse(X n)})"
   424 apply (simp add: congruent_def)
   425 apply (auto, ultra)
   426 done
   427 
   428 lemma hypreal_inverse: 
   429       "inverse (Abs_hypreal(hyprel``{%n. X n})) =  
   430        Abs_hypreal(hyprel `` {%n. if X n = 0 then 0 else inverse(X n)})"
   431 apply (simp add: hypreal_inverse_def)
   432 apply (rule_tac f = Abs_hypreal in arg_cong)
   433 apply (simp add: hyprel_in_hypreal [THEN Abs_hypreal_inverse] 
   434            UN_equiv_class [OF equiv_hyprel hypreal_inverse_congruent])
   435 done
   436 
   437 lemma hypreal_mult_inverse: 
   438      "x \<noteq> 0 ==> x*inverse(x) = (1::hypreal)"
   439 apply (simp add: hypreal_one_def hypreal_zero_def)
   440 apply (cases x)
   441 apply (simp add: hypreal_inverse hypreal_mult)
   442 apply (drule FreeUltrafilterNat_Compl_mem)
   443 apply (blast intro!: right_inverse FreeUltrafilterNat_subset)
   444 done
   445 
   446 lemma hypreal_mult_inverse_left:
   447      "x \<noteq> 0 ==> inverse(x)*x = (1::hypreal)"
   448 by (simp add: hypreal_mult_inverse hypreal_mult_commute)
   449 
   450 instance hypreal :: field
   451 proof
   452   fix x y z :: hypreal
   453   show "(x + y) + z = x + (y + z)" by (rule hypreal_add_assoc)
   454   show "x + y = y + x" by (rule hypreal_add_commute)
   455   show "0 + x = x" by simp
   456   show "- x + x = 0" by (simp add: hypreal_add_minus_left)
   457   show "x - y = x + (-y)" by (simp add: hypreal_diff_def)
   458   show "(x * y) * z = x * (y * z)" by (rule hypreal_mult_assoc)
   459   show "x * y = y * x" by (rule hypreal_mult_commute)
   460   show "1 * x = x" by (simp add: hypreal_mult_1)
   461   show "(x + y) * z = x * z + y * z" by (simp add: hypreal_add_mult_distrib)
   462   show "0 \<noteq> (1::hypreal)" by (rule hypreal_zero_not_eq_one)
   463   show "x \<noteq> 0 ==> inverse x * x = 1" by (simp add: hypreal_mult_inverse_left)
   464   show "x / y = x * inverse y" by (simp add: hypreal_divide_def)
   465 qed
   466 
   467 
   468 instance hypreal :: division_by_zero
   469 proof
   470   show "inverse 0 = (0::hypreal)" 
   471     by (simp add: hypreal_inverse hypreal_zero_def)
   472 qed
   473 
   474 
   475 subsection{*Properties of The @{text "\<le>"} Relation*}
   476 
   477 lemma hypreal_le: 
   478       "(Abs_hypreal(hyprel``{%n. X n}) \<le> Abs_hypreal(hyprel``{%n. Y n})) =  
   479        ({n. X n \<le> Y n} \<in> FreeUltrafilterNat)"
   480 apply (simp add: hypreal_le_def)
   481 apply (auto intro!: lemma_hyprel_refl, ultra)
   482 done
   483 
   484 lemma hypreal_le_refl: "w \<le> (w::hypreal)"
   485 apply (cases w)
   486 apply (simp add: hypreal_le) 
   487 done
   488 
   489 lemma hypreal_le_trans: "[| i \<le> j; j \<le> k |] ==> i \<le> (k::hypreal)"
   490 apply (cases i, cases j, cases k)
   491 apply (simp add: hypreal_le, ultra)
   492 done
   493 
   494 lemma hypreal_le_anti_sym: "[| z \<le> w; w \<le> z |] ==> z = (w::hypreal)"
   495 apply (cases z, cases w)
   496 apply (simp add: hypreal_le, ultra)
   497 done
   498 
   499 (* Axiom 'order_less_le' of class 'order': *)
   500 lemma hypreal_less_le: "((w::hypreal) < z) = (w \<le> z & w \<noteq> z)"
   501 by (simp add: hypreal_less_def)
   502 
   503 instance hypreal :: order
   504 proof qed
   505  (assumption |
   506   rule hypreal_le_refl hypreal_le_trans hypreal_le_anti_sym hypreal_less_le)+
   507 
   508 
   509 (* Axiom 'linorder_linear' of class 'linorder': *)
   510 lemma hypreal_le_linear: "(z::hypreal) \<le> w | w \<le> z"
   511 apply (cases z, cases w)
   512 apply (auto simp add: hypreal_le, ultra)
   513 done
   514 
   515 instance hypreal :: linorder 
   516   by (intro_classes, rule hypreal_le_linear)
   517 
   518 lemma hypreal_not_refl2: "!!(x::hypreal). x < y ==> x \<noteq> y"
   519 by (auto simp add: order_less_irrefl)
   520 
   521 lemma hypreal_add_left_mono: "x \<le> y ==> z + x \<le> z + (y::hypreal)"
   522 apply (cases x, cases y, cases z)
   523 apply (auto simp add: hypreal_le hypreal_add) 
   524 done
   525 
   526 lemma hypreal_mult_less_mono2: "[| (0::hypreal)<z; x<y |] ==> z*x<z*y"
   527 apply (cases x, cases y, cases z)
   528 apply (auto simp add: hypreal_zero_def hypreal_le hypreal_mult 
   529                       linorder_not_le [symmetric], ultra) 
   530 done
   531 
   532 
   533 subsection{*The Hyperreals Form an Ordered Field*}
   534 
   535 instance hypreal :: ordered_field
   536 proof
   537   fix x y z :: hypreal
   538   show "x \<le> y ==> z + x \<le> z + y" 
   539     by (rule hypreal_add_left_mono)
   540   show "x < y ==> 0 < z ==> z * x < z * y" 
   541     by (simp add: hypreal_mult_less_mono2)
   542   show "\<bar>x\<bar> = (if x < 0 then -x else x)"
   543     by (auto dest: order_le_less_trans simp add: hrabs_def linorder_not_le)
   544 qed
   545 
   546 lemma hypreal_mult_1_right: "z * (1::hypreal) = z"
   547   by (rule Ring_and_Field.mult_1_right)
   548 
   549 lemma hypreal_mult_minus_1 [simp]: "(- (1::hypreal)) * z = -z"
   550 by simp
   551 
   552 lemma hypreal_mult_minus_1_right [simp]: "z * (- (1::hypreal)) = -z"
   553 by (subst hypreal_mult_commute, simp)
   554 
   555 (*Used ONCE: in NSA.ML*)
   556 lemma hypreal_minus_distrib1: "-(y + -(x::hypreal)) = x + -y"
   557 by (simp add: hypreal_add_commute)
   558 
   559 (*Used ONCE: in Lim.ML*)
   560 lemma hypreal_eq_minus_iff3: "(x = y + z) = (x + -z = (y::hypreal))"
   561 by (auto simp add: hypreal_add_assoc)
   562 
   563 lemma hypreal_eq_minus_iff: "((x::hypreal) = y) = (x + - y = 0)"
   564 apply auto
   565 apply (rule Ring_and_Field.add_right_cancel [of _ "-y", THEN iffD1], auto)
   566 done
   567 
   568 (*Used 3 TIMES: in Lim.ML*)
   569 lemma hypreal_not_eq_minus_iff: "(x \<noteq> a) = (x + -a \<noteq> (0::hypreal))"
   570 by (auto dest: hypreal_eq_minus_iff [THEN iffD2])
   571 
   572 lemma hypreal_mult_left_cancel: "(c::hypreal) \<noteq> 0 ==> (c*a=c*b) = (a=b)"
   573 by auto
   574     
   575 lemma hypreal_mult_right_cancel: "(c::hypreal) \<noteq> 0 ==> (a*c=b*c) = (a=b)"
   576 by auto
   577 
   578 lemma hypreal_mult_not_0: "[| x \<noteq> 0; y \<noteq> 0 |] ==> x * y \<noteq> (0::hypreal)"
   579 by simp
   580 
   581 lemma hypreal_minus_inverse: "inverse(-x) = -inverse(x::hypreal)"
   582   by (rule Ring_and_Field.inverse_minus_eq)
   583 
   584 lemma hypreal_inverse_distrib: "inverse(x*y) = inverse(x)*inverse(y::hypreal)"
   585   by (rule Ring_and_Field.inverse_mult_distrib)
   586 
   587 
   588 subsection{* Division lemmas *}
   589 
   590 lemma hypreal_divide_one: "x/(1::hypreal) = x"
   591 by (simp add: hypreal_divide_def)
   592 
   593 
   594 (** As with multiplication, pull minus signs OUT of the / operator **)
   595 
   596 lemma hypreal_add_divide_distrib: "(x+y)/(z::hypreal) = x/z + y/z"
   597   by (rule Ring_and_Field.add_divide_distrib)
   598 
   599 lemma hypreal_inverse_add:
   600      "[|(x::hypreal) \<noteq> 0;  y \<noteq> 0 |]   
   601       ==> inverse(x) + inverse(y) = (x + y)*inverse(x*y)"
   602 by (simp add: Ring_and_Field.inverse_add mult_assoc)
   603 
   604 
   605 subsection{*The Embedding @{term hypreal_of_real} Preserves Field and 
   606       Order Properties*}
   607 
   608 lemma hypreal_of_real_add [simp]: 
   609      "hypreal_of_real (w + z) = hypreal_of_real w + hypreal_of_real z"
   610 apply (simp add: hypreal_of_real_def)
   611 apply (simp add: hypreal_add left_distrib)
   612 done
   613 
   614 lemma hypreal_of_real_mult [simp]: 
   615      "hypreal_of_real (w * z) = hypreal_of_real w * hypreal_of_real z"
   616 apply (simp add: hypreal_of_real_def)
   617 apply (simp add: hypreal_mult right_distrib)
   618 done
   619 
   620 lemma hypreal_of_real_one [simp]: "hypreal_of_real 1 = (1::hypreal)"
   621 by (simp add: hypreal_of_real_def hypreal_one_def)
   622 
   623 lemma hypreal_of_real_zero [simp]: "hypreal_of_real 0 = 0"
   624 by (simp add: hypreal_of_real_def hypreal_zero_def)
   625 
   626 lemma hypreal_of_real_le_iff [simp]: 
   627      "(hypreal_of_real w \<le> hypreal_of_real z) = (w \<le> z)"
   628 apply (simp add: hypreal_le_def hypreal_of_real_def, auto)
   629 apply (rule_tac [2] x = "%n. w" in exI, safe)
   630 apply (rule_tac [3] x = "%n. z" in exI, auto)
   631 apply (rule FreeUltrafilterNat_P, ultra)
   632 done
   633 
   634 lemma hypreal_of_real_less_iff [simp]: 
   635      "(hypreal_of_real w < hypreal_of_real z) = (w < z)"
   636 by (simp add: linorder_not_le [symmetric]) 
   637 
   638 lemma hypreal_of_real_eq_iff [simp]:
   639      "(hypreal_of_real w = hypreal_of_real z) = (w = z)"
   640 by (force intro: order_antisym hypreal_of_real_le_iff [THEN iffD1])
   641 
   642 text{*As above, for 0*}
   643 
   644 declare hypreal_of_real_less_iff [of 0, simplified, simp]
   645 declare hypreal_of_real_le_iff   [of 0, simplified, simp]
   646 declare hypreal_of_real_eq_iff   [of 0, simplified, simp]
   647 
   648 declare hypreal_of_real_less_iff [of _ 0, simplified, simp]
   649 declare hypreal_of_real_le_iff   [of _ 0, simplified, simp]
   650 declare hypreal_of_real_eq_iff   [of _ 0, simplified, simp]
   651 
   652 text{*As above, for 1*}
   653 
   654 declare hypreal_of_real_less_iff [of 1, simplified, simp]
   655 declare hypreal_of_real_le_iff   [of 1, simplified, simp]
   656 declare hypreal_of_real_eq_iff   [of 1, simplified, simp]
   657 
   658 declare hypreal_of_real_less_iff [of _ 1, simplified, simp]
   659 declare hypreal_of_real_le_iff   [of _ 1, simplified, simp]
   660 declare hypreal_of_real_eq_iff   [of _ 1, simplified, simp]
   661 
   662 lemma hypreal_of_real_minus [simp]:
   663      "hypreal_of_real (-r) = - hypreal_of_real  r"
   664 by (auto simp add: hypreal_of_real_def hypreal_minus)
   665 
   666 lemma hypreal_of_real_inverse [simp]:
   667      "hypreal_of_real (inverse r) = inverse (hypreal_of_real r)"
   668 apply (case_tac "r=0", simp)
   669 apply (rule_tac c1 = "hypreal_of_real r" in hypreal_mult_left_cancel [THEN iffD1])
   670 apply (auto simp add: hypreal_of_real_mult [symmetric])
   671 done
   672 
   673 lemma hypreal_of_real_divide [simp]:
   674      "hypreal_of_real (w / z) = hypreal_of_real w / hypreal_of_real z"
   675 by (simp add: hypreal_divide_def real_divide_def)
   676 
   677 
   678 subsection{*Misc Others*}
   679 
   680 lemma hypreal_less: 
   681       "(Abs_hypreal(hyprel``{%n. X n}) < Abs_hypreal(hyprel``{%n. Y n})) =  
   682        ({n. X n < Y n} \<in> FreeUltrafilterNat)"
   683 apply (auto simp add: hypreal_le linorder_not_le [symmetric], ultra+)
   684 done
   685 
   686 lemma hypreal_zero_num: "0 = Abs_hypreal (hyprel `` {%n. 0})"
   687 by (simp add: hypreal_zero_def [THEN meta_eq_to_obj_eq, symmetric])
   688 
   689 lemma hypreal_one_num: "1 = Abs_hypreal (hyprel `` {%n. 1})"
   690 by (simp add: hypreal_one_def [THEN meta_eq_to_obj_eq, symmetric])
   691 
   692 lemma hypreal_omega_gt_zero [simp]: "0 < omega"
   693 apply (simp add: omega_def)
   694 apply (auto simp add: hypreal_less hypreal_zero_num)
   695 done
   696 
   697 lemma hypreal_hrabs:
   698      "abs (Abs_hypreal (hyprel `` {X})) = 
   699       Abs_hypreal(hyprel `` {%n. abs (X n)})"
   700 apply (auto simp add: hrabs_def hypreal_zero_def hypreal_le hypreal_minus)
   701 apply (ultra, arith)+
   702 done
   703 
   704 
   705 
   706 lemma hypreal_add_zero_less_le_mono: "[|r < x; (0::hypreal) \<le> y|] ==> r < x+y"
   707 by (auto dest: add_less_le_mono)
   708 
   709 text{*The precondition could be weakened to @{term "0\<le>x"}*}
   710 lemma hypreal_mult_less_mono:
   711      "[| u<v;  x<y;  (0::hypreal) < v;  0 < x |] ==> u*x < v* y"
   712  by (simp add: Ring_and_Field.mult_strict_mono order_less_imp_le)
   713 
   714 
   715 subsection{*Existence of Infinite Hyperreal Number*}
   716 
   717 lemma Rep_hypreal_omega: "Rep_hypreal(omega) \<in> hypreal"
   718 by (simp add: omega_def)
   719 
   720 text{*Existence of infinite number not corresponding to any real number.
   721 Use assumption that member @{term FreeUltrafilterNat} is not finite.*}
   722 
   723 
   724 text{*A few lemmas first*}
   725 
   726 lemma lemma_omega_empty_singleton_disj: "{n::nat. x = real n} = {} |  
   727       (\<exists>y. {n::nat. x = real n} = {y})"
   728 by force
   729 
   730 lemma lemma_finite_omega_set: "finite {n::nat. x = real n}"
   731 by (cut_tac x = x in lemma_omega_empty_singleton_disj, auto)
   732 
   733 lemma not_ex_hypreal_of_real_eq_omega: 
   734       "~ (\<exists>x. hypreal_of_real x = omega)"
   735 apply (simp add: omega_def hypreal_of_real_def)
   736 apply (auto simp add: real_of_nat_Suc diff_eq_eq [symmetric] 
   737             lemma_finite_omega_set [THEN FreeUltrafilterNat_finite])
   738 done
   739 
   740 lemma hypreal_of_real_not_eq_omega: "hypreal_of_real x \<noteq> omega"
   741 by (cut_tac not_ex_hypreal_of_real_eq_omega, auto)
   742 
   743 text{*Existence of infinitesimal number also not corresponding to any
   744  real number*}
   745 
   746 lemma lemma_epsilon_empty_singleton_disj:
   747      "{n::nat. x = inverse(real(Suc n))} = {} |  
   748       (\<exists>y. {n::nat. x = inverse(real(Suc n))} = {y})"
   749 by auto
   750 
   751 lemma lemma_finite_epsilon_set: "finite {n. x = inverse(real(Suc n))}"
   752 by (cut_tac x = x in lemma_epsilon_empty_singleton_disj, auto)
   753 
   754 lemma not_ex_hypreal_of_real_eq_epsilon: 
   755       "~ (\<exists>x. hypreal_of_real x = epsilon)"
   756 apply (simp add: epsilon_def hypreal_of_real_def)
   757 apply (auto simp add: lemma_finite_epsilon_set [THEN FreeUltrafilterNat_finite])
   758 done
   759 
   760 lemma hypreal_of_real_not_eq_epsilon: "hypreal_of_real x \<noteq> epsilon"
   761 by (cut_tac not_ex_hypreal_of_real_eq_epsilon, auto)
   762 
   763 lemma hypreal_epsilon_not_zero: "epsilon \<noteq> 0"
   764 by (simp add: epsilon_def hypreal_zero_def)
   765 
   766 lemma hypreal_epsilon_inverse_omega: "epsilon = inverse(omega)"
   767 by (simp add: hypreal_inverse omega_def epsilon_def)
   768 
   769 
   770 ML
   771 {*
   772 val hrabs_def = thm "hrabs_def";
   773 val hypreal_hrabs = thm "hypreal_hrabs";
   774 
   775 val hypreal_zero_def = thm "hypreal_zero_def";
   776 val hypreal_one_def = thm "hypreal_one_def";
   777 val hypreal_minus_def = thm "hypreal_minus_def";
   778 val hypreal_diff_def = thm "hypreal_diff_def";
   779 val hypreal_inverse_def = thm "hypreal_inverse_def";
   780 val hypreal_divide_def = thm "hypreal_divide_def";
   781 val hypreal_of_real_def = thm "hypreal_of_real_def";
   782 val omega_def = thm "omega_def";
   783 val epsilon_def = thm "epsilon_def";
   784 val hypreal_add_def = thm "hypreal_add_def";
   785 val hypreal_mult_def = thm "hypreal_mult_def";
   786 val hypreal_less_def = thm "hypreal_less_def";
   787 val hypreal_le_def = thm "hypreal_le_def";
   788 
   789 val finite_exhausts = thm "finite_exhausts";
   790 val finite_not_covers = thm "finite_not_covers";
   791 val not_finite_nat = thm "not_finite_nat";
   792 val FreeUltrafilterNat_Ex = thm "FreeUltrafilterNat_Ex";
   793 val FreeUltrafilterNat_mem = thm "FreeUltrafilterNat_mem";
   794 val FreeUltrafilterNat_finite = thm "FreeUltrafilterNat_finite";
   795 val FreeUltrafilterNat_not_finite = thm "FreeUltrafilterNat_not_finite";
   796 val FreeUltrafilterNat_empty = thm "FreeUltrafilterNat_empty";
   797 val FreeUltrafilterNat_Int = thm "FreeUltrafilterNat_Int";
   798 val FreeUltrafilterNat_subset = thm "FreeUltrafilterNat_subset";
   799 val FreeUltrafilterNat_Compl = thm "FreeUltrafilterNat_Compl";
   800 val FreeUltrafilterNat_Compl_mem = thm "FreeUltrafilterNat_Compl_mem";
   801 val FreeUltrafilterNat_Compl_iff1 = thm "FreeUltrafilterNat_Compl_iff1";
   802 val FreeUltrafilterNat_Compl_iff2 = thm "FreeUltrafilterNat_Compl_iff2";
   803 val FreeUltrafilterNat_UNIV = thm "FreeUltrafilterNat_UNIV";
   804 val FreeUltrafilterNat_Nat_set = thm "FreeUltrafilterNat_Nat_set";
   805 val FreeUltrafilterNat_Nat_set_refl = thm "FreeUltrafilterNat_Nat_set_refl";
   806 val FreeUltrafilterNat_P = thm "FreeUltrafilterNat_P";
   807 val FreeUltrafilterNat_Ex_P = thm "FreeUltrafilterNat_Ex_P";
   808 val FreeUltrafilterNat_all = thm "FreeUltrafilterNat_all";
   809 val FreeUltrafilterNat_Un = thm "FreeUltrafilterNat_Un";
   810 val hyprel_iff = thm "hyprel_iff";
   811 val hyprel_refl = thm "hyprel_refl";
   812 val hyprel_sym = thm "hyprel_sym";
   813 val hyprel_trans = thm "hyprel_trans";
   814 val equiv_hyprel = thm "equiv_hyprel";
   815 val hyprel_in_hypreal = thm "hyprel_in_hypreal";
   816 val Abs_hypreal_inverse = thm "Abs_hypreal_inverse";
   817 val inj_on_Abs_hypreal = thm "inj_on_Abs_hypreal";
   818 val inj_Rep_hypreal = thm "inj_Rep_hypreal";
   819 val lemma_hyprel_refl = thm "lemma_hyprel_refl";
   820 val hypreal_empty_not_mem = thm "hypreal_empty_not_mem";
   821 val Rep_hypreal_nonempty = thm "Rep_hypreal_nonempty";
   822 val inj_hypreal_of_real = thm "inj_hypreal_of_real";
   823 val eq_Abs_hypreal = thm "eq_Abs_hypreal";
   824 val hypreal_minus_congruent = thm "hypreal_minus_congruent";
   825 val hypreal_minus = thm "hypreal_minus";
   826 val hypreal_add_congruent2 = thm "hypreal_add_congruent2";
   827 val hypreal_add = thm "hypreal_add";
   828 val hypreal_diff = thm "hypreal_diff";
   829 val hypreal_add_commute = thm "hypreal_add_commute";
   830 val hypreal_add_assoc = thm "hypreal_add_assoc";
   831 val hypreal_add_zero_left = thm "hypreal_add_zero_left";
   832 val hypreal_add_zero_right = thm "hypreal_add_zero_right";
   833 val hypreal_add_minus = thm "hypreal_add_minus";
   834 val hypreal_add_minus_left = thm "hypreal_add_minus_left";
   835 val hypreal_minus_distrib1 = thm "hypreal_minus_distrib1";
   836 val hypreal_mult_congruent2 = thm "hypreal_mult_congruent2";
   837 val hypreal_mult = thm "hypreal_mult";
   838 val hypreal_mult_commute = thm "hypreal_mult_commute";
   839 val hypreal_mult_assoc = thm "hypreal_mult_assoc";
   840 val hypreal_mult_1 = thm "hypreal_mult_1";
   841 val hypreal_mult_1_right = thm "hypreal_mult_1_right";
   842 val hypreal_mult_minus_1 = thm "hypreal_mult_minus_1";
   843 val hypreal_mult_minus_1_right = thm "hypreal_mult_minus_1_right";
   844 val hypreal_zero_not_eq_one = thm "hypreal_zero_not_eq_one";
   845 val hypreal_inverse_congruent = thm "hypreal_inverse_congruent";
   846 val hypreal_inverse = thm "hypreal_inverse";
   847 val hypreal_mult_inverse = thm "hypreal_mult_inverse";
   848 val hypreal_mult_inverse_left = thm "hypreal_mult_inverse_left";
   849 val hypreal_mult_left_cancel = thm "hypreal_mult_left_cancel";
   850 val hypreal_mult_right_cancel = thm "hypreal_mult_right_cancel";
   851 val hypreal_mult_not_0 = thm "hypreal_mult_not_0";
   852 val hypreal_minus_inverse = thm "hypreal_minus_inverse";
   853 val hypreal_inverse_distrib = thm "hypreal_inverse_distrib";
   854 val hypreal_not_refl2 = thm "hypreal_not_refl2";
   855 val hypreal_less = thm "hypreal_less";
   856 val hypreal_eq_minus_iff = thm "hypreal_eq_minus_iff";
   857 val hypreal_eq_minus_iff3 = thm "hypreal_eq_minus_iff3";
   858 val hypreal_not_eq_minus_iff = thm "hypreal_not_eq_minus_iff";
   859 val hypreal_le = thm "hypreal_le";
   860 val hypreal_le_refl = thm "hypreal_le_refl";
   861 val hypreal_le_linear = thm "hypreal_le_linear";
   862 val hypreal_le_trans = thm "hypreal_le_trans";
   863 val hypreal_le_anti_sym = thm "hypreal_le_anti_sym";
   864 val hypreal_less_le = thm "hypreal_less_le";
   865 val hypreal_of_real_add = thm "hypreal_of_real_add";
   866 val hypreal_of_real_mult = thm "hypreal_of_real_mult";
   867 val hypreal_of_real_less_iff = thm "hypreal_of_real_less_iff";
   868 val hypreal_of_real_le_iff = thm "hypreal_of_real_le_iff";
   869 val hypreal_of_real_eq_iff = thm "hypreal_of_real_eq_iff";
   870 val hypreal_of_real_minus = thm "hypreal_of_real_minus";
   871 val hypreal_of_real_one = thm "hypreal_of_real_one";
   872 val hypreal_of_real_zero = thm "hypreal_of_real_zero";
   873 val hypreal_of_real_inverse = thm "hypreal_of_real_inverse";
   874 val hypreal_of_real_divide = thm "hypreal_of_real_divide";
   875 val hypreal_divide_one = thm "hypreal_divide_one";
   876 val hypreal_add_divide_distrib = thm "hypreal_add_divide_distrib";
   877 val hypreal_inverse_add = thm "hypreal_inverse_add";
   878 val hypreal_zero_num = thm "hypreal_zero_num";
   879 val hypreal_one_num = thm "hypreal_one_num";
   880 val hypreal_omega_gt_zero = thm "hypreal_omega_gt_zero";
   881 
   882 val hypreal_add_zero_less_le_mono = thm"hypreal_add_zero_less_le_mono";
   883 val Rep_hypreal_omega = thm"Rep_hypreal_omega";
   884 val lemma_omega_empty_singleton_disj = thm"lemma_omega_empty_singleton_disj";
   885 val lemma_finite_omega_set = thm"lemma_finite_omega_set";
   886 val not_ex_hypreal_of_real_eq_omega = thm"not_ex_hypreal_of_real_eq_omega";
   887 val hypreal_of_real_not_eq_omega = thm"hypreal_of_real_not_eq_omega";
   888 val not_ex_hypreal_of_real_eq_epsilon = thm"not_ex_hypreal_of_real_eq_epsilon";
   889 val hypreal_of_real_not_eq_epsilon = thm"hypreal_of_real_not_eq_epsilon";
   890 val hypreal_epsilon_not_zero = thm"hypreal_epsilon_not_zero";
   891 val hypreal_epsilon_inverse_omega = thm"hypreal_epsilon_inverse_omega";
   892 *}
   893 
   894 end