src/HOL/Integration.thy
author huffman
Mon May 25 21:55:07 2009 -0700 (2009-05-25)
changeset 31252 5155117f9d66
parent 30082 43c5b7bfc791
child 31253 d54dc8956d48
permissions -rw-r--r--
clean up some proofs
haftmann@28952
     1
(*  Author      : Jacques D. Fleuriot
paulson@13958
     2
    Copyright   : 2000  University of Edinburgh
paulson@15093
     3
    Conversion to Isar and new proofs by Lawrence C Paulson, 2004
paulson@13958
     4
*)
paulson@13958
     5
paulson@15093
     6
header{*Theory of Integration*}
paulson@13958
     7
nipkow@15131
     8
theory Integration
huffman@29469
     9
imports Deriv ATP_Linkup
nipkow@15131
    10
begin
paulson@15093
    11
paulson@15093
    12
text{*We follow John Harrison in formalizing the Gauge integral.*}
paulson@13958
    13
wenzelm@19765
    14
definition
paulson@15093
    15
  --{*Partitions and tagged partitions etc.*}
paulson@13958
    16
wenzelm@21404
    17
  partition :: "[(real*real),nat => real] => bool" where
haftmann@28562
    18
  [code del]: "partition = (%(a,b) D. D 0 = a &
nipkow@15360
    19
                         (\<exists>N. (\<forall>n < N. D(n) < D(Suc n)) &
wenzelm@19765
    20
                              (\<forall>n \<ge> N. D(n) = b)))"
paulson@15093
    21
wenzelm@21404
    22
definition
wenzelm@21404
    23
  psize :: "(nat => real) => nat" where
haftmann@28562
    24
  [code del]:"psize D = (SOME N. (\<forall>n < N. D(n) < D(Suc n)) &
wenzelm@19765
    25
                      (\<forall>n \<ge> N. D(n) = D(N)))"
paulson@15093
    26
wenzelm@21404
    27
definition
wenzelm@21404
    28
  tpart :: "[(real*real),((nat => real)*(nat =>real))] => bool" where
haftmann@28562
    29
  [code del]:"tpart = (%(a,b) (D,p). partition(a,b) D &
wenzelm@19765
    30
                          (\<forall>n. D(n) \<le> p(n) & p(n) \<le> D(Suc n)))"
paulson@13958
    31
paulson@15093
    32
  --{*Gauges and gauge-fine divisions*}
paulson@15093
    33
wenzelm@21404
    34
definition
wenzelm@21404
    35
  gauge :: "[real => bool, real => real] => bool" where
haftmann@28562
    36
  [code del]:"gauge E g = (\<forall>x. E x --> 0 < g(x))"
paulson@13958
    37
wenzelm@21404
    38
definition
wenzelm@21404
    39
  fine :: "[real => real, ((nat => real)*(nat => real))] => bool" where
haftmann@28562
    40
  [code del]:"fine = (%g (D,p). \<forall>n. n < (psize D) --> D(Suc n) - D(n) < g(p n))"
paulson@13958
    41
paulson@15093
    42
  --{*Riemann sum*}
paulson@13958
    43
wenzelm@21404
    44
definition
wenzelm@21404
    45
  rsum :: "[((nat=>real)*(nat=>real)),real=>real] => real" where
wenzelm@19765
    46
  "rsum = (%(D,p) f. \<Sum>n=0..<psize(D). f(p n) * (D(Suc n) - D(n)))"
paulson@13958
    47
paulson@15093
    48
  --{*Gauge integrability (definite)*}
paulson@13958
    49
wenzelm@21404
    50
definition
wenzelm@21404
    51
  Integral :: "[(real*real),real=>real,real] => bool" where
haftmann@28562
    52
  [code del]: "Integral = (%(a,b) f k. \<forall>e > 0.
paulson@15093
    53
                               (\<exists>g. gauge(%x. a \<le> x & x \<le> b) g &
paulson@15093
    54
                               (\<forall>D p. tpart(a,b) (D,p) & fine(g)(D,p) -->
wenzelm@19765
    55
                                         \<bar>rsum(D,p) f - k\<bar> < e)))"
paulson@15093
    56
paulson@15093
    57
huffman@31252
    58
lemma Integral_def2:
huffman@31252
    59
  "Integral = (%(a,b) f k. \<forall>e>0. (\<exists>g. gauge(%x. a \<le> x & x \<le> b) g &
huffman@31252
    60
                               (\<forall>D p. tpart(a,b) (D,p) & fine(g)(D,p) -->
huffman@31252
    61
                                         \<bar>rsum(D,p) f - k\<bar> \<le> e)))"
huffman@31252
    62
unfolding Integral_def
huffman@31252
    63
apply (safe intro!: ext)
huffman@31252
    64
apply (fast intro: less_imp_le)
huffman@31252
    65
apply (drule_tac x="e/2" in spec)
huffman@31252
    66
apply force
huffman@31252
    67
done
huffman@31252
    68
huffman@29353
    69
lemma psize_unique:
huffman@29353
    70
  assumes 1: "\<forall>n < N. D(n) < D(Suc n)"
huffman@29353
    71
  assumes 2: "\<forall>n \<ge> N. D(n) = D(N)"
huffman@29353
    72
  shows "psize D = N"
huffman@29353
    73
unfolding psize_def
huffman@29353
    74
proof (rule some_equality)
huffman@29353
    75
  show "(\<forall>n<N. D(n) < D(Suc n)) \<and> (\<forall>n\<ge>N. D(n) = D(N))" using prems ..
huffman@29353
    76
next
huffman@29353
    77
  fix M assume "(\<forall>n<M. D(n) < D(Suc n)) \<and> (\<forall>n\<ge>M. D(n) = D(M))"
huffman@29353
    78
  hence 3: "\<forall>n<M. D(n) < D(Suc n)" and 4: "\<forall>n\<ge>M. D(n) = D(M)" by fast+
huffman@29353
    79
  show "M = N"
huffman@29353
    80
  proof (rule linorder_cases)
huffman@29353
    81
    assume "M < N"
huffman@29353
    82
    hence "D(M) < D(Suc M)" by (rule 1 [rule_format])
huffman@29353
    83
    also have "D(Suc M) = D(M)" by (rule 4 [rule_format], simp)
huffman@29353
    84
    finally show "M = N" by simp
huffman@29353
    85
  next
huffman@29353
    86
    assume "N < M"
huffman@29353
    87
    hence "D(N) < D(Suc N)" by (rule 3 [rule_format])
huffman@29353
    88
    also have "D(Suc N) = D(N)" by (rule 2 [rule_format], simp)
huffman@29353
    89
    finally show "M = N" by simp
huffman@29353
    90
  next
huffman@29353
    91
    assume "M = N" thus "M = N" .
huffman@29353
    92
  qed
huffman@29353
    93
qed
huffman@29353
    94
paulson@15093
    95
lemma partition_zero [simp]: "a = b ==> psize (%n. if n = 0 then a else b) = 0"
huffman@29353
    96
by (rule psize_unique, simp_all)
paulson@15093
    97
paulson@15093
    98
lemma partition_one [simp]: "a < b ==> psize (%n. if n = 0 then a else b) = 1"
huffman@29353
    99
by (rule psize_unique, simp_all)
paulson@15093
   100
paulson@15093
   101
lemma partition_single [simp]:
paulson@15093
   102
     "a \<le> b ==> partition(a,b)(%n. if n = 0 then a else b)"
paulson@15093
   103
by (auto simp add: partition_def order_le_less)
paulson@15093
   104
paulson@15093
   105
lemma partition_lhs: "partition(a,b) D ==> (D(0) = a)"
paulson@15093
   106
by (simp add: partition_def)
paulson@15093
   107
paulson@15093
   108
lemma partition:
paulson@15093
   109
       "(partition(a,b) D) =
paulson@15093
   110
        ((D 0 = a) &
nipkow@15360
   111
         (\<forall>n < psize D. D n < D(Suc n)) &
nipkow@15360
   112
         (\<forall>n \<ge> psize D. D n = b))"
huffman@29353
   113
apply (simp add: partition_def)
huffman@29353
   114
apply (rule iffI, clarify)
huffman@29353
   115
apply (subgoal_tac "psize D = N", simp)
huffman@29353
   116
