(* Title: HOL/Analysis/Sigma_Algebra.thy Author: Stefan Richter, Markus Wenzel, TU München Author: Johannes Hölzl, TU München Plus material from the Hurd/Coble measure theory development, translated by Lawrence Paulson. *) section ‹Describing measurable sets› theory Sigma_Algebra imports Complex_Main "HOL-Library.Countable_Set" "HOL-Library.FuncSet" "HOL-Library.Indicator_Function" "HOL-Library.Extended_Nonnegative_Real" "HOL-Library.Disjoint_Sets" begin text ‹Sigma algebras are an elementary concept in measure theory. To measure --- that is to integrate --- functions, we first have to measure sets. Unfortunately, when dealing with a large universe, it is often not possible to consistently assign a measure to every subset. Therefore it is necessary to define the set of measurable subsets of the universe. A sigma algebra is such a set that has three very natural and desirable properties.› subsection ‹Families of sets› locale subset_class = fixes Ω :: "'a set" and M :: "'a set set" assumes space_closed: "M ⊆ Pow Ω" lemma (in subset_class) sets_into_space: "x ∈ M ⟹ x ⊆ Ω" by (metis PowD contra_subsetD space_closed) subsubsection ‹Semiring of sets› locale semiring_of_sets = subset_class + assumes empty_sets[iff]: "{} ∈ M" assumes Int[intro]: "⋀a b. a ∈ M ⟹ b ∈ M ⟹ a ∩ b ∈ M" assumes Diff_cover: "⋀a b. a ∈ M ⟹ b ∈ M ⟹ ∃C⊆M. finite C ∧ disjoint C ∧ a - b = ⋃C" lemma (in semiring_of_sets) finite_INT[intro]: assumes "finite I" "I ≠ {}" "⋀i. i ∈ I ⟹ A i ∈ M" shows "(⋂i∈I. A i) ∈ M" using assms by (induct rule: finite_ne_induct) auto lemma (in semiring_of_sets) Int_space_eq1 [simp]: "x ∈ M ⟹ Ω ∩ x = x" by (metis Int_absorb1 sets_into_space) lemma (in semiring_of_sets) Int_space_eq2 [simp]: "x ∈ M ⟹ x ∩ Ω = x" by (metis Int_absorb2 sets_into_space) lemma (in semiring_of_sets) sets_Collect_conj: assumes "{x∈Ω. P x} ∈ M" "{x∈Ω. Q x} ∈ M" shows "{x∈Ω. Q x ∧ P x} ∈ M" proof - have "{x∈Ω. Q x ∧ P x} = {x∈Ω. Q x} ∩ {x∈Ω. P x}" by auto with assms show ?thesis by auto qed lemma (in semiring_of_sets) sets_Collect_finite_All': assumes "⋀i. i ∈ S ⟹ {x∈Ω. P i x} ∈ M" "finite S" "S ≠ {}" shows "{x∈Ω. ∀i∈S. P i x} ∈ M" proof - have "{x∈Ω. ∀i∈S. P i x} = (⋂i∈S. {x∈Ω. P i x})" using ‹S ≠ {}› by auto with assms show ?thesis by auto qed locale ring_of_sets = semiring_of_sets + assumes Un [intro]: "⋀a b. a ∈ M ⟹ b ∈ M ⟹ a ∪ b ∈ M" lemma (in ring_of_sets) finite_Union [intro]: "finite X ⟹ X ⊆ M ⟹ ⋃X ∈ M" by (induct set: finite) (auto simp add: Un) lemma (in ring_of_sets) finite_UN[intro]: assumes "finite I" and "⋀i. i ∈ I ⟹ A i ∈ M" shows "(⋃i∈I. A i) ∈ M" using assms by induct auto lemma (in ring_of_sets) Diff [intro]: assumes "a ∈ M" "b ∈ M" shows "a - b ∈ M" using Diff_cover[OF assms] by auto lemma ring_of_setsI: assumes space_closed: "M ⊆ Pow Ω" assumes empty_sets[iff]: "{} ∈ M" assumes Un[intro]: "⋀a b. a ∈ M ⟹ b ∈ M ⟹ a ∪ b ∈ M" assumes Diff[intro]: "⋀a b. a ∈ M ⟹ b ∈ M ⟹ a - b ∈ M" shows "ring_of_sets Ω M" proof fix a b assume ab: "a ∈ M" "b ∈ M" from ab show "∃C⊆M. finite C ∧ disjoint C ∧ a - b = ⋃C" by (intro exI[of _ "{a - b}"]) (auto simp: disjoint_def) have "a ∩ b = a - (a - b)" by auto also have "… ∈ M" using ab by auto finally show "a ∩ b ∈ M" . qed fact+ lemma ring_of_sets_iff: "ring_of_sets Ω M ⟷ M ⊆ Pow Ω ∧ {} ∈ M ∧ (∀a∈M. ∀b∈M. a ∪ b ∈ M) ∧ (∀a∈M. ∀b∈M. a - b ∈ M)" proof assume "ring_of_sets Ω M" then interpret ring_of_sets Ω M . show "M ⊆ Pow Ω ∧ {} ∈ M ∧ (∀a∈M. ∀b∈M. a ∪ b ∈ M) ∧ (∀a∈M. ∀b∈M. a - b ∈ M)" using space_closed by auto qed (auto intro!: ring_of_setsI) lemma (in ring_of_sets) insert_in_sets: assumes "{x} ∈ M" "A ∈ M" shows "insert x A ∈ M" proof - have "{x} ∪ A ∈ M" using assms by (rule Un) thus ?thesis by auto qed lemma (in ring_of_sets) sets_Collect_disj: assumes "{x∈Ω. P x} ∈ M" "{x∈Ω. Q x} ∈ M" shows "{x∈Ω. Q x ∨ P x} ∈ M" proof - have "{x∈Ω. Q x ∨ P x} = {x∈Ω. Q x} ∪ {x∈Ω. P x}" by auto with assms show ?thesis by auto qed lemma (in ring_of_sets) sets_Collect_finite_Ex: assumes "⋀i. i ∈ S ⟹ {x∈Ω. P i x} ∈ M" "finite S" shows "{x∈Ω. ∃i∈S. P i x} ∈ M" proof - have "{x∈Ω. ∃i∈S. P i x} = (⋃i∈S. {x∈Ω. P i x})" by auto with assms show ?thesis by auto qed locale algebra = ring_of_sets + assumes top [iff]: "Ω ∈ M" lemma (in algebra) compl_sets [intro]: "a ∈ M ⟹ Ω - a ∈ M" by auto lemma algebra_iff_Un: "algebra Ω M ⟷ M ⊆ Pow Ω ∧ {} ∈ M ∧ (∀a ∈ M. Ω - a ∈ M) ∧ (∀a ∈ M. ∀ b ∈ M. a ∪ b ∈ M)" (is "_ ⟷ ?Un") proof assume "algebra Ω M" then interpret algebra Ω M . show ?Un using sets_into_space by auto next assume ?Un then have "Ω ∈ M" by auto interpret ring_of_sets Ω M proof (rule ring_of_setsI) show Ω: "M ⊆ Pow Ω" "{} ∈ M" using ‹?Un› by auto fix a b assume a: "a ∈ M" and b: "b ∈ M" then show "a ∪ b ∈ M" using ‹?Un› by auto have "a - b = Ω - ((Ω - a) ∪ b)" using Ω a b by auto then show "a - b ∈ M" using a b ‹?Un› by auto qed show "algebra Ω M" proof qed fact qed lemma algebra_iff_Int: "algebra Ω M ⟷ M ⊆ Pow Ω & {} ∈ M & (∀a ∈ M. Ω - a ∈ M) & (∀a ∈ M. ∀ b ∈ M. a ∩ b ∈ M)" (is "_ ⟷ ?Int") proof assume "algebra Ω M" then interpret algebra Ω M . show ?Int using sets_into_space by auto next assume ?Int show "algebra Ω M" proof (unfold algebra_iff_Un, intro conjI ballI) show Ω: "M ⊆ Pow Ω" "{} ∈ M" using ‹?Int› by auto from ‹?Int› show "⋀a. a ∈ M ⟹ Ω - a ∈ M" by auto fix a b assume M: "a ∈ M" "b ∈ M" hence "a ∪ b = Ω - ((Ω - a) ∩ (Ω - b))" using Ω by blast also have "... ∈ M" using M ‹?Int› by auto finally show "a ∪ b ∈ M" . qed qed lemma (in algebra) sets_Collect_neg: assumes "{x∈Ω. P x} ∈ M" shows "{x∈Ω. ¬ P x} ∈ M" proof - have "{x∈Ω. ¬ P x} = Ω - {x∈Ω. P x}" by auto with assms show ?thesis by auto qed lemma (in algebra) sets_Collect_imp: "{x∈Ω. P x} ∈ M ⟹ {x∈Ω. Q x} ∈ M ⟹ {x∈Ω. Q x ⟶ P x} ∈ M" unfolding imp_conv_disj by (intro sets_Collect_disj sets_Collect_neg) lemma (in algebra) sets_Collect_const: "{x∈Ω. P} ∈ M" by (cases P) auto lemma algebra_single_set: "X ⊆ S ⟹ algebra S { {}, X, S - X, S }" by (auto simp: algebra_iff_Int) subsubsection ‹Restricted algebras› abbreviation (in algebra) "restricted_space A ≡ (op ∩ A) ` M" lemma (in algebra) restricted_algebra: assumes "A ∈ M" shows "algebra A (restricted_space A)" using assms by (auto simp: algebra_iff_Int) subsubsection ‹Sigma Algebras› locale sigma_algebra = algebra + assumes countable_nat_UN [intro]: "⋀A. range A ⊆ M ⟹ (⋃i::nat. A i) ∈ M" lemma (in algebra) is_sigma_algebra: assumes "finite M" shows "sigma_algebra Ω M" proof fix A :: "nat ⇒ 'a set" assume "range A ⊆ M" then have "(⋃i. A i) = (⋃s∈M ∩ range A. s)" by auto also have "(⋃s∈M ∩ range A. s) ∈ M" using ‹finite M› by auto finally show "(⋃i. A i) ∈ M" . qed lemma countable_UN_eq: fixes A :: "'i::countable ⇒ 'a set" shows "(range A ⊆ M ⟶ (⋃i. A i) ∈ M) ⟷ (range (A ∘ from_nat) ⊆ M ⟶ (⋃i. (A ∘ from_nat) i) ∈ M)" proof - let ?A' = "A ∘ from_nat" have *: "(⋃i. ?A' i) = (⋃i. A i)" (is "?l = ?r") proof safe fix x i assume "x ∈ A i" thus "x ∈ ?l" by (auto intro!: exI[of _ "to_nat i"]) next fix x i assume "x ∈ ?A' i" thus "x ∈ ?r" by (auto intro!: exI[of _ "from_nat i"]) qed have **: "range ?A' = range A" using surj_from_nat by (auto simp: image_comp [symmetric] intro!: imageI) show ?thesis unfolding * ** .. qed lemma (in sigma_algebra) countable_Union [intro]: assumes "countable X" "X ⊆ M" shows "⋃X ∈ M" proof cases assume "X ≠ {}" hence "⋃X = (⋃n. from_nat_into X n)" using assms by (auto intro: from_nat_into) (metis from_nat_into_surj) also have "… ∈ M" using assms by (auto intro!: countable_nat_UN) (metis ‹X ≠ {}› from_nat_into set_mp) finally show ?thesis . qed simp lemma (in sigma_algebra) countable_UN[intro]: fixes A :: "'i::countable ⇒ 'a set" assumes "A`X ⊆ M" shows "(⋃x∈X. A x) ∈ M" proof - let ?A = "λi. if i ∈ X then A i else {}" from assms have "range ?A ⊆ M" by auto with countable_nat_UN[of "?A ∘ from_nat"] countable_UN_eq[of ?A M] have "(⋃x. ?A x) ∈ M" by auto moreover have "(⋃x. ?A x) = (⋃x∈X. A x)" by (auto split: if_split_asm) ultimately show ?thesis by simp qed lemma (in sigma_algebra) countable_UN': fixes A :: "'i ⇒ 'a set" assumes X: "countable X" assumes A: "A`X ⊆ M" shows "(⋃x∈X. A x) ∈ M" proof - have "(⋃x∈X. A x) = (⋃i∈to_nat_on X ` X. A (from_nat_into X i))" using X by auto also have "… ∈ M" using A X by (intro countable_UN) auto finally show ?thesis . qed lemma (in sigma_algebra) countable_UN'': "⟦ countable X; ⋀x y. x ∈ X ⟹ A x ∈ M ⟧ ⟹ (⋃x∈X. A x) ∈ M" by(erule countable_UN')(auto) lemma (in sigma_algebra) countable_INT [intro]: fixes A :: "'i::countable ⇒ 'a set" assumes A: "A`X ⊆ M" "X ≠ {}" shows "(⋂i∈X. A i) ∈ M" proof - from A have "∀i∈X. A i ∈ M" by fast hence "Ω - (⋃i∈X. Ω - A i) ∈ M" by blast moreover have "(⋂i∈X. A i) = Ω - (⋃i∈X. Ω - A i)" using space_closed A by blast ultimately show ?thesis by metis qed lemma (in sigma_algebra) countable_INT': fixes A :: "'i ⇒ 'a set" assumes X: "countable X" "X ≠ {}" assumes A: "A`X ⊆ M" shows "(⋂x∈X. A x) ∈ M" proof - have "(⋂x∈X. A x) = (⋂i∈to_nat_on X ` X. A (from_nat_into X i))" using X by auto also have "… ∈ M" using A X by (intro countable_INT) auto finally show ?thesis . qed lemma (in sigma_algebra) countable_INT'': "UNIV ∈ M ⟹ countable I ⟹ (⋀i. i ∈ I ⟹ F i ∈ M) ⟹ (⋂i∈I. F i) ∈ M" by (cases "I = {}") (auto intro: countable_INT') lemma (in sigma_algebra) countable: assumes "⋀a. a ∈ A ⟹ {a} ∈ M" "countable A" shows "A ∈ M" proof - have "(⋃a∈A. {a}) ∈ M" using assms by (intro countable_UN') auto also have "(⋃a∈A. {a}) = A" by auto finally show ?thesis by auto qed lemma ring_of_sets_Pow: "ring_of_sets sp (Pow sp)" by (auto simp: ring_of_sets_iff) lemma algebra_Pow: "algebra sp (Pow sp)" by (auto simp: algebra_iff_Un) lemma sigma_algebra_iff: "sigma_algebra Ω M ⟷ algebra Ω M ∧ (∀A. range A ⊆ M ⟶ (⋃i::nat. A i) ∈ M)" by (simp add: sigma_algebra_def sigma_algebra_axioms_def) lemma sigma_algebra_Pow: "sigma_algebra sp (Pow sp)" by (auto simp: sigma_algebra_iff algebra_iff_Int) lemma (in sigma_algebra) sets_Collect_countable_All: assumes "⋀i. {x∈Ω. P i x} ∈ M" shows "{x∈Ω. ∀i::'i::countable. P i x} ∈ M" proof - have "{x∈Ω. ∀i::'i::countable. P i x} = (⋂i. {x∈Ω. P i x})" by auto with assms show ?thesis by auto qed lemma (in sigma_algebra) sets_Collect_countable_Ex: assumes "⋀i. {x∈Ω. P i x} ∈ M" shows "{x∈Ω. ∃i::'i::countable. P i x} ∈ M" proof - have "{x∈Ω. ∃i::'i::countable. P i x} = (⋃i. {x∈Ω. P i x})" by auto with assms show ?thesis by auto qed lemma (in sigma_algebra) sets_Collect_countable_Ex': assumes "⋀i. i ∈ I ⟹ {x∈Ω. P i x} ∈ M" assumes "countable I" shows "{x∈Ω. ∃i∈I. P i x} ∈ M" proof - have "{x∈Ω. ∃i∈I. P i x} = (⋃i∈I. {x∈Ω. P i x})" by auto with assms show ?thesis by (auto intro!: countable_UN') qed lemma (in sigma_algebra) sets_Collect_countable_All': assumes "⋀i. i ∈ I ⟹ {x∈Ω. P i x} ∈ M" assumes "countable I" shows "{x∈Ω. ∀i∈I. P i x} ∈ M" proof - have "{x∈Ω. ∀i∈I. P i x} = (⋂i∈I. {x∈Ω. P i x}) ∩ Ω" by auto with assms show ?thesis by (cases "I = {}") (auto intro!: countable_INT') qed lemma (in sigma_algebra) sets_Collect_countable_Ex1': assumes "⋀i. i ∈ I ⟹ {x∈Ω. P i x} ∈ M" assumes "countable I" shows "{x∈Ω. ∃!i∈I. P i x} ∈ M" proof - have "{x∈Ω. ∃!i∈I. P i x} = {x∈Ω. ∃i∈I. P i x ∧ (∀j∈I. P j x ⟶ i = j)}" by auto with assms show ?thesis by (auto intro!: sets_Collect_countable_All' sets_Collect_countable_Ex' sets_Collect_conj sets_Collect_imp sets_Collect_const) qed lemmas (in sigma_algebra) sets_Collect = sets_Collect_imp sets_Collect_disj sets_Collect_conj sets_Collect_neg sets_Collect_const sets_Collect_countable_All sets_Collect_countable_Ex sets_Collect_countable_All lemma (in sigma_algebra) sets_Collect_countable_Ball: assumes "⋀i. {x∈Ω. P i x} ∈ M" shows "{x∈Ω. ∀i::'i::countable∈X. P i x} ∈ M" unfolding Ball_def by (intro sets_Collect assms) lemma (in sigma_algebra) sets_Collect_countable_Bex: assumes "⋀i. {x∈Ω. P i x} ∈ M" shows "{x∈Ω. ∃i::'i::countable∈X. P i x} ∈ M" unfolding Bex_def by (intro sets_Collect assms) lemma sigma_algebra_single_set: assumes "X ⊆ S" shows "sigma_algebra S { {}, X, S - X, S }" using algebra.is_sigma_algebra[OF algebra_single_set[OF ‹X ⊆ S›]] by simp subsubsection ‹Binary Unions› definition binary :: "'a ⇒ 'a ⇒ nat ⇒ 'a" where "binary a b = (λx. b)(0 := a)" lemma range_binary_eq: "range(binary a b) = {a,b}" by (auto simp add: binary_def) lemma Un_range_binary: "a ∪ b = (⋃i::nat. binary a b i)" by (simp add: range_binary_eq cong del: strong_SUP_cong) lemma Int_range_binary: "a ∩ b = (⋂i::nat. binary a b i)" by (simp add: range_binary_eq cong del: strong_INF_cong) lemma sigma_algebra_iff2: "sigma_algebra Ω M ⟷ M ⊆ Pow Ω ∧ {} ∈ M ∧ (∀s ∈ M. Ω - s ∈ M) ∧ (∀A. range A ⊆ M ⟶ (⋃i::nat. A i) ∈ M)" by (auto simp add: range_binary_eq sigma_algebra_def sigma_algebra_axioms_def algebra_iff_Un Un_range_binary) subsubsection ‹Initial Sigma Algebra› text ‹Sigma algebras can naturally be created as the closure of any set of M with regard to the properties just postulated.› inductive_set sigma_sets :: "'a set ⇒ 'a set set ⇒ 'a set set" for sp :: "'a set" and A :: "'a set set" where Basic[intro, simp]: "a ∈ A ⟹ a ∈ sigma_sets sp A" | Empty: "{} ∈ sigma_sets sp A" | Compl: "a ∈ sigma_sets sp A ⟹ sp - a ∈ sigma_sets sp A" | Union: "(⋀i::nat. a i ∈ sigma_sets sp A) ⟹ (⋃i. a i) ∈ sigma_sets sp A" lemma (in sigma_algebra) sigma_sets_subset: assumes a: "a ⊆ M" shows "sigma_sets Ω a ⊆ M" proof fix x assume "x ∈ sigma_sets Ω a" from this show "x ∈ M" by (induct rule: sigma_sets.induct, auto) (metis a subsetD) qed lemma sigma_sets_into_sp: "A ⊆ Pow sp ⟹ x ∈ sigma_sets sp A ⟹ x ⊆ sp" by (erule sigma_sets.induct, auto) lemma sigma_algebra_sigma_sets: "a ⊆ Pow Ω ⟹ sigma_algebra Ω (sigma_sets Ω a)" by (auto simp add: sigma_algebra_iff2 dest: sigma_sets_into_sp intro!: sigma_sets.Union sigma_sets.Empty sigma_sets.Compl) lemma sigma_sets_least_sigma_algebra: assumes "A ⊆ Pow S" shows "sigma_sets S A = ⋂{B. A ⊆ B ∧ sigma_algebra S B}" proof safe fix B X assume "A ⊆ B" and sa: "sigma_algebra S B" and X: "X ∈ sigma_sets S A" from sigma_algebra.sigma_sets_subset[OF sa, simplified, OF ‹A ⊆ B›] X show "X ∈ B" by auto next fix X assume "X ∈ ⋂{B. A ⊆ B ∧ sigma_algebra S B}" then have [intro!]: "⋀B. A ⊆ B ⟹ sigma_algebra S B ⟹ X ∈ B" by simp have "A ⊆ sigma_sets S A" using assms by auto moreover have "sigma_algebra S (sigma_sets S A)" using assms by (intro sigma_algebra_sigma_sets[of A]) auto ultimately show "X ∈ sigma_sets S A" by auto qed lemma sigma_sets_top: "sp ∈ sigma_sets sp A" by (metis Diff_empty sigma_sets.Compl sigma_sets.Empty) lemma sigma_sets_Un: "a ∈ sigma_sets sp A ⟹ b ∈ sigma_sets sp A ⟹ a ∪ b ∈ sigma_sets sp A" apply (simp add: Un_range_binary range_binary_eq) apply (rule Union, simp add: binary_def) done lemma sigma_sets_Inter: assumes Asb: "A ⊆ Pow sp" shows "(⋀i::nat. a i ∈ sigma_sets sp A) ⟹ (⋂i. a i) ∈ sigma_sets sp A" proof - assume ai: "⋀i::nat. a i ∈ sigma_sets sp A" hence "⋀i::nat. sp-(a i) ∈ sigma_sets sp A" by (rule sigma_sets.Compl) hence "(⋃i. sp-(a i)) ∈ sigma_sets sp A" by (rule sigma_sets.Union) hence "sp-(⋃i. sp-(a i)) ∈ sigma_sets sp A" by (rule sigma_sets.Compl) also have "sp-(⋃i. sp-(a i)) = sp Int (⋂i. a i)" by auto also have "... = (⋂i. a i)" using ai by (blast dest: sigma_sets_into_sp [OF Asb]) finally show ?thesis . qed lemma sigma_sets_INTER: assumes Asb: "A ⊆ Pow sp" and ai: "⋀i::nat. i ∈ S ⟹ a i ∈ sigma_sets sp A" and non: "S ≠ {}" shows "(⋂i∈S. a i) ∈ sigma_sets sp A" proof - from ai have "⋀i. (if i∈S then a i else sp) ∈ sigma_sets sp A" by (simp add: sigma_sets.intros(2-) sigma_sets_top) hence "(⋂i. (if i∈S then a i else sp)) ∈ sigma_sets sp A" by (rule sigma_sets_Inter [OF Asb]) also have "(⋂i. (if i∈S then a i else sp)) = (⋂i∈S. a i)" by auto (metis ai non sigma_sets_into_sp subset_empty subset_iff Asb)+ finally show ?thesis . qed lemma sigma_sets_UNION: "countable B ⟹ (⋀b. b ∈ B ⟹ b ∈ sigma_sets X A) ⟹ (⋃B) ∈ sigma_sets X A" apply (cases "B = {}") apply (simp add: sigma_sets.Empty) using from_nat_into [of B] range_from_nat_into [of B] sigma_sets.Union [of "from_nat_into B" X A] apply simp apply auto apply (metis Sup_bot_conv(1) Union_empty ‹⟦B ≠ {}; countable B⟧ ⟹ range (from_nat_into B) = B›) done lemma (in sigma_algebra) sigma_sets_eq: "sigma_sets Ω M = M" proof show "M ⊆ sigma_sets Ω M" by (metis Set.subsetI sigma_sets.Basic) next show "sigma_sets Ω M ⊆ M" by (metis sigma_sets_subset subset_refl) qed lemma sigma_sets_eqI: assumes A: "⋀a. a ∈ A ⟹ a ∈ sigma_sets M B" assumes B: "⋀b. b ∈ B ⟹ b ∈ sigma_sets M A" shows "sigma_sets M A = sigma_sets M B" proof (intro set_eqI iffI) fix a assume "a ∈ sigma_sets M A" from this A show "a ∈ sigma_sets M B" by induct (auto intro!: sigma_sets.intros(2-) del: sigma_sets.Basic) next fix b assume "b ∈ sigma_sets M B" from this B show "b ∈ sigma_sets M A" by induct (auto intro!: sigma_sets.intros(2-) del: sigma_sets.Basic) qed lemma sigma_sets_subseteq: assumes "A ⊆ B" shows "sigma_sets X A ⊆ sigma_sets X B" proof fix x assume "x ∈ sigma_sets X A" then show "x ∈ sigma_sets X B" by induct (insert ‹A ⊆ B›, auto intro: sigma_sets.intros(2-)) qed lemma sigma_sets_mono: assumes "A ⊆ sigma_sets X B" shows "sigma_sets X A ⊆ sigma_sets X B" proof fix x assume "x ∈ sigma_sets X A" then show "x ∈ sigma_sets X B" by induct (insert ‹A ⊆ sigma_sets X B›, auto intro: sigma_sets.intros(2-)) qed lemma sigma_sets_mono': assumes "A ⊆ B" shows "sigma_sets X A ⊆ sigma_sets X B" proof fix x assume "x ∈ sigma_sets X A" then show "x ∈ sigma_sets X B" by induct (insert ‹A ⊆ B›, auto intro: sigma_sets.intros(2-)) qed lemma sigma_sets_superset_generator: "A ⊆ sigma_sets X A" by (auto intro: sigma_sets.Basic) lemma (in sigma_algebra) restriction_in_sets: fixes A :: "nat ⇒ 'a set" assumes "S ∈ M" and *: "range A ⊆ (λA. S ∩ A) ` M" (is "_ ⊆ ?r") shows "range A ⊆ M" "(⋃i. A i) ∈ (λA. S ∩ A) ` M" proof - { fix i have "A i ∈ ?r" using * by auto hence "∃B. A i = B ∩ S ∧ B ∈ M" by auto hence "A i ⊆ S" "A i ∈ M" using ‹S ∈ M› by auto } thus "range A ⊆ M" "(⋃i. A i) ∈ (λA. S ∩ A) ` M" by (auto intro!: image_eqI[of _ _ "(⋃i. A i)"]) qed lemma (in sigma_algebra) restricted_sigma_algebra: assumes "S ∈ M" shows "sigma_algebra S (restricted_space S)" unfolding sigma_algebra_def sigma_algebra_axioms_def proof safe show "algebra S (restricted_space S)" using restricted_algebra[OF assms] . next fix A :: "nat ⇒ 'a set" assume "range A ⊆ restricted_space S" from restriction_in_sets[OF assms this[simplified]] show "(⋃i. A i) ∈ restricted_space S" by simp qed lemma sigma_sets_Int: assumes "A ∈ sigma_sets sp st" "A ⊆ sp" shows "op ∩ A ` sigma_sets sp st = sigma_sets A (op ∩ A ` st)" proof (intro equalityI subsetI) fix x assume "x ∈ op ∩ A ` sigma_sets sp st" then obtain y where "y ∈ sigma_sets sp st" "x = y ∩ A" by auto then have "x ∈ sigma_sets (A ∩ sp) (op ∩ A ` st)" proof (induct arbitrary: x) case (Compl a) then show ?case by (force intro!: sigma_sets.Compl simp: Diff_Int_distrib ac_simps) next case (Union a) then show ?case by (auto intro!: sigma_sets.Union simp add: UN_extend_simps simp del: UN_simps) qed (auto intro!: sigma_sets.intros(2-)) then show "x ∈ sigma_sets A (op ∩ A ` st)" using ‹A ⊆ sp› by (simp add: Int_absorb2) next fix x assume "x ∈ sigma_sets A (op ∩ A ` st)" then show "x ∈ op ∩ A ` sigma_sets sp st" proof induct case (Compl a) then obtain x where "a = A ∩ x" "x ∈ sigma_sets sp st" by auto then show ?case using ‹A ⊆ sp› by (force simp add: image_iff intro!: bexI[of _ "sp - x"] sigma_sets.Compl) next case (Union a) then have "∀i. ∃x. x ∈ sigma_sets sp st ∧ a i = A ∩ x" by (auto simp: image_iff Bex_def) from choice[OF this] guess f .. then show ?case by (auto intro!: bexI[of _ "(⋃x. f x)"] sigma_sets.Union simp add: image_iff) qed (auto intro!: sigma_sets.intros(2-)) qed lemma sigma_sets_empty_eq: "sigma_sets A {} = {{}, A}" proof (intro set_eqI iffI) fix a assume "a ∈ sigma_sets A {}" then show "a ∈ {{}, A}" by induct blast+ qed (auto intro: sigma_sets.Empty sigma_sets_top) lemma sigma_sets_single[simp]: "sigma_sets A {A} = {{}, A}" proof (intro set_eqI iffI) fix x assume "x ∈ sigma_sets A {A}" then show "x ∈ {{}, A}" by induct blast+ next fix x assume "x ∈ {{}, A}" then show "x ∈ sigma_sets A {A}" by (auto intro: sigma_sets.Empty sigma_sets_top) qed lemma sigma_sets_sigma_sets_eq: "M ⊆ Pow S ⟹ sigma_sets S (sigma_sets S M) = sigma_sets S M" by (rule sigma_algebra.sigma_sets_eq[OF sigma_algebra_sigma_sets, of M S]) auto lemma sigma_sets_singleton: assumes "X ⊆ S" shows "sigma_sets S { X } = { {}, X, S - X, S }" proof - interpret sigma_algebra S "{ {}, X, S - X, S }" by (rule sigma_algebra_single_set) fact have "sigma_sets S { X } ⊆ sigma_sets S { {}, X, S - X, S }" by (rule sigma_sets_subseteq) simp moreover have "… = { {}, X, S - X, S }" using sigma_sets_eq by simp moreover { fix A assume "A ∈ { {}, X, S - X, S }" then have "A ∈ sigma_sets S { X }" by (auto intro: sigma_sets.intros(2-) sigma_sets_top) } ultimately have "sigma_sets S { X } = sigma_sets S { {}, X, S - X, S }" by (intro antisym) auto with sigma_sets_eq show ?thesis by simp qed lemma restricted_sigma: assumes S: "S ∈ sigma_sets Ω M" and M: "M ⊆ Pow Ω" shows "algebra.restricted_space (sigma_sets Ω M) S = sigma_sets S (algebra.restricted_space M S)" proof - from S sigma_sets_into_sp[OF M] have "S ∈ sigma_sets Ω M" "S ⊆ Ω" by auto from sigma_sets_Int[OF this] show ?thesis by simp qed lemma sigma_sets_vimage_commute: assumes X: "X ∈ Ω → Ω'" shows "{X -` A ∩ Ω |A. A ∈ sigma_sets Ω' M'} = sigma_sets Ω {X -` A ∩ Ω |A. A ∈ M'}" (is "?L = ?R") proof show "?L ⊆ ?R" proof clarify fix A assume "A ∈ sigma_sets Ω' M'" then show "X -` A ∩ Ω ∈ ?R" proof induct case Empty then show ?case by (auto intro!: sigma_sets.Empty) next case (Compl B) have [simp]: "X -` (Ω' - B) ∩ Ω = Ω - (X -` B ∩ Ω)" by (auto simp add: funcset_mem [OF X]) with Compl show ?case by (auto intro!: sigma_sets.Compl) next case (Union F) then show ?case by (auto simp add: vimage_UN UN_extend_simps(4) simp del: UN_simps intro!: sigma_sets.Union) qed auto qed show "?R ⊆ ?L" proof clarify fix A assume "A ∈ ?R" then show "∃B. A = X -` B ∩ Ω ∧ B ∈ sigma_sets Ω' M'" proof induct case (Basic B) then show ?case by auto next case Empty then show ?case by (auto intro!: sigma_sets.Empty exI[of _ "{}"]) next case (Compl B) then obtain A where A: "B = X -` A ∩ Ω" "A ∈ sigma_sets Ω' M'" by auto then have [simp]: "Ω - B = X -` (Ω' - A) ∩ Ω" by (auto simp add: funcset_mem [OF X]) with A(2) show ?case by (auto intro: sigma_sets.Compl) next case (Union F) then have "∀i. ∃B. F i = X -` B ∩ Ω ∧ B ∈ sigma_sets Ω' M'" by auto from choice[OF this] guess A .. note A = this with A show ?case by (auto simp: vimage_UN[symmetric] intro: sigma_sets.Union) qed qed qed lemma (in ring_of_sets) UNION_in_sets: fixes A:: "nat ⇒ 'a set" assumes A: "range A ⊆ M" shows "(⋃i∈{0..<n}. A i) ∈ M" proof (induct n) case 0 show ?case by simp next case (Suc n) thus ?case by (simp add: atLeastLessThanSuc) (metis A Un UNIV_I image_subset_iff) qed lemma (in ring_of_sets) range_disjointed_sets: assumes A: "range A ⊆ M" shows "range (disjointed A) ⊆ M" proof (auto simp add: disjointed_def) fix n show "A n - (⋃i∈{0..<n}. A i) ∈ M" using UNION_in_sets by (metis A Diff UNIV_I image_subset_iff) qed lemma (in algebra) range_disjointed_sets': "range A ⊆ M ⟹ range (disjointed A) ⊆ M" using range_disjointed_sets . lemma sigma_algebra_disjoint_iff: "sigma_algebra Ω M ⟷ algebra Ω M ∧ (∀A. range A ⊆ M ⟶ disjoint_family A ⟶ (⋃i::nat. A i) ∈ M)" proof (auto simp add: sigma_algebra_iff) fix A :: "nat ⇒ 'a set" assume M: "algebra Ω M" and A: "range A ⊆ M" and UnA: "∀A. range A ⊆ M ⟶ disjoint_family A ⟶ (⋃i::nat. A i) ∈ M" hence "range (disjointed A) ⊆ M ⟶ disjoint_family (disjointed A) ⟶ (⋃i. disjointed A i) ∈ M" by blast hence "(⋃i. disjointed A i) ∈ M" by (simp add: algebra.range_disjointed_sets'[of Ω] M A disjoint_family_disjointed) thus "(⋃i::nat. A i) ∈ M" by (simp add: UN_disjointed_eq) qed subsubsection ‹Ring generated by a semiring› definition (in semiring_of_sets) "generated_ring = { ⋃C | C. C ⊆ M ∧ finite C ∧ disjoint C }" lemma (in semiring_of_sets) generated_ringE[elim?]: assumes "a ∈ generated_ring" obtains C where "finite C" "disjoint C" "C ⊆ M" "a = ⋃C" using assms unfolding generated_ring_def by auto lemma (in semiring_of_sets) generated_ringI[intro?]: assumes "finite C" "disjoint C" "C ⊆ M" "a = ⋃C" shows "a ∈ generated_ring" using assms unfolding generated_ring_def by auto lemma (in semiring_of_sets) generated_ringI_Basic: "A ∈ M ⟹ A ∈ generated_ring" by (rule generated_ringI[of "{A}"]) (auto simp: disjoint_def) lemma (in semiring_of_sets) generated_ring_disjoint_Un[intro]: assumes a: "a ∈ generated_ring" and b: "b ∈ generated_ring" and "a ∩ b = {}" shows "a ∪ b ∈ generated_ring" proof - from a guess Ca .. note Ca = this from b guess Cb .. note Cb = this show ?thesis proof show "disjoint (Ca ∪ Cb)" using ‹a ∩ b = {}› Ca Cb by (auto intro!: disjoint_union) qed (insert Ca Cb, auto) qed lemma (in semiring_of_sets) generated_ring_empty: "{} ∈ generated_ring" by (auto simp: generated_ring_def disjoint_def) lemma (in semiring_of_sets) generated_ring_disjoint_Union: assumes "finite A" shows "A ⊆ generated_ring ⟹ disjoint A ⟹ ⋃A ∈ generated_ring" using assms by (induct A) (auto simp: disjoint_def intro!: generated_ring_disjoint_Un generated_ring_empty) lemma (in semiring_of_sets) generated_ring_disjoint_UNION: "finite I ⟹ disjoint (A ` I) ⟹ (⋀i. i ∈ I ⟹ A i ∈ generated_ring) ⟹ UNION I A ∈ generated_ring" by (intro generated_ring_disjoint_Union) auto lemma (in semiring_of_sets) generated_ring_Int: assumes a: "a ∈ generated_ring" and b: "b ∈ generated_ring" shows "a ∩ b ∈ generated_ring" proof - from a guess Ca .. note Ca = this from b guess Cb .. note Cb = this define C where "C = (λ(a,b). a ∩ b)` (Ca×Cb)" show ?thesis proof show "disjoint C" proof (simp add: disjoint_def C_def, intro ballI impI) fix a1 b1 a2 b2 assume sets: "a1 ∈ Ca" "b1 ∈ Cb" "a2 ∈ Ca" "b2 ∈ Cb" assume "a1 ∩ b1 ≠ a2 ∩ b2" then have "a1 ≠ a2 ∨ b1 ≠ b2" by auto then show "(a1 ∩ b1) ∩ (a2 ∩ b2) = {}" proof assume "a1 ≠ a2" with sets Ca have "a1 ∩ a2 = {}" by (auto simp: disjoint_def) then show ?thesis by auto next assume "b1 ≠ b2" with sets Cb have "b1 ∩ b2 = {}" by (auto simp: disjoint_def) then show ?thesis by auto qed qed qed (insert Ca Cb, auto simp: C_def) qed lemma (in semiring_of_sets) generated_ring_Inter: assumes "finite A" "A ≠ {}" shows "A ⊆ generated_ring ⟹ ⋂A ∈ generated_ring" using assms by (induct A rule: finite_ne_induct) (auto intro: generated_ring_Int) lemma (in semiring_of_sets) generated_ring_INTER: "finite I ⟹ I ≠ {} ⟹ (⋀i. i ∈ I ⟹ A i ∈ generated_ring) ⟹ INTER I A ∈ generated_ring" by (intro generated_ring_Inter) auto lemma (in semiring_of_sets) generating_ring: "ring_of_sets Ω generated_ring" proof (rule ring_of_setsI) let ?R = generated_ring show "?R ⊆ Pow Ω" using sets_into_space by (auto simp: generated_ring_def generated_ring_empty) show "{} ∈ ?R" by (rule generated_ring_empty) { fix a assume a: "a ∈ ?R" then guess Ca .. note Ca = this fix b assume b: "b ∈ ?R" then guess Cb .. note Cb = this show "a - b ∈ ?R" proof cases assume "Cb = {}" with Cb ‹a ∈ ?R› show ?thesis by simp next assume "Cb ≠ {}" with Ca Cb have "a - b = (⋃a'∈Ca. ⋂b'∈Cb. a' - b')" by auto also have "… ∈ ?R" proof (intro generated_ring_INTER generated_ring_disjoint_UNION) fix a b assume "a ∈ Ca" "b ∈ Cb" with Ca Cb Diff_cover[of a b] show "a - b ∈ ?R" by (auto simp add: generated_ring_def) (metis DiffI Diff_eq_empty_iff empty_iff) next show "disjoint ((λa'. ⋂b'∈Cb. a' - b')`Ca)" using Ca by (auto simp add: disjoint_def ‹Cb ≠ {}›) next show "finite Ca" "finite Cb" "Cb ≠ {}" by fact+ qed finally show "a - b ∈ ?R" . qed } note Diff = this fix a b assume sets: "a ∈ ?R" "b ∈ ?R" have "a ∪ b = (a - b) ∪ (a ∩ b) ∪ (b - a)" by auto also have "… ∈ ?R" by (intro sets generated_ring_disjoint_Un generated_ring_Int Diff) auto finally show "a ∪ b ∈ ?R" . qed lemma (in semiring_of_sets) sigma_sets_generated_ring_eq: "sigma_sets Ω generated_ring = sigma_sets Ω M" proof interpret M: sigma_algebra Ω "sigma_sets Ω M" using space_closed by (rule sigma_algebra_sigma_sets) show "sigma_sets Ω generated_ring ⊆ sigma_sets Ω M" by (blast intro!: sigma_sets_mono elim: generated_ringE) qed (auto intro!: generated_ringI_Basic sigma_sets_mono) subsubsection ‹A Two-Element Series› definition binaryset :: "'a set ⇒ 'a set ⇒ nat ⇒ 'a set" where "binaryset A B = (λx. {})(0 := A, Suc 0 := B)" lemma range_binaryset_eq: "range(binaryset A B) = {A,B,{}}" apply (simp add: binaryset_def) apply (rule set_eqI) apply (auto simp add: image_iff) done lemma UN_binaryset_eq: "(⋃i. binaryset A B i) = A ∪ B" by (simp add: range_binaryset_eq cong del: strong_SUP_cong) subsubsection ‹Closed CDI› definition closed_cdi where "closed_cdi Ω M ⟷ M ⊆ Pow Ω & (∀s ∈ M. Ω - s ∈ M) & (∀A. (range A ⊆ M) & (A 0 = {}) & (∀n. A n ⊆ A (Suc n)) ⟶ (⋃i. A i) ∈ M) & (∀A. (range A ⊆ M) & disjoint_family A ⟶ (⋃i::nat. A i) ∈ M)" inductive_set smallest_ccdi_sets :: "'a set ⇒ 'a set set ⇒ 'a set set" for Ω M where Basic [intro]: "a ∈ M ⟹ a ∈ smallest_ccdi_sets Ω M" | Compl [intro]: "a ∈ smallest_ccdi_sets Ω M ⟹ Ω - a ∈ smallest_ccdi_sets Ω M" | Inc: "range A ∈ Pow(smallest_ccdi_sets Ω M) ⟹ A 0 = {} ⟹ (⋀n. A n ⊆ A (Suc n)) ⟹ (⋃i. A i) ∈ smallest_ccdi_sets Ω M" | Disj: "range A ∈ Pow(smallest_ccdi_sets Ω M) ⟹ disjoint_family A ⟹ (⋃i::nat. A i) ∈ smallest_ccdi_sets Ω M" lemma (in subset_class) smallest_closed_cdi1: "M ⊆ smallest_ccdi_sets Ω M" by auto lemma (in subset_class) smallest_ccdi_sets: "smallest_ccdi_sets Ω M ⊆ Pow Ω" apply (rule subsetI) apply (erule smallest_ccdi_sets.induct) apply (auto intro: range_subsetD dest: sets_into_space) done lemma (in subset_class) smallest_closed_cdi2: "closed_cdi Ω (smallest_ccdi_sets Ω M)" apply (auto simp add: closed_cdi_def smallest_ccdi_sets) apply (blast intro: smallest_ccdi_sets.Inc smallest_ccdi_sets.Disj) + done lemma closed_cdi_subset: "closed_cdi Ω M ⟹ M ⊆ Pow Ω" by (simp add: closed_cdi_def) lemma closed_cdi_Compl: "closed_cdi Ω M ⟹ s ∈ M ⟹ Ω - s ∈ M" by (simp add: closed_cdi_def) lemma closed_cdi_Inc: "closed_cdi Ω M ⟹ range A ⊆ M ⟹ A 0 = {} ⟹ (!!n. A n ⊆ A (Suc n)) ⟹ (⋃i. A i) ∈ M" by (simp add: closed_cdi_def) lemma closed_cdi_Disj: "closed_cdi Ω M ⟹ range A ⊆ M ⟹ disjoint_family A ⟹ (⋃i::nat. A i) ∈ M" by (simp add: closed_cdi_def) lemma closed_cdi_Un: assumes cdi: "closed_cdi Ω M" and empty: "{} ∈ M" and A: "A ∈ M" and B: "B ∈ M" and disj: "A ∩ B = {}" shows "A ∪ B ∈ M" proof - have ra: "range (binaryset A B) ⊆ M" by (simp add: range_binaryset_eq empty A B) have di: "disjoint_family (binaryset A B)" using disj by (simp add: disjoint_family_on_def binaryset_def Int_commute) from closed_cdi_Disj [OF cdi ra di] show ?thesis by (simp add: UN_binaryset_eq) qed lemma (in algebra) smallest_ccdi_sets_Un: assumes A: "A ∈ smallest_ccdi_sets Ω M" and B: "B ∈ smallest_ccdi_sets Ω M" and disj: "A ∩ B = {}" shows "A ∪ B ∈ smallest_ccdi_sets Ω M" proof - have ra: "range (binaryset A B) ∈ Pow (smallest_ccdi_sets Ω M)" by (simp add: range_binaryset_eq A B smallest_ccdi_sets.Basic) have di: "disjoint_family (binaryset A B)" using disj by (simp add: disjoint_family_on_def binaryset_def Int_commute) from Disj [OF ra di] show ?thesis by (simp add: UN_binaryset_eq) qed lemma (in algebra) smallest_ccdi_sets_Int1: assumes a: "a ∈ M" shows "b ∈ smallest_ccdi_sets Ω M ⟹ a ∩ b ∈ smallest_ccdi_sets Ω M" proof (induct rule: smallest_ccdi_sets.induct) case (Basic x) thus ?case by (metis a Int smallest_ccdi_sets.Basic) next case (Compl x) have "a ∩ (Ω - x) = Ω - ((Ω - a) ∪ (a ∩ x))" by blast also have "... ∈ smallest_ccdi_sets Ω M" by (metis smallest_ccdi_sets.Compl a Compl(2) Diff_Int2 Diff_Int_distrib2 Diff_disjoint Int_Diff Int_empty_right smallest_ccdi_sets_Un smallest_ccdi_sets.Basic smallest_ccdi_sets.Compl) finally show ?case . next case (Inc A) have 1: "(⋃i. (λi. a ∩ A i) i) = a ∩ (⋃i. A i)" by blast have "range (λi. a ∩ A i) ∈ Pow(smallest_ccdi_sets Ω M)" using Inc by blast moreover have "(λi. a ∩ A i) 0 = {}" by (simp add: Inc) moreover have "!!n. (λi. a ∩ A i) n ⊆ (λi. a ∩ A i) (Suc n)" using Inc by blast ultimately have 2: "(⋃i. (λi. a ∩ A i) i) ∈ smallest_ccdi_sets Ω M" by (rule smallest_ccdi_sets.Inc) show ?case by (metis 1 2) next case (Disj A) have 1: "(⋃i. (λi. a ∩ A i) i) = a ∩ (⋃i. A i)" by blast have "range (λi. a ∩ A i) ∈ Pow(smallest_ccdi_sets Ω M)" using Disj by blast moreover have "disjoint_family (λi. a ∩ A i)" using Disj by (auto simp add: disjoint_family_on_def) ultimately have 2: "(⋃i. (λi. a ∩ A i) i) ∈ smallest_ccdi_sets Ω M" by (rule smallest_ccdi_sets.Disj) show ?case by (metis 1 2) qed lemma (in algebra) smallest_ccdi_sets_Int: assumes b: "b ∈ smallest_ccdi_sets Ω M" shows "a ∈ smallest_ccdi_sets Ω M ⟹ a ∩ b ∈ smallest_ccdi_sets Ω M" proof (induct rule: smallest_ccdi_sets.induct) case (Basic x) thus ?case by (metis b smallest_ccdi_sets_Int1) next case (Compl x) have "(Ω - x) ∩ b = Ω - (x ∩ b ∪ (Ω - b))" by blast also have "... ∈ smallest_ccdi_sets Ω M" by (metis Compl(2) Diff_disjoint Int_Diff Int_commute Int_empty_right b smallest_ccdi_sets.Compl smallest_ccdi_sets_Un) finally show ?case . next case (Inc A) have 1: "(⋃i. (λi. A i ∩ b) i) = (⋃i. A i) ∩ b" by blast have "range (λi. A i ∩ b) ∈ Pow(smallest_ccdi_sets Ω M)" using Inc by blast moreover have "(λi. A i ∩ b) 0 = {}" by (simp add: Inc) moreover have "!!n. (λi. A i ∩ b) n ⊆ (λi. A i ∩ b) (Suc n)" using Inc by blast ultimately have 2: "(⋃i. (λi. A i ∩ b) i) ∈ smallest_ccdi_sets Ω M" by (rule smallest_ccdi_sets.Inc) show ?case by (metis 1 2) next case (Disj A) have 1: "(⋃i. (λi. A i ∩ b) i) = (⋃i. A i) ∩ b" by blast have "range (λi. A i ∩ b) ∈ Pow(smallest_ccdi_sets Ω M)" using Disj by blast moreover have "disjoint_family (λi. A i ∩ b)" using Disj by (auto simp add: disjoint_family_on_def) ultimately have 2: "(⋃i. (λi. A i ∩ b) i) ∈ smallest_ccdi_sets Ω M" by (rule smallest_ccdi_sets.Disj) show ?case by (metis 1 2) qed lemma (in algebra) sigma_property_disjoint_lemma: assumes sbC: "M ⊆ C" and ccdi: "closed_cdi Ω C" shows "sigma_sets Ω M ⊆ C" proof - have "smallest_ccdi_sets Ω M ∈ {B . M ⊆ B ∧ sigma_algebra Ω B}" apply (auto simp add: sigma_algebra_disjoint_iff algebra_iff_Int smallest_ccdi_sets_Int) apply (metis Union_Pow_eq Union_upper subsetD smallest_ccdi_sets) apply (blast intro: smallest_ccdi_sets.Disj) done hence "sigma_sets (Ω) (M) ⊆ smallest_ccdi_sets Ω M" by clarsimp (drule sigma_algebra.sigma_sets_subset [where a="M"], auto) also have "... ⊆ C" proof fix x assume x: "x ∈ smallest_ccdi_sets Ω M" thus "x ∈ C" proof (induct rule: smallest_ccdi_sets.induct) case (Basic x) thus ?case by (metis Basic subsetD sbC) next case (Compl x) thus ?case by (blast intro: closed_cdi_Compl [OF ccdi, simplified]) next case (Inc A) thus ?case by (auto intro: closed_cdi_Inc [OF ccdi, simplified]) next case (Disj A) thus ?case by (auto intro: closed_cdi_Disj [OF ccdi, simplified]) qed qed finally show ?thesis . qed lemma (in algebra) sigma_property_disjoint: assumes sbC: "M ⊆ C" and compl: "!!s. s ∈ C ∩ sigma_sets (Ω) (M) ⟹ Ω - s ∈ C" and inc: "!!A. range A ⊆ C ∩ sigma_sets (Ω) (M) ⟹ A 0 = {} ⟹ (!!n. A n ⊆ A (Suc n)) ⟹ (⋃i. A i) ∈ C" and disj: "!!A. range A ⊆ C ∩ sigma_sets (Ω) (M) ⟹ disjoint_family A ⟹ (⋃i::nat. A i) ∈ C" shows "sigma_sets (Ω) (M) ⊆ C" proof - have "sigma_sets (Ω) (M) ⊆ C ∩ sigma_sets (Ω) (M)" proof (rule sigma_property_disjoint_lemma) show "M ⊆ C ∩ sigma_sets (Ω) (M)" by (metis Int_greatest Set.subsetI sbC sigma_sets.Basic) next show "closed_cdi Ω (C ∩ sigma_sets (Ω) (M))" by (simp add: closed_cdi_def compl inc disj) (metis PowI Set.subsetI le_infI2 sigma_sets_into_sp space_closed IntE sigma_sets.Compl range_subsetD sigma_sets.Union) qed thus ?thesis by blast qed subsubsection ‹Dynkin systems› locale dynkin_system = subset_class + assumes space: "Ω ∈ M" and compl[intro!]: "⋀A. A ∈ M ⟹ Ω - A ∈ M" and UN[intro!]: "⋀A. disjoint_family A ⟹ range A ⊆ M ⟹ (⋃i::nat. A i) ∈ M" lemma (in dynkin_system) empty[intro, simp]: "{} ∈ M" using space compl[of "Ω"] by simp lemma (in dynkin_system) diff: assumes sets: "D ∈ M" "E ∈ M" and "D ⊆ E" shows "E - D ∈ M" proof - let ?f = "λx. if x = 0 then D else if x = Suc 0 then Ω - E else {}" have "range ?f = {D, Ω - E, {}}" by (auto simp: image_iff) moreover have "D ∪ (Ω - E) = (⋃i. ?f i)" by (auto simp: image_iff split: if_split_asm) moreover have "disjoint_family ?f" unfolding disjoint_family_on_def using ‹D ∈ M›[THEN sets_into_space] ‹D ⊆ E› by auto ultimately have "Ω - (D ∪ (Ω - E)) ∈ M" using sets by auto also have "Ω - (D ∪ (Ω - E)) = E - D" using assms sets_into_space by auto finally show ?thesis . qed lemma dynkin_systemI: assumes "⋀ A. A ∈ M ⟹ A ⊆ Ω" "Ω ∈ M" assumes "⋀ A. A ∈ M ⟹ Ω - A ∈ M" assumes "⋀ A. disjoint_family A ⟹ range A ⊆ M ⟹ (⋃i::nat. A i) ∈ M" shows "dynkin_system Ω M" using assms by (auto simp: dynkin_system_def dynkin_system_axioms_def subset_class_def) lemma dynkin_systemI': assumes 1: "⋀ A. A ∈ M ⟹ A ⊆ Ω" assumes empty: "{} ∈ M" assumes Diff: "⋀ A. A ∈ M ⟹ Ω - A ∈ M" assumes 2: "⋀ A. disjoint_family A ⟹ range A ⊆ M ⟹ (⋃i::nat. A i) ∈ M" shows "dynkin_system Ω M" proof - from Diff[OF empty] have "Ω ∈ M" by auto from 1 this Diff 2 show ?thesis by (intro dynkin_systemI) auto qed lemma dynkin_system_trivial: shows "dynkin_system A (Pow A)" by (rule dynkin_systemI) auto lemma sigma_algebra_imp_dynkin_system: assumes "sigma_algebra Ω M" shows "dynkin_system Ω M" proof - interpret sigma_algebra Ω M by fact show ?thesis using sets_into_space by (fastforce intro!: dynkin_systemI) qed subsubsection "Intersection sets systems" definition "Int_stable M ⟷ (∀ a ∈ M. ∀ b ∈ M. a ∩ b ∈ M)" lemma (in algebra) Int_stable: "Int_stable M" unfolding Int_stable_def by auto lemma Int_stableI_image: "(⋀i j. i ∈ I ⟹ j ∈ I ⟹ ∃k∈I. A i ∩ A j = A k) ⟹ Int_stable (A ` I)" by (auto simp: Int_stable_def image_def) lemma Int_stableI: "(⋀a b. a ∈ A ⟹ b ∈ A ⟹ a ∩ b ∈ A) ⟹ Int_stable A" unfolding Int_stable_def by auto lemma Int_stableD: "Int_stable M ⟹ a ∈ M ⟹ b ∈ M ⟹ a ∩ b ∈ M" unfolding Int_stable_def by auto lemma (in dynkin_system) sigma_algebra_eq_Int_stable: "sigma_algebra Ω M ⟷ Int_stable M" proof assume "sigma_algebra Ω M" then show "Int_stable M" unfolding sigma_algebra_def using algebra.Int_stable by auto next assume "Int_stable M" show "sigma_algebra Ω M" unfolding sigma_algebra_disjoint_iff algebra_iff_Un proof (intro conjI ballI allI impI) show "M ⊆ Pow (Ω)" using sets_into_space by auto next fix A B assume "A ∈ M" "B ∈ M" then have "A ∪ B = Ω - ((Ω - A) ∩ (Ω - B))" "Ω - A ∈ M" "Ω - B ∈ M" using sets_into_space by auto then show "A ∪ B ∈ M" using ‹Int_stable M› unfolding Int_stable_def by auto qed auto qed subsubsection "Smallest Dynkin systems" definition dynkin where "dynkin Ω M = (⋂{D. dynkin_system Ω D ∧ M ⊆ D})" lemma dynkin_system_dynkin: assumes "M ⊆ Pow (Ω)" shows "dynkin_system Ω (dynkin Ω M)" proof (rule dynkin_systemI) fix A assume "A ∈ dynkin Ω M" moreover { fix D assume "A ∈ D" and d: "dynkin_system Ω D" then have "A ⊆ Ω" by (auto simp: dynkin_system_def subset_class_def) } moreover have "{D. dynkin_system Ω D ∧ M ⊆ D} ≠ {}" using assms dynkin_system_trivial by fastforce ultimately show "A ⊆ Ω" unfolding dynkin_def using assms by auto next show "Ω ∈ dynkin Ω M" unfolding dynkin_def using dynkin_system.space by fastforce next fix A assume "A ∈ dynkin Ω M" then show "Ω - A ∈ dynkin Ω M" unfolding dynkin_def using dynkin_system.compl by force next fix A :: "nat ⇒ 'a set" assume A: "disjoint_family A" "range A ⊆ dynkin Ω M" show "(⋃i. A i) ∈ dynkin Ω M" unfolding dynkin_def proof (simp, safe) fix D assume "dynkin_system Ω D" "M ⊆ D" with A have "(⋃i. A i) ∈ D" by (intro dynkin_system.UN) (auto simp: dynkin_def) then show "(⋃i. A i) ∈ D" by auto qed qed lemma dynkin_Basic[intro]: "A ∈ M ⟹ A ∈ dynkin Ω M" unfolding dynkin_def by auto lemma (in dynkin_system) restricted_dynkin_system: assumes "D ∈ M" shows "dynkin_system Ω {Q. Q ⊆ Ω ∧ Q ∩ D ∈ M}" proof (rule dynkin_systemI, simp_all) have "Ω ∩ D = D" using ‹D ∈ M› sets_into_space by auto then show "Ω ∩ D ∈ M" using ‹D ∈ M› by auto next fix A assume "A ⊆ Ω ∧ A ∩ D ∈ M" moreover have "(Ω - A) ∩ D = (Ω - (A ∩ D)) - (Ω - D)" by auto ultimately show "Ω - A ⊆ Ω ∧ (Ω - A) ∩ D ∈ M" using ‹D ∈ M› by (auto intro: diff) next fix A :: "nat ⇒ 'a set" assume "disjoint_family A" "range A ⊆ {Q. Q ⊆ Ω ∧ Q ∩ D ∈ M}" then have "⋀i. A i ⊆ Ω" "disjoint_family (λi. A i ∩ D)" "range (λi. A i ∩ D) ⊆ M" "(⋃x. A x) ∩ D = (⋃x. A x ∩ D)" by ((fastforce simp: disjoint_family_on_def)+) then show "(⋃x. A x) ⊆ Ω ∧ (⋃x. A x) ∩ D ∈ M" by (auto simp del: UN_simps) qed lemma (in dynkin_system) dynkin_subset: assumes "N ⊆ M" shows "dynkin Ω N ⊆ M" proof - have "dynkin_system Ω M" .. then have "dynkin_system Ω M" using assms unfolding dynkin_system_def dynkin_system_axioms_def subset_class_def by simp with ‹N ⊆ M› show ?thesis by (auto simp add: dynkin_def) qed lemma sigma_eq_dynkin: assumes sets: "M ⊆ Pow Ω" assumes "Int_stable M" shows "sigma_sets Ω M = dynkin Ω M" proof - have "dynkin Ω M ⊆ sigma_sets (Ω) (M)" using sigma_algebra_imp_dynkin_system unfolding dynkin_def sigma_sets_least_sigma_algebra[OF sets] by auto moreover interpret dynkin_system Ω "dynkin Ω M" using dynkin_system_dynkin[OF sets] . have "sigma_algebra Ω (dynkin Ω M)" unfolding sigma_algebra_eq_Int_stable Int_stable_def proof (intro ballI) fix A B assume "A ∈ dynkin Ω M" "B ∈ dynkin Ω M" let ?D = "λE. {Q. Q ⊆ Ω ∧ Q ∩ E ∈ dynkin Ω M}" have "M ⊆ ?D B" proof fix E assume "E ∈ M" then have "M ⊆ ?D E" "E ∈ dynkin Ω M" using sets_into_space ‹Int_stable M› by (auto simp: Int_stable_def) then have "dynkin Ω M ⊆ ?D E" using restricted_dynkin_system ‹E ∈ dynkin Ω M› by (intro dynkin_system.dynkin_subset) simp_all then have "B ∈ ?D E" using ‹B ∈ dynkin Ω M› by auto then have "E ∩ B ∈ dynkin Ω M" by (subst Int_commute) simp then show "E ∈ ?D B" using sets ‹E ∈ M› by auto qed then have "dynkin Ω M ⊆ ?D B" using restricted_dynkin_system ‹B ∈ dynkin Ω M› by (intro dynkin_system.dynkin_subset) simp_all then show "A ∩ B ∈ dynkin Ω M" using ‹A ∈ dynkin Ω M› sets_into_space by auto qed from sigma_algebra.sigma_sets_subset[OF this, of "M"] have "sigma_sets (Ω) (M) ⊆ dynkin Ω M" by auto ultimately have "sigma_sets (Ω) (M) = dynkin Ω M" by auto then show ?thesis by (auto simp: dynkin_def) qed lemma (in dynkin_system) dynkin_idem: "dynkin Ω M = M" proof - have "dynkin Ω M = M" proof show "M ⊆ dynkin Ω M" using dynkin_Basic by auto show "dynkin Ω M ⊆ M" by (intro dynkin_subset) auto qed then show ?thesis by (auto simp: dynkin_def) qed lemma (in dynkin_system) dynkin_lemma: assumes "Int_stable E" and E: "E ⊆ M" "M ⊆ sigma_sets Ω E" shows "sigma_sets Ω E = M" proof - have "E ⊆ Pow Ω" using E sets_into_space by force then have *: "sigma_sets Ω E = dynkin Ω E" using ‹Int_stable E› by (rule sigma_eq_dynkin) then have "dynkin Ω E = M" using assms dynkin_subset[OF E(1)] by simp with * show ?thesis using assms by (auto simp: dynkin_def) qed subsubsection ‹Induction rule for intersection-stable generators› text ‹The reason to introduce Dynkin-systems is the following induction rules for $\sigma$-algebras generated by a generator closed under intersection.› lemma sigma_sets_induct_disjoint[consumes 3, case_names basic empty compl union]: assumes "Int_stable G" and closed: "G ⊆ Pow Ω" and A: "A ∈ sigma_sets Ω G" assumes basic: "⋀A. A ∈ G ⟹ P A" and empty: "P {}" and compl: "⋀A. A ∈ sigma_sets Ω G ⟹ P A ⟹ P (Ω - A)" and union: "⋀A. disjoint_family A ⟹ range A ⊆ sigma_sets Ω G ⟹ (⋀i. P (A i)) ⟹ P (⋃i::nat. A i)" shows "P A" proof - let ?D = "{ A ∈ sigma_sets Ω G. P A }" interpret sigma_algebra Ω "sigma_sets Ω G" using closed by (rule sigma_algebra_sigma_sets) from compl[OF _ empty] closed have space: "P Ω" by simp interpret dynkin_system Ω ?D by standard (auto dest: sets_into_space intro!: space compl union) have "sigma_sets Ω G = ?D" by (rule dynkin_lemma) (auto simp: basic ‹Int_stable G›) with A show ?thesis by auto qed subsection ‹Measure type› definition positive :: "'a set set ⇒ ('a set ⇒ ennreal) ⇒ bool" where "positive M μ ⟷ μ {} = 0" definition countably_additive :: "'a set set ⇒ ('a set ⇒ ennreal) ⇒ bool" where "countably_additive M f ⟷ (∀A. range A ⊆ M ⟶ disjoint_family A ⟶ (⋃i. A i) ∈ M ⟶ (∑i. f (A i)) = f (⋃i. A i))" definition measure_space :: "'a set ⇒ 'a set set ⇒ ('a set ⇒ ennreal) ⇒ bool" where "measure_space Ω A μ ⟷ sigma_algebra Ω A ∧ positive A μ ∧ countably_additive A μ" typedef 'a measure = "{(Ω::'a set, A, μ). (∀a∈-A. μ a = 0) ∧ measure_space Ω A μ }" proof have "sigma_algebra UNIV {{}, UNIV}" by (auto simp: sigma_algebra_iff2) then show "(UNIV, {{}, UNIV}, λA. 0) ∈ {(Ω, A, μ). (∀a∈-A. μ a = 0) ∧ measure_space Ω A μ} " by (auto simp: measure_space_def positive_def countably_additive_def) qed definition space :: "'a measure ⇒ 'a set" where "space M = fst (Rep_measure M)" definition sets :: "'a measure ⇒ 'a set set" where "sets M = fst (snd (Rep_measure M))" definition emeasure :: "'a measure ⇒ 'a set ⇒ ennreal" where "emeasure M = snd (snd (Rep_measure M))" definition measure :: "'a measure ⇒ 'a set ⇒ real" where "measure M A = enn2real (emeasure M A)" declare [[coercion sets]] declare [[coercion measure]] declare [[coercion emeasure]] lemma measure_space: "measure_space (space M) (sets M) (emeasure M)" by (cases M) (auto simp: space_def sets_def emeasure_def Abs_measure_inverse) interpretation sets: sigma_algebra "space M" "sets M" for M :: "'a measure" using measure_space[of M] by (auto simp: measure_space_def) definition measure_of :: "'a set ⇒ 'a set set ⇒ ('a set ⇒ ennreal) ⇒ 'a measure" where "measure_of Ω A μ = Abs_measure (Ω, if A ⊆ Pow Ω then sigma_sets Ω A else {{}, Ω}, λa. if a ∈ sigma_sets Ω A ∧ measure_space Ω (sigma_sets Ω A) μ then μ a else 0)" abbreviation "sigma Ω A ≡ measure_of Ω A (λx. 0)" lemma measure_space_0: "A ⊆ Pow Ω ⟹ measure_space Ω (sigma_sets Ω A) (λx. 0)" unfolding measure_space_def by (auto intro!: sigma_algebra_sigma_sets simp: positive_def countably_additive_def) lemma sigma_algebra_trivial: "sigma_algebra Ω {{}, Ω}" by unfold_locales(fastforce intro: exI[where x="{{}}"] exI[where x="{Ω}"])+ lemma measure_space_0': "measure_space Ω {{}, Ω} (λx. 0)" by(simp add: measure_space_def positive_def countably_additive_def sigma_algebra_trivial) lemma measure_space_closed: assumes "measure_space Ω M μ" shows "M ⊆ Pow Ω" proof - interpret sigma_algebra Ω M using assms by(simp add: measure_space_def) show ?thesis by(rule space_closed) qed lemma (in ring_of_sets) positive_cong_eq: "(⋀a. a ∈ M ⟹ μ' a = μ a) ⟹ positive M μ' = positive M μ" by (auto simp add: positive_def) lemma (in sigma_algebra) countably_additive_eq: "(⋀a. a ∈ M ⟹ μ' a = μ a) ⟹ countably_additive M μ' = countably_additive M μ" unfolding countably_additive_def by (intro arg_cong[where f=All] ext) (auto simp add: countably_additive_def subset_eq) lemma measure_space_eq: assumes closed: "A ⊆ Pow Ω" and eq: "⋀a. a ∈ sigma_sets Ω A ⟹ μ a = μ' a" shows "measure_space Ω (sigma_sets Ω A) μ = measure_space Ω (sigma_sets Ω A) μ'" proof - interpret sigma_algebra Ω "sigma_sets Ω A" using closed by (rule sigma_algebra_sigma_sets) from positive_cong_eq[OF eq, of "λi. i"] countably_additive_eq[OF eq, of "λi. i"] show ?thesis by (auto simp: measure_space_def) qed lemma measure_of_eq: assumes closed: "A ⊆ Pow Ω" and eq: "(⋀a. a ∈ sigma_sets Ω A ⟹ μ a = μ' a)" shows "measure_of Ω A μ = measure_of Ω A μ'" proof - have "measure_space Ω (sigma_sets Ω A) μ = measure_space Ω (sigma_sets Ω A) μ'" using assms by (rule measure_space_eq) with eq show ?thesis by (auto simp add: measure_of_def intro!: arg_cong[where f=Abs_measure]) qed lemma shows space_measure_of_conv: "space (measure_of Ω A μ) = Ω" (is ?space) and sets_measure_of_conv: "sets (measure_of Ω A μ) = (if A ⊆ Pow Ω then sigma_sets Ω A else {{}, Ω})" (is ?sets) and emeasure_measure_of_conv: "emeasure (measure_of Ω A μ) = (λB. if B ∈ sigma_sets Ω A ∧ measure_space Ω (sigma_sets Ω A) μ then μ B else 0)" (is ?emeasure) proof - have "?space ∧ ?sets ∧ ?emeasure" proof(cases "measure_space Ω (sigma_sets Ω A) μ") case True from measure_space_closed[OF this] sigma_sets_superset_generator[of A Ω] have "A ⊆ Pow Ω" by simp hence "measure_space Ω (sigma_sets Ω A) μ = measure_space Ω (sigma_sets Ω A) (λa. if a ∈ sigma_sets Ω A then μ a else 0)" by(rule measure_space_eq) auto with True ‹A ⊆ Pow Ω› show ?thesis by(simp add: measure_of_def space_def sets_def emeasure_def Abs_measure_inverse) next case False thus ?thesis by(cases "A ⊆ Pow Ω")(simp_all add: Abs_measure_inverse measure_of_def sets_def space_def emeasure_def measure_space_0 measure_space_0') qed thus ?space ?sets ?emeasure by simp_all qed lemma [simp]: assumes A: "A ⊆ Pow Ω" shows sets_measure_of: "sets (measure_of Ω A μ) = sigma_sets Ω A" and space_measure_of: "space (measure_of Ω A μ) = Ω" using assms by(simp_all add: sets_measure_of_conv space_measure_of_conv) lemma space_in_measure_of[simp]: "Ω ∈ sets (measure_of Ω M μ)" by (subst sets_measure_of_conv) (auto simp: sigma_sets_top) lemma (in sigma_algebra) sets_measure_of_eq[simp]: "sets (measure_of Ω M μ) = M" using space_closed by (auto intro!: sigma_sets_eq) lemma (in sigma_algebra) space_measure_of_eq[simp]: "space (measure_of Ω M μ) = Ω" by (rule space_measure_of_conv) lemma measure_of_subset: "M ⊆ Pow Ω ⟹ M' ⊆ M ⟹ sets (measure_of Ω M' μ) ⊆ sets (measure_of Ω M μ')" by (auto intro!: sigma_sets_subseteq) lemma emeasure_sigma: "emeasure (sigma Ω A) = (λx. 0)" unfolding measure_of_def emeasure_def by (subst Abs_measure_inverse) (auto simp: measure_space_def positive_def countably_additive_def intro!: sigma_algebra_sigma_sets sigma_algebra_trivial) lemma sigma_sets_mono'': assumes "A ∈ sigma_sets C D" assumes "B ⊆ D" assumes "D ⊆ Pow C" shows "sigma_sets A B ⊆ sigma_sets C D" proof fix x assume "x ∈ sigma_sets A B" thus "x ∈ sigma_sets C D" proof induct case (Basic a) with assms have "a ∈ D" by auto thus ?case .. next case Empty show ?case by (rule sigma_sets.Empty) next from assms have "A ∈ sets (sigma C D)" by (subst sets_measure_of[OF ‹D ⊆ Pow C›]) moreover case (Compl a) hence "a ∈ sets (sigma C D)" by (subst sets_measure_of[OF ‹D ⊆ Pow C›]) ultimately have "A - a ∈ sets (sigma C D)" .. thus ?case by (subst (asm) sets_measure_of[OF ‹D ⊆ Pow C›]) next case (Union a) thus ?case by (intro sigma_sets.Union) qed qed lemma in_measure_of[intro, simp]: "M ⊆ Pow Ω ⟹ A ∈ M ⟹ A ∈ sets (measure_of Ω M μ)" by auto lemma space_empty_iff: "space N = {} ⟷ sets N = {{}}" by (metis Pow_empty Sup_bot_conv(1) cSup_singleton empty_iff sets.sigma_sets_eq sets.space_closed sigma_sets_top subset_singletonD) subsubsection ‹Constructing simple @{typ "'a measure"}› lemma emeasure_measure_of: assumes M: "M = measure_of Ω A μ" assumes ms: "A ⊆ Pow Ω" "positive (sets M) μ" "countably_additive (sets M) μ" assumes X: "X ∈ sets M" shows "emeasure M X = μ X" proof - interpret sigma_algebra Ω "sigma_sets Ω A" by (rule sigma_algebra_sigma_sets) fact have "measure_space Ω (sigma_sets Ω A) μ" using ms M by (simp add: measure_space_def sigma_algebra_sigma_sets) thus ?thesis using X ms by(simp add: M emeasure_measure_of_conv sets_measure_of_conv) qed lemma emeasure_measure_of_sigma: assumes ms: "sigma_algebra Ω M" "positive M μ" "countably_additive M μ" assumes A: "A ∈ M" shows "emeasure (measure_of Ω M μ) A = μ A" proof - interpret sigma_algebra Ω M by fact have "measure_space Ω (sigma_sets Ω M) μ" using ms sigma_sets_eq by (simp add: measure_space_def) thus ?thesis by(simp add: emeasure_measure_of_conv A) qed lemma measure_cases[cases type: measure]: obtains (measure) Ω A μ where "x = Abs_measure (Ω, A, μ)" "∀a∈-A. μ a = 0" "measure_space Ω A μ" by atomize_elim (cases x, auto) lemma sets_le_imp_space_le: "sets A ⊆ sets B ⟹ space A ⊆ space B" by (auto dest: sets.sets_into_space) lemma sets_eq_imp_space_eq: "sets M = sets M' ⟹ space M = space M'" by (auto intro!: antisym sets_le_imp_space_le) lemma emeasure_notin_sets: "A ∉ sets M ⟹ emeasure M A = 0" by (cases M) (auto simp: sets_def emeasure_def Abs_measure_inverse measure_space_def) lemma emeasure_neq_0_sets: "emeasure M A ≠ 0 ⟹ A ∈ sets M" using emeasure_notin_sets[of A M] by blast lemma measure_notin_sets: "A ∉ sets M ⟹ measure M A = 0" by (simp add: measure_def emeasure_notin_sets zero_ennreal.rep_eq) lemma measure_eqI: fixes M N :: "'a measure" assumes "sets M = sets N" and eq: "⋀A. A ∈ sets M ⟹ emeasure M A = emeasure N A" shows "M = N" proof (cases M N rule: measure_cases[case_product measure_cases]) case (measure_measure Ω A μ Ω' A' μ') interpret M: sigma_algebra Ω A using measure_measure by (auto simp: measure_space_def) interpret N: sigma_algebra Ω' A' using measure_measure by (auto simp: measure_space_def) have "A = sets M" "A' = sets N" using measure_measure by (simp_all add: sets_def Abs_measure_inverse) with ‹sets M = sets N› have AA': "A = A'" by simp moreover from M.top N.top M.space_closed N.space_closed AA' have "Ω = Ω'" by auto moreover { fix B have "μ B = μ' B" proof cases assume "B ∈ A" with eq ‹A = sets M› have "emeasure M B = emeasure N B" by simp with measure_measure show "μ B = μ' B" by (simp add: emeasure_def Abs_measure_inverse) next assume "B ∉ A" with ‹A = sets M› ‹A' = sets N› ‹A = A'› have "B ∉ sets M" "B ∉ sets N" by auto then have "emeasure M B = 0" "emeasure N B = 0" by (simp_all add: emeasure_notin_sets) with measure_measure show "μ B = μ' B" by (simp add: emeasure_def Abs_measure_inverse) qed } then have "μ = μ'" by auto ultimately show "M = N" by (simp add: measure_measure) qed lemma sigma_eqI: assumes [simp]: "M ⊆ Pow Ω" "N ⊆ Pow Ω" "sigma_sets Ω M = sigma_sets Ω N" shows "sigma Ω M = sigma Ω N" by (rule measure_eqI) (simp_all add: emeasure_sigma) subsubsection ‹Measurable functions› definition measurable :: "'a measure ⇒ 'b measure ⇒ ('a ⇒ 'b) set" (infixr "→⇩_{M}" 60) where "measurable A B = {f ∈ space A → space B. ∀y ∈ sets B. f -` y ∩ space A ∈ sets A}" lemma measurableI: "(⋀x. x ∈ space M ⟹ f x ∈ space N) ⟹ (⋀A. A ∈ sets N ⟹ f -` A ∩ space M ∈ sets M) ⟹ f ∈ measurable M N" by (auto simp: measurable_def) lemma measurable_space: "f ∈ measurable M A ⟹ x ∈ space M ⟹ f x ∈ space A" unfolding measurable_def by auto lemma measurable_sets: "f ∈ measurable M A ⟹ S ∈ sets A ⟹ f -` S ∩ space M ∈ sets M" unfolding measurable_def by auto lemma measurable_sets_Collect: assumes f: "f ∈ measurable M N" and P: "{x∈space N. P x} ∈ sets N" shows "{x∈space M. P (f x)} ∈ sets M" proof - have "f -` {x ∈ space N. P x} ∩ space M = {x∈space M. P (f x)}" using measurable_space[OF f] by auto with measurable_sets[OF f P] show ?thesis by simp qed lemma measurable_sigma_sets: assumes B: "sets N = sigma_sets Ω A" "A ⊆ Pow Ω" and f: "f ∈ space M → Ω" and ba: "⋀y. y ∈ A ⟹ (f -` y) ∩ space M ∈ sets M" shows "f ∈ measurable M N" proof - interpret A: sigma_algebra Ω "sigma_sets Ω A" using B(2) by (rule sigma_algebra_sigma_sets) from B sets.top[of N] A.top sets.space_closed[of N] A.space_closed have Ω: "Ω = space N" by force { fix X assume "X ∈ sigma_sets Ω A" then have "f -` X ∩ space M ∈ sets M ∧ X ⊆ Ω" proof induct case (Basic a) then show ?case by (auto simp add: ba) (metis B(2) subsetD PowD) next case (Compl a) have [simp]: "f -` Ω ∩ space M = space M" by (auto simp add: funcset_mem [OF f]) then show ?case by (auto simp add: vimage_Diff Diff_Int_distrib2 sets.compl_sets Compl) next case (Union a) then show ?case by (simp add: vimage_UN, simp only: UN_extend_simps(4)) blast qed auto } with f show ?thesis by (auto simp add: measurable_def B Ω) qed lemma measurable_measure_of: assumes B: "N ⊆ Pow Ω" and f: "f ∈ space M → Ω" and ba: "⋀y. y ∈ N ⟹ (f -` y) ∩ space M ∈ sets M" shows "f ∈ measurable M (measure_of Ω N μ)" proof - have "sets (measure_of Ω N μ) = sigma_sets Ω N" using B by (rule sets_measure_of) from this assms show ?thesis by (rule measurable_sigma_sets) qed lemma measurable_iff_measure_of: assumes "N ⊆ Pow Ω" "f ∈ space M → Ω" shows "f ∈ measurable M (measure_of Ω N μ) ⟷ (∀A∈N. f -` A ∩ space M ∈ sets M)" by (metis assms in_measure_of measurable_measure_of assms measurable_sets) lemma measurable_cong_sets: assumes sets: "sets M = sets M'" "sets N = sets N'" shows "measurable M N = measurable M' N'" using sets[THEN sets_eq_imp_space_eq] sets by (simp add: measurable_def) lemma measurable_cong: assumes "⋀w. w ∈ space M ⟹ f w = g w" shows "f ∈ measurable M M' ⟷ g ∈ measurable M M'" unfolding measurable_def using assms by (simp cong: vimage_inter_cong Pi_cong) lemma measurable_cong': assumes "⋀w. w ∈ space M =simp=> f w = g w" shows "f ∈ measurable M M' ⟷ g ∈ measurable M M'" unfolding measurable_def using assms by (simp cong: vimage_inter_cong Pi_cong add: simp_implies_def) lemma measurable_cong_strong: "M = N ⟹ M' = N' ⟹ (⋀w. w ∈ space M ⟹ f w = g w) ⟹ f ∈ measurable M M' ⟷ g ∈ measurable N N'" by (metis measurable_cong) lemma measurable_compose: assumes f: "f ∈ measurable M N" and g: "g ∈ measurable N L" shows "(λx. g (f x)) ∈ measurable M L" proof - have "⋀A. (λx. g (f x)) -` A ∩ space M = f -` (g -` A ∩ space N) ∩ space M" using measurable_space[OF f] by auto with measurable_space[OF f] measurable_space[OF g] show ?thesis by (auto intro: measurable_sets[OF f] measurable_sets[OF g] simp del: vimage_Int simp add: measurable_def) qed lemma measurable_comp: "f ∈ measurable M N ⟹ g ∈ measurable N L ⟹ g ∘ f ∈ measurable M L" using measurable_compose[of f M N g L] by (simp add: comp_def) lemma measurable_const: "c ∈ space M' ⟹ (λx. c) ∈ measurable M M'" by (auto simp add: measurable_def) lemma measurable_ident: "id ∈ measurable M M" by (auto simp add: measurable_def) lemma measurable_id: "(λx. x) ∈ measurable M M" by (simp add: measurable_def) lemma measurable_ident_sets: assumes eq: "sets M = sets M'" shows "(λx. x) ∈ measurable M M'" using measurable_ident[of M] unfolding id_def measurable_def eq sets_eq_imp_space_eq[OF eq] . lemma sets_Least: assumes meas: "⋀i::nat. {x∈space M. P i x} ∈ M" shows "(λx. LEAST j. P j x) -` A ∩ space M ∈ sets M" proof - { fix i have "(λx. LEAST j. P j x) -` {i} ∩ space M ∈ sets M" proof cases assume i: "(LEAST j. False) = i" have "(λx. LEAST j. P j x) -` {i} ∩ space M = {x∈space M. P i x} ∩ (space M - (⋃j<i. {x∈space M. P j x})) ∪ (space M - (⋃i. {x∈space M. P i x}))" by (simp add: set_eq_iff, safe) (insert i, auto dest: Least_le intro: LeastI intro!: Least_equality) with meas show ?thesis by (auto intro!: sets.Int) next assume i: "(LEAST j. False) ≠ i" then have "(λx. LEAST j. P j x) -` {i} ∩ space M = {x∈space M. P i x} ∩ (space M - (⋃j<i. {x∈space M. P j x}))" proof (simp add: set_eq_iff, safe) fix x assume neq: "(LEAST j. False) ≠ (LEAST j. P j x)" have "∃j. P j x" by (rule ccontr) (insert neq, auto) then show "P (LEAST j. P j x) x" by (rule LeastI_ex) qed (auto dest: Least_le intro!: Least_equality) with meas show ?thesis by auto qed } then have "(⋃i∈A. (λx. LEAST j. P j x) -` {i} ∩ space M) ∈ sets M" by (intro sets.countable_UN) auto moreover have "(⋃i∈A. (λx. LEAST j. P j x) -` {i} ∩ space M) = (λx. LEAST j. P j x) -` A ∩ space M" by auto ultimately show ?thesis by auto qed lemma measurable_mono1: "M' ⊆ Pow Ω ⟹ M ⊆ M' ⟹ measurable (measure_of Ω M μ) N ⊆ measurable (measure_of Ω M' μ') N" using measure_of_subset[of M' Ω M] by (auto simp add: measurable_def) subsubsection ‹Counting space› definition count_space :: "'a set ⇒ 'a measure" where "count_space Ω = measure_of Ω (Pow Ω) (λA. if finite A then of_nat (card A) else ∞)" lemma shows space_count_space[simp]: "space (count_space Ω) = Ω" and sets_count_space[simp]: "sets (count_space Ω) = Pow Ω" using sigma_sets_into_sp[of "Pow Ω" Ω] by (auto simp: count_space_def) lemma measurable_count_space_eq1[simp]: "f ∈ measurable (count_space A) M ⟷ f ∈ A → space M" unfolding measurable_def by simp lemma measurable_compose_countable': assumes f: "⋀i. i ∈ I ⟹ (λx. f i x) ∈ measurable M N" and g: "g ∈ measurable M (count_space I)" and I: "countable I" shows "(λx. f (g x) x) ∈ measurable M N" unfolding measurable_def proof safe fix x assume "x ∈ space M" then show "f (g x) x ∈ space N" using measurable_space[OF f] g[THEN measurable_space] by auto next fix A assume A: "A ∈ sets N" have "(λx. f (g x) x) -` A ∩ space M = (⋃i∈I. (g -` {i} ∩ space M) ∩ (f i -` A ∩ space M))" using measurable_space[OF g] by auto also have "… ∈ sets M" using f[THEN measurable_sets, OF _ A] g[THEN measurable_sets] by (auto intro!: sets.countable_UN' I intro: sets.Int[OF measurable_sets measurable_sets]) finally show "(λx. f (g x) x) -` A ∩ space M ∈ sets M" . qed lemma measurable_count_space_eq_countable: assumes "countable A" shows "f ∈ measurable M (count_space A) ⟷ (f ∈ space M → A ∧ (∀a∈A. f -` {a} ∩ space M ∈ sets M))" proof - { fix X assume "X ⊆ A" "f ∈ space M → A" with ‹countable A› have "f -` X ∩ space M = (⋃a∈X. f -` {a} ∩ space M)" "countable X" by (auto dest: countable_subset) moreover assume "∀a∈A. f -` {a} ∩ space M ∈ sets M" ultimately have "f -` X ∩ space M ∈ sets M" using ‹X ⊆ A› by (auto intro!: sets.countable_UN' simp del: UN_simps) } then show ?thesis unfolding measurable_def by auto qed lemma measurable_count_space_eq2: "finite A ⟹ f ∈ measurable M (count_space A) ⟷ (f ∈ space M → A ∧ (∀a∈A. f -` {a} ∩ space M ∈ sets M))" by (intro measurable_count_space_eq_countable countable_finite) lemma measurable_count_space_eq2_countable: fixes f :: "'a => 'c::countable" shows "f ∈ measurable M (count_space A) ⟷ (f ∈ space M → A ∧ (∀a∈A. f -` {a} ∩ space M ∈ sets M))" by (intro measurable_count_space_eq_countable countableI_type) lemma measurable_compose_countable: assumes f: "⋀i::'i::countable. (λx. f i x) ∈ measurable M N" and g: "g ∈ measurable M (count_space UNIV)" shows "(λx. f (g x) x) ∈ measurable M N" by (rule measurable_compose_countable'[OF assms]) auto lemma measurable_count_space_const: "(λx. c) ∈ measurable M (count_space UNIV)" by (simp add: measurable_const) lemma measurable_count_space: "f ∈ measurable (count_space A) (count_space UNIV)" by simp lemma measurable_compose_rev: assumes f: "f ∈ measurable L N" and g: "g ∈ measurable M L" shows "(λx. f (g x)) ∈ measurable M N" using measurable_compose[OF g f] . lemma measurable_empty_iff: "space N = {} ⟹ f ∈ measurable M N ⟷ space M = {}" by (auto simp add: measurable_def Pi_iff) subsubsection ‹Extend measure› definition "extend_measure Ω I G μ = (if (∃μ'. (∀i∈I. μ' (G i) = μ i) ∧ measure_space Ω (sigma_sets Ω (G`I)) μ') ∧ ¬ (∀i∈I. μ i = 0) then measure_of Ω (G`I) (SOME μ'. (∀i∈I. μ' (G i) = μ i) ∧ measure_space Ω (sigma_sets Ω (G`I)) μ') else measure_of Ω (G`I) (λ_. 0))" lemma space_extend_measure: "G ` I ⊆ Pow Ω ⟹ space (extend_measure Ω I G μ) = Ω" unfolding extend_measure_def by simp lemma sets_extend_measure: "G ` I ⊆ Pow Ω ⟹ sets (extend_measure Ω I G μ) = sigma_sets Ω (G`I)" unfolding extend_measure_def by simp lemma emeasure_extend_measure: assumes M: "M = extend_measure Ω I G μ" and eq: "⋀i. i ∈ I ⟹ μ' (G i) = μ i" and ms: "G ` I ⊆ Pow Ω" "positive (sets M) μ'" "countably_additive (sets M) μ'" and "i ∈ I" shows "emeasure M (G i) = μ i" proof cases assume *: "(∀i∈I. μ i = 0)" with M have M_eq: "M = measure_of Ω (G`I) (λ_. 0)" by (simp add: extend_measure_def) from measure_space_0[OF ms(1)] ms ‹i∈I› have "emeasure M (G i) = 0" by (intro emeasure_measure_of[OF M_eq]) (auto simp add: M measure_space_def sets_extend_measure) with ‹i∈I› * show ?thesis by simp next define P where "P μ' ⟷ (∀i∈I. μ' (G i) = μ i) ∧ measure_space Ω (sigma_sets Ω (G`I)) μ'" for μ' assume "¬ (∀i∈I. μ i = 0)" moreover have "measure_space (space M) (sets M) μ'" using ms unfolding measure_space_def by auto standard with ms eq have "∃μ'. P μ'" unfolding P_def by (intro exI[of _ μ']) (auto simp add: M space_extend_measure sets_extend_measure) ultimately have M_eq: "M = measure_of Ω (G`I) (Eps P)" by (simp add: M extend_measure_def P_def[symmetric]) from ‹∃μ'. P μ'› have P: "P (Eps P)" by (rule someI_ex) show "emeasure M (G i) = μ i" proof (subst emeasure_measure_of[OF M_eq]) have sets_M: "sets M = sigma_sets Ω (G`I)" using M_eq ms by (auto simp: sets_extend_measure) then show "G i ∈ sets M" using ‹i ∈ I› by auto show "positive (sets M) (Eps P)" "countably_additive (sets M) (Eps P)" "Eps P (G i) = μ i" using P ‹i∈I› by (auto simp add: sets_M measure_space_def P_def) qed fact qed lemma emeasure_extend_measure_Pair: assumes M: "M = extend_measure Ω {(i, j). I i j} (λ(i, j). G i j) (λ(i, j). μ i j)" and eq: "⋀i j. I i j ⟹ μ' (G i j) = μ i j" and ms: "⋀i j. I i j ⟹ G i j ∈ Pow Ω" "positive (sets M) μ'" "countably_additive (sets M) μ'" and "I i j" shows "emeasure M (G i j) = μ i j" using emeasure_extend_measure[OF M _ _ ms(2,3), of "(i,j)"] eq ms(1) ‹I i j› by (auto simp: subset_eq) subsection ‹The smallest $\sigma$-algebra regarding a function› definition "vimage_algebra X f M = sigma X {f -` A ∩ X | A. A ∈ sets M}" lemma space_vimage_algebra[simp]: "space (vimage_algebra X f M) = X" unfolding vimage_algebra_def by (rule space_measure_of) auto lemma sets_vimage_algebra: "sets (vimage_algebra X f M) = sigma_sets X {f -` A ∩ X | A. A ∈ sets M}" unfolding vimage_algebra_def by (rule sets_measure_of) auto lemma sets_vimage_algebra2: "f ∈ X → space M ⟹ sets (vimage_algebra X f M) = {f -` A ∩ X | A. A ∈ sets M}" using sigma_sets_vimage_commute[of f X "space M" "sets M"] unfolding sets_vimage_algebra sets.sigma_sets_eq by simp lemma sets_vimage_algebra_cong: "sets M = sets N ⟹ sets (vimage_algebra X f M) = sets (vimage_algebra X f N)" by (simp add: sets_vimage_algebra) lemma vimage_algebra_cong: assumes "X = Y" assumes "⋀x. x ∈ Y ⟹ f x = g x" assumes "sets M = sets N" shows "vimage_algebra X f M = vimage_algebra Y g N" by (auto simp: vimage_algebra_def assms intro!: arg_cong2[where f=sigma]) lemma in_vimage_algebra: "A ∈ sets M ⟹ f -` A ∩ X ∈ sets (vimage_algebra X f M)" by (auto simp: vimage_algebra_def) lemma sets_image_in_sets: assumes N: "space N = X" assumes f: "f ∈ measurable N M" shows "sets (vimage_algebra X f M) ⊆ sets N" unfolding sets_vimage_algebra N[symmetric] by (rule sets.sigma_sets_subset) (auto intro!: measurable_sets f) lemma measurable_vimage_algebra1: "f ∈ X → space M ⟹ f ∈ measurable (vimage_algebra X f M) M" unfolding measurable_def by (auto intro: in_vimage_algebra) lemma measurable_vimage_algebra2: assumes g: "g ∈ space N → X" and f: "(λx. f (g x)) ∈ measurable N M" shows "g ∈ measurable N (vimage_algebra X f M)" unfolding vimage_algebra_def proof (rule measurable_measure_of) fix A assume "A ∈ {f -` A ∩ X | A. A ∈ sets M}" then obtain Y where Y: "Y ∈ sets M" and A: "A = f -` Y ∩ X" by auto then have "g -` A ∩ space N = (λx. f (g x)) -` Y ∩ space N" using g by auto also have "… ∈ sets N" using f Y by (rule measurable_sets) finally show "g -` A ∩ space N ∈ sets N" . qed (insert g, auto) lemma vimage_algebra_sigma: assumes X: "X ⊆ Pow Ω'" and f: "f ∈ Ω → Ω'" shows "vimage_algebra Ω f (sigma Ω' X) = sigma Ω {f -` A ∩ Ω | A. A ∈ X }" (is "?V = ?S") proof (rule measure_eqI) have Ω: "{f -` A ∩ Ω |A. A ∈ X} ⊆ Pow Ω" by auto show "sets ?V = sets ?S" using sigma_sets_vimage_commute[OF f, of X] by (simp add: space_measure_of_conv f sets_vimage_algebra2 Ω X) qed (simp add: vimage_algebra_def emeasure_sigma) lemma vimage_algebra_vimage_algebra_eq: assumes *: "f ∈ X → Y" "g ∈ Y → space M" shows "vimage_algebra X f (vimage_algebra Y g M) = vimage_algebra X (λx. g (f x)) M" (is "?VV = ?V") proof (rule measure_eqI) have "(λx. g (f x)) ∈ X → space M" "⋀A. A ∩ f -` Y ∩ X = A ∩ X" using * by auto with * show "sets ?VV = sets ?V" by (simp add: sets_vimage_algebra2 ex_simps[symmetric] vimage_comp comp_def del: ex_simps) qed (simp add: vimage_algebra_def emeasure_sigma) subsubsection ‹Restricted Space Sigma Algebra› definition restrict_space where "restrict_space M Ω = measure_of (Ω ∩ space M) ((op ∩ Ω) ` sets M) (emeasure M)" lemma space_restrict_space: "space (restrict_space M Ω) = Ω ∩ space M" using sets.sets_into_space unfolding restrict_space_def by (subst space_measure_of) auto lemma space_restrict_space2: "Ω ∈ sets M ⟹ space (restrict_space M Ω) = Ω" by (simp add: space_restrict_space sets.sets_into_space) lemma sets_restrict_space: "sets (restrict_space M Ω) = (op ∩ Ω) ` sets M" unfolding restrict_space_def proof (subst sets_measure_of) show "op ∩ Ω ` sets M ⊆ Pow (Ω ∩ space M)" by (auto dest: sets.sets_into_space) have "sigma_sets (Ω ∩ space M) {((λx. x) -` X) ∩ (Ω ∩ space M) | X. X ∈ sets M} = (λX. X ∩ (Ω ∩ space M)) ` sets M" by (subst sigma_sets_vimage_commute[symmetric, where Ω' = "space M"]) (auto simp add: sets.sigma_sets_eq) moreover have "{((λx. x) -` X) ∩ (Ω ∩ space M) | X. X ∈ sets M} = (λX. X ∩ (Ω ∩ space M)) ` sets M" by auto moreover have "(λX. X ∩ (Ω ∩ space M)) ` sets M = (op ∩ Ω) ` sets M" by (intro image_cong) (auto dest: sets.sets_into_space) ultimately show "sigma_sets (Ω ∩ space M) (op ∩ Ω ` sets M) = op ∩ Ω ` sets M" by simp qed lemma restrict_space_sets_cong: "A = B ⟹ sets M = sets N ⟹ sets (restrict_space M A) = sets (restrict_space N B)" by (auto simp: sets_restrict_space) lemma sets_restrict_space_count_space : "sets (restrict_space (count_space A) B) = sets (count_space (A ∩ B))" by(auto simp add: sets_restrict_space) lemma sets_restrict_UNIV[simp]: "sets (restrict_space M UNIV) = sets M" by (auto simp add: sets_restrict_space) lemma sets_restrict_restrict_space: "sets (restrict_space (restrict_space M A) B) = sets (restrict_space M (A ∩ B))" unfolding sets_restrict_space image_comp by (intro image_cong) auto lemma sets_restrict_space_iff: "Ω ∩ space M ∈ sets M ⟹ A ∈ sets (restrict_space M Ω) ⟷ (A ⊆ Ω ∧ A ∈ sets M)" proof (subst sets_restrict_space, safe) fix A assume "Ω ∩ space M ∈ sets M" and A: "A ∈ sets M" then have "(Ω ∩ space M) ∩ A ∈ sets M" by rule also have "(Ω ∩ space M) ∩ A = Ω ∩ A" using sets.sets_into_space[OF A] by auto finally show "Ω ∩ A ∈ sets M" by auto qed auto lemma sets_restrict_space_cong: "sets M = sets N ⟹ sets (restrict_space M Ω) = sets (restrict_space N Ω)" by (simp add: sets_restrict_space) lemma restrict_space_eq_vimage_algebra: "Ω ⊆ space M ⟹ sets (restrict_space M Ω) = sets (vimage_algebra Ω (λx. x) M)" unfolding restrict_space_def apply (subst sets_measure_of) apply (auto simp add: image_subset_iff dest: sets.sets_into_space) [] apply (auto simp add: sets_vimage_algebra intro!: arg_cong2[where f=sigma_sets]) done lemma sets_Collect_restrict_space_iff: assumes "S ∈ sets M" shows "{x∈space (restrict_space M S). P x} ∈ sets (restrict_space M S) ⟷ {x∈space M. x ∈ S ∧ P x} ∈ sets M" proof - have "{x∈S. P x} = {x∈space M. x ∈ S ∧ P x}" using sets.sets_into_space[OF assms] by auto then show ?thesis by (subst sets_restrict_space_iff) (auto simp add: space_restrict_space assms) qed lemma measurable_restrict_space1: assumes f: "f ∈ measurable M N" shows "f ∈ measurable (restrict_space M Ω) N" unfolding measurable_def proof (intro CollectI conjI ballI) show sp: "f ∈ space (restrict_space M Ω) → space N" using measurable_space[OF f] by (auto simp: space_restrict_space) fix A assume "A ∈ sets N" have "f -` A ∩ space (restrict_space M Ω) = (f -` A ∩ space M) ∩ (Ω ∩ space M)" by (auto simp: space_restrict_space) also have "… ∈ sets (restrict_space M Ω)" unfolding sets_restrict_space using measurable_sets[OF f ‹A ∈ sets N›] by blast finally show "f -` A ∩ space (restrict_space M Ω) ∈ sets (restrict_space M Ω)" . qed lemma measurable_restrict_space2_iff: "f ∈ measurable M (restrict_space N Ω) ⟷ (f ∈ measurable M N ∧ f ∈ space M → Ω)" proof - have "⋀A. f ∈ space M → Ω ⟹ f -` Ω ∩ f -` A ∩ space M = f -` A ∩ space M" by auto then show ?thesis by (auto simp: measurable_def space_restrict_space Pi_Int[symmetric] sets_restrict_space) qed lemma measurable_restrict_space2: "f ∈ space M → Ω ⟹ f ∈ measurable M N ⟹ f ∈ measurable M (restrict_space N Ω)" by (simp add: measurable_restrict_space2_iff) lemma measurable_piecewise_restrict: assumes I: "countable C" and X: "⋀Ω. Ω ∈ C ⟹ Ω ∩ space M ∈ sets M" "space M ⊆ ⋃C" and f: "⋀Ω. Ω ∈ C ⟹ f ∈ measurable (restrict_space M Ω) N" shows "f ∈ measurable M N" proof (rule measurableI) fix x assume "x ∈ space M" with X obtain Ω where "Ω ∈ C" "x ∈ Ω" "x ∈ space M" by auto then show "f x ∈ space N" by (auto simp: space_restrict_space intro: f measurable_space) next fix A assume A: "A ∈ sets N" have "f -` A ∩ space M = (⋃Ω∈C. (f -` A ∩ (Ω ∩ space M)))" using X by (auto simp: subset_eq) also have "… ∈ sets M" using measurable_sets[OF f A] X I by (intro sets.countable_UN') (auto simp: sets_restrict_space_iff space_restrict_space) finally show "f -` A ∩ space M ∈ sets M" . qed lemma measurable_piecewise_restrict_iff: "countable C ⟹ (⋀Ω. Ω ∈ C ⟹ Ω ∩ space M ∈ sets M) ⟹ space M ⊆ (⋃C) ⟹ f ∈ measurable M N ⟷ (∀Ω∈C. f ∈ measurable (restrict_space M Ω) N)" by (auto intro: measurable_piecewise_restrict measurable_restrict_space1) lemma measurable_If_restrict_space_iff: "{x∈space M. P x} ∈ sets M ⟹ (λx. if P x then f x else g x) ∈ measurable M N ⟷ (f ∈ measurable (restrict_space M {x. P x}) N ∧ g ∈ measurable (restrict_space M {x. ¬ P x}) N)" by (subst measurable_piecewise_restrict_iff[where C="{{x. P x}, {x. ¬ P x}}"]) (auto simp: Int_def sets.sets_Collect_neg space_restrict_space conj_commute[of _ "x ∈ space M" for x] cong: measurable_cong') lemma measurable_If: "f ∈ measurable M M' ⟹ g ∈ measurable M M' ⟹ {x∈space M. P x} ∈ sets M ⟹ (λx. if P x then f x else g x) ∈ measurable M M'" unfolding measurable_If_restrict_space_iff by (auto intro: measurable_restrict_space1) lemma measurable_If_set: assumes measure: "f ∈ measurable M M'" "g ∈ measurable M M'" assumes P: "A ∩ space M ∈ sets M" shows "(λx. if x ∈ A then f x else g x) ∈ measurable M M'" proof (rule measurable_If[OF measure]) have "{x ∈ space M. x ∈ A} = A ∩ space M" by auto thus "{x ∈ space M. x ∈ A} ∈ sets M" using ‹A ∩ space M ∈ sets M› by auto qed lemma measurable_restrict_space_iff: "Ω ∩ space M ∈ sets M ⟹ c ∈ space N ⟹ f ∈ measurable (restrict_space M Ω) N ⟷ (λx. if x ∈ Ω then f x else c) ∈ measurable M N" by (subst measurable_If_restrict_space_iff) (simp_all add: Int_def conj_commute measurable_const) lemma restrict_space_singleton: "{x} ∈ sets M ⟹ sets (restrict_space M {x}) = sets (count_space {x})" using sets_restrict_space_iff[of "{x}" M] by (auto simp add: sets_restrict_space_iff dest!: subset_singletonD) lemma measurable_restrict_countable: assumes X[intro]: "countable X" assumes sets[simp]: "⋀x. x ∈ X ⟹ {x} ∈ sets M" assumes space[simp]: "⋀x. x ∈ X ⟹ f x ∈ space N" assumes f: "f ∈ measurable (restrict_space M (- X)) N" shows "f ∈ measurable M N" using f sets.countable[OF sets X] by (intro measurable_piecewise_restrict[where M=M and C="{- X} ∪ ((λx. {x}) ` X)"]) (auto simp: Diff_Int_distrib2 Compl_eq_Diff_UNIV Int_insert_left sets.Diff restrict_space_singleton simp del: sets_count_space cong: measurable_cong_sets) lemma measurable_discrete_difference: assumes f: "f ∈ measurable M N" assumes X: "countable X" "⋀x. x ∈ X ⟹ {x} ∈ sets M" "⋀x. x ∈ X ⟹ g x ∈ space N" assumes eq: "⋀x. x ∈ space M ⟹ x ∉ X ⟹ f x = g x" shows "g ∈ measurable M N" by (rule measurable_restrict_countable[OF X]) (auto simp: eq[symmetric] space_restrict_space cong: measurable_cong' intro: f measurable_restrict_space1) lemma measurable_count_space_extend: "A ⊆ B ⟹ f ∈ space M → A ⟹ f ∈ M →⇩_{M}count_space B ⟹ f ∈ M →⇩_{M}count_space A" by (auto simp: measurable_def) end