src/HOL/Probability/Caratheodory.thy
author hoelzl
Wed Feb 02 12:34:45 2011 +0100 (2011-02-02)
changeset 41689 3e39b0e730d6
parent 41023 9118eb4eb8dc
child 41981 cdf7693bbe08
permissions -rw-r--r--
the measure valuation is again part of the measure_space type, instead of an explicit parameter to the locale;
changed syntax for simple_function, simple_integral, positive_integral, integral and RN_deriv.
introduced binder variants for simple_integral, positive_integral and integral.
     1 header {*Caratheodory Extension Theorem*}
     2 
     3 theory Caratheodory
     4   imports Sigma_Algebra Positive_Extended_Real
     5 begin
     6 
     7 text{*From the Hurd/Coble measure theory development, translated by Lawrence Paulson.*}
     8 
     9 subsection {* Measure Spaces *}
    10 
    11 record 'a measure_space = "'a algebra" +
    12   measure :: "'a set \<Rightarrow> pextreal"
    13 
    14 definition positive where "positive M f \<longleftrightarrow> f {} = (0::pextreal)"
    15   -- "Positive is enforced by the type"
    16 
    17 definition additive where "additive M f \<longleftrightarrow>
    18   (\<forall>x \<in> sets M. \<forall>y \<in> sets M. x \<inter> y = {} \<longrightarrow> f (x \<union> y) = f x + f y)"
    19 
    20 definition countably_additive where "countably_additive M f \<longleftrightarrow>
    21   (\<forall>A. range A \<subseteq> sets M \<longrightarrow> disjoint_family A \<longrightarrow> (\<Union>i. A i) \<in> sets M \<longrightarrow>
    22     (\<Sum>\<^isub>\<infinity> n. f (A n)) = f (\<Union>i. A i))"
    23 
    24 definition increasing where "increasing M f \<longleftrightarrow>
    25   (\<forall>x \<in> sets M. \<forall>y \<in> sets M. x \<subseteq> y \<longrightarrow> f x \<le> f y)"
    26 
    27 definition subadditive where "subadditive M f \<longleftrightarrow>
    28   (\<forall>x \<in> sets M. \<forall>y \<in> sets M. x \<inter> y = {} \<longrightarrow>
    29     f (x \<union> y) \<le> f x + f y)"
    30 
    31 definition countably_subadditive where "countably_subadditive M f \<longleftrightarrow>
    32   (\<forall>A. range A \<subseteq> sets M \<longrightarrow> disjoint_family A \<longrightarrow> (\<Union>i. A i) \<in> sets M \<longrightarrow>
    33     f (\<Union>i. A i) \<le> (\<Sum>\<^isub>\<infinity> n. f (A n)))"
    34 
    35 definition lambda_system where "lambda_system M f = {l \<in> sets M.
    36   \<forall>x \<in> sets M. f (l \<inter> x) + f ((space M - l) \<inter> x) = f x}"
    37 
    38 definition outer_measure_space where "outer_measure_space M f \<longleftrightarrow>
    39   positive M f \<and> increasing M f \<and> countably_subadditive M f"
    40 
    41 definition measure_set where "measure_set M f X = {r.
    42   \<exists>A. range A \<subseteq> sets M \<and> disjoint_family A \<and> X \<subseteq> (\<Union>i. A i) \<and> (\<Sum>\<^isub>\<infinity> i. f (A i)) = r}"
    43 
    44 locale measure_space = sigma_algebra M for M :: "('a, 'b) measure_space_scheme" +
    45   assumes empty_measure [simp]: "measure M {} = 0"
    46       and ca: "countably_additive M (measure M)"
    47 
    48 abbreviation (in measure_space) "\<mu> \<equiv> measure M"
    49 
    50 lemma increasingD:
    51   "increasing M f \<Longrightarrow> x \<subseteq> y \<Longrightarrow> x\<in>sets M \<Longrightarrow> y\<in>sets M \<Longrightarrow> f x \<le> f y"
    52   by (auto simp add: increasing_def)
    53 
    54 lemma subadditiveD:
    55   "subadditive M f \<Longrightarrow> x \<inter> y = {} \<Longrightarrow> x \<in> sets M \<Longrightarrow> y \<in> sets M
    56     \<Longrightarrow> f (x \<union> y) \<le> f x + f y"
    57   by (auto simp add: subadditive_def)
    58 
    59 lemma additiveD:
    60   "additive M f \<Longrightarrow> x \<inter> y = {} \<Longrightarrow> x \<in> sets M \<Longrightarrow> y \<in> sets M
    61     \<Longrightarrow> f (x \<union> y) = f x + f y"
    62   by (auto simp add: additive_def)
    63 
    64 lemma countably_additiveD:
    65   "countably_additive M f \<Longrightarrow> range A \<subseteq> sets M \<Longrightarrow> disjoint_family A
    66     \<Longrightarrow> (\<Union>i. A i) \<in> sets M \<Longrightarrow> (\<Sum>\<^isub>\<infinity> n. f (A n)) = f (\<Union>i. A i)"
    67   by (simp add: countably_additive_def)
    68 
    69 lemma countably_subadditiveD:
    70   "countably_subadditive M f \<Longrightarrow> range A \<subseteq> sets M \<Longrightarrow> disjoint_family A \<Longrightarrow>
    71    (\<Union>i. A i) \<in> sets M \<Longrightarrow> f (\<Union>i. A i) \<le> psuminf (f o A)"
    72   by (auto simp add: countably_subadditive_def o_def)
    73 
    74 lemma countably_additiveI:
    75   "(\<And>A. range A \<subseteq> sets M \<Longrightarrow> disjoint_family A \<Longrightarrow> (\<Union>i. A i) \<in> sets M
    76     \<Longrightarrow> (\<Sum>\<^isub>\<infinity> n. f (A n)) = f (\<Union>i. A i)) \<Longrightarrow> countably_additive M f"
    77   by (simp add: countably_additive_def)
    78 
    79 section "Extend binary sets"
    80 
    81 lemma LIMSEQ_binaryset:
    82   assumes f: "f {} = 0"
    83   shows  "(\<lambda>n. \<Sum>i = 0..<n. f (binaryset A B i)) ----> f A + f B"
    84 proof -
    85   have "(\<lambda>n. \<Sum>i = 0..< Suc (Suc n). f (binaryset A B i)) = (\<lambda>n. f A + f B)"
    86     proof
    87       fix n
    88       show "(\<Sum>i\<Colon>nat = 0\<Colon>nat..<Suc (Suc n). f (binaryset A B i)) = f A + f B"
    89         by (induct n)  (auto simp add: binaryset_def f)
    90     qed
    91   moreover
    92   have "... ----> f A + f B" by (rule LIMSEQ_const)
    93   ultimately
    94   have "(\<lambda>n. \<Sum>i = 0..< Suc (Suc n). f (binaryset A B i)) ----> f A + f B"
    95     by metis
    96   hence "(\<lambda>n. \<Sum>i = 0..< n+2. f (binaryset A B i)) ----> f A + f B"
    97     by simp
    98   thus ?thesis by (rule LIMSEQ_offset [where k=2])
    99 qed
   100 
   101 lemma binaryset_sums:
   102   assumes f: "f {} = 0"
   103   shows  "(\<lambda>n. f (binaryset A B n)) sums (f A + f B)"
   104     by (simp add: sums_def LIMSEQ_binaryset [where f=f, OF f])
   105 
   106 lemma suminf_binaryset_eq:
   107   fixes f :: "'a set \<Rightarrow> real"
   108   shows "f {} = 0 \<Longrightarrow> (\<Sum>n. f (binaryset A B n)) = f A + f B"
   109   by (metis binaryset_sums sums_unique)
   110 
   111 lemma binaryset_psuminf:
   112   assumes "f {} = 0"
   113   shows "(\<Sum>\<^isub>\<infinity> n. f (binaryset A B n)) = f A + f B" (is "?suminf = ?sum")
   114 proof -
   115   have *: "{..<2} = {0, 1::nat}" by auto
   116   have "\<forall>n\<ge>2. f (binaryset A B n) = 0"
   117     unfolding binaryset_def
   118     using assms by auto
   119   hence "?suminf = (\<Sum>N<2. f (binaryset A B N))"
   120     by (rule psuminf_finite)
   121   also have "... = ?sum" unfolding * binaryset_def
   122     by simp
   123   finally show ?thesis .
   124 qed
   125 
   126 subsection {* Lambda Systems *}
   127 
   128 lemma (in algebra) lambda_system_eq:
   129   shows "lambda_system M f = {l \<in> sets M.
   130     \<forall>x \<in> sets M. f (x \<inter> l) + f (x - l) = f x}"
   131 proof -
   132   have [simp]: "!!l x. l \<in> sets M \<Longrightarrow> x \<in> sets M \<Longrightarrow> (space M - l) \<inter> x = x - l"
   133     by (metis Int_Diff Int_absorb1 Int_commute sets_into_space)
   134   show ?thesis
   135     by (auto simp add: lambda_system_def) (metis Int_commute)+
   136 qed
   137 
   138 lemma (in algebra) lambda_system_empty:
   139   "positive M f \<Longrightarrow> {} \<in> lambda_system M f"
   140   by (auto simp add: positive_def lambda_system_eq algebra_def)
   141 
   142 lemma lambda_system_sets:
   143   "x \<in> lambda_system M f \<Longrightarrow> x \<in> sets M"
   144   by (simp add: lambda_system_def)
   145 
   146 lemma (in algebra) lambda_system_Compl:
   147   fixes f:: "'a set \<Rightarrow> pextreal"
   148   assumes x: "x \<in> lambda_system M f"
   149   shows "space M - x \<in> lambda_system M f"
   150 proof -
   151   have "x \<subseteq> space M"
   152     by (metis sets_into_space lambda_system_sets x)
   153   hence "space M - (space M - x) = x"
   154     by (metis double_diff equalityE)
   155   with x show ?thesis
   156     by (force simp add: lambda_system_def ac_simps)
   157 qed
   158 
   159 lemma (in algebra) lambda_system_Int:
   160   fixes f:: "'a set \<Rightarrow> pextreal"
   161   assumes xl: "x \<in> lambda_system M f" and yl: "y \<in> lambda_system M f"
   162   shows "x \<inter> y \<in> lambda_system M f"
   163 proof -
   164   from xl yl show ?thesis
   165   proof (auto simp add: positive_def lambda_system_eq Int)
   166     fix u
   167     assume x: "x \<in> sets M" and y: "y \<in> sets M" and u: "u \<in> sets M"
   168        and fx: "\<forall>z\<in>sets M. f (z \<inter> x) + f (z - x) = f z"
   169        and fy: "\<forall>z\<in>sets M. f (z \<inter> y) + f (z - y) = f z"
   170     have "u - x \<inter> y \<in> sets M"
   171       by (metis Diff Diff_Int Un u x y)
   172     moreover
   173     have "(u - (x \<inter> y)) \<inter> y = u \<inter> y - x" by blast
   174     moreover
   175     have "u - x \<inter> y - y = u - y" by blast
   176     ultimately
   177     have ey: "f (u - x \<inter> y) = f (u \<inter> y - x) + f (u - y)" using fy
   178       by force
   179     have "f (u \<inter> (x \<inter> y)) + f (u - x \<inter> y)
   180           = (f (u \<inter> (x \<inter> y)) + f (u \<inter> y - x)) + f (u - y)"
   181       by (simp add: ey ac_simps)
   182     also have "... =  (f ((u \<inter> y) \<inter> x) + f (u \<inter> y - x)) + f (u - y)"
   183       by (simp add: Int_ac)
   184     also have "... = f (u \<inter> y) + f (u - y)"
   185       using fx [THEN bspec, of "u \<inter> y"] Int y u
   186       by force
   187     also have "... = f u"
   188       by (metis fy u)
   189     finally show "f (u \<inter> (x \<inter> y)) + f (u - x \<inter> y) = f u" .
   190   qed
   191 qed
   192 
   193 lemma (in algebra) lambda_system_Un:
   194   fixes f:: "'a set \<Rightarrow> pextreal"
   195   assumes xl: "x \<in> lambda_system M f" and yl: "y \<in> lambda_system M f"
   196   shows "x \<union> y \<in> lambda_system M f"
   197 proof -
   198   have "(space M - x) \<inter> (space M - y) \<in> sets M"
   199     by (metis Diff_Un Un compl_sets lambda_system_sets xl yl)
   200   moreover
   201   have "x \<union> y = space M - ((space M - x) \<inter> (space M - y))"
   202     by auto  (metis subsetD lambda_system_sets sets_into_space xl yl)+
   203   ultimately show ?thesis
   204     by (metis lambda_system_Compl lambda_system_Int xl yl)
   205 qed
   206 
   207 lemma (in algebra) lambda_system_algebra:
   208   "positive M f \<Longrightarrow> algebra (M\<lparr>sets := lambda_system M f\<rparr>)"
   209   apply (auto simp add: algebra_def)
   210   apply (metis lambda_system_sets set_mp sets_into_space)
   211   apply (metis lambda_system_empty)
   212   apply (metis lambda_system_Compl)
   213   apply (metis lambda_system_Un)
   214   done
   215 
   216 lemma (in algebra) lambda_system_strong_additive:
   217   assumes z: "z \<in> sets M" and disj: "x \<inter> y = {}"
   218       and xl: "x \<in> lambda_system M f" and yl: "y \<in> lambda_system M f"
   219   shows "f (z \<inter> (x \<union> y)) = f (z \<inter> x) + f (z \<inter> y)"
   220 proof -
   221   have "z \<inter> x = (z \<inter> (x \<union> y)) \<inter> x" using disj by blast
   222   moreover
   223   have "z \<inter> y = (z \<inter> (x \<union> y)) - x" using disj by blast
   224   moreover
   225   have "(z \<inter> (x \<union> y)) \<in> sets M"
   226     by (metis Int Un lambda_system_sets xl yl z)
   227   ultimately show ?thesis using xl yl
   228     by (simp add: lambda_system_eq)
   229 qed
   230 
   231 lemma (in algebra) lambda_system_additive:
   232      "additive (M (|sets := lambda_system M f|)) f"
   233 proof (auto simp add: additive_def)
   234   fix x and y
   235   assume disj: "x \<inter> y = {}"
   236      and xl: "x \<in> lambda_system M f" and yl: "y \<in> lambda_system M f"
   237   hence  "x \<in> sets M" "y \<in> sets M" by (blast intro: lambda_system_sets)+
   238   thus "f (x \<union> y) = f x + f y"
   239     using lambda_system_strong_additive [OF top disj xl yl]
   240     by (simp add: Un)
   241 qed
   242 
   243 lemma (in algebra) countably_subadditive_subadditive:
   244   assumes f: "positive M f" and cs: "countably_subadditive M f"
   245   shows  "subadditive M f"
   246 proof (auto simp add: subadditive_def)
   247   fix x y
   248   assume x: "x \<in> sets M" and y: "y \<in> sets M" and "x \<inter> y = {}"
   249   hence "disjoint_family (binaryset x y)"
   250     by (auto simp add: disjoint_family_on_def binaryset_def)
   251   hence "range (binaryset x y) \<subseteq> sets M \<longrightarrow>
   252          (\<Union>i. binaryset x y i) \<in> sets M \<longrightarrow>
   253          f (\<Union>i. binaryset x y i) \<le> (\<Sum>\<^isub>\<infinity> n. f (binaryset x y n))"
   254     using cs by (simp add: countably_subadditive_def)
   255   hence "{x,y,{}} \<subseteq> sets M \<longrightarrow> x \<union> y \<in> sets M \<longrightarrow>
   256          f (x \<union> y) \<le> (\<Sum>\<^isub>\<infinity> n. f (binaryset x y n))"
   257     by (simp add: range_binaryset_eq UN_binaryset_eq)
   258   thus "f (x \<union> y) \<le>  f x + f y" using f x y
   259     by (auto simp add: Un o_def binaryset_psuminf positive_def)
   260 qed
   261 
   262 lemma (in algebra) additive_sum:
   263   fixes A:: "nat \<Rightarrow> 'a set"
   264   assumes f: "positive M f" and ad: "additive M f"
   265       and A: "range A \<subseteq> sets M"
   266       and disj: "disjoint_family A"
   267   shows  "setsum (f \<circ> A) {0..<n} = f (\<Union>i\<in>{0..<n}. A i)"
   268 proof (induct n)
   269   case 0 show ?case using f by (simp add: positive_def)
   270 next
   271   case (Suc n)
   272   have "A n \<inter> (\<Union>i\<in>{0..<n}. A i) = {}" using disj
   273     by (auto simp add: disjoint_family_on_def neq_iff) blast
   274   moreover
   275   have "A n \<in> sets M" using A by blast
   276   moreover have "(\<Union>i\<in>{0..<n}. A i) \<in> sets M"
   277     by (metis A UNION_in_sets atLeast0LessThan)
   278   moreover
   279   ultimately have "f (A n \<union> (\<Union>i\<in>{0..<n}. A i)) = f (A n) + f(\<Union>i\<in>{0..<n}. A i)"
   280     using ad UNION_in_sets A by (auto simp add: additive_def)
   281   with Suc.hyps show ?case using ad
   282     by (auto simp add: atLeastLessThanSuc additive_def)
   283 qed
   284 
   285 lemma (in algebra) increasing_additive_bound:
   286   fixes A:: "nat \<Rightarrow> 'a set" and  f :: "'a set \<Rightarrow> pextreal"
   287   assumes f: "positive M f" and ad: "additive M f"
   288       and inc: "increasing M f"
   289       and A: "range A \<subseteq> sets M"
   290       and disj: "disjoint_family A"
   291   shows  "psuminf (f \<circ> A) \<le> f (space M)"
   292 proof (safe intro!: psuminf_bound)
   293   fix N
   294   have "setsum (f \<circ> A) {0..<N} = f (\<Union>i\<in>{0..<N}. A i)"
   295     by (rule additive_sum [OF f ad A disj])
   296   also have "... \<le> f (space M)" using space_closed A
   297     by (blast intro: increasingD [OF inc] UNION_in_sets top)
   298   finally show "setsum (f \<circ> A) {..<N} \<le> f (space M)" by (simp add: atLeast0LessThan)
   299 qed
   300 
   301 lemma lambda_system_increasing:
   302  "increasing M f \<Longrightarrow> increasing (M (|sets := lambda_system M f|)) f"
   303   by (simp add: increasing_def lambda_system_def)
   304 
   305 lemma lambda_system_positive:
   306   "positive M f \<Longrightarrow> positive (M (|sets := lambda_system M f|)) f"
   307   by (simp add: positive_def lambda_system_def)
   308 
   309 lemma (in algebra) lambda_system_strong_sum:
   310   fixes A:: "nat \<Rightarrow> 'a set" and f :: "'a set \<Rightarrow> pextreal"
   311   assumes f: "positive M f" and a: "a \<in> sets M"
   312       and A: "range A \<subseteq> lambda_system M f"
   313       and disj: "disjoint_family A"
   314   shows  "(\<Sum>i = 0..<n. f (a \<inter>A i)) = f (a \<inter> (\<Union>i\<in>{0..<n}. A i))"
   315 proof (induct n)
   316   case 0 show ?case using f by (simp add: positive_def)
   317 next
   318   case (Suc n)
   319   have 2: "A n \<inter> UNION {0..<n} A = {}" using disj
   320     by (force simp add: disjoint_family_on_def neq_iff)
   321   have 3: "A n \<in> lambda_system M f" using A
   322     by blast
   323   have 4: "UNION {0..<n} A \<in> lambda_system M f"
   324     using A algebra.UNION_in_sets [OF local.lambda_system_algebra, of f, OF f]
   325     by simp
   326   from Suc.hyps show ?case
   327     by (simp add: atLeastLessThanSuc lambda_system_strong_additive [OF a 2 3 4])
   328 qed
   329 
   330 lemma (in sigma_algebra) lambda_system_caratheodory:
   331   assumes oms: "outer_measure_space M f"
   332       and A: "range A \<subseteq> lambda_system M f"
   333       and disj: "disjoint_family A"
   334   shows  "(\<Union>i. A i) \<in> lambda_system M f \<and> psuminf (f \<circ> A) = f (\<Union>i. A i)"
   335 proof -
   336   have pos: "positive M f" and inc: "increasing M f"
   337    and csa: "countably_subadditive M f"
   338     by (metis oms outer_measure_space_def)+
   339   have sa: "subadditive M f"
   340     by (metis countably_subadditive_subadditive csa pos)
   341   have A': "range A \<subseteq> sets (M(|sets := lambda_system M f|))" using A
   342     by simp
   343   have alg_ls: "algebra (M(|sets := lambda_system M f|))"
   344     by (rule lambda_system_algebra) (rule pos)
   345   have A'': "range A \<subseteq> sets M"
   346      by (metis A image_subset_iff lambda_system_sets)
   347 
   348   have U_in: "(\<Union>i. A i) \<in> sets M"
   349     by (metis A'' countable_UN)
   350   have U_eq: "f (\<Union>i. A i) = psuminf (f o A)"
   351   proof (rule antisym)
   352     show "f (\<Union>i. A i) \<le> psuminf (f \<circ> A)"
   353       by (rule countably_subadditiveD [OF csa A'' disj U_in])
   354     show "psuminf (f \<circ> A) \<le> f (\<Union>i. A i)"
   355       by (rule psuminf_bound, unfold atLeast0LessThan[symmetric])
   356          (metis algebra.additive_sum [OF alg_ls] pos disj UN_Un Un_UNIV_right
   357                 lambda_system_positive lambda_system_additive
   358                 subset_Un_eq increasingD [OF inc] A' A'' UNION_in_sets U_in)
   359   qed
   360   {
   361     fix a
   362     assume a [iff]: "a \<in> sets M"
   363     have "f (a \<inter> (\<Union>i. A i)) + f (a - (\<Union>i. A i)) = f a"
   364     proof -
   365       show ?thesis
   366       proof (rule antisym)
   367         have "range (\<lambda>i. a \<inter> A i) \<subseteq> sets M" using A''
   368           by blast
   369         moreover
   370         have "disjoint_family (\<lambda>i. a \<inter> A i)" using disj
   371           by (auto simp add: disjoint_family_on_def)
   372         moreover
   373         have "a \<inter> (\<Union>i. A i) \<in> sets M"
   374           by (metis Int U_in a)
   375         ultimately
   376         have "f (a \<inter> (\<Union>i. A i)) \<le> psuminf (f \<circ> (\<lambda>i. a \<inter> i) \<circ> A)"
   377           using countably_subadditiveD [OF csa, of "(\<lambda>i. a \<inter> A i)"]
   378           by (simp add: o_def)
   379         hence "f (a \<inter> (\<Union>i. A i)) + f (a - (\<Union>i. A i)) \<le>
   380             psuminf (f \<circ> (\<lambda>i. a \<inter> i) \<circ> A) + f (a - (\<Union>i. A i))"
   381           by (rule add_right_mono)
   382         moreover
   383         have "psuminf (f \<circ> (\<lambda>i. a \<inter> i) \<circ> A) + f (a - (\<Union>i. A i)) \<le> f a"
   384           proof (safe intro!: psuminf_bound_add)
   385             fix n
   386             have UNION_in: "(\<Union>i\<in>{0..<n}. A i) \<in> sets M"
   387               by (metis A'' UNION_in_sets)
   388             have le_fa: "f (UNION {0..<n} A \<inter> a) \<le> f a" using A''
   389               by (blast intro: increasingD [OF inc] A'' UNION_in_sets)
   390             have ls: "(\<Union>i\<in>{0..<n}. A i) \<in> lambda_system M f"
   391               using algebra.UNION_in_sets [OF lambda_system_algebra [of f, OF pos]]
   392               by (simp add: A)
   393             hence eq_fa: "f a = f (a \<inter> (\<Union>i\<in>{0..<n}. A i)) + f (a - (\<Union>i\<in>{0..<n}. A i))"
   394               by (simp add: lambda_system_eq UNION_in)
   395             have "f (a - (\<Union>i. A i)) \<le> f (a - (\<Union>i\<in>{0..<n}. A i))"
   396               by (blast intro: increasingD [OF inc] UNION_eq_Union_image
   397                                UNION_in U_in)
   398             thus "setsum (f \<circ> (\<lambda>i. a \<inter> i) \<circ> A) {..<n} + f (a - (\<Union>i. A i)) \<le> f a"
   399               by (simp add: lambda_system_strong_sum pos A disj eq_fa add_left_mono atLeast0LessThan[symmetric])
   400           qed
   401         ultimately show "f (a \<inter> (\<Union>i. A i)) + f (a - (\<Union>i. A i)) \<le> f a"
   402           by (rule order_trans)
   403       next
   404         have "f a \<le> f (a \<inter> (\<Union>i. A i) \<union> (a - (\<Union>i. A i)))"
   405           by (blast intro:  increasingD [OF inc] U_in)
   406         also have "... \<le>  f (a \<inter> (\<Union>i. A i)) + f (a - (\<Union>i. A i))"
   407           by (blast intro: subadditiveD [OF sa] U_in)
   408         finally show "f a \<le> f (a \<inter> (\<Union>i. A i)) + f (a - (\<Union>i. A i))" .
   409         qed
   410      qed
   411   }
   412   thus  ?thesis
   413     by (simp add: lambda_system_eq sums_iff U_eq U_in)
   414 qed
   415 
   416 lemma (in sigma_algebra) caratheodory_lemma:
   417   assumes oms: "outer_measure_space M f"
   418   shows "measure_space \<lparr> space = space M, sets = lambda_system M f, measure = f \<rparr>"
   419     (is "measure_space ?M")
   420 proof -
   421   have pos: "positive M f"
   422     by (metis oms outer_measure_space_def)
   423   have alg: "algebra ?M"
   424     using lambda_system_algebra [of f, OF pos]
   425     by (simp add: algebra_def)
   426   then moreover
   427   have "sigma_algebra ?M"
   428     using lambda_system_caratheodory [OF oms]
   429     by (simp add: sigma_algebra_disjoint_iff)
   430   moreover
   431   have "measure_space_axioms ?M"
   432     using pos lambda_system_caratheodory [OF oms]
   433     by (simp add: measure_space_axioms_def positive_def lambda_system_sets
   434                   countably_additive_def o_def)
   435   ultimately
   436   show ?thesis
   437     by intro_locales (auto simp add: sigma_algebra_def)
   438 qed
   439 
   440 lemma (in algebra) additive_increasing:
   441   assumes posf: "positive M f" and addf: "additive M f"
   442   shows "increasing M f"
   443 proof (auto simp add: increasing_def)
   444   fix x y
   445   assume xy: "x \<in> sets M" "y \<in> sets M" "x \<subseteq> y"
   446   have "f x \<le> f x + f (y-x)" ..
   447   also have "... = f (x \<union> (y-x))" using addf
   448     by (auto simp add: additive_def) (metis Diff_disjoint Un_Diff_cancel Diff xy(1,2))
   449   also have "... = f y"
   450     by (metis Un_Diff_cancel Un_absorb1 xy(3))
   451   finally show "f x \<le> f y" .
   452 qed
   453 
   454 lemma (in algebra) countably_additive_additive:
   455   assumes posf: "positive M f" and ca: "countably_additive M f"
   456   shows "additive M f"
   457 proof (auto simp add: additive_def)
   458   fix x y
   459   assume x: "x \<in> sets M" and y: "y \<in> sets M" and "x \<inter> y = {}"
   460   hence "disjoint_family (binaryset x y)"
   461     by (auto simp add: disjoint_family_on_def binaryset_def)
   462   hence "range (binaryset x y) \<subseteq> sets M \<longrightarrow>
   463          (\<Union>i. binaryset x y i) \<in> sets M \<longrightarrow>
   464          f (\<Union>i. binaryset x y i) = (\<Sum>\<^isub>\<infinity> n. f (binaryset x y n))"
   465     using ca
   466     by (simp add: countably_additive_def)
   467   hence "{x,y,{}} \<subseteq> sets M \<longrightarrow> x \<union> y \<in> sets M \<longrightarrow>
   468          f (x \<union> y) = (\<Sum>\<^isub>\<infinity> n. f (binaryset x y n))"
   469     by (simp add: range_binaryset_eq UN_binaryset_eq)
   470   thus "f (x \<union> y) = f x + f y" using posf x y
   471     by (auto simp add: Un binaryset_psuminf positive_def)
   472 qed
   473 
   474 lemma inf_measure_nonempty:
   475   assumes f: "positive M f" and b: "b \<in> sets M" and a: "a \<subseteq> b" "{} \<in> sets M"
   476   shows "f b \<in> measure_set M f a"
   477 proof -
   478   have "psuminf (f \<circ> (\<lambda>i. {})(0 := b)) = setsum (f \<circ> (\<lambda>i. {})(0 := b)) {..<1::nat}"
   479     by (rule psuminf_finite) (simp add: f[unfolded positive_def])
   480   also have "... = f b"
   481     by simp
   482   finally have "psuminf (f \<circ> (\<lambda>i. {})(0 := b)) = f b" .
   483   thus ?thesis using assms
   484     by (auto intro!: exI [of _ "(\<lambda>i. {})(0 := b)"]
   485              simp: measure_set_def disjoint_family_on_def split_if_mem2 comp_def)
   486 qed
   487 
   488 lemma (in algebra) inf_measure_agrees:
   489   assumes posf: "positive M f" and ca: "countably_additive M f"
   490       and s: "s \<in> sets M"
   491   shows "Inf (measure_set M f s) = f s"
   492   unfolding Inf_pextreal_def
   493 proof (safe intro!: Greatest_equality)
   494   fix z
   495   assume z: "z \<in> measure_set M f s"
   496   from this obtain A where
   497     A: "range A \<subseteq> sets M" and disj: "disjoint_family A"
   498     and "s \<subseteq> (\<Union>x. A x)" and si: "psuminf (f \<circ> A) = z"
   499     by (auto simp add: measure_set_def comp_def)
   500   hence seq: "s = (\<Union>i. A i \<inter> s)" by blast
   501   have inc: "increasing M f"
   502     by (metis additive_increasing ca countably_additive_additive posf)
   503   have sums: "psuminf (\<lambda>i. f (A i \<inter> s)) = f (\<Union>i. A i \<inter> s)"
   504     proof (rule countably_additiveD [OF ca])
   505       show "range (\<lambda>n. A n \<inter> s) \<subseteq> sets M" using A s
   506         by blast
   507       show "disjoint_family (\<lambda>n. A n \<inter> s)" using disj
   508         by (auto simp add: disjoint_family_on_def)
   509       show "(\<Union>i. A i \<inter> s) \<in> sets M" using A s
   510         by (metis UN_extend_simps(4) s seq)
   511     qed
   512   hence "f s = psuminf (\<lambda>i. f (A i \<inter> s))"
   513     using seq [symmetric] by (simp add: sums_iff)
   514   also have "... \<le> psuminf (f \<circ> A)"
   515     proof (rule psuminf_le)
   516       fix n show "f (A n \<inter> s) \<le> (f \<circ> A) n" using A s
   517         by (force intro: increasingD [OF inc])
   518     qed
   519   also have "... = z" by (rule si)
   520   finally show "f s \<le> z" .
   521 next
   522   fix y
   523   assume y: "\<forall>u \<in> measure_set M f s. y \<le> u"
   524   thus "y \<le> f s"
   525     by (blast intro: inf_measure_nonempty [of _ f, OF posf s subset_refl])
   526 qed
   527 
   528 lemma inf_measure_empty:
   529   assumes posf: "positive M f" "{} \<in> sets M"
   530   shows "Inf (measure_set M f {}) = 0"
   531 proof (rule antisym)
   532   show "Inf (measure_set M f {}) \<le> 0"
   533     by (metis complete_lattice_class.Inf_lower `{} \<in> sets M`
   534               inf_measure_nonempty[OF posf] subset_refl posf[unfolded positive_def])
   535 qed simp
   536 
   537 lemma (in algebra) inf_measure_positive:
   538   "positive M f \<Longrightarrow> positive M (\<lambda>x. Inf (measure_set M f x))"
   539   by (simp add: positive_def inf_measure_empty)
   540 
   541 lemma (in algebra) inf_measure_increasing:
   542   assumes posf: "positive M f"
   543   shows "increasing \<lparr> space = space M, sets = Pow (space M) \<rparr>
   544                     (\<lambda>x. Inf (measure_set M f x))"
   545 apply (auto simp add: increasing_def)
   546 apply (rule complete_lattice_class.Inf_greatest)
   547 apply (rule complete_lattice_class.Inf_lower)
   548 apply (clarsimp simp add: measure_set_def, rule_tac x=A in exI, blast)
   549 done
   550 
   551 
   552 lemma (in algebra) inf_measure_le:
   553   assumes posf: "positive M f" and inc: "increasing M f"
   554       and x: "x \<in> {r . \<exists>A. range A \<subseteq> sets M \<and> s \<subseteq> (\<Union>i. A i) \<and> psuminf (f \<circ> A) = r}"
   555   shows "Inf (measure_set M f s) \<le> x"
   556 proof -
   557   from x
   558   obtain A where A: "range A \<subseteq> sets M" and ss: "s \<subseteq> (\<Union>i. A i)"
   559              and xeq: "psuminf (f \<circ> A) = x"
   560     by auto
   561   have dA: "range (disjointed A) \<subseteq> sets M"
   562     by (metis A range_disjointed_sets)
   563   have "\<forall>n.(f o disjointed A) n \<le> (f \<circ> A) n" unfolding comp_def
   564     by (metis increasingD [OF inc] UNIV_I dA image_subset_iff disjointed_subset A comp_def)
   565   hence sda: "psuminf (f o disjointed A) \<le> psuminf (f \<circ> A)"
   566     by (blast intro: psuminf_le)
   567   hence ley: "psuminf (f o disjointed A) \<le> x"
   568     by (metis xeq)
   569   hence y: "psuminf (f o disjointed A) \<in> measure_set M f s"
   570     apply (auto simp add: measure_set_def)
   571     apply (rule_tac x="disjointed A" in exI)
   572     apply (simp add: disjoint_family_disjointed UN_disjointed_eq ss dA comp_def)
   573     done
   574   show ?thesis
   575     by (blast intro: y order_trans [OF _ ley] posf complete_lattice_class.Inf_lower)
   576 qed
   577 
   578 lemma (in algebra) inf_measure_close:
   579   assumes posf: "positive M f" and e: "0 < e" and ss: "s \<subseteq> (space M)"
   580   shows "\<exists>A. range A \<subseteq> sets M \<and> disjoint_family A \<and> s \<subseteq> (\<Union>i. A i) \<and>
   581                psuminf (f \<circ> A) \<le> Inf (measure_set M f s) + e"
   582 proof (cases "Inf (measure_set M f s) = \<omega>")
   583   case False
   584   obtain l where "l \<in> measure_set M f s" "l \<le> Inf (measure_set M f s) + e"
   585     using Inf_close[OF False e] by auto
   586   thus ?thesis
   587     by (auto intro!: exI[of _ l] simp: measure_set_def comp_def)
   588 next
   589   case True
   590   have "measure_set M f s \<noteq> {}"
   591     by (metis emptyE ss inf_measure_nonempty [of _ f, OF posf top _ empty_sets])
   592   then obtain l where "l \<in> measure_set M f s" by auto
   593   moreover from True have "l \<le> Inf (measure_set M f s) + e" by simp
   594   ultimately show ?thesis
   595     by (auto intro!: exI[of _ l] simp: measure_set_def comp_def)
   596 qed
   597 
   598 lemma (in algebra) inf_measure_countably_subadditive:
   599   assumes posf: "positive M f" and inc: "increasing M f"
   600   shows "countably_subadditive (| space = space M, sets = Pow (space M) |)
   601                   (\<lambda>x. Inf (measure_set M f x))"
   602   unfolding countably_subadditive_def o_def
   603 proof (safe, simp, rule pextreal_le_epsilon)
   604   fix A :: "nat \<Rightarrow> 'a set" and e :: pextreal
   605 
   606   let "?outer n" = "Inf (measure_set M f (A n))"
   607   assume A: "range A \<subseteq> Pow (space M)"
   608      and disj: "disjoint_family A"
   609      and sb: "(\<Union>i. A i) \<subseteq> space M"
   610      and e: "0 < e"
   611   hence "\<exists>BB. \<forall>n. range (BB n) \<subseteq> sets M \<and> disjoint_family (BB n) \<and>
   612                    A n \<subseteq> (\<Union>i. BB n i) \<and>
   613                    psuminf (f o BB n) \<le> ?outer n + e * (1/2)^(Suc n)"
   614     apply (safe intro!: choice inf_measure_close [of f, OF posf _])
   615     using e sb by (cases e, auto simp add: not_le mult_pos_pos)
   616   then obtain BB
   617     where BB: "\<And>n. (range (BB n) \<subseteq> sets M)"
   618       and disjBB: "\<And>n. disjoint_family (BB n)"
   619       and sbBB: "\<And>n. A n \<subseteq> (\<Union>i. BB n i)"
   620       and BBle: "\<And>n. psuminf (f o BB n) \<le> ?outer n + e * (1/2)^(Suc n)"
   621     by auto blast
   622   have sll: "(\<Sum>\<^isub>\<infinity> n. psuminf (f o BB n)) \<le> psuminf ?outer + e"
   623     proof -
   624       have "(\<Sum>\<^isub>\<infinity> n. psuminf (f o BB n)) \<le> (\<Sum>\<^isub>\<infinity> n. ?outer n + e*(1/2) ^ Suc n)"
   625         by (rule psuminf_le[OF BBle])
   626       also have "... = psuminf ?outer + e"
   627         using psuminf_half_series by simp
   628       finally show ?thesis .
   629     qed
   630   def C \<equiv> "(split BB) o prod_decode"
   631   have C: "!!n. C n \<in> sets M"
   632     apply (rule_tac p="prod_decode n" in PairE)
   633     apply (simp add: C_def)
   634     apply (metis BB subsetD rangeI)
   635     done
   636   have sbC: "(\<Union>i. A i) \<subseteq> (\<Union>i. C i)"
   637     proof (auto simp add: C_def)
   638       fix x i
   639       assume x: "x \<in> A i"
   640       with sbBB [of i] obtain j where "x \<in> BB i j"
   641         by blast
   642       thus "\<exists>i. x \<in> split BB (prod_decode i)"
   643         by (metis prod_encode_inverse prod.cases)
   644     qed
   645   have "(f \<circ> C) = (f \<circ> (\<lambda>(x, y). BB x y)) \<circ> prod_decode"
   646     by (rule ext)  (auto simp add: C_def)
   647   moreover have "psuminf ... = (\<Sum>\<^isub>\<infinity> n. psuminf (f o BB n))" using BBle
   648     by (force intro!: psuminf_2dimen simp: o_def)
   649   ultimately have Csums: "psuminf (f \<circ> C) = (\<Sum>\<^isub>\<infinity> n. psuminf (f o BB n))" by simp
   650   have "Inf (measure_set M f (\<Union>i. A i)) \<le> (\<Sum>\<^isub>\<infinity> n. psuminf (f o BB n))"
   651     apply (rule inf_measure_le [OF posf(1) inc], auto)
   652     apply (rule_tac x="C" in exI)
   653     apply (auto simp add: C sbC Csums)
   654     done
   655   also have "... \<le> (\<Sum>\<^isub>\<infinity>n. Inf (measure_set M f (A n))) + e" using sll
   656     by blast
   657   finally show "Inf (measure_set M f (\<Union>i. A i)) \<le> psuminf ?outer + e" .
   658 qed
   659 
   660 lemma (in algebra) inf_measure_outer:
   661   "\<lbrakk> positive M f ; increasing M f \<rbrakk>
   662    \<Longrightarrow> outer_measure_space \<lparr> space = space M, sets = Pow (space M) \<rparr>
   663                           (\<lambda>x. Inf (measure_set M f x))"
   664   by (simp add: outer_measure_space_def inf_measure_empty
   665                 inf_measure_increasing inf_measure_countably_subadditive positive_def)
   666 
   667 (*MOVE UP*)
   668 
   669 lemma (in algebra) algebra_subset_lambda_system:
   670   assumes posf: "positive M f" and inc: "increasing M f"
   671       and add: "additive M f"
   672   shows "sets M \<subseteq> lambda_system (| space = space M, sets = Pow (space M) |)
   673                                 (\<lambda>x. Inf (measure_set M f x))"
   674 proof (auto dest: sets_into_space
   675             simp add: algebra.lambda_system_eq [OF algebra_Pow])
   676   fix x s
   677   assume x: "x \<in> sets M"
   678      and s: "s \<subseteq> space M"
   679   have [simp]: "!!x. x \<in> sets M \<Longrightarrow> s \<inter> (space M - x) = s-x" using s
   680     by blast
   681   have "Inf (measure_set M f (s\<inter>x)) + Inf (measure_set M f (s-x))
   682         \<le> Inf (measure_set M f s)"
   683     proof (rule pextreal_le_epsilon)
   684       fix e :: pextreal
   685       assume e: "0 < e"
   686       from inf_measure_close [of f, OF posf e s]
   687       obtain A where A: "range A \<subseteq> sets M" and disj: "disjoint_family A"
   688                  and sUN: "s \<subseteq> (\<Union>i. A i)"
   689                  and l: "psuminf (f \<circ> A) \<le> Inf (measure_set M f s) + e"
   690         by auto
   691       have [simp]: "!!x. x \<in> sets M \<Longrightarrow>
   692                       (f o (\<lambda>z. z \<inter> (space M - x)) o A) = (f o (\<lambda>z. z - x) o A)"
   693         by (rule ext, simp, metis A Int_Diff Int_space_eq2 range_subsetD)
   694       have  [simp]: "!!n. f (A n \<inter> x) + f (A n - x) = f (A n)"
   695         by (subst additiveD [OF add, symmetric])
   696            (auto simp add: x range_subsetD [OF A] Int_Diff_Un Int_Diff_disjoint)
   697       { fix u
   698         assume u: "u \<in> sets M"
   699         have [simp]: "\<And>n. f (A n \<inter> u) \<le> f (A n)"
   700           by (simp add: increasingD [OF inc] u Int range_subsetD [OF A])
   701         have 2: "Inf (measure_set M f (s \<inter> u)) \<le> psuminf (f \<circ> (\<lambda>z. z \<inter> u) \<circ> A)"
   702           proof (rule complete_lattice_class.Inf_lower)
   703             show "psuminf (f \<circ> (\<lambda>z. z \<inter> u) \<circ> A) \<in> measure_set M f (s \<inter> u)"
   704               apply (simp add: measure_set_def)
   705               apply (rule_tac x="(\<lambda>z. z \<inter> u) o A" in exI)
   706               apply (auto simp add: disjoint_family_subset [OF disj] o_def)
   707               apply (blast intro: u range_subsetD [OF A])
   708               apply (blast dest: subsetD [OF sUN])
   709               done
   710           qed
   711       } note lesum = this
   712       have inf1: "Inf (measure_set M f (s\<inter>x)) \<le> psuminf (f o (\<lambda>z. z\<inter>x) o A)"
   713         and inf2: "Inf (measure_set M f (s \<inter> (space M - x)))
   714                    \<le> psuminf (f o (\<lambda>z. z \<inter> (space M - x)) o A)"
   715         by (metis Diff lesum top x)+
   716       hence "Inf (measure_set M f (s\<inter>x)) + Inf (measure_set M f (s-x))
   717            \<le> psuminf (f o (\<lambda>s. s\<inter>x) o A) + psuminf (f o (\<lambda>s. s-x) o A)"
   718         by (simp add: x add_mono)
   719       also have "... \<le> psuminf (f o A)"
   720         by (simp add: x psuminf_add[symmetric] o_def)
   721       also have "... \<le> Inf (measure_set M f s) + e"
   722         by (rule l)
   723       finally show "Inf (measure_set M f (s\<inter>x)) + Inf (measure_set M f (s-x))
   724         \<le> Inf (measure_set M f s) + e" .
   725     qed
   726   moreover
   727   have "Inf (measure_set M f s)
   728        \<le> Inf (measure_set M f (s\<inter>x)) + Inf (measure_set M f (s-x))"
   729     proof -
   730     have "Inf (measure_set M f s) = Inf (measure_set M f ((s\<inter>x) \<union> (s-x)))"
   731       by (metis Un_Diff_Int Un_commute)
   732     also have "... \<le> Inf (measure_set M f (s\<inter>x)) + Inf (measure_set M f (s-x))"
   733       apply (rule subadditiveD)
   734       apply (rule algebra.countably_subadditive_subadditive[OF algebra_Pow])
   735       apply (simp add: positive_def inf_measure_empty[OF posf])
   736       apply (rule inf_measure_countably_subadditive)
   737       using s by (auto intro!: posf inc)
   738     finally show ?thesis .
   739     qed
   740   ultimately
   741   show "Inf (measure_set M f (s\<inter>x)) + Inf (measure_set M f (s-x))
   742         = Inf (measure_set M f s)"
   743     by (rule order_antisym)
   744 qed
   745 
   746 lemma measure_down:
   747   "measure_space N \<Longrightarrow> sigma_algebra M \<Longrightarrow> sets M \<subseteq> sets N \<Longrightarrow> measure N = measure M \<Longrightarrow> measure_space M"
   748   by (simp add: measure_space_def measure_space_axioms_def positive_def
   749                 countably_additive_def)
   750      blast
   751 
   752 theorem (in algebra) caratheodory:
   753   assumes posf: "positive M f" and ca: "countably_additive M f"
   754   shows "\<exists>\<mu> :: 'a set \<Rightarrow> pextreal. (\<forall>s \<in> sets M. \<mu> s = f s) \<and>
   755             measure_space \<lparr> space = space M, sets = sets (sigma M), measure = \<mu> \<rparr>"
   756 proof -
   757   have inc: "increasing M f"
   758     by (metis additive_increasing ca countably_additive_additive posf)
   759   let ?infm = "(\<lambda>x. Inf (measure_set M f x))"
   760   def ls \<equiv> "lambda_system (|space = space M, sets = Pow (space M)|) ?infm"
   761   have mls: "measure_space \<lparr>space = space M, sets = ls, measure = ?infm\<rparr>"
   762     using sigma_algebra.caratheodory_lemma
   763             [OF sigma_algebra_Pow  inf_measure_outer [OF posf inc]]
   764     by (simp add: ls_def)
   765   hence sls: "sigma_algebra (|space = space M, sets = ls, measure = ?infm|)"
   766     by (simp add: measure_space_def)
   767   have "sets M \<subseteq> ls"
   768     by (simp add: ls_def)
   769        (metis ca posf inc countably_additive_additive algebra_subset_lambda_system)
   770   hence sgs_sb: "sigma_sets (space M) (sets M) \<subseteq> ls"
   771     using sigma_algebra.sigma_sets_subset [OF sls, of "sets M"]
   772     by simp
   773   have "measure_space \<lparr> space = space M, sets = sets (sigma M), measure = ?infm \<rparr>"
   774     unfolding sigma_def
   775     by (rule measure_down [OF mls], rule sigma_algebra_sigma_sets)
   776        (simp_all add: sgs_sb space_closed)
   777   thus ?thesis using inf_measure_agrees [OF posf ca]
   778     by (intro exI[of _ ?infm]) auto
   779 qed
   780 
   781 end