apply (rule psize_unique, assumption, simp)
huffman@29353
   117
apply (simp, rule_tac x="psize D" in exI, simp)
paulson@15093
   118
done
paulson@15093
   119
paulson@15093
   120
lemma partition_rhs: "partition(a,b) D ==> (D(psize D) = b)"
paulson@15093
   121
by (simp add: partition)
paulson@15093
   122
paulson@15093
   123
lemma partition_rhs2: "[|partition(a,b) D; psize D \<le> n |] ==> (D n = b)"
paulson@15093
   124
by (simp add: partition)
paulson@15093
   125
paulson@15093
   126
lemma lemma_partition_lt_gen [rule_format]:
paulson@15093
   127
 "partition(a,b) D & m + Suc d \<le> n & n \<le> (psize D) --> D(m) < D(m + Suc d)"
paulson@15251
   128
apply (induct "d", auto simp add: partition)
paulson@15093
   129
apply (blast dest: Suc_le_lessD  intro: less_le_trans order_less_trans)
paulson@15093
   130
done
paulson@15093
   131
paulson@15093
   132
lemma less_eq_add_Suc: "m < n ==> \<exists>d. n = m + Suc d"
paulson@15093
   133
by (auto simp add: less_iff_Suc_add)
paulson@15093
   134
paulson@15093
   135
lemma partition_lt_gen:
paulson@15093
   136
     "[|partition(a,b) D; m < n; n \<le> (psize D)|] ==> D(m) < D(n)"
paulson@15093
   137
by (auto dest: less_eq_add_Suc intro: lemma_partition_lt_gen)
paulson@15093
   138
paulson@15093
   139
lemma partition_lt: "partition(a,b) D ==> n < (psize D) ==> D(0) < D(Suc n)"
paulson@15093
   140
apply (induct "n")
paulson@15093
   141
apply (auto simp add: partition)
paulson@15093
   142
done
paulson@15093
   143
paulson@15093
   144
lemma partition_le: "partition(a,b) D ==> a \<le> b"
paulson@15093
   145
apply (frule partition [THEN iffD1], safe)
paulson@15219
   146
apply (drule_tac x = "psize D" and P="%n. psize D \<le> n --> ?P n" in spec, safe)
paulson@15219
   147
apply (case_tac "psize D = 0")
huffman@30082
   148
apply (drule_tac [2] n = "psize D - Suc 0" in partition_lt, auto)
paulson@15093
   149
done
paulson@15093
   150
paulson@15093
   151
lemma partition_gt: "[|partition(a,b) D; n < (psize D)|] ==> D(n) < D(psize D)"
paulson@15093
   152
by (auto intro: partition_lt_gen)
paulson@15093
   153
paulson@15093
   154
lemma partition_eq: "partition(a,b) D ==> ((a = b) = (psize D = 0))"
paulson@15093
   155
apply (frule partition [THEN iffD1], safe)
paulson@15093
   156
apply (rotate_tac 2)
paulson@15093
   157
apply (drule_tac x = "psize D" in spec)
paulson@15093
   158
apply (rule ccontr)
huffman@30082
   159
apply (drule_tac n = "psize D - Suc 0" in partition_lt)
paulson@15219
   160
apply auto
paulson@15093
   161
done
paulson@15093
   162
paulson@15093
   163
lemma partition_lb: "partition(a,b) D ==> a \<le> D(r)"
paulson@15093
   164
apply (frule partition [THEN iffD1], safe)
paulson@15251
   165
apply (induct "r")
paulson@15251
   166
apply (cut_tac [2] y = "Suc r" and x = "psize D" in linorder_le_less_linear)
paulson@15251
   167
apply (auto intro: partition_le)
paulson@15251
   168
apply (drule_tac x = r in spec)
paulson@15251
   169
apply arith; 
paulson@15093
   170
done
paulson@15093
   171
paulson@15093
   172
lemma partition_lb_lt: "[| partition(a,b) D; psize D ~= 0 |] ==> a < D(Suc n)"
paulson@15093
   173
apply (rule_tac t = a in partition_lhs [THEN subst], assumption)
paulson@15093
   174
apply (cut_tac x = "Suc n" and y = "psize D" in linorder_le_less_linear)
paulson@15093
   175
apply (frule partition [THEN iffD1], safe)
paulson@15093
   176
 apply (blast intro: partition_lt less_le_trans)
paulson@15093
   177
apply (rotate_tac 3)
paulson@15093
   178
apply (drule_tac x = "Suc n" in spec)
paulson@15093
   179
apply (erule impE)
paulson@15093
   180
apply (erule less_imp_le)
nipkow@25134
   181
apply (frule partition_rhs)
nipkow@25134
   182
apply (drule partition_gt[of _ _ _ 0], arith)
paulson@15093
   183
apply (simp (no_asm_simp))
paulson@15093
   184
done
paulson@15093
   185
paulson@15093
   186
lemma partition_ub: "partition(a,b) D ==> D(r) \<le> b"
paulson@15093
   187
apply (frule partition [THEN iffD1])
paulson@15093
   188
apply (cut_tac x = "psize D" and y = r in linorder_le_less_linear, safe, blast)
paulson@15093
   189
apply (subgoal_tac "\<forall>x. D ((psize D) - x) \<le> b")
paulson@15093
   190
apply (rotate_tac 4)
paulson@15093
   191
apply (drule_tac x = "psize D - r" in spec)
paulson@15093
   192
apply (subgoal_tac "psize D - (psize D - r) = r")
paulson@15093
   193
apply simp
paulson@15093
   194
apply arith
paulson@15093
   195
apply safe
paulson@15093
   196
apply (induct_tac "x")
paulson@15093
   197
apply (simp (no_asm), blast)
paulson@15093
   198
apply (case_tac "psize D - Suc n = 0")
paulson@15093
   199
apply (erule_tac V = "\<forall>n. psize D \<le> n --> D n = b" in thin_rl)
paulson@15093
   200
apply (simp (no_asm_simp) add: partition_le)
paulson@15093
   201
apply (rule order_trans)
paulson@15093
   202
 prefer 2 apply assumption
paulson@15093
   203
apply (subgoal_tac "psize D - n = Suc (psize D - Suc n)")
paulson@15093
   204
 prefer 2 apply arith
webertj@20432
   205
apply (drule_tac x = "psize D - Suc n" in spec, simp) 
paulson@15093
   206
done
paulson@15093
   207
paulson@15093
   208
lemma partition_ub_lt: "[| partition(a,b) D; n < psize D |] ==> D(n) < b"
paulson@15093
   209
by (blast intro: partition_rhs [THEN subst] partition_gt)
paulson@15093
   210
paulson@15093
   211
lemma lemma_partition_append1:
paulson@15093
   212
     "[| partition (a, b) D1; partition (b, c) D2 |]
nipkow@15360
   213
       ==> (\<forall>n < psize D1 + psize D2.
paulson@15093
   214
             (if n < psize D1 then D1 n else D2 (n - psize D1))
paulson@15093
   215
             < (if Suc n < psize D1 then D1 (Suc n)
paulson@15093
   216
                else D2 (Suc n - psize D1))) &
nipkow@15360
   217
         (\<forall>n \<ge> psize D1 + psize D2.
paulson@15093
   218
             (if n < psize D1 then D1 n else D2 (n - psize D1)) =
paulson@15093
   219
             (if psize D1 + psize D2 < psize D1 then D1 (psize D1 + psize D2)
paulson@15093
   220
              else D2 (psize D1 + psize D2 - psize D1)))"
paulson@15093
   221
apply (auto intro: partition_lt_gen)
paulson@15093
   222
apply (subgoal_tac "psize D1 = Suc n")
paulson@15093
   223
apply (auto intro!: partition_lt_gen simp add: partition_lhs partition_ub_lt)
paulson@15093
   224
apply (auto intro!: partition_rhs2 simp add: partition_rhs
paulson@15093
   225
            split: nat_diff_split)
paulson@15093
   226
done
paulson@15093
   227
paulson@15093
   228
lemma lemma_psize1:
paulson@15093
   229
     "[| partition (a, b) D1; partition (b, c) D2; N < psize D1 |]
paulson@15093
   230
      ==> D1(N) < D2 (psize D2)"
paulson@15094
   231
