src/HOL/Analysis/Elementary_Metric_Spaces.thy
changeset 70136 f03a01a18c6e
parent 69922 4a9167f377b0
child 70617 c81ac117afa6
equal deleted inserted replaced
70135:ad6d4a14adb5 70136:f03a01a18c6e
    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"