Theory Sigma_Algebra

(*  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.
*)

chapter ‹Measure and Integration Theory›

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


section ‹Sigma Algebra›

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›

localetag important› 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›

localetag important› 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  CM. 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 "(iI. 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Ω. iS. P i x}  M"
proof -
  have "{xΩ. iS. P i x} = (iS. {xΩ. P i x})"
    using S  {} by auto
  with assms show ?thesis by auto
qed

subsubsection ‹Ring of sets›

localetag important› 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 "(iI. 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 "CM. 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  (aM. bM. a  b  M)  (aM. bM. a - b  M)"
proof
  assume "ring_of_sets Ω M"
  then interpret ring_of_sets Ω M .
  show "M  Pow Ω  {}  M  (aM. bM. a  b  M)  (aM. bM. 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Ω. iS. P i x}  M"
proof -
  have "{xΩ. iS. P i x} = (iS. {xΩ. P i x})"
    by auto
  with assms show ?thesis by auto
qed

subsubsection ‹Algebra of sets›

localetag important› algebra = ring_of_sets +
  assumes top [iff]: "Ω  M"

lemma (in algebra) compl_sets [intro]:
  "a  M  Ω - a  M"
  by auto

proposition 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

proposition 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)

subsubsectiontag unimportant› ‹Restricted algebras›

abbreviation (in algebra)
  "restricted_space A  ((∩) 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›

localetag important› 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) = (sM  range A. s)"
    by auto
  also have "(sM  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 "A ` range from_nat = range A"
    using surj_from_nat by simp
  then have **: "range ?A' = range A"
    by (simp only: image_comp [symmetric])
  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 cong del: SUP_cong)
  also have "  M" using assms
    by (auto intro!: countable_nat_UN) (metis X  {} from_nat_into subsetD)
  finally show ?thesis .
qed simp

lemma (in sigma_algebra) countable_UN[intro]:
  fixes A :: "'i::countable  'a set"
  assumes "A`X  M"
  shows  "(xX. 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) = (xX. 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  "(xX. A x)  M"
proof -
  have "(xX. A x) = (ito_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   (xX. 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 "(iX. A i)  M"
proof -
  from A have "iX. A i  M" by fast
  hence "Ω - (iX. Ω - A i)  M" by blast
  moreover
  have "(iX. A i) = Ω - (iX. Ω - 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  "(xX. A x)  M"
proof -
  have "(xX. A x) = (ito_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)  (iI. 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 "(aA. {a})  M"
    using assms by (intro countable_UN') auto
  also have "(aA. {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Ω. iI. P i x}  M"
proof -
  have "{xΩ. iI. P i x} = (iI. {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Ω. iI. P i x}  M"
proof -
  have "{xΩ. iI. P i x} = (iI. {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Ω. ∃!iI. P i x}  M"
proof -
  have "{xΩ. ∃!iI. P i x} = {xΩ. iI. P i x  (jI. 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::countableX. 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::countableX. 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

subsubsectiontag unimportant› ‹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: SUP_cong_simp)

lemma Int_range_binary: "a  b = (i::nat. binary a b i)"
  by (simp add: range_binary_eq cong del: INF_cong_simp)

lemma sigma_algebra_iff2:
  "sigma_algebra Ω M 
    M  Pow Ω  {}  M  (s  M. Ω - s  M)
     (A. range A  M ( i::nat. A i)  M)" (is "?P  ?R  ?S  ?V  ?W")
proof
  assume ?P
  then interpret sigma_algebra Ω M .
  from space_closed show "?R  ?S  ?V  ?W"
    by auto
next
  assume "?R  ?S  ?V  ?W"
  then have ?R ?S ?V ?W
    by simp_all
  show ?P
  proof (rule sigma_algebra.intro)
    show "sigma_algebra_axioms M"
      by standard (use ?W in simp)
    from ?W have *: "range (binary a b)  M   (range (binary a b))  M" for a b
      by auto
    show "algebra Ω M"
      unfolding algebra_iff_Un using ?R ?S ?V *
      by (auto simp add: range_binary_eq)
  qed