apply (rule_tac y = "D1 (psize D1)" in order_less_le_trans)
paulson@15219
   232
apply (erule partition_gt)
paulson@15093
   233
apply (auto simp add: partition_rhs partition_le)
paulson@15093
   234
done
paulson@15093
   235
paulson@15093
   236
lemma lemma_partition_append2:
paulson@15093
   237
     "[| partition (a, b) D1; partition (b, c) D2 |]
paulson@15093
   238
      ==> psize (%n. if n < psize D1 then D1 n else D2 (n - psize D1)) =
huffman@29353
   239
          psize D1 + psize D2"
huffman@29353
   240
apply (rule psize_unique)
huffman@29353
   241
apply (erule (1) lemma_partition_append1 [THEN conjunct1])
huffman@29353
   242
apply (erule (1) lemma_partition_append1 [THEN conjunct2])
paulson@15093
   243
done
paulson@15093
   244
paulson@15219
   245
lemma tpart_eq_lhs_rhs: "[|psize D = 0; tpart(a,b) (D,p)|] ==> a = b"
paulson@15219
   246
by (auto simp add: tpart_def partition_eq)
paulson@15093
   247
paulson@15093
   248
lemma tpart_partition: "tpart(a,b) (D,p) ==> partition(a,b) D"
paulson@15093
   249
by (simp add: tpart_def)
paulson@15093
   250
paulson@15093
   251
lemma partition_append:
paulson@15093
   252
     "[| tpart(a,b) (D1,p1); fine(g) (D1,p1);
paulson@15093
   253
         tpart(b,c) (D2,p2); fine(g) (D2,p2) |]
paulson@15093
   254
       ==> \<exists>D p. tpart(a,c) (D,p) & fine(g) (D,p)"
paulson@15093
   255
apply (rule_tac x = "%n. if n < psize D1 then D1 n else D2 (n - psize D1)"
paulson@15093
   256
       in exI)
paulson@15093
   257
apply (rule_tac x = "%n. if n < psize D1 then p1 n else p2 (n - psize D1)"
paulson@15093
   258
       in exI)
paulson@15093
   259
apply (case_tac "psize D1 = 0")
paulson@15093
   260
apply (auto dest: tpart_eq_lhs_rhs)
paulson@15093
   261
 prefer 2
paulson@15093
   262
apply (simp add: fine_def
paulson@15093
   263
                 lemma_partition_append2 [OF tpart_partition tpart_partition])
paulson@15093
   264
  --{*But must not expand @{term fine} in other subgoals*}
paulson@15093
   265
apply auto
paulson@15093
   266
apply (subgoal_tac "psize D1 = Suc n")
paulson@15093
   267
 prefer 2 apply arith
paulson@15093
   268
apply (drule tpart_partition [THEN partition_rhs])
paulson@15093
   269
apply (drule tpart_partition [THEN partition_lhs])
paulson@15093
   270
apply (auto split: nat_diff_split)
paulson@15093
   271
apply (auto simp add: tpart_def)
paulson@15093
   272
defer 1
paulson@15093
   273
 apply (subgoal_tac "psize D1 = Suc n")
paulson@15093
   274
  prefer 2 apply arith
paulson@15093
   275
 apply (drule partition_rhs)
paulson@15093
   276
 apply (drule partition_lhs, auto)
paulson@15093
   277
apply (simp split: nat_diff_split)
paulson@15944
   278
apply (subst partition) 
paulson@15944
   279
apply (subst (1 2) lemma_partition_append2, assumption+)
paulson@15944
   280
apply (rule conjI) 
paulson@15944
   281
apply (simp add: partition_lhs)
paulson@15944
   282
apply (drule lemma_partition_append1)
paulson@15944
   283
apply assumption; 
paulson@15944
   284
apply (simp add: partition_rhs)
paulson@15093
   285
done
paulson@15093
   286
paulson@15481
   287
paulson@15219
   288
text{*We can always find a division that is fine wrt any gauge*}
paulson@15093
   289
paulson@15093
   290
lemma partition_exists:
paulson@15093
   291
     "[| a \<le> b; gauge(%x. a \<le> x & x \<le> b) g |]
paulson@15093
   292
      ==> \<exists>D p. tpart(a,b) (D,p) & fine g (D,p)"
paulson@15093
   293
apply (cut_tac P = "%(u,v). a \<le> u & v \<le> b --> 
paulson@15093
   294
                   (\<exists>D p. tpart (u,v) (D,p) & fine (g) (D,p))" 
paulson@15093
   295
       in lemma_BOLZANO2)
paulson@15093
   296
apply safe
paulson@15219
   297
apply (blast intro: order_trans)+
paulson@15093
   298
apply (auto intro: partition_append)
paulson@15093
   299
apply (case_tac "a \<le> x & x \<le> b")
paulson@15093
   300
apply (rule_tac [2] x = 1 in exI, auto)
paulson@15093
   301
apply (rule_tac x = "g x" in exI)
paulson@15093
   302
apply (auto simp add: gauge_def)
paulson@15093
   303
apply (rule_tac x = "%n. if n = 0 then aa else ba" in exI)
paulson@15093
   304
apply (rule_tac x = "%n. if n = 0 then x else ba" in exI)
paulson@15093
   305
apply (auto simp add: tpart_def fine_def)
paulson@15093
   306
done
paulson@15093
   307
paulson@15093
   308
text{*Lemmas about combining gauges*}
paulson@15093
   309
paulson@15093
   310
lemma gauge_min:
paulson@15093
   311
     "[| gauge(E) g1; gauge(E) g2 |]
paulson@15093
   312
      ==> gauge(E) (%x. if g1(x) < g2(x) then g1(x) else g2(x))"
paulson@15093
   313
by (simp add: gauge_def)
paulson@15093
   314
paulson@15093
   315
lemma fine_min:
paulson@15093
   316
      "fine (%x. if g1(x) < g2(x) then g1(x) else g2(x)) (D,p)
paulson@15093
   317
       ==> fine(g1) (D,p) & fine(g2) (D,p)"
paulson@15093
   318
by (auto simp add: fine_def split: split_if_asm)
paulson@15093
   319
paulson@15093
   320
paulson@15093
   321
text{*The integral is unique if it exists*}
paulson@15093
   322
paulson@15093
   323
lemma Integral_unique:
paulson@15093
   324
    "[| a \<le> b; Integral(a,b) f k1; Integral(a,b) f k2 |] ==> k1 = k2"
paulson@15093
   325
apply (simp add: Integral_def)
paulson@15093
   326
apply (drule_tac x = "\<bar>k1 - k2\<bar> /2" in spec)+
paulson@15093
   327
apply auto
paulson@15093
   328
apply (drule gauge_min, assumption)
paulson@15093
   329
apply (drule_tac g = "%x. if g x < ga x then g x else ga x" 
paulson@15093
   330
       in partition_exists, assumption, auto)
paulson@15093
   331
apply (drule fine_min)
paulson@15093
   332
apply (drule spec)+
paulson@15093
   333
apply auto
paulson@15094
   334
apply (subgoal_tac "\<bar>(rsum (D,p) f - k2) - (rsum (D,p) f - k1)\<bar> < \<bar>k1 - k2\<bar>")
paulson@15093
   335
apply arith
paulson@15093
   336
apply (drule add_strict_mono, assumption)
paulson@15093
   337
apply (auto simp only: left_distrib [symmetric] mult_2_right [symmetric] 
huffman@17318
   338
                mult_less_cancel_right)
paulson@15093
   339
done
paulson@15093
   340
paulson@15093
   341
lemma Integral_zero [simp]: "Integral(a,a) f 0"
paulson@15093
   342
apply (auto simp add: Integral_def)
paulson@15093
   343
apply (rule_tac x = "%x. 1" in exI)
paulson@15093
   344
apply (auto dest: partition_eq simp add: gauge_def tpart_def rsum_def)
paulson@15093
   345
done
paulson@15093
   346
paulson@15093
   347
lemma sumr_partition_eq_diff_bounds [simp]:
nipkow@15539
   348
     "(\<Sum>n=0..<m. D (Suc n) - D n::real) = D(m) - D 0"
paulson@15251
   349
by (induct "m", auto)
paulson@15093
   350
paulson@15093
   351
lemma Integral_eq_diff_bounds: "a \<le> b ==> Integral(a,b) (%x. 1) (b - a)"
paulson@15219
   352
