8 imports Path_Connected Ordered_Euclidean_Space "HOL-Computational_Algebra.Primes" |
8 imports Path_Connected Ordered_Euclidean_Space "HOL-Computational_Algebra.Primes" |
9 begin |
9 begin |
10 |
10 |
11 subsection%important \<open>The Brouwer reduction theorem\<close> |
11 subsection%important \<open>The Brouwer reduction theorem\<close> |
12 |
12 |
13 theorem%important Brouwer_reduction_theorem_gen: |
13 theorem Brouwer_reduction_theorem_gen: |
14 fixes S :: "'a::euclidean_space set" |
14 fixes S :: "'a::euclidean_space set" |
15 assumes "closed S" "\<phi> S" |
15 assumes "closed S" "\<phi> S" |
16 and \<phi>: "\<And>F. \<lbrakk>\<And>n. closed(F n); \<And>n. \<phi>(F n); \<And>n. F(Suc n) \<subseteq> F n\<rbrakk> \<Longrightarrow> \<phi>(\<Inter>range F)" |
16 and \<phi>: "\<And>F. \<lbrakk>\<And>n. closed(F n); \<And>n. \<phi>(F n); \<And>n. F(Suc n) \<subseteq> F n\<rbrakk> \<Longrightarrow> \<phi>(\<Inter>range F)" |
17 obtains T where "T \<subseteq> S" "closed T" "\<phi> T" "\<And>U. \<lbrakk>U \<subseteq> S; closed U; \<phi> U\<rbrakk> \<Longrightarrow> \<not> (U \<subset> T)" |
17 obtains T where "T \<subseteq> S" "closed T" "\<phi> T" "\<And>U. \<lbrakk>U \<subseteq> S; closed U; \<phi> U\<rbrakk> \<Longrightarrow> \<not> (U \<subset> T)" |
18 proof%unimportant - |
18 proof - |
19 obtain B :: "nat \<Rightarrow> 'a set" |
19 obtain B :: "nat \<Rightarrow> 'a set" |
20 where "inj B" "\<And>n. open(B n)" and open_cov: "\<And>S. open S \<Longrightarrow> \<exists>K. S = \<Union>(B ` K)" |
20 where "inj B" "\<And>n. open(B n)" and open_cov: "\<And>S. open S \<Longrightarrow> \<exists>K. S = \<Union>(B ` K)" |
21 by (metis Setcompr_eq_image that univ_second_countable_sequence) |
21 by (metis Setcompr_eq_image that univ_second_countable_sequence) |
22 define A where "A \<equiv> rec_nat S (\<lambda>n a. if \<exists>U. U \<subseteq> a \<and> closed U \<and> \<phi> U \<and> U \<inter> (B n) = {} |
22 define A where "A \<equiv> rec_nat S (\<lambda>n a. if \<exists>U. U \<subseteq> a \<and> closed U \<and> \<phi> U \<and> U \<inter> (B n) = {} |
23 then SOME U. U \<subseteq> a \<and> closed U \<and> \<phi> U \<and> U \<inter> (B n) = {} |
23 then SOME U. U \<subseteq> a \<and> closed U \<and> \<phi> U \<and> U \<inter> (B n) = {} |
76 by (meson Inter_iff psubsetE rangeI subsetI) |
76 by (meson Inter_iff psubsetE rangeI subsetI) |
77 qed |
77 qed |
78 qed |
78 qed |
79 qed |
79 qed |
80 |
80 |
81 corollary%important Brouwer_reduction_theorem: |
81 corollary Brouwer_reduction_theorem: |
82 fixes S :: "'a::euclidean_space set" |
82 fixes S :: "'a::euclidean_space set" |
83 assumes "compact S" "\<phi> S" "S \<noteq> {}" |
83 assumes "compact S" "\<phi> S" "S \<noteq> {}" |
84 and \<phi>: "\<And>F. \<lbrakk>\<And>n. compact(F n); \<And>n. F n \<noteq> {}; \<And>n. \<phi>(F n); \<And>n. F(Suc n) \<subseteq> F n\<rbrakk> \<Longrightarrow> \<phi>(\<Inter>range F)" |
84 and \<phi>: "\<And>F. \<lbrakk>\<And>n. compact(F n); \<And>n. F n \<noteq> {}; \<And>n. \<phi>(F n); \<And>n. F(Suc n) \<subseteq> F n\<rbrakk> \<Longrightarrow> \<phi>(\<Inter>range F)" |
85 obtains T where "T \<subseteq> S" "compact T" "T \<noteq> {}" "\<phi> T" |
85 obtains T where "T \<subseteq> S" "compact T" "T \<noteq> {}" "\<phi> T" |
86 "\<And>U. \<lbrakk>U \<subseteq> S; closed U; U \<noteq> {}; \<phi> U\<rbrakk> \<Longrightarrow> \<not> (U \<subset> T)" |
86 "\<And>U. \<lbrakk>U \<subseteq> S; closed U; U \<noteq> {}; \<phi> U\<rbrakk> \<Longrightarrow> \<not> (U \<subset> T)" |
87 proof%unimportant (rule Brouwer_reduction_theorem_gen [of S "\<lambda>T. T \<noteq> {} \<and> T \<subseteq> S \<and> \<phi> T"]) |
87 proof (rule Brouwer_reduction_theorem_gen [of S "\<lambda>T. T \<noteq> {} \<and> T \<subseteq> S \<and> \<phi> T"]) |
88 fix F |
88 fix F |
89 assume cloF: "\<And>n. closed (F n)" |
89 assume cloF: "\<And>n. closed (F n)" |
90 and F: "\<And>n. F n \<noteq> {} \<and> F n \<subseteq> S \<and> \<phi> (F n)" and Fsub: "\<And>n. F (Suc n) \<subseteq> F n" |
90 and F: "\<And>n. F n \<noteq> {} \<and> F n \<subseteq> S \<and> \<phi> (F n)" and Fsub: "\<And>n. F (Suc n) \<subseteq> F n" |
91 show "\<Inter>(F ` UNIV) \<noteq> {} \<and> \<Inter>(F ` UNIV) \<subseteq> S \<and> \<phi> (\<Inter>(F ` UNIV))" |
91 show "\<Inter>(F ` UNIV) \<noteq> {} \<and> \<Inter>(F ` UNIV) \<subseteq> S \<and> \<phi> (\<Inter>(F ` UNIV))" |
92 proof (intro conjI) |
92 proof (intro conjI) |
104 show "S \<noteq> {} \<and> S \<subseteq> S \<and> \<phi> S" |
104 show "S \<noteq> {} \<and> S \<subseteq> S \<and> \<phi> S" |
105 by (simp add: assms) |
105 by (simp add: assms) |
106 qed (meson assms compact_imp_closed seq_compact_closed_subset seq_compact_eq_compact)+ |
106 qed (meson assms compact_imp_closed seq_compact_closed_subset seq_compact_eq_compact)+ |
107 |
107 |
108 |
108 |
109 subsection%important\<open>Arcwise Connections\<close>(*FIX ME this subsection is empty(?) *) |
109 subsection%unimportant\<open>Arcwise Connections\<close>(*FIX ME this subsection is empty(?) *) |
110 |
110 |
111 subsection%important\<open>Density of points with dyadic rational coordinates\<close> |
111 subsection%important\<open>Density of points with dyadic rational coordinates\<close> |
112 |
112 |
113 proposition%important closure_dyadic_rationals: |
113 proposition closure_dyadic_rationals: |
114 "closure (\<Union>k. \<Union>f \<in> Basis \<rightarrow> \<int>. |
114 "closure (\<Union>k. \<Union>f \<in> Basis \<rightarrow> \<int>. |
115 { \<Sum>i :: 'a :: euclidean_space \<in> Basis. (f i / 2^k) *\<^sub>R i }) = UNIV" |
115 { \<Sum>i :: 'a :: euclidean_space \<in> Basis. (f i / 2^k) *\<^sub>R i }) = UNIV" |
116 proof%unimportant - |
116 proof - |
117 have "x \<in> closure (\<Union>k. \<Union>f \<in> Basis \<rightarrow> \<int>. {\<Sum>i \<in> Basis. (f i / 2^k) *\<^sub>R i})" for x::'a |
117 have "x \<in> closure (\<Union>k. \<Union>f \<in> Basis \<rightarrow> \<int>. {\<Sum>i \<in> Basis. (f i / 2^k) *\<^sub>R i})" for x::'a |
118 proof (clarsimp simp: closure_approachable) |
118 proof (clarsimp simp: closure_approachable) |
119 fix e::real |
119 fix e::real |
120 assume "e > 0" |
120 assume "e > 0" |
121 then obtain k where k: "(1/2)^k < e/DIM('a)" |
121 then obtain k where k: "(1/2)^k < e/DIM('a)" |
165 qed |
165 qed |
166 show ?thesis |
166 show ?thesis |
167 using closure_dyadic_rationals closure_mono [OF *] by blast |
167 using closure_dyadic_rationals closure_mono [OF *] by blast |
168 qed |
168 qed |
169 |
169 |
170 lemma%unimportant closure_dyadic_rationals_in_convex_set: |
170 lemma closure_dyadic_rationals_in_convex_set: |
171 "\<lbrakk>convex S; interior S \<noteq> {}\<rbrakk> |
171 "\<lbrakk>convex S; interior S \<noteq> {}\<rbrakk> |
172 \<Longrightarrow> closure(S \<inter> |
172 \<Longrightarrow> closure(S \<inter> |
173 (\<Union>k. \<Union>f \<in> Basis \<rightarrow> \<int>. |
173 (\<Union>k. \<Union>f \<in> Basis \<rightarrow> \<int>. |
174 { \<Sum>i :: 'a :: euclidean_space \<in> Basis. (f i / 2^k) *\<^sub>R i })) = |
174 { \<Sum>i :: 'a :: euclidean_space \<in> Basis. (f i / 2^k) *\<^sub>R i })) = |
175 closure S" |
175 closure S" |
176 by (simp add: closure_dyadic_rationals closure_convex_Int_superset) |
176 by (simp add: closure_dyadic_rationals closure_convex_Int_superset) |
177 |
177 |
178 lemma%unimportant closure_rationals_in_convex_set: |
178 lemma closure_rationals_in_convex_set: |
179 "\<lbrakk>convex S; interior S \<noteq> {}\<rbrakk> |
179 "\<lbrakk>convex S; interior S \<noteq> {}\<rbrakk> |
180 \<Longrightarrow> closure(S \<inter> (\<Union>f \<in> Basis \<rightarrow> \<rat>. { \<Sum>i :: 'a :: euclidean_space \<in> Basis. f i *\<^sub>R i })) = |
180 \<Longrightarrow> closure(S \<inter> (\<Union>f \<in> Basis \<rightarrow> \<rat>. { \<Sum>i :: 'a :: euclidean_space \<in> Basis. f i *\<^sub>R i })) = |
181 closure S" |
181 closure S" |
182 by (simp add: closure_rational_coordinates closure_convex_Int_superset) |
182 by (simp add: closure_rational_coordinates closure_convex_Int_superset) |
183 |
183 |
184 |
184 |
185 text\<open> Every path between distinct points contains an arc, and hence |
185 text\<open> Every path between distinct points contains an arc, and hence |
186 path connection is equivalent to arcwise connection for distinct points. |
186 path connection is equivalent to arcwise connection for distinct points. |
187 The proof is based on Whyburn's "Topological Analysis".\<close> |
187 The proof is based on Whyburn's "Topological Analysis".\<close> |
188 |
188 |
189 lemma%important closure_dyadic_rationals_in_convex_set_pos_1: |
189 lemma closure_dyadic_rationals_in_convex_set_pos_1: |
190 fixes S :: "real set" |
190 fixes S :: "real set" |
191 assumes "convex S" and intnz: "interior S \<noteq> {}" and pos: "\<And>x. x \<in> S \<Longrightarrow> 0 \<le> x" |
191 assumes "convex S" and intnz: "interior S \<noteq> {}" and pos: "\<And>x. x \<in> S \<Longrightarrow> 0 \<le> x" |
192 shows "closure(S \<inter> (\<Union>k m. {of_nat m / 2^k})) = closure S" |
192 shows "closure(S \<inter> (\<Union>k m. {of_nat m / 2^k})) = closure S" |
193 proof%unimportant - |
193 proof - |
194 have "\<exists>m. f 1/2^k = real m / 2^k" if "(f 1) / 2^k \<in> S" "f 1 \<in> \<int>" for k and f :: "real \<Rightarrow> real" |
194 have "\<exists>m. f 1/2^k = real m / 2^k" if "(f 1) / 2^k \<in> S" "f 1 \<in> \<int>" for k and f :: "real \<Rightarrow> real" |
195 using that by (force simp: Ints_def zero_le_divide_iff power_le_zero_eq dest: pos zero_le_imp_eq_int) |
195 using that by (force simp: Ints_def zero_le_divide_iff power_le_zero_eq dest: pos zero_le_imp_eq_int) |
196 then have "S \<inter> (\<Union>k m. {real m / 2^k}) = S \<inter> |
196 then have "S \<inter> (\<Union>k m. {real m / 2^k}) = S \<inter> |
197 (\<Union>k. \<Union>f\<in>Basis \<rightarrow> \<int>. {\<Sum>i\<in>Basis. (f i / 2^k) *\<^sub>R i})" |
197 (\<Union>k. \<Union>f\<in>Basis \<rightarrow> \<int>. {\<Sum>i\<in>Basis. (f i / 2^k) *\<^sub>R i})" |
198 by force |
198 by force |
199 then show ?thesis |
199 then show ?thesis |
200 using closure_dyadic_rationals_in_convex_set [OF \<open>convex S\<close> intnz] by simp |
200 using closure_dyadic_rationals_in_convex_set [OF \<open>convex S\<close> intnz] by simp |
201 qed |
201 qed |
202 |
202 |
203 |
203 |
204 definition%important dyadics :: "'a::field_char_0 set" where "dyadics \<equiv> \<Union>k m. {of_nat m / 2^k}" |
204 definition%unimportant dyadics :: "'a::field_char_0 set" where "dyadics \<equiv> \<Union>k m. {of_nat m / 2^k}" |
205 |
205 |
206 lemma%unimportant real_in_dyadics [simp]: "real m \<in> dyadics" |
206 lemma real_in_dyadics [simp]: "real m \<in> dyadics" |
207 apply (simp add: dyadics_def) |
207 apply (simp add: dyadics_def) |
208 by (metis divide_numeral_1 numeral_One power_0) |
208 by (metis divide_numeral_1 numeral_One power_0) |
209 |
209 |
210 lemma%unimportant nat_neq_4k1: "of_nat m \<noteq> (4 * of_nat k + 1) / (2 * 2^n :: 'a::field_char_0)" |
210 lemma nat_neq_4k1: "of_nat m \<noteq> (4 * of_nat k + 1) / (2 * 2^n :: 'a::field_char_0)" |
211 proof |
211 proof |
212 assume "of_nat m = (4 * of_nat k + 1) / (2 * 2^n :: 'a)" |
212 assume "of_nat m = (4 * of_nat k + 1) / (2 * 2^n :: 'a)" |
213 then have "of_nat (m * (2 * 2^n)) = (of_nat (Suc (4 * k)) :: 'a)" |
213 then have "of_nat (m * (2 * 2^n)) = (of_nat (Suc (4 * k)) :: 'a)" |
214 by (simp add: divide_simps) |
214 by (simp add: divide_simps) |
215 then have "m * (2 * 2^n) = Suc (4 * k)" |
215 then have "m * (2 * 2^n) = Suc (4 * k)" |
342 apply (metis of_nat_Suc of_nat_mult of_nat_numeral) |
342 apply (metis of_nat_Suc of_nat_mult of_nat_numeral) |
343 by (metis of_nat_add of_nat_mult of_nat_numeral) |
343 by (metis of_nat_add of_nat_mult of_nat_numeral) |
344 qed |
344 qed |
345 |
345 |
346 |
346 |
347 function (domintros) dyad_rec :: "[nat \<Rightarrow> 'a, 'a\<Rightarrow>'a, 'a\<Rightarrow>'a, real] \<Rightarrow> 'a" where |
347 function%unimportant (domintros) dyad_rec :: "[nat \<Rightarrow> 'a, 'a\<Rightarrow>'a, 'a\<Rightarrow>'a, real] \<Rightarrow> 'a" where |
348 "dyad_rec b l r (real m) = b m" |
348 "dyad_rec b l r (real m) = b m" |
349 | "dyad_rec b l r ((4 * real m + 1) / 2 ^ (Suc n)) = l (dyad_rec b l r ((2*m + 1) / 2^n))" |
349 | "dyad_rec b l r ((4 * real m + 1) / 2 ^ (Suc n)) = l (dyad_rec b l r ((2*m + 1) / 2^n))" |
350 | "dyad_rec b l r ((4 * real m + 3) / 2 ^ (Suc n)) = r (dyad_rec b l r ((2*m + 1) / 2^n))" |
350 | "dyad_rec b l r ((4 * real m + 3) / 2 ^ (Suc n)) = r (dyad_rec b l r ((2*m + 1) / 2^n))" |
351 | "x \<notin> dyadics \<Longrightarrow> dyad_rec b l r x = undefined" |
351 | "x \<notin> dyadics \<Longrightarrow> dyad_rec b l r x = undefined" |
352 using iff_4k [of _ 1] iff_4k [of _ 3] |
352 using iff_4k [of _ 1] iff_4k [of _ 3] |
353 apply (simp_all add: nat_neq_4k1 nat_neq_4k3 neq_4k1_k43, atomize_elim) |
353 apply (simp_all add: nat_neq_4k1 nat_neq_4k3 neq_4k1_k43, atomize_elim) |
354 apply (fastforce simp add: dyadics_iff Nats_def field_simps)+ |
354 apply (fastforce simp add: dyadics_iff Nats_def field_simps)+ |
355 done |
355 done |
356 |
356 |
357 lemma%unimportant dyadics_levels: "dyadics = (\<Union>K. \<Union>k<K. \<Union> m. {of_nat m / 2^k})" |
357 lemma dyadics_levels: "dyadics = (\<Union>K. \<Union>k<K. \<Union> m. {of_nat m / 2^k})" |
358 unfolding dyadics_def by auto |
358 unfolding dyadics_def by auto |
359 |
359 |
360 lemma%important dyad_rec_level_termination: |
360 lemma dyad_rec_level_termination: |
361 assumes "k < K" |
361 assumes "k < K" |
362 shows "dyad_rec_dom(b, l, r, real m / 2^k)" |
362 shows "dyad_rec_dom(b, l, r, real m / 2^k)" |
363 using assms |
363 using assms |
364 proof%unimportant (induction K arbitrary: k m) |
364 proof (induction K arbitrary: k m) |
365 case 0 |
365 case 0 |
366 then show ?case by auto |
366 then show ?case by auto |
367 next |
367 next |
368 case (Suc K) |
368 case (Suc K) |
369 then consider "k = K" | "k < K" |
369 then consider "k = K" | "k < K" |
424 using Suc.IH by blast |
424 using Suc.IH by blast |
425 qed |
425 qed |
426 qed |
426 qed |
427 |
427 |
428 |
428 |
429 lemma%unimportant dyad_rec_termination: "x \<in> dyadics \<Longrightarrow> dyad_rec_dom(b,l,r,x)" |
429 lemma dyad_rec_termination: "x \<in> dyadics \<Longrightarrow> dyad_rec_dom(b,l,r,x)" |
430 by (auto simp: dyadics_levels intro: dyad_rec_level_termination) |
430 by (auto simp: dyadics_levels intro: dyad_rec_level_termination) |
431 |
431 |
432 lemma%unimportant dyad_rec_of_nat [simp]: "dyad_rec b l r (real m) = b m" |
432 lemma dyad_rec_of_nat [simp]: "dyad_rec b l r (real m) = b m" |
433 by (simp add: dyad_rec.psimps dyad_rec_termination) |
433 by (simp add: dyad_rec.psimps dyad_rec_termination) |
434 |
434 |
435 lemma%unimportant dyad_rec_41 [simp]: "dyad_rec b l r ((4 * real m + 1) / 2 ^ (Suc n)) = l (dyad_rec b l r ((2*m + 1) / 2^n))" |
435 lemma dyad_rec_41 [simp]: "dyad_rec b l r ((4 * real m + 1) / 2 ^ (Suc n)) = l (dyad_rec b l r ((2*m + 1) / 2^n))" |
436 apply (rule dyad_rec.psimps) |
436 apply (rule dyad_rec.psimps) |
437 by (metis dyad_rec_level_termination lessI add.commute of_nat_Suc of_nat_mult of_nat_numeral) |
437 by (metis dyad_rec_level_termination lessI add.commute of_nat_Suc of_nat_mult of_nat_numeral) |
438 |
438 |
439 |
439 |
440 lemma%unimportant dyad_rec_43 [simp]: "dyad_rec b l r ((4 * real m + 3) / 2 ^ (Suc n)) = r (dyad_rec b l r ((2*m + 1) / 2^n))" |
440 lemma dyad_rec_43 [simp]: "dyad_rec b l r ((4 * real m + 3) / 2 ^ (Suc n)) = r (dyad_rec b l r ((2*m + 1) / 2^n))" |
441 apply (rule dyad_rec.psimps) |
441 apply (rule dyad_rec.psimps) |
442 by (metis dyad_rec_level_termination lessI of_nat_add of_nat_mult of_nat_numeral) |
442 by (metis dyad_rec_level_termination lessI of_nat_add of_nat_mult of_nat_numeral) |
443 |
443 |
444 lemma%unimportant dyad_rec_41_times2: |
444 lemma dyad_rec_41_times2: |
445 assumes "n > 0" |
445 assumes "n > 0" |
446 shows "dyad_rec b l r (2 * ((4 * real m + 1) / 2^Suc n)) = l (dyad_rec b l r (2 * (2 * real m + 1) / 2^n))" |
446 shows "dyad_rec b l r (2 * ((4 * real m + 1) / 2^Suc n)) = l (dyad_rec b l r (2 * (2 * real m + 1) / 2^n))" |
447 proof - |
447 proof - |
448 obtain n' where n': "n = Suc n'" |
448 obtain n' where n': "n = Suc n'" |
449 using assms not0_implies_Suc by blast |
449 using assms not0_implies_Suc by blast |
477 also have "... = r (dyad_rec b l r (2 * (2 * real m + 1) / 2^n))" |
477 also have "... = r (dyad_rec b l r (2 * (2 * real m + 1) / 2^n))" |
478 by (simp add: n') |
478 by (simp add: n') |
479 finally show ?thesis . |
479 finally show ?thesis . |
480 qed |
480 qed |
481 |
481 |
482 definition%important dyad_rec2 |
482 definition%unimportant dyad_rec2 |
483 where "dyad_rec2 u v lc rc x = |
483 where "dyad_rec2 u v lc rc x = |
484 dyad_rec (\<lambda>z. (u,v)) (\<lambda>(a,b). (a, lc a b (midpoint a b))) (\<lambda>(a,b). (rc a b (midpoint a b), b)) (2*x)" |
484 dyad_rec (\<lambda>z. (u,v)) (\<lambda>(a,b). (a, lc a b (midpoint a b))) (\<lambda>(a,b). (rc a b (midpoint a b), b)) (2*x)" |
485 |
485 |
486 abbreviation leftrec where "leftrec u v lc rc x \<equiv> fst (dyad_rec2 u v lc rc x)" |
486 abbreviation%unimportant leftrec where "leftrec u v lc rc x \<equiv> fst (dyad_rec2 u v lc rc x)" |
487 abbreviation rightrec where "rightrec u v lc rc x \<equiv> snd (dyad_rec2 u v lc rc x)" |
487 abbreviation%unimportant rightrec where "rightrec u v lc rc x \<equiv> snd (dyad_rec2 u v lc rc x)" |
488 |
488 |
489 lemma%unimportant leftrec_base: "leftrec u v lc rc (real m / 2) = u" |
489 lemma leftrec_base: "leftrec u v lc rc (real m / 2) = u" |
490 by (simp add: dyad_rec2_def) |
490 by (simp add: dyad_rec2_def) |
491 |
491 |
492 lemma%unimportant leftrec_41: "n > 0 \<Longrightarrow> leftrec u v lc rc ((4 * real m + 1) / 2 ^ (Suc n)) = leftrec u v lc rc ((2 * real m + 1) / 2^n)" |
492 lemma leftrec_41: "n > 0 \<Longrightarrow> leftrec u v lc rc ((4 * real m + 1) / 2 ^ (Suc n)) = leftrec u v lc rc ((2 * real m + 1) / 2^n)" |
493 apply (simp only: dyad_rec2_def dyad_rec_41_times2) |
493 apply (simp only: dyad_rec2_def dyad_rec_41_times2) |
494 apply (simp add: case_prod_beta) |
494 apply (simp add: case_prod_beta) |
495 done |
495 done |
496 |
496 |
497 lemma%unimportant leftrec_43: "n > 0 \<Longrightarrow> |
497 lemma leftrec_43: "n > 0 \<Longrightarrow> |
498 leftrec u v lc rc ((4 * real m + 3) / 2 ^ (Suc n)) = |
498 leftrec u v lc rc ((4 * real m + 3) / 2 ^ (Suc n)) = |
499 rc (leftrec u v lc rc ((2 * real m + 1) / 2^n)) (rightrec u v lc rc ((2 * real m + 1) / 2^n)) |
499 rc (leftrec u v lc rc ((2 * real m + 1) / 2^n)) (rightrec u v lc rc ((2 * real m + 1) / 2^n)) |
500 (midpoint (leftrec u v lc rc ((2 * real m + 1) / 2^n)) (rightrec u v lc rc ((2 * real m + 1) / 2^n)))" |
500 (midpoint (leftrec u v lc rc ((2 * real m + 1) / 2^n)) (rightrec u v lc rc ((2 * real m + 1) / 2^n)))" |
501 apply (simp only: dyad_rec2_def dyad_rec_43_times2) |
501 apply (simp only: dyad_rec2_def dyad_rec_43_times2) |
502 apply (simp add: case_prod_beta) |
502 apply (simp add: case_prod_beta) |
503 done |
503 done |
504 |
504 |
505 lemma%unimportant rightrec_base: "rightrec u v lc rc (real m / 2) = v" |
505 lemma rightrec_base: "rightrec u v lc rc (real m / 2) = v" |
506 by (simp add: dyad_rec2_def) |
506 by (simp add: dyad_rec2_def) |
507 |
507 |
508 lemma%unimportant rightrec_41: "n > 0 \<Longrightarrow> |
508 lemma rightrec_41: "n > 0 \<Longrightarrow> |
509 rightrec u v lc rc ((4 * real m + 1) / 2 ^ (Suc n)) = |
509 rightrec u v lc rc ((4 * real m + 1) / 2 ^ (Suc n)) = |
510 lc (leftrec u v lc rc ((2 * real m + 1) / 2^n)) (rightrec u v lc rc ((2 * real m + 1) / 2^n)) |
510 lc (leftrec u v lc rc ((2 * real m + 1) / 2^n)) (rightrec u v lc rc ((2 * real m + 1) / 2^n)) |
511 (midpoint (leftrec u v lc rc ((2 * real m + 1) / 2^n)) (rightrec u v lc rc ((2 * real m + 1) / 2^n)))" |
511 (midpoint (leftrec u v lc rc ((2 * real m + 1) / 2^n)) (rightrec u v lc rc ((2 * real m + 1) / 2^n)))" |
512 apply (simp only: dyad_rec2_def dyad_rec_41_times2) |
512 apply (simp only: dyad_rec2_def dyad_rec_41_times2) |
513 apply (simp add: case_prod_beta) |
513 apply (simp add: case_prod_beta) |
514 done |
514 done |
515 |
515 |
516 lemma%unimportant rightrec_43: "n > 0 \<Longrightarrow> rightrec u v lc rc ((4 * real m + 3) / 2 ^ (Suc n)) = rightrec u v lc rc ((2 * real m + 1) / 2^n)" |
516 lemma rightrec_43: "n > 0 \<Longrightarrow> rightrec u v lc rc ((4 * real m + 3) / 2 ^ (Suc n)) = rightrec u v lc rc ((2 * real m + 1) / 2^n)" |
517 apply (simp only: dyad_rec2_def dyad_rec_43_times2) |
517 apply (simp only: dyad_rec2_def dyad_rec_43_times2) |
518 apply (simp add: case_prod_beta) |
518 apply (simp add: case_prod_beta) |
519 done |
519 done |
520 |
520 |
521 lemma%unimportant dyadics_in_open_unit_interval: |
521 lemma dyadics_in_open_unit_interval: |
522 "{0<..<1} \<inter> (\<Union>k m. {real m / 2^k}) = (\<Union>k. \<Union>m \<in> {0<..<2^k}. {real m / 2^k})" |
522 "{0<..<1} \<inter> (\<Union>k m. {real m / 2^k}) = (\<Union>k. \<Union>m \<in> {0<..<2^k}. {real m / 2^k})" |
523 by (auto simp: divide_simps) |
523 by (auto simp: divide_simps) |
524 |
524 |
525 |
525 |
526 |
526 |
527 theorem%important homeomorphic_monotone_image_interval: |
527 theorem homeomorphic_monotone_image_interval: |
528 fixes f :: "real \<Rightarrow> 'a::{real_normed_vector,complete_space}" |
528 fixes f :: "real \<Rightarrow> 'a::{real_normed_vector,complete_space}" |
529 assumes cont_f: "continuous_on {0..1} f" |
529 assumes cont_f: "continuous_on {0..1} f" |
530 and conn: "\<And>y. connected ({0..1} \<inter> f -` {y})" |
530 and conn: "\<And>y. connected ({0..1} \<inter> f -` {y})" |
531 and f_1not0: "f 1 \<noteq> f 0" |
531 and f_1not0: "f 1 \<noteq> f 0" |
532 shows "(f ` {0..1}) homeomorphic {0..1::real}" |
532 shows "(f ` {0..1}) homeomorphic {0..1::real}" |
533 proof%unimportant - |
533 proof - |
534 have "\<exists>c d. a \<le> c \<and> c \<le> m \<and> m \<le> d \<and> d \<le> b \<and> |
534 have "\<exists>c d. a \<le> c \<and> c \<le> m \<and> m \<le> d \<and> d \<le> b \<and> |
535 (\<forall>x \<in> {c..d}. f x = f m) \<and> |
535 (\<forall>x \<in> {c..d}. f x = f m) \<and> |
536 (\<forall>x \<in> {a..<c}. (f x \<noteq> f m)) \<and> |
536 (\<forall>x \<in> {a..<c}. (f x \<noteq> f m)) \<and> |
537 (\<forall>x \<in> {d<..b}. (f x \<noteq> f m)) \<and> |
537 (\<forall>x \<in> {d<..b}. (f x \<noteq> f m)) \<and> |
538 (\<forall>x \<in> {a..<c}. \<forall>y \<in> {d<..b}. f x \<noteq> f y)" |
538 (\<forall>x \<in> {a..<c}. \<forall>y \<in> {d<..b}. f x \<noteq> f y)" |
1661 then show ?thesis |
1661 then show ?thesis |
1662 using homeomorphic_sym by blast |
1662 using homeomorphic_sym by blast |
1663 qed |
1663 qed |
1664 |
1664 |
1665 |
1665 |
1666 theorem%important path_contains_arc: |
1666 theorem path_contains_arc: |
1667 fixes p :: "real \<Rightarrow> 'a::{complete_space,real_normed_vector}" |
1667 fixes p :: "real \<Rightarrow> 'a::{complete_space,real_normed_vector}" |
1668 assumes "path p" and a: "pathstart p = a" and b: "pathfinish p = b" and "a \<noteq> b" |
1668 assumes "path p" and a: "pathstart p = a" and b: "pathfinish p = b" and "a \<noteq> b" |
1669 obtains q where "arc q" "path_image q \<subseteq> path_image p" "pathstart q = a" "pathfinish q = b" |
1669 obtains q where "arc q" "path_image q \<subseteq> path_image p" "pathstart q = a" "pathfinish q = b" |
1670 proof%unimportant - |
1670 proof - |
1671 have ucont_p: "uniformly_continuous_on {0..1} p" |
1671 have ucont_p: "uniformly_continuous_on {0..1} p" |
1672 using \<open>path p\<close> unfolding path_def |
1672 using \<open>path p\<close> unfolding path_def |
1673 by (metis compact_Icc compact_uniformly_continuous) |
1673 by (metis compact_Icc compact_uniformly_continuous) |
1674 define \<phi> where "\<phi> \<equiv> \<lambda>S. S \<subseteq> {0..1} \<and> 0 \<in> S \<and> 1 \<in> S \<and> |
1674 define \<phi> where "\<phi> \<equiv> \<lambda>S. S \<subseteq> {0..1} \<and> 0 \<in> S \<and> 1 \<in> S \<and> |
1675 (\<forall>x \<in> S. \<forall>y \<in> S. open_segment x y \<inter> S = {} \<longrightarrow> p x = p y)" |
1675 (\<forall>x \<in> S. \<forall>y \<in> S. open_segment x y \<inter> S = {} \<longrightarrow> p x = p y)" |
1958 using \<open>arc g\<close> \<open>a = g u\<close> \<open>b = g v\<close> \<open>u \<in> {0..1}\<close> \<open>v \<in> {0..1}\<close> arc_subpath_arc \<open>a \<noteq> b\<close> by blast |
1958 using \<open>arc g\<close> \<open>a = g u\<close> \<open>b = g v\<close> \<open>u \<in> {0..1}\<close> \<open>v \<in> {0..1}\<close> arc_subpath_arc \<open>a \<noteq> b\<close> by blast |
1959 qed |
1959 qed |
1960 qed |
1960 qed |
1961 |
1961 |
1962 |
1962 |
1963 corollary%important path_connected_arcwise: |
1963 corollary path_connected_arcwise: |
1964 fixes S :: "'a::{complete_space,real_normed_vector} set" |
1964 fixes S :: "'a::{complete_space,real_normed_vector} set" |
1965 shows "path_connected S \<longleftrightarrow> |
1965 shows "path_connected S \<longleftrightarrow> |
1966 (\<forall>x \<in> S. \<forall>y \<in> S. x \<noteq> y \<longrightarrow> (\<exists>g. arc g \<and> path_image g \<subseteq> S \<and> pathstart g = x \<and> pathfinish g = y))" |
1966 (\<forall>x \<in> S. \<forall>y \<in> S. x \<noteq> y \<longrightarrow> (\<exists>g. arc g \<and> path_image g \<subseteq> S \<and> pathstart g = x \<and> pathfinish g = y))" |
1967 (is "?lhs = ?rhs") |
1967 (is "?lhs = ?rhs") |
1968 proof%unimportant (intro iffI impI ballI) |
1968 proof (intro iffI impI ballI) |
1969 fix x y |
1969 fix x y |
1970 assume "path_connected S" "x \<in> S" "y \<in> S" "x \<noteq> y" |
1970 assume "path_connected S" "x \<in> S" "y \<in> S" "x \<noteq> y" |
1971 then obtain p where p: "path p" "path_image p \<subseteq> S" "pathstart p = x" "pathfinish p = y" |
1971 then obtain p where p: "path p" "path_image p \<subseteq> S" "pathstart p = x" "pathfinish p = y" |
1972 by (force simp: path_connected_def) |
1972 by (force simp: path_connected_def) |
1973 then show "\<exists>g. arc g \<and> path_image g \<subseteq> S \<and> pathstart g = x \<and> pathfinish g = y" |
1973 then show "\<exists>g. arc g \<and> path_image g \<subseteq> S \<and> pathstart g = x \<and> pathfinish g = y" |
1989 qed |
1989 qed |
1990 qed |
1990 qed |
1991 qed |
1991 qed |
1992 |
1992 |
1993 |
1993 |
1994 corollary%important arc_connected_trans: |
1994 corollary arc_connected_trans: |
1995 fixes g :: "real \<Rightarrow> 'a::{complete_space,real_normed_vector}" |
1995 fixes g :: "real \<Rightarrow> 'a::{complete_space,real_normed_vector}" |
1996 assumes "arc g" "arc h" "pathfinish g = pathstart h" "pathstart g \<noteq> pathfinish h" |
1996 assumes "arc g" "arc h" "pathfinish g = pathstart h" "pathstart g \<noteq> pathfinish h" |
1997 obtains i where "arc i" "path_image i \<subseteq> path_image g \<union> path_image h" |
1997 obtains i where "arc i" "path_image i \<subseteq> path_image g \<union> path_image h" |
1998 "pathstart i = pathstart g" "pathfinish i = pathfinish h" |
1998 "pathstart i = pathstart g" "pathfinish i = pathfinish h" |
1999 by%unimportant (metis (no_types, hide_lams) arc_imp_path assms path_contains_arc path_image_join path_join pathfinish_join pathstart_join) |
1999 by (metis (no_types, hide_lams) arc_imp_path assms path_contains_arc path_image_join path_join pathfinish_join pathstart_join) |
2000 |
2000 |
2001 |
2001 |
2002 |
2002 |
2003 |
2003 |
2004 subsection%important\<open>Accessibility of frontier points\<close> |
2004 subsection%important\<open>Accessibility of frontier points\<close> |
2005 |
2005 |
2006 lemma%important dense_accessible_frontier_points: |
2006 lemma dense_accessible_frontier_points: |
2007 fixes S :: "'a::{complete_space,real_normed_vector} set" |
2007 fixes S :: "'a::{complete_space,real_normed_vector} set" |
2008 assumes "open S" and opeSV: "openin (subtopology euclidean (frontier S)) V" and "V \<noteq> {}" |
2008 assumes "open S" and opeSV: "openin (subtopology euclidean (frontier S)) V" and "V \<noteq> {}" |
2009 obtains g where "arc g" "g ` {0..<1} \<subseteq> S" "pathstart g \<in> S" "pathfinish g \<in> V" |
2009 obtains g where "arc g" "g ` {0..<1} \<subseteq> S" "pathstart g \<in> S" "pathfinish g \<in> V" |
2010 proof%unimportant - |
2010 proof - |
2011 obtain z where "z \<in> V" |
2011 obtain z where "z \<in> V" |
2012 using \<open>V \<noteq> {}\<close> by auto |
2012 using \<open>V \<noteq> {}\<close> by auto |
2013 then obtain r where "r > 0" and r: "ball z r \<inter> frontier S \<subseteq> V" |
2013 then obtain r where "r > 0" and r: "ball z r \<inter> frontier S \<subseteq> V" |
2014 by (metis openin_contains_ball opeSV) |
2014 by (metis openin_contains_ball opeSV) |
2015 then have "z \<in> frontier S" |
2015 then have "z \<in> frontier S" |
2096 by auto |
2096 by auto |
2097 qed |
2097 qed |
2098 qed |
2098 qed |
2099 |
2099 |
2100 |
2100 |
2101 lemma%important dense_accessible_frontier_points_connected: |
2101 lemma dense_accessible_frontier_points_connected: |
2102 fixes S :: "'a::{complete_space,real_normed_vector} set" |
2102 fixes S :: "'a::{complete_space,real_normed_vector} set" |
2103 assumes "open S" "connected S" "x \<in> S" "V \<noteq> {}" |
2103 assumes "open S" "connected S" "x \<in> S" "V \<noteq> {}" |
2104 and ope: "openin (subtopology euclidean (frontier S)) V" |
2104 and ope: "openin (subtopology euclidean (frontier S)) V" |
2105 obtains g where "arc g" "g ` {0..<1} \<subseteq> S" "pathstart g = x" "pathfinish g \<in> V" |
2105 obtains g where "arc g" "g ` {0..<1} \<subseteq> S" "pathstart g = x" "pathfinish g \<in> V" |
2106 proof%unimportant - |
2106 proof - |
2107 have "V \<subseteq> frontier S" |
2107 have "V \<subseteq> frontier S" |
2108 using ope openin_imp_subset by blast |
2108 using ope openin_imp_subset by blast |
2109 with \<open>open S\<close> \<open>x \<in> S\<close> have "x \<notin> V" |
2109 with \<open>open S\<close> \<open>x \<in> S\<close> have "x \<notin> V" |
2110 using interior_open by (auto simp: frontier_def) |
2110 using interior_open by (auto simp: frontier_def) |
2111 obtain g where "arc g" and g: "g ` {0..<1} \<subseteq> S" "pathstart g \<in> S" "pathfinish g \<in> V" |
2111 obtain g where "arc g" and g: "g ` {0..<1} \<subseteq> S" "pathstart g \<in> S" "pathfinish g \<in> V" |
2131 then show thesis |
2131 then show thesis |
2132 apply (rule that [OF \<open>arc h\<close>]) |
2132 apply (rule that [OF \<open>arc h\<close>]) |
2133 using h \<open>pathfinish g \<in> V\<close> by auto |
2133 using h \<open>pathfinish g \<in> V\<close> by auto |
2134 qed |
2134 qed |
2135 |
2135 |
2136 lemma%important dense_access_fp_aux: |
2136 lemma dense_access_fp_aux: |
2137 fixes S :: "'a::{complete_space,real_normed_vector} set" |
2137 fixes S :: "'a::{complete_space,real_normed_vector} set" |
2138 assumes S: "open S" "connected S" |
2138 assumes S: "open S" "connected S" |
2139 and opeSU: "openin (subtopology euclidean (frontier S)) U" |
2139 and opeSU: "openin (subtopology euclidean (frontier S)) U" |
2140 and opeSV: "openin (subtopology euclidean (frontier S)) V" |
2140 and opeSV: "openin (subtopology euclidean (frontier S)) V" |
2141 and "V \<noteq> {}" "\<not> U \<subseteq> V" |
2141 and "V \<noteq> {}" "\<not> U \<subseteq> V" |
2142 obtains g where "arc g" "pathstart g \<in> U" "pathfinish g \<in> V" "g ` {0<..<1} \<subseteq> S" |
2142 obtains g where "arc g" "pathstart g \<in> U" "pathfinish g \<in> V" "g ` {0<..<1} \<subseteq> S" |
2143 proof%unimportant - |
2143 proof - |
2144 have "S \<noteq> {}" |
2144 have "S \<noteq> {}" |
2145 using opeSV \<open>V \<noteq> {}\<close> by (metis frontier_empty openin_subtopology_empty) |
2145 using opeSV \<open>V \<noteq> {}\<close> by (metis frontier_empty openin_subtopology_empty) |
2146 then obtain x where "x \<in> S" by auto |
2146 then obtain x where "x \<in> S" by auto |
2147 obtain g where "arc g" and g: "g ` {0..<1} \<subseteq> S" "pathstart g = x" "pathfinish g \<in> V" |
2147 obtain g where "arc g" and g: "g ` {0..<1} \<subseteq> S" "pathstart g = x" "pathfinish g \<in> V" |
2148 using dense_accessible_frontier_points_connected [OF S \<open>x \<in> S\<close> \<open>V \<noteq> {}\<close> opeSV] by blast |
2148 using dense_accessible_frontier_points_connected [OF S \<open>x \<in> S\<close> \<open>V \<noteq> {}\<close> opeSV] by blast |
2178 using \<open>arc h\<close> \<open>arc \<gamma>\<close> |
2178 using \<open>arc h\<close> \<open>arc \<gamma>\<close> |
2179 by (metis arc_imp_simple_path path_image_def pathfinish_def pathstart_def simple_path_endless) |
2179 by (metis arc_imp_simple_path path_image_def pathfinish_def pathstart_def simple_path_endless) |
2180 qed |
2180 qed |
2181 qed |
2181 qed |
2182 |
2182 |
2183 lemma%important dense_accessible_frontier_point_pairs: |
2183 lemma dense_accessible_frontier_point_pairs: |
2184 fixes S :: "'a::{complete_space,real_normed_vector} set" |
2184 fixes S :: "'a::{complete_space,real_normed_vector} set" |
2185 assumes S: "open S" "connected S" |
2185 assumes S: "open S" "connected S" |
2186 and opeSU: "openin (subtopology euclidean (frontier S)) U" |
2186 and opeSU: "openin (subtopology euclidean (frontier S)) U" |
2187 and opeSV: "openin (subtopology euclidean (frontier S)) V" |
2187 and opeSV: "openin (subtopology euclidean (frontier S)) V" |
2188 and "U \<noteq> {}" "V \<noteq> {}" "U \<noteq> V" |
2188 and "U \<noteq> {}" "V \<noteq> {}" "U \<noteq> V" |
2189 obtains g where "arc g" "pathstart g \<in> U" "pathfinish g \<in> V" "g ` {0<..<1} \<subseteq> S" |
2189 obtains g where "arc g" "pathstart g \<in> U" "pathfinish g \<in> V" "g ` {0<..<1} \<subseteq> S" |
2190 proof%unimportant - |
2190 proof - |
2191 consider "\<not> U \<subseteq> V" | "\<not> V \<subseteq> U" |
2191 consider "\<not> U \<subseteq> V" | "\<not> V \<subseteq> U" |
2192 using \<open>U \<noteq> V\<close> by blast |
2192 using \<open>U \<noteq> V\<close> by blast |
2193 then show ?thesis |
2193 then show ?thesis |
2194 proof cases |
2194 proof cases |
2195 case 1 then show ?thesis |
2195 case 1 then show ?thesis |