# HG changeset patch # User paulson # Date 1694973395 -3600 # Node ID f8595f6d39a59336ca4644c57b985f51f8ef0816 # Parent 18ea58bdcf77b0929faea2a123fd136668dce4c4 (pointlessly) get rid of some simp calls within "proof" diff -r 18ea58bdcf77 -r f8595f6d39a5 src/HOL/Analysis/Starlike.thy --- a/src/HOL/Analysis/Starlike.thy Sat Sep 16 06:38:44 2023 +0000 +++ b/src/HOL/Analysis/Starlike.thy Sun Sep 17 18:56:35 2023 +0100 @@ -46,11 +46,9 @@ assumes "convex C" "T \ C" and z: "z \ rel_interior C" and dis: "disjnt S (rel_interior C)" shows "S \ (convex hull (insert z T)) = S \ (convex hull T)" (is "?lhs = ?rhs") proof - have "T = {} \ z \ S" + have *: "T = {} \ z \ S" using dis z by (auto simp add: disjnt_def) - then show "?lhs \ ?rhs" - proof (clarsimp simp add: convex_hull_insert_segments) - fix x y + { fix x y assume "x \ S" and y: "y \ convex hull T" and "x \ closed_segment z y" have "y \ closure C" by (metis y \convex C\ \T \ C\ closure_subset contra_subsetD convex_hull_eq hull_mono) @@ -58,10 +56,12 @@ by (meson \x \ S\ dis disjnt_iff) moreover have "x \ open_segment z y \ {z, y}" using \x \ closed_segment z y\ closed_segment_eq_open by blast - ultimately show "x \ convex hull T" + ultimately have "x \ convex hull T" using rel_interior_closure_convex_segment [OF \convex C\ z] using y z by blast - qed + } + with * show "?lhs \ ?rhs" + by (auto simp add: convex_hull_insert_segments) show "?rhs \ ?lhs" by (meson hull_mono inf_mono subset_insertI subset_refl) qed @@ -164,15 +164,18 @@ lemma in_interior_closure_convex_segment: fixes S :: "'a::euclidean_space set" assumes "convex S" and a: "a \ interior S" and b: "b \ closure S" - shows "open_segment a b \ interior S" -proof (clarsimp simp: in_segment) - fix u::real - assume u: "0 < u" "u < 1" - have "(1 - u) *\<^sub>R a + u *\<^sub>R b = b - (1 - u) *\<^sub>R (b - a)" - by (simp add: algebra_simps) - also have "... \ interior S" using mem_interior_closure_convex_shrink [OF assms] u - by simp - finally show "(1 - u) *\<^sub>R a + u *\<^sub>R b \ interior S" . + shows "open_segment a b \ interior S" +proof - + { fix u::real + assume u: "0 < u" "u < 1" + have "(1 - u) *\<^sub>R a + u *\<^sub>R b = b - (1 - u) *\<^sub>R (b - a)" + by (simp add: algebra_simps) + also have "... \ interior S" using mem_interior_closure_convex_shrink [OF assms] u + by simp + finally have "(1 - u) *\<^sub>R a + u *\<^sub>R b \ interior S" . + } + then show ?thesis + by (clarsimp simp: in_segment) qed lemma convex_closure_interior: @@ -193,11 +196,9 @@ using \a \ interior S\ closure_subset by blast next case False - show ?thesis - proof (clarsimp simp add: closure_def islimpt_approachable) - fix e::real + { fix e::real assume xnotS: "x \ interior S" and "0 < e" - show "\x'\interior S. x' \ x \ dist x' x < e" + have "\x'\interior S. x' \ x \ dist x' x < e" proof (intro bexI conjI) show "x - min (e/2 / norm (x - a)) 1 *\<^sub>R (x - a) \ x" using False \0 < e\ by (auto simp: algebra_simps min_def) @@ -207,7 +208,9 @@ using \0 < e\ False by (auto simp add: min_def a intro: mem_interior_closure_convex_shrink [OF \convex S\ a x]) qed - qed + } + then show ?thesis + by (auto simp add: closure_def islimpt_approachable) qed qed then show ?thesis @@ -232,11 +235,9 @@ have "conic hull S \ span S" by (simp add: hull_minimal span_superset) moreover - have "affine hull S \ conic hull S" - proof clarsimp - fix x + { fix x assume "x \ affine hull S" - show "x \ conic hull S" + have "x \ conic hull S" proof (cases "x=0") case True then show ?thesis @@ -252,7 +253,9 @@ then show ?thesis by (simp add: conic_hull_explicit) qed - qed + } + then have "affine hull S \ conic hull S" + by auto ultimately show ?thesis by blast qed @@ -313,16 +316,13 @@ assumes "finite S" and "0 \ S" shows "convex hull (insert 0 S) = {y. \u. (\x\S. 0 \ u x) \ sum u S \ 1 \ sum (\x. u x *\<^sub>R x) S = y}" -proof (simp add: convex_hull_finite set_eq_iff assms, safe) - fix x and u :: "'a \ real" - assume "0 \ u 0" "\x\S. 0 \ u x" "u 0 + sum u S = 1" - then show "\v. (\x\S. 0 \ v x) \ sum v S \ 1 \ (\x\S. v x *\<^sub>R x) = (\x\S. u x *\<^sub>R x)" - by force -next - fix x and u :: "'a \ real" - assume "\x\S. 0 \ u x" "sum u S \ 1" - then show "\v. 0 \ v 0 \ (\x\S. 0 \ v x) \ v 0 + sum v S = 1 \ (\x\S. v x *\<^sub>R x) = (\x\S. u x *\<^sub>R x)" - by (rule_tac x="\x. if x = 0 then 1 - sum u S else u x" in exI) (auto simp: sum_delta_notmem assms if_smult) +proof - + { fix x and u :: "'a \ real" + assume "\x\S. 0 \ u x" "sum u S \ 1" + then have "\v. 0 \ v 0 \ (\x\S. 0 \ v x) \ v 0 + sum v S = 1 \ (\x\S. v x *\<^sub>R x) = (\x\S. u x *\<^sub>R x)" + by (rule_tac x="\x. if x = 0 then 1 - sum u S else u x" in exI) (auto simp: sum_delta_notmem assms if_smult) + } + then show ?thesis by (auto simp: convex_hull_finite set_eq_iff assms) qed lemma substd_simplex: @@ -1444,13 +1444,11 @@ lemma rel_interior_inter_aux: "\{rel_interior S |S. S \ I} \ \I" proof - - { - fix y + { fix y assume "y \ \{rel_interior S |S. S \ I}" then have y: "\S \ I. y \ rel_interior S" by auto - { - fix S + { fix S assume "S \ I" then have "y \ S" using rel_interior_subset y by auto @@ -2345,32 +2343,31 @@ proof assume adl: "a + d *\<^sub>R l \ rel_interior S" obtain e where "e > 0" - and e: "\x'. x' \ affine hull S \ dist x' (a + d *\<^sub>R l) < e \ x' \ rel_interior S" + and e: "\x'. x' \ affine hull S \ dist x' (a + d *\<^sub>R l) < e \ x' \ rel_interior S" using relin_Ex adl by blast + have "d + e / norm l \ x" + if "0 < x" and nonrel: "a + x *\<^sub>R l \ rel_interior S" for x + proof (cases "x < d") + case True with inint nonrel \0 < x\ + show ?thesis by auto + next + case False + then have dle: "x < d + e / norm l \ dist (a + x *\<^sub>R l) (a + d *\<^sub>R l) < e" + by (simp add: field_simps \l \ 0\) + have ain: "a + x *\<^sub>R l \ affine hull S" + by (metis add_diff_cancel_left' aff affine_affine_hull mem_affine_3_minus aaff) + show ?thesis + using e [OF ain] nonrel dle by force + qed + then have "d + e / norm l \ Inf {d. 0 < d \ a + d *\<^sub>R l \ rel_interior S}" - proof (rule cInf_greatest [OF nonMT], clarsimp) - fix x::real - assume "0 < x" and nonrel: "a + x *\<^sub>R l \ rel_interior S" - show "d + e / norm l \ x" - proof (cases "x < d") - case True with inint nonrel \0 < x\ - show ?thesis by auto - next - case False - then have dle: "x < d + e / norm l \ dist (a + x *\<^sub>R l) (a + d *\<^sub>R l) < e" - by (simp add: field_simps \l \ 0\) - have ain: "a + x *\<^sub>R l \ affine hull S" - by (metis add_diff_cancel_left' aff affine_affine_hull mem_affine_3_minus aaff) - show ?thesis - using e [OF ain] nonrel dle by force - qed - qed + by (force simp add: intro: cInf_greatest [OF nonMT]) then show False using \0 < e\ \l \ 0\ by (simp add: d_def [symmetric] field_simps) qed - moreover have "a + d *\<^sub>R l \ closure S" - proof (clarsimp simp: closure_approachable) - fix \::real assume "0 < \" + moreover + have "\y\S. dist y (a + d *\<^sub>R l) < \" if "0 < \" for \::real + proof - have 1: "a + (d - min d (\ / 2 / norm l)) *\<^sub>R l \ S" proof (rule subsetD [OF rel_interior_subset inint]) show "d - min d (\ / 2 / norm l) < d" @@ -2381,10 +2378,12 @@ also have "... < \" using \l \ 0\ \0 < \\ by (simp add: field_simps) finally have 2: "norm l * min d (\ / (norm l * 2)) < \" . - show "\y\S. dist y (a + d *\<^sub>R l) < \" + show ?thesis using 1 2 \0 < d\ \0 < \\ by (rule_tac x="a + (d - min d (\ / 2 / norm l)) *\<^sub>R l" in bexI) (auto simp: algebra_simps) qed + then have "a + d *\<^sub>R l \ closure S" + by (auto simp: closure_approachable) ultimately have infront: "a + d *\<^sub>R l \ rel_frontier S" by (simp add: rel_frontier_def) show ?thesis @@ -3029,12 +3028,15 @@ (if card(S) \ DIM('a) then {} else {y. \u. (\x \ S. 0 < u x) \ sum u S = 1 \ (\x\S. u x *\<^sub>R x) = y})" (is "_ = (if _ then _ else ?rhs)") -proof (clarsimp simp: aff_independent_finite empty_interior_convex_hull assms) - assume S: "\ card S \ DIM('a)" - have "interior (convex hull S) = rel_interior(convex hull S)" - using assms S by (simp add: affine_independent_span_gt rel_interior_interior) - then show "interior(convex hull S) = ?rhs" - by (simp add: assms S rel_interior_convex_hull_explicit) +proof - + { assume S: "\ card S \ DIM('a)" + have "interior (convex hull S) = rel_interior(convex hull S)" + using assms S by (simp add: affine_independent_span_gt rel_interior_interior) + then have "interior(convex hull S) = ?rhs" + by (simp add: assms S rel_interior_convex_hull_explicit) + } + then show ?thesis + by (auto simp: aff_independent_finite empty_interior_convex_hull assms) qed lemma interior_convex_hull_explicit: @@ -3084,22 +3086,26 @@ fixes a :: "'a::euclidean_space" shows "interior(open_segment a b) = (if 2 \ DIM('a) then {} else open_segment a b)" -proof (simp add: not_le, intro conjI impI) - assume "2 \ DIM('a)" - then show "interior (open_segment a b) = {}" +proof (cases "2 \ DIM('a)") + case True + then have "interior (open_segment a b) = {}" using interior_closed_segment_ge2 interior_mono segment_open_subset_closed by blast + with True show ?thesis + by auto next - assume le2: "DIM('a) < 2" - show "interior (open_segment a b) = open_segment a b" + case ge2: False + have "interior (open_segment a b) = open_segment a b" proof (cases "a = b") case True then show ?thesis by auto next case False - with le2 have "affine hull (open_segment a b) = UNIV" + with ge2 have "affine hull (open_segment a b) = UNIV" by (simp add: False affine_independent_span_gt) then show "interior (open_segment a b) = open_segment a b" using rel_interior_interior rel_interior_open_segment by blast qed + with ge2 show ?thesis + by auto qed lemma interior_closed_segment: @@ -4870,12 +4876,15 @@ lemma bounded_hyperplane_eq_trivial: fixes a :: "'a::euclidean_space" shows "bounded {x. a \ x = r} \ (if a = 0 then r \ 0 else DIM('a) = 1)" -proof (simp add: bounded_hyperplane_eq_trivial_0, clarify) - assume "r \ 0" "a \ 0" - have "aff_dim {x. y \ x = 0} = aff_dim {x. a \ x = r}" if "y \ 0" for y::'a - by (metis that \a \ 0\ aff_dim_hyperplane) - then show "bounded {x. a \ x = r} = (DIM('a) = Suc 0)" - by (metis One_nat_def \a \ 0\ affine_bounded_eq_lowdim affine_hyperplane bounded_hyperplane_eq_trivial_0) +proof - + { assume "r \ 0" "a \ 0" + have "aff_dim {x. y \ x = 0} = aff_dim {x. a \ x = r}" if "y \ 0" for y::'a + by (metis that \a \ 0\ aff_dim_hyperplane) + then have "bounded {x. a \ x = r} = (DIM('a) = Suc 0)" + by (metis One_nat_def \a \ 0\ affine_bounded_eq_lowdim affine_hyperplane bounded_hyperplane_eq_trivial_0) + } + then show ?thesis + by (auto simp: bounded_hyperplane_eq_trivial_0) qed subsection\<^marker>\tag unimportant\\General case without assuming closure and getting non-strict separation\ @@ -5218,29 +5227,26 @@ have cc0: "cc x = 0" if "x \ S" "x \ T \ T'" for x using le [OF \x \ S\] that c0 by (force simp: cc_def cc'_def split: if_split_asm) + have ge0: "\x\T \ T'. 0 \ (cc(a := c a)) x" + by (simp add: c0 cc_def) + have "sum (cc(a := c a)) (insert a (T \ T')) = c a + sum (cc(a := c a)) (T \ T')" + by (simp add: anot) + also have "... = c a + sum (cc(a := c a)) S" + using \T \ S\ False cc0 cc_def \a \ S\ by (fastforce intro!: sum.mono_neutral_left split: if_split_asm) + also have "... = c a + (1 - c a)" + by (metis \a \ S\ fun_upd_other sum.cong sumSS'(1)) + finally have 1: "sum (cc(a := c a)) (insert a (T \ T')) = 1" + by simp + have "(\x\insert a (T \ T'). (cc(a := c a)) x *\<^sub>R x) = c a *\<^sub>R a + (\x \ T \ T'. (cc(a := c a)) x *\<^sub>R x)" + by (simp add: anot) + also have "... = c a *\<^sub>R a + (\x \ S. (cc(a := c a)) x *\<^sub>R x)" + using \T \ S\ False cc0 by (fastforce intro!: sum.mono_neutral_left split: if_split_asm) + also have "... = c a *\<^sub>R a + x - c a *\<^sub>R a" + by (simp add: wsumSS \a \ S\ if_smult sum_delta_notmem) + finally have self: "(\x\insert a (T \ T'). (cc(a := c a)) x *\<^sub>R x) = x" + by simp show ?thesis - proof (simp add: convex_hull_finite, intro exI conjI) - show "\x\T \ T'. 0 \ (cc(a := c a)) x" - by (simp add: c0 cc_def) - show "0 \ (cc(a := c a)) a" - by (simp add: c0) - have "sum (cc(a := c a)) (insert a (T \ T')) = c a + sum (cc(a := c a)) (T \ T')" - by (simp add: anot) - also have "... = c a + sum (cc(a := c a)) S" - using \T \ S\ False cc0 cc_def \a \ S\ by (fastforce intro!: sum.mono_neutral_left split: if_split_asm) - also have "... = c a + (1 - c a)" - by (metis \a \ S\ fun_upd_other sum.cong sumSS'(1)) - finally show "sum (cc(a := c a)) (insert a (T \ T')) = 1" - by simp - have "(\x\insert a (T \ T'). (cc(a := c a)) x *\<^sub>R x) = c a *\<^sub>R a + (\x \ T \ T'. (cc(a := c a)) x *\<^sub>R x)" - by (simp add: anot) - also have "... = c a *\<^sub>R a + (\x \ S. (cc(a := c a)) x *\<^sub>R x)" - using \T \ S\ False cc0 by (fastforce intro!: sum.mono_neutral_left split: if_split_asm) - also have "... = c a *\<^sub>R a + x - c a *\<^sub>R a" - by (simp add: wsumSS \a \ S\ if_smult sum_delta_notmem) - finally show "(\x\insert a (T \ T'). (cc(a := c a)) x *\<^sub>R x) = x" - by simp - qed + by (force simp: convex_hull_finite c0 intro!: ge0 1 self exI [where x = "cc(a := c a)"]) next case 2 then have "sum cc' S \ sum cc S" @@ -5251,29 +5257,26 @@ have cc0: "cc' x = 0" if "x \ S" "x \ T \ T'" for x using le [OF \x \ S\] that c'0 by (force simp: cc_def cc'_def split: if_split_asm) + have ge0: "\x\T \ T'. 0 \ (cc'(a := c' a)) x" + by (simp add: c'0 cc'_def) + have "sum (cc'(a := c' a)) (insert a (T \ T')) = c' a + sum (cc'(a := c' a)) (T \ T')" + by (simp add: anot) + also have "... = c' a + sum (cc'(a := c' a)) S" + using \T \ S\ False cc0 by (fastforce intro!: sum.mono_neutral_left split: if_split_asm) + also have "... = c' a + (1 - c' a)" + by (metis \a \ S\ fun_upd_other sum.cong sumSS') + finally have 1: "sum (cc'(a := c' a)) (insert a (T \ T')) = 1" + by simp + have "(\x\insert a (T \ T'). (cc'(a := c' a)) x *\<^sub>R x) = c' a *\<^sub>R a + (\x \ T \ T'. (cc'(a := c' a)) x *\<^sub>R x)" + by (simp add: anot) + also have "... = c' a *\<^sub>R a + (\x \ S. (cc'(a := c' a)) x *\<^sub>R x)" + using \T \ S\ False cc0 by (fastforce intro!: sum.mono_neutral_left split: if_split_asm) + also have "... = c a *\<^sub>R a + x - c a *\<^sub>R a" + by (simp add: wsumSS \a \ S\ if_smult sum_delta_notmem) + finally have self: "(\x\insert a (T \ T'). (cc'(a := c' a)) x *\<^sub>R x) = x" + by simp show ?thesis - proof (simp add: convex_hull_finite, intro exI conjI) - show "\x\T \ T'. 0 \ (cc'(a := c' a)) x" - by (simp add: c'0 cc'_def) - show "0 \ (cc'(a := c' a)) a" - by (simp add: c'0) - have "sum (cc'(a := c' a)) (insert a (T \ T')) = c' a + sum (cc'(a := c' a)) (T \ T')" - by (simp add: anot) - also have "... = c' a + sum (cc'(a := c' a)) S" - using \T \ S\ False cc0 by (fastforce intro!: sum.mono_neutral_left split: if_split_asm) - also have "... = c' a + (1 - c' a)" - by (metis \a \ S\ fun_upd_other sum.cong sumSS') - finally show "sum (cc'(a := c' a)) (insert a (T \ T')) = 1" - by simp - have "(\x\insert a (T \ T'). (cc'(a := c' a)) x *\<^sub>R x) = c' a *\<^sub>R a + (\x \ T \ T'. (cc'(a := c' a)) x *\<^sub>R x)" - by (simp add: anot) - also have "... = c' a *\<^sub>R a + (\x \ S. (cc'(a := c' a)) x *\<^sub>R x)" - using \T \ S\ False cc0 by (fastforce intro!: sum.mono_neutral_left split: if_split_asm) - also have "... = c a *\<^sub>R a + x - c a *\<^sub>R a" - by (simp add: wsumSS \a \ S\ if_smult sum_delta_notmem) - finally show "(\x\insert a (T \ T'). (cc'(a := c' a)) x *\<^sub>R x) = x" - by simp - qed + by (force simp: convex_hull_finite c'0 intro!: ge0 1 self exI [where x = "cc'(a := c' a)"]) qed qed @@ -5584,17 +5587,20 @@ also have "... = card ((\x. e *\<^sub>R x) ` B)" using \0 < e\ by (force simp: inj_on_def card_image) also have "... \ dim ((\x. - a + x) ` S)" - proof (simp, rule independent_card_le_dim) + proof - have e': "cball 0 e \ (\x. x - a) ` T \ (\x. x - a) ` S" using e by (auto simp: dist_norm norm_minus_commute subset_eq) have "(\x. e *\<^sub>R x) ` B \ cball 0 e \ (\x. x - a) ` T" using Bsub \0 < e\ eq1 subT' \a \ T\ by (auto simp: subspace_def) - then show "(\x. e *\<^sub>R x) ` B \ (\x. x - a) ` S" + then have "(\x. e *\<^sub>R x) ` B \ (\x. x - a) ` S" using e' by blast + moreover have "inj_on ((*\<^sub>R) e) (span B)" using \0 < e\ inj_on_def by fastforce - then show "independent ((\x. e *\<^sub>R x) ` B)" + then have "independent ((\x. e *\<^sub>R x) ` B)" using linear_scale_self \independent B\ linear_dependent_inj_imageD by blast + ultimately show ?thesis + by (auto simp: intro!: independent_card_le_dim) qed also have "... = aff_dim S" using \a \ S\ aff_dim_eq_dim hull_inc by (force cong: image_cong_simp)