apply (auto simp add: order_le_less rsum_def Integral_def)
paulson@15093
   353
apply (rule_tac x = "%x. b - a" in exI)
huffman@22998
   354
apply (auto simp add: gauge_def abs_less_iff tpart_def partition)
paulson@15093
   355
done
paulson@15093
   356
paulson@15093
   357
lemma Integral_mult_const: "a \<le> b ==> Integral(a,b) (%x. c)  (c*(b - a))"
paulson@15219
   358
apply (auto simp add: order_le_less rsum_def Integral_def)
paulson@15093
   359
apply (rule_tac x = "%x. b - a" in exI)
huffman@22998
   360
apply (auto simp add: setsum_right_distrib [symmetric] gauge_def abs_less_iff 
paulson@15093
   361
               right_diff_distrib [symmetric] partition tpart_def)
paulson@15093
   362
done
paulson@15093
   363
paulson@15093
   364
lemma Integral_mult:
paulson@15093
   365
     "[| a \<le> b; Integral(a,b) f k |] ==> Integral(a,b) (%x. c * f x) (c * k)"
paulson@15221
   366
apply (auto simp add: order_le_less 
paulson@15221
   367
            dest: Integral_unique [OF order_refl Integral_zero])
ballarin@19279
   368
apply (auto simp add: rsum_def Integral_def setsum_right_distrib[symmetric] mult_assoc)
huffman@22998
   369
apply (rule_tac a2 = c in abs_ge_zero [THEN order_le_imp_less_or_eq, THEN disjE])
paulson@15093
   370
 prefer 2 apply force
paulson@15093
   371
apply (drule_tac x = "e/abs c" in spec, auto)
paulson@15093
   372
apply (simp add: zero_less_mult_iff divide_inverse)
paulson@15093
   373
apply (rule exI, auto)
paulson@15093
   374
apply (drule spec)+
paulson@15093
   375
apply auto
paulson@15094
   376
apply (rule_tac z1 = "inverse (abs c)" in real_mult_less_iff1 [THEN iffD1])
paulson@16924
   377
apply (auto simp add: abs_mult divide_inverse [symmetric] right_diff_distrib [symmetric])
paulson@15093
   378
done
paulson@15093
   379
paulson@15093
   380
text{*Fundamental theorem of calculus (Part I)*}
paulson@15093
   381
nipkow@15105
   382
text{*"Straddle Lemma" : Swartz and Thompson: AMM 95(7) 1988 *}
paulson@15093
   383
paulson@16588
   384
lemma choiceP: "\<forall>x. P(x) --> (\<exists>y. Q x y) ==> \<exists>f. (\<forall>x. P(x) --> Q x (f x))" 
paulson@16588
   385
by (insert bchoice [of "Collect P" Q], simp) 
paulson@15093
   386
paulson@15093
   387
(*UNUSED
paulson@15093
   388
lemma choice2: "\<forall>x. (\<exists>y. R(y) & (\<exists>z. Q x y z)) ==>
paulson@15093
   389
      \<exists>f fa. (\<forall>x. R(f x) & Q x (f x) (fa x))"
paulson@15093
   390
*)
paulson@15093
   391
paulson@15093
   392
paulson@15093
   393
lemma strad1:
huffman@31252
   394
       "\<lbrakk>\<forall>z::real. z \<noteq> x \<and> \<bar>z - x\<bar> < s \<longrightarrow>
huffman@31252
   395
             \<bar>(f z - f x) / (z - x) - f' x\<bar> < e/2;
huffman@31252
   396
        0 < s; 0 < e; a \<le> x; x \<le> b\<rbrakk>
huffman@31252
   397
       \<Longrightarrow> \<forall>z. \<bar>z - x\<bar> < s -->\<bar>f z - f x - f' x * (z - x)\<bar> \<le> e/2 * \<bar>z - x\<bar>"
huffman@31252
   398
apply clarify
paulson@15094
   399
apply (case_tac "0 < \<bar>z - x\<bar>")
paulson@15093
   400
 prefer 2 apply (simp add: zero_less_abs_iff)
paulson@15093
   401
apply (drule_tac x = z in spec)
paulson@15093
   402
apply (rule_tac z1 = "\<bar>inverse (z - x)\<bar>" 
paulson@15093
   403
       in real_mult_le_cancel_iff2 [THEN iffD1])
paulson@15093
   404
 apply simp
paulson@15093
   405
apply (simp del: abs_inverse abs_mult add: abs_mult [symmetric]
paulson@15093
   406
          mult_assoc [symmetric])
paulson@15093
   407
