equal
deleted
inserted
replaced
13 |
13 |
14 section \<open>Elementary Metric Spaces\<close> |
14 section \<open>Elementary Metric Spaces\<close> |
15 |
15 |
16 subsection \<open>Open and closed balls\<close> |
16 subsection \<open>Open and closed balls\<close> |
17 |
17 |
18 definition%important ball :: "'a::metric_space \<Rightarrow> real \<Rightarrow> 'a set" |
18 definition\<^marker>\<open>tag important\<close> ball :: "'a::metric_space \<Rightarrow> real \<Rightarrow> 'a set" |
19 where "ball x e = {y. dist x y < e}" |
19 where "ball x e = {y. dist x y < e}" |
20 |
20 |
21 definition%important cball :: "'a::metric_space \<Rightarrow> real \<Rightarrow> 'a set" |
21 definition\<^marker>\<open>tag important\<close> cball :: "'a::metric_space \<Rightarrow> real \<Rightarrow> 'a set" |
22 where "cball x e = {y. dist x y \<le> e}" |
22 where "cball x e = {y. dist x y \<le> e}" |
23 |
23 |
24 definition%important sphere :: "'a::metric_space \<Rightarrow> real \<Rightarrow> 'a set" |
24 definition\<^marker>\<open>tag important\<close> sphere :: "'a::metric_space \<Rightarrow> real \<Rightarrow> 'a set" |
25 where "sphere x e = {y. dist x y = e}" |
25 where "sphere x e = {y. dist x y = e}" |
26 |
26 |
27 lemma mem_ball [simp]: "y \<in> ball x e \<longleftrightarrow> dist x y < e" |
27 lemma mem_ball [simp]: "y \<in> ball x e \<longleftrightarrow> dist x y < e" |
28 by (simp add: ball_def) |
28 by (simp add: ball_def) |
29 |
29 |
715 |
715 |
716 |
716 |
717 subsection \<open>Boundedness\<close> |
717 subsection \<open>Boundedness\<close> |
718 |
718 |
719 (* FIXME: This has to be unified with BSEQ!! *) |
719 (* FIXME: This has to be unified with BSEQ!! *) |
720 definition%important (in metric_space) bounded :: "'a set \<Rightarrow> bool" |
720 definition\<^marker>\<open>tag important\<close> (in metric_space) bounded :: "'a set \<Rightarrow> bool" |
721 where "bounded S \<longleftrightarrow> (\<exists>x e. \<forall>y\<in>S. dist x y \<le> e)" |
721 where "bounded S \<longleftrightarrow> (\<exists>x e. \<forall>y\<in>S. dist x y \<le> e)" |
722 |
722 |
723 lemma bounded_subset_cball: "bounded S \<longleftrightarrow> (\<exists>e x. S \<subseteq> cball x e \<and> 0 \<le> e)" |
723 lemma bounded_subset_cball: "bounded S \<longleftrightarrow> (\<exists>e x. S \<subseteq> cball x e \<and> 0 \<le> e)" |
724 unfolding bounded_def subset_eq by auto (meson order_trans zero_le_dist) |
724 unfolding bounded_def subset_eq by auto (meson order_trans zero_le_dist) |
725 |
725 |
1196 using \<open>a \<in> s\<close> by blast |
1196 using \<open>a \<in> s\<close> by blast |
1197 qed |
1197 qed |
1198 |
1198 |
1199 subsection \<open>The diameter of a set\<close> |
1199 subsection \<open>The diameter of a set\<close> |
1200 |
1200 |
1201 definition%important diameter :: "'a::metric_space set \<Rightarrow> real" where |
1201 definition\<^marker>\<open>tag important\<close> diameter :: "'a::metric_space set \<Rightarrow> real" where |
1202 "diameter S = (if S = {} then 0 else SUP (x,y)\<in>S\<times>S. dist x y)" |
1202 "diameter S = (if S = {} then 0 else SUP (x,y)\<in>S\<times>S. dist x y)" |
1203 |
1203 |
1204 lemma diameter_empty [simp]: "diameter{} = 0" |
1204 lemma diameter_empty [simp]: "diameter{} = 0" |
1205 by (auto simp: diameter_def) |
1205 by (auto simp: diameter_def) |
1206 |
1206 |
1462 lemma compact_closure [simp]: |
1462 lemma compact_closure [simp]: |
1463 fixes S :: "'a::heine_borel set" |
1463 fixes S :: "'a::heine_borel set" |
1464 shows "compact(closure S) \<longleftrightarrow> bounded S" |
1464 shows "compact(closure S) \<longleftrightarrow> bounded S" |
1465 by (meson bounded_closure bounded_subset closed_closure closure_subset compact_eq_bounded_closed) |
1465 by (meson bounded_closure bounded_subset closed_closure closure_subset compact_eq_bounded_closed) |
1466 |
1466 |
1467 instance%important real :: heine_borel |
1467 instance\<^marker>\<open>tag important\<close> real :: heine_borel |
1468 proof%unimportant |
1468 proof |
1469 fix f :: "nat \<Rightarrow> real" |
1469 fix f :: "nat \<Rightarrow> real" |
1470 assume f: "bounded (range f)" |
1470 assume f: "bounded (range f)" |
1471 obtain r :: "nat \<Rightarrow> nat" where r: "strict_mono r" "monoseq (f \<circ> r)" |
1471 obtain r :: "nat \<Rightarrow> nat" where r: "strict_mono r" "monoseq (f \<circ> r)" |
1472 unfolding comp_def by (metis seq_monosub) |
1472 unfolding comp_def by (metis seq_monosub) |
1473 then have "Bseq (f \<circ> r)" |
1473 then have "Bseq (f \<circ> r)" |
1543 |
1543 |
1544 lemma bounded_snd: "bounded s \<Longrightarrow> bounded (snd ` s)" |
1544 lemma bounded_snd: "bounded s \<Longrightarrow> bounded (snd ` s)" |
1545 unfolding bounded_def |
1545 unfolding bounded_def |
1546 by (metis (no_types, hide_lams) dist_snd_le image_iff order.trans) |
1546 by (metis (no_types, hide_lams) dist_snd_le image_iff order.trans) |
1547 |
1547 |
1548 instance%important prod :: (heine_borel, heine_borel) heine_borel |
1548 instance\<^marker>\<open>tag important\<close> prod :: (heine_borel, heine_borel) heine_borel |
1549 proof%unimportant |
1549 proof |
1550 fix f :: "nat \<Rightarrow> 'a \<times> 'b" |
1550 fix f :: "nat \<Rightarrow> 'a \<times> 'b" |
1551 assume f: "bounded (range f)" |
1551 assume f: "bounded (range f)" |
1552 then have "bounded (fst ` range f)" |
1552 then have "bounded (fst ` range f)" |
1553 by (rule bounded_fst) |
1553 by (rule bounded_fst) |
1554 then have s1: "bounded (range (fst \<circ> f))" |
1554 then have s1: "bounded (range (fst \<circ> f))" |
1842 shows "\<exists>!x. (f x = x)" |
1842 shows "\<exists>!x. (f x = x)" |
1843 using assms banach_fix[OF complete_UNIV UNIV_not_empty assms(1,2) subset_UNIV, of f] |
1843 using assms banach_fix[OF complete_UNIV UNIV_not_empty assms(1,2) subset_UNIV, of f] |
1844 by auto |
1844 by auto |
1845 |
1845 |
1846 |
1846 |
1847 subsection%unimportant\<open> Finite intersection property\<close> |
1847 subsection\<^marker>\<open>tag unimportant\<close>\<open> Finite intersection property\<close> |
1848 |
1848 |
1849 text\<open>Also developed in HOL's toplogical spaces theory, but the Heine-Borel type class isn't available there.\<close> |
1849 text\<open>Also developed in HOL's toplogical spaces theory, but the Heine-Borel type class isn't available there.\<close> |
1850 |
1850 |
1851 lemma closed_imp_fip: |
1851 lemma closed_imp_fip: |
1852 fixes S :: "'a::heine_borel set" |
1852 fixes S :: "'a::heine_borel set" |
1959 qed |
1959 qed |
1960 |
1960 |
1961 |
1961 |
1962 subsection \<open>Infimum Distance\<close> |
1962 subsection \<open>Infimum Distance\<close> |
1963 |
1963 |
1964 definition%important "infdist x A = (if A = {} then 0 else INF a\<in>A. dist x a)" |
1964 definition\<^marker>\<open>tag important\<close> "infdist x A = (if A = {} then 0 else INF a\<in>A. dist x a)" |
1965 |
1965 |
1966 lemma bdd_below_image_dist[intro, simp]: "bdd_below (dist x ` A)" |
1966 lemma bdd_below_image_dist[intro, simp]: "bdd_below (dist x ` A)" |
1967 by (auto intro!: zero_le_dist) |
1967 by (auto intro!: zero_le_dist) |
1968 |
1968 |
1969 lemma infdist_notempty: "A \<noteq> {} \<Longrightarrow> infdist x A = (INF a\<in>A. dist x a)" |
1969 lemma infdist_notempty: "A \<noteq> {} \<Longrightarrow> infdist x A = (INF a\<in>A. dist x a)" |
2451 using f |
2451 using f |
2452 unfolding continuous_on_iff uniformly_continuous_on_def |
2452 unfolding continuous_on_iff uniformly_continuous_on_def |
2453 by (force intro: compact_uniformly_equicontinuous [OF S, of "{f}"]) |
2453 by (force intro: compact_uniformly_equicontinuous [OF S, of "{f}"]) |
2454 |
2454 |
2455 |
2455 |
2456 subsection%unimportant\<open> Theorems relating continuity and uniform continuity to closures\<close> |
2456 subsection\<^marker>\<open>tag unimportant\<close>\<open> Theorems relating continuity and uniform continuity to closures\<close> |
2457 |
2457 |
2458 lemma continuous_on_closure: |
2458 lemma continuous_on_closure: |
2459 "continuous_on (closure S) f \<longleftrightarrow> |
2459 "continuous_on (closure S) f \<longleftrightarrow> |
2460 (\<forall>x e. x \<in> closure S \<and> 0 < e |
2460 (\<forall>x e. x \<in> closure S \<and> 0 < e |
2461 \<longrightarrow> (\<exists>d. 0 < d \<and> (\<forall>y. y \<in> S \<and> dist y x < d \<longrightarrow> dist (f y) (f x) < e)))" |
2461 \<longrightarrow> (\<exists>d. 0 < d \<and> (\<forall>y. y \<in> S \<and> dist y x < d \<longrightarrow> dist (f y) (f x) < e)))" |
2858 with a have "\<Inter>(range S) = {a}" |
2858 with a have "\<Inter>(range S) = {a}" |
2859 unfolding image_def by auto |
2859 unfolding image_def by auto |
2860 then show ?thesis .. |
2860 then show ?thesis .. |
2861 qed |
2861 qed |
2862 |
2862 |
2863 subsection%unimportant \<open>Making a continuous function avoid some value in a neighbourhood\<close> |
2863 subsection\<^marker>\<open>tag unimportant\<close> \<open>Making a continuous function avoid some value in a neighbourhood\<close> |
2864 |
2864 |
2865 lemma continuous_within_avoid: |
2865 lemma continuous_within_avoid: |
2866 fixes f :: "'a::metric_space \<Rightarrow> 'b::t1_space" |
2866 fixes f :: "'a::metric_space \<Rightarrow> 'b::t1_space" |
2867 assumes "continuous (at x within s) f" |
2867 assumes "continuous (at x within s) f" |
2868 and "f x \<noteq> a" |
2868 and "f x \<noteq> a" |
3039 by auto |
3039 by auto |
3040 |
3040 |
3041 |
3041 |
3042 subsection\<open>The infimum of the distance between two sets\<close> |
3042 subsection\<open>The infimum of the distance between two sets\<close> |
3043 |
3043 |
3044 definition%important setdist :: "'a::metric_space set \<Rightarrow> 'a set \<Rightarrow> real" where |
3044 definition\<^marker>\<open>tag important\<close> setdist :: "'a::metric_space set \<Rightarrow> 'a set \<Rightarrow> real" where |
3045 "setdist s t \<equiv> |
3045 "setdist s t \<equiv> |
3046 (if s = {} \<or> t = {} then 0 |
3046 (if s = {} \<or> t = {} then 0 |
3047 else Inf {dist x y| x y. x \<in> s \<and> y \<in> t})" |
3047 else Inf {dist x y| x y. x \<in> s \<and> y \<in> t})" |
3048 |
3048 |
3049 lemma setdist_empty1 [simp]: "setdist {} t = 0" |
3049 lemma setdist_empty1 [simp]: "setdist {} t = 0" |