src/HOL/Probability/Projective_Family.thy
 changeset 50042 6fe18351e9dd parent 50041 afe886a04198 child 50087 635d73673b5e
```     1.1 --- a/src/HOL/Probability/Projective_Family.thy	Fri Nov 09 14:14:45 2012 +0100
1.2 +++ b/src/HOL/Probability/Projective_Family.thy	Fri Nov 09 14:31:26 2012 +0100
1.3 @@ -1,3 +1,10 @@
1.4 +(*  Title:      HOL/Probability/Projective_Family.thy
1.5 +    Author:     Fabian Immler, TU München
1.6 +    Author:     Johannes Hölzl, TU München
1.7 +*)
1.8 +
1.10 +
1.11  theory Projective_Family
1.12  imports Finite_Product_Measure Probability_Measure
1.13  begin
1.14 @@ -99,6 +106,195 @@
1.15    using assms
1.16    by (subst PiP_finite) (auto simp: PiP_finite finite_subset projective)
1.17
1.18 +lemma prod_emb_injective:
1.19 +  assumes "J \<noteq> {}" "J \<subseteq> L" "finite J" and sets: "X \<in> sets (Pi\<^isub>M J M)" "Y \<in> sets (Pi\<^isub>M J M)"
1.20 +  assumes "prod_emb L M J X = prod_emb L M J Y"
1.21 +  shows "X = Y"
1.22 +proof (rule injective_vimage_restrict)
1.23 +  show "X \<subseteq> (\<Pi>\<^isub>E i\<in>J. space (M i))" "Y \<subseteq> (\<Pi>\<^isub>E i\<in>J. space (M i))"
1.24 +    using sets[THEN sets_into_space] by (auto simp: space_PiM)
1.25 +  have "\<forall>i\<in>L. \<exists>x. x \<in> space (M i)"
1.26 +  proof
1.27 +    fix i assume "i \<in> L"
1.28 +    interpret prob_space "P {i}" using prob_space by simp
1.29 +    from not_empty show "\<exists>x. x \<in> space (M i)" by (auto simp add: proj_space space_PiM)
1.30 +  qed
1.31 +  from bchoice[OF this]
1.32 +  show "(\<Pi>\<^isub>E i\<in>L. space (M i)) \<noteq> {}" by auto
1.33 +  show "(\<lambda>x. restrict x J) -` X \<inter> (\<Pi>\<^isub>E i\<in>L. space (M i)) = (\<lambda>x. restrict x J) -` Y \<inter> (\<Pi>\<^isub>E i\<in>L. space (M i))"
1.34 +    using `prod_emb L M J X = prod_emb L M J Y` by (simp add: prod_emb_def)
1.35 +qed fact
1.36 +
1.37 +abbreviation
1.38 +  "emb L K X \<equiv> prod_emb L M K X"
1.39 +
1.40 +definition generator :: "('i \<Rightarrow> 'a) set set" where
1.41 +  "generator = (\<Union>J\<in>{J. J \<noteq> {} \<and> finite J \<and> J \<subseteq> I}. emb I J ` sets (Pi\<^isub>M J M))"
1.42 +
1.43 +lemma generatorI':
1.44 +  "J \<noteq> {} \<Longrightarrow> finite J \<Longrightarrow> J \<subseteq> I \<Longrightarrow> X \<in> sets (Pi\<^isub>M J M) \<Longrightarrow> emb I J X \<in> generator"
1.45 +  unfolding generator_def by auto
1.46 +
1.47 +lemma algebra_generator:
1.48 +  assumes "I \<noteq> {}" shows "algebra (\<Pi>\<^isub>E i\<in>I. space (M i)) generator" (is "algebra ?\<Omega> ?G")
1.49 +  unfolding algebra_def algebra_axioms_def ring_of_sets_iff
1.50 +proof (intro conjI ballI)
1.51 +  let ?G = generator
1.52 +  show "?G \<subseteq> Pow ?\<Omega>"
1.53 +    by (auto simp: generator_def prod_emb_def)
1.54 +  from `I \<noteq> {}` obtain i where "i \<in> I" by auto
1.55 +  then show "{} \<in> ?G"
1.56 +    by (auto intro!: exI[of _ "{i}"] image_eqI[where x="\<lambda>i. {}"]
1.57 +             simp: sigma_sets.Empty generator_def prod_emb_def)
1.58 +  from `i \<in> I` show "?\<Omega> \<in> ?G"
1.59 +    by (auto intro!: exI[of _ "{i}"] image_eqI[where x="Pi\<^isub>E {i} (\<lambda>i. space (M i))"]
1.60 +             simp: generator_def prod_emb_def)
1.61 +  fix A assume "A \<in> ?G"
1.62 +  then obtain JA XA where XA: "JA \<noteq> {}" "finite JA" "JA \<subseteq> I" "XA \<in> sets (Pi\<^isub>M JA M)" and A: "A = emb I JA XA"
1.63 +    by (auto simp: generator_def)
1.64 +  fix B assume "B \<in> ?G"
1.65 +  then obtain JB XB where XB: "JB \<noteq> {}" "finite JB" "JB \<subseteq> I" "XB \<in> sets (Pi\<^isub>M JB M)" and B: "B = emb I JB XB"
1.66 +    by (auto simp: generator_def)
1.67 +  let ?RA = "emb (JA \<union> JB) JA XA"
1.68 +  let ?RB = "emb (JA \<union> JB) JB XB"
1.69 +  have *: "A - B = emb I (JA \<union> JB) (?RA - ?RB)" "A \<union> B = emb I (JA \<union> JB) (?RA \<union> ?RB)"
1.70 +    using XA A XB B by auto
1.71 +  show "A - B \<in> ?G" "A \<union> B \<in> ?G"
1.72 +    unfolding * using XA XB by (safe intro!: generatorI') auto
1.73 +qed
1.74 +
1.75 +lemma sets_PiM_generator:
1.76 +  "sets (PiM I M) = sigma_sets (\<Pi>\<^isub>E i\<in>I. space (M i)) generator"
1.77 +proof cases
1.78 +  assume "I = {}" then show ?thesis
1.79 +    unfolding generator_def
1.80 +    by (auto simp: sets_PiM_empty sigma_sets_empty_eq cong: conj_cong)
1.81 +next
1.82 +  assume "I \<noteq> {}"
1.83 +  show ?thesis
1.84 +  proof
1.85 +    show "sets (Pi\<^isub>M I M) \<subseteq> sigma_sets (\<Pi>\<^isub>E i\<in>I. space (M i)) generator"
1.86 +      unfolding sets_PiM
1.87 +    proof (safe intro!: sigma_sets_subseteq)
1.88 +      fix A assume "A \<in> prod_algebra I M" with `I \<noteq> {}` show "A \<in> generator"
1.89 +        by (auto intro!: generatorI' sets_PiM_I_finite elim!: prod_algebraE)
1.90 +    qed
1.91 +  qed (auto simp: generator_def space_PiM[symmetric] intro!: sigma_sets_subset)
1.92 +qed
1.93 +
1.94 +lemma generatorI:
1.95 +  "J \<noteq> {} \<Longrightarrow> finite J \<Longrightarrow> J \<subseteq> I \<Longrightarrow> X \<in> sets (Pi\<^isub>M J M) \<Longrightarrow> A = emb I J X \<Longrightarrow> A \<in> generator"
1.96 +  unfolding generator_def by auto
1.97 +
1.98 +definition
1.99 +  "\<mu>G A =
1.100 +    (THE x. \<forall>J. J \<noteq> {} \<longrightarrow> finite J \<longrightarrow> J \<subseteq> I \<longrightarrow> (\<forall>X\<in>sets (Pi\<^isub>M J M). A = emb I J X \<longrightarrow> x = emeasure (PiP J M P) X))"
1.101 +
1.102 +lemma \<mu>G_spec:
1.103 +  assumes J: "J \<noteq> {}" "finite J" "J \<subseteq> I" "A = emb I J X" "X \<in> sets (Pi\<^isub>M J M)"
1.104 +  shows "\<mu>G A = emeasure (PiP J M P) X"
1.105 +  unfolding \<mu>G_def
1.106 +proof (intro the_equality allI impI ballI)
1.107 +  fix K Y assume K: "K \<noteq> {}" "finite K" "K \<subseteq> I" "A = emb I K Y" "Y \<in> sets (Pi\<^isub>M K M)"
1.108 +  have "emeasure (PiP K M P) Y = emeasure (PiP (K \<union> J) M P) (emb (K \<union> J) K Y)"
1.109 +    using K J by simp
1.110 +  also have "emb (K \<union> J) K Y = emb (K \<union> J) J X"
1.111 +    using K J by (simp add: prod_emb_injective[of "K \<union> J" I])
1.112 +  also have "emeasure (PiP (K \<union> J) M P) (emb (K \<union> J) J X) = emeasure (PiP J M P) X"
1.113 +    using K J by simp
1.114 +  finally show "emeasure (PiP J M P) X = emeasure (PiP K M P) Y" ..
1.115 +qed (insert J, force)
1.116 +
1.117 +lemma \<mu>G_eq:
1.118 +  "J \<noteq> {} \<Longrightarrow> finite J \<Longrightarrow> J \<subseteq> I \<Longrightarrow> X \<in> sets (Pi\<^isub>M J M) \<Longrightarrow> \<mu>G (emb I J X) = emeasure (PiP J M P) X"
1.119 +  by (intro \<mu>G_spec) auto
1.120 +
1.121 +lemma generator_Ex:
1.122 +  assumes *: "A \<in> generator"
1.123 +  shows "\<exists>J X. J \<noteq> {} \<and> finite J \<and> J \<subseteq> I \<and> X \<in> sets (Pi\<^isub>M J M) \<and> A = emb I J X \<and> \<mu>G A = emeasure (PiP J M P) X"
1.124 +proof -
1.125 +  from * obtain J X where J: "J \<noteq> {}" "finite J" "J \<subseteq> I" "A = emb I J X" "X \<in> sets (Pi\<^isub>M J M)"
1.126 +    unfolding generator_def by auto
1.127 +  with \<mu>G_spec[OF this] show ?thesis by auto
1.128 +qed
1.129 +
1.130 +lemma generatorE:
1.131 +  assumes A: "A \<in> generator"
1.132 +  obtains J X where "J \<noteq> {}" "finite J" "J \<subseteq> I" "X \<in> sets (Pi\<^isub>M J M)" "emb I J X = A" "\<mu>G A = emeasure (PiP J M P) X"
1.133 +proof -
1.134 +  from generator_Ex[OF A] obtain X J where "J \<noteq> {}" "finite J" "J \<subseteq> I" "X \<in> sets (Pi\<^isub>M J M)" "emb I J X = A"
1.135 +    "\<mu>G A = emeasure (PiP J M P) X" by auto
1.136 +  then show thesis by (intro that) auto
1.137 +qed
1.138 +
1.139 +lemma merge_sets:
1.140 +  "J \<inter> K = {} \<Longrightarrow> A \<in> sets (Pi\<^isub>M (J \<union> K) M) \<Longrightarrow> x \<in> space (Pi\<^isub>M J M) \<Longrightarrow> (\<lambda>y. merge J K (x,y)) -` A \<inter> space (Pi\<^isub>M K M) \<in> sets (Pi\<^isub>M K M)"
1.141 +  by simp
1.142 +
1.143 +lemma merge_emb:
1.144 +  assumes "K \<subseteq> I" "J \<subseteq> I" and y: "y \<in> space (Pi\<^isub>M J M)"
1.145 +  shows "((\<lambda>x. merge J (I - J) (y, x)) -` emb I K X \<inter> space (Pi\<^isub>M I M)) =
1.146 +    emb I (K - J) ((\<lambda>x. merge J (K - J) (y, x)) -` emb (J \<union> K) K X \<inter> space (Pi\<^isub>M (K - J) M))"
1.147 +proof -
1.148 +  have [simp]: "\<And>x J K L. merge J K (y, restrict x L) = merge J (K \<inter> L) (y, x)"
1.149 +    by (auto simp: restrict_def merge_def)
1.150 +  have [simp]: "\<And>x J K L. restrict (merge J K (y, x)) L = merge (J \<inter> L) (K \<inter> L) (y, x)"
1.151 +    by (auto simp: restrict_def merge_def)
1.152 +  have [simp]: "(I - J) \<inter> K = K - J" using `K \<subseteq> I` `J \<subseteq> I` by auto
1.153 +  have [simp]: "(K - J) \<inter> (K \<union> J) = K - J" by auto
1.154 +  have [simp]: "(K - J) \<inter> K = K - J" by auto
1.155 +  from y `K \<subseteq> I` `J \<subseteq> I` show ?thesis
1.156 +    by (simp split: split_merge add: prod_emb_def Pi_iff extensional_merge_sub set_eq_iff space_PiM)
1.157 +       auto
1.158 +qed
1.159 +
1.160 +lemma positive_\<mu>G:
1.161 +  assumes "I \<noteq> {}"
1.162 +  shows "positive generator \<mu>G"
1.163 +proof -
1.164 +  interpret G!: algebra "\<Pi>\<^isub>E i\<in>I. space (M i)" generator by (rule algebra_generator) fact
1.165 +  show ?thesis
1.166 +  proof (intro positive_def[THEN iffD2] conjI ballI)
1.167 +    from generatorE[OF G.empty_sets] guess J X . note this[simp]
1.168 +    have "X = {}"
1.169 +      by (rule prod_emb_injective[of J I]) simp_all
1.170 +    then show "\<mu>G {} = 0" by simp
1.171 +  next
1.172 +    fix A assume "A \<in> generator"
1.173 +    from generatorE[OF this] guess J X . note this[simp]
1.174 +    show "0 \<le> \<mu>G A" by (simp add: emeasure_nonneg)
1.175 +  qed
1.176 +qed
1.177 +
1.179 +  assumes "I \<noteq> {}"
1.180 +  shows "additive generator \<mu>G"
1.181 +proof -
1.182 +  interpret G!: algebra "\<Pi>\<^isub>E i\<in>I. space (M i)" generator by (rule algebra_generator) fact
1.183 +  show ?thesis
1.184 +  proof (intro additive_def[THEN iffD2] ballI impI)
1.185 +    fix A assume "A \<in> generator" with generatorE guess J X . note J = this
1.186 +    fix B assume "B \<in> generator" with generatorE guess K Y . note K = this
1.187 +    assume "A \<inter> B = {}"
1.188 +    have JK: "J \<union> K \<noteq> {}" "J \<union> K \<subseteq> I" "finite (J \<union> K)"
1.189 +      using J K by auto
1.190 +    have JK_disj: "emb (J \<union> K) J X \<inter> emb (J \<union> K) K Y = {}"
1.191 +      apply (rule prod_emb_injective[of "J \<union> K" I])
1.192 +      apply (insert `A \<inter> B = {}` JK J K)
1.193 +      apply (simp_all add: Int prod_emb_Int)
1.194 +      done
1.195 +    have AB: "A = emb I (J \<union> K) (emb (J \<union> K) J X)" "B = emb I (J \<union> K) (emb (J \<union> K) K Y)"
1.196 +      using J K by simp_all
1.197 +    then have "\<mu>G (A \<union> B) = \<mu>G (emb I (J \<union> K) (emb (J \<union> K) J X \<union> emb (J \<union> K) K Y))"
1.198 +      by simp
1.199 +    also have "\<dots> = emeasure (PiP (J \<union> K) M P) (emb (J \<union> K) J X \<union> emb (J \<union> K) K Y)"
1.200 +      using JK J(1, 4) K(1, 4) by (simp add: \<mu>G_eq Un del: prod_emb_Un)
1.201 +    also have "\<dots> = \<mu>G A + \<mu>G B"
1.202 +      using J K JK_disj by (simp add: plus_emeasure[symmetric])
1.203 +    finally show "\<mu>G (A \<union> B) = \<mu>G A + \<mu>G B" .
1.204 +  qed
1.205 +qed
1.206 +
1.207  end
1.208
1.209  end
```