apply (subgoal_tac "inverse (z - x) * (f z - f x - f' x * (z - x)) 
paulson@15093
   408
                    = (f z - f x) / (z - x) - f' x")
paulson@15093
   409
 apply (simp add: abs_mult [symmetric] mult_ac diff_minus)
paulson@15093
   410
apply (subst mult_commute)
paulson@15093
   411
apply (simp add: left_distrib diff_minus)
paulson@15093
   412
apply (simp add: mult_assoc divide_inverse)
paulson@15093
   413
apply (simp add: left_distrib)
paulson@15093
   414
done
paulson@15093
   415
paulson@15093
   416
lemma lemma_straddle:
huffman@31252
   417
  assumes f': "\<forall>x. a \<le> x & x \<le> b --> DERIV f x :> f'(x)" and "0 < e"
huffman@31252
   418
  shows "\<exists>g. gauge(%x. a \<le> x & x \<le> b) g &
paulson@15093
   419
                (\<forall>x u v. a \<le> u & u \<le> x & x \<le> v & v \<le> b & (v - u) < g(x)
paulson@15094
   420
                  --> \<bar>(f(v) - f(u)) - (f'(x) * (v - u))\<bar> \<le> e * (v - u))"
huffman@31252
   421
proof -
huffman@31252
   422
  have "\<forall>x. a \<le> x & x \<le> b --> 
nipkow@15360
   423
        (\<exists>d > 0. \<forall>u v. u \<le> x & x \<le> v & (v - u) < d --> 
huffman@31252
   424
                       \<bar>(f(v) - f(u)) - (f'(x) * (v - u))\<bar> \<le> e * (v - u))"
huffman@31252
   425
  proof (clarify)
huffman@31252
   426
    fix x :: real assume "a \<le> x" and "x \<le> b"
huffman@31252
   427
    with f' have "DERIV f x :> f'(x)" by simp
huffman@31252
   428
    then have "\<forall>r>0. \<exists>s>0. \<forall>z. z \<noteq> x \<and> \<bar>z - x\<bar> < s \<longrightarrow> \<bar>(f z - f x) / (z - x) - f' x\<bar> < r"
huffman@31252
   429
      by (simp add: DERIV_iff2 LIM_def)
huffman@31252
   430
    with `0 < e` obtain s
huffman@31252
   431
    where "\<forall>z. z \<noteq> x \<and> \<bar>z - x\<bar> < s \<longrightarrow> \<bar>(f z - f x) / (z - x) - f' x\<bar> < e/2" and "0 < s"
huffman@31252
   432
      by (drule_tac x="e/2" in spec, auto)
huffman@31252
   433
    then have strad [rule_format]:
huffman@31252
   434
        "\<forall>z. \<bar>z - x\<bar> < s --> \<bar>f z - f x - f' x * (z - x)\<bar> \<le> e/2 * \<bar>z - x\<bar>"
huffman@31252
   435
      using `0 < e` `a \<le> x` `x \<le> b` by (rule strad1)
huffman@31252
   436
    show "\<exists>d>0. \<forall>u v. u \<le> x \<and> x \<le> v \<and> v - u < d \<longrightarrow> \<bar>f v - f u - f' x * (v - u)\<bar> \<le> e * (v - u)"
huffman@31252
   437
    proof (safe intro!: exI)
huffman@31252
   438
      show "0 < s" by fact
huffman@31252
   439
    next
huffman@31252
   440
      fix u v :: real assume "u \<le> x" and "x \<le> v" and "v - u < s"
huffman@31252
   441
      have "\<bar>f v - f u - f' x * (v - u)\<bar> =
huffman@31252
   442
            \<bar>(f v - f x - f' x * (v - x)) + (f x - f u - f' x * (x - u))\<bar>"
huffman@31252
   443
        by (simp add: right_diff_distrib)
huffman@31252
   444
      also have "\<dots> \<le> \<bar>f v - f x - f' x * (v - x)\<bar> + \<bar>f x - f u - f' x * (x - u)\<bar>"
huffman@31252
   445
        by (rule abs_triangle_ineq)
huffman@31252
   446
      also have "\<dots> = \<bar>f v - f x - f' x * (v - x)\<bar> + \<bar>f u - f x - f' x * (u - x)\<bar>"
huffman@31252
   447
        by (simp add: right_diff_distrib)
huffman@31252
   448
      also have "\<dots> \<le> (e/2) * \<bar>v - x\<bar> + (e/2) * \<bar>u - x\<bar>"
huffman@31252
   449
        using `u \<le> x` `x \<le> v` `v - u < s` by (intro add_mono strad, simp_all)
huffman@31252
   450
      also have "\<dots> \<le> e * (v - u) / 2 + e * (v - u) / 2"
huffman@31252
   451
        using `u \<le> x` `x \<le> v` `0 < e` by (intro add_mono, simp_all)
huffman@31252
   452
      also have "\<dots> = e * (v - u)"
huffman@31252
   453
        by simp
huffman@31252
   454
      finally show "\<bar>f v - f u - f' x * (v - u)\<bar> \<le> e * (v - u)" .
huffman@31252
   455
    qed
huffman@31252
   456
  qed
huffman@31252
   457
  thus ?thesis
huffman@31252
   458
    by (simp add: gauge_def) (drule choiceP, auto)
huffman@31252
   459
qed
paulson@15093
   460
paulson@15093
   461
lemma FTC1: "[|a \<le> b; \<forall>x. a \<le> x & x \<le> b --> DERIV f x :> f'(x) |]
paulson@15219
   462
             ==> Integral(a,b) f' (f(b) - f(a))"
huffman@31252
   463
 apply (drule order_le_imp_less_or_eq, auto)
huffman@31252
   464
 apply (auto simp add: Integral_def2)
huffman@31252
   465
 apply (drule_tac e = "e / (b - a)" in lemma_straddle)
huffman@31252
   466
  apply (simp add: divide_pos_pos)
huffman@31252
   467
 apply clarify
huffman@31252
   468
 apply (rule_tac x="g" in exI, clarify)
huffman@31252
   469
 apply (clarsimp simp add: tpart_def rsum_def)
huffman@31252
   470
 apply (subgoal_tac "(\<Sum>n=0..<psize D. f(D(Suc n)) - f(D n)) = f b - f a")
huffman@31252
   471
  prefer 2
huffman@31252
   472
  apply (cut_tac D = "%n. f (D n)" and m = "psize D"
paulson@15093
   473
        in sumr_partition_eq_diff_bounds)
huffman@31252
   474
  apply (simp add: partition_lhs partition_rhs)
huffman@31252
   475
 apply (erule subst)
huffman@31252
   476
 apply (subst setsum_subtractf [symmetric])
huffman@31252
   477
 apply (rule setsum_abs [THEN order_trans])
huffman@31252
   478
 apply (subgoal_tac "e = (\<Sum>n=0..<psize D. (e / (b - a)) * (D (Suc n) - (D n)))")
huffman@31252
   479
  apply (erule ssubst)
huffman@31252
   480
  apply (simp add: abs_minus_commute)
huffman@31252
   481
  apply (rule setsum_mono)
huffman@31252
   482
  apply (simp add: partition_lb partition_ub fine_def)
huffman@31252
   483
 apply (subst setsum_right_distrib [symmetric])
huffman@31252
   484
 apply (subst sumr_partition_eq_diff_bounds)
paulson@15093
   485
 apply (simp add: partition_lhs partition_rhs)
paulson@15093
   486
done
paulson@13958
   487
paulson@13958
   488
paulson@15093
   489
lemma Integral_subst: "[| Integral(a,b) f k1; k2=k1 |] ==> Integral(a,b) f k2"
paulson@15093
   490
by simp
paulson@15093
   491
paulson@15093
   492
lemma Integral_add:
paulson@15093
   493
     "[| a \<le> b; b \<le> c; Integral(a,b) f' k1; Integral(b,c) f' k2;
paulson@15093
   494
         \<forall>x. a \<le> x & x \<le> c --> DERIV f x :> f' x |]
paulson@15093
   495
     ==> Integral(a,c) f' (k1 + k2)"
paulson@15093
   496
apply (rule FTC1 [THEN Integral_subst], auto)
paulson@15093
   497
apply (frule FTC1, auto)
paulson@15093
   498
apply (frule_tac a = b in FTC1, auto)
paulson@15093
   499
apply (drule_tac x = x in spec, auto)
paulson@15093
   500
apply (drule_tac ?k2.0 = "f b - f a" in Integral_unique)
paulson@15093
   501
apply (drule_tac [3] ?k2.0 = "f c - f b" in Integral_unique, auto)
paulson@15093
   502
done
paulson@15093
   503
paulson@15093
   504
lemma partition_psize_Least:
paulson@15093
   505
     "partition(a,b) D ==> psize D = (LEAST n. D(n) = b)"
paulson@15093
   506
apply (auto intro!: Least_equality [symmetric] partition_rhs)
paulson@15219
   507
apply (auto dest: partition_ub_lt simp add: linorder_not_less [symmetric])
paulson@15093
   508
done
paulson@15093
   509
paulson@15093
   510
lemma lemma_partition_bounded: "partition (a, c) D ==> ~ (\<exists>n. c < D(n))"
paulson@15093
   511
apply safe
paulson@15093
   512
apply (drule_tac r = n in partition_ub, auto)
paulson@15093
   513
done
paulson@15093
   514
paulson@15093
   515
lemma lemma_partition_eq:
paulson@15093
   516
     "partition (a, c) D ==> D = (%n. if D n < c then D n else c)"
paulson@15093
   517
apply (rule ext, auto)
paulson@15093
   518
apply (auto dest!: lemma_partition_bounded)
paulson@15093
   519
apply (drule_tac x = n in spec, auto)
paulson@15093
   520
done
paulson@15093
   521
paulson@15093
   522
lemma lemma_partition_eq2:
paulson@15093
   523
     "partition (a, c) D ==> D = (%n. if D n \<le> c then D n else c)"
paulson@15093
   524
apply (rule ext, auto)
paulson@15093
   525
apply (auto dest!: lemma_partition_bounded)
paulson@15093
   526
apply (drule_tac x = n in spec, auto)
paulson@15093
   527
done
paulson@15093
   528
paulson@15093
   529
lemma partition_lt_Suc:
paulson@15093
   530
     "[| partition(a,b) D; n < psize D |] ==> D n < D (Suc n)"
paulson@15093
   531
by (auto simp add: partition)
paulson@15093
   532
paulson@15093
   533
lemma tpart_tag_eq: "tpart(a,c) (D,p) ==> p = (%n. if D n < c then p n else c)"
paulson@15093
   534
apply (rule ext)
paulson@15093
   535
apply (auto simp add: tpart_def)
paulson@15093
   536
apply (drule linorder_not_less [THEN iffD1])
paulson@15093
   537
apply (drule_tac r = "Suc n" in partition_ub)
paulson@15093
   538
apply (drule_tac x = n in spec, auto)
paulson@15093
   539
done
paulson@15093
   540
paulson@15093
   541
subsection{*Lemmas for Additivity Theorem of Gauge Integral*}
paulson@15093
   542
paulson@15093
   543
lemma lemma_additivity1:
paulson@15093
   544
     "[| a \<le> D n; D n < b; partition(a,b) D |] ==> n < psize D"
paulson@15093
   545
by (auto simp add: partition linorder_not_less [symmetric])
paulson@15093
   546
paulson@15093
   547
lemma lemma_additivity2: "[| a \<le> D n; partition(a,D n) D |] ==> psize D \<le> n"
paulson@15093
   548
apply (rule ccontr, drule not_leE)
paulson@15093
   549
apply (frule partition [THEN iffD1], safe)
paulson@15093
   550
apply (frule_tac r = "Suc n" in partition_ub)
paulson@15093
   551
apply (auto dest!: spec)
paulson@15093
   552
done
paulson@15093
   553
paulson@15093
   554
lemma partition_eq_bound:
paulson@15093
   555
     "[| partition(a,b) D; psize D < m |] ==> D(m) = D(psize D)"
paulson@15093
   556
by (auto simp add: partition)
paulson@15093
   557
paulson@15093
   558
lemma partition_ub2: "[| partition(a,b) D; psize D < m |] ==> D(r) \<le> D(m)"
paulson@15093
   559
by (simp add: partition partition_ub)
paulson@15093
   560
paulson@15093
   561
lemma tag_point_eq_partition_point:
paulson@15093
   562
    "[| tpart(a,b) (D,p); psize D \<le> m |] ==> p(m) = D(m)"
paulson@15093
   563
apply (simp add: tpart_def, auto)
paulson@15093
   564
apply (drule_tac x = m in spec)
paulson@15093
   565
apply (auto simp add: partition_rhs2)
paulson@15093
   566
done
paulson@15093
   567
paulson@15093
   568
lemma partition_lt_cancel: "[| partition(a,b) D; D m < D n |] ==> m < n"
paulson@24742
   569
apply (cut_tac less_linear [of n "psize D"], auto)
paulson@24742
   570
apply (cut_tac less_linear [of m n])
paulson@24742
   571
apply (cut_tac less_linear [of m "psize D"])
paulson@15093
   572
apply (auto dest: partition_gt)
paulson@15093
   573
apply (drule_tac n = m in partition_lt_gen, auto)
paulson@15093
   574
apply (frule partition_eq_bound)
paulson@15093
   575
apply (drule_tac [2] partition_gt, auto)
chaieb@29811
   576
apply (metis linear not_less partition_rhs partition_rhs2)
nipkow@29833
   577
apply (metis lemma_additivity1 order_less_trans partition_eq_bound partition_lb partition_rhs)
paulson@15093
   578
done
paulson@15093
   579
paulson@15093
   580
lemma lemma_additivity4_psize_eq:
paulson@15093
   581
     "[| a \<le> D n; D n < b; partition (a, b) D |]
paulson@15093
   582
      ==> psize (%x. if D x < D n then D(x) else D n) = n"
huffman@29353
   583
apply (frule (2) lemma_additivity1)
huffman@29353
   584
apply (rule psize_unique, auto)
huffman@29353
   585
apply (erule partition_lt_Suc, erule (1) less_trans)
huffman@29353
   586
apply (erule notE)
huffman@29353
   587
apply (erule (1) partition_lt_gen, erule less_imp_le)
huffman@29353
   588
apply (drule (1) partition_lt_cancel, simp)
paulson@15093
   589
done
paulson@15093
   590
paulson@15093
   591
lemma lemma_psize_left_less_psize:
paulson@15093
   592
     "partition (a, b) D
paulson@15093
   593
      ==> psize (%x. if D x < D n then D(x) else D n) \<le> psize D"
paulson@15093
   594
apply (frule_tac r = n in partition_ub)
paulson@15219
   595
apply (drule_tac x = "D n" in order_le_imp_less_or_eq)
paulson@15093
   596
apply (auto simp add: lemma_partition_eq [symmetric])
paulson@15093
   597
apply (frule_tac r = n in partition_lb)
paulson@15219
   598
apply (drule (2) lemma_additivity4_psize_eq)  
paulson@15219
   599
apply (rule ccontr, auto)
paulson@15093
   600
apply (frule_tac not_leE [THEN [2] partition_eq_bound])
paulson@15093
   601
apply (auto simp add: partition_rhs)
paulson@15093
   602
done
paulson@15093
   603
paulson@15093
   604
lemma lemma_psize_left_less_psize2:
paulson@15093
   605
     "[| partition(a,b) D; na < psize (%x. if D x < D n then D(x) else D n) |]
paulson@15093
   606
      ==> na < psize D"
paulson@15219
   607
by (erule lemma_psize_left_less_psize [THEN [2] less_le_trans])
paulson@15093
   608
paulson@15093
   609
paulson@15093
   610
lemma lemma_additivity3:
paulson@15093
   611
     "[| partition(a,b) D; D na < D n; D n < D (Suc na);
paulson@15093
   612
         n < psize D |]
paulson@15093
   613
      ==> False"
paulson@24742
   614
by (metis not_less_eq partition_lt_cancel real_of_nat_less_iff)
paulson@24742
   615
paulson@15093
   616
paulson@15093
   617
lemma psize_const [simp]: "psize (%x. k) = 0"
paulson@15219
   618
by (auto simp add: psize_def)
paulson@15093
   619
paulson@15093
   620
lemma lemma_additivity3a:
paulson@15093
   621
     "[| partition(a,b) D; D na < D n; D n < D (Suc na);
paulson@15093
   622
         na < psize D |]
paulson@15093
   623
      ==> False"
paulson@15093
   624
apply (frule_tac m = n in partition_lt_cancel)
paulson@15093
   625
apply (auto intro: lemma_additivity3)
paulson@15093
   626
done
paulson@15093
   627
paulson@15093
   628
lemma better_lemma_psize_right_eq1:
paulson@15093
   629
     "[| partition(a,b) D; D n < b |] ==> psize (%x. D (x + n)) \<le> psize D - n"
paulson@15093
   630
apply (simp add: psize_def [of "(%x. D (x + n))"]);
paulson@15093
   631
apply (rule_tac a = "psize D - n" in someI2, auto)
paulson@15093
   632
  apply (simp add: partition less_diff_conv)
paulson@15219
   633
 apply (simp add: le_diff_conv partition_rhs2 split: nat_diff_split)
paulson@15093
   634
apply (drule_tac x = "psize D - n" in spec, auto)
paulson@15093
   635
apply (frule partition_rhs, safe)
paulson@15093
   636
apply (frule partition_lt_cancel, assumption)
paulson@15093
   637
apply (drule partition [THEN iffD1], safe)
paulson@15093
   638
apply (subgoal_tac "~ D (psize D - n + n) < D (Suc (psize D - n + n))")
paulson@15093
   639
 apply blast
paulson@15093
   640
apply (drule_tac x = "Suc (psize D)" and P="%n. ?P n \<longrightarrow> D n = D (psize D)"
paulson@15093
   641
       in spec)
paulson@15219
   642
apply simp
paulson@15093
   643
done
paulson@15093
   644
paulson@15219
   645
lemma psize_le_n: "partition (a, D n) D ==> psize D \<le> n" 
paulson@15093
   646
apply (rule ccontr, drule not_leE)
paulson@15093
   647
apply (frule partition_lt_Suc, assumption)
paulson@15093
   648
apply (frule_tac r = "Suc n" in partition_ub, auto)
paulson@15093
   649
done
paulson@15093
   650
paulson@15093
   651
lemma better_lemma_psize_right_eq1a:
paulson@15093
   652
     "partition(a,D n) D ==> psize (%x. D (x + n)) \<le> psize D - n"
paulson@15093
   653
apply (simp add: psize_def [of "(%x. D (x + n))"]);
paulson@15093
   654
apply (rule_tac a = "psize D - n" in someI2, auto)
paulson@15093
   655
  apply (simp add: partition less_diff_conv)
paulson@15093
   656
 apply (simp add: le_diff_conv)
paulson@15093
   657
apply (case_tac "psize D \<le> n")
paulson@15093
   658
  apply (force intro: partition_rhs2)
paulson@15093
   659
 apply (simp add: partition linorder_not_le)
paulson@15093
   660
apply (rule ccontr, drule not_leE)
paulson@15093
   661
apply (frule psize_le_n)
paulson@15093
   662
apply (drule_tac x = "psize D - n" in spec, simp)
paulson@15093
   663
apply (drule partition [THEN iffD1], safe)
paulson@15219
   664
apply (drule_tac x = "Suc n" and P="%na. ?s \<le> na \<longrightarrow> D na = D n" in spec, auto)
paulson@15093
   665
done
paulson@15093
   666
paulson@15093
   667
lemma better_lemma_psize_right_eq:
paulson@15093
   668
     "partition(a,b) D ==> psize (%x. D (x + n)) \<le> psize D - n"
paulson@15219
   669
apply (frule_tac r1 = n in partition_ub [THEN order_le_imp_less_or_eq])
paulson@15093
   670
apply (blast intro: better_lemma_psize_right_eq1a better_lemma_psize_right_eq1)
paulson@15093
   671
done
paulson@15093
   672
paulson@15093
   673
lemma lemma_psize_right_eq1:
paulson@15093
   674
     "[| partition(a,b) D; D n < b |] ==> psize (%x. D (x + n)) \<le> psize D"
paulson@15219
   675
apply (simp add: psize_def [of "(%x. D (x + n))"])
paulson@15093
   676
apply (rule_tac a = "psize D - n" in someI2, auto)
paulson@15093
   677
  apply (simp add: partition less_diff_conv)
paulson@15093
   678
 apply (subgoal_tac "n \<le> psize D")
paulson@15093
   679
  apply (simp add: partition le_diff_conv)
paulson@15093
   680
 apply (rule ccontr, drule not_leE)
paulson@15219
   681
 apply (drule_tac less_imp_le [THEN [2] partition_rhs2], assumption, simp)
paulson@15093
   682
apply (drule_tac x = "psize D" in spec)
paulson@15093
   683
apply (simp add: partition)
paulson@15093
   684
done
paulson@15093
   685
paulson@15093
   686
(* should be combined with previous theorem; also proof has redundancy *)
paulson@15093
   687
lemma lemma_psize_right_eq1a:
paulson@15093
   688
     "partition(a,D n) D ==> psize (%x. D (x + n)) \<le> psize D"
paulson@15093
   689
apply (simp add: psize_def [of "(%x. D (x + n))"]);
paulson@15093
   690
apply (rule_tac a = "psize D - n" in someI2, auto)
paulson@15093
   691
  apply (simp add: partition less_diff_conv)
paulson@15093
   692
 apply (case_tac "psize D \<le> n")
paulson@15093
   693
  apply (force intro: partition_rhs2 simp add: le_diff_conv)
paulson@15093
   694
 apply (simp add: partition le_diff_conv)
paulson@15093
   695
apply (rule ccontr, drule not_leE)
paulson@15093
   696
apply (drule_tac x = "psize D" in spec)
paulson@15093
   697
apply (simp add: partition)
paulson@15093
   698
done
paulson@15093
   699
paulson@15093
   700
lemma lemma_psize_right_eq:
paulson@15093
   701
     "[| partition(a,b) D |] ==> psize (%x. D (x + n)) \<le> psize D"
paulson@15219
   702
apply (frule_tac r1 = n in partition_ub [THEN order_le_imp_less_or_eq])
paulson@15093
   703
apply (blast intro: lemma_psize_right_eq1a lemma_psize_right_eq1)
paulson@15093
   704
done
paulson@15093
   705
paulson@15093
   706
lemma tpart_left1:
paulson@15093
   707
     "[| a \<le> D n; tpart (a, b) (D, p) |]
paulson@15093
   708
      ==> tpart(a, D n) (%x. if D x < D n then D(x) else D n,
paulson@15093
   709
          %x. if D x < D n then p(x) else D n)"
paulson@15093
   710
apply (frule_tac r = n in tpart_partition [THEN partition_ub])
paulson@15219
   711
apply (drule_tac x = "D n" in order_le_imp_less_or_eq)
paulson@15093
   712
apply (auto simp add: tpart_partition [THEN lemma_partition_eq, symmetric] tpart_tag_eq [symmetric])
paulson@15093
   713
apply (frule_tac tpart_partition [THEN [3] lemma_additivity1])
paulson@15093
   714
apply (auto simp add: tpart_def)
paulson@15219
   715
apply (drule_tac [2] linorder_not_less [THEN iffD1, THEN order_le_imp_less_or_eq], auto)
paulson@15219
   716
  prefer 3 apply (drule_tac x=na in spec, arith)
paulson@15093
   717
 prefer 2 apply (blast dest: lemma_additivity3)
paulson@15219
   718
apply (frule (2) lemma_additivity4_psize_eq)
paulson@15093
   719
apply (rule partition [THEN iffD2])
paulson@15093
   720
apply (frule partition [THEN iffD1])
paulson@15219
   721
apply safe 
paulson@15219
   722
apply (auto simp add: partition_lt_gen)  
nipkow@15197
   723
apply (drule (1) partition_lt_cancel, arith)
paulson@15093
   724
done
paulson@15093
   725
paulson@15093
   726
lemma fine_left1:
paulson@15093
   727
     "[| a \<le> D n; tpart (a, b) (D, p); gauge (%x. a \<le> x & x \<le> D n) g;
paulson@15093
   728
         fine (%x. if x < D n then min (g x) ((D n - x)/ 2)
paulson@15093
   729
                 else if x = D n then min (g (D n)) (ga (D n))
paulson@15093
   730
                      else min (ga x) ((x - D n)/ 2)) (D, p) |]
paulson@15093
   731
      ==> fine g
paulson@15093
   732
           (%x. if D x < D n then D(x) else D n,
paulson@15093
   733
            %x. if D x < D n then p(x) else D n)"
paulson@15093
   734
apply (auto simp add: fine_def tpart_def gauge_def)
paulson@15093
   735
apply (frule_tac [!] na=na in lemma_psize_left_less_psize2)
paulson@15093
   736
apply (drule_tac [!] x = na in spec, auto)
paulson@15093
   737
apply (drule_tac [!] x = na in spec, auto)
paulson@15093
   738
apply (auto dest: lemma_additivity3a simp add: split_if_asm)
paulson@15093
   739
done
paulson@15093
   740
paulson@15093
   741
lemma tpart_right1:
paulson@15093
   742
     "[| a \<le> D n; tpart (a, b) (D, p) |]
paulson@15093
   743
      ==> tpart(D n, b) (%x. D(x + n),%x. p(x + n))"
paulson@15093
   744
apply (simp add: tpart_def partition_def, safe)
paulson@15093
   745
apply (rule_tac x = "N - n" in exI, auto)
paulson@15093
   746
done
paulson@15093
   747
paulson@15093
   748
lemma fine_right1:
paulson@15093
   749
     "[| a \<le> D n; tpart (a, b) (D, p); gauge (%x. D n \<le> x & x \<le> b) ga;
paulson@15093
   750
         fine (%x. if x < D n then min (g x) ((D n - x)/ 2)
paulson@15093
   751
                 else if x = D n then min (g (D n)) (ga (D n))
paulson@15093
   752
                      else min (ga x) ((x - D n)/ 2)) (D, p) |]
paulson@15093
   753
      ==> fine ga (%x. D(x + n),%x. p(x + n))"
paulson@15093
   754
apply (auto simp add: fine_def gauge_def)
paulson@15093
   755
apply (drule_tac x = "na + n" in spec)
webertj@20217
   756
apply (frule_tac n = n in tpart_partition [THEN better_lemma_psize_right_eq], auto)
paulson@15093
   757
apply (simp add: tpart_def, safe)
paulson@15094
   758
apply (subgoal_tac "D n \<le> p (na + n)")
paulson@15219
   759
apply (drule_tac y = "p (na + n)" in order_le_imp_less_or_eq)
paulson@15093
   760
apply safe
paulson@15093
   761
apply (simp split: split_if_asm, simp)
paulson@15093
   762
apply (drule less_le_trans, assumption)
paulson@15093
   763
apply (rotate_tac 5)
paulson@15093
   764
apply (drule_tac x = "na + n" in spec, safe)
paulson@15093
   765
apply (rule_tac y="D (na + n)" in order_trans)
paulson@15093
   766
apply (case_tac "na = 0", auto)
chaieb@23315
   767
apply (erule partition_lt_gen [THEN order_less_imp_le])
chaieb@23315
   768
apply arith
chaieb@23315
   769
apply arith
paulson@15093
   770
done
paulson@15093
   771
paulson@15093
   772
lemma rsum_add: "rsum (D, p) (%x. f x + g x) =  rsum (D, p) f + rsum(D, p) g"
nipkow@15536
   773
by (simp add: rsum_def setsum_addf left_distrib)
paulson@15093
   774
paulson@15094
   775
text{* Bartle/Sherbert: Theorem 10.1.5 p. 278 *}
paulson@15093
   776
lemma Integral_add_fun:
paulson@15093
   777
    "[| a \<le> b; Integral(a,b) f k1; Integral(a,b) g k2 |]
paulson@15093
   778
     ==> Integral(a,b) (%x. f x + g x) (k1 + k2)"
paulson@15093
   779
apply (simp add: Integral_def, auto)
paulson@15093
   780
apply ((drule_tac x = "e/2" in spec)+)
paulson@15093
   781
apply auto
paulson@15093
   782
apply (drule gauge_min, assumption)
paulson@15094
   783
apply (rule_tac x = " (%x. if ga x < gaa x then ga x else gaa x)" in exI)
paulson@15093
   784
apply auto
paulson@15093
   785
apply (drule fine_min)
paulson@15093
   786
apply ((drule spec)+, auto)
paulson@15093
   787
apply (drule_tac a = "\<bar>rsum (D, p) f - k1\<bar> * 2" and c = "\<bar>rsum (D, p) g - k2\<bar> * 2" in add_strict_mono, assumption)
paulson@15093
   788
apply (auto simp only: rsum_add left_distrib [symmetric]
webertj@20217
   789
                mult_2_right [symmetric] real_mult_less_iff1)
paulson@15093
   790
done
paulson@15093
   791
paulson@15093
   792
lemma partition_lt_gen2:
paulson@15093
   793
     "[| partition(a,b) D; r < psize D |] ==> 0 < D (Suc r) - D r"
paulson@15093
   794
by (auto simp add: partition)
paulson@15093
   795
paulson@15093
   796
lemma lemma_Integral_le:
paulson@15093
   797
     "[| \<forall>x. a \<le> x & x \<le> b --> f x \<le> g x;
paulson@15093
   798
         tpart(a,b) (D,p)
nipkow@15360
   799
      |] ==> \<forall>n \<le> psize D. f (p n) \<le> g (p n)"