qed


subsubsection ‹Initial Sigma Algebra›

texttag important› ‹Sigma algebras can naturally be created as the closure of any set of
  M with regard to the properties just postulated.›

inductive_settag important› 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 binary_in_sigma_sets:
  "binary a b i  sigma_sets sp A" if "a  sigma_sets sp A" and "b  sigma_sets sp A"
  using that by (simp add: binary_def)

lemma sigma_sets_Un:
  "a  b  sigma_sets sp A" if "a  sigma_sets sp A" and "b  sigma_sets sp A"
  using that by (simp add: Un_range_binary binary_in_sigma_sets Union)

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 "(iS. a i)  sigma_sets sp A"
proof -
  from ai have "i. (if iS then a i else sp)  sigma_sets sp A"
    by (simp add: sigma_sets.intros(2-) sigma_sets_top)
  hence "(i. (if iS then a i else sp))  sigma_sets sp A"
    by (rule sigma_sets_Inter [OF Asb])
  also have "(i. (if iS then a i else sp)) = (iS. 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"
  using from_nat_into [of B] range_from_nat_into [of B] sigma_sets.Union [of "from_nat_into B" X A]
  by (cases "B = {}") (simp_all add: sigma_sets.Empty cong del: SUP_cong)

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 "(∩) A ` sigma_sets sp st = sigma_sets A ((∩) A ` st)"
proof (intro equalityI subsetI)
  fix x assume "x  (∩) 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) ((∩) 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 ((∩) A ` st)"
    using A  sp by (simp add: Int_absorb2)
next
  fix x assume "x  sigma_sets A ((∩) A ` st)"
  then show "x  (∩) 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)
    then obtain f where "x. f x  sigma_sets sp st  a x = A  f x"
      by metis
    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
      then obtain A where "x. F x = X -` A x  Ω  A x  sigma_sets Ω' M'"
        by metis
      then 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

subsubsectiontag unimportant› ‹Ring generated by a semiring›

definition (in semiring_of_sets) generated_ring :: "'a set set" where
  "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 b obtain Ca Cb
    where Ca: "finite Ca" "disjoint Ca" "Ca  M" "a =  Ca"
      and Cb: "finite Cb" "disjoint Cb" "Cb  M" "b =  Cb"
    using generated_ringE by metis
  show ?thesis
  proof
    from a  b = {} Ca Cb show "disjoint (Ca  Cb)"
      by (auto intro!: disjoint_union)
  qed (use Ca Cb in 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)  (A ` I)  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 b obtain Ca Cb
    where Ca: "finite Ca" "disjoint Ca" "Ca  M" "a =  Ca"
      and Cb: "finite Cb" "disjoint Cb" "Cb  M" "b =  Cb"
    using generated_ringE by metis
  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 (use Ca Cb in 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)  (A ` I)  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 b assume "a  ?R" "b  ?R"
    then obtain Ca Cb
      where Ca: "finite Ca" "disjoint Ca" "Ca  M" "a =  Ca"
        and Cb: "finite Cb" "disjoint Cb" "Cb  M" "b =  Cb"
      using generated_ringE by metis
    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)

subsubsectiontag unimportant› ‹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: SUP_cong_simp)

subsubsection ‹Closed CDI›

definitiontag important› closed_cdi :: "'a set  'a set set  bool" 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›

localetag important› 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 UN by auto fastforce
  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"

definitiontag important› Int_stable :: "'a set set  bool" where
"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  kI. 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"

definitiontag important› Dynkin :: "'a set  'a set set  'a set set" 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)  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›

texttag important› ‹The reason to introduce Dynkin-systems is the following induction rules for σ›-algebras
generated by a generator closed under intersection.›

