src/HOL/Analysis/Elementary_Normed_Spaces.thy
author wenzelm
Mon Mar 25 17:21:26 2019 +0100 (4 weeks ago)
changeset 69981 3dced198b9ec
parent 69922 4a9167f377b0
child 70065 cc89a395b5a3
permissions -rw-r--r--
more strict AFP properties;
immler@69544
     1
(*  Author:     L C Paulson, University of Cambridge
immler@69544
     2
    Author:     Amine Chaieb, University of Cambridge
immler@69544
     3
    Author:     Robert Himmelmann, TU Muenchen
immler@69544
     4
    Author:     Brian Huffman, Portland State University
immler@69544
     5
*)
immler@69544
     6
immler@69544
     7
section \<open>Elementary Normed Vector Spaces\<close>
immler@69544
     8
immler@69544
     9
theory Elementary_Normed_Spaces
immler@69544
    10
  imports
immler@69544
    11
  "HOL-Library.FuncSet"
immler@69544
    12
  Elementary_Metric_Spaces
immler@69617
    13
  Connected
immler@69544
    14
begin
immler@69544
    15
immler@69544
    16
subsection%unimportant \<open>Various Lemmas Combining Imports\<close>
immler@69544
    17
immler@69544
    18
lemma countable_PiE:
immler@69544
    19
  "finite I \<Longrightarrow> (\<And>i. i \<in> I \<Longrightarrow> countable (F i)) \<Longrightarrow> countable (Pi\<^sub>E I F)"
immler@69544
    20
  by (induct I arbitrary: F rule: finite_induct) (auto simp: PiE_insert_eq)
immler@69544
    21
immler@69544
    22
immler@69544
    23
lemma open_sums:
immler@69544
    24
  fixes T :: "('b::real_normed_vector) set"
immler@69544
    25
  assumes "open S \<or> open T"
immler@69544
    26
  shows "open (\<Union>x\<in> S. \<Union>y \<in> T. {x + y})"
immler@69544
    27
  using assms
immler@69544
    28
proof
immler@69544
    29
  assume S: "open S"
immler@69544
    30
  show ?thesis
immler@69544
    31
  proof (clarsimp simp: open_dist)
immler@69544
    32
    fix x y
immler@69544
    33
    assume "x \<in> S" "y \<in> T"
immler@69544
    34
    with S obtain e where "e > 0" and e: "\<And>x'. dist x' x < e \<Longrightarrow> x' \<in> S"
immler@69544
    35
      by (auto simp: open_dist)
immler@69544
    36
    then have "\<And>z. dist z (x + y) < e \<Longrightarrow> \<exists>x\<in>S. \<exists>y\<in>T. z = x + y"
immler@69544
    37
      by (metis \<open>y \<in> T\<close> diff_add_cancel dist_add_cancel2)
immler@69544
    38
    then show "\<exists>e>0. \<forall>z. dist z (x + y) < e \<longrightarrow> (\<exists>x\<in>S. \<exists>y\<in>T. z = x + y)"
immler@69544
    39
      using \<open>0 < e\<close> \<open>x \<in> S\<close> by blast
immler@69544
    40
  qed
immler@69544
    41
next
immler@69544
    42
  assume T: "open T"
immler@69544
    43
  show ?thesis
immler@69544
    44
  proof (clarsimp simp: open_dist)
immler@69544
    45
    fix x y
immler@69544
    46
    assume "x \<in> S" "y \<in> T"
immler@69544
    47
    with T obtain e where "e > 0" and e: "\<And>x'. dist x' y < e \<Longrightarrow> x' \<in> T"
immler@69544
    48
      by (auto simp: open_dist)
immler@69544
    49
    then have "\<And>z. dist z (x + y) < e \<Longrightarrow> \<exists>x\<in>S. \<exists>y\<in>T. z = x + y"