paulson@15093
   800
apply (simp add: tpart_def)
paulson@15093
   801
apply (auto, frule partition [THEN iffD1], auto)
paulson@15093
   802
apply (drule_tac x = "p n" in spec, auto)
paulson@15093
   803
apply (case_tac "n = 0", simp)
paulson@15093
   804
apply (rule partition_lt_gen [THEN order_less_le_trans, THEN order_less_imp_le], auto)
paulson@15093
   805
apply (drule le_imp_less_or_eq, auto)
paulson@15093
   806
apply (drule_tac [2] x = "psize D" in spec, auto)
paulson@15093
   807
apply (drule_tac r = "Suc n" in partition_ub)
paulson@15093
   808
apply (drule_tac x = n in spec, auto)
paulson@15093
   809
done
paulson@15093
   810
paulson@15093
   811
lemma lemma_Integral_rsum_le:
paulson@15093
   812
     "[| \<forall>x. a \<le> x & x \<le> b --> f x \<le> g x;
paulson@15093
   813
         tpart(a,b) (D,p)
paulson@15093
   814
      |] ==> rsum(D,p) f \<le> rsum(D,p) g"
paulson@15093
   815
apply (simp add: rsum_def)
nipkow@15539
   816
apply (auto intro!: setsum_mono dest: tpart_partition [THEN partition_lt_gen2]
paulson@15093
   817
               dest!: lemma_Integral_le)
