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