4972 fixes S :: "real set" |
4972 fixes S :: "real set" |
4973 shows "S \<noteq> {} ==> (\<exists>b. b <=* S) ==> isGlb UNIV S (Inf S)" |
4973 shows "S \<noteq> {} ==> (\<exists>b. b <=* S) ==> isGlb UNIV S (Inf S)" |
4974 by (auto simp add: isLb_def setle_def setge_def isGlb_def greatestP_def) |
4974 by (auto simp add: isLb_def setle_def setge_def isGlb_def greatestP_def) |
4975 lemma distance_attains_sup: |
4975 lemma distance_attains_sup: |
4976 assumes "compact s" "s \<noteq> {}" |
4976 assumes "compact s" "s \<noteq> {}" |
4977 shows "\<exists>x \<in> s. \<forall>y \<in> s. dist a y \<le> dist a x" |
4977 shows "\<exists>x\<in>s. \<forall>y\<in>s. dist a y \<le> dist a x" |
4978 proof (rule continuous_attains_sup [OF assms]) |
4978 proof (rule continuous_attains_sup [OF assms]) |
4979 { fix x assume "x\<in>s" |
4979 { fix x assume "x\<in>s" |
4980 have "(dist a ---> dist a x) (at x within s)" |
4980 have "(dist a ---> dist a x) (at x within s)" |
4981 by (intro tendsto_dist tendsto_const Lim_at_within tendsto_ident_at) |
4981 by (intro tendsto_dist tendsto_const Lim_at_within tendsto_ident_at) |
4982 } |
4982 } |
4987 text {* For \emph{minimal} distance, we only need closure, not compactness. *} |
4987 text {* For \emph{minimal} distance, we only need closure, not compactness. *} |
4988 |
4988 |
4989 lemma distance_attains_inf: |
4989 lemma distance_attains_inf: |
4990 fixes a :: "'a::heine_borel" |
4990 fixes a :: "'a::heine_borel" |
4991 assumes "closed s" "s \<noteq> {}" |
4991 assumes "closed s" "s \<noteq> {}" |
4992 shows "\<exists>x \<in> s. \<forall>y \<in> s. dist a x \<le> dist a y" |
4992 shows "\<exists>x\<in>s. \<forall>y\<in>s. dist a x \<le> dist a y" |
4993 proof- |
4993 proof- |
4994 from assms(2) obtain b where "b\<in>s" by auto |
4994 from assms(2) obtain b where "b \<in> s" by auto |
4995 let ?B = "cball a (dist b a) \<inter> s" |
4995 let ?B = "s \<inter> cball a (dist b a)" |
4996 have "b \<in> ?B" using `b\<in>s` by (simp add: dist_commute) |
4996 have "?B \<noteq> {}" using `b \<in> s` by (auto simp add: dist_commute) |
4997 hence "?B \<noteq> {}" by auto |
4997 moreover have "continuous_on ?B (dist a)" |
4998 moreover |
4998 by (auto intro!: continuous_at_imp_continuous_on continuous_dist continuous_at_id continuous_const) |
4999 { fix x assume "x\<in>?B" |
|
5000 fix e::real assume "e>0" |
|
5001 { fix x' assume "x'\<in>?B" and as:"dist x' x < e" |
|
5002 from as have "\<bar>dist a x' - dist a x\<bar> < e" |
|
5003 unfolding abs_less_iff minus_diff_eq |
|
5004 using dist_triangle2 [of a x' x] |
|
5005 using dist_triangle [of a x x'] |
|
5006 by arith |
|
5007 } |
|
5008 hence "\<exists>d>0. \<forall>x'\<in>?B. dist x' x < d \<longrightarrow> \<bar>dist a x' - dist a x\<bar> < e" |
|
5009 using `e>0` by auto |
|
5010 } |
|
5011 hence "continuous_on (cball a (dist b a) \<inter> s) (dist a)" |
|
5012 unfolding continuous_on Lim_within dist_norm real_norm_def |
|
5013 by fast |
|
5014 moreover have "compact ?B" |
4999 moreover have "compact ?B" |
5015 using compact_cball[of a "dist b a"] |
5000 by (intro closed_inter_compact `closed s` compact_cball) |
5016 unfolding compact_eq_bounded_closed |
5001 ultimately obtain x where "x \<in> ?B" "\<forall>y\<in>?B. dist a x \<le> dist a y" |
5017 using bounded_Int and closed_Int and assms(1) by auto |
5002 by (metis continuous_attains_inf) |
5018 ultimately obtain x where "x\<in>cball a (dist b a) \<inter> s" "\<forall>y\<in>cball a (dist b a) \<inter> s. dist a x \<le> dist a y" |
|
5019 using continuous_attains_inf[of ?B "dist a"] by fastforce |
|
5020 thus ?thesis by fastforce |
5003 thus ?thesis by fastforce |
5021 qed |
5004 qed |
5022 |
5005 |
5023 |
5006 |
5024 subsection {* Pasted sets *} |
5007 subsection {* Pasted sets *} |
5332 with `x\<in>s` show ?thesis using dist_pos_lt[of a x] and`a \<notin> s` by blast |
5315 with `x\<in>s` show ?thesis using dist_pos_lt[of a x] and`a \<notin> s` by blast |
5333 qed |
5316 qed |
5334 |
5317 |
5335 lemma separate_compact_closed: |
5318 lemma separate_compact_closed: |
5336 fixes s t :: "'a::heine_borel set" |
5319 fixes s t :: "'a::heine_borel set" |
5337 assumes "compact s" and "closed t" and "s \<inter> t = {}" |
5320 assumes "compact s" and t: "closed t" "s \<inter> t = {}" |
5338 shows "\<exists>d>0. \<forall>x\<in>s. \<forall>y\<in>t. d \<le> dist x y" |
5321 shows "\<exists>d>0. \<forall>x\<in>s. \<forall>y\<in>t. d \<le> dist x y" |
5339 proof - (* FIXME: long proof *) |
5322 proof cases |
5340 let ?T = "\<Union>x\<in>s. { ball x (d / 2) | d. 0 < d \<and> (\<forall>y\<in>t. d \<le> dist x y) }" |
5323 assume "s \<noteq> {} \<and> t \<noteq> {}" |
5341 note `compact s` |
5324 then have "s \<noteq> {}" "t \<noteq> {}" by auto |
5342 moreover have "\<forall>t\<in>?T. open t" by auto |
5325 let ?inf = "\<lambda>x. infdist x t" |
5343 moreover have "s \<subseteq> \<Union>?T" |
5326 have "continuous_on s ?inf" |
5344 apply auto |
5327 by (auto intro!: continuous_at_imp_continuous_on continuous_infdist continuous_at_id) |
5345 apply (rule rev_bexI, assumption) |
5328 then obtain x where x: "x \<in> s" "\<forall>y\<in>s. ?inf x \<le> ?inf y" |
5346 apply (subgoal_tac "x \<notin> t") |
5329 using continuous_attains_inf[OF `compact s` `s \<noteq> {}`] by auto |
5347 apply (drule separate_point_closed [OF `closed t`]) |
5330 then have "0 < ?inf x" |
5348 apply clarify |
5331 using t `t \<noteq> {}` in_closed_iff_infdist_zero by (auto simp: less_le infdist_nonneg) |
5349 apply (rule_tac x="ball x (d / 2)" in exI) |
5332 moreover have "\<forall>x'\<in>s. \<forall>y\<in>t. ?inf x \<le> dist x' y" |
5350 apply simp |
5333 using x by (auto intro: order_trans infdist_le) |
5351 apply fast |
5334 ultimately show ?thesis |
5352 apply (cut_tac assms(3)) |
5335 by auto |
5353 apply auto |
5336 qed (auto intro!: exI[of _ 1]) |
5354 done |
|
5355 ultimately obtain U where "U \<subseteq> ?T" and "finite U" and "s \<subseteq> \<Union>U" |
|
5356 by (rule compactE) |
|
5357 from `finite U` and `U \<subseteq> ?T` have "\<exists>d>0. \<forall>x\<in>\<Union>U. \<forall>y\<in>t. d \<le> dist x y" |
|
5358 apply (induct set: finite) |
|
5359 apply simp |
|
5360 apply (rule exI) |
|
5361 apply (rule zero_less_one) |
|
5362 apply clarsimp |
|
5363 apply (rename_tac y e) |
|
5364 apply (rule_tac x="min d (e / 2)" in exI) |
|
5365 apply simp |
|
5366 apply (subst ball_Un) |
|
5367 apply (rule conjI) |
|
5368 apply (intro ballI, rename_tac z) |
|
5369 apply (rule min_max.le_infI2) |
|
5370 apply (simp only: mem_ball) |
|
5371 apply (drule (1) bspec) |
|
5372 apply (cut_tac x=y and y=x and z=z in dist_triangle, arith) |
|
5373 apply simp |
|
5374 apply (intro ballI) |
|
5375 apply (rule min_max.le_infI1) |
|
5376 apply simp |
|
5377 done |
|
5378 with `s \<subseteq> \<Union>U` show ?thesis |
|
5379 by fast |
|
5380 qed |
|
5381 |
5337 |
5382 lemma separate_closed_compact: |
5338 lemma separate_closed_compact: |
5383 fixes s t :: "'a::heine_borel set" |
5339 fixes s t :: "'a::heine_borel set" |
5384 assumes "closed s" and "compact t" and "s \<inter> t = {}" |
5340 assumes "closed s" and "compact t" and "s \<inter> t = {}" |
5385 shows "\<exists>d>0. \<forall>x\<in>s. \<forall>y\<in>t. d \<le> dist x y" |
5341 shows "\<exists>d>0. \<forall>x\<in>s. \<forall>y\<in>t. d \<le> dist x y" |