src/HOL/Analysis/Tagged_Division.thy
changeset 70136 f03a01a18c6e
parent 69861 62e47f06d22c
child 70817 dd675800469d
equal deleted inserted replaced
70135:ad6d4a14adb5 70136:f03a01a18c6e
    29 lemmas scaleR_simps = scaleR_zero_left scaleR_minus_left scaleR_left_diff_distrib
    29 lemmas scaleR_simps = scaleR_zero_left scaleR_minus_left scaleR_left_diff_distrib
    30   scaleR_zero_right scaleR_minus_right scaleR_right_diff_distrib scaleR_eq_0_iff
    30   scaleR_zero_right scaleR_minus_right scaleR_right_diff_distrib scaleR_eq_0_iff
    31   scaleR_cancel_left scaleR_cancel_right scaleR_add_right scaleR_add_left real_vector_class.scaleR_one
    31   scaleR_cancel_left scaleR_cancel_right scaleR_add_right scaleR_add_left real_vector_class.scaleR_one
    32 
    32 
    33 
    33 
    34 subsection%unimportant \<open>Sundries\<close>
    34 subsection\<^marker>\<open>tag unimportant\<close> \<open>Sundries\<close>
    35 
    35 
    36 
    36 
    37 text\<open>A transitive relation is well-founded if all initial segments are finite.\<close>
    37 text\<open>A transitive relation is well-founded if all initial segments are finite.\<close>
    38 lemma wf_finite_segments:
    38 lemma wf_finite_segments:
    39   assumes "irrefl r" and "trans r" and "\<And>x. finite {y. (y, x) \<in> r}"
    39   assumes "irrefl r" and "trans r" and "\<And>x. finite {y. (y, x) \<in> r}"
   130 lemma interval_not_empty: "\<forall>i\<in>Basis. a\<bullet>i \<le> b\<bullet>i \<Longrightarrow> cbox a b \<noteq> {}"
   130 lemma interval_not_empty: "\<forall>i\<in>Basis. a\<bullet>i \<le> b\<bullet>i \<Longrightarrow> cbox a b \<noteq> {}"
   131   by (simp add: box_ne_empty)
   131   by (simp add: box_ne_empty)
   132 
   132 
   133 subsection \<open>Bounds on intervals where they exist\<close>
   133 subsection \<open>Bounds on intervals where they exist\<close>
   134 
   134 
   135 definition%important interval_upperbound :: "('a::euclidean_space) set \<Rightarrow> 'a"
   135 definition\<^marker>\<open>tag important\<close> interval_upperbound :: "('a::euclidean_space) set \<Rightarrow> 'a"
   136   where "interval_upperbound s = (\<Sum>i\<in>Basis. (SUP x\<in>s. x\<bullet>i) *\<^sub>R i)"
   136   where "interval_upperbound s = (\<Sum>i\<in>Basis. (SUP x\<in>s. x\<bullet>i) *\<^sub>R i)"
   137 
   137 
   138 definition%important interval_lowerbound :: "('a::euclidean_space) set \<Rightarrow> 'a"
   138 definition\<^marker>\<open>tag important\<close> interval_lowerbound :: "('a::euclidean_space) set \<Rightarrow> 'a"
   139   where "interval_lowerbound s = (\<Sum>i\<in>Basis. (INF x\<in>s. x\<bullet>i) *\<^sub>R i)"
   139   where "interval_lowerbound s = (\<Sum>i\<in>Basis. (INF x\<in>s. x\<bullet>i) *\<^sub>R i)"
   140 
   140 
   141 lemma interval_upperbound[simp]:
   141 lemma interval_upperbound[simp]:
   142   "\<forall>i\<in>Basis. a\<bullet>i \<le> b\<bullet>i \<Longrightarrow>
   142   "\<forall>i\<in>Basis. a\<bullet>i \<le> b\<bullet>i \<Longrightarrow>
   143     interval_upperbound (cbox a b) = (b::'a::euclidean_space)"
   143     interval_upperbound (cbox a b) = (b::'a::euclidean_space)"
   192       by (subst sum_Basis_prod_eq) (auto simp add: sum_prod)
   192       by (subst sum_Basis_prod_eq) (auto simp add: sum_prod)
   193 qed
   193 qed
   194 
   194 
   195 subsection \<open>The notion of a gauge --- simply an open set containing the point\<close>
   195 subsection \<open>The notion of a gauge --- simply an open set containing the point\<close>
   196 
   196 
   197 definition%important "gauge \<gamma> \<longleftrightarrow> (\<forall>x. x \<in> \<gamma> x \<and> open (\<gamma> x))"
   197 definition\<^marker>\<open>tag important\<close> "gauge \<gamma> \<longleftrightarrow> (\<forall>x. x \<in> \<gamma> x \<and> open (\<gamma> x))"
   198 
   198 
   199 lemma gaugeI:
   199 lemma gaugeI:
   200   assumes "\<And>x. x \<in> \<gamma> x"
   200   assumes "\<And>x. x \<in> \<gamma> x"
   201     and "\<And>x. open (\<gamma> x)"
   201     and "\<And>x. open (\<gamma> x)"
   202   shows "gauge \<gamma>"
   202   shows "gauge \<gamma>"
   249   shows "gauge (\<lambda>x. {y. f y \<in> d (f x)})"
   249   shows "gauge (\<lambda>x. {y. f y \<in> d (f x)})"
   250   using assms unfolding gauge_def by force
   250   using assms unfolding gauge_def by force
   251 
   251 
   252 subsection \<open>Divisions\<close>
   252 subsection \<open>Divisions\<close>
   253 
   253 
   254 definition%important division_of (infixl "division'_of" 40)
   254 definition\<^marker>\<open>tag important\<close> division_of (infixl "division'_of" 40)
   255 where
   255 where
   256   "s division_of i \<longleftrightarrow>
   256   "s division_of i \<longleftrightarrow>
   257     finite s \<and>
   257     finite s \<and>
   258     (\<forall>K\<in>s. K \<subseteq> i \<and> K \<noteq> {} \<and> (\<exists>a b. K = cbox a b)) \<and>
   258     (\<forall>K\<in>s. K \<subseteq> i \<and> K \<noteq> {} \<and> (\<exists>a b. K = cbox a b)) \<and>
   259     (\<forall>K1\<in>s. \<forall>K2\<in>s. K1 \<noteq> K2 \<longrightarrow> interior(K1) \<inter> interior(K2) = {}) \<and>
   259     (\<forall>K1\<in>s. \<forall>K2\<in>s. K1 \<noteq> K2 \<longrightarrow> interior(K1) \<inter> interior(K2) = {}) \<and>
   995   }
   995   }
   996 qed
   996 qed
   997 
   997 
   998 subsection \<open>Tagged (partial) divisions\<close>
   998 subsection \<open>Tagged (partial) divisions\<close>
   999 
   999 
  1000 definition%important tagged_partial_division_of (infixr "tagged'_partial'_division'_of" 40)
  1000 definition\<^marker>\<open>tag important\<close> tagged_partial_division_of (infixr "tagged'_partial'_division'_of" 40)
  1001   where "s tagged_partial_division_of i \<longleftrightarrow>
  1001   where "s tagged_partial_division_of i \<longleftrightarrow>
  1002     finite s \<and>
  1002     finite s \<and>
  1003     (\<forall>x K. (x, K) \<in> s \<longrightarrow> x \<in> K \<and> K \<subseteq> i \<and> (\<exists>a b. K = cbox a b)) \<and>
  1003     (\<forall>x K. (x, K) \<in> s \<longrightarrow> x \<in> K \<and> K \<subseteq> i \<and> (\<exists>a b. K = cbox a b)) \<and>
  1004     (\<forall>x1 K1 x2 K2. (x1, K1) \<in> s \<and> (x2, K2) \<in> s \<and> (x1, K1) \<noteq> (x2, K2) \<longrightarrow>
  1004     (\<forall>x1 K1 x2 K2. (x1, K1) \<in> s \<and> (x2, K2) \<in> s \<and> (x1, K1) \<noteq> (x2, K2) \<longrightarrow>
  1005       interior K1 \<inter> interior K2 = {})"
  1005       interior K1 \<inter> interior K2 = {})"
  1012     and "\<And>x K. (x,K) \<in> s \<Longrightarrow> \<exists>a b. K = cbox a b"
  1012     and "\<And>x K. (x,K) \<in> s \<Longrightarrow> \<exists>a b. K = cbox a b"
  1013     and "\<And>x1 K1 x2 K2. (x1,K1) \<in> s \<Longrightarrow>
  1013     and "\<And>x1 K1 x2 K2. (x1,K1) \<in> s \<Longrightarrow>
  1014       (x2, K2) \<in> s \<Longrightarrow> (x1, K1) \<noteq> (x2, K2) \<Longrightarrow> interior K1 \<inter> interior K2 = {}"
  1014       (x2, K2) \<in> s \<Longrightarrow> (x1, K1) \<noteq> (x2, K2) \<Longrightarrow> interior K1 \<inter> interior K2 = {}"
  1015   using assms unfolding tagged_partial_division_of_def by blast+
  1015   using assms unfolding tagged_partial_division_of_def by blast+
  1016 
  1016 
  1017 definition%important tagged_division_of (infixr "tagged'_division'_of" 40)
  1017 definition\<^marker>\<open>tag important\<close> tagged_division_of (infixr "tagged'_division'_of" 40)
  1018   where "s tagged_division_of i \<longleftrightarrow> s tagged_partial_division_of i \<and> (\<Union>{K. \<exists>x. (x,K) \<in> s} = i)"
  1018   where "s tagged_division_of i \<longleftrightarrow> s tagged_partial_division_of i \<and> (\<Union>{K. \<exists>x. (x,K) \<in> s} = i)"
  1019 
  1019 
  1020 lemma tagged_division_of_finite: "s tagged_division_of i \<Longrightarrow> finite s"
  1020 lemma tagged_division_of_finite: "s tagged_division_of i \<Longrightarrow> finite s"
  1021   unfolding tagged_division_of_def tagged_partial_division_of_def by auto
  1021   unfolding tagged_division_of_def tagged_partial_division_of_def by auto
  1022 
  1022 
  1290 
  1290 
  1291 text \<open>This auxiliary structure is used to sum up over the elements of a division. Main theorem is
  1291 text \<open>This auxiliary structure is used to sum up over the elements of a division. Main theorem is
  1292   \<open>operative_division\<close>. Instances for the monoid are \<^typ>\<open>'a option\<close>, \<^typ>\<open>real\<close>, and
  1292   \<open>operative_division\<close>. Instances for the monoid are \<^typ>\<open>'a option\<close>, \<^typ>\<open>real\<close>, and
  1293   \<^typ>\<open>bool\<close>.\<close>
  1293   \<^typ>\<open>bool\<close>.\<close>
  1294 
  1294 
  1295 paragraph%important \<open>Using additivity of lifted function to encode definedness.\<close>
  1295 paragraph\<^marker>\<open>tag important\<close> \<open>Using additivity of lifted function to encode definedness.\<close>
  1296 text \<open>%whitespace\<close>
  1296 text \<open>%whitespace\<close>
  1297 definition%important lift_option :: "('a \<Rightarrow> 'b \<Rightarrow> 'c) \<Rightarrow> 'a option \<Rightarrow> 'b option \<Rightarrow> 'c option"
  1297 definition\<^marker>\<open>tag important\<close> lift_option :: "('a \<Rightarrow> 'b \<Rightarrow> 'c) \<Rightarrow> 'a option \<Rightarrow> 'b option \<Rightarrow> 'c option"
  1298 where
  1298 where
  1299   "lift_option f a' b' = Option.bind a' (\<lambda>a. Option.bind b' (\<lambda>b. Some (f a b)))"
  1299   "lift_option f a' b' = Option.bind a' (\<lambda>a. Option.bind b' (\<lambda>b. Some (f a b)))"
  1300 
  1300 
  1301 lemma lift_option_simps[simp]:
  1301 lemma lift_option_simps[simp]:
  1302   "lift_option f (Some a) (Some b) = Some (f a b)"
  1302   "lift_option f (Some a) (Some b) = Some (f a b)"
  1303   "lift_option f None b' = None"
  1303   "lift_option f None b' = None"
  1304   "lift_option f a' None = None"
  1304   "lift_option f a' None = None"
  1305   by (auto simp: lift_option_def)
  1305   by (auto simp: lift_option_def)
  1306 
  1306 
  1307 lemma%important comm_monoid_lift_option:
  1307 lemma\<^marker>\<open>tag important\<close> comm_monoid_lift_option:
  1308   assumes "comm_monoid f z"
  1308   assumes "comm_monoid f z"
  1309   shows "comm_monoid (lift_option f) (Some z)"
  1309   shows "comm_monoid (lift_option f) (Some z)"
  1310 proof -
  1310 proof -
  1311   from assms interpret comm_monoid f z .
  1311   from assms interpret comm_monoid f z .
  1312   show ?thesis
  1312   show ?thesis
  1333   by (meson zero_less_one)
  1333   by (meson zero_less_one)
  1334 
  1334 
  1335 
  1335 
  1336 paragraph \<open>Division points\<close>
  1336 paragraph \<open>Division points\<close>
  1337 text \<open>%whitespace\<close>
  1337 text \<open>%whitespace\<close>
  1338 definition%important "division_points (k::('a::euclidean_space) set) d =
  1338 definition\<^marker>\<open>tag important\<close> "division_points (k::('a::euclidean_space) set) d =
  1339    {(j,x). j \<in> Basis \<and> (interval_lowerbound k)\<bullet>j < x \<and> x < (interval_upperbound k)\<bullet>j \<and>
  1339    {(j,x). j \<in> Basis \<and> (interval_lowerbound k)\<bullet>j < x \<and> x < (interval_upperbound k)\<bullet>j \<and>
  1340      (\<exists>i\<in>d. (interval_lowerbound i)\<bullet>j = x \<or> (interval_upperbound i)\<bullet>j = x)}"
  1340      (\<exists>i\<in>d. (interval_lowerbound i)\<bullet>j = x \<or> (interval_upperbound i)\<bullet>j = x)}"
  1341 
  1341 
  1342 lemma division_points_finite:
  1342 lemma division_points_finite:
  1343   fixes i :: "'a::euclidean_space set"
  1343   fixes i :: "'a::euclidean_space set"
  1856 qed
  1856 qed
  1857 
  1857 
  1858 
  1858 
  1859 subsection \<open>Fine-ness of a partition w.r.t. a gauge\<close>
  1859 subsection \<open>Fine-ness of a partition w.r.t. a gauge\<close>
  1860 
  1860 
  1861 definition%important fine  (infixr "fine" 46)
  1861 definition\<^marker>\<open>tag important\<close> fine  (infixr "fine" 46)
  1862   where "d fine s \<longleftrightarrow> (\<forall>(x,k) \<in> s. k \<subseteq> d x)"
  1862   where "d fine s \<longleftrightarrow> (\<forall>(x,k) \<in> s. k \<subseteq> d x)"
  1863 
  1863 
  1864 lemma fineI:
  1864 lemma fineI:
  1865   assumes "\<And>x k. (x, k) \<in> s \<Longrightarrow> k \<subseteq> d x"
  1865   assumes "\<And>x k. (x, k) \<in> s \<Longrightarrow> k \<subseteq> d x"
  1866   shows "d fine s"
  1866   shows "d fine s"
  1905     using assms(1) assms(3) assms(4) pfn(1) tagged_division_Union apply force
  1905     using assms(1) assms(3) assms(4) pfn(1) tagged_division_Union apply force
  1906     by (metis (mono_tags, lifting) fine_Union imageE pfn(2))
  1906     by (metis (mono_tags, lifting) fine_Union imageE pfn(2))
  1907 qed
  1907 qed
  1908 (* FIXME structure here, do not have one lemma in each subsection *)
  1908 (* FIXME structure here, do not have one lemma in each subsection *)
  1909 
  1909 
  1910 subsection%unimportant \<open>The set we're concerned with must be closed\<close>
  1910 subsection\<^marker>\<open>tag unimportant\<close> \<open>The set we're concerned with must be closed\<close>
  1911 
  1911 
  1912 lemma division_of_closed:
  1912 lemma division_of_closed:
  1913   fixes i :: "'n::euclidean_space set"
  1913   fixes i :: "'n::euclidean_space set"
  1914   shows "s division_of i \<Longrightarrow> closed i"
  1914   shows "s division_of i \<Longrightarrow> closed i"
  1915   unfolding division_of_def by fastforce
  1915   unfolding division_of_def by fastforce
  2299   with p obtain q where q: "q tagged_division_of \<Union>{k. \<exists>x. (x, k) \<in> p}" "d fine q" "\<forall>(x, k)\<in>p. k \<subseteq> d x \<longrightarrow> (x, k) \<in> q"
  2299   with p obtain q where q: "q tagged_division_of \<Union>{k. \<exists>x. (x, k) \<in> p}" "d fine q" "\<forall>(x, k)\<in>p. k \<subseteq> d x \<longrightarrow> (x, k) \<in> q"
  2300     by (meson \<open>gauge d\<close>)
  2300     by (meson \<open>gauge d\<close>)
  2301   with ptag that show ?thesis by auto
  2301   with ptag that show ?thesis by auto
  2302 qed
  2302 qed
  2303 
  2303 
  2304 subsubsection%important \<open>Covering lemma\<close>
  2304 subsubsection\<^marker>\<open>tag important\<close> \<open>Covering lemma\<close>
  2305 
  2305 
  2306 text\<open> Some technical lemmas used in the approximation results that follow. Proof of the covering
  2306 text\<open> Some technical lemmas used in the approximation results that follow. Proof of the covering
  2307   lemma is an obvious multidimensional generalization of Lemma 3, p65 of Swartz's
  2307   lemma is an obvious multidimensional generalization of Lemma 3, p65 of Swartz's
  2308   "Introduction to Gauge Integrals". \<close>
  2308   "Introduction to Gauge Integrals". \<close>
  2309 
  2309 
  2573 
  2573 
  2574 subsection \<open>Division filter\<close>
  2574 subsection \<open>Division filter\<close>
  2575 
  2575 
  2576 text \<open>Divisions over all gauges towards finer divisions.\<close>
  2576 text \<open>Divisions over all gauges towards finer divisions.\<close>
  2577 
  2577 
  2578 definition%important division_filter :: "'a::euclidean_space set \<Rightarrow> ('a \<times> 'a set) set filter"
  2578 definition\<^marker>\<open>tag important\<close> division_filter :: "'a::euclidean_space set \<Rightarrow> ('a \<times> 'a set) set filter"
  2579   where "division_filter s = (INF g\<in>{g. gauge g}. principal {p. p tagged_division_of s \<and> g fine p})"
  2579   where "division_filter s = (INF g\<in>{g. gauge g}. principal {p. p tagged_division_of s \<and> g fine p})"
  2580 
  2580 
  2581 proposition eventually_division_filter:
  2581 proposition eventually_division_filter:
  2582   "(\<forall>\<^sub>F p in division_filter s. P p) \<longleftrightarrow>
  2582   "(\<forall>\<^sub>F p in division_filter s. P p) \<longleftrightarrow>
  2583     (\<exists>g. gauge g \<and> (\<forall>p. p tagged_division_of s \<and> g fine p \<longrightarrow> P p))"
  2583     (\<exists>g. gauge g \<and> (\<forall>p. p tagged_division_of s \<and> g fine p \<longrightarrow> P p))"