paulson@15093
   818
done
paulson@15093
   819
paulson@15093
   820
lemma Integral_le:
paulson@15093
   821
    "[| a \<le> b;
paulson@15093
   822
        \<forall>x. a \<le> x & x \<le> b --> f(x) \<le> g(x);
paulson@15093
   823
        Integral(a,b) f k1; Integral(a,b) g k2
paulson@15093
   824
     |] ==> k1 \<le> k2"
paulson@15093
   825
apply (simp add: Integral_def)
paulson@15093
   826
apply (rotate_tac 2)
paulson@15093
   827
apply (drule_tac x = "\<bar>k1 - k2\<bar> /2" in spec)
paulson@15221
   828
apply (drule_tac x = "\<bar>k1 - k2\<bar> /2" in spec, auto)
paulson@15093
   829
apply (drule gauge_min, assumption)
paulson@15093
   830
apply (drule_tac g = "%x. if ga x < gaa x then ga x else gaa x" 
paulson@15093
   831
       in partition_exists, assumption, auto)
paulson@15093
   832
apply (drule fine_min)
paulson@15093
   833
apply (drule_tac x = D in spec, drule_tac x = D in spec)
paulson@15093
   834
apply (drule_tac x = p in spec, drule_tac x = p in spec, auto)
paulson@15093
   835