proposition 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›

definitiontag important› positive :: "'a set set  ('a set  ennreal)  bool" where
  "positive M μ  μ {} = 0"

definitiontag important› 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))"

definitiontag important› measure_space :: "'a set  'a set set  ('a set  ennreal)  bool" where
"measure_space Ω A μ 
  sigma_algebra Ω A  positive A μ  countably_additive A μ"

typedeftag important› '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

definitiontag important› space :: "'a measure  'a set" where
  "space M = fst (Rep_measure M)"

definitiontag important› sets :: "'a measure  'a set set" where
  "sets M = fst (snd (Rep_measure M))"

definitiontag important› emeasure :: "'a measure  'a set  ennreal" where
  "emeasure M = snd (snd (Rep_measure M))"

definitiontag important› 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)

definitiontag important› 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

proposition 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›

definitiontag important› 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: "{xspace N. P x}  sets N" shows "{xspace M. P (f x)}  sets M"
proof -
  have "f -` {x  space N. P x}  space M = {xspace 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 μ)  (AN. 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_simp:
  "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. {xspace 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 =
        {xspace M. P i x}  (space M - (j<i. {xspace M. P j x}))  (space M - (i. {xspace 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 =
        {xspace M. P i x}  (space M - (j<i. {xspace 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 "(iA. (λx. LEAST j. P j x) -` {i}  space M)  sets M"
    by (intro sets.countable_UN) auto
  moreover have "(iA. (λ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›

definitiontag important› 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 = (iI. (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  (aA. f -` {a}  space M  sets M))"
proof -
  { fix X assume "X  A" "f  space M  A"
    with countable A have "f -` X  space M = (aX. f -` {a}  space M)" "countable X"
      by (auto dest: countable_subset)
    moreover assume "aA. 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  (aA. 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  (aA. 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)

subsubsectiontag unimportant› ‹Extend measure›

definition extend_measure :: "'a set  'b set  ('b  'a set)  ('b  ennreal)  'a measure"
  where
"extend_measure Ω I G μ =
  (if (μ'. (iI. μ' (G i) = μ i)  measure_space Ω (sigma_sets Ω (G`I)) μ')  ¬ (iI. μ i = 0)
      then measure_of Ω (G`I) (SOME μ'. (iI. μ' (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 *: "(iI. μ 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 iI
  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 iI * show ?thesis
    by simp
next
  define P where "P μ'  (iI. μ' (G i) = μ i)  measure_space Ω (sigma_sets Ω (G`I)) μ'" for μ'
  assume "¬ (iI. μ 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 iI 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 σ›-algebra regarding a function›

definitiontag important› vimage_algebra :: "'a set  ('a  'b)  'b measure  'a measure" where
  "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 vimage_comp comp_def flip: ex_simps)
qed (simp add: vimage_algebra_def emeasure_sigma)

subsubsection ‹Restricted Space Sigma Algebra›

definition restrict_space :: "'a measure  'a set  'a measure" where
  "restrict_space M Ω = measure_of (Ω  space M) (((∩) Ω) ` 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 [simp]: "Ω  sets M  space (restrict_space M Ω) = Ω"
  by (simp add: space_restrict_space sets.sets_into_space)

lemma sets_restrict_space: "sets (restrict_space M Ω) = ((∩) Ω) ` sets M"
  unfolding restrict_space_def
proof (subst sets_measure_of)
  show "(∩) Ω ` 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 = ((∩) Ω) ` sets M"
    by (intro image_cong) (auto dest: sets.sets_into_space)
  ultimately show "sigma_sets (Ω  space M) ((∩) Ω ` sets M) = (∩) Ω ` 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 "{xspace (restrict_space M S). P x}  sets (restrict_space M S)  {xspace M. x  S  P x}  sets M"
proof -
  have "{xS. P x} = {xspace 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:
  "{xspace 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'  {xspace 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