diff -r 09a4954e7c07 -r 3170b5eb9f5a src/HOL/Multivariate_Analysis/Path_Connected.thy --- a/src/HOL/Multivariate_Analysis/Path_Connected.thy Sat Sep 14 22:50:15 2013 +0200 +++ b/src/HOL/Multivariate_Analysis/Path_Connected.thy Sat Sep 14 23:52:36 2013 +0200 @@ -11,7 +11,7 @@ subsection {* Paths. *} definition path :: "(real \ 'a::topological_space) \ bool" - where "path g \ continuous_on {0 .. 1} g" + where "path g \ continuous_on {0..1} g" definition pathstart :: "(real \ 'a::topological_space) \ 'a" where "pathstart g = g 0" @@ -22,10 +22,10 @@ definition path_image :: "(real \ 'a::topological_space) \ 'a set" where "path_image g = g ` {0 .. 1}" -definition reversepath :: "(real \ 'a::topological_space) \ (real \ 'a)" +definition reversepath :: "(real \ 'a::topological_space) \ real \ 'a" where "reversepath g = (\x. g(1 - x))" -definition joinpaths :: "(real \ 'a::topological_space) \ (real \ 'a) \ (real \ 'a)" +definition joinpaths :: "(real \ 'a::topological_space) \ (real \ 'a) \ real \ 'a" (infixr "+++" 75) where "g1 +++ g2 = (\x. if x \ 1/2 then g1 (2 * x) else g2 (2 * x - 1))" @@ -40,62 +40,77 @@ subsection {* Some lemmas about these concepts. *} lemma injective_imp_simple_path: "injective_path g \ simple_path g" - unfolding injective_path_def simple_path_def by auto + unfolding injective_path_def simple_path_def + by auto lemma path_image_nonempty: "path_image g \ {}" - unfolding path_image_def image_is_empty interval_eq_empty by auto - -lemma pathstart_in_path_image[intro]: "(pathstart g) \ path_image g" - unfolding pathstart_def path_image_def by auto + unfolding path_image_def image_is_empty interval_eq_empty + by auto -lemma pathfinish_in_path_image[intro]: "(pathfinish g) \ path_image g" - unfolding pathfinish_def path_image_def by auto +lemma pathstart_in_path_image[intro]: "pathstart g \ path_image g" + unfolding pathstart_def path_image_def + by auto -lemma connected_path_image[intro]: "path g \ connected(path_image g)" +lemma pathfinish_in_path_image[intro]: "pathfinish g \ path_image g" + unfolding pathfinish_def path_image_def + by auto + +lemma connected_path_image[intro]: "path g \ connected (path_image g)" unfolding path_def path_image_def apply (erule connected_continuous_image) apply (rule convex_connected, rule convex_real_interval) done -lemma compact_path_image[intro]: "path g \ compact(path_image g)" +lemma compact_path_image[intro]: "path g \ compact (path_image g)" unfolding path_def path_image_def - by (erule compact_continuous_image, rule compact_interval) + apply (erule compact_continuous_image) + apply (rule compact_interval) + done -lemma reversepath_reversepath[simp]: "reversepath(reversepath g) = g" - unfolding reversepath_def by auto +lemma reversepath_reversepath[simp]: "reversepath (reversepath g) = g" + unfolding reversepath_def + by auto -lemma pathstart_reversepath[simp]: "pathstart(reversepath g) = pathfinish g" - unfolding pathstart_def reversepath_def pathfinish_def by auto +lemma pathstart_reversepath[simp]: "pathstart (reversepath g) = pathfinish g" + unfolding pathstart_def reversepath_def pathfinish_def + by auto -lemma pathfinish_reversepath[simp]: "pathfinish(reversepath g) = pathstart g" - unfolding pathstart_def reversepath_def pathfinish_def by auto +lemma pathfinish_reversepath[simp]: "pathfinish (reversepath g) = pathstart g" + unfolding pathstart_def reversepath_def pathfinish_def + by auto lemma pathstart_join[simp]: "pathstart (g1 +++ g2) = pathstart g1" - unfolding pathstart_def joinpaths_def pathfinish_def by auto + unfolding pathstart_def joinpaths_def pathfinish_def + by auto lemma pathfinish_join[simp]: "pathfinish (g1 +++ g2) = pathfinish g2" - unfolding pathstart_def joinpaths_def pathfinish_def by auto + unfolding pathstart_def joinpaths_def pathfinish_def + by auto -lemma path_image_reversepath[simp]: "path_image(reversepath g) = path_image g" +lemma path_image_reversepath[simp]: "path_image (reversepath g) = path_image g" proof - - have *: "\g. path_image(reversepath g) \ path_image g" + have *: "\g. path_image (reversepath g) \ path_image g" unfolding path_image_def subset_eq reversepath_def Ball_def image_iff - apply(rule,rule,erule bexE) - apply(rule_tac x="1 - xa" in bexI) + apply rule + apply rule + apply (erule bexE) + apply (rule_tac x="1 - xa" in bexI) apply auto done show ?thesis using *[of g] *[of "reversepath g"] - unfolding reversepath_reversepath by auto + unfolding reversepath_reversepath + by auto qed -lemma path_reversepath[simp]: "path (reversepath g) \ path g" +lemma path_reversepath [simp]: "path (reversepath g) \ path g" proof - have *: "\g. path g \ path (reversepath g)" unfolding path_def reversepath_def apply (rule continuous_on_compose[unfolded o_def, of _ "\x. 1 - x"]) apply (intro continuous_on_intros) - apply (rule continuous_on_subset[of "{0..1}"], assumption) + apply (rule continuous_on_subset[of "{0..1}"]) + apply assumption apply auto done show ?thesis @@ -116,43 +131,59 @@ have g1: "continuous_on {0..1} g1 \ continuous_on {0..1} ((g1 +++ g2) \ (\x. x / 2))" by (intro continuous_on_cong refl) (auto simp: joinpaths_def) have g2: "continuous_on {0..1} g2 \ continuous_on {0..1} ((g1 +++ g2) \ (\x. x / 2 + 1/2))" - using assms by (intro continuous_on_cong refl) (auto simp: joinpaths_def pathfinish_def pathstart_def) - show "continuous_on {0..1} g1" "continuous_on {0..1} g2" + using assms + by (intro continuous_on_cong refl) (auto simp: joinpaths_def pathfinish_def pathstart_def) + show "continuous_on {0..1} g1" and "continuous_on {0..1} g2" unfolding g1 g2 by (auto intro!: continuous_on_intros continuous_on_subset[OF cont] simp del: o_apply) next assume g1g2: "continuous_on {0..1} g1" "continuous_on {0..1} g2" have 01: "{0 .. 1} = {0..1/2} \ {1/2 .. 1::real}" by auto - { fix x :: real assume "0 \ x" "x \ 1" then have "x \ (\x. x * 2) ` {0..1 / 2}" - by (intro image_eqI[where x="x/2"]) auto } + { + fix x :: real + assume "0 \ x" and "x \ 1" + then have "x \ (\x. x * 2) ` {0..1 / 2}" + by (intro image_eqI[where x="x/2"]) auto + } note 1 = this - { fix x :: real assume "0 \ x" "x \ 1" then have "x \ (\x. x * 2 - 1) ` {1 / 2..1}" - by (intro image_eqI[where x="x/2 + 1/2"]) auto } + { + fix x :: real + assume "0 \ x" and "x \ 1" + then have "x \ (\x. x * 2 - 1) ` {1 / 2..1}" + by (intro image_eqI[where x="x/2 + 1/2"]) auto + } note 2 = this show "continuous_on {0..1} (g1 +++ g2)" - using assms unfolding joinpaths_def 01 - by (intro continuous_on_cases closed_atLeastAtMost g1g2[THEN continuous_on_compose2] continuous_on_intros) - (auto simp: field_simps pathfinish_def pathstart_def intro!: 1 2) + using assms + unfolding joinpaths_def 01 + apply (intro continuous_on_cases closed_atLeastAtMost g1g2[THEN continuous_on_compose2] continuous_on_intros) + apply (auto simp: field_simps pathfinish_def pathstart_def intro!: 1 2) + done qed -lemma path_image_join_subset: "path_image(g1 +++ g2) \ (path_image g1 \ path_image g2)" - unfolding path_image_def joinpaths_def by auto +lemma path_image_join_subset: "path_image (g1 +++ g2) \ path_image g1 \ path_image g2" + unfolding path_image_def joinpaths_def + by auto lemma subset_path_image_join: - assumes "path_image g1 \ s" "path_image g2 \ s" - shows "path_image(g1 +++ g2) \ s" - using path_image_join_subset[of g1 g2] and assms by auto + assumes "path_image g1 \ s" + and "path_image g2 \ s" + shows "path_image (g1 +++ g2) \ s" + using path_image_join_subset[of g1 g2] and assms + by auto lemma path_image_join: assumes "pathfinish g1 = pathstart g2" - shows "path_image(g1 +++ g2) = (path_image g1) \ (path_image g2)" - apply (rule, rule path_image_join_subset, rule) + shows "path_image (g1 +++ g2) = path_image g1 \ path_image g2" + apply rule + apply (rule path_image_join_subset) + apply rule unfolding Un_iff proof (erule disjE) fix x assume "x \ path_image g1" - then obtain y where y: "y\{0..1}" "x = g1 y" + then obtain y where y: "y \ {0..1}" "x = g1 y" unfolding path_image_def image_iff by auto then show "x \ path_image (g1 +++ g2)" unfolding joinpaths_def path_image_def image_iff @@ -162,20 +193,22 @@ next fix x assume "x \ path_image g2" - then obtain y where y: "y\{0..1}" "x = g2 y" + then obtain y where y: "y \ {0..1}" "x = g2 y" unfolding path_image_def image_iff by auto then show "x \ path_image (g1 +++ g2)" unfolding joinpaths_def path_image_def image_iff - apply(rule_tac x="(1/2) *\<^sub>R (y + 1)" in bexI) + apply (rule_tac x="(1/2) *\<^sub>R (y + 1)" in bexI) using assms(1)[unfolded pathfinish_def pathstart_def] - apply (auto simp add: add_divide_distrib) + apply (auto simp add: add_divide_distrib) done qed lemma not_in_path_image_join: - assumes "x \ path_image g1" "x \ path_image g2" - shows "x \ path_image(g1 +++ g2)" - using assms and path_image_join_subset[of g1 g2] by auto + assumes "x \ path_image g1" + and "x \ path_image g2" + shows "x \ path_image (g1 +++ g2)" + using assms and path_image_join_subset[of g1 g2] + by auto lemma simple_path_reversepath: assumes "simple_path g" @@ -184,82 +217,111 @@ unfolding simple_path_def reversepath_def apply - apply (rule ballI)+ - apply (erule_tac x="1-x" in ballE, erule_tac x="1-y" in ballE) + apply (erule_tac x="1-x" in ballE) + apply (erule_tac x="1-y" in ballE) apply auto done lemma simple_path_join_loop: - assumes "injective_path g1" "injective_path g2" "pathfinish g2 = pathstart g1" - "(path_image g1 \ path_image g2) \ {pathstart g1,pathstart g2}" - shows "simple_path(g1 +++ g2)" + assumes "injective_path g1" + and "injective_path g2" + and "pathfinish g2 = pathstart g1" + and "path_image g1 \ path_image g2 \ {pathstart g1, pathstart g2}" + shows "simple_path (g1 +++ g2)" unfolding simple_path_def -proof ((rule ballI)+, rule impI) +proof (intro ballI impI) let ?g = "g1 +++ g2" note inj = assms(1,2)[unfolded injective_path_def, rule_format] fix x y :: real assume xy: "x \ {0..1}" "y \ {0..1}" "?g x = ?g y" show "x = y \ x = 0 \ y = 1 \ x = 1 \ y = 0" - proof (case_tac "x \ 1/2", case_tac[!] "y \ 1/2", unfold not_le) + proof (cases "x \ 1/2", case_tac[!] "y \ 1/2", unfold not_le) assume as: "x \ 1 / 2" "y \ 1 / 2" then have "g1 (2 *\<^sub>R x) = g1 (2 *\<^sub>R y)" - using xy(3) unfolding joinpaths_def by auto - moreover - have "2 *\<^sub>R x \ {0..1}" "2 *\<^sub>R y \ {0..1}" using xy(1,2) as + using xy(3) + unfolding joinpaths_def + by auto + moreover have "2 *\<^sub>R x \ {0..1}" "2 *\<^sub>R y \ {0..1}" + using xy(1,2) as by auto - ultimately - show ?thesis using inj(1)[of "2*\<^sub>R x" "2*\<^sub>R y"] by auto + ultimately show ?thesis + using inj(1)[of "2*\<^sub>R x" "2*\<^sub>R y"] + by auto next - assume as:"x > 1 / 2" "y > 1 / 2" + assume as: "x > 1 / 2" "y > 1 / 2" then have "g2 (2 *\<^sub>R x - 1) = g2 (2 *\<^sub>R y - 1)" - using xy(3) unfolding joinpaths_def by auto - moreover - have "2 *\<^sub>R x - 1 \ {0..1}" "2 *\<^sub>R y - 1 \ {0..1}" - using xy(1,2) as by auto - ultimately - show ?thesis using inj(2)[of "2*\<^sub>R x - 1" "2*\<^sub>R y - 1"] by auto + using xy(3) + unfolding joinpaths_def + by auto + moreover have "2 *\<^sub>R x - 1 \ {0..1}" "2 *\<^sub>R y - 1 \ {0..1}" + using xy(1,2) as + by auto + ultimately show ?thesis + using inj(2)[of "2*\<^sub>R x - 1" "2*\<^sub>R y - 1"] by auto next - assume as:"x \ 1 / 2" "y > 1 / 2" + assume as: "x \ 1 / 2" "y > 1 / 2" then have "?g x \ path_image g1" "?g y \ path_image g2" unfolding path_image_def joinpaths_def using xy(1,2) by auto - moreover - have "?g y \ pathstart g2" using as(2) unfolding pathstart_def joinpaths_def + moreover have "?g y \ pathstart g2" + using as(2) + unfolding pathstart_def joinpaths_def using inj(2)[of "2 *\<^sub>R y - 1" 0] and xy(2) by (auto simp add: field_simps) - ultimately - have *:"?g x = pathstart g1" using assms(4) unfolding xy(3) by auto - then have "x = 0" unfolding pathstart_def joinpaths_def using as(1) and xy(1) - using inj(1)[of "2 *\<^sub>R x" 0] by auto - moreover - have "y = 1" using * unfolding xy(3) assms(3)[THEN sym] - unfolding joinpaths_def pathfinish_def using as(2) and xy(2) - using inj(2)[of "2 *\<^sub>R y - 1" 1] by auto - ultimately show ?thesis by auto + ultimately have *: "?g x = pathstart g1" + using assms(4) + unfolding xy(3) + by auto + then have "x = 0" + unfolding pathstart_def joinpaths_def + using as(1) and xy(1) + using inj(1)[of "2 *\<^sub>R x" 0] + by auto + moreover have "y = 1" + using * + unfolding xy(3) assms(3)[symmetric] + unfolding joinpaths_def pathfinish_def + using as(2) and xy(2) + using inj(2)[of "2 *\<^sub>R y - 1" 1] + by auto + ultimately show ?thesis + by auto next assume as: "x > 1 / 2" "y \ 1 / 2" - then have "?g x \ path_image g2" "?g y \ path_image g1" + then have "?g x \ path_image g2" and "?g y \ path_image g1" unfolding path_image_def joinpaths_def using xy(1,2) by auto - moreover - have "?g x \ pathstart g2" using as(1) unfolding pathstart_def joinpaths_def + moreover have "?g x \ pathstart g2" + using as(1) + unfolding pathstart_def joinpaths_def using inj(2)[of "2 *\<^sub>R x - 1" 0] and xy(1) by (auto simp add: field_simps) - ultimately - have *: "?g y = pathstart g1" using assms(4) unfolding xy(3) by auto - then have "y = 0" unfolding pathstart_def joinpaths_def using as(2) and xy(2) - using inj(1)[of "2 *\<^sub>R y" 0] by auto - moreover - have "x = 1" using * unfolding xy(3)[THEN sym] assms(3)[THEN sym] + ultimately have *: "?g y = pathstart g1" + using assms(4) + unfolding xy(3) + by auto + then have "y = 0" + unfolding pathstart_def joinpaths_def + using as(2) and xy(2) + using inj(1)[of "2 *\<^sub>R y" 0] + by auto + moreover have "x = 1" + using * + unfolding xy(3)[symmetric] assms(3)[symmetric] unfolding joinpaths_def pathfinish_def using as(1) and xy(1) - using inj(2)[of "2 *\<^sub>R x - 1" 1] by auto - ultimately show ?thesis by auto + using inj(2)[of "2 *\<^sub>R x - 1" 1] + by auto + ultimately show ?thesis + by auto qed qed lemma injective_path_join: - assumes "injective_path g1" "injective_path g2" "pathfinish g1 = pathstart g2" - "(path_image g1 \ path_image g2) \ {pathstart g2}" - shows "injective_path(g1 +++ g2)" + assumes "injective_path g1" + and "injective_path g2" + and "pathfinish g1 = pathstart g2" + and "path_image g1 \ path_image g2 \ {pathstart g2}" + shows "injective_path (g1 +++ g2)" unfolding injective_path_def proof (rule, rule, rule) let ?g = "g1 +++ g2" @@ -268,31 +330,39 @@ assume xy: "x \ {0..1}" "y \ {0..1}" "(g1 +++ g2) x = (g1 +++ g2) y" show "x = y" proof (cases "x \ 1/2", case_tac[!] "y \ 1/2", unfold not_le) - assume "x \ 1 / 2" "y \ 1 / 2" - then show ?thesis using inj(1)[of "2*\<^sub>R x" "2*\<^sub>R y"] and xy + assume "x \ 1 / 2" and "y \ 1 / 2" + then show ?thesis + using inj(1)[of "2*\<^sub>R x" "2*\<^sub>R y"] and xy unfolding joinpaths_def by auto next - assume "x > 1 / 2" "y > 1 / 2" - then show ?thesis using inj(2)[of "2*\<^sub>R x - 1" "2*\<^sub>R y - 1"] and xy + assume "x > 1 / 2" and "y > 1 / 2" + then show ?thesis + using inj(2)[of "2*\<^sub>R x - 1" "2*\<^sub>R y - 1"] and xy unfolding joinpaths_def by auto next assume as: "x \ 1 / 2" "y > 1 / 2" - then have "?g x \ path_image g1" "?g y \ path_image g2" + then have "?g x \ path_image g1" and "?g y \ path_image g2" unfolding path_image_def joinpaths_def - using xy(1,2) by auto - then have "?g x = pathfinish g1" "?g y = pathstart g2" - using assms(4) unfolding assms(3) xy(3) by auto + using xy(1,2) + by auto + then have "?g x = pathfinish g1" and "?g y = pathstart g2" + using assms(4) + unfolding assms(3) xy(3) + by auto then show ?thesis using as and inj(1)[of "2 *\<^sub>R x" 1] inj(2)[of "2 *\<^sub>R y - 1" 0] and xy(1,2) unfolding pathstart_def pathfinish_def joinpaths_def by auto next - assume as:"x > 1 / 2" "y \ 1 / 2" - then have "?g x \ path_image g2" "?g y \ path_image g1" + assume as:"x > 1 / 2" "y \ 1 / 2" + then have "?g x \ path_image g2" and "?g y \ path_image g1" unfolding path_image_def joinpaths_def - using xy(1,2) by auto - then have "?g x = pathstart g2" "?g y = pathfinish g1" - using assms(4) unfolding assms(3) xy(3) by auto + using xy(1,2) + by auto + then have "?g x = pathstart g2" and "?g y = pathfinish g1" + using assms(4) + unfolding assms(3) xy(3) + by auto then show ?thesis using as and inj(2)[of "2 *\<^sub>R x - 1" 0] inj(1)[of "2 *\<^sub>R y" 1] and xy(1,2) unfolding pathstart_def pathfinish_def joinpaths_def by auto @@ -300,64 +370,85 @@ qed lemmas join_paths_simps = path_join path_image_join pathstart_join pathfinish_join - + -subsection {* Reparametrizing a closed curve to start at some chosen point. *} +subsection {* Reparametrizing a closed curve to start at some chosen point *} -definition "shiftpath a (f::real \ 'a::topological_space) = - (\x. if (a + x) \ 1 then f(a + x) else f(a + x - 1))" +definition shiftpath :: "real \ (real \ 'a::topological_space) \ real \ 'a" + where "shiftpath a f = (\x. if (a + x) \ 1 then f (a + x) else f (a + x - 1))" -lemma pathstart_shiftpath: "a \ 1 \ pathstart(shiftpath a g) = g a" +lemma pathstart_shiftpath: "a \ 1 \ pathstart (shiftpath a g) = g a" unfolding pathstart_def shiftpath_def by auto lemma pathfinish_shiftpath: - assumes "0 \ a" "pathfinish g = pathstart g" - shows "pathfinish(shiftpath a g) = g a" - using assms unfolding pathstart_def pathfinish_def shiftpath_def + assumes "0 \ a" + and "pathfinish g = pathstart g" + shows "pathfinish (shiftpath a g) = g a" + using assms + unfolding pathstart_def pathfinish_def shiftpath_def by auto lemma endpoints_shiftpath: - assumes "pathfinish g = pathstart g" "a \ {0 .. 1}" - shows "pathfinish(shiftpath a g) = g a" "pathstart(shiftpath a g) = g a" - using assms by(auto intro!:pathfinish_shiftpath pathstart_shiftpath) + assumes "pathfinish g = pathstart g" + and "a \ {0 .. 1}" + shows "pathfinish (shiftpath a g) = g a" + and "pathstart (shiftpath a g) = g a" + using assms + by (auto intro!: pathfinish_shiftpath pathstart_shiftpath) lemma closed_shiftpath: - assumes "pathfinish g = pathstart g" "a \ {0..1}" - shows "pathfinish(shiftpath a g) = pathstart(shiftpath a g)" - using endpoints_shiftpath[OF assms] by auto + assumes "pathfinish g = pathstart g" + and "a \ {0..1}" + shows "pathfinish (shiftpath a g) = pathstart (shiftpath a g)" + using endpoints_shiftpath[OF assms] + by auto lemma path_shiftpath: - assumes "path g" "pathfinish g = pathstart g" "a \ {0..1}" - shows "path(shiftpath a g)" + assumes "path g" + and "pathfinish g = pathstart g" + and "a \ {0..1}" + shows "path (shiftpath a g)" proof - - have *: "{0 .. 1} = {0 .. 1-a} \ {1-a .. 1}" using assms(3) by auto + have *: "{0 .. 1} = {0 .. 1-a} \ {1-a .. 1}" + using assms(3) by auto have **: "\x. x + a = 1 \ g (x + a - 1) = g (x + a)" - using assms(2)[unfolded pathfinish_def pathstart_def] by auto + using assms(2)[unfolded pathfinish_def pathstart_def] + by auto show ?thesis unfolding path_def shiftpath_def * apply (rule continuous_on_union) apply (rule closed_real_atLeastAtMost)+ - apply (rule continuous_on_eq[of _ "g \ (\x. a + x)"]) prefer 3 - apply (rule continuous_on_eq[of _ "g \ (\x. a - 1 + x)"]) defer prefer 3 - apply (rule continuous_on_intros)+ prefer 2 + apply (rule continuous_on_eq[of _ "g \ (\x. a + x)"]) + prefer 3 + apply (rule continuous_on_eq[of _ "g \ (\x. a - 1 + x)"]) + defer + prefer 3 + apply (rule continuous_on_intros)+ + prefer 2 apply (rule continuous_on_intros)+ apply (rule_tac[1-2] continuous_on_subset[OF assms(1)[unfolded path_def]]) using assms(3) and ** - apply (auto, auto simp add: field_simps) + apply auto + apply (auto simp add: field_simps) done qed lemma shiftpath_shiftpath: - assumes "pathfinish g = pathstart g" "a \ {0..1}" "x \ {0..1}" + assumes "pathfinish g = pathstart g" + and "a \ {0..1}" + and "x \ {0..1}" shows "shiftpath (1 - a) (shiftpath a g) x = g x" - using assms unfolding pathfinish_def pathstart_def shiftpath_def by auto + using assms + unfolding pathfinish_def pathstart_def shiftpath_def + by auto lemma path_image_shiftpath: - assumes "a \ {0..1}" "pathfinish g = pathstart g" - shows "path_image(shiftpath a g) = path_image g" + assumes "a \ {0..1}" + and "pathfinish g = pathstart g" + shows "path_image (shiftpath a g) = path_image g" proof - { fix x - assume as:"g 1 = g 0" "x \ {0..1::real}" " \y\{0..1} \ {x. \ a + x \ 1}. g x \ g (a + y - 1)" + assume as: "g 1 = g 0" "x \ {0..1::real}" " \y\{0..1} \ {x. \ a + x \ 1}. g x \ g (a + y - 1)" then have "\y\{0..1} \ {x. a + x \ 1}. g x = g (a + y)" proof (cases "a \ x") case False @@ -368,46 +459,57 @@ done next case True - then show ?thesis using as(1-2) and assms(1) apply(rule_tac x="x - a" in bexI) - by(auto simp add: field_simps) + then show ?thesis + using as(1-2) and assms(1) + apply (rule_tac x="x - a" in bexI) + apply (auto simp add: field_simps) + done qed } then show ?thesis - using assms unfolding shiftpath_def path_image_def pathfinish_def pathstart_def - by(auto simp add: image_iff) + using assms + unfolding shiftpath_def path_image_def pathfinish_def pathstart_def + by (auto simp add: image_iff) qed -subsection {* Special case of straight-line paths. *} +subsection {* Special case of straight-line paths *} definition linepath :: "'a::real_normed_vector \ 'a \ real \ 'a" where "linepath a b = (\x. (1 - x) *\<^sub>R a + x *\<^sub>R b)" -lemma pathstart_linepath[simp]: "pathstart(linepath a b) = a" - unfolding pathstart_def linepath_def by auto +lemma pathstart_linepath[simp]: "pathstart (linepath a b) = a" + unfolding pathstart_def linepath_def + by auto -lemma pathfinish_linepath[simp]: "pathfinish(linepath a b) = b" - unfolding pathfinish_def linepath_def by auto +lemma pathfinish_linepath[simp]: "pathfinish (linepath a b) = b" + unfolding pathfinish_def linepath_def + by auto lemma continuous_linepath_at[intro]: "continuous (at x) (linepath a b)" - unfolding linepath_def by (intro continuous_intros) + unfolding linepath_def + by (intro continuous_intros) lemma continuous_on_linepath[intro]: "continuous_on s (linepath a b)" - using continuous_linepath_at by(auto intro!: continuous_at_imp_continuous_on) + using continuous_linepath_at + by (auto intro!: continuous_at_imp_continuous_on) -lemma path_linepath[intro]: "path(linepath a b)" - unfolding path_def by(rule continuous_on_linepath) +lemma path_linepath[intro]: "path (linepath a b)" + unfolding path_def + by (rule continuous_on_linepath) -lemma path_image_linepath[simp]: "path_image(linepath a b) = (closed_segment a b)" +lemma path_image_linepath[simp]: "path_image (linepath a b) = closed_segment a b" unfolding path_image_def segment linepath_def - apply (rule set_eqI, rule) defer + apply (rule set_eqI) + apply rule + defer unfolding mem_Collect_eq image_iff - apply(erule exE) - apply(rule_tac x="u *\<^sub>R 1" in bexI) + apply (erule exE) + apply (rule_tac x="u *\<^sub>R 1" in bexI) apply auto done -lemma reversepath_linepath[simp]: "reversepath(linepath a b) = linepath b a" +lemma reversepath_linepath[simp]: "reversepath (linepath a b) = linepath b a" unfolding reversepath_def linepath_def by auto @@ -415,25 +517,30 @@ assumes "a \ b" shows "injective_path (linepath a b)" proof - - { fix x y :: "real" + { + fix x y :: "real" assume "x *\<^sub>R b + y *\<^sub>R a = x *\<^sub>R a + y *\<^sub>R b" - then have "(x - y) *\<^sub>R a = (x - y) *\<^sub>R b" by (simp add: algebra_simps) - with assms have "x = y" by simp } + then have "(x - y) *\<^sub>R a = (x - y) *\<^sub>R b" + by (simp add: algebra_simps) + with assms have "x = y" + by simp + } then show ?thesis unfolding injective_path_def linepath_def by (auto simp add: algebra_simps) qed -lemma simple_path_linepath[intro]: "a \ b \ simple_path(linepath a b)" - by(auto intro!: injective_imp_simple_path injective_path_linepath) +lemma simple_path_linepath[intro]: "a \ b \ simple_path (linepath a b)" + by (auto intro!: injective_imp_simple_path injective_path_linepath) -subsection {* Bounding a point away from a path. *} +subsection {* Bounding a point away from a path *} lemma not_on_path_ball: fixes g :: "real \ 'a::heine_borel" - assumes "path g" "z \ path_image g" - shows "\e > 0. ball z e \ (path_image g) = {}" + assumes "path g" + and "z \ path_image g" + shows "\e > 0. ball z e \ path_image g = {}" proof - obtain a where "a \ path_image g" "\y \ path_image g. dist z a \ dist z y" using distance_attains_inf[OF _ path_image_nonempty, of g z] @@ -447,34 +554,43 @@ lemma not_on_path_cball: fixes g :: "real \ 'a::heine_borel" - assumes "path g" "z \ path_image g" + assumes "path g" + and "z \ path_image g" shows "\e>0. cball z e \ (path_image g) = {}" proof - - obtain e where "ball z e \ path_image g = {}" "e>0" + obtain e where "ball z e \ path_image g = {}" "e > 0" using not_on_path_ball[OF assms] by auto - moreover have "cball z (e/2) \ ball z e" using `e>0` by auto - ultimately show ?thesis apply(rule_tac x="e/2" in exI) by auto + moreover have "cball z (e/2) \ ball z e" + using `e > 0` by auto + ultimately show ?thesis + apply (rule_tac x="e/2" in exI) + apply auto + done qed -subsection {* Path component, considered as a "joinability" relation (from Tom Hales). *} +subsection {* Path component, considered as a "joinability" relation (from Tom Hales) *} definition "path_component s x y \ (\g. path g \ path_image g \ s \ pathstart g = x \ pathfinish g = y)" -lemmas path_defs = path_def pathstart_def pathfinish_def path_image_def path_component_def +lemmas path_defs = path_def pathstart_def pathfinish_def path_image_def path_component_def lemma path_component_mem: assumes "path_component s x y" - shows "x \ s" "y \ s" - using assms unfolding path_defs by auto + shows "x \ s" and "y \ s" + using assms + unfolding path_defs + by auto lemma path_component_refl: assumes "x \ s" shows "path_component s x x" unfolding path_defs apply (rule_tac x="\u. x" in exI) - using assms apply (auto intro!:continuous_on_intros) done + using assms + apply (auto intro!: continuous_on_intros) + done lemma path_component_refl_eq: "path_component s x x \ x \ s" by (auto intro!: path_component_mem path_component_refl) @@ -488,21 +604,21 @@ done lemma path_component_trans: - assumes "path_component s x y" "path_component s y z" + assumes "path_component s x y" + and "path_component s y z" shows "path_component s x z" using assms unfolding path_component_def - apply - - apply (erule exE)+ + apply (elim exE) apply (rule_tac x="g +++ ga" in exI) apply (auto simp add: path_image_join) done -lemma path_component_of_subset: "s \ t \ path_component s x y \ path_component t x y" +lemma path_component_of_subset: "s \ t \ path_component s x y \ path_component t x y" unfolding path_component_def by auto -subsection {* Can also consider it as a set, as the name suggests. *} +text {* Can also consider it as a set, as the name suggests. *} lemma path_component_set: "{y. path_component s x y} = @@ -514,13 +630,15 @@ done lemma path_component_subset: "{y. path_component s x y} \ s" - apply (rule, rule path_component_mem(2)) + apply rule + apply (rule path_component_mem(2)) apply auto done lemma path_component_eq_empty: "{y. path_component s x y} = {} \ x \ s" apply rule - apply (drule equals0D[of _ x]) defer + apply (drule equals0D[of _ x]) + defer apply (rule equals0I) unfolding mem_Collect_eq apply (drule path_component_mem(1)) @@ -529,29 +647,35 @@ done -subsection {* Path connectedness of a space. *} +subsection {* Path connectedness of a space *} definition "path_connected s \ - (\x\s. \y\s. \g. path g \ (path_image g) \ s \ pathstart g = x \ pathfinish g = y)" + (\x\s. \y\s. \g. path g \ path_image g \ s \ pathstart g = x \ pathfinish g = y)" lemma path_connected_component: "path_connected s \ (\x\s. \y\s. path_component s x y)" unfolding path_connected_def path_component_def by auto -lemma path_connected_component_set: "path_connected s \ (\x\s. {y. path_component s x y} = s)" +lemma path_connected_component_set: "path_connected s \ (\x\s. {y. path_component s x y} = s)" unfolding path_connected_component - apply (rule, rule, rule, rule path_component_subset) + apply rule + apply rule + apply rule + apply (rule path_component_subset) unfolding subset_eq mem_Collect_eq Ball_def apply auto done -subsection {* Some useful lemmas about path-connectedness. *} +subsection {* Some useful lemmas about path-connectedness *} lemma convex_imp_path_connected: fixes s :: "'a::real_normed_vector set" - assumes "convex s" shows "path_connected s" + assumes "convex s" + shows "path_connected s" unfolding path_connected_def - apply (rule, rule, rule_tac x = "linepath x y" in exI) + apply rule + apply rule + apply (rule_tac x = "linepath x y" in exI) unfolding path_image_linepath using assms [unfolded convex_contains_segment] apply auto @@ -561,26 +685,33 @@ assumes "path_connected s" shows "connected s" unfolding connected_def not_ex - apply (rule, rule, rule ccontr) + apply rule + apply rule + apply (rule ccontr) unfolding not_not - apply (erule conjE)+ + apply (elim conjE) proof - fix e1 e2 assume as: "open e1" "open e2" "s \ e1 \ e2" "e1 \ e2 \ s = {}" "e1 \ s \ {}" "e2 \ s \ {}" - then obtain x1 x2 where obt:"x1\e1\s" "x2\e2\s" by auto - then obtain g where g:"path g" "path_image g \ s" "pathstart g = x1" "pathfinish g = x2" + then obtain x1 x2 where obt:"x1 \ e1 \ s" "x2 \ e2 \ s" + by auto + then obtain g where g: "path g" "path_image g \ s" "pathstart g = x1" "pathfinish g = x2" using assms[unfolded path_connected_def,rule_format,of x1 x2] by auto have *: "connected {0..1::real}" by (auto intro!: convex_connected convex_real_interval) have "{0..1} \ {x \ {0..1}. g x \ e1} \ {x \ {0..1}. g x \ e2}" using as(3) g(2)[unfolded path_defs] by blast moreover have "{x \ {0..1}. g x \ e1} \ {x \ {0..1}. g x \ e2} = {}" - using as(4) g(2)[unfolded path_defs] unfolding subset_eq by auto + using as(4) g(2)[unfolded path_defs] + unfolding subset_eq + by auto moreover have "{x \ {0..1}. g x \ e1} \ {} \ {x \ {0..1}. g x \ e2} \ {}" - using g(3,4)[unfolded path_defs] using obt + using g(3,4)[unfolded path_defs] + using obt by (simp add: ex_in_conv [symmetric], metis zero_le_one order_refl) ultimately show False - using *[unfolded connected_local not_ex, rule_format, of "{x\{0..1}. g x \ e1}" "{x\{0..1}. g x \ e2}"] + using *[unfolded connected_local not_ex, rule_format, + of "{x\{0..1}. g x \ e1}" "{x\{0..1}. g x \ e2}"] using continuous_open_in_preimage[OF g(1)[unfolded path_def] as(1)] using continuous_open_in_preimage[OF g(1)[unfolded path_def] as(2)] by auto @@ -600,20 +731,23 @@ unfolding mem_Collect_eq apply auto done - then obtain e where e:"e>0" "ball y e \ s" - using assms[unfolded open_contains_ball] by auto + then obtain e where e: "e > 0" "ball y e \ s" + using assms[unfolded open_contains_ball] + by auto show "\e > 0. ball y e \ {y. path_component s x y}" apply (rule_tac x=e in exI) - apply (rule,rule `e>0`, rule) + apply (rule,rule `e>0`) + apply rule unfolding mem_ball mem_Collect_eq proof - fix z assume "dist y z < e" then show "path_component s x z" - apply (rule_tac path_component_trans[of _ _ y]) defer + apply (rule_tac path_component_trans[of _ _ y]) + defer apply (rule path_component_of_subset[OF e(2)]) apply (rule convex_imp_path_connected[OF convex_ball, unfolded path_connected_component, rule_format]) - using `e>0` as + using `e > 0` as apply auto done qed @@ -622,16 +756,21 @@ lemma open_non_path_component: fixes s :: "'a::real_normed_vector set" assumes "open s" - shows "open(s - {y. path_component s x y})" + shows "open (s - {y. path_component s x y})" unfolding open_contains_ball proof fix y - assume as: "y\s - {y. path_component s x y}" - then obtain e where e:"e>0" "ball y e \ s" - using assms [unfolded open_contains_ball] by auto + assume as: "y \ s - {y. path_component s x y}" + then obtain e where e: "e > 0" "ball y e \ s" + using assms [unfolded open_contains_ball] + by auto show "\e>0. ball y e \ s - {y. path_component s x y}" apply (rule_tac x=e in exI) - apply (rule, rule `e>0`, rule, rule) defer + apply rule + apply (rule `e>0`) + apply rule + apply rule + defer proof (rule ccontr) fix z assume "z \ ball y e" "\ z \ {y. path_component s x y}" @@ -643,43 +782,49 @@ apply (rule convex_imp_path_connected[OF convex_ball, unfolded path_connected_component, rule_format]) apply auto done - then show False using as by auto + then show False + using as by auto qed (insert e(2), auto) qed lemma connected_open_path_connected: fixes s :: "'a::real_normed_vector set" - assumes "open s" "connected s" + assumes "open s" + and "connected s" shows "path_connected s" unfolding path_connected_component_set proof (rule, rule, rule path_component_subset, rule) fix x y - assume "x \ s" "y \ s" + assume "x \ s" and "y \ s" show "y \ {y. path_component s x y}" proof (rule ccontr) - assume "y \ {y. path_component s x y}" - moreover - have "{y. path_component s x y} \ s \ {}" - using `x\s` path_component_eq_empty path_component_subset[of s x] by auto + assume "\ ?thesis" + moreover have "{y. path_component s x y} \ s \ {}" + using `x \ s` path_component_eq_empty path_component_subset[of s x] + by auto ultimately show False - using `y\s` open_non_path_component[OF assms(1)] open_path_component[OF assms(1)] - using assms(2)[unfolded connected_def not_ex, rule_format, of"{y. path_component s x y}" "s - {y. path_component s x y}"] + using `y \ s` open_non_path_component[OF assms(1)] open_path_component[OF assms(1)] + using assms(2)[unfolded connected_def not_ex, rule_format, + of"{y. path_component s x y}" "s - {y. path_component s x y}"] by auto qed qed lemma path_connected_continuous_image: - assumes "continuous_on s f" "path_connected s" + assumes "continuous_on s f" + and "path_connected s" shows "path_connected (f ` s)" unfolding path_connected_def proof (rule, rule) fix x' y' assume "x' \ f ` s" "y' \ f ` s" - then obtain x y where xy: "x\s" "y\s" "x' = f x" "y' = f y" by auto - guess g using assms(2)[unfolded path_connected_def, rule_format, OF xy(1,2)] .. + then obtain x y where x: "x \ s" and y: "y \ s" and x': "x' = f x" and y': "y' = f y" + by auto + from x y obtain g where "path g \ path_image g \ s \ pathstart g = x \ pathfinish g = y" + using assms(2)[unfolded path_connected_def] by fast then show "\g. path g \ path_image g \ f ` s \ pathstart g = x' \ pathfinish g = y'" - unfolding xy + unfolding x' y' apply (rule_tac x="f \ g" in exI) unfolding path_defs apply (intro conjI continuous_on_compose continuous_on_subset[OF assms(1)]) @@ -688,11 +833,12 @@ qed lemma homeomorphic_path_connectedness: - "s homeomorphic t \ (path_connected s \ path_connected t)" + "s homeomorphic t \ path_connected s \ path_connected t" unfolding homeomorphic_def homeomorphism_def - apply (erule exE|erule conjE)+ + apply (erule exE|erule conjE)+ apply rule - apply (drule_tac f=f in path_connected_continuous_image) prefer 3 + apply (drule_tac f=f in path_connected_continuous_image) + prefer 3 apply (drule_tac f=g in path_connected_continuous_image) apply auto done @@ -702,21 +848,26 @@ lemma path_connected_singleton: "path_connected {a}" unfolding path_connected_def pathstart_def pathfinish_def path_image_def - apply (clarify, rule_tac x="\x. a" in exI, simp add: image_constant_conv) + apply clarify + apply (rule_tac x="\x. a" in exI) + apply (simp add: image_constant_conv) apply (simp add: path_def continuous_on_const) done lemma path_connected_Un: - assumes "path_connected s" "path_connected t" "s \ t \ {}" + assumes "path_connected s" + and "path_connected t" + and "s \ t \ {}" shows "path_connected (s \ t)" unfolding path_connected_component proof (rule, rule) fix x y assume as: "x \ s \ t" "y \ s \ t" - from assms(3) obtain z where "z \ s \ t" by auto + from assms(3) obtain z where "z \ s \ t" + by auto then show "path_component (s \ t) x y" using as and assms(1-2)[unfolded path_connected_component] - apply - + apply - apply (erule_tac[!] UnE)+ apply (rule_tac[2-3] path_component_trans[of _ _ z]) apply (auto simp add:path_component_of_subset [OF Un_upper1] path_component_of_subset[OF Un_upper2]) @@ -740,11 +891,11 @@ qed -subsection {* sphere is path-connected. *} +subsection {* Sphere is path-connected *} lemma path_connected_punctured_universe: assumes "2 \ DIM('a::euclidean_space)" - shows "path_connected((UNIV::'a::euclidean_space set) - {a})" + shows "path_connected ((UNIV::'a set) - {a})" proof - let ?A = "{x::'a. \i\Basis. x \ i < a \ i}" let ?B = "{x::'a. \i\Basis. a \ i < x \ i}" @@ -754,70 +905,87 @@ proof (rule path_connected_UNION) fix i :: 'a assume "i \ Basis" - then show "(\i\Basis. (a \ i - 1)*\<^sub>R i) \ {x::'a. x \ i < a \ i}" by simp + then show "(\i\Basis. (a \ i - 1)*\<^sub>R i) \ {x::'a. x \ i < a \ i}" + by simp show "path_connected {x. x \ i < a \ i}" using convex_imp_path_connected [OF convex_halfspace_lt, of i "a \ i"] by (simp add: inner_commute) qed - have B: "path_connected ?B" unfolding Collect_bex_eq + have B: "path_connected ?B" + unfolding Collect_bex_eq proof (rule path_connected_UNION) fix i :: 'a assume "i \ Basis" - then show "(\i\Basis. (a \ i + 1) *\<^sub>R i) \ {x::'a. a \ i < x \ i}" by simp + then show "(\i\Basis. (a \ i + 1) *\<^sub>R i) \ {x::'a. a \ i < x \ i}" + by simp show "path_connected {x. a \ i < x \ i}" using convex_imp_path_connected [OF convex_halfspace_gt, of "a \ i" i] by (simp add: inner_commute) qed - obtain S :: "'a set" where "S \ Basis" "card S = Suc (Suc 0)" - using ex_card[OF assms] by auto - then obtain b0 b1 :: 'a where "b0 \ Basis" "b1 \ Basis" "b0 \ b1" + obtain S :: "'a set" where "S \ Basis" and "card S = Suc (Suc 0)" + using ex_card[OF assms] + by auto + then obtain b0 b1 :: 'a where "b0 \ Basis" and "b1 \ Basis" and "b0 \ b1" unfolding card_Suc_eq by auto - then have "a + b0 - b1 \ ?A \ ?B" by (auto simp: inner_simps inner_Basis) - then have "?A \ ?B \ {}" by fast + then have "a + b0 - b1 \ ?A \ ?B" + by (auto simp: inner_simps inner_Basis) + then have "?A \ ?B \ {}" + by fast with A B have "path_connected (?A \ ?B)" by (rule path_connected_Un) also have "?A \ ?B = {x. \i\Basis. x \ i \ a \ i}" unfolding neq_iff bex_disj_distrib Collect_disj_eq .. also have "\ = {x. x \ a}" - unfolding euclidean_eq_iff [where 'a='a] by (simp add: Bex_def) - also have "\ = UNIV - {a}" by auto + unfolding euclidean_eq_iff [where 'a='a] + by (simp add: Bex_def) + also have "\ = UNIV - {a}" + by auto finally show ?thesis . qed lemma path_connected_sphere: assumes "2 \ DIM('a::euclidean_space)" - shows "path_connected {x::'a::euclidean_space. norm(x - a) = r}" + shows "path_connected {x::'a. norm (x - a) = r}" proof (rule linorder_cases [of r 0]) assume "r < 0" - then have "{x::'a. norm(x - a) = r} = {}" by auto - then show ?thesis using path_connected_empty by simp + then have "{x::'a. norm(x - a) = r} = {}" + by auto + then show ?thesis + using path_connected_empty by simp next assume "r = 0" - then show ?thesis using path_connected_singleton by simp + then show ?thesis + using path_connected_singleton by simp next assume r: "0 < r" - then have *: "{x::'a. norm(x - a) = r} = (\x. a + r *\<^sub>R x) ` {x. norm x = 1}" - apply - - apply (rule set_eqI, rule) + have *: "{x::'a. norm(x - a) = r} = (\x. a + r *\<^sub>R x) ` {x. norm x = 1}" + apply (rule set_eqI) + apply rule unfolding image_iff apply (rule_tac x="(1/r) *\<^sub>R (x - a)" in bexI) unfolding mem_Collect_eq norm_scaleR + using r apply (auto simp add: scaleR_right_diff_distrib) done have **: "{x::'a. norm x = 1} = (\x. (1/norm x) *\<^sub>R x) ` (UNIV - {0})" - apply (rule set_eqI,rule) + apply (rule set_eqI) + apply rule unfolding image_iff apply (rule_tac x=x in bexI) unfolding mem_Collect_eq - apply (auto split:split_if_asm) + apply (auto split: split_if_asm) done have "continuous_on (UNIV - {0}) (\x::'a. 1 / norm x)" - unfolding field_divide_inverse by (simp add: continuous_on_intros) - then show ?thesis unfolding * ** using path_connected_punctured_universe[OF assms] + unfolding field_divide_inverse + by (simp add: continuous_on_intros) + then show ?thesis + unfolding * ** + using path_connected_punctured_universe[OF assms] by (auto intro!: path_connected_continuous_image continuous_on_intros) qed -lemma connected_sphere: "2 \ DIM('a::euclidean_space) \ connected {x::'a. norm(x - a) = r}" - using path_connected_sphere path_connected_imp_connected by auto +lemma connected_sphere: "2 \ DIM('a::euclidean_space) \ connected {x::'a. norm (x - a) = r}" + using path_connected_sphere path_connected_imp_connected + by auto end