src/HOL/SupInf.thy
 author haftmann Thu Mar 18 13:56:34 2010 +0100 (2010-03-18) changeset 35823 bd26885af9f4 parent 35581 a25e51e2d64d child 36007 095b1022e2ae permissions -rw-r--r--
dropped odd interpretation of comm_monoid_mult into comm_monoid_add
```     1 (*  Author: Amine Chaieb and L C Paulson, University of Cambridge *)
```
```     2
```
```     3 header {*Sup and Inf Operators on Sets of Reals.*}
```
```     4
```
```     5 theory SupInf
```
```     6 imports RComplete
```
```     7 begin
```
```     8
```
```     9 instantiation real :: Sup
```
```    10 begin
```
```    11 definition
```
```    12   Sup_real_def [code del]: "Sup X == (LEAST z::real. \<forall>x\<in>X. x\<le>z)"
```
```    13
```
```    14 instance ..
```
```    15 end
```
```    16
```
```    17 instantiation real :: Inf
```
```    18 begin
```
```    19 definition
```
```    20   Inf_real_def [code del]: "Inf (X::real set) == - (Sup (uminus ` X))"
```
```    21
```
```    22 instance ..
```
```    23 end
```
```    24
```
```    25 subsection{*Supremum of a set of reals*}
```
```    26
```
```    27 lemma Sup_upper [intro]: (*REAL_SUP_UBOUND in HOL4*)
```
```    28   fixes x :: real
```
```    29   assumes x: "x \<in> X"
```
```    30       and z: "!!x. x \<in> X \<Longrightarrow> x \<le> z"
```
```    31   shows "x \<le> Sup X"
```
```    32 proof (auto simp add: Sup_real_def)
```
```    33   from reals_complete2
```
```    34   obtain s where s: "(\<forall>y\<in>X. y \<le> s) & (\<forall>z. ((\<forall>y\<in>X. y \<le> z) --> s \<le> z))"
```
```    35     by (blast intro: x z)
```
```    36   hence "x \<le> s"
```
```    37     by (blast intro: x z)
```
```    38   also with s have "... = (LEAST z. \<forall>x\<in>X. x \<le> z)"
```
```    39     by (fast intro: Least_equality [symmetric])
```
```    40   finally show "x \<le> (LEAST z. \<forall>x\<in>X. x \<le> z)" .
```
```    41 qed
```
```    42
```
```    43 lemma Sup_least [intro]: (*REAL_IMP_SUP_LE in HOL4*)
```
```    44   fixes z :: real
```
```    45   assumes x: "X \<noteq> {}"
```
```    46       and z: "\<And>x. x \<in> X \<Longrightarrow> x \<le> z"
```
```    47   shows "Sup X \<le> z"
```
```    48 proof (auto simp add: Sup_real_def)
```
```    49   from reals_complete2 x
```
```    50   obtain s where s: "(\<forall>y\<in>X. y \<le> s) & (\<forall>z. ((\<forall>y\<in>X. y \<le> z) --> s \<le> z))"
```
```    51     by (blast intro: z)
```
```    52   hence "(LEAST z. \<forall>x\<in>X. x \<le> z) = s"
```
```    53     by (best intro: Least_equality)
```
```    54   also with s z have "... \<le> z"
```
```    55     by blast
```
```    56   finally show "(LEAST z. \<forall>x\<in>X. x \<le> z) \<le> z" .
```
```    57 qed
```
```    58
```
```    59 lemma less_SupE:
```
```    60   fixes y :: real
```
```    61   assumes "y < Sup X" "X \<noteq> {}"
```
```    62   obtains x where "x\<in>X" "y < x"
```
```    63 by (metis SupInf.Sup_least assms linorder_not_less that)
```
```    64
```
```    65 lemma Sup_singleton [simp]: "Sup {x::real} = x"
```
```    66   by (force intro: Least_equality simp add: Sup_real_def)
```
```    67
```
```    68 lemma Sup_eq_maximum: (*REAL_SUP_MAX in HOL4*)
```
```    69   fixes z :: real
```
```    70   assumes X: "z \<in> X" and z: "!!x. x \<in> X \<Longrightarrow> x \<le> z"
```
```    71   shows  "Sup X = z"
```
```    72   by (force intro: Least_equality X z simp add: Sup_real_def)
```
```    73
```
```    74 lemma Sup_upper2: (*REAL_IMP_LE_SUP in HOL4*)
```
```    75   fixes x :: real
```
```    76   shows "x \<in> X \<Longrightarrow> y \<le> x \<Longrightarrow> (!!x. x \<in> X \<Longrightarrow> x \<le> z) \<Longrightarrow> y \<le> Sup X"
```
```    77   by (metis Sup_upper real_le_trans)
```
```    78
```
```    79 lemma Sup_real_iff : (*REAL_SUP_LE in HOL4*)
```
```    80   fixes z :: real
```
```    81   shows "X ~= {} ==> (!!x. x \<in> X ==> x \<le> z) ==> (\<exists>x\<in>X. y<x) <-> y < Sup X"
```
```    82   by (metis Sup_least Sup_upper linorder_not_le le_less_trans)
```
```    83
```
```    84 lemma Sup_eq:
```
```    85   fixes a :: real
```
```    86   shows "(!!x. x \<in> X \<Longrightarrow> x \<le> a)
```
```    87         \<Longrightarrow> (!!y. (!!x. x \<in> X \<Longrightarrow> x \<le> y) \<Longrightarrow> a \<le> y) \<Longrightarrow> Sup X = a"
```
```    88   by (metis Sup_least Sup_upper add_le_cancel_left diff_add_cancel insert_absorb
```
```    89         insert_not_empty real_le_antisym)
```
```    90
```
```    91 lemma Sup_le:
```
```    92   fixes S :: "real set"
```
```    93   shows "S \<noteq> {} \<Longrightarrow> S *<= b \<Longrightarrow> Sup S \<le> b"
```
```    94 by (metis SupInf.Sup_least setle_def)
```
```    95
```
```    96 lemma Sup_upper_EX:
```
```    97   fixes x :: real
```
```    98   shows "x \<in> X \<Longrightarrow> \<exists>z. \<forall>x. x \<in> X \<longrightarrow> x \<le> z \<Longrightarrow>  x \<le> Sup X"
```
```    99   by blast
```
```   100
```
```   101 lemma Sup_insert_nonempty:
```
```   102   fixes x :: real
```
```   103   assumes x: "x \<in> X"
```
```   104       and z: "!!x. x \<in> X \<Longrightarrow> x \<le> z"
```
```   105   shows "Sup (insert a X) = max a (Sup X)"
```
```   106 proof (cases "Sup X \<le> a")
```
```   107   case True
```
```   108   thus ?thesis
```
```   109     apply (simp add: max_def)
```
```   110     apply (rule Sup_eq_maximum)
```
```   111     apply (metis insertCI)
```
```   112     apply (metis Sup_upper insertE le_iff_sup real_le_linear real_le_trans sup_absorb1 z)
```
```   113     done
```
```   114 next
```
```   115   case False
```
```   116   hence 1:"a < Sup X" by simp
```
```   117   have "Sup X \<le> Sup (insert a X)"
```
```   118     apply (rule Sup_least)
```
```   119     apply (metis empty_psubset_nonempty psubset_eq x)
```
```   120     apply (rule Sup_upper_EX)
```
```   121     apply blast
```
```   122     apply (metis insert_iff real_le_linear real_le_refl real_le_trans z)
```
```   123     done
```
```   124   moreover
```
```   125   have "Sup (insert a X) \<le> Sup X"
```
```   126     apply (rule Sup_least)
```
```   127     apply blast
```
```   128     apply (metis False Sup_upper insertE real_le_linear z)
```
```   129     done
```
```   130   ultimately have "Sup (insert a X) = Sup X"
```
```   131     by (blast intro:  antisym )
```
```   132   thus ?thesis
```
```   133     by (metis 1 min_max.le_iff_sup real_less_def)
```
```   134 qed
```
```   135
```
```   136 lemma Sup_insert_if:
```
```   137   fixes X :: "real set"
```
```   138   assumes z: "!!x. x \<in> X \<Longrightarrow> x \<le> z"
```
```   139   shows "Sup (insert a X) = (if X={} then a else max a (Sup X))"
```
```   140 by auto (metis Sup_insert_nonempty z)
```
```   141
```
```   142 lemma Sup:
```
```   143   fixes S :: "real set"
```
```   144   shows "S \<noteq> {} \<Longrightarrow> (\<exists>b. S *<= b) \<Longrightarrow> isLub UNIV S (Sup S)"
```
```   145 by  (auto simp add: isLub_def setle_def leastP_def isUb_def intro!: setgeI)
```
```   146
```
```   147 lemma Sup_finite_Max:
```
```   148   fixes S :: "real set"
```
```   149   assumes fS: "finite S" and Se: "S \<noteq> {}"
```
```   150   shows "Sup S = Max S"
```
```   151 using fS Se
```
```   152 proof-
```
```   153   let ?m = "Max S"
```
```   154   from Max_ge[OF fS] have Sm: "\<forall> x\<in> S. x \<le> ?m" by metis
```
```   155   with Sup[OF Se] have lub: "isLub UNIV S (Sup S)" by (metis setle_def)
```
```   156   from Max_in[OF fS Se] lub have mrS: "?m \<le> Sup S"
```
```   157     by (auto simp add: isLub_def leastP_def setle_def setge_def isUb_def)
```
```   158   moreover
```
```   159   have "Sup S \<le> ?m" using Sm lub
```
```   160     by (auto simp add: isLub_def leastP_def isUb_def setle_def setge_def)
```
```   161   ultimately  show ?thesis by arith
```
```   162 qed
```
```   163
```
```   164 lemma Sup_finite_in:
```
```   165   fixes S :: "real set"
```
```   166   assumes fS: "finite S" and Se: "S \<noteq> {}"
```
```   167   shows "Sup S \<in> S"
```
```   168   using Sup_finite_Max[OF fS Se] Max_in[OF fS Se] by metis
```
```   169
```
```   170 lemma Sup_finite_ge_iff:
```
```   171   fixes S :: "real set"
```
```   172   assumes fS: "finite S" and Se: "S \<noteq> {}"
```
```   173   shows "a \<le> Sup S \<longleftrightarrow> (\<exists> x \<in> S. a \<le> x)"
```
```   174 by (metis Max_ge Se Sup_finite_Max Sup_finite_in fS linorder_not_le less_le_trans)
```
```   175
```
```   176 lemma Sup_finite_le_iff:
```
```   177   fixes S :: "real set"
```
```   178   assumes fS: "finite S" and Se: "S \<noteq> {}"
```
```   179   shows "a \<ge> Sup S \<longleftrightarrow> (\<forall> x \<in> S. a \<ge> x)"
```
```   180 by (metis Max_ge Se Sup_finite_Max Sup_finite_in fS le_iff_sup real_le_trans)
```
```   181
```
```   182 lemma Sup_finite_gt_iff:
```
```   183   fixes S :: "real set"
```
```   184   assumes fS: "finite S" and Se: "S \<noteq> {}"
```
```   185   shows "a < Sup S \<longleftrightarrow> (\<exists> x \<in> S. a < x)"
```
```   186 by (metis Se Sup_finite_le_iff fS linorder_not_less)
```
```   187
```
```   188 lemma Sup_finite_lt_iff:
```
```   189   fixes S :: "real set"
```
```   190   assumes fS: "finite S" and Se: "S \<noteq> {}"
```
```   191   shows "a > Sup S \<longleftrightarrow> (\<forall> x \<in> S. a > x)"
```
```   192 by (metis Se Sup_finite_ge_iff fS linorder_not_less)
```
```   193
```
```   194 lemma Sup_unique:
```
```   195   fixes S :: "real set"
```
```   196   shows "S *<= b \<Longrightarrow> (\<forall>b' < b. \<exists>x \<in> S. b' < x) \<Longrightarrow> Sup S = b"
```
```   197 unfolding setle_def
```
```   198 apply (rule Sup_eq, auto)
```
```   199 apply (metis linorder_not_less)
```
```   200 done
```
```   201
```
```   202 lemma Sup_abs_le:
```
```   203   fixes S :: "real set"
```
```   204   shows "S \<noteq> {} \<Longrightarrow> (\<forall>x\<in>S. \<bar>x\<bar> \<le> a) \<Longrightarrow> \<bar>Sup S\<bar> \<le> a"
```
```   205 by (auto simp add: abs_le_interval_iff) (metis Sup_upper2)
```
```   206
```
```   207 lemma Sup_bounds:
```
```   208   fixes S :: "real set"
```
```   209   assumes Se: "S \<noteq> {}" and l: "a <=* S" and u: "S *<= b"
```
```   210   shows "a \<le> Sup S \<and> Sup S \<le> b"
```
```   211 proof-
```
```   212   from Sup[OF Se] u have lub: "isLub UNIV S (Sup S)" by blast
```
```   213   hence b: "Sup S \<le> b" using u
```
```   214     by (auto simp add: isLub_def leastP_def setle_def setge_def isUb_def)
```
```   215   from Se obtain y where y: "y \<in> S" by blast
```
```   216   from lub l have "a \<le> Sup S"
```
```   217     by (auto simp add: isLub_def leastP_def setle_def setge_def isUb_def)
```
```   218        (metis le_iff_sup le_sup_iff y)
```
```   219   with b show ?thesis by blast
```
```   220 qed
```
```   221
```
```   222 lemma Sup_asclose:
```
```   223   fixes S :: "real set"
```
```   224   assumes S:"S \<noteq> {}" and b: "\<forall>x\<in>S. \<bar>x - l\<bar> \<le> e" shows "\<bar>Sup S - l\<bar> \<le> e"
```
```   225 proof-
```
```   226   have th: "\<And>(x::real) l e. \<bar>x - l\<bar> \<le> e \<longleftrightarrow> l - e \<le> x \<and> x \<le> l + e" by arith
```
```   227   thus ?thesis using S b Sup_bounds[of S "l - e" "l+e"] unfolding th
```
```   228     by  (auto simp add: setge_def setle_def)
```
```   229 qed
```
```   230
```
```   231 lemma Sup_lessThan[simp]: "Sup {..<x} = (x::real)"
```
```   232   by (auto intro!: Sup_eq intro: dense_le)
```
```   233
```
```   234 lemma Sup_greaterThanLessThan[simp]: "y < x \<Longrightarrow> Sup {y<..<x} = (x::real)"
```
```   235   by (auto intro!: Sup_eq intro: dense_le_bounded)
```
```   236
```
```   237 lemma Sup_atLeastLessThan[simp]: "y < x \<Longrightarrow> Sup {y..<x} = (x::real)"
```
```   238   by (auto intro!: Sup_eq intro: dense_le_bounded)
```
```   239
```
```   240 lemma Sup_atMost[simp]: "Sup {..x} = (x::real)"
```
```   241   by (auto intro!: Sup_eq_maximum)
```
```   242
```
```   243 lemma Sup_greaterThanAtMost[simp]: "y < x \<Longrightarrow> Sup {y<..x} = (x::real)"
```
```   244   by (auto intro!: Sup_eq_maximum)
```
```   245
```
```   246 lemma Sup_atLeastAtMost[simp]: "y \<le> x \<Longrightarrow> Sup {y..x} = (x::real)"
```
```   247   by (auto intro!: Sup_eq_maximum)
```
```   248
```
```   249
```
```   250 subsection{*Infimum of a set of reals*}
```
```   251
```
```   252 lemma Inf_lower [intro]:
```
```   253   fixes z :: real
```
```   254   assumes x: "x \<in> X"
```
```   255       and z: "!!x. x \<in> X \<Longrightarrow> z \<le> x"
```
```   256   shows "Inf X \<le> x"
```
```   257 proof -
```
```   258   have "-x \<le> Sup (uminus ` X)"
```
```   259     by (rule Sup_upper [where z = "-z"]) (auto simp add: image_iff x z)
```
```   260   thus ?thesis
```
```   261     by (auto simp add: Inf_real_def)
```
```   262 qed
```
```   263
```
```   264 lemma Inf_greatest [intro]:
```
```   265   fixes z :: real
```
```   266   assumes x: "X \<noteq> {}"
```
```   267       and z: "\<And>x. x \<in> X \<Longrightarrow> z \<le> x"
```
```   268   shows "z \<le> Inf X"
```
```   269 proof -
```
```   270   have "Sup (uminus ` X) \<le> -z" using x z by force
```
```   271   hence "z \<le> - Sup (uminus ` X)"
```
```   272     by simp
```
```   273   thus ?thesis
```
```   274     by (auto simp add: Inf_real_def)
```
```   275 qed
```
```   276
```
```   277 lemma Inf_singleton [simp]: "Inf {x::real} = x"
```
```   278   by (simp add: Inf_real_def)
```
```   279
```
```   280 lemma Inf_eq_minimum: (*REAL_INF_MIN in HOL4*)
```
```   281   fixes z :: real
```
```   282   assumes x: "z \<in> X" and z: "!!x. x \<in> X \<Longrightarrow> z \<le> x"
```
```   283   shows  "Inf X = z"
```
```   284 proof -
```
```   285   have "Sup (uminus ` X) = -z" using x z
```
```   286     by (force intro: Sup_eq_maximum x z)
```
```   287   thus ?thesis
```
```   288     by (simp add: Inf_real_def)
```
```   289 qed
```
```   290
```
```   291 lemma Inf_lower2:
```
```   292   fixes x :: real
```
```   293   shows "x \<in> X \<Longrightarrow> x \<le> y \<Longrightarrow> (!!x. x \<in> X \<Longrightarrow> z \<le> x) \<Longrightarrow> Inf X \<le> y"
```
```   294   by (metis Inf_lower real_le_trans)
```
```   295
```
```   296 lemma Inf_real_iff:
```
```   297   fixes z :: real
```
```   298   shows "X \<noteq> {} \<Longrightarrow> (!!x. x \<in> X \<Longrightarrow> z \<le> x) \<Longrightarrow> (\<exists>x\<in>X. x<y) \<longleftrightarrow> Inf X < y"
```
```   299   by (metis Inf_greatest Inf_lower less_le_not_le real_le_linear
```
```   300             order_less_le_trans)
```
```   301
```
```   302 lemma Inf_eq:
```
```   303   fixes a :: real
```
```   304   shows "(!!x. x \<in> X \<Longrightarrow> a \<le> x) \<Longrightarrow> (!!y. (!!x. x \<in> X \<Longrightarrow> y \<le> x) \<Longrightarrow> y \<le> a) \<Longrightarrow> Inf X = a"
```
```   305   by (metis Inf_greatest Inf_lower add_le_cancel_left diff_add_cancel
```
```   306         insert_absorb insert_not_empty real_le_antisym)
```
```   307
```
```   308 lemma Inf_ge:
```
```   309   fixes S :: "real set"
```
```   310   shows "S \<noteq> {} \<Longrightarrow> b <=* S \<Longrightarrow> Inf S \<ge> b"
```
```   311 by (metis SupInf.Inf_greatest setge_def)
```
```   312
```
```   313 lemma Inf_lower_EX:
```
```   314   fixes x :: real
```
```   315   shows "x \<in> X \<Longrightarrow> \<exists>z. \<forall>x. x \<in> X \<longrightarrow> z \<le> x \<Longrightarrow> Inf X \<le> x"
```
```   316   by blast
```
```   317
```
```   318 lemma Inf_insert_nonempty:
```
```   319   fixes x :: real
```
```   320   assumes x: "x \<in> X"
```
```   321       and z: "!!x. x \<in> X \<Longrightarrow> z \<le> x"
```
```   322   shows "Inf (insert a X) = min a (Inf X)"
```
```   323 proof (cases "a \<le> Inf X")
```
```   324   case True
```
```   325   thus ?thesis
```
```   326     by (simp add: min_def)
```
```   327        (blast intro: Inf_eq_minimum real_le_refl real_le_trans z)
```
```   328 next
```
```   329   case False
```
```   330   hence 1:"Inf X < a" by simp
```
```   331   have "Inf (insert a X) \<le> Inf X"
```
```   332     apply (rule Inf_greatest)
```
```   333     apply (metis empty_psubset_nonempty psubset_eq x)
```
```   334     apply (rule Inf_lower_EX)
```
```   335     apply (blast intro: elim:)
```
```   336     apply (metis insert_iff real_le_linear real_le_refl real_le_trans z)
```
```   337     done
```
```   338   moreover
```
```   339   have "Inf X \<le> Inf (insert a X)"
```
```   340     apply (rule Inf_greatest)
```
```   341     apply blast
```
```   342     apply (metis False Inf_lower insertE real_le_linear z)
```
```   343     done
```
```   344   ultimately have "Inf (insert a X) = Inf X"
```
```   345     by (blast intro:  antisym )
```
```   346   thus ?thesis
```
```   347     by (metis False min_max.inf_absorb2 real_le_linear)
```
```   348 qed
```
```   349
```
```   350 lemma Inf_insert_if:
```
```   351   fixes X :: "real set"
```
```   352   assumes z:  "!!x. x \<in> X \<Longrightarrow> z \<le> x"
```
```   353   shows "Inf (insert a X) = (if X={} then a else min a (Inf X))"
```
```   354 by auto (metis Inf_insert_nonempty z)
```
```   355
```
```   356 lemma Inf_greater:
```
```   357   fixes z :: real
```
```   358   shows "X \<noteq> {} \<Longrightarrow> Inf X < z \<Longrightarrow> \<exists>x \<in> X. x < z"
```
```   359   by (metis Inf_real_iff mem_def not_leE)
```
```   360
```
```   361 lemma Inf_close:
```
```   362   fixes e :: real
```
```   363   shows "X \<noteq> {} \<Longrightarrow> 0 < e \<Longrightarrow> \<exists>x \<in> X. x < Inf X + e"
```
```   364   by (metis add_strict_increasing add_commute Inf_greater linorder_not_le pos_add_strict)
```
```   365
```
```   366 lemma Inf_finite_Min:
```
```   367   fixes S :: "real set"
```
```   368   shows "finite S \<Longrightarrow> S \<noteq> {} \<Longrightarrow> Inf S = Min S"
```
```   369 by (simp add: Inf_real_def Sup_finite_Max image_image)
```
```   370
```
```   371 lemma Inf_finite_in:
```
```   372   fixes S :: "real set"
```
```   373   assumes fS: "finite S" and Se: "S \<noteq> {}"
```
```   374   shows "Inf S \<in> S"
```
```   375   using Inf_finite_Min[OF fS Se] Min_in[OF fS Se] by metis
```
```   376
```
```   377 lemma Inf_finite_ge_iff:
```
```   378   fixes S :: "real set"
```
```   379   shows "finite S \<Longrightarrow> S \<noteq> {} \<Longrightarrow> a \<le> Inf S \<longleftrightarrow> (\<forall> x \<in> S. a \<le> x)"
```
```   380 by (metis Inf_finite_Min Inf_finite_in Min_le real_le_trans)
```
```   381
```
```   382 lemma Inf_finite_le_iff:
```
```   383   fixes S :: "real set"
```
```   384   shows "finite S \<Longrightarrow> S \<noteq> {} \<Longrightarrow> a \<ge> Inf S \<longleftrightarrow> (\<exists> x \<in> S. a \<ge> x)"
```
```   385 by (metis Inf_finite_Min Inf_finite_ge_iff Inf_finite_in Min_le
```
```   386           real_le_antisym real_le_linear)
```
```   387
```
```   388 lemma Inf_finite_gt_iff:
```
```   389   fixes S :: "real set"
```
```   390   shows "finite S \<Longrightarrow> S \<noteq> {} \<Longrightarrow> a < Inf S \<longleftrightarrow> (\<forall> x \<in> S. a < x)"
```
```   391 by (metis Inf_finite_le_iff linorder_not_less)
```
```   392
```
```   393 lemma Inf_finite_lt_iff:
```
```   394   fixes S :: "real set"
```
```   395   shows "finite S \<Longrightarrow> S \<noteq> {} \<Longrightarrow> a > Inf S \<longleftrightarrow> (\<exists> x \<in> S. a > x)"
```
```   396 by (metis Inf_finite_ge_iff linorder_not_less)
```
```   397
```
```   398 lemma Inf_unique:
```
```   399   fixes S :: "real set"
```
```   400   shows "b <=* S \<Longrightarrow> (\<forall>b' > b. \<exists>x \<in> S. b' > x) \<Longrightarrow> Inf S = b"
```
```   401 unfolding setge_def
```
```   402 apply (rule Inf_eq, auto)
```
```   403 apply (metis less_le_not_le linorder_not_less)
```
```   404 done
```
```   405
```
```   406 lemma Inf_abs_ge:
```
```   407   fixes S :: "real set"
```
```   408   shows "S \<noteq> {} \<Longrightarrow> (\<forall>x\<in>S. \<bar>x\<bar> \<le> a) \<Longrightarrow> \<bar>Inf S\<bar> \<le> a"
```
```   409 by (simp add: Inf_real_def) (rule Sup_abs_le, auto)
```
```   410
```
```   411 lemma Inf_asclose:
```
```   412   fixes S :: "real set"
```
```   413   assumes S:"S \<noteq> {}" and b: "\<forall>x\<in>S. \<bar>x - l\<bar> \<le> e" shows "\<bar>Inf S - l\<bar> \<le> e"
```
```   414 proof -
```
```   415   have "\<bar>- Sup (uminus ` S) - l\<bar> =  \<bar>Sup (uminus ` S) - (-l)\<bar>"
```
```   416     by auto
```
```   417   also have "... \<le> e"
```
```   418     apply (rule Sup_asclose)
```
```   419     apply (auto simp add: S)
```
```   420     apply (metis abs_minus_add_cancel b add_commute real_diff_def)
```
```   421     done
```
```   422   finally have "\<bar>- Sup (uminus ` S) - l\<bar> \<le> e" .
```
```   423   thus ?thesis
```
```   424     by (simp add: Inf_real_def)
```
```   425 qed
```
```   426
```
```   427 lemma Inf_greaterThanLessThan[simp]: "y < x \<Longrightarrow> Inf {y<..<x} = (y::real)"
```
```   428   by (simp add: Inf_real_def)
```
```   429
```
```   430 lemma Inf_atLeastLessThan[simp]: "y < x \<Longrightarrow> Inf {y..<x} = (y::real)"
```
```   431   by (simp add: Inf_real_def)
```
```   432
```
```   433 lemma Inf_atLeast[simp]: "Inf {x..} = (x::real)"
```
```   434   by (simp add: Inf_real_def)
```
```   435
```
```   436 lemma Inf_greaterThanAtMost[simp]: "y < x \<Longrightarrow> Inf {y<..x} = (y::real)"
```
```   437   by (simp add: Inf_real_def)
```
```   438
```
```   439 lemma Inf_atLeastAtMost[simp]: "y \<le> x \<Longrightarrow> Inf {y..x} = (y::real)"
```
```   440   by (simp add: Inf_real_def)
```
```   441
```
```   442 subsection{*Relate max and min to Sup and Inf.*}
```
```   443
```
```   444 lemma real_max_Sup:
```
```   445   fixes x :: real
```
```   446   shows "max x y = Sup {x,y}"
```
```   447 proof-
```
```   448   have f: "finite {x, y}" "{x,y} \<noteq> {}"  by simp_all
```
```   449   from Sup_finite_le_iff[OF f, of "max x y"] have "Sup {x,y} \<le> max x y" by simp
```
```   450   moreover
```
```   451   have "max x y \<le> Sup {x,y}" using Sup_finite_ge_iff[OF f, of "max x y"]
```
```   452     by (simp add: linorder_linear)
```
```   453   ultimately show ?thesis by arith
```
```   454 qed
```
```   455
```
```   456 lemma real_min_Inf:
```
```   457   fixes x :: real
```
```   458   shows "min x y = Inf {x,y}"
```
```   459 proof-
```
```   460   have f: "finite {x, y}" "{x,y} \<noteq> {}"  by simp_all
```
```   461   from Inf_finite_le_iff[OF f, of "min x y"] have "Inf {x,y} \<le> min x y"
```
```   462     by (simp add: linorder_linear)
```
```   463   moreover
```
```   464   have "min x y \<le> Inf {x,y}" using Inf_finite_ge_iff[OF f, of "min x y"]
```
```   465     by simp
```
```   466   ultimately show ?thesis by arith
```
```   467 qed
```
```   468
```
```   469 lemma reals_complete_interval:
```
```   470   fixes a::real and b::real
```
```   471   assumes "a < b" and "P a" and "~P b"
```
```   472   shows "\<exists>c. a \<le> c & c \<le> b & (\<forall>x. a \<le> x & x < c --> P x) &
```
```   473              (\<forall>d. (\<forall>x. a \<le> x & x < d --> P x) --> d \<le> c)"
```
```   474 proof (rule exI [where x = "Sup {d. \<forall>x. a \<le> x & x < d --> P x}"], auto)
```
```   475   show "a \<le> Sup {d. \<forall>c. a \<le> c \<and> c < d \<longrightarrow> P c}"
```
```   476     by (rule SupInf.Sup_upper [where z=b], auto)
```
```   477        (metis `a < b` `\<not> P b` real_le_linear real_less_def)
```
```   478 next
```
```   479   show "Sup {d. \<forall>c. a \<le> c \<and> c < d \<longrightarrow> P c} \<le> b"
```
```   480     apply (rule SupInf.Sup_least)
```
```   481     apply (auto simp add: )
```
```   482     apply (metis less_le_not_le)
```
```   483     apply (metis `a<b` `~ P b` real_le_linear real_less_def)
```
```   484     done
```
```   485 next
```
```   486   fix x
```
```   487   assume x: "a \<le> x" and lt: "x < Sup {d. \<forall>c. a \<le> c \<and> c < d \<longrightarrow> P c}"
```
```   488   show "P x"
```
```   489     apply (rule less_SupE [OF lt], auto)
```
```   490     apply (metis less_le_not_le)
```
```   491     apply (metis x)
```
```   492     done
```
```   493 next
```
```   494   fix d
```
```   495     assume 0: "\<forall>x. a \<le> x \<and> x < d \<longrightarrow> P x"
```
```   496     thus "d \<le> Sup {d. \<forall>c. a \<le> c \<and> c < d \<longrightarrow> P c}"
```
```   497       by (rule_tac z="b" in SupInf.Sup_upper, auto)
```
```   498          (metis `a<b` `~ P b` real_le_linear real_less_def)
```
```   499 qed
```
```   500
```
```   501 end
```