immler@69544
    50
      by (metis \<open>x \<in> S\<close> add_diff_cancel_left' add_diff_eq diff_diff_add dist_norm)
immler@69544
    51
    then show "\<exists>e>0. \<forall>z. dist z (x + y) < e \<longrightarrow> (\<exists>x\<in>S. \<exists>y\<in>T. z = x + y)"
immler@69544
    52
      using \<open>0 < e\<close> \<open>y \<in> T\<close> by blast
immler@69544
    53
  qed
immler@69544
    54
qed
immler@69544
    55
immler@69544
    56
immler@69544
    57
subsection \<open>Support\<close>
immler@69544
    58
immler@69544
    59
definition (in monoid_add) support_on :: "'b set \<Rightarrow> ('b \<Rightarrow> 'a) \<Rightarrow> 'b set"
immler@69544
    60
  where "support_on s f = {x\<in>s. f x \<noteq> 0}"
immler@69544
    61
immler@69544
    62
lemma in_support_on: "x \<in> support_on s f \<longleftrightarrow> x \<in> s \<and> f x \<noteq> 0"
immler@69544
    63
  by (simp add: support_on_def)
immler@69544
    64
immler@69544
    65
lemma support_on_simps[simp]:
immler@69544
    66
  "support_on {} f = {}"
immler@69544
    67
  "support_on (insert x s) f =
immler@69544
    68
    (if f x = 0 then support_on s f else insert x (support_on s f))"
immler@69544
    69
  "support_on (s \<union> t) f = support_on s f \<union> support_on t f"
immler@69544
    70
  "support_on (s \<inter> t) f = support_on s f \<inter> support_on t f"
immler@69544
    71
  "support_on (s - t) f = support_on s f - support_on t f"
immler@69544
    72
  "support_on (f ` s) g = f ` (support_on s (g \<circ> f))"
immler@69544
    73
  unfolding support_on_def by auto
immler@69544
    74
immler@69544
    75
lemma support_on_cong:
immler@69544
    76
  "(\<And>x. x \<in> s \<Longrightarrow> f x = 0 \<longleftrightarrow> g x = 0) \<Longrightarrow> support_on s f = support_on s g"
immler@69544
    77
  by (auto simp: support_on_def)
immler@69544
    78
immler@69544
    79
lemma support_on_if: "a \<noteq> 0 \<Longrightarrow> support_on A (\<lambda>x. if P x then a else 0) = {x\<in>A. P x}"
immler@69544
    80
  by (auto simp: support_on_def)
immler@69544
    81
immler@69544
    82
lemma support_on_if_subset: "support_on A (\<lambda>x. if P x then a else 0) \<subseteq> {x \<in> A. P x}"
immler@69544
    83
  by (auto simp: support_on_def)
immler@69544
    84
immler@69544
    85
lemma finite_support[intro]: "finite S \<Longrightarrow> finite (support_on S f)"
immler@69544
    86
  unfolding support_on_def by auto
immler@69544
    87
immler@69544
    88
(* TODO: is supp_sum really needed? TODO: Generalize to Finite_Set.fold *)
immler@69544
    89
definition (in comm_monoid_add) supp_sum :: "('b \<Rightarrow> 'a) \<Rightarrow> 'b set \<Rightarrow> 'a"
immler@69544
    90
  where "supp_sum f S = (\<Sum>x\<in>support_on S f. f x)"
immler@69544
    91
immler@69544
    92
lemma supp_sum_empty[simp]: "supp_sum f {} = 0"
immler@69544
    93
  unfolding supp_sum_def by auto
immler@69544
    94
immler@69544
    95
lemma supp_sum_insert[simp]:
immler@69544
    96
  "finite (support_on S f) \<Longrightarrow>
immler@69544
    97
    supp_sum f (insert x S) = (if x \<in> S then supp_sum f S else f x + supp_sum f S)"
immler@69544
    98
  by (simp add: supp_sum_def in_support_on insert_absorb)
immler@69544
    99
immler@69544
   100
lemma supp_sum_divide_distrib: "supp_sum f A / (r::'a::field) = supp_sum (\<lambda>n. f n / r) A"
immler@69544
   101
  by (cases "r = 0")
immler@69544
   102
     (auto simp: supp_sum_def sum_divide_distrib intro!: sum.cong support_on_cong)
immler@69544
   103
immler@69544
   104
immler@69544
   105
subsection \<open>Intervals\<close>
immler@69544
   106
immler@69544
   107
lemma image_affinity_interval:
immler@69544
   108
  fixes c :: "'a::ordered_real_vector"
immler@69544
   109
  shows "((\<lambda>x. m *\<^sub>R x + c) ` {a..b}) = 
immler@69544
   110
           (if {a..b}={} then {}
immler@69544
   111
            else if 0 \<le> m then {m *\<^sub>R a + c .. m  *\<^sub>R b + c}
immler@69544
   112
            else {m *\<^sub>R b + c .. m *\<^sub>R a + c})"
immler@69544
   113
         (is "?lhs = ?rhs")
immler@69544
   114
proof (cases "m=0")
immler@69544
   115
  case True
immler@69544
   116
  then show ?thesis
immler@69544
   117
    by force
immler@69544
   118
next
immler@69544
   119
  case False
immler@69544
   120
  show ?thesis
immler@69544
   121
  proof
immler@69544
   122
    show "?lhs \<subseteq> ?rhs"
immler@69544
   123
      by (auto simp: scaleR_left_mono scaleR_left_mono_neg)
immler@69544
   124
    show "?rhs \<subseteq> ?lhs"
immler@69544
   125
    proof (clarsimp, intro conjI impI subsetI)
immler@69544
   126
      show "\<lbrakk>0 \<le> m; a \<le> b; x \<in> {m *\<^sub>R a + c..m *\<^sub>R b + c}\<rbrakk>
immler@69544
   127
            \<Longrightarrow> x \<in> (\<lambda>x. m *\<^sub>R x + c) ` {a..b}" for x
immler@69544
   128
        apply (rule_tac x="inverse m *\<^sub>R (x-c)" in rev_image_eqI)
immler@69544
   129
        using False apply (auto simp: le_diff_eq pos_le_divideRI)
immler@69544
   130
        using diff_le_eq pos_le_divideR_eq by force
immler@69544
   131
      show "\<lbrakk>\<not> 0 \<le> m; a \<le> b;  x \<in> {m *\<^sub>R b + c..m *\<^sub>R a + c}\<rbrakk>
immler@69544
   132
            \<Longrightarrow> x \<in> (\<lambda>x. m *\<^sub>R x + c) ` {a..b}" for x
immler@69544
   133
        apply (rule_tac x="inverse m *\<^sub>R (x-c)" in rev_image_eqI)
immler@69544
   134
        apply (auto simp: diff_le_eq neg_le_divideR_eq)
immler@69544
   135
        using diff_eq_diff_less_eq linordered_field_class.sign_simps(11) minus_diff_eq not_less scaleR_le_cancel_left_neg by fastforce
immler@69544
   136
    qed
immler@69544
   137
  qed
immler@69544
   138
qed
immler@69544
   139
immler@69611
   140
subsection \<open>Limit Points\<close>
immler@69611
   141
immler@69611
   142
lemma islimpt_ball:
immler@69611
   143
  fixes x y :: "'a::{real_normed_vector,perfect_space}"
immler@69611
   144
  shows "y islimpt ball x e \<longleftrightarrow> 0 < e \<and> y \<in> cball x e"
immler@69611
   145
  (is "?lhs \<longleftrightarrow> ?rhs")
immler@69611
   146
proof
immler@69611
   147
  show ?rhs if ?lhs
immler@69611
   148
  proof
immler@69611
   149
    {
immler@69611
   150
      assume "e \<le> 0"
immler@69611
   151
      then have *: "ball x e = {}"
immler@69611
   152
        using ball_eq_empty[of x e] by auto
immler@69611
   153
      have False using \<open>?lhs\<close>
immler@69611
   154
        unfolding * using islimpt_EMPTY[of y] by auto
immler@69611
   155
    }
immler@69611
   156
    then show "e > 0" by (metis not_less)
immler@69611
   157
    show "y \<in> cball x e"
immler@69611
   158
      using closed_cball[of x e] islimpt_subset[of y "ball x e" "cball x e"]
immler@69611
   159
        ball_subset_cball[of x e] \<open>?lhs\<close>
immler@69611
   160
      unfolding closed_limpt by auto
immler@69611
   161
  qed
immler@69611
   162
  show ?lhs if ?rhs
immler@69611
   163
  proof -
immler@69611
   164
    from that have "e > 0" by auto
immler@69611
   165
    {
immler@69611
   166
      fix d :: real
immler@69611
   167
      assume "d > 0"
immler@69611
   168
      have "\<exists>x'\<in>ball x e. x' \<noteq> y \<and> dist x' y < d"
immler@69611
   169
      proof (cases "d \<le> dist x y")
immler@69611
   170
        case True
immler@69611
   171
        then show "\<exists>x'\<in>ball x e. x' \<noteq> y \<and> dist x' y < d"
immler@69611
   172
        proof (cases "x = y")
immler@69611
   173
          case True
immler@69611
   174
          then have False
immler@69611
   175
            using \<open>d \<le> dist x y\<close> \<open>d>0\<close> by auto
immler@69611
   176
          then show "\<exists>x'\<in>ball x e. x' \<noteq> y \<and> dist x' y < d"
immler@69611
   177
            by auto
immler@69611
   178
        next
immler@69611
   179
          case False
immler@69611
   180
          have "dist x (y - (d / (2 * dist y x)) *\<^sub>R (y - x)) =
immler@69611
   181
            norm (x - y + (d / (2 * norm (y - x))) *\<^sub>R (y - x))"
immler@69611
   182
            unfolding mem_cball mem_ball dist_norm diff_diff_eq2 diff_add_eq[symmetric]
immler@69611
   183
            by auto
immler@69611
   184
          also have "\<dots> = \<bar>- 1 + d / (2 * norm (x - y))\<bar> * norm (x - y)"
immler@69611
   185
            using scaleR_left_distrib[of "- 1" "d / (2 * norm (y - x))", symmetric, of "y - x"]
immler@69611
   186
            unfolding scaleR_minus_left scaleR_one
immler@69611
   187
            by (auto simp: norm_minus_commute)
immler@69611
   188
          also have "\<dots> = \<bar>- norm (x - y) + d / 2\<bar>"
immler@69611
   189
            unfolding abs_mult_pos[of "norm (x - y)", OF norm_ge_zero[of "x - y"]]
immler@69611
   190
            unfolding distrib_right using \<open>x\<noteq>y\<close>  by auto
immler@69611
   191
          also have "\<dots> \<le> e - d/2" using \<open>d \<le> dist x y\<close> and \<open>d>0\<close> and \<open>?rhs\<close>
immler@69611
   192
            by (auto simp: dist_norm)
immler@69611
   193
          finally have "y - (d / (2 * dist y x)) *\<^sub>R (y - x) \<in> ball x e" using \<open>d>0\<close>
immler@69611
   194
            by auto
immler@69611
   195
          moreover
immler@69611
   196
          have "(d / (2*dist y x)) *\<^sub>R (y - x) \<noteq> 0"
immler@69611
   197
            using \<open>x\<noteq>y\<close>[unfolded dist_nz] \<open>d>0\<close> unfolding scaleR_eq_0_iff
immler@69611
   198
            by (auto simp: dist_commute)
immler@69611
   199
          moreover
immler@69611
   200
          have "dist (y - (d / (2 * dist y x)) *\<^sub>R (y - x)) y < d"
immler@69611
   201
            unfolding dist_norm
immler@69611
   202
            apply simp
immler@69611
   203
            unfolding norm_minus_cancel
immler@69611
   204
            using \<open>d > 0\<close> \<open>x\<noteq>y\<close>[unfolded dist_nz] dist_commute[of x y]
immler@69611
   205
            unfolding dist_norm
immler@69611
   206
            apply auto
immler@69611
   207
            done
immler@69611
   208
          ultimately show "\<exists>x'\<in>ball x e. x' \<noteq> y \<and> dist x' y < d"
immler@69611
   209
            apply (rule_tac x = "y - (d / (2*dist y x)) *\<^sub>R (y - x)" in bexI)
immler@69611
   210
            apply auto
immler@69611
   211
            done
immler@69611
   212
        qed
immler@69611
   213
      next
immler@69611
   214
        case False
immler@69611
   215
        then have "d > dist x y" by auto
immler@69611
   216
        show "\<exists>x' \<in> ball x e. x' \<noteq> y \<and> dist x' y < d"
immler@69611
   217
        proof (cases "x = y")
immler@69611
   218
          case True
immler@69611
   219
          obtain z where **: "z \<noteq> y" "dist z y < min e d"
immler@69611
   220
            using perfect_choose_dist[of "min e d" y]
immler@69611
   221
            using \<open>d > 0\<close> \<open>e>0\<close> by auto
immler@69611
   222
          show "\<exists>x'\<in>ball x e. x' \<noteq> y \<and> dist x' y < d"
immler@69611
   223
            unfolding \<open>x = y\<close>
immler@69611
   224
            using \<open>z \<noteq> y\<close> **
immler@69611
   225
            apply (rule_tac x=z in bexI)
immler@69611
   226
            apply (auto simp: dist_commute)
immler@69611
   227
            done
immler@69611
   228
        next
immler@69611
   229
          case False
immler@69611
   230
          then show "\<exists>x'\<in>ball x e. x' \<noteq> y \<and> dist x' y < d"
immler@69611
   231
            using \<open>d>0\<close> \<open>d > dist x y\<close> \<open>?rhs\<close>
immler@69611
   232
            apply (rule_tac x=x in bexI, auto)
immler@69611
   233
            done
immler@69611
   234
        qed
immler@69611
   235
      qed
immler@69611
   236
    }
immler@69611
   237
    then show ?thesis
immler@69611
   238
      unfolding mem_cball islimpt_approachable mem_ball by auto
immler@69611
   239
  qed
immler@69611
   240
qed
immler@69611
   241
immler@69611
   242
lemma closure_ball_lemma:
immler@69611
   243
  fixes x y :: "'a::real_normed_vector"
immler@69611
   244
  assumes "x \<noteq> y"
immler@69611
   245
  shows "y islimpt ball x (dist x y)"
immler@69611
   246
proof (rule islimptI)
immler@69611
   247
  fix T
immler@69611
   248
  assume "y \<in> T" "open T"
immler@69611
   249
  then obtain r where "0 < r" "\<forall>z. dist z y < r \<longrightarrow> z \<in> T"
immler@69611
   250
    unfolding open_dist by fast
immler@69611
   251
  (* choose point between x and y, within distance r of y. *)
immler@69611
   252
  define k where "k = min 1 (r / (2 * dist x y))"
immler@69611
   253
  define z where "z = y + scaleR k (x - y)"
immler@69611
   254
  have z_def2: "z = x + scaleR (1 - k) (y - x)"
immler@69611
   255
    unfolding z_def by (simp add: algebra_simps)
immler@69611
   256
  have "dist z y < r"
immler@69611
   257
    unfolding z_def k_def using \<open>0 < r\<close>
immler@69611
   258
    by (simp add: dist_norm min_def)
immler@69611
   259
  then have "z \<in> T"
immler@69611
   260
    using \<open>\<forall>z. dist z y < r \<longrightarrow> z \<in> T\<close> by simp
immler@69611
   261
  have "dist x z < dist x y"
immler@69611
   262
    unfolding z_def2 dist_norm
immler@69611
   263
    apply (simp add: norm_minus_commute)
immler@69611
   264
    apply (simp only: dist_norm [symmetric])
immler@69611
   265
    apply (subgoal_tac "\<bar>1 - k\<bar> * dist x y < 1 * dist x y", simp)
immler@69611
   266
    apply (rule mult_strict_right_mono)
immler@69611
   267
    apply (simp add: k_def \<open>0 < r\<close> \<open>x \<noteq> y\<close>)
immler@69611
   268
    apply (simp add: \<open>x \<noteq> y\<close>)
immler@69611
   269
    done
immler@69611
   270
  then have "z \<in> ball x (dist x y)"
immler@69611
   271
    by simp
immler@69611
   272
  have "z \<noteq> y"
immler@69611
   273
    unfolding z_def k_def using \<open>x \<noteq> y\<close> \<open>0 < r\<close>
immler@69611
   274
    by (simp add: min_def)
immler@69611
   275
  show "\<exists>z\<in>ball x (dist x y). z \<in> T \<and> z \<noteq> y"
immler@69611
   276
    using \<open>z \<in> ball x (dist x y)\<close> \<open>z \<in> T\<close> \<open>z \<noteq> y\<close>
immler@69611
   277
    by fast
immler@69611
   278
qed
immler@69611
   279
immler@69611
   280
immler@69611
   281
subsection \<open>Balls and Spheres in Normed Spaces\<close>
immler@69611
   282
immler@69611
   283
lemma mem_ball_0 [simp]: "x \<in> ball 0 e \<longleftrightarrow> norm x < e"
immler@69611
   284
  for x :: "'a::real_normed_vector"
immler@69611
   285
  by (simp add: dist_norm)
immler@69611
   286
immler@69611
   287
lemma mem_cball_0 [simp]: "x \<in> cball 0 e \<longleftrightarrow> norm x \<le> e"
immler@69611
   288
  for x :: "'a::real_normed_vector"
immler@69611
   289
  by (simp add: dist_norm)
immler@69611
   290
immler@69611
   291
lemma closure_ball [simp]:
immler@69611
   292
  fixes x :: "'a::real_normed_vector"
immler@69611
   293
  shows "0 < e \<Longrightarrow> closure (ball x e) = cball x e"
immler@69611
   294
  apply (rule equalityI)
immler@69611
   295
  apply (rule closure_minimal)
immler@69611
   296
  apply (rule ball_subset_cball)
immler@69611
   297
  apply (rule closed_cball)
immler@69611
   298
  apply (rule subsetI, rename_tac y)
immler@69611
   299
  apply (simp add: le_less [where 'a=real])
immler@69611
   300
  apply (erule disjE)
immler@69611
   301
  apply (rule subsetD [OF closure_subset], simp)
immler@69611
   302
  apply (simp add: closure_def, clarify)
immler@69611
   303
  apply (rule closure_ball_lemma)
immler@69611
   304
  apply simp
immler@69611
   305
  done
immler@69611
   306
immler@69611
   307
lemma mem_sphere_0 [simp]: "x \<in> sphere 0 e \<longleftrightarrow> norm x = e"
immler@69611
   308
  for x :: "'a::real_normed_vector"
immler@69611
   309
  by (simp add: dist_norm)
immler@69611
   310
immler@69611
   311
(* In a trivial vector space, this fails for e = 0. *)
immler@69611
   312
lemma interior_cball [simp]:
immler@69611
   313
  fixes x :: "'a::{real_normed_vector, perfect_space}"
immler@69611
   314
  shows "interior (cball x e) = ball x e"
immler@69611
   315
proof (cases "e \<ge> 0")
immler@69611
   316
  case False note cs = this
immler@69611
   317
  from cs have null: "ball x e = {}"
immler@69611
   318
    using ball_empty[of e x] by auto
immler@69611
   319
  moreover
immler@69611
   320
  have "cball x e = {}"
immler@69611
   321
  proof (rule equals0I)
immler@69611
   322
    fix y
immler@69611
   323
    assume "y \<in> cball x e"
immler@69611
   324
    then show False
immler@69611
   325
      by (metis ball_eq_empty null cs dist_eq_0_iff dist_le_zero_iff empty_subsetI mem_cball
immler@69611
   326
          subset_antisym subset_ball)
immler@69611
   327
  qed
immler@69611
   328
  then have "interior (cball x e) = {}"
immler@69611
   329
    using interior_empty by auto
immler@69611
   330
  ultimately show ?thesis by blast
immler@69611
   331
next
immler@69611
   332
  case True note cs = this
immler@69611
   333
  have "ball x e \<subseteq> cball x e"
immler@69611
   334
    using ball_subset_cball by auto
immler@69611
   335
  moreover
immler@69611
   336
  {
immler@69611
   337
    fix S y
immler@69611
   338
    assume as: "S \<subseteq> cball x e" "open S" "y\<in>S"
immler@69611
   339
    then obtain d where "d>0" and d: "\<forall>x'. dist x' y < d \<longrightarrow> x' \<in> S"
immler@69611
   340
      unfolding open_dist by blast
immler@69611
   341
    then obtain xa where xa_y: "xa \<noteq> y" and xa: "dist xa y < d"
immler@69611
   342
      using perfect_choose_dist [of d] by auto
immler@69611
   343
    have "xa \<in> S"
immler@69611
   344
      using d[THEN spec[where x = xa]]
immler@69611
   345
      using xa by (auto simp: dist_commute)
immler@69611
   346
    then have xa_cball: "xa \<in> cball x e"
immler@69611
   347
      using as(1) by auto
immler@69611
   348
    then have "y \<in> ball x e"
immler@69611
   349
    proof (cases "x = y")
immler@69611
   350
      case True
immler@69611
   351
      then have "e > 0" using cs order.order_iff_strict xa_cball xa_y by fastforce
immler@69611
   352
      then show "y \<in> ball x e"
immler@69611
   353
        using \<open>x = y \<close> by simp
immler@69611
   354
    next
immler@69611
   355
      case False
immler@69611
   356
      have "dist (y + (d / 2 / dist y x) *\<^sub>R (y - x)) y < d"
immler@69611
   357
        unfolding dist_norm
immler@69611
   358
        using \<open>d>0\<close> norm_ge_zero[of "y - x"] \<open>x \<noteq> y\<close> by auto
immler@69611
   359
      then have *: "y + (d / 2 / dist y x) *\<^sub>R (y - x) \<in> cball x e"
immler@69611
   360
        using d as(1)[unfolded subset_eq] by blast
immler@69611
   361
      have "y - x \<noteq> 0" using \<open>x \<noteq> y\<close> by auto
immler@69611
   362
      hence **:"d / (2 * norm (y - x)) > 0"
immler@69611
   363
        unfolding zero_less_norm_iff[symmetric] using \<open>d>0\<close> by auto
immler@69611
   364
      have "dist (y + (d / 2 / dist y x) *\<^sub>R (y - x)) x =
immler@69611
   365
        norm (y + (d / (2 * norm (y - x))) *\<^sub>R y - (d / (2 * norm (y - x))) *\<^sub>R x - x)"
immler@69611
   366
        by (auto simp: dist_norm algebra_simps)
immler@69611
   367
      also have "\<dots> = norm ((1 + d / (2 * norm (y - x))) *\<^sub>R (y - x))"
immler@69611
   368
        by (auto simp: algebra_simps)
immler@69611
   369
      also have "\<dots> = \<bar>1 + d / (2 * norm (y - x))\<bar> * norm (y - x)"
immler@69611
   370
        using ** by auto
immler@69611
   371
      also have "\<dots> = (dist y x) + d/2"
immler@69611
   372
        using ** by (auto simp: distrib_right dist_norm)
immler@69611
   373
      finally have "e \<ge> dist x y +d/2"
immler@69611
   374
        using *[unfolded mem_cball] by (auto simp: dist_commute)
immler@69611
   375
      then show "y \<in> ball x e"
immler@69611
   376
        unfolding mem_ball using \<open>d>0\<close> by auto
immler@69611
   377
    qed
immler@69611
   378
  }
immler@69611
   379
  then have "\<forall>S \<subseteq> cball x e. open S \<longrightarrow> S \<subseteq> ball x e"
immler@69611
   380
    by auto
immler@69611
   381
  ultimately show ?thesis
immler@69611
   382
    using interior_unique[of "ball x e" "cball x e"]
immler@69611
   383
    using open_ball[of x e]
immler@69611
   384
    by auto
immler@69611
   385
qed
immler@69611
   386
immler@69611
   387
lemma frontier_ball [simp]:
immler@69611
   388
  fixes a :: "'a::real_normed_vector"
immler@69611
   389
  shows "0 < e \<Longrightarrow> frontier (ball a e) = sphere a e"
immler@69611
   390
  by (force simp: frontier_def)
immler@69611
   391
immler@69611
   392
lemma frontier_cball [simp]:
immler@69611
   393
  fixes a :: "'a::{real_normed_vector, perfect_space}"
immler@69611
   394
  shows "frontier (cball a e) = sphere a e"
immler@69611
   395
  by (force simp: frontier_def)
immler@69611
   396
immler@69611
   397
corollary compact_sphere [simp]:
immler@69611
   398
  fixes a :: "'a::{real_normed_vector,perfect_space,heine_borel}"
immler@69611
   399
  shows "compact (sphere a r)"
immler@69611
   400
using compact_frontier [of "cball a r"] by simp
immler@69611
   401
immler@69611
   402
corollary bounded_sphere [simp]:
immler@69611
   403
  fixes a :: "'a::{real_normed_vector,perfect_space,heine_borel}"
immler@69611
   404
  shows "bounded (sphere a r)"
immler@69611
   405
by (simp add: compact_imp_bounded)
immler@69611
   406
immler@69611
   407
corollary closed_sphere  [simp]:
immler@69611
   408
  fixes a :: "'a::{real_normed_vector,perfect_space,heine_borel}"
immler@69611
   409
  shows "closed (sphere a r)"
immler@69611
   410
by (simp add: compact_imp_closed)
immler@69611
   411
immler@69611
   412
lemma image_add_ball [simp]:
immler@69611
   413
  fixes a :: "'a::real_normed_vector"
immler@69611
   414
  shows "(+) b ` ball a r = ball (a+b) r"
immler@69611
   415
apply (intro equalityI subsetI)
immler@69611
   416
apply (force simp: dist_norm)
immler@69611
   417
apply (rule_tac x="x-b" in image_eqI)
immler@69611
   418
apply (auto simp: dist_norm algebra_simps)
immler@69611
   419
done
immler@69611
   420
immler@69611
   421
lemma image_add_cball [simp]:
immler@69611
   422
  fixes a :: "'a::real_normed_vector"
immler@69611
   423
  shows "(+) b ` cball a r = cball (a+b) r"
immler@69611
   424
apply (intro equalityI subsetI)
immler@69611
   425
apply (force simp: dist_norm)
immler@69611
   426
apply (rule_tac x="x-b" in image_eqI)
immler@69611
   427
apply (auto simp: dist_norm algebra_simps)
immler@69611
   428
done
immler@69611
   429
immler@69544
   430
immler@69544
   431
subsection%unimportant \<open>Various Lemmas on Normed Algebras\<close>
immler@69544
   432
immler@69544
   433
immler@69544
   434
lemma closed_of_nat_image: "closed (of_nat ` A :: 'a::real_normed_algebra_1 set)"
immler@69544
   435
  by (rule discrete_imp_closed[of 1]) (auto simp: dist_of_nat)
immler@69544
   436
immler@69544
   437
lemma closed_of_int_image: "closed (of_int ` A :: 'a::real_normed_algebra_1 set)"
immler@69544
   438
  by (rule discrete_imp_closed[of 1]) (auto simp: dist_of_int)
immler@69544
   439
immler@69544
   440
lemma closed_Nats [simp]: "closed (\<nat> :: 'a :: real_normed_algebra_1 set)"
immler@69544
   441
  unfolding Nats_def by (rule closed_of_nat_image)
immler@69544
   442
immler@69544
   443
lemma closed_Ints [simp]: "closed (\<int> :: 'a :: real_normed_algebra_1 set)"
immler@69544
   444
  unfolding Ints_def by (rule closed_of_int_image)
immler@69544
   445
immler@69544
   446
lemma closed_subset_Ints:
immler@69544
   447
  fixes A :: "'a :: real_normed_algebra_1 set"
immler@69544
   448
  assumes "A \<subseteq> \<int>"
immler@69544
   449
  shows   "closed A"
immler@69544
   450
proof (intro discrete_imp_closed[OF zero_less_one] ballI impI, goal_cases)
immler@69544
   451
  case (1 x y)
immler@69544
   452
  with assms have "x \<in> \<int>" and "y \<in> \<int>" by auto
immler@69544
   453
  with \<open>dist y x < 1\<close> show "y = x"
immler@69544
   454
    by (auto elim!: Ints_cases simp: dist_of_int)
immler@69544
   455
qed
immler@69544
   456
immler@69544
   457
subsection \<open>Filters\<close>
immler@69544
   458
immler@69544
   459
definition indirection :: "'a::real_normed_vector \<Rightarrow> 'a \<Rightarrow> 'a filter"  (infixr "indirection" 70)
immler@69544
   460
  where "a indirection v = at a within {b. \<exists>c\<ge>0. b - a = scaleR c v}"
immler@69544
   461
immler@69544
   462
immler@69544
   463
subsection \<open>Trivial Limits\<close>
immler@69544
   464
immler@69544
   465
lemma trivial_limit_at_infinity:
immler@69544
   466
  "\<not> trivial_limit (at_infinity :: ('a::{real_normed_vector,perfect_space}) filter)"
immler@69544
   467
  unfolding trivial_limit_def eventually_at_infinity
immler@69544
   468
  apply clarsimp
immler@69544
   469
  apply (subgoal_tac "\<exists>x::'a. x \<noteq> 0", clarify)
immler@69544
   470
   apply (rule_tac x="scaleR (b / norm x) x" in exI, simp)
immler@69544
   471
  apply (cut_tac islimpt_UNIV [of "0::'a", unfolded islimpt_def])
immler@69544
   472
  apply (drule_tac x=UNIV in spec, simp)
immler@69544
   473
  done
immler@69544
   474
immler@69611
   475
lemma at_within_ball_bot_iff:
immler@69611
   476
  fixes x y :: "'a::{real_normed_vector,perfect_space}"
immler@69611
   477
  shows "at x within ball y r = bot \<longleftrightarrow> (r=0 \<or> x \<notin> cball y r)"
immler@69611
   478
  unfolding trivial_limit_within 
immler@69611
   479
  apply (auto simp add:trivial_limit_within islimpt_ball )
immler@69611
   480
  by (metis le_less_trans less_eq_real_def zero_le_dist)
immler@69611
   481
immler@69611
   482
immler@69544
   483
subsection \<open>Limits\<close>
immler@69544
   484
immler@69544
   485
proposition Lim_at_infinity: "(f \<longlongrightarrow> l) at_infinity \<longleftrightarrow> (\<forall>e>0. \<exists>b. \<forall>x. norm x \<ge> b \<longrightarrow> dist (f x) l < e)"
immler@69544
   486
  by (auto simp: tendsto_iff eventually_at_infinity)
immler@69544
   487
immler@69544
   488
corollary Lim_at_infinityI [intro?]:
immler@69544
   489
  assumes "\<And>e. e > 0 \<Longrightarrow> \<exists>B. \<forall>x. norm x \<ge> B \<longrightarrow> dist (f x) l \<le> e"
immler@69544
   490
  shows "(f \<longlongrightarrow> l) at_infinity"
immler@69544
   491
  apply (simp add: Lim_at_infinity, clarify)
immler@69544
   492
  apply (rule ex_forward [OF assms [OF half_gt_zero]], auto)
immler@69544
   493
  done
immler@69544
   494
immler@69544
   495
lemma Lim_transform_within_set_eq:
immler@69544
   496
  fixes a l :: "'a::real_normed_vector"
immler@69544
   497
  shows "eventually (\<lambda>x. x \<in> s \<longleftrightarrow> x \<in> t) (at a)
immler@69544
   498
         \<Longrightarrow> ((f \<longlongrightarrow> l) (at a within s) \<longleftrightarrow> (f \<longlongrightarrow> l) (at a within t))"
immler@69544
   499
  by (force intro: Lim_transform_within_set elim: eventually_mono)
immler@69544
   500
immler@69544
   501
lemma Lim_null:
immler@69544
   502
  fixes f :: "'a \<Rightarrow> 'b::real_normed_vector"
immler@69544
   503
  shows "(f \<longlongrightarrow> l) net \<longleftrightarrow> ((\<lambda>x. f(x) - l) \<longlongrightarrow> 0) net"
immler@69544
   504
  by (simp add: Lim dist_norm)
immler@69544
   505
immler@69544
   506
lemma Lim_null_comparison:
immler@69544
   507
  fixes f :: "'a \<Rightarrow> 'b::real_normed_vector"
immler@69544
   508
  assumes "eventually (\<lambda>x. norm (f x) \<le> g x) net" "(g \<longlongrightarrow> 0) net"
immler@69544
   509
  shows "(f \<longlongrightarrow> 0) net"
immler@69544
   510
  using assms(2)
immler@69544
   511
proof (rule metric_tendsto_imp_tendsto)
immler@69544
   512
  show "eventually (\<lambda>x. dist (f x) 0 \<le> dist (g x) 0) net"
immler@69544
   513
    using assms(1) by (rule eventually_mono) (simp add: dist_norm)
immler@69544
   514
qed
immler@69544
   515
immler@69544
   516
lemma Lim_transform_bound:
immler@69544
   517
  fixes f :: "'a \<Rightarrow> 'b::real_normed_vector"
immler@69544
   518
    and g :: "'a \<Rightarrow> 'c::real_normed_vector"
immler@69544
   519
  assumes "eventually (\<lambda>n. norm (f n) \<le> norm (g n)) net"
immler@69544
   520
    and "(g \<longlongrightarrow> 0) net"
immler@69544
   521
  shows "(f \<longlongrightarrow> 0) net"
immler@69544
   522
  using assms(1) tendsto_norm_zero [OF assms(2)]
immler@69544
   523
  by (rule Lim_null_comparison)
immler@69544
   524
immler@69544
   525
lemma lim_null_mult_right_bounded:
immler@69544
   526
  fixes f :: "'a \<Rightarrow> 'b::real_normed_div_algebra"
immler@69544
   527
  assumes f: "(f \<longlongrightarrow> 0) F" and g: "eventually (\<lambda>x. norm(g x) \<le> B) F"
immler@69544
   528
    shows "((\<lambda>z. f z * g z) \<longlongrightarrow> 0) F"
immler@69544
   529
proof -
immler@69544
   530
  have *: "((\<lambda>x. norm (f x) * B) \<longlongrightarrow> 0) F"
immler@69544
   531
    by (simp add: f tendsto_mult_left_zero tendsto_norm_zero)
immler@69544
   532
  have "((\<lambda>x. norm (f x) * norm (g x)) \<longlongrightarrow> 0) F"
immler@69544
   533
    apply (rule Lim_null_comparison [OF _ *])
immler@69544
   534
    apply (simp add: eventually_mono [OF g] mult_left_mono)
immler@69544
   535
    done
immler@69544
   536
  then show ?thesis
immler@69544
   537
    by (subst tendsto_norm_zero_iff [symmetric]) (simp add: norm_mult)
immler@69544
   538
qed
immler@69544
   539
immler@69544
   540
lemma lim_null_mult_left_bounded:
immler@69544
   541
  fixes f :: "'a \<Rightarrow> 'b::real_normed_div_algebra"
immler@69544
   542
  assumes g: "eventually (\<lambda>x. norm(g x) \<le> B) F" and f: "(f \<longlongrightarrow> 0) F"
immler@69544
   543
    shows "((\<lambda>z. g z * f z) \<longlongrightarrow> 0) F"
immler@69544
   544
proof -
immler@69544
   545
  have *: "((\<lambda>x. B * norm (f x)) \<longlongrightarrow> 0) F"
immler@69544
   546
    by (simp add: f tendsto_mult_right_zero tendsto_norm_zero)
immler@69544
   547
  have "((\<lambda>x. norm (g x) * norm (f x)) \<longlongrightarrow> 0) F"
immler@69544
   548
    apply (rule Lim_null_comparison [OF _ *])
immler@69544
   549
    apply (simp add: eventually_mono [OF g] mult_right_mono)
immler@69544
   550
    done
immler@69544
   551
  then show ?thesis
immler@69544
   552
    by (subst tendsto_norm_zero_iff [symmetric]) (simp add: norm_mult)
immler@69544
   553
qed
immler@69544
   554
immler@69544
   555
lemma lim_null_scaleR_bounded:
immler@69544
   556
  assumes f: "(f \<longlongrightarrow> 0) net" and gB: "eventually (\<lambda>a. f a = 0 \<or> norm(g a) \<le> B) net"
immler@69544
   557
    shows "((\<lambda>n. f n *\<^sub>R g n) \<longlongrightarrow> 0) net"
immler@69544
   558
proof
immler@69544
   559
  fix \<epsilon>::real
immler@69544
   560
  assume "0 < \<epsilon>"
immler@69544
   561
  then have B: "0 < \<epsilon> / (abs B + 1)" by simp
immler@69544
   562
  have *: "\<bar>f x\<bar> * norm (g x) < \<epsilon>" if f: "\<bar>f x\<bar> * (\<bar>B\<bar> + 1) < \<epsilon>" and g: "norm (g x) \<le> B" for x
immler@69544
   563
  proof -
immler@69544
   564
    have "\<bar>f x\<bar> * norm (g x) \<le> \<bar>f x\<bar> * B"
immler@69544
   565
      by (simp add: mult_left_mono g)
immler@69544
   566
    also have "\<dots> \<le> \<bar>f x\<bar> * (\<bar>B\<bar> + 1)"
immler@69544
   567
      by (simp add: mult_left_mono)
immler@69544
   568
    also have "\<dots> < \<epsilon>"
immler@69544
   569
      by (rule f)
immler@69544
   570
    finally show ?thesis .
immler@69544
   571
  qed
immler@69544
   572
  show "\<forall>\<^sub>F x in net. dist (f x *\<^sub>R g x) 0 < \<epsilon>"
immler@69544
   573
    apply (rule eventually_mono [OF eventually_conj [OF tendstoD [OF f B] gB] ])
immler@69544
   574
    apply (auto simp: \<open>0 < \<epsilon>\<close> divide_simps * split: if_split_asm)
immler@69544
   575
    done
immler@69544
   576
qed
immler@69544
   577
immler@69544
   578
lemma Lim_norm_ubound:
immler@69544
   579
  fixes f :: "'a \<Rightarrow> 'b::real_normed_vector"
immler@69544
   580
  assumes "\<not>(trivial_limit net)" "(f \<longlongrightarrow> l) net" "eventually (\<lambda>x. norm(f x) \<le> e) net"
immler@69544
   581
  shows "norm(l) \<le> e"
immler@69544
   582
  using assms by (fast intro: tendsto_le tendsto_intros)
immler@69544
   583
immler@69544
   584
lemma Lim_norm_lbound:
immler@69544
   585
  fixes f :: "'a \<Rightarrow> 'b::real_normed_vector"
immler@69544
   586
  assumes "\<not> trivial_limit net"
immler@69544
   587
    and "(f \<longlongrightarrow> l) net"
immler@69544
   588
    and "eventually (\<lambda>x. e \<le> norm (f x)) net"
immler@69544
   589
  shows "e \<le> norm l"
immler@69544
   590
  using assms by (fast intro: tendsto_le tendsto_intros)
immler@69544
   591
immler@69544
   592
text\<open>Limit under bilinear function\<close>
immler@69544
   593
immler@69544
   594
lemma Lim_bilinear:
immler@69544
   595
  assumes "(f \<longlongrightarrow> l) net"
immler@69544
   596
    and "(g \<longlongrightarrow> m) net"
immler@69544
   597
    and "bounded_bilinear h"
immler@69544
   598
  shows "((\<lambda>x. h (f x) (g x)) \<longlongrightarrow> (h l m)) net"
immler@69544
   599
  using \<open>bounded_bilinear h\<close> \<open>(f \<longlongrightarrow> l) net\<close> \<open>(g \<longlongrightarrow> m) net\<close>
immler@69544
   600
  by (rule bounded_bilinear.tendsto)
immler@69544
   601
immler@69544
   602
lemma Lim_at_zero:
immler@69544
   603
  fixes a :: "'a::real_normed_vector"
immler@69544
   604
    and l :: "'b::topological_space"
immler@69544
   605
  shows "(f \<longlongrightarrow> l) (at a) \<longleftrightarrow> ((\<lambda>x. f(a + x)) \<longlongrightarrow> l) (at 0)"
immler@69544
   606
  using LIM_offset_zero LIM_offset_zero_cancel ..
immler@69544
   607
immler@69544
   608
immler@69544
   609
subsection%unimportant \<open>Limit Point of Filter\<close>
immler@69544
   610
immler@69544
   611
lemma netlimit_at_vector:
immler@69544
   612
  fixes a :: "'a::real_normed_vector"
immler@69544
   613
  shows "netlimit (at a) = a"
immler@69544
   614
proof (cases "\<exists>x. x \<noteq> a")
immler@69544
   615
  case True then obtain x where x: "x \<noteq> a" ..
immler@69544
   616
  have "\<not> trivial_limit (at a)"
immler@69544
   617
    unfolding trivial_limit_def eventually_at dist_norm
immler@69544
   618
    apply clarsimp
immler@69544
   619
    apply (rule_tac x="a + scaleR (d / 2) (sgn (x - a))" in exI)
immler@69544
   620
    apply (simp add: norm_sgn sgn_zero_iff x)
immler@69544
   621
    done
immler@69544
   622
  then show ?thesis
immler@69544
   623
    by (rule netlimit_within [of a UNIV])
immler@69544
   624
qed simp
immler@69544
   625
immler@69544
   626
subsection \<open>Boundedness\<close>
immler@69544
   627
immler@69611
   628
lemma continuous_on_closure_norm_le:
immler@69611
   629
  fixes f :: "'a::metric_space \<Rightarrow> 'b::real_normed_vector"
immler@69611
   630
  assumes "continuous_on (closure s) f"
immler@69611
   631
    and "\<forall>y \<in> s. norm(f y) \<le> b"
immler@69611
   632
    and "x \<in> (closure s)"
immler@69611
   633
  shows "norm (f x) \<le> b"
immler@69611
   634
proof -
immler@69611
   635
  have *: "f ` s \<subseteq> cball 0 b"
immler@69611
   636
    using assms(2)[unfolded mem_cball_0[symmetric]] by auto
immler@69611
   637
  show ?thesis
immler@69611
   638
    by (meson "*" assms(1) assms(3) closed_cball image_closure_subset image_subset_iff mem_cball_0)
immler@69611
   639
qed
immler@69611
   640
immler@69544
   641
lemma bounded_pos: "bounded S \<longleftrightarrow> (\<exists>b>0. \<forall>x\<in> S. norm x \<le> b)"
immler@69544
   642
  apply (simp add: bounded_iff)
immler@69544
   643
  apply (subgoal_tac "\<And>x (y::real). 0 < 1 + \<bar>y\<bar> \<and> (x \<le> y \<longrightarrow> x \<le> 1 + \<bar>y\<bar>)")
immler@69544
   644
  apply metis
immler@69544
   645
  apply arith
immler@69544
   646
  done
immler@69544
   647
immler@69544
   648
lemma bounded_pos_less: "bounded S \<longleftrightarrow> (\<exists>b>0. \<forall>x\<in> S. norm x < b)"
immler@69544
   649
  apply (simp add: bounded_pos)
immler@69544
   650
  apply (safe; rule_tac x="b+1" in exI; force)
immler@69544
   651
  done
immler@69544
   652
immler@69544
   653
lemma Bseq_eq_bounded:
immler@69544
   654
  fixes f :: "nat \<Rightarrow> 'a::real_normed_vector"
immler@69544
   655
  shows "Bseq f \<longleftrightarrow> bounded (range f)"
immler@69544
   656
  unfolding Bseq_def bounded_pos by auto
immler@69544
   657
immler@69544
   658
lemma bounded_linear_image:
immler@69544
   659
  assumes "bounded S"
immler@69544
   660
    and "bounded_linear f"
immler@69544
   661
  shows "bounded (f ` S)"
immler@69544
   662
proof -
immler@69544
   663
  from assms(1) obtain b where "b > 0" and b: "\<forall>x\<in>S. norm x \<le> b"
immler@69544
   664
    unfolding bounded_pos by auto
immler@69544
   665
  from assms(2) obtain B where B: "B > 0" "\<forall>x. norm (f x) \<le> B * norm x"
immler@69544
   666
    using bounded_linear.pos_bounded by (auto simp: ac_simps)
immler@69544
   667
  show ?thesis
immler@69544
   668
    unfolding bounded_pos
immler@69544
   669
  proof (intro exI, safe)
immler@69544
   670
    show "norm (f x) \<le> B * b" if "x \<in> S" for x
immler@69544
   671
      by (meson B b less_imp_le mult_left_mono order_trans that)
immler@69544
   672
  qed (use \<open>b > 0\<close> \<open>B > 0\<close> in auto)
immler@69544
   673
qed
immler@69544
   674
immler@69544
   675
lemma bounded_scaling:
immler@69544
   676
  fixes S :: "'a::real_normed_vector set"
immler@69544
   677
  shows "bounded S \<Longrightarrow> bounded ((\<lambda>x. c *\<^sub>R x) ` S)"
immler@69544
   678
  apply (rule bounded_linear_image, assumption)
immler@69544
   679
  apply (rule bounded_linear_scaleR_right)
immler@69544
   680
  done
immler@69544
   681
immler@69544
   682
lemma bounded_scaleR_comp:
immler@69544
   683
  fixes f :: "'a \<Rightarrow> 'b::real_normed_vector"
immler@69544
   684
  assumes "bounded (f ` S)"
immler@69544
   685
  shows "bounded ((\<lambda>x. r *\<^sub>R f x) ` S)"
immler@69544
   686
  using bounded_scaling[of "f ` S" r] assms
immler@69544
   687
  by (auto simp: image_image)
immler@69544
   688
immler@69544
   689
lemma bounded_translation:
immler@69544
   690
  fixes S :: "'a::real_normed_vector set"
immler@69544
   691
  assumes "bounded S"
immler@69544
   692
  shows "bounded ((\<lambda>x. a + x) ` S)"
immler@69544
   693
proof -
immler@69544
   694
  from assms obtain b where b: "b > 0" "\<forall>x\<in>S. norm x \<le> b"
immler@69544
   695
    unfolding bounded_pos by auto
immler@69544
   696
  {
immler@69544
   697
    fix x
immler@69544
   698
    assume "x \<in> S"
immler@69544
   699
    then have "norm (a + x) \<le> b + norm a"
immler@69544
   700
      using norm_triangle_ineq[of a x] b by auto
immler@69544
   701
  }
immler@69544
   702
  then show ?thesis
immler@69544
   703
    unfolding bounded_pos
immler@69544
   704
    using norm_ge_zero[of a] b(1) and add_strict_increasing[of b 0 "norm a"]
immler@69544
   705
    by (auto intro!: exI[of _ "b + norm a"])
immler@69544
   706
qed
immler@69544
   707
immler@69544
   708
lemma bounded_translation_minus:
immler@69544
   709
  fixes S :: "'a::real_normed_vector set"
immler@69544
   710
  shows "bounded S \<Longrightarrow> bounded ((\<lambda>x. x - a) ` S)"
immler@69544
   711
using bounded_translation [of S "-a"] by simp
immler@69544
   712
immler@69544
   713
lemma bounded_uminus [simp]:
immler@69544
   714
  fixes X :: "'a::real_normed_vector set"
immler@69544
   715
  shows "bounded (uminus ` X) \<longleftrightarrow> bounded X"
immler@69544
   716
by (auto simp: bounded_def dist_norm; rule_tac x="-x" in exI; force simp: add.commute norm_minus_commute)
immler@69544
   717
immler@69544
   718
lemma uminus_bounded_comp [simp]:
immler@69544
   719
  fixes f :: "'a \<Rightarrow> 'b::real_normed_vector"
immler@69544
   720
  shows "bounded ((\<lambda>x. - f x) ` S) \<longleftrightarrow> bounded (f ` S)"
immler@69544
   721
  using bounded_uminus[of "f ` S"]
immler@69544
   722
  by (auto simp: image_image)
immler@69544
   723
immler@69544
   724
lemma bounded_plus_comp:
immler@69544
   725
  fixes f g::"'a \<Rightarrow> 'b::real_normed_vector"
immler@69544
   726
  assumes "bounded (f ` S)"
immler@69544
   727
  assumes "bounded (g ` S)"
immler@69544
   728
  shows "bounded ((\<lambda>x. f x + g x) ` S)"
immler@69544
   729
proof -
immler@69544
   730
  {
immler@69544
   731
    fix B C
immler@69544
   732
    assume "\<And>x. x\<in>S \<Longrightarrow> norm (f x) \<le> B" "\<And>x. x\<in>S \<Longrightarrow> norm (g x) \<le> C"
immler@69544
   733
    then have "\<And>x. x \<in> S \<Longrightarrow> norm (f x + g x) \<le> B + C"
immler@69544
   734
      by (auto intro!: norm_triangle_le add_mono)
immler@69544
   735
  } then show ?thesis
immler@69544
   736
    using assms by (fastforce simp: bounded_iff)
immler@69544
   737
qed
immler@69544
   738
immler@69544
   739
lemma bounded_plus:
immler@69544
   740
  fixes S ::"'a::real_normed_vector set"
immler@69544
   741
  assumes "bounded S" "bounded T"
immler@69544
   742
  shows "bounded ((\<lambda>(x,y). x + y) ` (S \<times> T))"
immler@69544
   743
  using bounded_plus_comp [of fst "S \<times> T" snd] assms
immler@69544
   744
  by (auto simp: split_def split: if_split_asm)
immler@69544
   745
immler@69544
   746
lemma bounded_minus_comp:
immler@69544
   747
  "bounded (f ` S) \<Longrightarrow> bounded (g ` S) \<Longrightarrow> bounded ((\<lambda>x. f x - g x) ` S)"
immler@69544
   748
  for f g::"'a \<Rightarrow> 'b::real_normed_vector"
immler@69544
   749
  using bounded_plus_comp[of "f" S "\<lambda>x. - g x"]
immler@69544
   750
  by auto
immler@69544
   751
immler@69544
   752
lemma bounded_minus:
immler@69544
   753
  fixes S ::"'a::real_normed_vector set"
immler@69544
   754
  assumes "bounded S" "bounded T"
immler@69544
   755
  shows "bounded ((\<lambda>(x,y). x - y) ` (S \<times> T))"
immler@69544
   756
  using bounded_minus_comp [of fst "S \<times> T" snd] assms
immler@69544
   757
  by (auto simp: split_def split: if_split_asm)
immler@69544
   758
immler@69544
   759
lemma not_bounded_UNIV[simp]:
immler@69544
   760
  "\<not> bounded (UNIV :: 'a::{real_normed_vector, perfect_space} set)"
immler@69544
   761
proof (auto simp: bounded_pos not_le)
immler@69544
   762
  obtain x :: 'a where "x \<noteq> 0"
immler@69544
   763
    using perfect_choose_dist [OF zero_less_one] by fast
immler@69544
   764
  fix b :: real
immler@69544
   765
  assume b: "b >0"
immler@69544
   766
  have b1: "b +1 \<ge> 0"
immler@69544
   767
    using b by simp
immler@69544
   768
  with \<open>x \<noteq> 0\<close> have "b < norm (scaleR (b + 1) (sgn x))"
immler@69544
   769
    by (simp add: norm_sgn)
immler@69544
   770
  then show "\<exists>x::'a. b < norm x" ..
immler@69544
   771
qed
immler@69544
   772
immler@69544
   773
corollary cobounded_imp_unbounded:
immler@69544
   774
    fixes S :: "'a::{real_normed_vector, perfect_space} set"
immler@69544
   775
    shows "bounded (- S) \<Longrightarrow> \<not> bounded S"
immler@69544
   776
  using bounded_Un [of S "-S"]  by (simp add: sup_compl_top)
immler@69544
   777
immler@69611
   778
subsection%unimportant\<open>Relations among convergence and absolute convergence for power series\<close>
immler@69611
   779
immler@69611
   780
lemma summable_imp_bounded:
immler@69611
   781
  fixes f :: "nat \<Rightarrow> 'a::real_normed_vector"
immler@69611
   782
  shows "summable f \<Longrightarrow> bounded (range f)"
immler@69611
   783
by (frule summable_LIMSEQ_zero) (simp add: convergent_imp_bounded)
immler@69611
   784
immler@69611
   785
lemma summable_imp_sums_bounded:
immler@69611
   786
   "summable f \<Longrightarrow> bounded (range (\<lambda>n. sum f {..<n}))"
immler@69611
   787
by (auto simp: summable_def sums_def dest: convergent_imp_bounded)
immler@69611
   788
immler@69611
   789
lemma power_series_conv_imp_absconv_weak:
immler@69611
   790
  fixes a:: "nat \<Rightarrow> 'a::{real_normed_div_algebra,banach}" and w :: 'a
immler@69611
   791
  assumes sum: "summable (\<lambda>n. a n * z ^ n)" and no: "norm w < norm z"
immler@69611
   792
    shows "summable (\<lambda>n. of_real(norm(a n)) * w ^ n)"
immler@69611
   793
proof -
immler@69611
   794
  obtain M where M: "\<And>x. norm (a x * z ^ x) \<le> M"
immler@69611
   795
    using summable_imp_bounded [OF sum] by (force simp: bounded_iff)
immler@69611
   796
  then have *: "summable (\<lambda>n. norm (a n) * norm w ^ n)"
immler@69611
   797
    by (rule_tac M=M in Abel_lemma) (auto simp: norm_mult norm_power intro: no)
immler@69611
   798
  show ?thesis
immler@69611
   799
    apply (rule series_comparison_complex [of "(\<lambda>n. of_real(norm(a n) * norm w ^ n))"])
immler@69611
   800
    apply (simp only: summable_complex_of_real *)
immler@69611
   801
    apply (auto simp: norm_mult norm_power)
immler@69611
   802
    done
immler@69611
   803
qed
immler@69611
   804
immler@69544
   805
immler@69544
   806
subsection \<open>Normed spaces with the Heine-Borel property\<close>
immler@69544
   807
immler@69544
   808
lemma not_compact_UNIV[simp]:
immler@69544
   809
  fixes s :: "'a::{real_normed_vector,perfect_space,heine_borel} set"
immler@69544
   810
  shows "\<not> compact (UNIV::'a set)"
immler@69544
   811
    by (simp add: compact_eq_bounded_closed)
immler@69544
   812
lp15@69918
   813
lemma not_compact_space_euclideanreal [simp]: "\<not> compact_space euclideanreal"
lp15@69918
   814
  by (simp add: compact_space_def)
lp15@69918
   815
immler@69544
   816
text\<open>Representing sets as the union of a chain of compact sets.\<close>
immler@69544
   817
lemma closed_Union_compact_subsets:
immler@69544
   818
  fixes S :: "'a::{heine_borel,real_normed_vector} set"
immler@69544
   819
  assumes "closed S"
immler@69544
   820
  obtains F where "\<And>n. compact(F n)" "\<And>n. F n \<subseteq> S" "\<And>n. F n \<subseteq> F(Suc n)"
immler@69544
   821
                  "(\<Union>n. F n) = S" "\<And>K. \<lbrakk>compact K; K \<subseteq> S\<rbrakk> \<Longrightarrow> \<exists>N. \<forall>n \<ge> N. K \<subseteq> F n"
immler@69544
   822
proof
immler@69544
   823
  show "compact (S \<inter> cball 0 (of_nat n))" for n
immler@69544
   824
    using assms compact_eq_bounded_closed by auto
immler@69544
   825
next
immler@69544
   826
  show "(\<Union>n. S \<inter> cball 0 (real n)) = S"
immler@69544
   827
    by (auto simp: real_arch_simple)
immler@69544
   828
next
immler@69544
   829
  fix K :: "'a set"
immler@69544
   830
  assume "compact K" "K \<subseteq> S"
immler@69544
   831
  then obtain N where "K \<subseteq> cball 0 N"
immler@69544
   832
    by (meson bounded_pos mem_cball_0 compact_imp_bounded subsetI)
immler@69544
   833
  then show "\<exists>N. \<forall>n\<ge>N. K \<subseteq> S \<inter> cball 0 (real n)"
immler@69544
   834
    by (metis of_nat_le_iff Int_subset_iff \<open>K \<subseteq> S\<close> real_arch_simple subset_cball subset_trans)
immler@69544
   835
qed auto
immler@69544
   836
immler@69611
   837
subsection \<open>Intersecting chains of compact sets and the Baire property\<close>
immler@69611
   838
immler@69611
   839
proposition bounded_closed_chain:
immler@69611
   840
  fixes \<F> :: "'a::heine_borel set set"
immler@69611
   841
  assumes "B \<in> \<F>" "bounded B" and \<F>: "\<And>S. S \<in> \<F> \<Longrightarrow> closed S" and "{} \<notin> \<F>"
immler@69611
   842
      and chain: "\<And>S T. S \<in> \<F> \<and> T \<in> \<F> \<Longrightarrow> S \<subseteq> T \<or> T \<subseteq> S"
immler@69611
   843
    shows "\<Inter>\<F> \<noteq> {}"
immler@69611
   844
proof -
immler@69611
   845
  have "B \<inter> \<Inter>\<F> \<noteq> {}"
immler@69611
   846
  proof (rule compact_imp_fip)
immler@69611
   847
    show "compact B" "\<And>T. T \<in> \<F> \<Longrightarrow> closed T"
immler@69611
   848
      by (simp_all add: assms compact_eq_bounded_closed)
immler@69611
   849
    show "\<lbrakk>finite \<G>; \<G> \<subseteq> \<F>\<rbrakk> \<Longrightarrow> B \<inter> \<Inter>\<G> \<noteq> {}" for \<G>
immler@69611
   850
    proof (induction \<G> rule: finite_induct)
immler@69611
   851
      case empty
immler@69611
   852
      with assms show ?case by force
immler@69611
   853
    next
immler@69611
   854
      case (insert U \<G>)
immler@69611
   855
      then have "U \<in> \<F>" and ne: "B \<inter> \<Inter>\<G> \<noteq> {}" by auto
immler@69611
   856
      then consider "B \<subseteq> U" | "U \<subseteq> B"
immler@69611
   857
          using \<open>B \<in> \<F>\<close> chain by blast
immler@69611
   858
        then show ?case
immler@69611
   859
        proof cases
immler@69611
   860
          case 1
immler@69611
   861
          then show ?thesis
immler@69611
   862
            using Int_left_commute ne by auto
immler@69611
   863
        next
immler@69611
   864
          case 2
immler@69611
   865
          have "U \<noteq> {}"
immler@69611
   866
            using \<open>U \<in> \<F>\<close> \<open>{} \<notin> \<F>\<close> by blast
immler@69611
   867
          moreover
immler@69611
   868
          have False if "\<And>x. x \<in> U \<Longrightarrow> \<exists>Y\<in>\<G>. x \<notin> Y"
immler@69611
   869
          proof -
immler@69611
   870
            have "\<And>x. x \<in> U \<Longrightarrow> \<exists>Y\<in>\<G>. Y \<subseteq> U"
immler@69611
   871
              by (metis chain contra_subsetD insert.prems insert_subset that)
immler@69611
   872
            then obtain Y where "Y \<in> \<G>" "Y \<subseteq> U"
immler@69611
   873
              by (metis all_not_in_conv \<open>U \<noteq> {}\<close>)
immler@69611
   874
            moreover obtain x where "x \<in> \<Inter>\<G>"
immler@69611
   875
              by (metis Int_emptyI ne)
immler@69611
   876
            ultimately show ?thesis
immler@69611
   877
              by (metis Inf_lower subset_eq that)
immler@69611
   878
          qed
immler@69611
   879
          with 2 show ?thesis
immler@69611
   880
            by blast
immler@69611
   881
        qed
immler@69611
   882
      qed
immler@69611
   883
  qed
immler@69611
   884
  then show ?thesis by blast
immler@69611
   885
qed
immler@69611
   886
immler@69611
   887
corollary compact_chain:
immler@69611
   888
  fixes \<F> :: "'a::heine_borel set set"
immler@69611
   889
  assumes "\<And>S. S \<in> \<F> \<Longrightarrow> compact S" "{} \<notin> \<F>"
immler@69611
   890
          "\<And>S T. S \<in> \<F> \<and> T \<in> \<F> \<Longrightarrow> S \<subseteq> T \<or> T \<subseteq> S"
immler@69611
   891
    shows "\<Inter> \<F> \<noteq> {}"
immler@69611
   892
proof (cases "\<F> = {}")
immler@69611
   893
  case True
immler@69611
   894
  then show ?thesis by auto
immler@69611
   895
next
immler@69611
   896
  case False
immler@69611
   897
  show ?thesis
immler@69611
   898
    by (metis False all_not_in_conv assms compact_imp_bounded compact_imp_closed bounded_closed_chain)
immler@69611
   899
qed
immler@69611
   900
immler@69611
   901
lemma compact_nest:
immler@69611
   902
  fixes F :: "'a::linorder \<Rightarrow> 'b::heine_borel set"
immler@69611
   903
  assumes F: "\<And>n. compact(F n)" "\<And>n. F n \<noteq> {}" and mono: "\<And>m n. m \<le> n \<Longrightarrow> F n \<subseteq> F m"
nipkow@69745
   904
  shows "\<Inter>(range F) \<noteq> {}"
immler@69611
   905
proof -
immler@69611
   906
  have *: "\<And>S T. S \<in> range F \<and> T \<in> range F \<Longrightarrow> S \<subseteq> T \<or> T \<subseteq> S"
immler@69611
   907
    by (metis mono image_iff le_cases)
immler@69611
   908
  show ?thesis
immler@69611
   909
    apply (rule compact_chain [OF _ _ *])
immler@69611
   910
    using F apply (blast intro: dest: *)+
immler@69611
   911
    done
immler@69611
   912
qed
immler@69611
   913
immler@69611
   914
text\<open>The Baire property of dense sets\<close>
immler@69611
   915
theorem Baire:
immler@69611
   916
  fixes S::"'a::{real_normed_vector,heine_borel} set"
immler@69611
   917
  assumes "closed S" "countable \<G>"
lp15@69922
   918
      and ope: "\<And>T. T \<in> \<G> \<Longrightarrow> openin (top_of_set S) T \<and> S \<subseteq> closure T"
immler@69611
   919
 shows "S \<subseteq> closure(\<Inter>\<G>)"
immler@69611
   920
proof (cases "\<G> = {}")
immler@69611
   921
  case True
immler@69611
   922
  then show ?thesis
immler@69611
   923
    using closure_subset by auto
immler@69611
   924
next
immler@69611
   925
  let ?g = "from_nat_into \<G>"
immler@69611
   926
  case False
immler@69611
   927
  then have gin: "?g n \<in> \<G>" for n
immler@69611
   928
    by (simp add: from_nat_into)
immler@69611
   929
  show ?thesis
immler@69611
   930
  proof (clarsimp simp: closure_approachable)
immler@69611
   931
    fix x and e::real
immler@69611
   932
    assume "x \<in> S" "0 < e"
lp15@69922
   933
    obtain TF where opeF: "\<And>n. openin (top_of_set S) (TF n)"
immler@69611
   934
               and ne: "\<And>n. TF n \<noteq> {}"
immler@69611
   935
               and subg: "\<And>n. S \<inter> closure(TF n) \<subseteq> ?g n"
immler@69611
   936
               and subball: "\<And>n. closure(TF n) \<subseteq> ball x e"
immler@69611
   937
               and decr: "\<And>n. TF(Suc n) \<subseteq> TF n"
immler@69611
   938
    proof -
lp15@69922
   939
      have *: "\<exists>Y. (openin (top_of_set S) Y \<and> Y \<noteq> {} \<and>
immler@69611
   940
                   S \<inter> closure Y \<subseteq> ?g n \<and> closure Y \<subseteq> ball x e) \<and> Y \<subseteq> U"
lp15@69922
   941
        if opeU: "openin (top_of_set S) U" and "U \<noteq> {}" and cloU: "closure U \<subseteq> ball x e" for U n
immler@69611
   942
      proof -
immler@69611
   943
        obtain T where T: "open T" "U = T \<inter> S"
lp15@69922
   944
          using \<open>openin (top_of_set S) U\<close> by (auto simp: openin_subtopology)
immler@69611
   945
        with \<open>U \<noteq> {}\<close> have "T \<inter> closure (?g n) \<noteq> {}"
immler@69611
   946
          using gin ope by fastforce
immler@69611
   947
        then have "T \<inter> ?g n \<noteq> {}"
immler@69611
   948
          using \<open>open T\<close> open_Int_closure_eq_empty by blast
immler@69611
   949
        then obtain y where "y \<in> U" "y \<in> ?g n"
immler@69611
   950
          using T ope [of "?g n", OF gin] by (blast dest:  openin_imp_subset)
lp15@69922
   951
        moreover have "openin (top_of_set S) (U \<inter> ?g n)"
immler@69611
   952
          using gin ope opeU by blast
immler@69611
   953
        ultimately obtain d where U: "U \<inter> ?g n \<subseteq> S" and "d > 0" and d: "ball y d \<inter> S \<subseteq> U \<inter> ?g n"
immler@69611
   954
          by (force simp: openin_contains_ball)
immler@69611
   955
        show ?thesis
immler@69611
   956
        proof (intro exI conjI)
lp15@69922
   957
          show "openin (top_of_set S) (S \<inter> ball y (d/2))"
immler@69611
   958
            by (simp add: openin_open_Int)
immler@69611
   959
          show "S \<inter> ball y (d/2) \<noteq> {}"
immler@69611
   960
            using \<open>0 < d\<close> \<open>y \<in> U\<close> opeU openin_imp_subset by fastforce
immler@69611
   961
          have "S \<inter> closure (S \<inter> ball y (d/2)) \<subseteq> S \<inter> closure (ball y (d/2))"
immler@69611
   962
            using closure_mono by blast
immler@69611
   963
          also have "... \<subseteq> ?g n"
immler@69611
   964
            using \<open>d > 0\<close> d by force
immler@69611
   965
          finally show "S \<inter> closure (S \<inter> ball y (d/2)) \<subseteq> ?g n" .
immler@69611
   966
          have "closure (S \<inter> ball y (d/2)) \<subseteq> S \<inter> ball y d"
immler@69611
   967
          proof -
immler@69611
   968
            have "closure (ball y (d/2)) \<subseteq> ball y d"
immler@69611
   969
              using \<open>d > 0\<close> by auto
immler@69611
   970
            then have "closure (S \<inter> ball y (d/2)) \<subseteq> ball y d"
immler@69611
   971
              by (meson closure_mono inf.cobounded2 subset_trans)
immler@69611
   972
            then show ?thesis
immler@69611
   973
              by (simp add: \<open>closed S\<close> closure_minimal)
immler@69611
   974
          qed
immler@69611
   975
          also have "...  \<subseteq> ball x e"
immler@69611
   976
            using cloU closure_subset d by blast
immler@69611
   977
          finally show "closure (S \<inter> ball y (d/2)) \<subseteq> ball x e" .
immler@69611
   978
          show "S \<inter> ball y (d/2) \<subseteq> U"
immler@69611
   979
            using ball_divide_subset_numeral d by blast
immler@69611
   980
        qed
immler@69611
   981
      qed
lp15@69922
   982
      let ?\<Phi> = "\<lambda>n X. openin (top_of_set S) X \<and> X \<noteq> {} \<and>
immler@69611
   983
                      S \<inter> closure X \<subseteq> ?g n \<and> closure X \<subseteq> ball x e"
immler@69611
   984
      have "closure (S \<inter> ball x (e / 2)) \<subseteq> closure(ball x (e/2))"
immler@69611
   985
        by (simp add: closure_mono)
immler@69611
   986
      also have "...  \<subseteq> ball x e"
immler@69611
   987
        using \<open>e > 0\<close> by auto
immler@69611
   988
      finally have "closure (S \<inter> ball x (e / 2)) \<subseteq> ball x e" .
lp15@69922
   989
      moreover have"openin (top_of_set S) (S \<inter> ball x (e / 2))" "S \<inter> ball x (e / 2) \<noteq> {}"
immler@69611
   990
        using \<open>0 < e\<close> \<open>x \<in> S\<close> by auto
immler@69611
   991
      ultimately obtain Y where Y: "?\<Phi> 0 Y \<and> Y \<subseteq> S \<inter> ball x (e / 2)"
immler@69611
   992
            using * [of "S \<inter> ball x (e/2)" 0] by metis
immler@69611
   993
      show thesis
immler@69611
   994
      proof (rule exE [OF dependent_nat_choice [of ?\<Phi> "\<lambda>n X Y. Y \<subseteq> X"]])
immler@69611
   995
        show "\<exists>x. ?\<Phi> 0 x"
immler@69611
   996
          using Y by auto
immler@69611
   997
        show "\<exists>Y. ?\<Phi> (Suc n) Y \<and> Y \<subseteq> X" if "?\<Phi> n X" for X n
immler@69611
   998
          using that by (blast intro: *)
immler@69611
   999
      qed (use that in metis)
immler@69611
  1000
    qed
immler@69611
  1001
    have "(\<Inter>n. S \<inter> closure (TF n)) \<noteq> {}"
immler@69611
  1002
    proof (rule compact_nest)
immler@69611
  1003
      show "\<And>n. compact (S \<inter> closure (TF n))"
immler@69611
  1004
        by (metis closed_closure subball bounded_subset_ballI compact_eq_bounded_closed closed_Int_compact [OF \<open>closed S\<close>])
immler@69611
  1005
      show "\<And>n. S \<inter> closure (TF n) \<noteq> {}"
immler@69611
  1006
        by (metis Int_absorb1 opeF \<open>closed S\<close> closure_eq_empty closure_minimal ne openin_imp_subset)
immler@69611
  1007
      show "\<And>m n. m \<le> n \<Longrightarrow> S \<inter> closure (TF n) \<subseteq> S \<inter> closure (TF m)"
immler@69611
  1008
        by (meson closure_mono decr dual_order.refl inf_mono lift_Suc_antimono_le)
immler@69611
  1009
    qed
immler@69611
  1010
    moreover have "(\<Inter>n. S \<inter> closure (TF n)) \<subseteq> {y \<in> \<Inter>\<G>. dist y x < e}"
immler@69611
  1011
    proof (clarsimp, intro conjI)
immler@69611
  1012
      fix y
immler@69611
  1013
      assume "y \<in> S" and y: "\<forall>n. y \<in> closure (TF n)"
immler@69611
  1014
      then show "\<forall>T\<in>\<G>. y \<in> T"
lp15@69712
  1015
        by (metis Int_iff from_nat_into_surj [OF \<open>countable \<G>\<close>] subsetD subg)
immler@69611
  1016
      show "dist y x < e"
immler@69611
  1017
        by (metis y dist_commute mem_ball subball subsetCE)
immler@69611
  1018
    qed
immler@69611
  1019
    ultimately show "\<exists>y \<in> \<Inter>\<G>. dist y x < e"
immler@69611
  1020
      by auto
immler@69611
  1021
  qed
immler@69611
  1022
qed
immler@69611
  1023
immler@69544
  1024
immler@69544
  1025
subsection \<open>Continuity\<close>
immler@69544
  1026
immler@69544
  1027
subsubsection%unimportant \<open>Structural rules for uniform continuity\<close>
immler@69544
  1028
immler@69613
  1029
lemma (in bounded_linear) uniformly_continuous_on[continuous_intros]:
immler@69613
  1030
  fixes g :: "_::metric_space \<Rightarrow> _"
immler@69613
  1031
  assumes "uniformly_continuous_on s g"
immler@69613
  1032
  shows "uniformly_continuous_on s (\<lambda>x. f (g x))"
immler@69613
  1033
  using assms unfolding uniformly_continuous_on_sequentially
immler@69613
  1034
  unfolding dist_norm tendsto_norm_zero_iff diff[symmetric]
immler@69613
  1035
  by (auto intro: tendsto_zero)
immler@69613
  1036
immler@69544
  1037
lemma uniformly_continuous_on_dist[continuous_intros]:
immler@69544
  1038
  fixes f g :: "'a::metric_space \<Rightarrow> 'b::metric_space"
immler@69544
  1039
  assumes "uniformly_continuous_on s f"
immler@69544
  1040
    and "uniformly_continuous_on s g"
immler@69544
  1041
  shows "uniformly_continuous_on s (\<lambda>x. dist (f x) (g x))"
immler@69544
  1042
proof -
immler@69544
  1043
  {
immler@69544
  1044
    fix a b c d :: 'b
immler@69544
  1045
    have "\<bar>dist a b - dist c d\<bar> \<le> dist a c + dist b d"
immler@69544
  1046
      using dist_triangle2 [of a b c] dist_triangle2 [of b c d]
immler@69544
  1047
      using dist_triangle3 [of c d a] dist_triangle [of a d b]
immler@69544
  1048
      by arith
immler@69544
  1049
  } note le = this
immler@69544
  1050
  {
immler@69544
  1051
    fix x y
immler@69544
  1052
    assume f: "(\<lambda>n. dist (f (x n)) (f (y n))) \<longlonglongrightarrow> 0"
immler@69544
  1053
    assume g: "(\<lambda>n. dist (g (x n)) (g (y n))) \<longlonglongrightarrow> 0"
immler@69544
  1054
    have "(\<lambda>n. \<bar>dist (f (x n)) (g (x n)) - dist (f (y n)) (g (y n))\<bar>) \<longlonglongrightarrow> 0"
immler@69544
  1055
      by (rule Lim_transform_bound [OF _ tendsto_add_zero [OF f g]],
immler@69544
  1056
        simp add: le)
immler@69544
  1057
  }
immler@69544
  1058
  then show ?thesis
immler@69544
  1059
    using assms unfolding uniformly_continuous_on_sequentially
immler@69544
  1060
    unfolding dist_real_def by simp
immler@69544
  1061
qed
immler@69544
  1062
immler@69544
  1063
lemma uniformly_continuous_on_norm[continuous_intros]:
immler@69544
  1064
  fixes f :: "'a :: metric_space \<Rightarrow> 'b :: real_normed_vector"
immler@69544
  1065
  assumes "uniformly_continuous_on s f"
immler@69544
  1066
  shows "uniformly_continuous_on s (\<lambda>x. norm (f x))"
immler@69544
  1067
  unfolding norm_conv_dist using assms
immler@69544
  1068
  by (intro uniformly_continuous_on_dist uniformly_continuous_on_const)
immler@69544
  1069
immler@69544
  1070
lemma uniformly_continuous_on_cmul[continuous_intros]:
immler@69544
  1071
  fixes f :: "'a::metric_space \<Rightarrow> 'b::real_normed_vector"
immler@69544
  1072
  assumes "uniformly_continuous_on s f"
immler@69544
  1073
  shows "uniformly_continuous_on s (\<lambda>x. c *\<^sub>R f(x))"
immler@69544
  1074
  using bounded_linear_scaleR_right assms
immler@69544
  1075
  by (rule bounded_linear.uniformly_continuous_on)
immler@69544
  1076
immler@69544
  1077
lemma dist_minus:
immler@69544
  1078
  fixes x y :: "'a::real_normed_vector"
immler@69544
  1079
  shows "dist (- x) (- y) = dist x y"
immler@69544
  1080
  unfolding dist_norm minus_diff_minus norm_minus_cancel ..
immler@69544
  1081
immler@69544
  1082
lemma uniformly_continuous_on_minus[continuous_intros]:
immler@69544
  1083
  fixes f :: "'a::metric_space \<Rightarrow> 'b::real_normed_vector"
immler@69544
  1084
  shows "uniformly_continuous_on s f \<Longrightarrow> uniformly_continuous_on s (\<lambda>x. - f x)"
immler@69544
  1085
  unfolding uniformly_continuous_on_def dist_minus .
immler@69544
  1086
immler@69544
  1087
lemma uniformly_continuous_on_add[continuous_intros]:
immler@69544
  1088
  fixes f g :: "'a::metric_space \<Rightarrow> 'b::real_normed_vector"
immler@69544
  1089
  assumes "uniformly_continuous_on s f"
immler@69544
  1090
    and "uniformly_continuous_on s g"
immler@69544
  1091
  shows "uniformly_continuous_on s (\<lambda>x. f x + g x)"
immler@69544
  1092
  using assms
immler@69544
  1093
  unfolding uniformly_continuous_on_sequentially
immler@69544
  1094
  unfolding dist_norm tendsto_norm_zero_iff add_diff_add
immler@69544
  1095
  by (auto intro: tendsto_add_zero)
immler@69544
  1096
immler@69544
  1097
lemma uniformly_continuous_on_diff[continuous_intros]:
immler@69544
  1098
  fixes f :: "'a::metric_space \<Rightarrow> 'b::real_normed_vector"
immler@69544
  1099
  assumes "uniformly_continuous_on s f"
immler@69544
  1100
    and "uniformly_continuous_on s g"
immler@69544
  1101
  shows "uniformly_continuous_on s (\<lambda>x. f x - g x)"
immler@69544
  1102
  using assms uniformly_continuous_on_add [of s f "- g"]
immler@69544
  1103
    by (simp add: fun_Compl_def uniformly_continuous_on_minus)
immler@69544
  1104
immler@69544
  1105
immler@69544
  1106
subsection%unimportant \<open>Topological properties of linear functions\<close>
immler@69544
  1107
immler@69544
  1108
lemma linear_lim_0:
immler@69544
  1109
  assumes "bounded_linear f"
immler@69544
  1110
  shows "(f \<longlongrightarrow> 0) (at (0))"
immler@69544
  1111
proof -
immler@69544
  1112
  interpret f: bounded_linear f by fact
immler@69544
  1113
  have "(f \<longlongrightarrow> f 0) (at 0)"
immler@69544
  1114
    using tendsto_ident_at by (rule f.tendsto)
immler@69544
  1115
  then show ?thesis unfolding f.zero .
immler@69544
  1116
qed
immler@69544
  1117
immler@69544
  1118
lemma linear_continuous_at:
immler@69544
  1119
  assumes "bounded_linear f"
immler@69544
  1120
  shows "continuous (at a) f"
immler@69544
  1121
  unfolding continuous_at using assms
immler@69544
  1122
  apply (rule bounded_linear.tendsto)
immler@69544
  1123
  apply (rule tendsto_ident_at)
immler@69544
  1124
  done
immler@69544
  1125
immler@69544
  1126
lemma linear_continuous_within:
immler@69544
  1127
  "bounded_linear f \<Longrightarrow> continuous (at x within s) f"
immler@69544
  1128
  using continuous_at_imp_continuous_within[of x f s] using linear_continuous_at[of f] by auto
immler@69544
  1129
immler@69544
  1130
lemma linear_continuous_on:
immler@69544
  1131
  "bounded_linear f \<Longrightarrow> continuous_on s f"
immler@69544
  1132
  using continuous_at_imp_continuous_on[of s f] using linear_continuous_at[of f] by auto
immler@69544
  1133
immler@69613
  1134
subsection%unimportant \<open>Arithmetic Preserves Topological Properties\<close>
immler@69613
  1135
immler@69613
  1136
lemma open_scaling[intro]:
immler@69613
  1137
  fixes s :: "'a::real_normed_vector set"
immler@69613
  1138
  assumes "c \<noteq> 0"
immler@69613
  1139
    and "open s"
immler@69613
  1140
  shows "open((\<lambda>x. c *\<^sub>R x) ` s)"
immler@69613
  1141
proof -
immler@69613
  1142
  {
immler@69613
  1143
    fix x
immler@69613
  1144
    assume "x \<in> s"
immler@69613
  1145
    then obtain e where "e>0"
immler@69613
  1146
      and e:"\<forall>x'. dist x' x < e \<longrightarrow> x' \<in> s" using assms(2)[unfolded open_dist, THEN bspec[where x=x]]
immler@69613
  1147
      by auto
immler@69613
  1148
    have "e * \<bar>c\<bar> > 0"
immler@69613
  1149
      using assms(1)[unfolded zero_less_abs_iff[symmetric]] \<open>e>0\<close> by auto
immler@69613
  1150
    moreover
immler@69613
  1151
    {
immler@69613
  1152
      fix y
immler@69613
  1153
      assume "dist y (c *\<^sub>R x) < e * \<bar>c\<bar>"
immler@69613
  1154
      then have "norm ((1 / c) *\<^sub>R y - x) < e"
immler@69613
  1155
        unfolding dist_norm
immler@69613
  1156
        using norm_scaleR[of c "(1 / c) *\<^sub>R y - x", unfolded scaleR_right_diff_distrib, unfolded scaleR_scaleR] assms(1)
immler@69613
  1157
          assms(1)[unfolded zero_less_abs_iff[symmetric]] by (simp del:zero_less_abs_iff)
immler@69613
  1158
      then have "y \<in> (*\<^sub>R) c ` s"
immler@69613
  1159
        using rev_image_eqI[of "(1 / c) *\<^sub>R y" s y "(*\<^sub>R) c"]
immler@69613
  1160
        using e[THEN spec[where x="(1 / c) *\<^sub>R y"]]
immler@69613
  1161
        using assms(1)
immler@69613
  1162
        unfolding dist_norm scaleR_scaleR
immler@69613
  1163
        by auto
immler@69613
  1164
    }
immler@69613
  1165
    ultimately have "\<exists>e>0. \<forall>x'. dist x' (c *\<^sub>R x) < e \<longrightarrow> x' \<in> (*\<^sub>R) c ` s"
immler@69613
  1166
      apply (rule_tac x="e * \<bar>c\<bar>" in exI, auto)
immler@69613
  1167
      done
immler@69613
  1168
  }
immler@69613
  1169
  then show ?thesis unfolding open_dist by auto
immler@69613
  1170
qed
immler@69613
  1171
immler@69613
  1172
lemma minus_image_eq_vimage:
immler@69613
  1173
  fixes A :: "'a::ab_group_add set"
immler@69613
  1174
  shows "(\<lambda>x. - x) ` A = (\<lambda>x. - x) -` A"
immler@69613
  1175
  by (auto intro!: image_eqI [where f="\<lambda>x. - x"])
immler@69613
  1176
immler@69613
  1177
lemma open_negations:
immler@69613
  1178
  fixes S :: "'a::real_normed_vector set"
immler@69613
  1179
  shows "open S \<Longrightarrow> open ((\<lambda>x. - x) ` S)"
immler@69613
  1180
  using open_scaling [of "- 1" S] by simp
immler@69613
  1181
immler@69613
  1182
lemma open_translation:
immler@69613
  1183
  fixes S :: "'a::real_normed_vector set"
immler@69613
  1184
  assumes "open S"
immler@69613
  1185
  shows "open((\<lambda>x. a + x) ` S)"
immler@69613
  1186
proof -
immler@69613
  1187
  {
immler@69613
  1188
    fix x
immler@69613
  1189
    have "continuous (at x) (\<lambda>x. x - a)"
immler@69613
  1190
      by (intro continuous_diff continuous_ident continuous_const)
immler@69613
  1191
  }
immler@69613
  1192
  moreover have "{x. x - a \<in> S} = (+) a ` S"
immler@69613
  1193
    by force
immler@69613
  1194
  ultimately show ?thesis
immler@69613
  1195
    by (metis assms continuous_open_vimage vimage_def)
immler@69613
  1196
qed
immler@69613
  1197
immler@69613
  1198
lemma open_neg_translation:
immler@69613
  1199
  fixes s :: "'a::real_normed_vector set"
immler@69613
  1200
  assumes "open s"
immler@69613
  1201
  shows "open((\<lambda>x. a - x) ` s)"
immler@69613
  1202
  using open_translation[OF open_negations[OF assms], of a]
immler@69613
  1203
  by (auto simp: image_image)
immler@69613
  1204
immler@69613
  1205
lemma open_affinity:
immler@69613
  1206
  fixes S :: "'a::real_normed_vector set"
immler@69613
  1207
  assumes "open S"  "c \<noteq> 0"
immler@69613
  1208
  shows "open ((\<lambda>x. a + c *\<^sub>R x) ` S)"
immler@69613
  1209
proof -
immler@69613
  1210
  have *: "(\<lambda>x. a + c *\<^sub>R x) = (\<lambda>x. a + x) \<circ> (\<lambda>x. c *\<^sub>R x)"
immler@69613
  1211
    unfolding o_def ..
immler@69613
  1212
  have "(+) a ` (*\<^sub>R) c ` S = ((+) a \<circ> (*\<^sub>R) c) ` S"
immler@69613
  1213
    by auto
immler@69613
  1214
  then show ?thesis
immler@69613
  1215
    using assms open_translation[of "(*\<^sub>R) c ` S" a]
immler@69613
  1216
    unfolding *
immler@69613
  1217
    by auto
immler@69613
  1218
qed
immler@69613
  1219
immler@69613
  1220
lemma interior_translation:
haftmann@69661
  1221
  "interior ((+) a ` S) = (+) a ` (interior S)" for S :: "'a::real_normed_vector set"
immler@69613
  1222
proof (rule set_eqI, rule)
immler@69613
  1223
  fix x
immler@69613
  1224
  assume "x \<in> interior ((+) a ` S)"
immler@69613
  1225
  then obtain e where "e > 0" and e: "ball x e \<subseteq> (+) a ` S"
immler@69613
  1226
    unfolding mem_interior by auto
immler@69613
  1227
  then have "ball (x - a) e \<subseteq> S"
immler@69613
  1228
    unfolding subset_eq Ball_def mem_ball dist_norm
immler@69613
  1229
    by (auto simp: diff_diff_eq)
immler@69613
  1230
  then show "x \<in> (+) a ` interior S"
immler@69613
  1231
    unfolding image_iff
immler@69613
  1232
    apply (rule_tac x="x - a" in bexI)
immler@69613
  1233
    unfolding mem_interior
immler@69613
  1234
    using \<open>e > 0\<close>
immler@69613
  1235
    apply auto
immler@69613
  1236
    done
immler@69613
  1237
next
immler@69613
  1238
  fix x
immler@69613
  1239
  assume "x \<in> (+) a ` interior S"
immler@69613
  1240
  then obtain y e where "e > 0" and e: "ball y e \<subseteq> S" and y: "x = a + y"
immler@69613
  1241
    unfolding image_iff Bex_def mem_interior by auto
immler@69613
  1242
  {
immler@69613
  1243
    fix z
immler@69613
  1244
    have *: "a + y - z = y + a - z" by auto
immler@69613
  1245
    assume "z \<in> ball x e"
immler@69613
  1246
    then have "z - a \<in> S"
immler@69613
  1247
      using e[unfolded subset_eq, THEN bspec[where x="z - a"]]
immler@69613
  1248
      unfolding mem_ball dist_norm y group_add_class.diff_diff_eq2 *
immler@69613
  1249
      by auto
immler@69613
  1250
    then have "z \<in> (+) a ` S"
immler@69613
  1251
      unfolding image_iff by (auto intro!: bexI[where x="z - a"])
immler@69613
  1252
  }
immler@69613
  1253
  then have "ball x e \<subseteq> (+) a ` S"
immler@69613
  1254
    unfolding subset_eq by auto
immler@69613
  1255
  then show "x \<in> interior ((+) a ` S)"
immler@69613
  1256
    unfolding mem_interior using \<open>e > 0\<close> by auto
immler@69613
  1257
qed
immler@69613
  1258
haftmann@69661
  1259
lemma interior_translation_subtract:
haftmann@69661
  1260
  "interior ((\<lambda>x. x - a) ` S) = (\<lambda>x. x - a) ` interior S" for S :: "'a::real_normed_vector set"
haftmann@69661
  1261
  using interior_translation [of "- a"] by (simp cong: image_cong_simp)
haftmann@69661
  1262
haftmann@69661
  1263
immler@69613
  1264
lemma compact_scaling:
immler@69613
  1265
  fixes s :: "'a::real_normed_vector set"
immler@69613
  1266
  assumes "compact s"
immler@69613
  1267
  shows "compact ((\<lambda>x. c *\<^sub>R x) ` s)"
immler@69613
  1268
proof -
immler@69613
  1269
  let ?f = "\<lambda>x. scaleR c x"
immler@69613
  1270
  have *: "bounded_linear ?f" by (rule bounded_linear_scaleR_right)
immler@69613
  1271
  show ?thesis
immler@69613
  1272
    using compact_continuous_image[of s ?f] continuous_at_imp_continuous_on[of s ?f]
immler@69613
  1273
    using linear_continuous_at[OF *] assms
immler@69613
  1274
    by auto
immler@69613
  1275
qed
immler@69613
  1276
immler@69613
  1277
lemma compact_negations:
immler@69613
  1278
  fixes s :: "'a::real_normed_vector set"
immler@69613
  1279
  assumes "compact s"
immler@69613
  1280
  shows "compact ((\<lambda>x. - x) ` s)"
immler@69613
  1281
  using compact_scaling [OF assms, of "- 1"] by auto
immler@69613
  1282
immler@69613
  1283
lemma compact_sums:
immler@69613
  1284
  fixes s t :: "'a::real_normed_vector set"
immler@69613
  1285
  assumes "compact s"
immler@69613
  1286
    and "compact t"
immler@69613
  1287
  shows "compact {x + y | x y. x \<in> s \<and> y \<in> t}"
immler@69613
  1288
proof -
immler@69613
  1289
  have *: "{x + y | x y. x \<in> s \<and> y \<in> t} = (\<lambda>z. fst z + snd z) ` (s \<times> t)"
immler@69613
  1290
    apply auto
immler@69613
  1291
    unfolding image_iff
immler@69613
  1292
    apply (rule_tac x="(xa, y)" in bexI)
immler@69613
  1293
    apply auto
immler@69613
  1294
    done
immler@69613
  1295
  have "continuous_on (s \<times> t) (\<lambda>z. fst z + snd z)"
immler@69613
  1296
    unfolding continuous_on by (rule ballI) (intro tendsto_intros)
immler@69613
  1297
  then show ?thesis
immler@69613
  1298
    unfolding * using compact_continuous_image compact_Times [OF assms] by auto
immler@69613
  1299
qed
immler@69613
  1300
immler@69613
  1301
lemma compact_differences:
immler@69613
  1302
  fixes s t :: "'a::real_normed_vector set"
immler@69613
  1303
  assumes "compact s"
immler@69613
  1304
    and "compact t"
immler@69613
  1305
  shows "compact {x - y | x y. x \<in> s \<and> y \<in> t}"
immler@69613
  1306
proof-
immler@69613
  1307
  have "{x - y | x y. x\<in>s \<and> y \<in> t} =  {x + y | x y. x \<in> s \<and> y \<in> (uminus ` t)}"
immler@69613
  1308
    apply auto
immler@69613
  1309
    apply (rule_tac x= xa in exI, auto)
immler@69613
  1310
    done
immler@69613
  1311
  then show ?thesis
immler@69613
  1312
    using compact_sums[OF assms(1) compact_negations[OF assms(2)]] by auto
immler@69613
  1313
qed
immler@69613
  1314
immler@69613
  1315
lemma compact_translation:
haftmann@69661
  1316
  "compact ((+) a ` s)" if "compact s" for s :: "'a::real_normed_vector set"
immler@69613
  1317
proof -
immler@69613
  1318
  have "{x + y |x y. x \<in> s \<and> y \<in> {a}} = (\<lambda>x. a + x) ` s"
immler@69613
  1319
    by auto
immler@69613
  1320
  then show ?thesis
haftmann@69661
  1321
    using compact_sums [OF that compact_sing [of a]] by auto
immler@69613
  1322
qed
immler@69613
  1323
haftmann@69661
  1324
lemma compact_translation_subtract:
haftmann@69661
  1325
  "compact ((\<lambda>x. x - a) ` s)" if "compact s" for s :: "'a::real_normed_vector set"
haftmann@69661
  1326
  using that compact_translation [of s "- a"] by (simp cong: image_cong_simp)
haftmann@69661
  1327
immler@69613
  1328
lemma compact_affinity:
immler@69613
  1329
  fixes s :: "'a::real_normed_vector set"
immler@69613
  1330
  assumes "compact s"
immler@69613
  1331
  shows "compact ((\<lambda>x. a + c *\<^sub>R x) ` s)"
immler@69613
  1332
proof -
immler@69613
  1333
  have "(+) a ` (*\<^sub>R) c ` s = (\<lambda>x. a + c *\<^sub>R x) ` s"
immler@69613
  1334
    by auto
immler@69613
  1335
  then show ?thesis
immler@69613
  1336
    using compact_translation[OF compact_scaling[OF assms], of a c] by auto
immler@69613
  1337
qed
immler@69613
  1338
immler@69613
  1339
lemma closed_scaling:
immler@69613
  1340
  fixes S :: "'a::real_normed_vector set"
immler@69613
  1341
  assumes "closed S"
immler@69613
  1342
  shows "closed ((\<lambda>x. c *\<^sub>R x) ` S)"
immler@69613
  1343
proof (cases "c = 0")
immler@69613
  1344
  case True then show ?thesis
immler@69613
  1345
    by (auto simp: image_constant_conv)
immler@69613
  1346
next
immler@69613
  1347
  case False
immler@69613
  1348
  from assms have "closed ((\<lambda>x. inverse c *\<^sub>R x) -` S)"
immler@69613
  1349
    by (simp add: continuous_closed_vimage)
immler@69613
  1350
  also have "(\<lambda>x. inverse c *\<^sub>R x) -` S = (\<lambda>x. c *\<^sub>R x) ` S"
immler@69613
  1351
    using \<open>c \<noteq> 0\<close> by (auto elim: image_eqI [rotated])
immler@69613
  1352
  finally show ?thesis .
immler@69613
  1353
qed
immler@69613
  1354
immler@69613
  1355
lemma closed_negations:
immler@69613
  1356
  fixes S :: "'a::real_normed_vector set"
immler@69613
  1357
  assumes "closed S"
immler@69613
  1358
  shows "closed ((\<lambda>x. -x) ` S)"
immler@69613
  1359
  using closed_scaling[OF assms, of "- 1"] by simp
immler@69613
  1360
immler@69613
  1361
lemma compact_closed_sums:
immler@69613
  1362
  fixes S :: "'a::real_normed_vector set"
immler@69613
  1363
  assumes "compact S" and "closed T"
immler@69613
  1364
  shows "closed (\<Union>x\<in> S. \<Union>y \<in> T. {x + y})"
immler@69613
  1365
proof -
immler@69613
  1366
  let ?S = "{x + y |x y. x \<in> S \<and> y \<in> T}"
immler@69613
  1367
  {
immler@69613
  1368
    fix x l
immler@69613
  1369
    assume as: "\<forall>n. x n \<in> ?S"  "(x \<longlongrightarrow> l) sequentially"
immler@69613
  1370
    from as(1) obtain f where f: "\<forall>n. x n = fst (f n) + snd (f n)"  "\<forall>n. fst (f n) \<in> S"  "\<forall>n. snd (f n) \<in> T"
immler@69613
  1371
      using choice[of "\<lambda>n y. x n = (fst y) + (snd y) \<and> fst y \<in> S \<and> snd y \<in> T"] by auto
immler@69613
  1372
    obtain l' r where "l'\<in>S" and r: "strict_mono r" and lr: "(((\<lambda>n. fst (f n)) \<circ> r) \<longlongrightarrow> l') sequentially"
immler@69613
  1373
      using assms(1)[unfolded compact_def, THEN spec[where x="\<lambda> n. fst (f n)"]] using f(2) by auto
immler@69613
  1374
    have "((\<lambda>n. snd (f (r n))) \<longlongrightarrow> l - l') sequentially"
immler@69613
  1375
      using tendsto_diff[OF LIMSEQ_subseq_LIMSEQ[OF as(2) r] lr] and f(1)
immler@69613
  1376
      unfolding o_def
immler@69613
  1377
      by auto
immler@69613
  1378
    then have "l - l' \<in> T"
immler@69613
  1379
      using assms(2)[unfolded closed_sequential_limits,
immler@69613
  1380
        THEN spec[where x="\<lambda> n. snd (f (r n))"],
immler@69613
  1381
        THEN spec[where x="l - l'"]]
immler@69613
  1382
      using f(3)
immler@69613
  1383
      by auto
immler@69613
  1384
    then have "l \<in> ?S"
immler@69613
  1385
      using \<open>l' \<in> S\<close>
immler@69613
  1386
      apply auto
immler@69613
  1387
      apply (rule_tac x=l' in exI)
immler@69613
  1388
      apply (rule_tac x="l - l'" in exI, auto)
immler@69613
  1389
      done
immler@69613
  1390
  }
immler@69613
  1391
  moreover have "?S = (\<Union>x\<in> S. \<Union>y \<in> T. {x + y})"
immler@69613
  1392
    by force
immler@69613
  1393
  ultimately show ?thesis
immler@69613
  1394
    unfolding closed_sequential_limits
immler@69613
  1395
    by (metis (no_types, lifting))
immler@69613
  1396
qed
immler@69613
  1397
immler@69613
  1398
lemma closed_compact_sums:
immler@69613
  1399
  fixes S T :: "'a::real_normed_vector set"
immler@69613
  1400
  assumes "closed S" "compact T"
immler@69613
  1401
  shows "closed (\<Union>x\<in> S. \<Union>y \<in> T. {x + y})"
immler@69613
  1402
proof -
immler@69613
  1403
  have "(\<Union>x\<in> T. \<Union>y \<in> S. {x + y}) = (\<Union>x\<in> S. \<Union>y \<in> T. {x + y})"
immler@69613
  1404
    by auto
immler@69613
  1405
  then show ?thesis
immler@69613
  1406
    using compact_closed_sums[OF assms(2,1)] by simp
immler@69613
  1407
qed
immler@69613
  1408
immler@69613
  1409
lemma compact_closed_differences:
immler@69613
  1410
  fixes S T :: "'a::real_normed_vector set"
immler@69613
  1411
  assumes "compact S" "closed T"
immler@69613
  1412
  shows "closed (\<Union>x\<in> S. \<Union>y \<in> T. {x - y})"
immler@69613
  1413
proof -
immler@69613
  1414
  have "(\<Union>x\<in> S. \<Union>y \<in> uminus ` T. {x + y}) = (\<Union>x\<in> S. \<Union>y \<in> T. {x - y})"
immler@69613
  1415
    by force
immler@69613
  1416
  then show ?thesis
immler@69613
  1417
    using compact_closed_sums[OF assms(1) closed_negations[OF assms(2)]] by auto
immler@69613
  1418
qed
immler@69613
  1419
immler@69613
  1420
lemma closed_compact_differences:
immler@69613
  1421
  fixes S T :: "'a::real_normed_vector set"
immler@69613
  1422
  assumes "closed S" "compact T"
immler@69613
  1423
  shows "closed (\<Union>x\<in> S. \<Union>y \<in> T. {x - y})"
immler@69613
  1424
proof -
immler@69613
  1425
  have "(\<Union>x\<in> S. \<Union>y \<in> uminus ` T. {x + y}) = {x - y |x y. x \<in> S \<and> y \<in> T}"
immler@69613
  1426
    by auto
immler@69613
  1427
 then show ?thesis
immler@69613
  1428
  using closed_compact_sums[OF assms(1) compact_negations[OF assms(2)]] by simp
immler@69613
  1429
qed
immler@69613
  1430
immler@69613
  1431
lemma closed_translation:
haftmann@69661
  1432
  "closed ((+) a ` S)" if "closed S" for a :: "'a::real_normed_vector"
immler@69613
  1433
proof -
immler@69613
  1434
  have "(\<Union>x\<in> {a}. \<Union>y \<in> S. {x + y}) = ((+) a ` S)" by auto
immler@69613
  1435
  then show ?thesis
haftmann@69661
  1436
    using compact_closed_sums [OF compact_sing [of a] that] by auto
immler@69613
  1437
qed
immler@69613
  1438
haftmann@69661
  1439
lemma closed_translation_subtract:
haftmann@69661
  1440
  "closed ((\<lambda>x. x - a) ` S)" if "closed S" for a :: "'a::real_normed_vector"
haftmann@69661
  1441
  using that closed_translation [of S "- a"] by (simp cong: image_cong_simp)
haftmann@69661
  1442
immler@69613
  1443
lemma closure_translation:
haftmann@69661
  1444
  "closure ((+) a ` s) = (+) a ` closure s" for a :: "'a::real_normed_vector"
immler@69613
  1445
proof -
immler@69613
  1446
  have *: "(+) a ` (- s) = - (+) a ` s"
haftmann@69661
  1447
    by (auto intro!: image_eqI [where x = "x - a" for x])
immler@69613
  1448
  show ?thesis
haftmann@69661
  1449
    using interior_translation [of a "- s", symmetric]
haftmann@69661
  1450
    by (simp add: closure_interior translation_Compl *)
immler@69613
  1451
qed
immler@69613
  1452
haftmann@69661
  1453
lemma closure_translation_subtract:
haftmann@69661
  1454
  "closure ((\<lambda>x. x - a) ` s) = (\<lambda>x. x - a) ` closure s" for a :: "'a::real_normed_vector"
haftmann@69661
  1455
  using closure_translation [of "- a" s] by (simp cong: image_cong_simp)
haftmann@69661
  1456
immler@69613
  1457
lemma frontier_translation:
haftmann@69661
  1458
  "frontier ((+) a ` s) = (+) a ` frontier s" for a :: "'a::real_normed_vector"
haftmann@69661
  1459
  by (auto simp add: frontier_def translation_diff interior_translation closure_translation)
haftmann@69661
  1460
haftmann@69661
  1461
lemma frontier_translation_subtract:
haftmann@69661
  1462
  "frontier ((+) a ` s) = (+) a ` frontier s" for a :: "'a::real_normed_vector"
haftmann@69661
  1463
  by (auto simp add: frontier_def translation_diff interior_translation closure_translation)
immler@69613
  1464
immler@69613
  1465
lemma sphere_translation:
haftmann@69661
  1466
  "sphere (a + c) r = (+) a ` sphere c r" for a :: "'n::real_normed_vector"
haftmann@69661
  1467
  by (auto simp: dist_norm algebra_simps intro!: image_eqI [where x = "x - a" for x])
haftmann@69661
  1468
haftmann@69661
  1469
lemma sphere_translation_subtract:
haftmann@69661
  1470
  "sphere (c - a) r = (\<lambda>x. x - a) ` sphere c r" for a :: "'n::real_normed_vector"
haftmann@69661
  1471
  using sphere_translation [of "- a" c] by (simp cong: image_cong_simp)
immler@69613
  1472
immler@69613
  1473
lemma cball_translation:
haftmann@69661
  1474
  "cball (a + c) r = (+) a ` cball c r" for a :: "'n::real_normed_vector"
haftmann@69661
  1475
  by (auto simp: dist_norm algebra_simps intro!: image_eqI [where x = "x - a" for x])
haftmann@69661
  1476
haftmann@69661
  1477
lemma cball_translation_subtract:
haftmann@69661
  1478
  "cball (c - a) r = (\<lambda>x. x - a) ` cball c r" for a :: "'n::real_normed_vector"
haftmann@69661
  1479
  using cball_translation [of "- a" c] by (simp cong: image_cong_simp)
immler@69613
  1480
immler@69613
  1481
lemma ball_translation:
haftmann@69661
  1482
  "ball (a + c) r = (+) a ` ball c r" for a :: "'n::real_normed_vector"
haftmann@69661
  1483
  by (auto simp: dist_norm algebra_simps intro!: image_eqI [where x = "x - a" for x])
haftmann@69661
  1484
haftmann@69661
  1485
lemma ball_translation_subtract:
haftmann@69661
  1486
  "ball (c - a) r = (\<lambda>x. x - a) ` ball c r" for a :: "'n::real_normed_vector"
haftmann@69661
  1487
  using ball_translation [of "- a" c] by (simp cong: image_cong_simp)
immler@69613
  1488
immler@69613
  1489
immler@69613
  1490
subsection%unimportant\<open>Homeomorphisms\<close>
immler@69613
  1491
immler@69613
  1492
lemma homeomorphic_scaling:
immler@69613
  1493
  fixes s :: "'a::real_normed_vector set"
immler@69613
  1494
  assumes "c \<noteq> 0"
immler@69613
  1495
  shows "s homeomorphic ((\<lambda>x. c *\<^sub>R x) ` s)"
immler@69613
  1496
  unfolding homeomorphic_minimal
immler@69613
  1497
  apply (rule_tac x="\<lambda>x. c *\<^sub>R x" in exI)
immler@69613
  1498
  apply (rule_tac x="\<lambda>x. (1 / c) *\<^sub>R x" in exI)
immler@69613
  1499
  using assms
immler@69613
  1500
  apply (auto simp: continuous_intros)
immler@69613
  1501
  done
immler@69613
  1502
immler@69613
  1503
lemma homeomorphic_translation:
immler@69613
  1504
  fixes s :: "'a::real_normed_vector set"
immler@69613
  1505
  shows "s homeomorphic ((\<lambda>x. a + x) ` s)"
immler@69613
  1506
  unfolding homeomorphic_minimal
immler@69613
  1507
  apply (rule_tac x="\<lambda>x. a + x" in exI)
immler@69613
  1508
  apply (rule_tac x="\<lambda>x. -a + x" in exI)
immler@69613
  1509
  using continuous_on_add [OF continuous_on_const continuous_on_id, of s a]
immler@69613
  1510
    continuous_on_add [OF continuous_on_const continuous_on_id, of "plus a ` s" "- a"]
immler@69613
  1511
  apply auto
immler@69613
  1512
  done
immler@69613
  1513
immler@69613
  1514
lemma homeomorphic_affinity:
immler@69613
  1515
  fixes s :: "'a::real_normed_vector set"
immler@69613
  1516
  assumes "c \<noteq> 0"
immler@69613
  1517
  shows "s homeomorphic ((\<lambda>x. a + c *\<^sub>R x) ` s)"
immler@69613
  1518
proof -
immler@69613
  1519
  have *: "(+) a ` (*\<^sub>R) c ` s = (\<lambda>x. a + c *\<^sub>R x) ` s" by auto
immler@69613
  1520
  show ?thesis
immler@69613
  1521
    using homeomorphic_trans
immler@69613
  1522
    using homeomorphic_scaling[OF assms, of s]
immler@69613
  1523
    using homeomorphic_translation[of "(\<lambda>x. c *\<^sub>R x) ` s" a]
immler@69613
  1524
    unfolding *
immler@69613
  1525
    by auto
immler@69613
  1526
qed
immler@69613
  1527
immler@69613
  1528
lemma homeomorphic_balls:
immler@69613
  1529
  fixes a b ::"'a::real_normed_vector"
immler@69613
  1530
  assumes "0 < d"  "0 < e"
immler@69613
  1531
  shows "(ball a d) homeomorphic  (ball b e)" (is ?th)
immler@69613
  1532
    and "(cball a d) homeomorphic (cball b e)" (is ?cth)
immler@69613
  1533
proof -
immler@69613
  1534
  show ?th unfolding homeomorphic_minimal
immler@69613
  1535
    apply(rule_tac x="\<lambda>x. b + (e/d) *\<^sub>R (x - a)" in exI)
immler@69613
  1536
    apply(rule_tac x="\<lambda>x. a + (d/e) *\<^sub>R (x - b)" in exI)
immler@69613
  1537
    using assms
immler@69613
  1538
    apply (auto intro!: continuous_intros
immler@69613
  1539
      simp: dist_commute dist_norm pos_divide_less_eq mult_strict_left_mono)
immler@69613
  1540
    done
immler@69613
  1541
  show ?cth unfolding homeomorphic_minimal
immler@69613
  1542
    apply(rule_tac x="\<lambda>x. b + (e/d) *\<^sub>R (x - a)" in exI)
immler@69613
  1543
    apply(rule_tac x="\<lambda>x. a + (d/e) *\<^sub>R (x - b)" in exI)
immler@69613
  1544
    using assms
immler@69613
  1545
    apply (auto intro!: continuous_intros
immler@69613
  1546
      simp: dist_commute dist_norm pos_divide_le_eq mult_strict_left_mono)
immler@69613
  1547
    done
immler@69613
  1548
qed
immler@69613
  1549
immler@69613
  1550
lemma homeomorphic_spheres:
immler@69613
  1551
  fixes a b ::"'a::real_normed_vector"
immler@69613
  1552
  assumes "0 < d"  "0 < e"
immler@69613
  1553
  shows "(sphere a d) homeomorphic (sphere b e)"
immler@69613
  1554
unfolding homeomorphic_minimal
immler@69613
  1555
    apply(rule_tac x="\<lambda>x. b + (e/d) *\<^sub>R (x - a)" in exI)
immler@69613
  1556
    apply(rule_tac x="\<lambda>x. a + (d/e) *\<^sub>R (x - b)" in exI)
immler@69613
  1557
    using assms
immler@69613
  1558
    apply (auto intro!: continuous_intros
immler@69613
  1559
      simp: dist_commute dist_norm pos_divide_less_eq mult_strict_left_mono)
immler@69613
  1560
    done
immler@69613
  1561
immler@69613
  1562
lemma homeomorphic_ball01_UNIV:
immler@69613
  1563
  "ball (0::'a::real_normed_vector) 1 homeomorphic (UNIV:: 'a set)"
immler@69613
  1564
  (is "?B homeomorphic ?U")
immler@69613
  1565
proof
immler@69613
  1566
  have "x \<in> (\<lambda>z. z /\<^sub>R (1 - norm z)) ` ball 0 1" for x::'a
immler@69613
  1567
    apply (rule_tac x="x /\<^sub>R (1 + norm x)" in image_eqI)
immler@69613
  1568
     apply (auto simp: divide_simps)
immler@69613
  1569
    using norm_ge_zero [of x] apply linarith+
immler@69613
  1570
    done
immler@69613
  1571
  then show "(\<lambda>z::'a. z /\<^sub>R (1 - norm z)) ` ?B = ?U"
immler@69613
  1572
    by blast
immler@69613
  1573
  have "x \<in> range (\<lambda>z. (1 / (1 + norm z)) *\<^sub>R z)" if "norm x < 1" for x::'a
immler@69613
  1574
    apply (rule_tac x="x /\<^sub>R (1 - norm x)" in image_eqI)
immler@69613
  1575
    using that apply (auto simp: divide_simps)
immler@69613
  1576
    done
immler@69613
  1577
  then show "(\<lambda>z::'a. z /\<^sub>R (1 + norm z)) ` ?U = ?B"
immler@69613
  1578
    by (force simp: divide_simps dest: add_less_zeroD)
immler@69613
  1579
  show "continuous_on (ball 0 1) (\<lambda>z. z /\<^sub>R (1 - norm z))"
immler@69613
  1580
    by (rule continuous_intros | force)+
immler@69613
  1581
  show "continuous_on UNIV (\<lambda>z. z /\<^sub>R (1 + norm z))"
immler@69613
  1582
    apply (intro continuous_intros)
immler@69613
  1583
    apply (metis le_add_same_cancel1 norm_ge_zero not_le zero_less_one)
immler@69613
  1584
    done
immler@69613
  1585
  show "\<And>x. x \<in> ball 0 1 \<Longrightarrow>
immler@69613
  1586
         x /\<^sub>R (1 - norm x) /\<^sub>R (1 + norm (x /\<^sub>R (1 - norm x))) = x"
immler@69613
  1587
    by (auto simp: divide_simps)
immler@69613
  1588
  show "\<And>y. y /\<^sub>R (1 + norm y) /\<^sub>R (1 - norm (y /\<^sub>R (1 + norm y))) = y"
immler@69613
  1589
    apply (auto simp: divide_simps)
immler@69613
  1590
    apply (metis le_add_same_cancel1 norm_ge_zero not_le zero_less_one)
immler@69613
  1591
    done
immler@69613
  1592
qed
immler@69613
  1593
immler@69613
  1594
proposition homeomorphic_ball_UNIV:
immler@69613
  1595
  fixes a ::"'a::real_normed_vector"
immler@69613
  1596
  assumes "0 < r" shows "ball a r homeomorphic (UNIV:: 'a set)"
immler@69613
  1597
  using assms homeomorphic_ball01_UNIV homeomorphic_balls(1) homeomorphic_trans zero_less_one by blast
immler@69613
  1598
immler@69613
  1599
immler@69615
  1600
subsection%unimportant \<open>Discrete\<close>
immler@69615
  1601
immler@69615
  1602
lemma finite_implies_discrete:
immler@69615
  1603
  fixes S :: "'a::topological_space set"
immler@69615
  1604
  assumes "finite (f ` S)"
immler@69615
  1605
  shows "(\<forall>x \<in> S. \<exists>e>0. \<forall>y. y \<in> S \<and> f y \<noteq> f x \<longrightarrow> e \<le> norm (f y - f x))"
immler@69615
  1606
proof -
immler@69615
  1607
  have "\<exists>e>0. \<forall>y. y \<in> S \<and> f y \<noteq> f x \<longrightarrow> e \<le> norm (f y - f x)" if "x \<in> S" for x
immler@69615
  1608
  proof (cases "f ` S - {f x} = {}")
immler@69615
  1609
    case True
immler@69615
  1610
    with zero_less_numeral show ?thesis
immler@69615
  1611
      by (fastforce simp add: Set.image_subset_iff cong: conj_cong)
immler@69615
  1612
  next
immler@69615
  1613
    case False
immler@69615
  1614
    then obtain z where z: "z \<in> S" "f z \<noteq> f x"
immler@69615
  1615
      by blast
immler@69615
  1616
    have finn: "finite {norm (z - f x) |z. z \<in> f ` S - {f x}}"
immler@69615
  1617
      using assms by simp
immler@69615
  1618
    then have *: "0 < Inf{norm(z - f x) | z. z \<in> f ` S - {f x}}"
immler@69615
  1619
      apply (rule finite_imp_less_Inf)
immler@69615
  1620
      using z apply force+
immler@69615
  1621
      done
immler@69615
  1622
    show ?thesis
immler@69615
  1623
      by (force intro!: * cInf_le_finite [OF finn])
immler@69615
  1624
  qed
immler@69615
  1625
  with assms show ?thesis
immler@69615
  1626
    by blast
immler@69615
  1627
qed
immler@69615
  1628
immler@69615
  1629
immler@69613
  1630
subsection%unimportant \<open>Completeness of "Isometry" (up to constant bounds)\<close>
immler@69613
  1631
immler@69613
  1632
lemma cauchy_isometric:\<comment> \<open>TODO: rename lemma to \<open>Cauchy_isometric\<close>\<close>
immler@69613
  1633
  assumes e: "e > 0"
immler@69613
  1634
    and s: "subspace s"
immler@69613
  1635
    and f: "bounded_linear f"
immler@69613
  1636
    and normf: "\<forall>x\<in>s. norm (f x) \<ge> e * norm x"
immler@69613
  1637
    and xs: "\<forall>n. x n \<in> s"
immler@69613
  1638
    and cf: "Cauchy (f \<circ> x)"
immler@69613
  1639
  shows "Cauchy x"
immler@69613
  1640
proof -
immler@69613
  1641
  interpret f: bounded_linear f by fact
immler@69613
  1642
  have "\<exists>N. \<forall>n\<ge>N. norm (x n - x N) < d" if "d > 0" for d :: real
immler@69613
  1643
  proof -
immler@69613
  1644
    from that obtain N where N: "\<forall>n\<ge>N. norm (f (x n) - f (x N)) < e * d"
immler@69613
  1645
      using cf[unfolded Cauchy_def o_def dist_norm, THEN spec[where x="e*d"]] e
immler@69613
  1646
      by auto
immler@69613
  1647
    have "norm (x n - x N) < d" if "n \<ge> N" for n
immler@69613
  1648
    proof -
immler@69613
  1649
      have "e * norm (x n - x N) \<le> norm (f (x n - x N))"
immler@69613
  1650
        using subspace_diff[OF s, of "x n" "x N"]
immler@69613
  1651
        using xs[THEN spec[where x=N]] and xs[THEN spec[where x=n]]
immler@69613
  1652
        using normf[THEN bspec[where x="x n - x N"]]
immler@69613
  1653
        by auto
immler@69613
  1654
      also have "norm (f (x n - x N)) < e * d"
immler@69613
  1655
        using \<open>N \<le> n\<close> N unfolding f.diff[symmetric] by auto
immler@69613
  1656
      finally show ?thesis
immler@69613
  1657
        using \<open>e>0\<close> by simp
immler@69613
  1658
    qed
immler@69613
  1659
    then show ?thesis by auto
immler@69613
  1660
  qed
immler@69613
  1661
  then show ?thesis
immler@69613
  1662
    by (simp add: Cauchy_altdef2 dist_norm)
immler@69613
  1663
qed
immler@69613
  1664
immler@69613
  1665
lemma complete_isometric_image:
immler@69613
  1666
  assumes "0 < e"
immler@69613
  1667
    and s: "subspace s"
immler@69613
  1668
    and f: "bounded_linear f"
immler@69613
  1669
    and normf: "\<forall>x\<in>s. norm(f x) \<ge> e * norm(x)"
immler@69613
  1670
    and cs: "complete s"
immler@69613
  1671
  shows "complete (f ` s)"
immler@69613
  1672
proof -
immler@69613
  1673
  have "\<exists>l\<in>f ` s. (g \<longlongrightarrow> l) sequentially"
immler@69613
  1674
    if as:"\<forall>n::nat. g n \<in> f ` s" and cfg:"Cauchy g" for g
immler@69613
  1675
  proof -
immler@69613
  1676
    from that obtain x where "\<forall>n. x n \<in> s \<and> g n = f (x n)"
immler@69613
  1677
      using choice[of "\<lambda> n xa. xa \<in> s \<and> g n = f xa"] by auto
immler@69613
  1678
    then have x: "\<forall>n. x n \<in> s" "\<forall>n. g n = f (x n)" by auto
immler@69613
  1679
    then have "f \<circ> x = g" by (simp add: fun_eq_iff)
immler@69613
  1680
    then obtain l where "l\<in>s" and l:"(x \<longlongrightarrow> l) sequentially"
immler@69613
  1681
      using cs[unfolded complete_def, THEN spec[where x=x]]
immler@69613
  1682
      using cauchy_isometric[OF \<open>0 < e\<close> s f normf] and cfg and x(1)
immler@69613
  1683
      by auto
immler@69613
  1684
    then show ?thesis
immler@69613
  1685
      using linear_continuous_at[OF f, unfolded continuous_at_sequentially, THEN spec[where x=x], of l]
immler@69613
  1686
      by (auto simp: \<open>f \<circ> x = g\<close>)
immler@69613
  1687
  qed
immler@69613
  1688
  then show ?thesis
immler@69613
  1689
    unfolding complete_def by auto
immler@69613
  1690
qed
immler@69613
  1691
immler@69617
  1692
subsection \<open>Connected Normed Spaces\<close>
immler@69617
  1693
immler@69617
  1694
lemma compact_components:
immler@69617
  1695
  fixes s :: "'a::heine_borel set"
immler@69617
  1696
  shows "\<lbrakk>compact s; c \<in> components s\<rbrakk> \<Longrightarrow> compact c"
immler@69617
  1697
by (meson bounded_subset closed_components in_components_subset compact_eq_bounded_closed)
immler@69617
  1698
immler@69617
  1699
lemma discrete_subset_disconnected:
immler@69617
  1700
  fixes S :: "'a::topological_space set"
immler@69617
  1701
  fixes t :: "'b::real_normed_vector set"
immler@69617
  1702
  assumes conf: "continuous_on S f"
immler@69617
  1703
      and no: "\<And>x. x \<in> S \<Longrightarrow> \<exists>e>0. \<forall>y. y \<in> S \<and> f y \<noteq> f x \<longrightarrow> e \<le> norm (f y - f x)"
immler@69617
  1704
   shows "f ` S \<subseteq> {y. connected_component_set (f ` S) y = {y}}"
immler@69617
  1705
proof -
immler@69617
  1706
  { fix x assume x: "x \<in> S"
immler@69617
  1707
    then obtain e where "e>0" and ele: "\<And>y. \<lbrakk>y \<in> S; f y \<noteq> f x\<rbrakk> \<Longrightarrow> e \<le> norm (f y - f x)"
immler@69617
  1708
      using conf no [OF x] by auto
immler@69617
  1709
    then have e2: "0 \<le> e / 2"
immler@69617
  1710
      by simp
immler@69617
  1711
    have "f y = f x" if "y \<in> S" and ccs: "f y \<in> connected_component_set (f ` S) (f x)" for y
immler@69617
  1712
      apply (rule ccontr)
immler@69617
  1713
      using connected_closed [of "connected_component_set (f ` S) (f x)"] \<open>e>0\<close>
immler@69617
  1714
      apply (simp add: del: ex_simps)
immler@69617
  1715
      apply (drule spec [where x="cball (f x) (e / 2)"])
immler@69617
  1716
      apply (drule spec [where x="- ball(f x) e"])
immler@69617
  1717
      apply (auto simp: dist_norm open_closed [symmetric] simp del: le_divide_eq_numeral1 dest!: connected_component_in)
immler@69617
  1718
        apply (metis diff_self e2 ele norm_minus_commute norm_zero not_less)
immler@69617
  1719
       using centre_in_cball connected_component_refl_eq e2 x apply blast
immler@69617
  1720
      using ccs
immler@69617
  1721
      apply (force simp: cball_def dist_norm norm_minus_commute dest: ele [OF \<open>y \<in> S\<close>])
immler@69617
  1722
      done
immler@69617
  1723
    moreover have "connected_component_set (f ` S) (f x) \<subseteq> f ` S"
immler@69617
  1724
      by (auto simp: connected_component_in)
immler@69617
  1725
    ultimately have "connected_component_set (f ` S) (f x) = {f x}"
immler@69617
  1726
      by (auto simp: x)
immler@69617
  1727
  }
immler@69617
  1728
  with assms show ?thesis
immler@69617
  1729
    by blast
immler@69617
  1730
qed
immler@69617
  1731
immler@69617
  1732
lemma continuous_disconnected_range_constant_eq:
immler@69617
  1733
      "(connected S \<longleftrightarrow>
immler@69617
  1734
           (\<forall>f::'a::topological_space \<Rightarrow> 'b::real_normed_algebra_1.
immler@69617
  1735
            \<forall>t. continuous_on S f \<and> f ` S \<subseteq> t \<and> (\<forall>y \<in> t. connected_component_set t y = {y})
immler@69617
  1736
            \<longrightarrow> f constant_on S))" (is ?thesis1)
immler@69617
  1737
  and continuous_discrete_range_constant_eq:
immler@69617
  1738
      "(connected S \<longleftrightarrow>
immler@69617
  1739
         (\<forall>f::'a::topological_space \<Rightarrow> 'b::real_normed_algebra_1.
immler@69617
  1740
          continuous_on S f \<and>
immler@69617
  1741
          (\<forall>x \<in> S. \<exists>e. 0 < e \<and> (\<forall>y. y \<in> S \<and> (f y \<noteq> f x) \<longrightarrow> e \<le> norm(f y - f x)))
immler@69617
  1742
          \<longrightarrow> f constant_on S))" (is ?thesis2)
immler@69617
  1743
  and continuous_finite_range_constant_eq:
immler@69617
  1744
      "(connected S \<longleftrightarrow>
immler@69617
  1745
         (\<forall>f::'a::topological_space \<Rightarrow> 'b::real_normed_algebra_1.
immler@69617
  1746
          continuous_on S f \<and> finite (f ` S)
immler@69617
  1747
          \<longrightarrow> f constant_on S))" (is ?thesis3)
immler@69617
  1748
proof -
immler@69617
  1749
  have *: "\<And>s t u v. \<lbrakk>s \<Longrightarrow> t; t \<Longrightarrow> u; u \<Longrightarrow> v; v \<Longrightarrow> s\<rbrakk>
immler@69617
  1750
    \<Longrightarrow> (s \<longleftrightarrow> t) \<and> (s \<longleftrightarrow> u) \<and> (s \<longleftrightarrow> v)"
immler@69617
  1751
    by blast
immler@69617
  1752
  have "?thesis1 \<and> ?thesis2 \<and> ?thesis3"
immler@69617
  1753
    apply (rule *)
immler@69617
  1754
    using continuous_disconnected_range_constant apply metis
immler@69617
  1755
    apply clarify
immler@69617
  1756
    apply (frule discrete_subset_disconnected; blast)
immler@69617
  1757
    apply (blast dest: finite_implies_discrete)
immler@69617
  1758
    apply (blast intro!: finite_range_constant_imp_connected)
immler@69617
  1759
    done
immler@69617
  1760
  then show ?thesis1 ?thesis2 ?thesis3
immler@69617
  1761
    by blast+
immler@69617
  1762
qed
immler@69617
  1763
immler@69617
  1764
lemma continuous_discrete_range_constant:
immler@69617
  1765
  fixes f :: "'a::topological_space \<Rightarrow> 'b::real_normed_algebra_1"
immler@69617
  1766
  assumes S: "connected S"
immler@69617
  1767
      and "continuous_on S f"
immler@69617
  1768
      and "\<And>x. x \<in> S \<Longrightarrow> \<exists>e>0. \<forall>y. y \<in> S \<and> f y \<noteq> f x \<longrightarrow> e \<le> norm (f y - f x)"
immler@69617
  1769
    shows "f constant_on S"
immler@69617
  1770
  using continuous_discrete_range_constant_eq [THEN iffD1, OF S] assms by blast
immler@69617
  1771
immler@69617
  1772
lemma continuous_finite_range_constant:
immler@69617
  1773
  fixes f :: "'a::topological_space \<Rightarrow> 'b::real_normed_algebra_1"
immler@69617
  1774
  assumes "connected S"
immler@69617
  1775
      and "continuous_on S f"
immler@69617
  1776
      and "finite (f ` S)"
immler@69617
  1777
    shows "f constant_on S"
immler@69617
  1778
  using assms continuous_finite_range_constant_eq  by blast
immler@69617
  1779
immler@69613
  1780
immler@69544
  1781
end