# HG changeset patch # User paulson # Date 1524427514 -3600 # Node ID c8a506be83bd230ea4fef6d505540b792426144d # Parent b91a043c0dcbfa726f36234e50e22f52c5498f8d Tidied a lot of messy proofs diff -r b91a043c0dcb -r c8a506be83bd src/HOL/Analysis/Brouwer_Fixpoint.thy --- a/src/HOL/Analysis/Brouwer_Fixpoint.thy Sat Apr 21 11:13:35 2018 +0200 +++ b/src/HOL/Analysis/Brouwer_Fixpoint.thy Sun Apr 22 21:05:14 2018 +0100 @@ -2,9 +2,6 @@ Author: Robert Himmelmann, TU Muenchen (Translation from HOL light) and LCP *) -(* ========================================================================= *) -(* Results connected with topological dimension. *) -(* *) (* At the moment this is just Brouwer's fixpoint theorem. The proof is from *) (* Kuhn: "some combinatorial lemmas in topology", IBM J. v4. (1960) p. 518 *) (* See "http://www.research.ibm.com/journal/rd/045/ibmrd0405K.pdf". *) @@ -14,7 +11,6 @@ (* the big advantage of Kuhn's proof over the usual Sperner's lemma one. *) (* *) (* (c) Copyright, John Harrison 1998-2008 *) -(* ========================================================================= *) section \Results connected with topological dimension\ @@ -40,11 +36,7 @@ lemma swap_image: "Fun.swap i j f ` A = (if i \ A then (if j \ A then f ` A else f ` ((A - {i}) \ {j})) else (if j \ A then f ` ((A - {j}) \ {i}) else f ` A))" - apply (auto simp: Fun.swap_def image_iff) - apply metis - apply (metis member_remove remove_def) - apply (metis member_remove remove_def) - done + by (auto simp: swap_def image_def) metis lemmas swap_apply1 = swap_apply(1) lemmas swap_apply2 = swap_apply(2) @@ -191,9 +183,9 @@ moreover obtain a where "rl a = Suc n" "a \ s" by (metis atMost_iff image_iff le_Suc_eq rl) ultimately have n: "{..n} = rl ` (s - {a})" - by (auto simp add: inj_on_image_set_diff Diff_subset rl) + by (auto simp: inj_on_image_set_diff Diff_subset rl) have "{a\s. rl ` (s - {a}) = {..n}} = {a}" - using inj_rl \a \ s\ by (auto simp add: n inj_on_image_eq_iff[OF inj_rl] Diff_subset) + using inj_rl \a \ s\ by (auto simp: n inj_on_image_eq_iff[OF inj_rl] Diff_subset) then show "card ?S = 1" unfolding card_S by simp } @@ -202,7 +194,7 @@ proof cases assume *: "{..n} \ rl ` s" with rl rl_bd[OF s] have rl_s: "rl ` s = {..n}" - by (auto simp add: atMost_Suc subset_insert_iff split: if_split_asm) + by (auto simp: atMost_Suc subset_insert_iff split: if_split_asm) then have "\ inj_on rl s" by (intro pigeonhole) simp then obtain a b where ab: "a \ s" "b \ s" "rl a = rl b" "a \ b" @@ -210,7 +202,7 @@ then have eq: "rl ` (s - {a}) = rl ` s" by auto with ab have inj: "inj_on rl (s - {a})" - by (intro eq_card_imp_inj_on) (auto simp add: rl_s card_Diff_singleton_if) + by (intro eq_card_imp_inj_on) (auto simp: rl_s card_Diff_singleton_if) { fix x assume "x \ s" "x \ {a, b}" then have "rl ` s - {rl x} = rl ` ((s - {a}) - {x})" @@ -275,7 +267,7 @@ with upd have "upd ` {..< x} \ upd ` {..< y}" by (subst inj_on_image_eq_iff[where C="{..< n}"]) (auto simp: bij_betw_def) then have "enum x \ enum y" - by (auto simp add: enum_def fun_eq_iff) } + by (auto simp: enum_def fun_eq_iff) } then show ?thesis by (auto simp: inj_on_def) qed @@ -325,7 +317,7 @@ by (auto simp: enum_def le_fun_def in_upd_image Ball_def[symmetric]) lemma enum_strict_mono: "i \ n \ j \ n \ enum i < enum j \ i < j" - using enum_mono[of i j] enum_inj[of i j] by (auto simp add: le_less) + using enum_mono[of i j] enum_inj[of i j] by (auto simp: le_less) lemma chain: "a \ s \ b \ s \ a \ b \ b \ a" by (auto simp: s_eq enum_mono) @@ -346,7 +338,7 @@ by (induct i) (auto simp: enum_Suc enum_0 base_out upd_space not_less[symmetric]) lemma out_eq_p: "a \ s \ n \ j \ a j = p" - unfolding s_eq by (auto simp add: enum_eq_p) + unfolding s_eq by (auto simp: enum_eq_p) lemma s_le_p: "a \ s \ a j \ p" using out_eq_p[of a j] s_space by (cases "j < n") auto @@ -578,7 +570,7 @@ by (auto simp: image_iff Ball_def) arith then have upd_Suc: "\i. i \ n \ (upd\Suc) ` {..< i} = upd ` {..< Suc i} - {n}" using \upd 0 = n\ upd_inj - by (auto simp add: image_comp[symmetric] inj_on_image_set_diff[OF inj_upd]) + by (auto simp: image_comp[symmetric] inj_on_image_set_diff[OF inj_upd]) have n_in_upd: "\i. n \ upd ` {..< Suc i}" using \upd 0 = n\ by auto @@ -685,7 +677,7 @@ qed lemma card_2_exists: "card s = 2 \ (\x\s. \y\s. x \ y \ (\z\s. z = x \ z = y))" - by (auto simp add: card_Suc_eq eval_nat_numeral) + by (auto simp: card_Suc_eq eval_nat_numeral) lemma ksimplex_replace_2: assumes s: "ksimplex p n s" and "a \ s" and "n \ 0" @@ -723,11 +715,11 @@ obtain i' where "i' \ n" "enum i' \ enum 0" "enum i' (upd 0) \ p" unfolding s_eq by (auto intro: upd_space simp: enum_inj) then have "enum 1 \ enum i'" "enum i' (upd 0) < p" - using enum_le_p[of i' "upd 0"] by (auto simp add: enum_inj enum_mono upd_space) + using enum_le_p[of i' "upd 0"] by (auto simp: enum_inj enum_mono upd_space) then have "enum 1 (upd 0) < p" - by (auto simp add: le_fun_def intro: le_less_trans) + by (auto simp: le_fun_def intro: le_less_trans) then show "enum (Suc 0) \ {.. {..n \ 0\ by (auto simp add: enum_0 enum_Suc PiE_iff extensional_def upd_space) + using base \n \ 0\ by (auto simp: enum_0 enum_Suc PiE_iff extensional_def upd_space) { fix i assume "n \ i" then show "enum (Suc 0) i = p" using \n \ 0\ by (auto simp: enum_eq_p) } @@ -745,7 +737,7 @@ { fix j assume j: "j < n" from j \n \ 0\ have "f' j = enum (Suc j)" - by (auto simp add: f'_def enum_def upd_inj in_upd_image image_comp[symmetric] fun_eq_iff) } + by (auto simp: f'_def enum_def upd_inj in_upd_image image_comp[symmetric] fun_eq_iff) } note f'_eq_enum = this then have "enum ` Suc ` {..< n} = f' ` {..< n}" by (force simp: enum_inj) @@ -859,10 +851,10 @@ by (simp_all add: rot_def) { fix j assume j: "Suc j \ n" then have "b.enum (Suc j) = enum j" - by (induct j) (auto simp add: benum1 enum_0 b.enum_Suc enum_Suc rot_simps) } + by (induct j) (auto simp: benum1 enum_0 b.enum_Suc enum_Suc rot_simps) } note b_enum_eq_enum = this then have "enum ` {..< n} = b.enum ` Suc ` {..< n}" - by (auto simp add: image_comp intro!: image_cong) + by (auto simp: image_comp intro!: image_cong) also have "Suc ` {..< n} = {.. n} - {0}" by (auto simp: image_iff Ball_def) arith also have "{..< n} = {.. n} - {n}" @@ -871,7 +863,7 @@ unfolding s_eq \a = enum i\ \i = n\ using inj_on_image_set_diff[OF inj_enum Diff_subset, of "{n}"] inj_on_image_set_diff[OF b.inj_enum Diff_subset, of "{0}"] - by (simp add: comp_def ) + by (simp add: comp_def) have "b.enum 0 \ b.enum n" by (simp add: b.enum_mono) @@ -956,7 +948,7 @@ moreover note i ultimately have "enum j = b.enum j \ j \ i" unfolding enum_def[abs_def] b.enum_def[abs_def] - by (auto simp add: fun_eq_iff swap_image i'_def + by (auto simp: fun_eq_iff swap_image i'_def in_upd_image inj_on_image_set_diff[OF inj_upd]) } note enum_eq_benum = this then have "enum ` ({.. n} - {i}) = b.enum ` ({.. n} - {i})" @@ -1001,7 +993,7 @@ then obtain j where "t.enum (Suc l) = enum j" "j \ n" "enum j \ enum i" unfolding s_eq \a = enum i\ by auto with i have "t.enum (Suc l) \ t.enum l \ t.enum k \ t.enum (Suc l)" - by (auto simp add: i'_def enum_mono enum_inj l k) + by (auto simp: i'_def enum_mono enum_inj l k) with \Suc l < k\ \k \ n\ show False by (simp add: t.enum_mono) qed @@ -1041,7 +1033,7 @@ assume u: "u l = upd (Suc i')" define B where "B = b.enum ` {..n}" have "b.enum i' = enum i'" - using enum_eq_benum[of i'] i by (auto simp add: i'_def gr0_conv_Suc) + using enum_eq_benum[of i'] i by (auto simp: i'_def gr0_conv_Suc) have "c = t.enum (Suc l)" unfolding c_eq .. also have "t.enum (Suc l) = b.enum (Suc i')" using u \l < k\ \k \ n\ \Suc i' < n\ @@ -1432,7 +1424,7 @@ proof (rule ccontr) define n where "n = DIM('a)" have n: "1 \ n" "0 < n" "n \ 0" - unfolding n_def by (auto simp add: Suc_le_eq DIM_positive) + unfolding n_def by (auto simp: Suc_le_eq DIM_positive) assume "\ ?thesis" then have *: "\ (\x\unit_cube. f x - x = 0)" by auto @@ -1447,73 +1439,45 @@ using assms(2)[unfolded image_subset_iff Ball_def] unfolding mem_unit_cube by auto - obtain label :: "'a \ 'a \ nat" where + obtain label :: "'a \ 'a \ nat" where label [rule_format]: "\x. \i\Basis. label x i \ 1" - "\x. \i\Basis. x \ unit_cube \ True \ x \ i = 0 \ label x i = 0" - "\x. \i\Basis. x \ unit_cube \ True \ x \ i = 1 \ label x i = 1" - "\x. \i\Basis. x \ unit_cube \ True \ label x i = 0 \ x \ i \ f x \ i" - "\x. \i\Basis. x \ unit_cube \ True \ label x i = 1 \ f x \ i \ x \ i" - using kuhn_labelling_lemma[OF *] by blast + "\x. \i\Basis. x \ unit_cube \ x \ i = 0 \ label x i = 0" + "\x. \i\Basis. x \ unit_cube \ x \ i = 1 \ label x i = 1" + "\x. \i\Basis. x \ unit_cube \ label x i = 0 \ x \ i \ f x \ i" + "\x. \i\Basis. x \ unit_cube \ label x i = 1 \ f x \ i \ x \ i" + using kuhn_labelling_lemma[OF *] by auto note label = this [rule_format] have lem1: "\x\unit_cube. \y\unit_cube. \i\Basis. label x i \ label y i \ \f x \ i - x \ i\ \ norm (f y - f x) + norm (y - x)" proof safe fix x y :: 'a - assume x: "x \ unit_cube" - assume y: "y \ unit_cube" + assume x: "x \ unit_cube" and y: "y \ unit_cube" fix i assume i: "label x i \ label y i" "i \ Basis" have *: "\x y fx fy :: real. x \ fx \ fy \ y \ fx \ x \ y \ fy \ \fx - x\ \ \fy - fx\ + \y - x\" by auto have "\(f x - x) \ i\ \ \(f y - f x)\i\ + \(y - x)\i\" - unfolding inner_simps - apply (rule *) - apply (cases "label x i = 0") - apply (rule disjI1) - apply rule - prefer 3 - apply (rule disjI2) - apply rule - proof - - assume lx: "label x i = 0" - then have ly: "label y i = 1" - using i label(1)[of i y] - by auto - show "x \ i \ f x \ i" - apply (rule label(4)[rule_format]) - using x y lx i(2) - apply auto - done - show "f y \ i \ y \ i" - apply (rule label(5)[rule_format]) - using x y ly i(2) - apply auto - done + proof (cases "label x i = 0") + case True + then have fxy: "\ f y \ i \ y \ i \ f x \ i \ x \ i" + by (metis True i label(1) label(5) le_antisym less_one not_le_imp_less y) + show ?thesis + unfolding inner_simps + by (rule *) (auto simp: True i label x y fxy) next - assume "label x i \ 0" - then have l: "label x i = 1" "label y i = 0" - using i label(1)[of i x] label(1)[of i y] - by auto - show "f x \ i \ x \ i" - apply (rule label(5)[rule_format]) - using x y l i(2) - apply auto - done - show "y \ i \ f y \ i" - apply (rule label(4)[rule_format]) - using x y l i(2) - apply auto - done + case False + then show ?thesis + using label [OF \i \ Basis\] i(1) x y + apply (auto simp: inner_diff_left le_Suc_eq) + by (metis "*") qed also have "\ \ norm (f y - f x) + norm (y - x)" - apply (rule add_mono) - apply (rule Basis_le_norm[OF i(2)])+ - done + by (simp add: add_mono i(2) norm_bound_Basis_le) finally show "\f x \ i - x \ i\ \ norm (f y - f x) + norm (y - x)" unfolding inner_simps . qed have "\e>0. \x\unit_cube. \y\unit_cube. \z\unit_cube. \i\Basis. - norm (x - z) < e \ norm (y - z) < e \ label x i \ label y i \ + norm (x - z) < e \ norm (y - z) < e \ label x i \ label y i \ \(f(z) - z)\i\ < d / (real n)" proof - have d': "d / real n / 8 > 0" @@ -1530,9 +1494,7 @@ unfolding dist_norm by blast show ?thesis - apply (rule_tac x="min (e/2) (d/real n/8)" in exI) - apply safe - proof - + proof (intro exI conjI ballI impI) show "0 < min (e / 2) (d / real n / 8)" using d' e by auto fix x y z i @@ -1551,10 +1513,9 @@ unfolding inner_simps proof (rule *) show "\f x \ i - x \ i\ \ norm (f y -f x) + norm (y - x)" - apply (rule lem1[rule_format]) - using as i - apply auto - done + using as(1) as(2) as(6) i lem1 by blast + show "norm (f x - f z) < d / real n / 8" + using d' e as by auto show "\f x \ i - f z \ i\ \ norm (f x - f z)" "\x \ i - z \ i\ \ norm (x - z)" unfolding inner_diff_left[symmetric] by (rule Basis_le_norm[OF i])+ @@ -1563,30 +1524,14 @@ unfolding norm_minus_commute by auto also have "\ < e / 2 + e / 2" - apply (rule add_strict_mono) - using as(4,5) - apply auto - done + using as(4) as(5) by auto finally show "norm (f y - f x) < d / real n / 8" - apply - - apply (rule e(2)) - using as - apply auto - done + using as(1) as(2) e(2) by auto have "norm (y - z) + norm (x - z) < d / real n / 8 + d / real n / 8" - apply (rule add_strict_mono) - using as - apply auto - done - then show "norm (y - x) < 2 * (d / real n / 8)" - using tria + using as(4) as(5) by auto + with tria show "norm (y - x) < 2 * (d / real n / 8)" by auto - show "norm (f x - f z) < d / real n / 8" - apply (rule e(2)) - using as e(1) - apply auto - done - qed (insert as, auto) + qed (use as in auto) qed qed then @@ -1635,14 +1580,14 @@ { fix x :: "nat \ nat" and i assume "\i p" "i < n" "x i = p \ x i = 0" then have "(\i\Basis. (real (x (b' i)) / real p) *\<^sub>R i) \ (unit_cube::'a set)" using b'_Basis - by (auto simp add: mem_unit_cube inner_simps bij_betw_def zero_le_divide_iff divide_le_eq_1) } + by (auto simp: mem_unit_cube inner_simps bij_betw_def zero_le_divide_iff divide_le_eq_1) } note cube = this have q2: "\x. (\i p) \ (\i (label (\i\Basis. (real (x (b' i)) / real p) *\<^sub>R i) \ b) i = 0)" - unfolding o_def using cube \p > 0\ by (intro allI impI label(2)) (auto simp add: b'') + unfolding o_def using cube \p > 0\ by (intro allI impI label(2)) (auto simp: b'') have q3: "\x. (\i p) \ (\i (label (\i\Basis. (real (x (b' i)) / real p) *\<^sub>R i) \ b) i = 1)" - using cube \p > 0\ unfolding o_def by (intro allI impI label(3)) (auto simp add: b'') + using cube \p > 0\ unfolding o_def by (intro allI impI label(3)) (auto simp: b'') obtain q where q: "\ii unit_cube" unfolding z_def mem_unit_cube using b'_Basis - by (auto simp add: bij_betw_def zero_le_divide_iff divide_le_eq_1) + by (auto simp: bij_betw_def zero_le_divide_iff divide_le_eq_1) then have d_fz_z: "d \ norm (f z - z)" by (rule d) assume "\ ?thesis" then have as: "\i\Basis. \f z \ i - z \ i\ < d / real n" using \n > 0\ - by (auto simp add: not_le inner_diff) + by (auto simp: not_le inner_diff) have "norm (f z - z) \ (\i\Basis. \f z \ i - z \ i\)" unfolding inner_diff_left[symmetric] by (rule norm_le_l1) also have "\ < (\(i::'a) \ Basis. d / real n)" - apply (rule sum_strict_mono) - using as - apply auto - done + by (meson as finite_Basis nonempty_Basis sum_strict_mono) also have "\ = d" - using DIM_positive[where 'a='a] - by (auto simp: n_def) + using DIM_positive[where 'a='a] by (auto simp: n_def) finally show False using d_fz_z by auto qed @@ -1698,50 +1639,37 @@ apply (rule order_trans) apply (rule rs(1)[OF b'_im,THEN conjunct2]) using q(1)[rule_format,OF b'_im] - apply (auto simp add: Suc_le_eq) + apply (auto simp: Suc_le_eq) done then have "r' \ unit_cube" unfolding r'_def mem_unit_cube using b'_Basis - by (auto simp add: bij_betw_def zero_le_divide_iff divide_le_eq_1) + by (auto simp: bij_betw_def zero_le_divide_iff divide_le_eq_1) define s' :: 'a where "s' = (\i\Basis. (real (s (b' i)) / real p) *\<^sub>R i)" have "\i. i \ Basis \ s (b' i) \ p" - apply (rule order_trans) - apply (rule rs(2)[OF b'_im, THEN conjunct2]) - using q(1)[rule_format,OF b'_im] - apply (auto simp add: Suc_le_eq) - done + using b'_im q(1) rs(2) by fastforce then have "s' \ unit_cube" unfolding s'_def mem_unit_cube - using b'_Basis - by (auto simp add: bij_betw_def zero_le_divide_iff divide_le_eq_1) + using b'_Basis by (auto simp: bij_betw_def zero_le_divide_iff divide_le_eq_1) have "z \ unit_cube" unfolding z_def mem_unit_cube using b'_Basis q(1)[rule_format,OF b'_im] \p > 0\ - by (auto simp add: bij_betw_def zero_le_divide_iff divide_le_eq_1 less_imp_le) - have *: "\x. 1 + real x = real (Suc x)" - by auto + by (auto simp: bij_betw_def zero_le_divide_iff divide_le_eq_1 less_imp_le) { have "(\i\Basis. \real (r (b' i)) - real (q (b' i))\) \ (\(i::'a)\Basis. 1)" - apply (rule sum_mono) - using rs(1)[OF b'_im] - apply (auto simp add:* field_simps simp del: of_nat_Suc) - done + by (rule sum_mono) (use rs(1)[OF b'_im] in force) also have "\ < e * real p" using p \e > 0\ \p > 0\ - by (auto simp add: field_simps n_def) + by (auto simp: field_simps n_def) finally have "(\i\Basis. \real (r (b' i)) - real (q (b' i))\) < e * real p" . } moreover { have "(\i\Basis. \real (s (b' i)) - real (q (b' i))\) \ (\(i::'a)\Basis. 1)" - apply (rule sum_mono) - using rs(2)[OF b'_im] - apply (auto simp add:* field_simps simp del: of_nat_Suc) - done + by (rule sum_mono) (use rs(2)[OF b'_im] in force) also have "\ < e * real p" using p \e > 0\ \p > 0\ - by (auto simp add: field_simps n_def) + by (auto simp: field_simps n_def) finally have "(\i\Basis. \real (s (b' i)) - real (q (b' i))\) < e * real p" . } ultimately @@ -1749,7 +1677,7 @@ unfolding r'_def s'_def z_def using \p > 0\ apply (rule_tac[!] le_less_trans[OF norm_le_l1]) - apply (auto simp add: field_simps sum_divide_distrib[symmetric] inner_diff_left) + apply (auto simp: field_simps sum_divide_distrib[symmetric] inner_diff_left) done then have "\(f z - z) \ i\ < d / real n" using rs(3) i @@ -1762,121 +1690,100 @@ subsection \Retractions\ -definition "retraction s t r \ t \ s \ continuous_on s r \ r ` s \ t \ (\x\t. r x = x)" +definition "retraction S T r \ T \ S \ continuous_on S r \ r ` S \ T \ (\x\T. r x = x)" definition retract_of (infixl "retract'_of" 50) - where "(t retract_of s) \ (\r. retraction s t r)" - -lemma retraction_idempotent: "retraction s t r \ x \ s \ r (r x) = r x" + where "(T retract_of S) \ (\r. retraction S T r)" + +lemma retraction_idempotent: "retraction S T r \ x \ S \ r (r x) = r x" unfolding retraction_def by auto subsection \Preservation of fixpoints under (more general notion of) retraction\ lemma invertible_fixpoint_property: - fixes s :: "'a::euclidean_space set" - and t :: "'b::euclidean_space set" - assumes "continuous_on t i" - and "i ` t \ s" - and "continuous_on s r" - and "r ` s \ t" - and "\y\t. r (i y) = y" - and "\f. continuous_on s f \ f ` s \ s \ (\x\s. f x = x)" - and "continuous_on t g" - and "g ` t \ t" - obtains y where "y \ t" and "g y = y" + fixes S :: "'a::euclidean_space set" + and T :: "'b::euclidean_space set" + assumes contt: "continuous_on T i" + and "i ` T \ S" + and contr: "continuous_on S r" + and "r ` S \ T" + and ri: "\y. y \ T \ r (i y) = y" + and FP: "\f. \continuous_on S f; f ` S \ S\ \ \x\S. f x = x" + and contg: "continuous_on T g" + and "g ` T \ T" + obtains y where "y \ T" and "g y = y" proof - - have "\x\s. (i \ g \ r) x = x" - apply (rule assms(6)[rule_format]) - apply rule - apply (rule continuous_on_compose assms)+ - apply ((rule continuous_on_subset)?, rule assms)+ - using assms(2,4,8) - apply auto - apply blast - done - then obtain x where x: "x \ s" "(i \ g \ r) x = x" .. - then have *: "g (r x) \ t" + have "\x\S. (i \ g \ r) x = x" + proof (rule FP) + show "continuous_on S (i \ g \ r)" + by (meson contt contr assms(4) contg assms(8) continuous_on_compose continuous_on_subset) + show "(i \ g \ r) ` S \ S" + using assms(2,4,8) by force + qed + then obtain x where x: "x \ S" "(i \ g \ r) x = x" .. + then have *: "g (r x) \ T" using assms(4,8) by auto have "r ((i \ g \ r) x) = r x" using x by auto then show ?thesis - apply (rule_tac that[of "r x"]) - using x - unfolding o_def - unfolding assms(5)[rule_format,OF *] - using assms(4) - apply auto - done + using "*" ri that by auto qed lemma homeomorphic_fixpoint_property: - fixes s :: "'a::euclidean_space set" - and t :: "'b::euclidean_space set" - assumes "s homeomorphic t" - shows "(\f. continuous_on s f \ f ` s \ s \ (\x\s. f x = x)) \ - (\g. continuous_on t g \ g ` t \ t \ (\y\t. g y = y))" + fixes S :: "'a::euclidean_space set" + and T :: "'b::euclidean_space set" + assumes "S homeomorphic T" + shows "(\f. continuous_on S f \ f ` S \ S \ (\x\S. f x = x)) \ + (\g. continuous_on T g \ g ` T \ T \ (\y\T. g y = y))" + (is "?lhs = ?rhs") proof - - obtain r i where - "\x\s. i (r x) = x" - "r ` s = t" - "continuous_on s r" - "\y\t. r (i y) = y" - "i ` t = s" - "continuous_on t i" - using assms - unfolding homeomorphic_def homeomorphism_def - by blast - then show ?thesis - apply - - apply rule - apply (rule_tac[!] allI impI)+ - apply (rule_tac g=g in invertible_fixpoint_property[of t i s r]) - prefer 10 - apply (rule_tac g=f in invertible_fixpoint_property[of s r t i]) - apply auto - done + obtain r i where r: + "\x\S. i (r x) = x" "r ` S = T" "continuous_on S r" + "\y\T. r (i y) = y" "i ` T = S" "continuous_on T i" + using assms unfolding homeomorphic_def homeomorphism_def by blast + show ?thesis + proof + assume ?lhs + with r show ?rhs + by (metis invertible_fixpoint_property[of T i S r] order_refl) + next + assume ?rhs + with r show ?lhs + by (metis invertible_fixpoint_property[of S r T i] order_refl) + qed qed lemma retract_fixpoint_property: fixes f :: "'a::euclidean_space \ 'b::euclidean_space" - and s :: "'a set" - assumes "t retract_of s" - and "\f. continuous_on s f \ f ` s \ s \ (\x\s. f x = x)" - and "continuous_on t g" - and "g ` t \ t" - obtains y where "y \ t" and "g y = y" + and S :: "'a set" + assumes "T retract_of S" + and FP: "\f. \continuous_on S f; f ` S \ S\ \ \x\S. f x = x" + and contg: "continuous_on T g" + and "g ` T \ T" + obtains y where "y \ T" and "g y = y" proof - - obtain h where "retraction s t h" + obtain h where "retraction S T h" using assms(1) unfolding retract_of_def .. then show ?thesis unfolding retraction_def - apply - - apply (rule invertible_fixpoint_property[OF continuous_on_id _ _ _ _ assms(2), of t h g]) - prefer 7 - apply (rule_tac y = y in that) - using assms - apply auto - done + using invertible_fixpoint_property[OF continuous_on_id _ _ _ _ FP] + by (metis assms(4) contg image_ident that) qed subsection \The Brouwer theorem for any set with nonempty interior\ lemma convex_unit_cube: "convex unit_cube" - apply (rule is_interval_convex) - apply (clarsimp simp add: is_interval_def mem_unit_cube) - apply (drule (1) bspec)+ - apply auto - done + by (rule is_interval_convex) (fastforce simp add: is_interval_def mem_unit_cube) lemma brouwer_weak: fixes f :: "'a::euclidean_space \ 'a" - assumes "compact s" - and "convex s" - and "interior s \ {}" - and "continuous_on s f" - and "f ` s \ s" - obtains x where "x \ s" and "f x = x" + assumes "compact S" + and "convex S" + and "interior S \ {}" + and "continuous_on S f" + and "f ` S \ S" + obtains x where "x \ S" and "f x = x" proof - let ?U = "unit_cube :: 'a set" have "\Basis /\<^sub>R 2 \ interior ?U" @@ -1890,7 +1797,7 @@ unfolding unit_cube_def by force qed then have *: "interior ?U \ {}" by fast - have *: "?U homeomorphic s" + have *: "?U homeomorphic S" using homeomorphic_convex_compact[OF convex_unit_cube compact_unit_cube * assms(2,1,3)] . have "\f. continuous_on ?U f \ f ` ?U \ ?U \ (\x\?U. f x = x)" @@ -1898,7 +1805,7 @@ then show ?thesis unfolding homeomorphic_fixpoint_property[OF *] using assms - by (auto simp: intro: that) + by (auto intro: that) qed @@ -1920,49 +1827,37 @@ lemma brouwer: fixes f :: "'a::euclidean_space \ 'a" - assumes "compact s" - and "convex s" - and "s \ {}" - and "continuous_on s f" - and "f ` s \ s" - obtains x where "x \ s" and "f x = x" + assumes S: "compact S" "convex S" "S \ {}" + and contf: "continuous_on S f" + and fim: "f ` S \ S" + obtains x where "x \ S" and "f x = x" proof - - have "\e>0. s \ cball 0 e" - using compact_imp_bounded[OF assms(1)] - unfolding bounded_pos - apply (erule_tac exE) - apply (rule_tac x=b in exI) - apply (auto simp add: dist_norm) - done - then obtain e where e: "e > 0" "s \ cball 0 e" + have "\e>0. S \ cball 0 e" + using compact_imp_bounded[OF \compact S\] unfolding bounded_pos + by auto + then obtain e where e: "e > 0" "S \ cball 0 e" by blast - have "\x\ cball 0 e. (f \ closest_point s) x = x" - apply (rule_tac brouwer_ball[OF e(1), of 0 "f \ closest_point s"]) - apply (rule continuous_on_compose ) - apply (rule continuous_on_closest_point[OF assms(2) compact_imp_closed[OF assms(1)] assms(3)]) - apply (rule continuous_on_subset[OF assms(4)]) - apply (insert closest_point_in_set[OF compact_imp_closed[OF assms(1)] assms(3)]) - using assms(5)[unfolded subset_eq] - using e(2)[unfolded subset_eq mem_cball] - apply (auto simp add: dist_norm) - done - then obtain x where x: "x \ cball 0 e" "(f \ closest_point s) x = x" .. - have *: "closest_point s x = x" - apply (rule closest_point_self) - apply (rule assms(5)[unfolded subset_eq,THEN bspec[where x="x"], unfolded image_iff]) - apply (rule_tac x="closest_point s x" in bexI) - using x - unfolding o_def - using closest_point_in_set[OF compact_imp_closed[OF assms(1)] assms(3), of x] - apply auto - done + have "\x\ cball 0 e. (f \ closest_point S) x = x" + proof (rule_tac brouwer_ball[OF e(1)]) + show "continuous_on (cball 0 e) (f \ closest_point S)" + apply (rule continuous_on_compose) + using S compact_eq_bounded_closed continuous_on_closest_point apply blast + by (meson S contf closest_point_in_set compact_imp_closed continuous_on_subset image_subsetI) + show "(f \ closest_point S) ` cball 0 e \ cball 0 e" + by clarsimp (metis S fim closest_point_exists(1) compact_eq_bounded_closed e(2) image_subset_iff mem_cball_0 subsetCE) + qed (use assms in auto) + then obtain x where x: "x \ cball 0 e" "(f \ closest_point S) x = x" .. + have "x \ S" + by (metis closest_point_in_set comp_apply compact_imp_closed fim image_eqI S(1) S(3) subset_iff x(2)) + then have *: "closest_point S x = x" + by (rule closest_point_self) show thesis - apply (rule_tac x="closest_point s x" in that) - unfolding x(2)[unfolded o_def] - apply (rule closest_point_in_set[OF compact_imp_closed[OF assms(1)] assms(3)]) - using * - apply auto - done + proof + show "closest_point S x \ S" + by (simp add: "*" \x \ S\) + show "f (closest_point S x) = closest_point S x" + using "*" x(2) by auto + qed qed text \So we get the no-retraction theorem.\ @@ -1975,17 +1870,15 @@ assume *: "frontier (cball a e) retract_of (cball a e)" have **: "\xa. a - (2 *\<^sub>R a - xa) = - (a - xa)" using scaleR_left_distrib[of 1 1 a] by auto - obtain x where x: - "x \ {x. norm (a - x) = e}" - "2 *\<^sub>R a - x = x" - apply (rule retract_fixpoint_property[OF *, of "\x. scaleR 2 a - x"]) - apply (blast intro: brouwer_ball[OF assms]) - apply (intro continuous_intros) - unfolding frontier_cball subset_eq Ball_def image_iff dist_norm sphere_def - apply (auto simp add: ** norm_minus_commute) - done + obtain x where x: "x \ {x. norm (a - x) = e}" "2 *\<^sub>R a - x = x" + proof (rule retract_fixpoint_property[OF *, of "\x. scaleR 2 a - x"]) + show "continuous_on (frontier (cball a e)) ((-) (2 *\<^sub>R a))" + by (intro continuous_intros) + show "(-) (2 *\<^sub>R a) ` frontier (cball a e) \ frontier (cball a e)" + by clarsimp (metis "**" dist_norm norm_minus_cancel) + qed (auto simp: dist_norm intro: brouwer_ball[OF assms]) then have "scaleR 2 a = scaleR 1 x + scaleR 1 x" - by (auto simp add: algebra_simps) + by (auto simp: algebra_simps) then have "a = x" unfolding scaleR_left_distrib[symmetric] by auto @@ -2006,11 +1899,7 @@ case False then show ?thesis unfolding contractible_def nullhomotopic_from_sphere_extension - apply (simp add: not_less) - apply (rule_tac x=id in exI) - apply (auto simp: continuous_on_def) - apply (meson dist_not_less_zero le_less less_le_trans) - done + using continuous_on_const less_eq_real_def by auto qed lemma connected_sphere_eq: @@ -2035,9 +1924,8 @@ by (metis dist_self greater insertI1 less_add_same_cancel1 mem_sphere mult_2 not_le zero_le_dist) then have "finite (sphere a r)" by auto - with L \r > 0\ show "False" - apply (auto simp: connected_finite_iff_sing) - using xy by auto + with L \r > 0\ xy show "False" + using connected_finite_iff_sing by auto qed with greater show ?rhs by (metis DIM_ge_Suc0 One_nat_def Suc_1 le_antisym not_less_eq_eq) @@ -2098,12 +1986,10 @@ unfolding retraction_def proof (intro conjI ballI) show "frontier (cball a B) \ cball a B" - by (force simp:) + by force show "continuous_on (cball a B) h" unfolding h_def - apply (intro continuous_intros) - using contg continuous_on_subset notga apply auto - done + by (intro continuous_intros) (use contg continuous_on_subset notga in auto) show "h ` cball a B \ frontier (cball a B)" using \0 < B\ by (auto simp: h_def notga dist_norm) show "\x. x \ frontier (cball a B) \ h x = x" @@ -2117,76 +2003,76 @@ subsection\More Properties of Retractions\ lemma retraction: - "retraction s t r \ - t \ s \ continuous_on s r \ r ` s = t \ (\x \ t. r x = x)" + "retraction S T r \ + T \ S \ continuous_on S r \ r ` S = T \ (\x \ T. r x = x)" by (force simp: retraction_def) lemma retract_of_imp_extensible: - assumes "s retract_of t" and "continuous_on s f" and "f ` s \ u" - obtains g where "continuous_on t g" "g ` t \ u" "\x. x \ s \ g x = f x" + assumes "S retract_of T" and "continuous_on S f" and "f ` S \ U" + obtains g where "continuous_on T g" "g ` T \ U" "\x. x \ S \ g x = f x" using assms apply (clarsimp simp add: retract_of_def retraction) -apply (rule_tac g = "f o r" in that) +apply (rule_tac g = "f \ r" in that) apply (auto simp: continuous_on_compose2) done lemma idempotent_imp_retraction: - assumes "continuous_on s f" and "f ` s \ s" and "\x. x \ s \ f(f x) = f x" - shows "retraction s (f ` s) f" + assumes "continuous_on S f" and "f ` S \ S" and "\x. x \ S \ f(f x) = f x" + shows "retraction S (f ` S) f" by (simp add: assms retraction) lemma retraction_subset: - assumes "retraction s t r" and "t \ s'" and "s' \ s" - shows "retraction s' t r" -apply (simp add: retraction_def) -by (metis assms continuous_on_subset image_mono retraction) + assumes "retraction S T r" and "T \ s'" and "s' \ S" + shows "retraction s' T r" + unfolding retraction_def + by (metis assms continuous_on_subset image_mono retraction) lemma retract_of_subset: - assumes "t retract_of s" and "t \ s'" and "s' \ s" - shows "t retract_of s'" + assumes "T retract_of S" and "T \ s'" and "s' \ S" + shows "T retract_of s'" by (meson assms retract_of_def retraction_subset) -lemma retraction_refl [simp]: "retraction s s (\x. x)" +lemma retraction_refl [simp]: "retraction S S (\x. x)" by (simp add: continuous_on_id retraction) -lemma retract_of_refl [iff]: "s retract_of s" +lemma retract_of_refl [iff]: "S retract_of S" using continuous_on_id retract_of_def retraction_def by fastforce lemma retract_of_imp_subset: - "s retract_of t \ s \ t" + "S retract_of T \ S \ T" by (simp add: retract_of_def retraction_def) lemma retract_of_empty [simp]: - "({} retract_of s) \ s = {}" "(s retract_of {}) \ s = {}" + "({} retract_of S) \ S = {}" "(S retract_of {}) \ S = {}" by (auto simp: retract_of_def retraction_def) -lemma retract_of_singleton [iff]: "({x} retract_of s) \ x \ s" +lemma retract_of_singleton [iff]: "({x} retract_of S) \ x \ S" using continuous_on_const by (auto simp: retract_of_def retraction_def) lemma retraction_comp: - "\retraction s t f; retraction t u g\ - \ retraction s u (g o f)" + "\retraction S T f; retraction T U g\ + \ retraction S U (g \ f)" apply (auto simp: retraction_def intro: continuous_on_compose2) by blast lemma retract_of_trans [trans]: - assumes "s retract_of t" and "t retract_of u" - shows "s retract_of u" + assumes "S retract_of T" and "T retract_of U" + shows "S retract_of U" using assms by (auto simp: retract_of_def intro: retraction_comp) lemma closedin_retract: - fixes s :: "'a :: real_normed_vector set" - assumes "s retract_of t" - shows "closedin (subtopology euclidean t) s" + fixes S :: "'a :: real_normed_vector set" + assumes "S retract_of T" + shows "closedin (subtopology euclidean T) S" proof - - obtain r where "s \ t" "continuous_on t r" "r ` t \ s" "\x. x \ s \ r x = x" + obtain r where "S \ T" "continuous_on T r" "r ` T \ S" "\x. x \ S \ r x = x" using assms by (auto simp: retract_of_def retraction_def) - then have s: "s = {x \ t. (norm(r x - x)) = 0}" by auto + then have S: "S = {x \ T. (norm(r x - x)) = 0}" by auto show ?thesis - apply (subst s) + apply (subst S) apply (rule continuous_closedin_preimage_constant) - by (simp add: \continuous_on t r\ continuous_on_diff continuous_on_id continuous_on_norm) + by (simp add: \continuous_on T r\ continuous_on_diff continuous_on_id continuous_on_norm) qed lemma closedin_self [simp]: @@ -2195,52 +2081,52 @@ by (simp add: closedin_retract) lemma retract_of_contractible: - assumes "contractible t" "s retract_of t" - shows "contractible s" + assumes "contractible T" "S retract_of T" + shows "contractible S" using assms apply (clarsimp simp add: retract_of_def contractible_def retraction_def homotopic_with) apply (rule_tac x="r a" in exI) -apply (rule_tac x="r o h" in exI) +apply (rule_tac x="r \ h" in exI) apply (intro conjI continuous_intros continuous_on_compose) apply (erule continuous_on_subset | force)+ done lemma retract_of_compact: - "\compact t; s retract_of t\ \ compact s" + "\compact T; S retract_of T\ \ compact S" by (metis compact_continuous_image retract_of_def retraction) lemma retract_of_closed: - fixes s :: "'a :: real_normed_vector set" - shows "\closed t; s retract_of t\ \ closed s" + fixes S :: "'a :: real_normed_vector set" + shows "\closed T; S retract_of T\ \ closed S" by (metis closedin_retract closedin_closed_eq) lemma retract_of_connected: - "\connected t; s retract_of t\ \ connected s" + "\connected T; S retract_of T\ \ connected S" by (metis Topological_Spaces.connected_continuous_image retract_of_def retraction) lemma retract_of_path_connected: - "\path_connected t; s retract_of t\ \ path_connected s" + "\path_connected T; S retract_of T\ \ path_connected S" by (metis path_connected_continuous_image retract_of_def retraction) lemma retract_of_simply_connected: - "\simply_connected t; s retract_of t\ \ simply_connected s" + "\simply_connected T; S retract_of T\ \ simply_connected S" apply (simp add: retract_of_def retraction_def, clarify) apply (rule simply_connected_retraction_gen) apply (force simp: continuous_on_id elim!: continuous_on_subset)+ done lemma retract_of_homotopically_trivial: - assumes ts: "t retract_of s" - and hom: "\f g. \continuous_on u f; f ` u \ s; - continuous_on u g; g ` u \ s\ - \ homotopic_with (\x. True) u s f g" - and "continuous_on u f" "f ` u \ t" - and "continuous_on u g" "g ` u \ t" - shows "homotopic_with (\x. True) u t f g" + assumes ts: "T retract_of S" + and hom: "\f g. \continuous_on U f; f ` U \ S; + continuous_on U g; g ` U \ S\ + \ homotopic_with (\x. True) U S f g" + and "continuous_on U f" "f ` U \ T" + and "continuous_on U g" "g ` U \ T" + shows "homotopic_with (\x. True) U T f g" proof - - obtain r where "r ` s \ s" "continuous_on s r" "\x\s. r (r x) = r x" "t = r ` s" + obtain r where "r ` S \ S" "continuous_on S r" "\x\S. r (r x) = r x" "T = r ` S" using ts by (auto simp: retract_of_def retraction) - then obtain k where "Retracts s r t k" + then obtain k where "Retracts S r T k" unfolding Retracts_def by (metis continuous_on_subset dual_order.trans image_iff image_mono) then show ?thesis @@ -2251,15 +2137,15 @@ qed lemma retract_of_homotopically_trivial_null: - assumes ts: "t retract_of s" - and hom: "\f. \continuous_on u f; f ` u \ s\ - \ \c. homotopic_with (\x. True) u s f (\x. c)" - and "continuous_on u f" "f ` u \ t" - obtains c where "homotopic_with (\x. True) u t f (\x. c)" + assumes ts: "T retract_of S" + and hom: "\f. \continuous_on U f; f ` U \ S\ + \ \c. homotopic_with (\x. True) U S f (\x. c)" + and "continuous_on U f" "f ` U \ T" + obtains c where "homotopic_with (\x. True) U T f (\x. c)" proof - - obtain r where "r ` s \ s" "continuous_on s r" "\x\s. r (r x) = r x" "t = r ` s" + obtain r where "r ` S \ S" "continuous_on S r" "\x\S. r (r x) = r x" "T = r ` S" using ts by (auto simp: retract_of_def retraction) - then obtain k where "Retracts s r t k" + then obtain k where "Retracts S r T k" unfolding Retracts_def by (metis continuous_on_subset dual_order.trans image_iff image_mono) then show ?thesis @@ -2269,35 +2155,34 @@ qed lemma retraction_imp_quotient_map: - "retraction s t r - \ u \ t - \ (openin (subtopology euclidean s) (s \ r -` u) \ - openin (subtopology euclidean t) u)" + "retraction S T r + \ U \ T + \ (openin (subtopology euclidean S) (S \ r -` U) \ + openin (subtopology euclidean T) U)" apply (clarsimp simp add: retraction) apply (rule continuous_right_inverse_imp_quotient_map [where g=r]) apply (auto simp: elim: continuous_on_subset) done lemma retract_of_locally_compact: - fixes s :: "'a :: {heine_borel,real_normed_vector} set" - shows "\ locally compact s; t retract_of s\ \ locally compact t" + fixes S :: "'a :: {heine_borel,real_normed_vector} set" + shows "\ locally compact S; T retract_of S\ \ locally compact T" by (metis locally_compact_closedin closedin_retract) lemma retract_of_Times: - "\s retract_of s'; t retract_of t'\ \ (s \ t) retract_of (s' \ t')" + "\S retract_of s'; T retract_of t'\ \ (S \ T) retract_of (s' \ t')" apply (simp add: retract_of_def retraction_def Sigma_mono, clarify) apply (rename_tac f g) -apply (rule_tac x="\z. ((f o fst) z, (g o snd) z)" in exI) +apply (rule_tac x="\z. ((f \ fst) z, (g \ snd) z)" in exI) apply (rule conjI continuous_intros | erule continuous_on_subset | force)+ done lemma homotopic_into_retract: - "\f ` s \ t; g ` s \ t; t retract_of u; - homotopic_with (\x. True) s u f g\ - \ homotopic_with (\x. True) s t f g" + "\f ` S \ T; g ` S \ T; T retract_of U; homotopic_with (\x. True) S U f g\ + \ homotopic_with (\x. True) S T f g" apply (subst (asm) homotopic_with_def) apply (simp add: homotopic_with retract_of_def retraction_def, clarify) -apply (rule_tac x="r o h" in exI) +apply (rule_tac x="r \ h" in exI) apply (rule conjI continuous_intros | erule continuous_on_subset | force simp: image_subset_iff)+ done @@ -2317,15 +2202,19 @@ lemma deformation_retract_imp_homotopy_eqv: fixes S :: "'a::euclidean_space set" - assumes "homotopic_with (\x. True) S S id r" "retraction S T r" - shows "S homotopy_eqv T" - apply (simp add: homotopy_eqv_def) - apply (rule_tac x=r in exI) - using assms apply (simp add: retraction_def) - apply (rule_tac x=id in exI) - apply (auto simp: continuous_on_id) - apply (metis homotopic_with_symD) - by (metis continuous_on_id' homotopic_with_equal homotopic_with_symD id_apply image_id subset_refl) + assumes "homotopic_with (\x. True) S S id r" and r: "retraction S T r" + shows "S homotopy_eqv T" +proof - + have "homotopic_with (\x. True) S S (id \ r) id" + by (simp add: assms(1) homotopic_with_symD) + moreover have "homotopic_with (\x. True) T T (r \ id) id" + using r unfolding retraction_def + by (metis (no_types, lifting) comp_id continuous_on_id' homotopic_with_equal homotopic_with_symD id_def image_id order_refl) + ultimately + show ?thesis + unfolding homotopy_eqv_def + by (metis continuous_on_id' id_def image_id r retraction_def) +qed lemma deformation_retract: fixes S :: "'a::euclidean_space set" @@ -2356,10 +2245,8 @@ have "{a} retract_of S" by (simp add: \a \ S\) moreover have "homotopic_with (\x. True) S S id (\x. a)" - using assms - apply (clarsimp simp add: contractible_def) - apply (rule homotopic_with_trans, assumption) - by (metis assms(1) contractible_imp_path_connected homotopic_constant_maps homotopic_with_sym homotopic_with_trans insert_absorb insert_not_empty path_component_mem(1) path_connected_component) + using assms + by (auto simp: contractible_def continuous_on_const continuous_on_id homotopic_into_contractible image_subset_iff) moreover have "(\x. a) ` S \ {a}" by (simp add: image_subsetI) ultimately show ?thesis @@ -2382,15 +2269,12 @@ using assms by auto (metis imageI subset_iff) have contp': "continuous_on S p" by (rule continuous_on_subset [OF contp \S \ T\]) - have "continuous_on T (q \ p)" - apply (rule continuous_on_compose [OF contp]) - apply (simp add: *) - apply (rule continuous_on_inv [OF contp' \compact S\]) - using assms by auto + have "continuous_on (p ` T) q" + by (simp add: "*" assms(1) assms(2) assms(5) continuous_on_inv contp' rev_subsetD) + then have "continuous_on T (q \ p)" + by (rule continuous_on_compose [OF contp]) then show ?thesis - apply (rule continuous_on_eq [of _ "q o p"]) - apply (simp add: o_def) - done + by (rule continuous_on_eq [of _ "q \ p"]) (simp add: o_def) qed lemma continuous_on_compact_surface_projection: @@ -2441,21 +2325,19 @@ have aaffS: "a \ affine hull S" by (meson arelS subsetD hull_inc rel_interior_subset) have "((\z. z - a) ` (affine hull S - {a})) = ((\z. z - a) ` (affine hull S)) - {0}" - by (auto simp: ) + by auto moreover have "continuous_on (((\z. z - a) ` (affine hull S)) - {0}) (\x. dd x *\<^sub>R x)" proof (rule continuous_on_compact_surface_projection) show "compact (rel_frontier ((\z. z - a) ` S))" by (simp add: \bounded S\ bounded_translation_minus compact_rel_frontier_bounded) have releq: "rel_frontier ((\z. z - a) ` S) = (\z. z - a) ` rel_frontier S" using rel_frontier_translation [of "-a"] add.commute by simp - also have "... \ (\z. z - a) ` (affine hull S) - {0}" + also have "\ \ (\z. z - a) ` (affine hull S) - {0}" using rel_frontier_affine_hull arelS rel_frontier_def by fastforce finally show "rel_frontier ((\z. z - a) ` S) \ (\z. z - a) ` (affine hull S) - {0}" . show "cone ((\z. z - a) ` (affine hull S))" - apply (rule subspace_imp_cone) - using aaffS - apply (simp add: subspace_affine image_comp o_def affine_translation_aux [of a]) - done + by (rule subspace_imp_cone) + (use aaffS in \simp add: subspace_affine image_comp o_def affine_translation_aux [of a]\) show "(0 < k \ k *\<^sub>R x \ rel_frontier ((\z. z - a) ` S)) \ (dd x = k)" if x: "x \ (\z. z - a) ` (affine hull S) - {0}" for k x proof @@ -2471,7 +2353,7 @@ then have segsub: "open_segment a (a + k *\<^sub>R x) \ rel_interior S" by (metis rel_interior_closure_convex_segment [OF \convex S\ arelS]) have "x \ 0" and xaffS: "a + x \ affine hull S" - using x by (auto simp: ) + using x by auto then have "0 < dd x" and inS: "a + dd x *\<^sub>R x \ rel_frontier S" using dd1 by auto moreover have "a + dd x *\<^sub>R x \ open_segment a (a + k *\<^sub>R x)" @@ -2483,7 +2365,7 @@ apply (metis (no_types) \k \ 0\ divide_inverse_commute inverse_eq_divide mult.left_commute right_inverse) done ultimately show ?thesis - using segsub by (auto simp add: rel_frontier_def) + using segsub by (auto simp: rel_frontier_def) qed moreover have False if "k < dd x" using x k that rel_frontier_def @@ -2497,7 +2379,7 @@ have "continuous_on (affine hull S - {a}) ((\x. a + dd x *\<^sub>R x) \ (\z. z - a))" by (intro * continuous_intros continuous_on_compose) with affS have contdd: "continuous_on (T - {a}) ((\x. a + dd x *\<^sub>R x) \ (\z. z - a))" - by (blast intro: continuous_on_subset elim: ) + by (blast intro: continuous_on_subset) show ?thesis proof show "homotopic_with (\x. True) (T - {a}) (T - {a}) id (\x. a + dd (x - a) *\<^sub>R (x - a))" @@ -2510,11 +2392,10 @@ if "x \ T - {a}" for x proof (clarsimp simp: in_segment, intro conjI) fix u::real assume u: "0 \ u" "u \ 1" - show "(1 - u) *\<^sub>R x + u *\<^sub>R (a + dd (x - a) *\<^sub>R (x - a)) \ T" - apply (rule convexD [OF \convex T\]) - using that u apply (auto simp add: ) - apply (metis add.commute affS dd1 diff_add_cancel eq_iff_diff_eq_0 relS subsetD) - done + have "a + dd (x - a) *\<^sub>R (x - a) \ T" + by (metis DiffD1 DiffD2 add.commute add.right_neutral affS dd1 diff_add_cancel relS singletonI subsetCE that) + then show "(1 - u) *\<^sub>R x + u *\<^sub>R (a + dd (x - a) *\<^sub>R (x - a)) \ T" + using convexD [OF \convex T\] that u by simp have iff: "(1 - u) *\<^sub>R x + u *\<^sub>R (a + d *\<^sub>R (x - a)) = a \ (1 - u + u * d) *\<^sub>R (x - a) = 0" for d by (auto simp: algebra_simps) @@ -2541,7 +2422,7 @@ show "a + dd (x - a) *\<^sub>R (x - a) = x" if x: "x \ rel_frontier S" for x proof - have "x \ a" - using that arelS by (auto simp add: rel_frontier_def) + using that arelS by (auto simp: rel_frontier_def) have False if "dd (x - a) < 1" proof - have "x \ closure S" @@ -2551,7 +2432,7 @@ have xaffS: "x \ affine hull S" using affS relS x by auto then have "0 < dd (x - a)" and inS: "a + dd (x - a) *\<^sub>R (x - a) \ rel_frontier S" - using dd1 by (auto simp add: \x \ a\) + using dd1 by (auto simp: \x \ a\) moreover have "a + dd (x - a) *\<^sub>R (x - a) \ open_segment a x" using \x \ a\ \0 < dd (x - a)\ apply (simp add: in_segment) @@ -2559,7 +2440,7 @@ apply (simp add: algebra_simps that) done ultimately show ?thesis - using segsub by (auto simp add: rel_frontier_def) + using segsub by (auto simp: rel_frontier_def) qed moreover have False if "1 < dd (x - a)" using x that dd2 [of "x - a" 1] \x \ a\ closure_affine_hull @@ -2578,7 +2459,7 @@ assumes "bounded S" "convex S" "a \ rel_interior S" shows "rel_frontier S retract_of (affine hull S - {a})" apply (rule rel_frontier_deformation_retract_of_punctured_convex [of S "affine hull S" a]) -apply (auto simp add: affine_imp_convex rel_frontier_affine_hull retract_of_def assms) +apply (auto simp: affine_imp_convex rel_frontier_affine_hull retract_of_def assms) done corollary rel_boundary_retract_of_punctured_affine_hull: @@ -2643,7 +2524,7 @@ using assms by (auto simp: path_component_def) then show ?thesis apply (simp add: path_def path_image_def pathstart_def pathfinish_def homotopic_with_def) - apply (rule_tac x = "\z. inverse(norm(snd z - (g o fst)z)) *\<^sub>R (snd z - (g o fst)z)" in exI) + apply (rule_tac x = "\z. inverse(norm(snd z - (g \ fst)z)) *\<^sub>R (snd z - (g \ fst)z)" in exI) apply (intro conjI continuous_intros) apply (rule continuous_intros | erule continuous_on_subset | fastforce simp: divide_simps sphere_def)+ done @@ -2767,7 +2648,7 @@ using hom by (force simp: homeomorphic_def) then have "continuous_on (f ` T) g" by (meson \f ` T \ S\ continuous_on_subset homeomorphism_def) - then have contgf: "continuous_on T (g o f)" + then have contgf: "continuous_on T (g \ f)" by (metis continuous_on_compose contf) have gfTC: "(g \ f) ` T \ C" proof - @@ -2779,7 +2660,7 @@ "\x. x \ T \ f' x = (g \ f) x" by (metis Dugundji [OF C cloUT contgf gfTC]) show ?thesis - proof (rule_tac g = "h o r o f'" in that) + proof (rule_tac g = "h \ r \ f'" in that) show "continuous_on U (h \ r \ f')" apply (intro continuous_on_compose f') using continuous_on_subset contr f' apply blast @@ -2811,7 +2692,7 @@ have [simp]: "S' \ U" using clo closedin_limpt by blast show ?thesis proof (simp add: retraction_def retract_of_def, intro exI conjI) - show "continuous_on U (g o h')" + show "continuous_on U (g \ h')" apply (intro continuous_on_compose h') apply (meson hom continuous_on_subset h' homeomorphism_cont1) done @@ -2853,7 +2734,7 @@ using clo closedin_imp_subset by auto show "T retract_of U" proof (simp add: retraction_def retract_of_def, intro exI conjI) - show "continuous_on U (g o h')" + show "continuous_on U (g \ h')" apply (intro continuous_on_compose h') apply (meson hom continuous_on_subset h' homeomorphism_cont1) done @@ -2919,7 +2800,7 @@ using hom by (force simp: homeomorphic_def) have "continuous_on (f ` T) g" by (meson \f ` T \ S\ continuous_on_subset homeomorphism_def homgh) - then have contgf: "continuous_on T (g o f)" + then have contgf: "continuous_on T (g \ f)" by (intro continuous_on_compose contf) have gfTC: "(g \ f) ` T \ C" proof - @@ -2933,7 +2814,7 @@ and eq: "\x. x \ T \ f' x = (g \ f) x" by (metis Dugundji [OF C cloUT contgf gfTC]) show ?thesis - proof (rule_tac V = "U \ f' -` D" and g = "h o r o f'" in that) + proof (rule_tac V = "U \ f' -` D" and g = "h \ r \ f'" in that) show "T \ U \ f' -` D" using cloUT closedin_imp_subset \S' \ D\ \f ` T \ S\ eq homeomorphism_image1 homgh by fastforce @@ -2976,7 +2857,7 @@ by (blast intro: ANR_imp_absolute_neighbourhood_extensor [OF \ANR S\ h clo]) have "S' retract_of V" proof (simp add: retraction_def retract_of_def, intro exI conjI \S' \ V\) - show "continuous_on V (g o h')" + show "continuous_on V (g \ h')" apply (intro continuous_on_compose h') apply (meson hom continuous_on_subset h' homeomorphism_cont1) done @@ -3029,7 +2910,7 @@ using clo closedin_imp_subset by auto have "T retract_of V" proof (simp add: retraction_def retract_of_def, intro exI conjI \T \ V\) - show "continuous_on V (g o h')" + show "continuous_on V (g \ h')" apply (intro continuous_on_compose h') apply (meson hom continuous_on_subset h' homeomorphism_cont1) done @@ -3086,7 +2967,7 @@ using Diff_subset_conv \U - Z \ W\ by blast ultimately show ?thesis apply (rule_tac V=V and W = "U-W" in that) - using openin_imp_subset apply (force simp:)+ + using openin_imp_subset apply force+ done qed @@ -3146,7 +3027,7 @@ proof (simp add: retraction_def retract_of_def, intro exI conjI) show "S' \ W" "S' \ h -` X" using him WS' closedin_imp_subset by blast+ - show "continuous_on (W \ h -` X) (f o r o h)" + show "continuous_on (W \ h -` X) (f \ r \ h)" proof (intro continuous_on_compose) show "continuous_on (W \ h -` X) h" by (meson conth continuous_on_subset inf_le1) @@ -3356,7 +3237,7 @@ apply (clarsimp elim!: all_forward) apply (erule impCE, metis subset_trans) apply (clarsimp elim!: ex_forward) -apply (rule_tac x="r o g" in exI) +apply (rule_tac x="r \ g" in exI) by (metis comp_apply continuous_on_compose continuous_on_subset subsetD imageI image_comp image_mono subset_trans) lemma AR_retract_of_AR: @@ -3642,7 +3523,7 @@ obtain r0 where "S \ T \ W0" and contr0: "continuous_on W0 r0" and "r0 ` W0 \ S \ T" and r0 [simp]: "\x. x \ S \ T \ r0 x = x" - using ret by (force simp add: retract_of_def retraction_def) + using ret by (force simp: retract_of_def retraction_def) have ST: "x \ W \ x \ S \ x \ T" for x using assms by (auto simp: W_def setdist_sing_in_set dest!: setdist_eq_0_closedin) define r where "r \ \x. if x \ W0 then r0 x else x" @@ -3667,8 +3548,7 @@ and opeSW1: "openin (subtopology euclidean S') W1" and "g ` W1 \ S" and geqr: "\x. x \ W0 \ S \ g x = r x" apply (rule ANR_imp_absolute_neighbourhood_extensor [OF \ANR S\ _ \r ` (W0 \ S) \ S\ cloS'WS]) - apply (rule continuous_on_subset [OF contr]) - apply (blast intro: elim: )+ + apply (rule continuous_on_subset [OF contr], blast+) done have cloT'WT: "closedin (subtopology euclidean T') (W0 \ T)" by (meson closedin_subset_trans UT cloUT' \T \ T'\ \W \ T'\ cloUW cloWW0 @@ -3677,13 +3557,12 @@ and opeSW2: "openin (subtopology euclidean T') W2" and "h ` W2 \ T" and heqr: "\x. x \ W0 \ T \ h x = r x" apply (rule ANR_imp_absolute_neighbourhood_extensor [OF \ANR T\ _ \r ` (W0 \ T) \ T\ cloT'WT]) - apply (rule continuous_on_subset [OF contr]) - apply (blast intro: elim: )+ + apply (rule continuous_on_subset [OF contr], blast+) done have "S' \ T' = W" by (force simp: S'_def T'_def W_def) obtain O1 O2 where "open O1" "W1 = S' \ O1" "open O2" "W2 = T' \ O2" - using opeSW1 opeSW2 by (force simp add: openin_open) + using opeSW1 opeSW2 by (force simp: openin_open) show ?thesis proof have eq: "W1 - (W - U0) \ (W2 - (W - U0)) = @@ -3692,25 +3571,23 @@ by (auto simp: \S' \ T' = U\ [symmetric] \S' \ T' = W\ [symmetric] \W1 = S' \ O1\ \W2 = T' \ O2\) show "openin (subtopology euclidean U) (W1 - (W - U0) \ (W2 - (W - U0)))" apply (subst eq) - apply (intro openin_Un openin_Int_open openin_diff closedin_diff cloUW opeUU0 cloUS' cloUT' \open O1\ \open O2\) - apply simp_all + apply (intro openin_Un openin_Int_open openin_diff closedin_diff cloUW opeUU0 cloUS' cloUT' \open O1\ \open O2\, simp_all) done have cloW1: "closedin (subtopology euclidean (W1 - (W - U0) \ (W2 - (W - U0)))) (W1 - (W - U0))" using cloUS' apply (simp add: closedin_closed) apply (erule ex_forward) using U0 \W0 \ S \ W1\ - apply (auto simp add: \W1 = S' \ O1\ \W2 = T' \ O2\ \S' \ T' = U\ [symmetric]\S' \ T' = W\ [symmetric]) + apply (auto simp: \W1 = S' \ O1\ \W2 = T' \ O2\ \S' \ T' = U\ [symmetric]\S' \ T' = W\ [symmetric]) done have cloW2: "closedin (subtopology euclidean (W1 - (W - U0) \ (W2 - (W - U0)))) (W2 - (W - U0))" using cloUT' apply (simp add: closedin_closed) apply (erule ex_forward) using U0 \W0 \ T \ W2\ - apply (auto simp add: \W1 = S' \ O1\ \W2 = T' \ O2\ \S' \ T' = U\ [symmetric]\S' \ T' = W\ [symmetric]) + apply (auto simp: \W1 = S' \ O1\ \W2 = T' \ O2\ \S' \ T' = U\ [symmetric]\S' \ T' = W\ [symmetric]) done have *: "\x\S \ T. (if x \ S' then g x else h x) = x" using ST \S' \ T' = W\ cloT'WT closedin_subset geqr heqr - apply (auto simp: r_def) - apply fastforce + apply (auto simp: r_def, fastforce) using \S \ S'\ \T \ T'\ \W0 \ S \ W1\ \W1 = S' \ O1\ by auto have "\r. continuous_on (W1 - (W - U0) \ (W2 - (W - U0))) r \ r ` (W1 - (W - U0) \ (W2 - (W - U0))) \ S \ T \ @@ -3725,7 +3602,7 @@ done then show "S \ T retract_of W1 - (W - U0) \ (W2 - (W - U0))" using \W0 \ S \ W1\ \W0 \ T \ W2\ ST opeUU0 U0 - by (auto simp add: retract_of_def retraction_def) + by (auto simp: retract_of_def retraction_def) qed qed @@ -4059,15 +3936,15 @@ by (auto simp: closest_point_self) have "rel_frontier S retract_of affine hull S - {a}" by (simp add: assms a rel_frontier_retract_of_punctured_affine_hull) - also have "... retract_of {x. closest_point (affine hull S) x \ a}" + also have "\ retract_of {x. closest_point (affine hull S) x \ a}" apply (simp add: retract_of_def retraction_def ahS) apply (rule_tac x="closest_point (affine hull S)" in exI) - apply (auto simp add: False closest_point_self affine_imp_convex closest_point_in_set continuous_on_closest_point) + apply (auto simp: False closest_point_self affine_imp_convex closest_point_in_set continuous_on_closest_point) done finally have "rel_frontier S retract_of {x. closest_point (affine hull S) x \ a}" . moreover have "openin (subtopology euclidean UNIV) (UNIV \ closest_point (affine hull S) -` (- {a}))" apply (rule continuous_openin_preimage_gen) - apply (auto simp add: False affine_imp_convex continuous_on_closest_point) + apply (auto simp: False affine_imp_convex continuous_on_closest_point) done ultimately show ?thesis unfolding ENR_def @@ -4116,7 +3993,7 @@ apply (rule continuous_on_cases_local [OF clS clT]) using r by (auto simp: continuous_on_id) qed (use r in auto) - also have "... retract_of U" + also have "\ retract_of U" by (rule Un) finally show ?thesis . qed @@ -4499,7 +4376,7 @@ and him: "h ` ({0..1} \ S) \ U" and [simp]: "\x. h(0, x) = f x" "\x. h(1::real, x) = g x" using assms by (auto simp: homotopic_with_def) - define h' where "h' \ \z. if snd z \ S then h z else (f o snd) z" + define h' where "h' \ \z. if snd z \ S then h z else (f \ snd) z" define B where "B \ {0::real} \ T \ {0..1} \ S" have clo0T: "closedin (subtopology euclidean ({0..1} \ T)) ({0::real} \ T)" by (simp add: closedin_subtopology_refl closedin_Times) @@ -4542,7 +4419,7 @@ "retraction V B r" for V r using that apply (clarsimp simp add: retraction_def) - apply (rule Vk [of V "h' o r"], assumption+) + apply (rule Vk [of V "h' \ r"], assumption+) apply (metis continuous_on_compose conth' continuous_on_subset) using \h' ` B \ U\ apply force+ done @@ -4629,7 +4506,7 @@ proof assume ?lhs then obtain c where c: "homotopic_with (\x. True) S T (\x. c) f" - by (blast intro: homotopic_with_symD elim: ) + by (blast intro: homotopic_with_symD) have "closedin (subtopology euclidean UNIV) S" using \closed S\ closed_closedin by fastforce then obtain g where "continuous_on UNIV g" "range g \ T" @@ -4645,10 +4522,10 @@ then obtain c where "homotopic_with (\h. True) UNIV T g (\x. c)" using nullhomotopic_from_contractible [of UNIV g T] contractible_UNIV by blast then show ?lhs - apply (rule_tac x="c" in exI) + apply (rule_tac x=c in exI) apply (rule homotopic_with_eq [of _ _ _ g "\x. c"]) apply (rule homotopic_with_subset_left) - apply (auto simp add: \\x. x \ S \ g x = f x\) + apply (auto simp: \\x. x \ S \ g x = f x\) done qed @@ -4672,7 +4549,7 @@ (is "?lhs = ?rhs") proof (cases "r = 0") case True with fim show ?thesis - apply (auto simp: ) + apply auto using fim continuous_on_const apply fastforce by (metis contf contractible_sing nullhomotopic_into_contractible) next @@ -4717,11 +4594,11 @@ obtain g where "range g \ sphere 0 1" "continuous_on UNIV g" "\x. x \ S \ g x = (x - a) /\<^sub>R norm (x - a)" using notr - by (auto simp add: nullhomotopic_into_sphere_extension + by (auto simp: nullhomotopic_into_sphere_extension [OF \closed S\ continuous_on_Borsuk_map [OF \a \ S\] False s01]) with \a \ S\ show "~ ?lhs" apply (clarsimp simp: Borsuk_map_into_sphere [of a S, symmetric] dest!: nog) - apply (drule_tac x="g" in spec) + apply (drule_tac x=g in spec) using continuous_on_subset by fastforce next assume "~ ?lhs" @@ -5070,7 +4947,7 @@ then obtain k where "y \ V k" and j: "\j V j" by (metis image_iff V wop) with him t show "\(t, y) \ T" - by (subst eq) (force simp:)+ + by (subst eq) force+ qed fix X y assume "X \ \" "y \ X"