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