1377 by force |
1377 by force |
1378 qed |
1378 qed |
1379 |
1379 |
1380 lemma division_points_psubset: |
1380 lemma division_points_psubset: |
1381 fixes a :: "'a::euclidean_space" |
1381 fixes a :: "'a::euclidean_space" |
1382 assumes "d division_of (cbox a b)" |
1382 assumes d: "d division_of (cbox a b)" |
1383 and "\<forall>i\<in>Basis. a\<bullet>i < b\<bullet>i" "a\<bullet>k < c" "c < b\<bullet>k" |
1383 and altb: "\<forall>i\<in>Basis. a\<bullet>i < b\<bullet>i" "a\<bullet>k < c" "c < b\<bullet>k" |
1384 and "l \<in> d" |
1384 and "l \<in> d" |
1385 and disj: "interval_lowerbound l\<bullet>k = c \<or> interval_upperbound l\<bullet>k = c" |
1385 and disj: "interval_lowerbound l\<bullet>k = c \<or> interval_upperbound l\<bullet>k = c" |
1386 and k: "k \<in> Basis" |
1386 and k: "k \<in> Basis" |
1387 shows "division_points (cbox a b \<inter> {x. x\<bullet>k \<le> c}) {l \<inter> {x. x\<bullet>k \<le> c} | l. l\<in>d \<and> l \<inter> {x. x\<bullet>k \<le> c} \<noteq> {}} \<subset> |
1387 shows "division_points (cbox a b \<inter> {x. x\<bullet>k \<le> c}) {l \<inter> {x. x\<bullet>k \<le> c} | l. l\<in>d \<and> l \<inter> {x. x\<bullet>k \<le> c} \<noteq> {}} \<subset> |
1388 division_points (cbox a b) d" (is "?D1 \<subset> ?D") |
1388 division_points (cbox a b) d" (is "?D1 \<subset> ?D") |
1389 and "division_points (cbox a b \<inter> {x. x\<bullet>k \<ge> c}) {l \<inter> {x. x\<bullet>k \<ge> c} | l. l\<in>d \<and> l \<inter> {x. x\<bullet>k \<ge> c} \<noteq> {}} \<subset> |
1389 and "division_points (cbox a b \<inter> {x. x\<bullet>k \<ge> c}) {l \<inter> {x. x\<bullet>k \<ge> c} | l. l\<in>d \<and> l \<inter> {x. x\<bullet>k \<ge> c} \<noteq> {}} \<subset> |
1390 division_points (cbox a b) d" (is "?D2 \<subset> ?D") |
1390 division_points (cbox a b) d" (is "?D2 \<subset> ?D") |
1391 proof - |
1391 proof - |
1392 have ab: "\<forall>i\<in>Basis. a\<bullet>i \<le> b\<bullet>i" |
1392 have ab: "\<forall>i\<in>Basis. a\<bullet>i \<le> b\<bullet>i" |
1393 using assms(2) by (auto intro!:less_imp_le) |
1393 using altb by (auto intro!:less_imp_le) |
1394 guess u v using division_ofD(4)[OF assms(1,5)] by (elim exE) note l=this |
1394 obtain u v where l: "l = cbox u v" |
|
1395 using d \<open>l \<in> d\<close> by blast |
1395 have uv: "\<forall>i\<in>Basis. u\<bullet>i \<le> v\<bullet>i" "\<forall>i\<in>Basis. a\<bullet>i \<le> u\<bullet>i \<and> v\<bullet>i \<le> b\<bullet>i" |
1396 have uv: "\<forall>i\<in>Basis. u\<bullet>i \<le> v\<bullet>i" "\<forall>i\<in>Basis. a\<bullet>i \<le> u\<bullet>i \<and> v\<bullet>i \<le> b\<bullet>i" |
1396 using division_ofD(2,2,3)[OF assms(1,5)] unfolding l box_ne_empty |
1397 apply (metis assms(5) box_ne_empty(1) cbox_division_memE d l) |
1397 using subset_box(1) |
1398 by (metis assms(5) box_ne_empty(1) cbox_division_memE d l subset_box(1)) |
1398 apply auto |
|
1399 apply blast+ |
|
1400 done |
|
1401 have *: "interval_upperbound (cbox a b \<inter> {x. x \<bullet> k \<le> interval_upperbound l \<bullet> k}) \<bullet> k = interval_upperbound l \<bullet> k" |
1399 have *: "interval_upperbound (cbox a b \<inter> {x. x \<bullet> k \<le> interval_upperbound l \<bullet> k}) \<bullet> k = interval_upperbound l \<bullet> k" |
1402 "interval_upperbound (cbox a b \<inter> {x. x \<bullet> k \<le> interval_lowerbound l \<bullet> k}) \<bullet> k = interval_lowerbound l \<bullet> k" |
1400 "interval_upperbound (cbox a b \<inter> {x. x \<bullet> k \<le> interval_lowerbound l \<bullet> k}) \<bullet> k = interval_lowerbound l \<bullet> k" |
1403 unfolding l interval_split[OF k] interval_bounds[OF uv(1)] |
1401 unfolding l interval_split[OF k] interval_bounds[OF uv(1)] |
1404 using uv[rule_format, of k] ab k |
1402 using uv[rule_format, of k] ab k |
1405 by auto |
1403 by auto |
2373 unfolding fine_def |
2371 unfolding fine_def |
2374 apply auto |
2372 apply auto |
2375 done |
2373 done |
2376 next |
2374 next |
2377 case (insert xk p) |
2375 case (insert xk p) |
2378 guess x k using surj_pair[of xk] by (elim exE) note xk=this |
2376 obtain x k where xk: "xk = (x, k)" |
2379 note tagged_partial_division_subset[OF insert(4) subset_insertI] |
2377 using surj_pair[of xk] by metis |
2380 from insert(3)[OF this insert(5)] |
|
2381 obtain q1 where q1: "q1 tagged_division_of \<Union>{k. \<exists>x. (x, k) \<in> p}" |
2378 obtain q1 where q1: "q1 tagged_division_of \<Union>{k. \<exists>x. (x, k) \<in> p}" |
2382 and "d fine q1" |
2379 and "d fine q1" |
2383 and q1I: "\<And>x k. \<lbrakk>(x, k)\<in>p; k \<subseteq> d x\<rbrakk> \<Longrightarrow> (x, k) \<in> q1" |
2380 and q1I: "\<And>x k. \<lbrakk>(x, k)\<in>p; k \<subseteq> d x\<rbrakk> \<Longrightarrow> (x, k) \<in> q1" |
2384 by (force simp add: ) |
2381 using case_prodD tagged_partial_division_subset[OF insert(4) subset_insertI] |
|
2382 by (metis (mono_tags, lifting) insert.hyps(3) insert.prems(2)) |
2385 have *: "\<Union>{l. \<exists>y. (y,l) \<in> insert xk p} = k \<union> \<Union>{l. \<exists>y. (y,l) \<in> p}" |
2383 have *: "\<Union>{l. \<exists>y. (y,l) \<in> insert xk p} = k \<union> \<Union>{l. \<exists>y. (y,l) \<in> p}" |
2386 unfolding xk by auto |
2384 unfolding xk by auto |
2387 note p = tagged_partial_division_ofD[OF insert(4)] |
2385 note p = tagged_partial_division_ofD[OF insert(4)] |
2388 from p(4)[unfolded xk, OF insertI1] guess u v by (elim exE) note uv=this |
2386 obtain u v where uv: "k = cbox u v" |
2389 |
2387 using p(4)[unfolded xk, OF insertI1] by blast |
2390 have "finite {k. \<exists>x. (x, k) \<in> p}" |
2388 have "finite {k. \<exists>x. (x, k) \<in> p}" |
2391 apply (rule finite_subset[of _ "snd ` p"]) |
2389 apply (rule finite_subset[of _ "snd ` p"]) |
2392 using p |
2390 using image_iff apply fastforce |
2393 apply safe |
2391 using insert.hyps(1) by blast |
2394 apply (metis image_iff snd_conv) |
|
2395 apply auto |
|
2396 done |
|
2397 then have int: "interior (cbox u v) \<inter> interior (\<Union>{k. \<exists>x. (x, k) \<in> p}) = {}" |
2392 then have int: "interior (cbox u v) \<inter> interior (\<Union>{k. \<exists>x. (x, k) \<in> p}) = {}" |
2398 apply (rule Int_interior_Union_intervals) |
2393 proof (rule Int_interior_Union_intervals) |
2399 apply (rule open_interior) |
2394 show "open (interior (cbox u v))" |
2400 unfolding mem_Collect_eq |
2395 by auto |
2401 apply (erule_tac[!] exE) |
2396 show "\<And>T. T \<in> {k. \<exists>x. (x, k) \<in> p} \<Longrightarrow> \<exists>a b. T = cbox a b" |
2402 apply (drule p(4)[OF insertI2]) |
2397 using p(4) by auto |
2403 apply assumption |
2398 show "\<And>T. T \<in> {k. \<exists>x. (x, k) \<in> p} \<Longrightarrow> interior (cbox u v) \<inter> interior T = {}" |
2404 apply (rule p(5)) |
2399 by clarify (metis insert.hyps(2) insert_iff interior_cbox p(5) uv xk) |
2405 unfolding uv xk |
2400 qed |
2406 apply (rule insertI1) |
|
2407 apply (rule insertI2) |
|
2408 apply assumption |
|
2409 using insert(2) |
|
2410 unfolding uv xk |
|
2411 apply auto |
|
2412 done |
|
2413 show ?case |
2401 show ?case |
2414 proof (cases "cbox u v \<subseteq> d x") |
2402 proof (cases "cbox u v \<subseteq> d x") |
2415 case True |
2403 case True |
2416 then show ?thesis |
2404 have "{(x, cbox u v)} tagged_division_of cbox u v" |
|
2405 by (simp add: p(2) uv xk tagged_division_of_self) |
|
2406 then have "{(x, cbox u v)} \<union> q1 tagged_division_of \<Union>{k. \<exists>x. (x, k) \<in> insert xk p}" |
|
2407 unfolding * uv by (metis (no_types, lifting) int q1 tagged_division_union) |
|
2408 with True show ?thesis |
2417 apply (rule_tac x="{(x,cbox u v)} \<union> q1" in exI) |
2409 apply (rule_tac x="{(x,cbox u v)} \<union> q1" in exI) |
2418 apply rule |
2410 using \<open>d fine q1\<close> fine_def q1I uv xk apply fastforce |
2419 unfolding * uv |
|
2420 apply (rule tagged_division_union) |
|
2421 apply (rule tagged_division_of_self) |
|
2422 apply (rule p[unfolded xk uv] insertI1)+ |
|
2423 apply (rule q1) |
|
2424 apply (rule int) |
|
2425 apply rule |
|
2426 apply (rule fine_Un) |
|
2427 apply (subst fine_def) |
|
2428 apply (auto simp add: \<open>d fine q1\<close> q1I uv xk) |
|
2429 done |
2411 done |
2430 next |
2412 next |
2431 case False |
2413 case False |
2432 from fine_division_exists[OF assms(2), of u v] guess q2 . note q2=this |
2414 obtain q2 where q2: "q2 tagged_division_of cbox u v" "d fine q2" |
|
2415 using fine_division_exists[OF assms(2)] by blast |
2433 show ?thesis |
2416 show ?thesis |
2434 apply (rule_tac x="q2 \<union> q1" in exI) |
2417 apply (rule_tac x="q2 \<union> q1" in exI) |
2435 apply rule |
2418 apply (intro conjI) |
2436 unfolding * uv |
2419 unfolding * uv |
2437 apply (rule tagged_division_union q2 q1 int fine_Un)+ |
2420 apply (rule tagged_division_union q2 q1 int fine_Un)+ |
2438 apply (auto intro: q1 q2 fine_Un \<open>d fine q1\<close> simp add: False q1I uv xk) |
2421 apply (auto intro: q1 q2 fine_Un \<open>d fine q1\<close> simp add: False q1I uv xk) |
2439 done |
2422 done |
2440 qed |
2423 qed |