5096 qed |
5100 qed |
5097 |
5101 |
5098 text {* Hence we get the following. *} |
5102 text {* Hence we get the following. *} |
5099 |
5103 |
5100 lemma compact_sup_maxdistance: |
5104 lemma compact_sup_maxdistance: |
5101 fixes s :: "'a::real_normed_vector set" |
5105 fixes s :: "'a::metric_space set" |
5102 assumes "compact s" "s \<noteq> {}" |
5106 assumes "compact s" "s \<noteq> {}" |
5103 shows "\<exists>x\<in>s. \<exists>y\<in>s. \<forall>u\<in>s. \<forall>v\<in>s. norm(u - v) \<le> norm(x - y)" |
5107 shows "\<exists>x\<in>s. \<exists>y\<in>s. \<forall>u\<in>s. \<forall>v\<in>s. dist u v \<le> dist x y" |
5104 proof- |
5108 proof- |
5105 have "{x - y | x y . x\<in>s \<and> y\<in>s} \<noteq> {}" using `s \<noteq> {}` by auto |
5109 have "compact (s \<times> s)" using `compact s` by (intro compact_Times) |
5106 then obtain x where x:"x\<in>{x - y |x y. x \<in> s \<and> y \<in> s}" "\<forall>y\<in>{x - y |x y. x \<in> s \<and> y \<in> s}. norm y \<le> norm x" |
5110 moreover have "s \<times> s \<noteq> {}" using `s \<noteq> {}` by auto |
5107 using compact_differences[OF assms(1) assms(1)] |
5111 moreover have "continuous_on (s \<times> s) (\<lambda>x. dist (fst x) (snd x))" |
5108 using distance_attains_sup[where 'a="'a", unfolded dist_norm, of "{x - y | x y . x\<in>s \<and> y\<in>s}" 0] by auto |
5112 by (intro continuous_at_imp_continuous_on ballI continuous_dist |
5109 from x(1) obtain a b where "a\<in>s" "b\<in>s" "x = a - b" by auto |
5113 continuous_isCont[THEN iffD1] isCont_fst isCont_snd isCont_ident) |
5110 thus ?thesis using x(2)[unfolded `x = a - b`] by blast |
5114 ultimately show ?thesis |
|
5115 using continuous_attains_sup[of "s \<times> s" "\<lambda>x. dist (fst x) (snd x)"] by auto |
5111 qed |
5116 qed |
5112 |
5117 |
5113 text {* We can state this in terms of diameter of a set. *} |
5118 text {* We can state this in terms of diameter of a set. *} |
5114 |
5119 |
5115 definition "diameter s = (if s = {} then 0::real else Sup {norm(x - y) | x y. x \<in> s \<and> y \<in> s})" |
5120 definition "diameter s = (if s = {} then 0::real else Sup {dist x y | x y. x \<in> s \<and> y \<in> s})" |
5116 (* TODO: generalize to class metric_space *) |
5121 |
|
5122 lemma diameter_bounded_bound: |
|
5123 fixes s :: "'a :: metric_space set" |
|
5124 assumes s: "bounded s" "x \<in> s" "y \<in> s" |
|
5125 shows "dist x y \<le> diameter s" |
|
5126 proof - |
|
5127 let ?D = "{dist x y |x y. x \<in> s \<and> y \<in> s}" |
|
5128 from s obtain z d where z: "\<And>x. x \<in> s \<Longrightarrow> dist z x \<le> d" |
|
5129 unfolding bounded_def by auto |
|
5130 have "dist x y \<le> Sup ?D" |
|
5131 proof (rule Sup_upper, safe) |
|
5132 fix a b assume "a \<in> s" "b \<in> s" |
|
5133 with z[of a] z[of b] dist_triangle[of a b z] |
|
5134 show "dist a b \<le> 2 * d" |
|
5135 by (simp add: dist_commute) |
|
5136 qed (insert s, auto) |
|
5137 with `x \<in> s` show ?thesis |
|
5138 by (auto simp add: diameter_def) |
|
5139 qed |
|
5140 |
|
5141 lemma diameter_lower_bounded: |
|
5142 fixes s :: "'a :: metric_space set" |
|
5143 assumes s: "bounded s" and d: "0 < d" "d < diameter s" |
|
5144 shows "\<exists>x\<in>s. \<exists>y\<in>s. d < dist x y" |
|
5145 proof (rule ccontr) |
|
5146 let ?D = "{dist x y |x y. x \<in> s \<and> y \<in> s}" |
|
5147 assume contr: "\<not> ?thesis" |
|
5148 moreover |
|
5149 from d have "s \<noteq> {}" |
|
5150 by (auto simp: diameter_def) |
|
5151 then have "?D \<noteq> {}" by auto |
|
5152 ultimately have "Sup ?D \<le> d" |
|
5153 by (intro Sup_least) (auto simp: not_less) |
|
5154 with `d < diameter s` `s \<noteq> {}` show False |
|
5155 by (auto simp: diameter_def) |
|
5156 qed |
5117 |
5157 |
5118 lemma diameter_bounded: |
5158 lemma diameter_bounded: |
5119 assumes "bounded s" |
5159 assumes "bounded s" |
5120 shows "\<forall>x\<in>s. \<forall>y\<in>s. norm(x - y) \<le> diameter s" |
5160 shows "\<forall>x\<in>s. \<forall>y\<in>s. dist x y \<le> diameter s" |
5121 "\<forall>d>0. d < diameter s --> (\<exists>x\<in>s. \<exists>y\<in>s. norm(x - y) > d)" |
5161 "\<forall>d>0. d < diameter s \<longrightarrow> (\<exists>x\<in>s. \<exists>y\<in>s. dist x y > d)" |
5122 proof- |
5162 using diameter_bounded_bound[of s] diameter_lower_bounded[of s] assms |
5123 let ?D = "{norm (x - y) |x y. x \<in> s \<and> y \<in> s}" |
5163 by auto |
5124 obtain a where a:"\<forall>x\<in>s. norm x \<le> a" using assms[unfolded bounded_iff] by auto |
|
5125 { fix x y assume "x \<in> s" "y \<in> s" |
|
5126 hence "norm (x - y) \<le> 2 * a" using norm_triangle_ineq[of x "-y", unfolded norm_minus_cancel] a[THEN bspec[where x=x]] a[THEN bspec[where x=y]] by (auto simp add: field_simps) } |
|
5127 note * = this |
|
5128 { fix x y assume "x\<in>s" "y\<in>s" hence "s \<noteq> {}" by auto |
|
5129 have "norm(x - y) \<le> diameter s" unfolding diameter_def using `s\<noteq>{}` *[OF `x\<in>s` `y\<in>s`] `x\<in>s` `y\<in>s` |
|
5130 by simp (blast del: Sup_upper intro!: * Sup_upper) } |
|
5131 moreover |
|
5132 { fix d::real assume "d>0" "d < diameter s" |
|
5133 hence "s\<noteq>{}" unfolding diameter_def by auto |
|
5134 have "\<exists>d' \<in> ?D. d' > d" |
|
5135 proof(rule ccontr) |
|
5136 assume "\<not> (\<exists>d'\<in>{norm (x - y) |x y. x \<in> s \<and> y \<in> s}. d < d')" |
|
5137 hence "\<forall>d'\<in>?D. d' \<le> d" by auto (metis not_leE) |
|
5138 thus False using `d < diameter s` `s\<noteq>{}` |
|
5139 apply (auto simp add: diameter_def) |
|
5140 apply (drule Sup_real_iff [THEN [2] rev_iffD2]) |
|
5141 apply (auto, force) |
|
5142 done |
|
5143 qed |
|
5144 hence "\<exists>x\<in>s. \<exists>y\<in>s. norm(x - y) > d" by auto } |
|
5145 ultimately show "\<forall>x\<in>s. \<forall>y\<in>s. norm(x - y) \<le> diameter s" |
|
5146 "\<forall>d>0. d < diameter s --> (\<exists>x\<in>s. \<exists>y\<in>s. norm(x - y) > d)" by auto |
|
5147 qed |
|
5148 |
|
5149 lemma diameter_bounded_bound: |
|
5150 "bounded s \<Longrightarrow> x \<in> s \<Longrightarrow> y \<in> s ==> norm(x - y) \<le> diameter s" |
|
5151 using diameter_bounded by blast |
|
5152 |
5164 |
5153 lemma diameter_compact_attained: |
5165 lemma diameter_compact_attained: |
5154 fixes s :: "'a::real_normed_vector set" |
|
5155 assumes "compact s" "s \<noteq> {}" |
5166 assumes "compact s" "s \<noteq> {}" |
5156 shows "\<exists>x\<in>s. \<exists>y\<in>s. (norm(x - y) = diameter s)" |
5167 shows "\<exists>x\<in>s. \<exists>y\<in>s. dist x y = diameter s" |
5157 proof- |
5168 proof - |
5158 have b:"bounded s" using assms(1) by (rule compact_imp_bounded) |
5169 have b:"bounded s" using assms(1) by (rule compact_imp_bounded) |
5159 then obtain x y where xys:"x\<in>s" "y\<in>s" and xy:"\<forall>u\<in>s. \<forall>v\<in>s. norm (u - v) \<le> norm (x - y)" using compact_sup_maxdistance[OF assms] by auto |
5170 then obtain x y where xys:"x\<in>s" "y\<in>s" and xy:"\<forall>u\<in>s. \<forall>v\<in>s. dist u v \<le> dist x y" |
5160 hence "diameter s \<le> norm (x - y)" |
5171 using compact_sup_maxdistance[OF assms] by auto |
|
5172 hence "diameter s \<le> dist x y" |
5161 unfolding diameter_def by clarsimp (rule Sup_least, fast+) |
5173 unfolding diameter_def by clarsimp (rule Sup_least, fast+) |
5162 thus ?thesis |
5174 thus ?thesis |
5163 by (metis b diameter_bounded_bound order_antisym xys) |
5175 by (metis b diameter_bounded_bound order_antisym xys) |
5164 qed |
5176 qed |
5165 |
5177 |