apply (frule lemma_Integral_rsum_le, assumption)
paulson@15094
   836
apply (subgoal_tac "\<bar>(rsum (D,p) f - k1) - (rsum (D,p) g - k2)\<bar> < \<bar>k1 - k2\<bar>")
paulson@15093
   837
apply arith
paulson@15093
   838
apply (drule add_strict_mono, assumption)
paulson@15093
   839
apply (auto simp only: left_distrib [symmetric] mult_2_right [symmetric]
webertj@20217
   840
                       real_mult_less_iff1)
paulson@15093
   841
done
paulson@15093
   842
paulson@15093
   843
lemma Integral_imp_Cauchy:
paulson@15093
   844
     "(\<exists>k. Integral(a,b) f k) ==>
nipkow@15360
   845
      (\<forall>e > 0. \<exists>g. gauge (%x. a \<le> x & x \<le> b) g &
paulson@15093
   846
                       (\<forall>D1 D2 p1 p2.
paulson@15093
   847
                            tpart(a,b) (D1, p1) & fine g (D1,p1) &
paulson@15093
   848
                            tpart(a,b) (D2, p2) & fine g (D2,p2) -->
nipkow@15360
   849
                            \<bar>rsum(D1,p1) f - rsum(D2,p2) f\<bar> < e))"
paulson@15093
   850
apply (simp add: Integral_def, auto)
paulson@15093
   851
apply (drule_tac x = "e/2" in spec, auto)
paulson@15093
   852
apply (rule exI, auto)
paulson@15093
   853
apply (frule_tac x = D1 in spec)
paulson@15093
   854
apply (frule_tac x = D2 in spec)
paulson@15093
   855
apply ((drule spec)+, auto)
paulson@15093
   856
apply (erule_tac V = "0 < e" in thin_rl)
paulson@15093
   857
apply (drule add_strict_mono, assumption)
paulson@15093
   858
apply (auto simp only: left_distrib [symmetric] mult_2_right [symmetric]
webertj@20217
   859
                       real_mult_less_iff1)
paulson@15093
   860
done
paulson@15093
   861
paulson@15093
   862
lemma Cauchy_iff2:
paulson@15093
   863
     "Cauchy X =
huffman@20563
   864
      (\<forall>j. (\<exists>M. \<forall>m \<ge> M. \<forall>n \<ge> M. \<bar>X m - X n\<bar> < inverse(real (Suc j))))"
paulson@15093
   865
apply (simp add: Cauchy_def, auto)
paulson@15093
   866
apply (drule reals_Archimedean, safe)
paulson@15093
   867
apply (drule_tac x = n in spec, auto)
paulson@15093
   868
apply (rule_tac x = M in exI, auto)
nipkow@15360
   869
apply (drule_tac x = m in spec, simp)
paulson@15093
   870
apply (drule_tac x = na in spec, auto)
paulson@15093
   871
done
paulson@15093
   872
paulson@15093
   873
lemma partition_exists2:
paulson@15093
   874
     "[| a \<le> b; \<forall>n. gauge (%x. a \<le> x & x \<le> b) (fa n) |]
paulson@15093
   875
      ==> \<forall>n. \<exists>D p. tpart (a, b) (D, p) & fine (fa n) (D, p)"
paulson@15219
   876
by (blast dest: partition_exists) 
paulson@15093
   877
paulson@15093
   878
lemma monotonic_anti_derivative:
huffman@20792
   879
  fixes f g :: "real => real" shows
paulson@15093
   880
     "[| a \<le> b; \<forall>c. a \<le> c & c \<le> b --> f' c \<le> g' c;
paulson@15093
   881
         \<forall>x. DERIV f x :> f' x; \<forall>x. DERIV g x :> g' x |]
paulson@15093
   882
      ==> f b - f a \<le> g b - g a"
paulson@15093
   883
apply (rule Integral_le, assumption)
paulson@15219
   884
apply (auto intro: FTC1) 
paulson@15093
   885
done
paulson@15093
   886
paulson@15093
   887
end