src/HOL/Analysis/Topology_Euclidean_Space.thy
author immler
Mon Jan 07 13:16:33 2019 +0100 (4 months ago)
changeset 69617 63ee37c519a3
parent 69615 e502cd4d7062
child 69618 2be1baf40351
permissions -rw-r--r--
reduced dependencies of Connected.thy
lp15@63938
     1
(*  Author:     L C Paulson, University of Cambridge
himmelma@33175
     2
    Author:     Amine Chaieb, University of Cambridge
himmelma@33175
     3
    Author:     Robert Himmelmann, TU Muenchen
huffman@44075
     4
    Author:     Brian Huffman, Portland State University
himmelma@33175
     5
*)
himmelma@33175
     6
immler@69516
     7
section \<open>Elementary Topology in Euclidean Space\<close>
himmelma@33175
     8
himmelma@33175
     9
theory Topology_Euclidean_Space
immler@69516
    10
  imports
immler@69544
    11
    Elementary_Normed_Spaces
immler@69516
    12
    Linear_Algebra
immler@69516
    13
    Norm_Arith
hoelzl@51343
    14
begin
hoelzl@51343
    15
hoelzl@50526
    16
lemma euclidean_dist_l2:
hoelzl@50526
    17
  fixes x y :: "'a :: euclidean_space"
nipkow@67155
    18
  shows "dist x y = L2_set (\<lambda>i. dist (x \<bullet> i) (y \<bullet> i)) Basis"
nipkow@67155
    19
  unfolding dist_norm norm_eq_sqrt_inner L2_set_def
hoelzl@50526
    20
  by (subst euclidean_inner) (simp add: power2_eq_square inner_diff_left)
hoelzl@50526
    21
immler@67685
    22
lemma norm_nth_le: "norm (x \<bullet> i) \<le> norm x" if "i \<in> Basis"
immler@67685
    23
proof -
immler@67685
    24
  have "(x \<bullet> i)\<^sup>2 = (\<Sum>i\<in>{i}. (x \<bullet> i)\<^sup>2)"
immler@67685
    25
    by simp
immler@67685
    26
  also have "\<dots> \<le> (\<Sum>i\<in>Basis. (x \<bullet> i)\<^sup>2)"
immler@67685
    27
    by (intro sum_mono2) (auto simp: that)
immler@67685
    28
  finally show ?thesis
immler@67685
    29
    unfolding norm_conv_dist euclidean_dist_l2[of x] L2_set_def
immler@67685
    30
    by (auto intro!: real_le_rsqrt)
immler@67685
    31
qed
immler@67685
    32
immler@67685
    33
immler@69613
    34
subsection%unimportant\<open>Balls in Euclidean Space\<close>
immler@69613
    35
immler@69613
    36
lemma cball_subset_cball_iff:
immler@69613
    37
  fixes a :: "'a :: euclidean_space"
immler@69613
    38
  shows "cball a r \<subseteq> cball a' r' \<longleftrightarrow> dist a a' + r \<le> r' \<or> r < 0"
immler@69613
    39
    (is "?lhs \<longleftrightarrow> ?rhs")
immler@69613
    40
proof
immler@69613
    41
  assume ?lhs
immler@69613
    42
  then show ?rhs
immler@69613
    43
  proof (cases "r < 0")
immler@69613
    44
    case True
immler@69613
    45
    then show ?rhs by simp
immler@69613
    46
  next
immler@69613
    47
    case False
immler@69613
    48
    then have [simp]: "r \<ge> 0" by simp
immler@69613
    49
    have "norm (a - a') + r \<le> r'"
immler@69613
    50
    proof (cases "a = a'")
immler@69613
    51
      case True
immler@69613
    52
      then show ?thesis
immler@69613
    53
        using subsetD [where c = "a + r *\<^sub>R (SOME i. i \<in> Basis)", OF \<open>?lhs\<close>] subsetD [where c = a, OF \<open>?lhs\<close>]
immler@69613
    54
        by (force simp: SOME_Basis dist_norm)
immler@69613
    55
    next
immler@69613
    56
      case False
immler@69613
    57
      have "norm (a' - (a + (r / norm (a - a')) *\<^sub>R (a - a'))) = norm (a' - a - (r / norm (a - a')) *\<^sub>R (a - a'))"
immler@69613
    58
        by (simp add: algebra_simps)
immler@69613
    59
      also have "... = norm ((-1 - (r / norm (a - a'))) *\<^sub>R (a - a'))"
immler@69613
    60
        by (simp add: algebra_simps)
immler@69613
    61
      also from \<open>a \<noteq> a'\<close> have "... = \<bar>- norm (a - a') - r\<bar>"
immler@69613
    62
        by (simp add: abs_mult_pos field_simps)
immler@69613
    63
      finally have [simp]: "norm (a' - (a + (r / norm (a - a')) *\<^sub>R (a - a'))) = \<bar>norm (a - a') + r\<bar>"
immler@69613
    64
        by linarith
immler@69613
    65
      from \<open>a \<noteq> a'\<close> show ?thesis
immler@69613
    66
        using subsetD [where c = "a' + (1 + r / norm(a - a')) *\<^sub>R (a - a')", OF \<open>?lhs\<close>]
immler@69613
    67
        by (simp add: dist_norm scaleR_add_left)
immler@69613
    68
    qed
immler@69613
    69
    then show ?rhs
immler@69613
    70
      by (simp add: dist_norm)
immler@69613
    71
  qed
immler@69613
    72
next
immler@69613
    73
  assume ?rhs
immler@69613
    74
  then show ?lhs
immler@69613
    75
    by (auto simp: ball_def dist_norm)
immler@69613
    76
      (metis add.commute add_le_cancel_right dist_norm dist_triangle3 order_trans)
immler@69613
    77
qed
immler@69613
    78
immler@69613
    79
lemma cball_subset_ball_iff: "cball a r \<subseteq> ball a' r' \<longleftrightarrow> dist a a' + r < r' \<or> r < 0"
immler@69613
    80
  (is "?lhs \<longleftrightarrow> ?rhs")
immler@69613
    81
  for a :: "'a::euclidean_space"
immler@69613
    82
proof
immler@69613
    83
  assume ?lhs
immler@69613
    84
  then show ?rhs
immler@69613
    85
  proof (cases "r < 0")
immler@69613
    86
    case True then
immler@69613
    87
    show ?rhs by simp
immler@69613
    88
  next
immler@69613
    89
    case False
immler@69613
    90
    then have [simp]: "r \<ge> 0" by simp
immler@69613
    91
    have "norm (a - a') + r < r'"
immler@69613
    92
    proof (cases "a = a'")
immler@69613
    93
      case True
immler@69613
    94
      then show ?thesis
immler@69613
    95
        using subsetD [where c = "a + r *\<^sub>R (SOME i. i \<in> Basis)", OF \<open>?lhs\<close>] subsetD [where c = a, OF \<open>?lhs\<close>]
immler@69613
    96
        by (force simp: SOME_Basis dist_norm)
immler@69613
    97
    next
immler@69613
    98
      case False
immler@69613
    99
      have False if "norm (a - a') + r \<ge> r'"
immler@69613
   100
      proof -
immler@69613
   101
        from that have "\<bar>r' - norm (a - a')\<bar> \<le> r"
immler@69613
   102
          by (simp split: abs_split)
immler@69613
   103
            (metis \<open>0 \<le> r\<close> \<open>?lhs\<close> centre_in_cball dist_commute dist_norm less_asym mem_ball subset_eq)
immler@69613
   104
        then show ?thesis
immler@69613
   105
          using subsetD [where c = "a + (r' / norm(a - a') - 1) *\<^sub>R (a - a')", OF \<open>?lhs\<close>] \<open>a \<noteq> a'\<close>
immler@69613
   106
          by (simp add: dist_norm field_simps)
immler@69613
   107
            (simp add: diff_divide_distrib scaleR_left_diff_distrib)
immler@69613
   108
      qed
immler@69613
   109
      then show ?thesis by force
immler@69613
   110
    qed
immler@69613
   111
    then show ?rhs by (simp add: dist_norm)
immler@69613
   112
  qed
immler@69613
   113
next
immler@69613
   114
  assume ?rhs
immler@69613
   115
  then show ?lhs
immler@69613
   116
    by (auto simp: ball_def dist_norm)
immler@69613
   117
      (metis add.commute add_le_cancel_right dist_norm dist_triangle3 le_less_trans)
immler@69613
   118
qed
immler@69613
   119
immler@69613
   120
lemma ball_subset_cball_iff: "ball a r \<subseteq> cball a' r' \<longleftrightarrow> dist a a' + r \<le> r' \<or> r \<le> 0"
immler@69613
   121
  (is "?lhs = ?rhs")
immler@69613
   122
  for a :: "'a::euclidean_space"
immler@69613
   123
proof (cases "r \<le> 0")
immler@69613
   124
  case True
immler@69613
   125
  then show ?thesis
immler@69613
   126
    using dist_not_less_zero less_le_trans by force
immler@69613
   127
next
immler@69613
   128
  case False
immler@69613
   129
  show ?thesis
immler@69613
   130
  proof
immler@69613
   131
    assume ?lhs
immler@69613
   132
    then have "(cball a r \<subseteq> cball a' r')"
immler@69613
   133
      by (metis False closed_cball closure_ball closure_closed closure_mono not_less)
immler@69613
   134
    with False show ?rhs
immler@69613
   135
      by (fastforce iff: cball_subset_cball_iff)
immler@69613
   136
  next
immler@69613
   137
    assume ?rhs
immler@69613
   138
    with False show ?lhs
immler@69613
   139
      using ball_subset_cball cball_subset_cball_iff by blast
immler@69613
   140
  qed
immler@69613
   141
qed
immler@69613
   142
immler@69613
   143
lemma ball_subset_ball_iff:
immler@69613
   144
  fixes a :: "'a :: euclidean_space"
immler@69613
   145
  shows "ball a r \<subseteq> ball a' r' \<longleftrightarrow> dist a a' + r \<le> r' \<or> r \<le> 0"
immler@69613
   146
        (is "?lhs = ?rhs")
immler@69613
   147
proof (cases "r \<le> 0")
immler@69613
   148
  case True then show ?thesis
immler@69613
   149
    using dist_not_less_zero less_le_trans by force
immler@69613
   150
next
immler@69613
   151
  case False show ?thesis
immler@69613
   152
  proof
immler@69613
   153
    assume ?lhs
immler@69613
   154
    then have "0 < r'"
immler@69613
   155
      by (metis (no_types) False \<open>?lhs\<close> centre_in_ball dist_norm le_less_trans mem_ball norm_ge_zero not_less set_mp)
immler@69613
   156
    then have "(cball a r \<subseteq> cball a' r')"
immler@69613
   157
      by (metis False\<open>?lhs\<close> closure_ball closure_mono not_less)
immler@69613
   158
    then show ?rhs
immler@69613
   159
      using False cball_subset_cball_iff by fastforce
immler@69613
   160
  next
immler@69613
   161
  assume ?rhs then show ?lhs
immler@69613
   162
    apply (auto simp: ball_def)
immler@69613
   163
    apply (metis add.commute add_le_cancel_right dist_commute dist_triangle_lt not_le order_trans)
immler@69613
   164
    using dist_not_less_zero order.strict_trans2 apply blast
immler@69613
   165
    done
immler@69613
   166
  qed
immler@69613
   167
qed
immler@69613
   168
immler@69613
   169
immler@69613
   170
lemma ball_eq_ball_iff:
immler@69613
   171
  fixes x :: "'a :: euclidean_space"
immler@69613
   172
  shows "ball x d = ball y e \<longleftrightarrow> d \<le> 0 \<and> e \<le> 0 \<or> x=y \<and> d=e"
immler@69613
   173
        (is "?lhs = ?rhs")
immler@69613
   174
proof
immler@69613
   175
  assume ?lhs
immler@69613
   176
  then show ?rhs
immler@69613
   177
  proof (cases "d \<le> 0 \<or> e \<le> 0")
immler@69613
   178
    case True
immler@69613
   179
      with \<open>?lhs\<close> show ?rhs
immler@69613
   180
        by safe (simp_all only: ball_eq_empty [of y e, symmetric] ball_eq_empty [of x d, symmetric])
immler@69613
   181
  next
immler@69613
   182
    case False
immler@69613
   183
    with \<open>?lhs\<close> show ?rhs
immler@69613
   184
      apply (auto simp: set_eq_subset ball_subset_ball_iff dist_norm norm_minus_commute algebra_simps)
immler@69613
   185
      apply (metis add_le_same_cancel1 le_add_same_cancel1 norm_ge_zero norm_pths(2) order_trans)
immler@69613
   186
      apply (metis add_increasing2 add_le_imp_le_right eq_iff norm_ge_zero)
immler@69613
   187
      done
immler@69613
   188
  qed
immler@69613
   189
next
immler@69613
   190
  assume ?rhs then show ?lhs
immler@69613
   191
    by (auto simp: set_eq_subset ball_subset_ball_iff)
immler@69613
   192
qed
immler@69613
   193
immler@69613
   194
lemma cball_eq_cball_iff:
immler@69613
   195
  fixes x :: "'a :: euclidean_space"
immler@69613
   196
  shows "cball x d = cball y e \<longleftrightarrow> d < 0 \<and> e < 0 \<or> x=y \<and> d=e"
immler@69613
   197
        (is "?lhs = ?rhs")
immler@69613
   198
proof
immler@69613
   199
  assume ?lhs
immler@69613
   200
  then show ?rhs
immler@69613
   201
  proof (cases "d < 0 \<or> e < 0")
immler@69613
   202
    case True
immler@69613
   203
      with \<open>?lhs\<close> show ?rhs
immler@69613
   204
        by safe (simp_all only: cball_eq_empty [of y e, symmetric] cball_eq_empty [of x d, symmetric])
immler@69613
   205
  next
immler@69613
   206
    case False
immler@69613
   207
    with \<open>?lhs\<close> show ?rhs
immler@69613
   208
      apply (auto simp: set_eq_subset cball_subset_cball_iff dist_norm norm_minus_commute algebra_simps)
immler@69613
   209
      apply (metis add_le_same_cancel1 le_add_same_cancel1 norm_ge_zero norm_pths(2) order_trans)
immler@69613
   210
      apply (metis add_increasing2 add_le_imp_le_right eq_iff norm_ge_zero)
immler@69613
   211
      done
immler@69613
   212
  qed
immler@69613
   213
next
immler@69613
   214
  assume ?rhs then show ?lhs
immler@69613
   215
    by (auto simp: set_eq_subset cball_subset_cball_iff)
immler@69613
   216
qed
immler@69613
   217
immler@69613
   218
lemma ball_eq_cball_iff:
immler@69613
   219
  fixes x :: "'a :: euclidean_space"
immler@69613
   220
  shows "ball x d = cball y e \<longleftrightarrow> d \<le> 0 \<and> e < 0" (is "?lhs = ?rhs")
immler@69613
   221
proof
immler@69613
   222
  assume ?lhs
immler@69613
   223
  then show ?rhs
immler@69613
   224
    apply (auto simp: set_eq_subset ball_subset_cball_iff cball_subset_ball_iff algebra_simps)
immler@69613
   225
    apply (metis add_increasing2 add_le_cancel_right add_less_same_cancel1 dist_not_less_zero less_le_trans zero_le_dist)
immler@69613
   226
    apply (metis add_less_same_cancel1 dist_not_less_zero less_le_trans not_le)
immler@69613
   227
    using \<open>?lhs\<close> ball_eq_empty cball_eq_empty apply blast+
immler@69613
   228
    done
immler@69613
   229
next
immler@69613
   230
  assume ?rhs then show ?lhs by auto
immler@69613
   231
qed
immler@69613
   232
immler@69613
   233
lemma cball_eq_ball_iff:
immler@69613
   234
  fixes x :: "'a :: euclidean_space"
immler@69613
   235
  shows "cball x d = ball y e \<longleftrightarrow> d < 0 \<and> e \<le> 0"
immler@69613
   236
  using ball_eq_cball_iff by blast
immler@69613
   237
immler@69613
   238
lemma finite_ball_avoid:
immler@69613
   239
  fixes S :: "'a :: euclidean_space set"
immler@69613
   240
  assumes "open S" "finite X" "p \<in> S"
immler@69613
   241
  shows "\<exists>e>0. \<forall>w\<in>ball p e. w\<in>S \<and> (w\<noteq>p \<longrightarrow> w\<notin>X)"
immler@69613
   242
proof -
immler@69613
   243
  obtain e1 where "0 < e1" and e1_b:"ball p e1 \<subseteq> S"
immler@69613
   244
    using open_contains_ball_eq[OF \<open>open S\<close>] assms by auto
immler@69613
   245
  obtain e2 where "0 < e2" and "\<forall>x\<in>X. x \<noteq> p \<longrightarrow> e2 \<le> dist p x"
immler@69613
   246
    using finite_set_avoid[OF \<open>finite X\<close>,of p] by auto
immler@69613
   247
  hence "\<forall>w\<in>ball p (min e1 e2). w\<in>S \<and> (w\<noteq>p \<longrightarrow> w\<notin>X)" using e1_b by auto
immler@69613
   248
  thus "\<exists>e>0. \<forall>w\<in>ball p e. w \<in> S \<and> (w \<noteq> p \<longrightarrow> w \<notin> X)" using \<open>e2>0\<close> \<open>e1>0\<close>
immler@69613
   249
    apply (rule_tac x="min e1 e2" in exI)
immler@69613
   250
    by auto
immler@69613
   251
qed
immler@69613
   252
immler@69613
   253
lemma finite_cball_avoid:
immler@69613
   254
  fixes S :: "'a :: euclidean_space set"
immler@69613
   255
  assumes "open S" "finite X" "p \<in> S"
immler@69613
   256
  shows "\<exists>e>0. \<forall>w\<in>cball p e. w\<in>S \<and> (w\<noteq>p \<longrightarrow> w\<notin>X)"
immler@69613
   257
proof -
immler@69613
   258
  obtain e1 where "e1>0" and e1: "\<forall>w\<in>ball p e1. w\<in>S \<and> (w\<noteq>p \<longrightarrow> w\<notin>X)"
immler@69613
   259
    using finite_ball_avoid[OF assms] by auto
immler@69613
   260
  define e2 where "e2 \<equiv> e1/2"
immler@69613
   261
  have "e2>0" and "e2 < e1" unfolding e2_def using \<open>e1>0\<close> by auto
immler@69613
   262
  then have "cball p e2 \<subseteq> ball p e1" by (subst cball_subset_ball_iff,auto)
immler@69613
   263
  then show "\<exists>e>0. \<forall>w\<in>cball p e. w \<in> S \<and> (w \<noteq> p \<longrightarrow> w \<notin> X)" using \<open>e2>0\<close> e1 by auto
immler@69613
   264
qed
immler@69613
   265
immler@69613
   266
wenzelm@60420
   267
subsection \<open>Boxes\<close>
immler@56189
   268
hoelzl@57447
   269
abbreviation One :: "'a::euclidean_space"
hoelzl@57447
   270
  where "One \<equiv> \<Sum>Basis"
hoelzl@57447
   271
lp15@63114
   272
lemma One_non_0: assumes "One = (0::'a::euclidean_space)" shows False
lp15@63114
   273
proof -
lp15@63114
   274
  have "dependent (Basis :: 'a set)"
lp15@63114
   275
    apply (simp add: dependent_finite)
lp15@63114
   276
    apply (rule_tac x="\<lambda>i. 1" in exI)
lp15@63114
   277
    using SOME_Basis apply (auto simp: assms)
lp15@63114
   278
    done
lp15@63114
   279
  with independent_Basis show False by force
lp15@63114
   280
qed
lp15@63114
   281
lp15@63114
   282
corollary One_neq_0[iff]: "One \<noteq> 0"
lp15@63114
   283
  by (metis One_non_0)
lp15@63114
   284
lp15@63114
   285
corollary Zero_neq_One[iff]: "0 \<noteq> One"
lp15@63114
   286
  by (metis One_non_0)
lp15@63114
   287
immler@67962
   288
definition%important (in euclidean_space) eucl_less (infix "<e" 50)
immler@54775
   289
  where "eucl_less a b \<longleftrightarrow> (\<forall>i\<in>Basis. a \<bullet> i < b \<bullet> i)"
immler@54775
   290
immler@67962
   291
definition%important box_eucl_less: "box a b = {x. a <e x \<and> x <e b}"
immler@67962
   292
definition%important "cbox a b = {x. \<forall>i\<in>Basis. a \<bullet> i \<le> x \<bullet> i \<and> x \<bullet> i \<le> b \<bullet> i}"
immler@54775
   293
immler@54775
   294
lemma box_def: "box a b = {x. \<forall>i\<in>Basis. a \<bullet> i < x \<bullet> i \<and> x \<bullet> i < b \<bullet> i}"
immler@54775
   295
  and in_box_eucl_less: "x \<in> box a b \<longleftrightarrow> a <e x \<and> x <e b"
immler@56188
   296
  and mem_box: "x \<in> box a b \<longleftrightarrow> (\<forall>i\<in>Basis. a \<bullet> i < x \<bullet> i \<and> x \<bullet> i < b \<bullet> i)"
immler@56188
   297
    "x \<in> cbox a b \<longleftrightarrow> (\<forall>i\<in>Basis. a \<bullet> i \<le> x \<bullet> i \<and> x \<bullet> i \<le> b \<bullet> i)"
immler@56188
   298
  by (auto simp: box_eucl_less eucl_less_def cbox_def)
immler@56188
   299
lp15@60615
   300
lemma cbox_Pair_eq: "cbox (a, c) (b, d) = cbox a b \<times> cbox c d"
lp15@60615
   301
  by (force simp: cbox_def Basis_prod_def)
lp15@60615
   302
lp15@60615
   303
lemma cbox_Pair_iff [iff]: "(x, y) \<in> cbox (a, c) (b, d) \<longleftrightarrow> x \<in> cbox a b \<and> y \<in> cbox c d"
lp15@60615
   304
  by (force simp: cbox_Pair_eq)
lp15@60615
   305
lp15@65587
   306
lemma cbox_Complex_eq: "cbox (Complex a c) (Complex b d) = (\<lambda>(x,y). Complex x y) ` (cbox a b \<times> cbox c d)"
lp15@65587
   307
  apply (auto simp: cbox_def Basis_complex_def)
lp15@65587
   308
  apply (rule_tac x = "(Re x, Im x)" in image_eqI)
lp15@65587
   309
  using complex_eq by auto
lp15@65587
   310
lp15@60615
   311
lemma cbox_Pair_eq_0: "cbox (a, c) (b, d) = {} \<longleftrightarrow> cbox a b = {} \<or> cbox c d = {}"
lp15@60615
   312
  by (force simp: cbox_Pair_eq)
lp15@60615
   313
lp15@60615
   314
lemma swap_cbox_Pair [simp]: "prod.swap ` cbox (c, a) (d, b) = cbox (a,c) (b,d)"
lp15@60615
   315
  by auto
lp15@60615
   316
immler@56188
   317
lemma mem_box_real[simp]:
immler@56188
   318
  "(x::real) \<in> box a b \<longleftrightarrow> a < x \<and> x < b"
immler@56188
   319
  "(x::real) \<in> cbox a b \<longleftrightarrow> a \<le> x \<and> x \<le> b"
immler@56188
   320
  by (auto simp: mem_box)
immler@56188
   321
immler@56188
   322
lemma box_real[simp]:
immler@56188
   323
  fixes a b:: real
immler@56188
   324
  shows "box a b = {a <..< b}" "cbox a b = {a .. b}"
immler@56188
   325
  by auto
hoelzl@50526
   326
hoelzl@57447
   327
lemma box_Int_box:
hoelzl@57447
   328
  fixes a :: "'a::euclidean_space"
hoelzl@57447
   329
  shows "box a b \<inter> box c d =
hoelzl@57447
   330
    box (\<Sum>i\<in>Basis. max (a\<bullet>i) (c\<bullet>i) *\<^sub>R i) (\<Sum>i\<in>Basis. min (b\<bullet>i) (d\<bullet>i) *\<^sub>R i)"
hoelzl@57447
   331
  unfolding set_eq_iff and Int_iff and mem_box by auto
hoelzl@57447
   332
immler@50087
   333
lemma rational_boxes:
wenzelm@61076
   334
  fixes x :: "'a::euclidean_space"
wenzelm@53291
   335
  assumes "e > 0"
lp15@66643
   336
  shows "\<exists>a b. (\<forall>i\<in>Basis. a \<bullet> i \<in> \<rat> \<and> b \<bullet> i \<in> \<rat>) \<and> x \<in> box a b \<and> box a b \<subseteq> ball x e"
immler@50087
   337
proof -
wenzelm@63040
   338
  define e' where "e' = e / (2 * sqrt (real (DIM ('a))))"
wenzelm@53291
   339
  then have e: "e' > 0"
nipkow@56541
   340
    using assms by (auto simp: DIM_positive)
hoelzl@50526
   341
  have "\<forall>i. \<exists>y. y \<in> \<rat> \<and> y < x \<bullet> i \<and> x \<bullet> i - y < e'" (is "\<forall>i. ?th i")
immler@50087
   342
  proof
wenzelm@53255
   343
    fix i
wenzelm@53255
   344
    from Rats_dense_in_real[of "x \<bullet> i - e'" "x \<bullet> i"] e
wenzelm@53255
   345
    show "?th i" by auto
immler@50087
   346
  qed
wenzelm@55522
   347
  from choice[OF this] obtain a where
wenzelm@55522
   348
    a: "\<forall>xa. a xa \<in> \<rat> \<and> a xa < x \<bullet> xa \<and> x \<bullet> xa - a xa < e'" ..
hoelzl@50526
   349
  have "\<forall>i. \<exists>y. y \<in> \<rat> \<and> x \<bullet> i < y \<and> y - x \<bullet> i < e'" (is "\<forall>i. ?th i")
immler@50087
   350
  proof
wenzelm@53255
   351
    fix i
wenzelm@53255
   352
    from Rats_dense_in_real[of "x \<bullet> i" "x \<bullet> i + e'"] e
wenzelm@53255
   353
    show "?th i" by auto
immler@50087
   354
  qed
wenzelm@55522
   355
  from choice[OF this] obtain b where
wenzelm@55522
   356
    b: "\<forall>xa. b xa \<in> \<rat> \<and> x \<bullet> xa < b xa \<and> b xa - x \<bullet> xa < e'" ..
hoelzl@50526
   357
  let ?a = "\<Sum>i\<in>Basis. a i *\<^sub>R i" and ?b = "\<Sum>i\<in>Basis. b i *\<^sub>R i"
hoelzl@50526
   358
  show ?thesis
hoelzl@50526
   359
  proof (rule exI[of _ ?a], rule exI[of _ ?b], safe)
wenzelm@53255
   360
    fix y :: 'a
wenzelm@53255
   361
    assume *: "y \<in> box ?a ?b"
wenzelm@53015
   362
    have "dist x y = sqrt (\<Sum>i\<in>Basis. (dist (x \<bullet> i) (y \<bullet> i))\<^sup>2)"
nipkow@67155
   363
      unfolding L2_set_def[symmetric] by (rule euclidean_dist_l2)
hoelzl@50526
   364
    also have "\<dots> < sqrt (\<Sum>(i::'a)\<in>Basis. e^2 / real (DIM('a)))"
nipkow@64267
   365
    proof (rule real_sqrt_less_mono, rule sum_strict_mono)
wenzelm@53255
   366
      fix i :: "'a"
wenzelm@53255
   367
      assume i: "i \<in> Basis"
wenzelm@53255
   368
      have "a i < y\<bullet>i \<and> y\<bullet>i < b i"
wenzelm@53255
   369
        using * i by (auto simp: box_def)
wenzelm@53255
   370
      moreover have "a i < x\<bullet>i" "x\<bullet>i - a i < e'"
wenzelm@53255
   371
        using a by auto
wenzelm@53255
   372
      moreover have "x\<bullet>i < b i" "b i - x\<bullet>i < e'"
wenzelm@53255
   373
        using b by auto
wenzelm@53255
   374
      ultimately have "\<bar>x\<bullet>i - y\<bullet>i\<bar> < 2 * e'"
wenzelm@53255
   375
        by auto
hoelzl@50526
   376
      then have "dist (x \<bullet> i) (y \<bullet> i) < e/sqrt (real (DIM('a)))"
immler@50087
   377
        unfolding e'_def by (auto simp: dist_real_def)
wenzelm@53015
   378
      then have "(dist (x \<bullet> i) (y \<bullet> i))\<^sup>2 < (e/sqrt (real (DIM('a))))\<^sup>2"
immler@50087
   379
        by (rule power_strict_mono) auto
wenzelm@53015
   380
      then show "(dist (x \<bullet> i) (y \<bullet> i))\<^sup>2 < e\<^sup>2 / real DIM('a)"
immler@50087
   381
        by (simp add: power_divide)
immler@50087
   382
    qed auto
wenzelm@53255
   383
    also have "\<dots> = e"
lp15@61609
   384
      using \<open>0 < e\<close> by simp
wenzelm@53255
   385
    finally show "y \<in> ball x e"
wenzelm@53255
   386
      by (auto simp: ball_def)
hoelzl@50526
   387
  qed (insert a b, auto simp: box_def)
hoelzl@50526
   388
qed
immler@51103
   389
hoelzl@50526
   390
lemma open_UNION_box:
wenzelm@61076
   391
  fixes M :: "'a::euclidean_space set"
wenzelm@53282
   392
  assumes "open M"
hoelzl@50526
   393
  defines "a' \<equiv> \<lambda>f :: 'a \<Rightarrow> real \<times> real. (\<Sum>(i::'a)\<in>Basis. fst (f i) *\<^sub>R i)"
hoelzl@50526
   394
  defines "b' \<equiv> \<lambda>f :: 'a \<Rightarrow> real \<times> real. (\<Sum>(i::'a)\<in>Basis. snd (f i) *\<^sub>R i)"
wenzelm@53015
   395
  defines "I \<equiv> {f\<in>Basis \<rightarrow>\<^sub>E \<rat> \<times> \<rat>. box (a' f) (b' f) \<subseteq> M}"
hoelzl@50526
   396
  shows "M = (\<Union>f\<in>I. box (a' f) (b' f))"
wenzelm@52624
   397
proof -
wenzelm@60462
   398
  have "x \<in> (\<Union>f\<in>I. box (a' f) (b' f))" if "x \<in> M" for x
wenzelm@60462
   399
  proof -
wenzelm@52624
   400
    obtain e where e: "e > 0" "ball x e \<subseteq> M"
wenzelm@60420
   401
      using openE[OF \<open>open M\<close> \<open>x \<in> M\<close>] by auto
wenzelm@53282
   402
    moreover obtain a b where ab:
wenzelm@53282
   403
      "x \<in> box a b"
wenzelm@53282
   404
      "\<forall>i \<in> Basis. a \<bullet> i \<in> \<rat>"
wenzelm@53282
   405
      "\<forall>i\<in>Basis. b \<bullet> i \<in> \<rat>"
wenzelm@53282
   406
      "box a b \<subseteq> ball x e"
wenzelm@52624
   407
      using rational_boxes[OF e(1)] by metis
wenzelm@60462
   408
    ultimately show ?thesis
wenzelm@52624
   409
       by (intro UN_I[of "\<lambda>i\<in>Basis. (a \<bullet> i, b \<bullet> i)"])
wenzelm@52624
   410
          (auto simp: euclidean_representation I_def a'_def b'_def)
wenzelm@60462
   411
  qed
wenzelm@52624
   412
  then show ?thesis by (auto simp: I_def)
wenzelm@52624
   413
qed
wenzelm@52624
   414
lp15@66154
   415
corollary open_countable_Union_open_box:
lp15@66154
   416
  fixes S :: "'a :: euclidean_space set"
lp15@66154
   417
  assumes "open S"
lp15@66154
   418
  obtains \<D> where "countable \<D>" "\<D> \<subseteq> Pow S" "\<And>X. X \<in> \<D> \<Longrightarrow> \<exists>a b. X = box a b" "\<Union>\<D> = S"
lp15@66154
   419
proof -
lp15@66154
   420
  let ?a = "\<lambda>f. (\<Sum>(i::'a)\<in>Basis. fst (f i) *\<^sub>R i)"
lp15@66154
   421
  let ?b = "\<lambda>f. (\<Sum>(i::'a)\<in>Basis. snd (f i) *\<^sub>R i)"
lp15@66154
   422
  let ?I = "{f\<in>Basis \<rightarrow>\<^sub>E \<rat> \<times> \<rat>. box (?a f) (?b f) \<subseteq> S}"
lp15@66154
   423
  let ?\<D> = "(\<lambda>f. box (?a f) (?b f)) ` ?I"
lp15@66154
   424
  show ?thesis
lp15@66154
   425
  proof
lp15@66154
   426
    have "countable ?I"
lp15@66154
   427
      by (simp add: countable_PiE countable_rat)
lp15@66154
   428
    then show "countable ?\<D>"
lp15@66154
   429
      by blast
lp15@66154
   430
    show "\<Union>?\<D> = S"
lp15@66154
   431
      using open_UNION_box [OF assms] by metis
lp15@66154
   432
  qed auto
lp15@66154
   433
qed
lp15@66154
   434
lp15@66154
   435
lemma rational_cboxes:
lp15@66154
   436
  fixes x :: "'a::euclidean_space"
lp15@66154
   437
  assumes "e > 0"
lp15@66154
   438
  shows "\<exists>a b. (\<forall>i\<in>Basis. a \<bullet> i \<in> \<rat> \<and> b \<bullet> i \<in> \<rat>) \<and> x \<in> cbox a b \<and> cbox a b \<subseteq> ball x e"
lp15@66154
   439
proof -
lp15@66154
   440
  define e' where "e' = e / (2 * sqrt (real (DIM ('a))))"
lp15@66154
   441
  then have e: "e' > 0"
lp15@66154
   442
    using assms by auto
lp15@66154
   443
  have "\<forall>i. \<exists>y. y \<in> \<rat> \<and> y < x \<bullet> i \<and> x \<bullet> i - y < e'" (is "\<forall>i. ?th i")
lp15@66154
   444
  proof
lp15@66154
   445
    fix i
lp15@66154
   446
    from Rats_dense_in_real[of "x \<bullet> i - e'" "x \<bullet> i"] e
lp15@66154
   447
    show "?th i" by auto
lp15@66154
   448
  qed
lp15@66154
   449
  from choice[OF this] obtain a where
lp15@66154
   450
    a: "\<forall>u. a u \<in> \<rat> \<and> a u < x \<bullet> u \<and> x \<bullet> u - a u < e'" ..
lp15@66154
   451
  have "\<forall>i. \<exists>y. y \<in> \<rat> \<and> x \<bullet> i < y \<and> y - x \<bullet> i < e'" (is "\<forall>i. ?th i")
lp15@66154
   452
  proof
lp15@66154
   453
    fix i
lp15@66154
   454
    from Rats_dense_in_real[of "x \<bullet> i" "x \<bullet> i + e'"] e
lp15@66154
   455
    show "?th i" by auto
lp15@66154
   456
  qed
lp15@66154
   457
  from choice[OF this] obtain b where
lp15@66154
   458
    b: "\<forall>u. b u \<in> \<rat> \<and> x \<bullet> u < b u \<and> b u - x \<bullet> u < e'" ..
lp15@66154
   459
  let ?a = "\<Sum>i\<in>Basis. a i *\<^sub>R i" and ?b = "\<Sum>i\<in>Basis. b i *\<^sub>R i"
lp15@66154
   460
  show ?thesis
lp15@66154
   461
  proof (rule exI[of _ ?a], rule exI[of _ ?b], safe)
lp15@66154
   462
    fix y :: 'a
lp15@66154
   463
    assume *: "y \<in> cbox ?a ?b"
lp15@66154
   464
    have "dist x y = sqrt (\<Sum>i\<in>Basis. (dist (x \<bullet> i) (y \<bullet> i))\<^sup>2)"
nipkow@67155
   465
      unfolding L2_set_def[symmetric] by (rule euclidean_dist_l2)
lp15@66154
   466
    also have "\<dots> < sqrt (\<Sum>(i::'a)\<in>Basis. e^2 / real (DIM('a)))"
lp15@66154
   467
    proof (rule real_sqrt_less_mono, rule sum_strict_mono)
lp15@66154
   468
      fix i :: "'a"
lp15@66154
   469
      assume i: "i \<in> Basis"
lp15@66154
   470
      have "a i \<le> y\<bullet>i \<and> y\<bullet>i \<le> b i"
lp15@66154
   471
        using * i by (auto simp: cbox_def)
lp15@66154
   472
      moreover have "a i < x\<bullet>i" "x\<bullet>i - a i < e'"
lp15@66154
   473
        using a by auto
lp15@66154
   474
      moreover have "x\<bullet>i < b i" "b i - x\<bullet>i < e'"
lp15@66154
   475
        using b by auto
lp15@66154
   476
      ultimately have "\<bar>x\<bullet>i - y\<bullet>i\<bar> < 2 * e'"
lp15@66154
   477
        by auto
lp15@66154
   478
      then have "dist (x \<bullet> i) (y \<bullet> i) < e/sqrt (real (DIM('a)))"
lp15@66154
   479
        unfolding e'_def by (auto simp: dist_real_def)
lp15@66154
   480
      then have "(dist (x \<bullet> i) (y \<bullet> i))\<^sup>2 < (e/sqrt (real (DIM('a))))\<^sup>2"
lp15@66154
   481
        by (rule power_strict_mono) auto
lp15@66154
   482
      then show "(dist (x \<bullet> i) (y \<bullet> i))\<^sup>2 < e\<^sup>2 / real DIM('a)"
lp15@66154
   483
        by (simp add: power_divide)
lp15@66154
   484
    qed auto
lp15@66154
   485
    also have "\<dots> = e"
lp15@66154
   486
      using \<open>0 < e\<close> by simp
lp15@66154
   487
    finally show "y \<in> ball x e"
lp15@66154
   488
      by (auto simp: ball_def)
lp15@66154
   489
  next
lp15@66154
   490
    show "x \<in> cbox (\<Sum>i\<in>Basis. a i *\<^sub>R i) (\<Sum>i\<in>Basis. b i *\<^sub>R i)"
lp15@66154
   491
      using a b less_imp_le by (auto simp: cbox_def)
lp15@66154
   492
  qed (use a b cbox_def in auto)
lp15@66154
   493
qed
lp15@66154
   494
lp15@66154
   495
lemma open_UNION_cbox:
lp15@66154
   496
  fixes M :: "'a::euclidean_space set"
lp15@66154
   497
  assumes "open M"
lp15@66154
   498
  defines "a' \<equiv> \<lambda>f. (\<Sum>(i::'a)\<in>Basis. fst (f i) *\<^sub>R i)"
lp15@66154
   499
  defines "b' \<equiv> \<lambda>f. (\<Sum>(i::'a)\<in>Basis. snd (f i) *\<^sub>R i)"
lp15@66154
   500
  defines "I \<equiv> {f\<in>Basis \<rightarrow>\<^sub>E \<rat> \<times> \<rat>. cbox (a' f) (b' f) \<subseteq> M}"
lp15@66154
   501
  shows "M = (\<Union>f\<in>I. cbox (a' f) (b' f))"
lp15@66154
   502
proof -
lp15@66154
   503
  have "x \<in> (\<Union>f\<in>I. cbox (a' f) (b' f))" if "x \<in> M" for x
lp15@66154
   504
  proof -
lp15@66154
   505
    obtain e where e: "e > 0" "ball x e \<subseteq> M"
lp15@66154
   506
      using openE[OF \<open>open M\<close> \<open>x \<in> M\<close>] by auto
lp15@66154
   507
    moreover obtain a b where ab: "x \<in> cbox a b" "\<forall>i \<in> Basis. a \<bullet> i \<in> \<rat>"
lp15@66154
   508
                                  "\<forall>i \<in> Basis. b \<bullet> i \<in> \<rat>" "cbox a b \<subseteq> ball x e"
lp15@66154
   509
      using rational_cboxes[OF e(1)] by metis
lp15@66154
   510
    ultimately show ?thesis
lp15@66154
   511
       by (intro UN_I[of "\<lambda>i\<in>Basis. (a \<bullet> i, b \<bullet> i)"])
lp15@66154
   512
          (auto simp: euclidean_representation I_def a'_def b'_def)
lp15@66154
   513
  qed
lp15@66154
   514
  then show ?thesis by (auto simp: I_def)
lp15@66154
   515
qed
lp15@66154
   516
lp15@66154
   517
corollary open_countable_Union_open_cbox:
lp15@66154
   518
  fixes S :: "'a :: euclidean_space set"
lp15@66154
   519
  assumes "open S"
lp15@66154
   520
  obtains \<D> where "countable \<D>" "\<D> \<subseteq> Pow S" "\<And>X. X \<in> \<D> \<Longrightarrow> \<exists>a b. X = cbox a b" "\<Union>\<D> = S"
lp15@66154
   521
proof -
lp15@66154
   522
  let ?a = "\<lambda>f. (\<Sum>(i::'a)\<in>Basis. fst (f i) *\<^sub>R i)"
lp15@66154
   523
  let ?b = "\<lambda>f. (\<Sum>(i::'a)\<in>Basis. snd (f i) *\<^sub>R i)"
lp15@66154
   524
  let ?I = "{f\<in>Basis \<rightarrow>\<^sub>E \<rat> \<times> \<rat>. cbox (?a f) (?b f) \<subseteq> S}"
lp15@66154
   525
  let ?\<D> = "(\<lambda>f. cbox (?a f) (?b f)) ` ?I"
lp15@66154
   526
  show ?thesis
lp15@66154
   527
  proof
lp15@66154
   528
    have "countable ?I"
lp15@66154
   529
      by (simp add: countable_PiE countable_rat)
lp15@66154
   530
    then show "countable ?\<D>"
lp15@66154
   531
      by blast
lp15@66154
   532
    show "\<Union>?\<D> = S"
lp15@66154
   533
      using open_UNION_cbox [OF assms] by metis
lp15@66154
   534
  qed auto
lp15@66154
   535
qed
lp15@66154
   536
immler@56189
   537
lemma box_eq_empty:
immler@56189
   538
  fixes a :: "'a::euclidean_space"
immler@56189
   539
  shows "(box a b = {} \<longleftrightarrow> (\<exists>i\<in>Basis. b\<bullet>i \<le> a\<bullet>i))" (is ?th1)
immler@56189
   540
    and "(cbox a b = {} \<longleftrightarrow> (\<exists>i\<in>Basis. b\<bullet>i < a\<bullet>i))" (is ?th2)
immler@56189
   541
proof -
immler@56189
   542
  {
immler@56189
   543
    fix i x
immler@56189
   544
    assume i: "i\<in>Basis" and as:"b\<bullet>i \<le> a\<bullet>i" and x:"x\<in>box a b"
immler@56189
   545
    then have "a \<bullet> i < x \<bullet> i \<and> x \<bullet> i < b \<bullet> i"
immler@56189
   546
      unfolding mem_box by (auto simp: box_def)
immler@56189
   547
    then have "a\<bullet>i < b\<bullet>i" by auto
immler@56189
   548
    then have False using as by auto
immler@56189
   549
  }
immler@56189
   550
  moreover
immler@56189
   551
  {
immler@56189
   552
    assume as: "\<forall>i\<in>Basis. \<not> (b\<bullet>i \<le> a\<bullet>i)"
immler@56189
   553
    let ?x = "(1/2) *\<^sub>R (a + b)"
immler@56189
   554
    {
immler@56189
   555
      fix i :: 'a
immler@56189
   556
      assume i: "i \<in> Basis"
immler@56189
   557
      have "a\<bullet>i < b\<bullet>i"
immler@56189
   558
        using as[THEN bspec[where x=i]] i by auto
immler@56189
   559
      then have "a\<bullet>i < ((1/2) *\<^sub>R (a+b)) \<bullet> i" "((1/2) *\<^sub>R (a+b)) \<bullet> i < b\<bullet>i"
immler@56189
   560
        by (auto simp: inner_add_left)
immler@56189
   561
    }
immler@56189
   562
    then have "box a b \<noteq> {}"
immler@56189
   563
      using mem_box(1)[of "?x" a b] by auto
immler@56189
   564
  }
immler@56189
   565
  ultimately show ?th1 by blast
immler@56189
   566
immler@56189
   567
  {
immler@56189
   568
    fix i x
immler@56189
   569
    assume i: "i \<in> Basis" and as:"b\<bullet>i < a\<bullet>i" and x:"x\<in>cbox a b"
immler@56189
   570
    then have "a \<bullet> i \<le> x \<bullet> i \<and> x \<bullet> i \<le> b \<bullet> i"
immler@56189
   571
      unfolding mem_box by auto
immler@56189
   572
    then have "a\<bullet>i \<le> b\<bullet>i" by auto
immler@56189
   573
    then have False using as by auto
immler@56189
   574
  }
immler@56189
   575
  moreover
immler@56189
   576
  {
immler@56189
   577
    assume as:"\<forall>i\<in>Basis. \<not> (b\<bullet>i < a\<bullet>i)"
immler@56189
   578
    let ?x = "(1/2) *\<^sub>R (a + b)"
immler@56189
   579
    {
immler@56189
   580
      fix i :: 'a
immler@56189
   581
      assume i:"i \<in> Basis"
immler@56189
   582
      have "a\<bullet>i \<le> b\<bullet>i"
immler@56189
   583
        using as[THEN bspec[where x=i]] i by auto
immler@56189
   584
      then have "a\<bullet>i \<le> ((1/2) *\<^sub>R (a+b)) \<bullet> i" "((1/2) *\<^sub>R (a+b)) \<bullet> i \<le> b\<bullet>i"
immler@56189
   585
        by (auto simp: inner_add_left)
immler@56189
   586
    }
immler@56189
   587
    then have "cbox a b \<noteq> {}"
immler@56189
   588
      using mem_box(2)[of "?x" a b] by auto
immler@56189
   589
  }
immler@56189
   590
  ultimately show ?th2 by blast
immler@56189
   591
qed
immler@56189
   592
immler@56189
   593
lemma box_ne_empty:
immler@56189
   594
  fixes a :: "'a::euclidean_space"
immler@56189
   595
  shows "cbox a b \<noteq> {} \<longleftrightarrow> (\<forall>i\<in>Basis. a\<bullet>i \<le> b\<bullet>i)"
immler@56189
   596
  and "box a b \<noteq> {} \<longleftrightarrow> (\<forall>i\<in>Basis. a\<bullet>i < b\<bullet>i)"
immler@56189
   597
  unfolding box_eq_empty[of a b] by fastforce+
immler@56189
   598
immler@56189
   599
lemma
immler@56189
   600
  fixes a :: "'a::euclidean_space"
lp15@66112
   601
  shows cbox_sing [simp]: "cbox a a = {a}"
lp15@66112
   602
    and box_sing [simp]: "box a a = {}"
immler@56189
   603
  unfolding set_eq_iff mem_box eq_iff [symmetric]
immler@56189
   604
  by (auto intro!: euclidean_eqI[where 'a='a])
immler@56189
   605
     (metis all_not_in_conv nonempty_Basis)
immler@56189
   606
immler@56189
   607
lemma subset_box_imp:
immler@56189
   608
  fixes a :: "'a::euclidean_space"
immler@56189
   609
  shows "(\<forall>i\<in>Basis. a\<bullet>i \<le> c\<bullet>i \<and> d\<bullet>i \<le> b\<bullet>i) \<Longrightarrow> cbox c d \<subseteq> cbox a b"
immler@56189
   610
    and "(\<forall>i\<in>Basis. a\<bullet>i < c\<bullet>i \<and> d\<bullet>i < b\<bullet>i) \<Longrightarrow> cbox c d \<subseteq> box a b"
immler@56189
   611
    and "(\<forall>i\<in>Basis. a\<bullet>i \<le> c\<bullet>i \<and> d\<bullet>i \<le> b\<bullet>i) \<Longrightarrow> box c d \<subseteq> cbox a b"
immler@56189
   612
     and "(\<forall>i\<in>Basis. a\<bullet>i \<le> c\<bullet>i \<and> d\<bullet>i \<le> b\<bullet>i) \<Longrightarrow> box c d \<subseteq> box a b"
immler@56189
   613
  unfolding subset_eq[unfolded Ball_def] unfolding mem_box
wenzelm@58757
   614
  by (best intro: order_trans less_le_trans le_less_trans less_imp_le)+
immler@56189
   615
immler@56189
   616
lemma box_subset_cbox:
immler@56189
   617
  fixes a :: "'a::euclidean_space"
immler@56189
   618
  shows "box a b \<subseteq> cbox a b"
immler@56189
   619
  unfolding subset_eq [unfolded Ball_def] mem_box
immler@56189
   620
  by (fast intro: less_imp_le)
immler@56189
   621
immler@56189
   622
lemma subset_box:
immler@56189
   623
  fixes a :: "'a::euclidean_space"
wenzelm@64539
   624
  shows "cbox c d \<subseteq> cbox a b \<longleftrightarrow> (\<forall>i\<in>Basis. c\<bullet>i \<le> d\<bullet>i) \<longrightarrow> (\<forall>i\<in>Basis. a\<bullet>i \<le> c\<bullet>i \<and> d\<bullet>i \<le> b\<bullet>i)" (is ?th1)
wenzelm@64539
   625
    and "cbox c d \<subseteq> box a b \<longleftrightarrow> (\<forall>i\<in>Basis. c\<bullet>i \<le> d\<bullet>i) \<longrightarrow> (\<forall>i\<in>Basis. a\<bullet>i < c\<bullet>i \<and> d\<bullet>i < b\<bullet>i)" (is ?th2)
wenzelm@64539
   626
    and "box c d \<subseteq> cbox a b \<longleftrightarrow> (\<forall>i\<in>Basis. c\<bullet>i < d\<bullet>i) \<longrightarrow> (\<forall>i\<in>Basis. a\<bullet>i \<le> c\<bullet>i \<and> d\<bullet>i \<le> b\<bullet>i)" (is ?th3)
wenzelm@64539
   627
    and "box c d \<subseteq> box a b \<longleftrightarrow> (\<forall>i\<in>Basis. c\<bullet>i < d\<bullet>i) \<longrightarrow> (\<forall>i\<in>Basis. a\<bullet>i \<le> c\<bullet>i \<and> d\<bullet>i \<le> b\<bullet>i)" (is ?th4)
immler@56189
   628
proof -
lp15@68120
   629
  let ?lesscd = "\<forall>i\<in>Basis. c\<bullet>i < d\<bullet>i"
lp15@68120
   630
  let ?lerhs = "\<forall>i\<in>Basis. a\<bullet>i \<le> c\<bullet>i \<and> d\<bullet>i \<le> b\<bullet>i"
lp15@68120
   631
  show ?th1 ?th2
lp15@68120
   632
    by (fastforce simp: mem_box)+
lp15@68120
   633
  have acdb: "a\<bullet>i \<le> c\<bullet>i \<and> d\<bullet>i \<le> b\<bullet>i"
lp15@68120
   634
    if i: "i \<in> Basis" and box: "box c d \<subseteq> cbox a b" and cd: "\<And>i. i \<in> Basis \<Longrightarrow> c\<bullet>i < d\<bullet>i" for i
lp15@68120
   635
  proof -
lp15@68120
   636
    have "box c d \<noteq> {}"
lp15@68120
   637
      using that
lp15@68120
   638
      unfolding box_eq_empty by force
lp15@68120
   639
    { let ?x = "(\<Sum>j\<in>Basis. (if j=i then ((min (a\<bullet>j) (d\<bullet>j))+c\<bullet>j)/2 else (c\<bullet>j+d\<bullet>j)/2) *\<^sub>R j)::'a"
lp15@68120
   640
      assume *: "a\<bullet>i > c\<bullet>i"
lp15@68120
   641
      then have "c \<bullet> j < ?x \<bullet> j \<and> ?x \<bullet> j < d \<bullet> j" if "j \<in> Basis" for j
lp15@68120
   642
        using cd that by (fastforce simp add: i *)
lp15@68120
   643
      then have "?x \<in> box c d"
lp15@68120
   644
        unfolding mem_box by auto
lp15@68120
   645
      moreover have "?x \<notin> cbox a b"
lp15@68120
   646
        using i cd * by (force simp: mem_box)
lp15@68120
   647
      ultimately have False using box by auto
immler@56189
   648
    }
lp15@68120
   649
    then have "a\<bullet>i \<le> c\<bullet>i" by force
immler@56189
   650
    moreover
lp15@68120
   651
    { let ?x = "(\<Sum>j\<in>Basis. (if j=i then ((max (b\<bullet>j) (c\<bullet>j))+d\<bullet>j)/2 else (c\<bullet>j+d\<bullet>j)/2) *\<^sub>R j)::'a"
lp15@68120
   652
      assume *: "b\<bullet>i < d\<bullet>i"
lp15@68120
   653
      then have "d \<bullet> j > ?x \<bullet> j \<and> ?x \<bullet> j > c \<bullet> j" if "j \<in> Basis" for j
lp15@68120
   654
        using cd that by (fastforce simp add: i *)
lp15@68120
   655
      then have "?x \<in> box c d"
immler@56189
   656
        unfolding mem_box by auto
lp15@68120
   657
      moreover have "?x \<notin> cbox a b"
lp15@68120
   658
        using i cd * by (force simp: mem_box)
lp15@68120
   659
      ultimately have False using box by auto
immler@56189
   660
    }
immler@56189
   661
    then have "b\<bullet>i \<ge> d\<bullet>i" by (rule ccontr) auto
lp15@68120
   662
    ultimately show ?thesis by auto
lp15@68120
   663
  qed
immler@56189
   664
  show ?th3
lp15@68120
   665
    using acdb by (fastforce simp add: mem_box)
lp15@68120
   666
  have acdb': "a\<bullet>i \<le> c\<bullet>i \<and> d\<bullet>i \<le> b\<bullet>i"
lp15@68120
   667
    if "i \<in> Basis" "box c d \<subseteq> box a b" "\<And>i. i \<in> Basis \<Longrightarrow> c\<bullet>i < d\<bullet>i" for i
lp15@68120
   668
      using box_subset_cbox[of a b] that acdb by auto
immler@56189
   669
  show ?th4
lp15@68120
   670
    using acdb' by (fastforce simp add: mem_box)
immler@56189
   671
qed
immler@56189
   672
lp15@63945
   673
lemma eq_cbox: "cbox a b = cbox c d \<longleftrightarrow> cbox a b = {} \<and> cbox c d = {} \<or> a = c \<and> b = d"
lp15@63945
   674
      (is "?lhs = ?rhs")
lp15@63945
   675
proof
lp15@63945
   676
  assume ?lhs
lp15@63945
   677
  then have "cbox a b \<subseteq> cbox c d" "cbox c d \<subseteq> cbox a b"
lp15@63945
   678
    by auto
lp15@63945
   679
  then show ?rhs
lp15@66643
   680
    by (force simp: subset_box box_eq_empty intro: antisym euclidean_eqI)
lp15@63945
   681
next
lp15@63945
   682
  assume ?rhs
lp15@63945
   683
  then show ?lhs
lp15@63945
   684
    by force
lp15@63945
   685
qed
lp15@63945
   686
lp15@63945
   687
lemma eq_cbox_box [simp]: "cbox a b = box c d \<longleftrightarrow> cbox a b = {} \<and> box c d = {}"
wenzelm@64539
   688
  (is "?lhs \<longleftrightarrow> ?rhs")
lp15@63945
   689
proof
lp15@68120
   690
  assume L: ?lhs
lp15@68120
   691
  then have "cbox a b \<subseteq> box c d" "box c d \<subseteq> cbox a b"
lp15@63945
   692
    by auto
lp15@63945
   693
  then show ?rhs
hoelzl@63957
   694
    apply (simp add: subset_box)
lp15@68120
   695
    using L box_ne_empty box_sing apply (fastforce simp add:)
lp15@63945
   696
    done
lp15@68120
   697
qed force
lp15@63945
   698
lp15@63945
   699
lemma eq_box_cbox [simp]: "box a b = cbox c d \<longleftrightarrow> box a b = {} \<and> cbox c d = {}"
lp15@63945
   700
  by (metis eq_cbox_box)
lp15@63945
   701
lp15@63945
   702
lemma eq_box: "box a b = box c d \<longleftrightarrow> box a b = {} \<and> box c d = {} \<or> a = c \<and> b = d"
wenzelm@64539
   703
  (is "?lhs \<longleftrightarrow> ?rhs")
lp15@63945
   704
proof
lp15@68120
   705
  assume L: ?lhs
lp15@63945
   706
  then have "box a b \<subseteq> box c d" "box c d \<subseteq> box a b"
lp15@63945
   707
    by auto
lp15@63945
   708
  then show ?rhs
lp15@63945
   709
    apply (simp add: subset_box)
lp15@68120
   710
    using box_ne_empty(2) L
lp15@63945
   711
    apply auto
lp15@63945
   712
     apply (meson euclidean_eqI less_eq_real_def not_less)+
lp15@63945
   713
    done
lp15@68120
   714
qed force
lp15@63945
   715
eberlm@66466
   716
lemma subset_box_complex:
lp15@66643
   717
   "cbox a b \<subseteq> cbox c d \<longleftrightarrow>
eberlm@66466
   718
      (Re a \<le> Re b \<and> Im a \<le> Im b) \<longrightarrow> Re a \<ge> Re c \<and> Im a \<ge> Im c \<and> Re b \<le> Re d \<and> Im b \<le> Im d"
lp15@66643
   719
   "cbox a b \<subseteq> box c d \<longleftrightarrow>
eberlm@66466
   720
      (Re a \<le> Re b \<and> Im a \<le> Im b) \<longrightarrow> Re a > Re c \<and> Im a > Im c \<and> Re b < Re d \<and> Im b < Im d"
eberlm@66466
   721
   "box a b \<subseteq> cbox c d \<longleftrightarrow>
eberlm@66466
   722
      (Re a < Re b \<and> Im a < Im b) \<longrightarrow> Re a \<ge> Re c \<and> Im a \<ge> Im c \<and> Re b \<le> Re d \<and> Im b \<le> Im d"
lp15@66643
   723
   "box a b \<subseteq> box c d \<longleftrightarrow>
eberlm@66466
   724
      (Re a < Re b \<and> Im a < Im b) \<longrightarrow> Re a \<ge> Re c \<and> Im a \<ge> Im c \<and> Re b \<le> Re d \<and> Im b \<le> Im d"
eberlm@66466
   725
  by (subst subset_box; force simp: Basis_complex_def)+
eberlm@66466
   726
lp15@63945
   727
lemma Int_interval:
immler@56189
   728
  fixes a :: "'a::euclidean_space"
immler@56189
   729
  shows "cbox a b \<inter> cbox c d =
immler@56189
   730
    cbox (\<Sum>i\<in>Basis. max (a\<bullet>i) (c\<bullet>i) *\<^sub>R i) (\<Sum>i\<in>Basis. min (b\<bullet>i) (d\<bullet>i) *\<^sub>R i)"
immler@56189
   731
  unfolding set_eq_iff and Int_iff and mem_box
immler@56189
   732
  by auto
immler@56189
   733
immler@56189
   734
lemma disjoint_interval:
immler@56189
   735
  fixes a::"'a::euclidean_space"
immler@56189
   736
  shows "cbox a b \<inter> cbox c d = {} \<longleftrightarrow> (\<exists>i\<in>Basis. (b\<bullet>i < a\<bullet>i \<or> d\<bullet>i < c\<bullet>i \<or> b\<bullet>i < c\<bullet>i \<or> d\<bullet>i < a\<bullet>i))" (is ?th1)
immler@56189
   737
    and "cbox a b \<inter> box c d = {} \<longleftrightarrow> (\<exists>i\<in>Basis. (b\<bullet>i < a\<bullet>i \<or> d\<bullet>i \<le> c\<bullet>i \<or> b\<bullet>i \<le> c\<bullet>i \<or> d\<bullet>i \<le> a\<bullet>i))" (is ?th2)
immler@56189
   738
    and "box a b \<inter> cbox c d = {} \<longleftrightarrow> (\<exists>i\<in>Basis. (b\<bullet>i \<le> a\<bullet>i \<or> d\<bullet>i < c\<bullet>i \<or> b\<bullet>i \<le> c\<bullet>i \<or> d\<bullet>i \<le> a\<bullet>i))" (is ?th3)
immler@56189
   739
    and "box a b \<inter> box c d = {} \<longleftrightarrow> (\<exists>i\<in>Basis. (b\<bullet>i \<le> a\<bullet>i \<or> d\<bullet>i \<le> c\<bullet>i \<or> b\<bullet>i \<le> c\<bullet>i \<or> d\<bullet>i \<le> a\<bullet>i))" (is ?th4)
immler@56189
   740
proof -
immler@56189
   741
  let ?z = "(\<Sum>i\<in>Basis. (((max (a\<bullet>i) (c\<bullet>i)) + (min (b\<bullet>i) (d\<bullet>i))) / 2) *\<^sub>R i)::'a"
immler@56189
   742
  have **: "\<And>P Q. (\<And>i :: 'a. i \<in> Basis \<Longrightarrow> Q ?z i \<Longrightarrow> P i) \<Longrightarrow>
immler@56189
   743
      (\<And>i x :: 'a. i \<in> Basis \<Longrightarrow> P i \<Longrightarrow> Q x i) \<Longrightarrow> (\<forall>x. \<exists>i\<in>Basis. Q x i) \<longleftrightarrow> (\<exists>i\<in>Basis. P i)"
immler@56189
   744
    by blast
immler@56189
   745
  note * = set_eq_iff Int_iff empty_iff mem_box ball_conj_distrib[symmetric] eq_False ball_simps(10)
immler@56189
   746
  show ?th1 unfolding * by (intro **) auto
immler@56189
   747
  show ?th2 unfolding * by (intro **) auto
immler@56189
   748
  show ?th3 unfolding * by (intro **) auto
immler@56189
   749
  show ?th4 unfolding * by (intro **) auto
immler@56189
   750
qed
immler@56189
   751
hoelzl@57447
   752
lemma UN_box_eq_UNIV: "(\<Union>i::nat. box (- (real i *\<^sub>R One)) (real i *\<^sub>R One)) = UNIV"
hoelzl@57447
   753
proof -
wenzelm@61942
   754
  have "\<bar>x \<bullet> b\<bar> < real_of_int (\<lceil>Max ((\<lambda>b. \<bar>x \<bullet> b\<bar>)`Basis)\<rceil> + 1)"
wenzelm@60462
   755
    if [simp]: "b \<in> Basis" for x b :: 'a
wenzelm@60462
   756
  proof -
wenzelm@61942
   757
    have "\<bar>x \<bullet> b\<bar> \<le> real_of_int \<lceil>\<bar>x \<bullet> b\<bar>\<rceil>"
lp15@61609
   758
      by (rule le_of_int_ceiling)
wenzelm@61942
   759
    also have "\<dots> \<le> real_of_int \<lceil>Max ((\<lambda>b. \<bar>x \<bullet> b\<bar>)`Basis)\<rceil>"
nipkow@59587
   760
      by (auto intro!: ceiling_mono)
wenzelm@61942
   761
    also have "\<dots> < real_of_int (\<lceil>Max ((\<lambda>b. \<bar>x \<bullet> b\<bar>)`Basis)\<rceil> + 1)"
hoelzl@57447
   762
      by simp
wenzelm@60462
   763
    finally show ?thesis .
wenzelm@60462
   764
  qed
wenzelm@60462
   765
  then have "\<exists>n::nat. \<forall>b\<in>Basis. \<bar>x \<bullet> b\<bar> < real n" for x :: 'a
nipkow@59587
   766
    by (metis order.strict_trans reals_Archimedean2)
hoelzl@57447
   767
  moreover have "\<And>x b::'a. \<And>n::nat.  \<bar>x \<bullet> b\<bar> < real n \<longleftrightarrow> - real n < x \<bullet> b \<and> x \<bullet> b < real n"
hoelzl@57447
   768
    by auto
hoelzl@57447
   769
  ultimately show ?thesis
nipkow@64267
   770
    by (auto simp: box_def inner_sum_left inner_Basis sum.If_cases)
hoelzl@57447
   771
qed
hoelzl@57447
   772
immler@69613
   773
lemma image_affinity_cbox: fixes m::real
immler@69613
   774
  fixes a b c :: "'a::euclidean_space"
immler@69613
   775
  shows "(\<lambda>x. m *\<^sub>R x + c) ` cbox a b =
immler@69613
   776
    (if cbox a b = {} then {}
immler@69613
   777
     else (if 0 \<le> m then cbox (m *\<^sub>R a + c) (m *\<^sub>R b + c)
immler@69613
   778
     else cbox (m *\<^sub>R b + c) (m *\<^sub>R a + c)))"
immler@69613
   779
proof (cases "m = 0")
immler@69613
   780
  case True
immler@69613
   781
  {
immler@69613
   782
    fix x
immler@69613
   783
    assume "\<forall>i\<in>Basis. x \<bullet> i \<le> c \<bullet> i" "\<forall>i\<in>Basis. c \<bullet> i \<le> x \<bullet> i"
immler@69613
   784
    then have "x = c"
immler@69613
   785
      by (simp add: dual_order.antisym euclidean_eqI)
immler@69613
   786
  }
immler@69613
   787
  moreover have "c \<in> cbox (m *\<^sub>R a + c) (m *\<^sub>R b + c)"
immler@69613
   788
    unfolding True by (auto simp: cbox_sing)
immler@69613
   789
  ultimately show ?thesis using True by (auto simp: cbox_def)
immler@69613
   790
next
immler@69613
   791
  case False
immler@69613
   792
  {
immler@69613
   793
    fix y
immler@69613
   794
    assume "\<forall>i\<in>Basis. a \<bullet> i \<le> y \<bullet> i" "\<forall>i\<in>Basis. y \<bullet> i \<le> b \<bullet> i" "m > 0"
immler@69613
   795
    then have "\<forall>i\<in>Basis. (m *\<^sub>R a + c) \<bullet> i \<le> (m *\<^sub>R y + c) \<bullet> i" and "\<forall>i\<in>Basis. (m *\<^sub>R y + c) \<bullet> i \<le> (m *\<^sub>R b + c) \<bullet> i"
immler@69613
   796
      by (auto simp: inner_distrib)
immler@69613
   797
  }
immler@69613
   798
  moreover
immler@69613
   799
  {
immler@69613
   800
    fix y
immler@69613
   801
    assume "\<forall>i\<in>Basis. a \<bullet> i \<le> y \<bullet> i" "\<forall>i\<in>Basis. y \<bullet> i \<le> b \<bullet> i" "m < 0"
immler@69613
   802
    then have "\<forall>i\<in>Basis. (m *\<^sub>R b + c) \<bullet> i \<le> (m *\<^sub>R y + c) \<bullet> i" and "\<forall>i\<in>Basis. (m *\<^sub>R y + c) \<bullet> i \<le> (m *\<^sub>R a + c) \<bullet> i"
immler@69613
   803
      by (auto simp: mult_left_mono_neg inner_distrib)
immler@69613
   804
  }
immler@69613
   805
  moreover
immler@69613
   806
  {
immler@69613
   807
    fix y
immler@69613
   808
    assume "m > 0" and "\<forall>i\<in>Basis. (m *\<^sub>R a + c) \<bullet> i \<le> y \<bullet> i" and "\<forall>i\<in>Basis. y \<bullet> i \<le> (m *\<^sub>R b + c) \<bullet> i"
immler@69613
   809
    then have "y \<in> (\<lambda>x. m *\<^sub>R x + c) ` cbox a b"
immler@69613
   810
      unfolding image_iff Bex_def mem_box
immler@69613
   811
      apply (intro exI[where x="(1 / m) *\<^sub>R (y - c)"])
immler@69613
   812
      apply (auto simp: pos_le_divide_eq pos_divide_le_eq mult.commute inner_distrib inner_diff_left)
immler@69613
   813
      done
immler@69613
   814
  }
immler@69613
   815
  moreover
immler@69613
   816
  {
immler@69613
   817
    fix y
immler@69613
   818
    assume "\<forall>i\<in>Basis. (m *\<^sub>R b + c) \<bullet> i \<le> y \<bullet> i" "\<forall>i\<in>Basis. y \<bullet> i \<le> (m *\<^sub>R a + c) \<bullet> i" "m < 0"
immler@69613
   819
    then have "y \<in> (\<lambda>x. m *\<^sub>R x + c) ` cbox a b"
immler@69613
   820
      unfolding image_iff Bex_def mem_box
immler@69613
   821
      apply (intro exI[where x="(1 / m) *\<^sub>R (y - c)"])
immler@69613
   822
      apply (auto simp: neg_le_divide_eq neg_divide_le_eq mult.commute inner_distrib inner_diff_left)
immler@69613
   823
      done
immler@69613
   824
  }
immler@69613
   825
  ultimately show ?thesis using False by (auto simp: cbox_def)
immler@69613
   826
qed
immler@69613
   827
immler@69613
   828
lemma image_smult_cbox:"(\<lambda>x. m *\<^sub>R (x::_::euclidean_space)) ` cbox a b =
immler@69613
   829
  (if cbox a b = {} then {} else if 0 \<le> m then cbox (m *\<^sub>R a) (m *\<^sub>R b) else cbox (m *\<^sub>R b) (m *\<^sub>R a))"
immler@69613
   830
  using image_affinity_cbox[of m 0 a b] by auto
immler@69613
   831
immler@69516
   832
nipkow@69508
   833
subsection \<open>General Intervals\<close>
immler@67962
   834
immler@67962
   835
definition%important "is_interval (s::('a::euclidean_space) set) \<longleftrightarrow>
immler@56189
   836
  (\<forall>a\<in>s. \<forall>b\<in>s. \<forall>x. (\<forall>i\<in>Basis. ((a\<bullet>i \<le> x\<bullet>i \<and> x\<bullet>i \<le> b\<bullet>i) \<or> (b\<bullet>i \<le> x\<bullet>i \<and> x\<bullet>i \<le> a\<bullet>i))) \<longrightarrow> x \<in> s)"
immler@56189
   837
immler@67685
   838
lemma is_interval_1:
immler@67685
   839
  "is_interval (s::real set) \<longleftrightarrow> (\<forall>a\<in>s. \<forall>b\<in>s. \<forall> x. a \<le> x \<and> x \<le> b \<longrightarrow> x \<in> s)"
immler@67685
   840
  unfolding is_interval_def by auto
immler@67685
   841
immler@67685
   842
lemma is_interval_inter: "is_interval X \<Longrightarrow> is_interval Y \<Longrightarrow> is_interval (X \<inter> Y)"
immler@67685
   843
  unfolding is_interval_def
immler@67685
   844
  by blast
immler@67685
   845
lp15@66089
   846
lemma is_interval_cbox [simp]: "is_interval (cbox a (b::'a::euclidean_space))" (is ?th1)
lp15@66089
   847
  and is_interval_box [simp]: "is_interval (box a b)" (is ?th2)
immler@56189
   848
  unfolding is_interval_def mem_box Ball_def atLeastAtMost_iff
immler@56189
   849
  by (meson order_trans le_less_trans less_le_trans less_trans)+
immler@56189
   850
lp15@61609
   851
lemma is_interval_empty [iff]: "is_interval {}"
lp15@61609
   852
  unfolding is_interval_def  by simp
lp15@61609
   853
lp15@61609
   854
lemma is_interval_univ [iff]: "is_interval UNIV"
lp15@61609
   855
  unfolding is_interval_def  by simp
immler@56189
   856
immler@56189
   857
lemma mem_is_intervalI:
immler@56189
   858
  assumes "is_interval s"
wenzelm@64539
   859
    and "a \<in> s" "b \<in> s"
wenzelm@64539
   860
    and "\<And>i. i \<in> Basis \<Longrightarrow> a \<bullet> i \<le> x \<bullet> i \<and> x \<bullet> i \<le> b \<bullet> i \<or> b \<bullet> i \<le> x \<bullet> i \<and> x \<bullet> i \<le> a \<bullet> i"
immler@56189
   861
  shows "x \<in> s"
immler@56189
   862
  by (rule assms(1)[simplified is_interval_def, rule_format, OF assms(2,3,4)])
immler@56189
   863
immler@56189
   864
lemma interval_subst:
immler@56189
   865
  fixes S::"'a::euclidean_space set"
immler@56189
   866
  assumes "is_interval S"
wenzelm@64539
   867
    and "x \<in> S" "y j \<in> S"
wenzelm@64539
   868
    and "j \<in> Basis"
immler@56189
   869
  shows "(\<Sum>i\<in>Basis. (if i = j then y i \<bullet> i else x \<bullet> i) *\<^sub>R i) \<in> S"
immler@56189
   870
  by (rule mem_is_intervalI[OF assms(1,2)]) (auto simp: assms)
immler@56189
   871
immler@56189
   872
lemma mem_box_componentwiseI:
immler@56189
   873
  fixes S::"'a::euclidean_space set"
immler@56189
   874
  assumes "is_interval S"
immler@56189
   875
  assumes "\<And>i. i \<in> Basis \<Longrightarrow> x \<bullet> i \<in> ((\<lambda>x. x \<bullet> i) ` S)"
immler@56189
   876
  shows "x \<in> S"
immler@56189
   877
proof -
immler@56189
   878
  from assms have "\<forall>i \<in> Basis. \<exists>s \<in> S. x \<bullet> i = s \<bullet> i"
immler@56189
   879
    by auto
wenzelm@64539
   880
  with finite_Basis obtain s and bs::"'a list"
wenzelm@64539
   881
    where s: "\<And>i. i \<in> Basis \<Longrightarrow> x \<bullet> i = s i \<bullet> i" "\<And>i. i \<in> Basis \<Longrightarrow> s i \<in> S"
wenzelm@64539
   882
      and bs: "set bs = Basis" "distinct bs"
immler@56189
   883
    by (metis finite_distinct_list)
wenzelm@64539
   884
  from nonempty_Basis s obtain j where j: "j \<in> Basis" "s j \<in> S"
wenzelm@64539
   885
    by blast
wenzelm@63040
   886
  define y where
wenzelm@63040
   887
    "y = rec_list (s j) (\<lambda>j _ Y. (\<Sum>i\<in>Basis. (if i = j then s i \<bullet> i else Y \<bullet> i) *\<^sub>R i))"
immler@56189
   888
  have "x = (\<Sum>i\<in>Basis. (if i \<in> set bs then s i \<bullet> i else s j \<bullet> i) *\<^sub>R i)"
lp15@66643
   889
    using bs by (auto simp: s(1)[symmetric] euclidean_representation)
immler@56189
   890
  also have [symmetric]: "y bs = \<dots>"
immler@56189
   891
    using bs(2) bs(1)[THEN equalityD1]
immler@56189
   892
    by (induct bs) (auto simp: y_def euclidean_representation intro!: euclidean_eqI[where 'a='a])
immler@56189
   893
  also have "y bs \<in> S"
immler@56189
   894
    using bs(1)[THEN equalityD1]
immler@56189
   895
    apply (induct bs)
wenzelm@64539
   896
     apply (auto simp: y_def j)
immler@56189
   897
    apply (rule interval_subst[OF assms(1)])
wenzelm@64539
   898
      apply (auto simp: s)
immler@56189
   899
    done
immler@56189
   900
  finally show ?thesis .
immler@56189
   901
qed
immler@56189
   902
lp15@63007
   903
lemma cbox01_nonempty [simp]: "cbox 0 One \<noteq> {}"
nipkow@64267
   904
  by (simp add: box_ne_empty inner_Basis inner_sum_left sum_nonneg)
lp15@63007
   905
lp15@63007
   906
lemma box01_nonempty [simp]: "box 0 One \<noteq> {}"
lp15@66089
   907
  by (simp add: box_ne_empty inner_Basis inner_sum_left)
lp15@63075
   908
lp15@64773
   909
lemma empty_as_interval: "{} = cbox One (0::'a::euclidean_space)"
lp15@64773
   910
  using nonempty_Basis box01_nonempty box_eq_empty(1) box_ne_empty(1) by blast
lp15@64773
   911
lp15@66089
   912
lemma interval_subset_is_interval:
lp15@66089
   913
  assumes "is_interval S"
lp15@66089
   914
  shows "cbox a b \<subseteq> S \<longleftrightarrow> cbox a b = {} \<or> a \<in> S \<and> b \<in> S" (is "?lhs = ?rhs")
lp15@66089
   915
proof
lp15@66089
   916
  assume ?lhs
lp15@66089
   917
  then show ?rhs  using box_ne_empty(1) mem_box(2) by fastforce
lp15@66089
   918
next
lp15@66089
   919
  assume ?rhs
lp15@66089
   920
  have "cbox a b \<subseteq> S" if "a \<in> S" "b \<in> S"
lp15@66089
   921
    using assms unfolding is_interval_def
lp15@66089
   922
    apply (clarsimp simp add: mem_box)
lp15@66089
   923
    using that by blast
lp15@66089
   924
  with \<open>?rhs\<close> show ?lhs
lp15@66089
   925
    by blast
lp15@66089
   926
qed
lp15@66089
   927
immler@67685
   928
lemma is_real_interval_union:
immler@67685
   929
  "is_interval (X \<union> Y)"
immler@67685
   930
  if X: "is_interval X" and Y: "is_interval Y" and I: "(X \<noteq> {} \<Longrightarrow> Y \<noteq> {} \<Longrightarrow> X \<inter> Y \<noteq> {})"
immler@67685
   931
  for X Y::"real set"
immler@67685
   932
proof -
immler@67685
   933
  consider "X \<noteq> {}" "Y \<noteq> {}" | "X = {}" | "Y = {}" by blast
immler@67685
   934
  then show ?thesis
immler@67685
   935
  proof cases
immler@67685
   936
    case 1
immler@67685
   937
    then obtain r where "r \<in> X \<or> X \<inter> Y = {}" "r \<in> Y \<or> X \<inter> Y = {}"
immler@67685
   938
      by blast
immler@67685
   939
    then show ?thesis
immler@67685
   940
      using I 1 X Y unfolding is_interval_1
immler@67685
   941
      by (metis (full_types) Un_iff le_cases)
immler@67685
   942
  qed (use that in auto)
immler@67685
   943
qed
immler@67685
   944
immler@67685
   945
lemma is_interval_translationI:
immler@67685
   946
  assumes "is_interval X"
immler@67685
   947
  shows "is_interval ((+) x ` X)"
immler@67685
   948
  unfolding is_interval_def
immler@67685
   949
proof safe
immler@67685
   950
  fix b d e
immler@67685
   951
  assume "b \<in> X" "d \<in> X"
immler@67685
   952
    "\<forall>i\<in>Basis. (x + b) \<bullet> i \<le> e \<bullet> i \<and> e \<bullet> i \<le> (x + d) \<bullet> i \<or>
immler@67685
   953
       (x + d) \<bullet> i \<le> e \<bullet> i \<and> e \<bullet> i \<le> (x + b) \<bullet> i"
immler@67685
   954
  hence "e - x \<in> X"
immler@67685
   955
    by (intro mem_is_intervalI[OF assms \<open>b \<in> X\<close> \<open>d \<in> X\<close>, of "e - x"])
immler@67685
   956
      (auto simp: algebra_simps)
immler@67685
   957
  thus "e \<in> (+) x ` X" by force
immler@67685
   958
qed
immler@67685
   959
immler@67685
   960
lemma is_interval_uminusI:
immler@67685
   961
  assumes "is_interval X"
immler@67685
   962
  shows "is_interval (uminus ` X)"
immler@67685
   963
  unfolding is_interval_def
immler@67685
   964
proof safe
immler@67685
   965
  fix b d e
immler@67685
   966
  assume "b \<in> X" "d \<in> X"
immler@67685
   967
    "\<forall>i\<in>Basis. (- b) \<bullet> i \<le> e \<bullet> i \<and> e \<bullet> i \<le> (- d) \<bullet> i \<or>
immler@67685
   968
       (- d) \<bullet> i \<le> e \<bullet> i \<and> e \<bullet> i \<le> (- b) \<bullet> i"
immler@67685
   969
  hence "- e \<in> X"
immler@67685
   970
    by (intro mem_is_intervalI[OF assms \<open>b \<in> X\<close> \<open>d \<in> X\<close>, of "- e"])
immler@67685
   971
      (auto simp: algebra_simps)
immler@67685
   972
  thus "e \<in> uminus ` X" by force
immler@67685
   973
qed
immler@67685
   974
immler@67685
   975
lemma is_interval_uminus[simp]: "is_interval (uminus ` x) = is_interval x"
immler@67685
   976
  using is_interval_uminusI[of x] is_interval_uminusI[of "uminus ` x"]
immler@67685
   977
  by (auto simp: image_image)
immler@67685
   978
immler@67685
   979
lemma is_interval_neg_translationI:
immler@67685
   980
  assumes "is_interval X"
immler@67685
   981
  shows "is_interval ((-) x ` X)"
immler@67685
   982
proof -
immler@67685
   983
  have "(-) x ` X = (+) x ` uminus ` X"
immler@67685
   984
    by (force simp: algebra_simps)
immler@67685
   985
  also have "is_interval \<dots>"
immler@67685
   986
    by (metis is_interval_uminusI is_interval_translationI assms)
immler@67685
   987
  finally show ?thesis .
immler@67685
   988
qed
immler@67685
   989
immler@67685
   990
lemma is_interval_translation[simp]:
immler@67685
   991
  "is_interval ((+) x ` X) = is_interval X"
immler@67685
   992
  using is_interval_neg_translationI[of "(+) x ` X" x]
immler@67685
   993
  by (auto intro!: is_interval_translationI simp: image_image)
immler@67685
   994
immler@67685
   995
lemma is_interval_minus_translation[simp]:
immler@67685
   996
  shows "is_interval ((-) x ` X) = is_interval X"
immler@67685
   997
proof -
immler@67685
   998
  have "(-) x ` X = (+) x ` uminus ` X"
immler@67685
   999
    by (force simp: algebra_simps)
immler@67685
  1000
  also have "is_interval \<dots> = is_interval X"
immler@67685
  1001
    by simp
immler@67685
  1002
  finally show ?thesis .
immler@67685
  1003
qed
immler@67685
  1004
immler@67685
  1005
lemma is_interval_minus_translation'[simp]:
immler@67685
  1006
  shows "is_interval ((\<lambda>x. x - c) ` X) = is_interval X"
immler@67685
  1007
  using is_interval_translation[of "-c" X]
immler@67685
  1008
  by (metis image_cong uminus_add_conv_diff)
immler@67685
  1009
immler@69611
  1010
immler@69611
  1011
subsection%unimportant \<open>Bounded Projections\<close>
immler@62127
  1012
immler@69611
  1013
lemma bounded_inner_imp_bdd_above:
immler@69611
  1014
  assumes "bounded s"
immler@69611
  1015
    shows "bdd_above ((\<lambda>x. x \<bullet> a) ` s)"
immler@69611
  1016
by (simp add: assms bounded_imp_bdd_above bounded_linear_image bounded_linear_inner_left)
himmelma@33175
  1017
immler@69611
  1018
lemma bounded_inner_imp_bdd_below:
immler@69611
  1019
  assumes "bounded s"
immler@69611
  1020
    shows "bdd_below ((\<lambda>x. x \<bullet> a) ` s)"
immler@69611
  1021
by (simp add: assms bounded_imp_bdd_below bounded_linear_image bounded_linear_inner_left)
huffman@44632
  1022
wenzelm@53282
  1023
immler@69611
  1024
subsection%unimportant \<open>Structural rules for pointwise continuity\<close>
himmelma@33175
  1025
hoelzl@51361
  1026
lemma continuous_infnorm[continuous_intros]:
wenzelm@53282
  1027
  "continuous F f \<Longrightarrow> continuous F (\<lambda>x. infnorm (f x))"
huffman@44647
  1028
  unfolding continuous_def by (rule tendsto_infnorm)
himmelma@33175
  1029
hoelzl@51361
  1030
lemma continuous_inner[continuous_intros]:
wenzelm@53282
  1031
  assumes "continuous F f"
wenzelm@53282
  1032
    and "continuous F g"
huffman@44647
  1033
  shows "continuous F (\<lambda>x. inner (f x) (g x))"
huffman@44647
  1034
  using assms unfolding continuous_def by (rule tendsto_inner)
huffman@44647
  1035
immler@69516
  1036
immler@69611
  1037
subsection%unimportant \<open>Structural rules for setwise continuity\<close>
himmelma@33175
  1038
hoelzl@56371
  1039
lemma continuous_on_infnorm[continuous_intros]:
wenzelm@53282
  1040
  "continuous_on s f \<Longrightarrow> continuous_on s (\<lambda>x. infnorm (f x))"
huffman@44647
  1041
  unfolding continuous_on by (fast intro: tendsto_infnorm)
huffman@44647
  1042
hoelzl@56371
  1043
lemma continuous_on_inner[continuous_intros]:
huffman@44531
  1044
  fixes g :: "'a::topological_space \<Rightarrow> 'b::real_inner"
wenzelm@53282
  1045
  assumes "continuous_on s f"
wenzelm@53282
  1046
    and "continuous_on s g"
huffman@44531
  1047
  shows "continuous_on s (\<lambda>x. inner (f x) (g x))"
huffman@44531
  1048
  using bounded_bilinear_inner assms
huffman@44531
  1049
  by (rule bounded_bilinear.continuous_on)
huffman@44531
  1050
immler@69613
  1051
immler@69613
  1052
subsection%unimportant \<open>Openness of halfspaces.\<close>
himmelma@33175
  1053
himmelma@33175
  1054
lemma open_halfspace_lt: "open {x. inner a x < b}"
hoelzl@63332
  1055
  by (simp add: open_Collect_less continuous_on_inner continuous_on_const continuous_on_id)
himmelma@33175
  1056
himmelma@33175
  1057
lemma open_halfspace_gt: "open {x. inner a x > b}"
hoelzl@63332
  1058
  by (simp add: open_Collect_less continuous_on_inner continuous_on_const continuous_on_id)
himmelma@33175
  1059
wenzelm@53282
  1060
lemma open_halfspace_component_lt: "open {x::'a::euclidean_space. x\<bullet>i < a}"
hoelzl@63332
  1061
  by (simp add: open_Collect_less continuous_on_inner continuous_on_const continuous_on_id)
himmelma@33175
  1062
wenzelm@53282
  1063
lemma open_halfspace_component_gt: "open {x::'a::euclidean_space. x\<bullet>i > a}"
hoelzl@63332
  1064
  by (simp add: open_Collect_less continuous_on_inner continuous_on_const continuous_on_id)
himmelma@33175
  1065
immler@69611
  1066
lemma eucl_less_eq_halfspaces:
immler@69611
  1067
  fixes a :: "'a::euclidean_space"
immler@69611
  1068
  shows "{x. x <e a} = (\<Inter>i\<in>Basis. {x. x \<bullet> i < a \<bullet> i})"
immler@69611
  1069
        "{x. a <e x} = (\<Inter>i\<in>Basis. {x. a \<bullet> i < x \<bullet> i})"
immler@69611
  1070
  by (auto simp: eucl_less_def)
immler@69611
  1071
immler@69611
  1072
lemma open_Collect_eucl_less[simp, intro]:
immler@69611
  1073
  fixes a :: "'a::euclidean_space"
immler@69611
  1074
  shows "open {x. x <e a}" "open {x. a <e x}"
immler@69611
  1075
  by (auto simp: eucl_less_eq_halfspaces open_halfspace_component_lt open_halfspace_component_gt)
immler@69611
  1076
immler@69613
  1077
subsection%unimportant \<open>Closure of halfspaces and hyperplanes\<close>
immler@69613
  1078
immler@69613
  1079
lemma continuous_at_inner: "continuous (at x) (inner a)"
immler@69613
  1080
  unfolding continuous_at by (intro tendsto_intros)
immler@69613
  1081
immler@69613
  1082
lemma closed_halfspace_le: "closed {x. inner a x \<le> b}"
immler@69613
  1083
  by (simp add: closed_Collect_le continuous_on_inner continuous_on_const continuous_on_id)
immler@69613
  1084
immler@69613
  1085
lemma closed_halfspace_ge: "closed {x. inner a x \<ge> b}"
immler@69613
  1086
  by (simp add: closed_Collect_le continuous_on_inner continuous_on_const continuous_on_id)
immler@69613
  1087
immler@69613
  1088
lemma closed_hyperplane: "closed {x. inner a x = b}"
immler@69613
  1089
  by (simp add: closed_Collect_eq continuous_on_inner continuous_on_const continuous_on_id)
immler@69613
  1090
immler@69613
  1091
lemma closed_halfspace_component_le: "closed {x::'a::euclidean_space. x\<bullet>i \<le> a}"
immler@69613
  1092
  by (simp add: closed_Collect_le continuous_on_inner continuous_on_const continuous_on_id)
immler@69613
  1093
immler@69613
  1094
lemma closed_halfspace_component_ge: "closed {x::'a::euclidean_space. x\<bullet>i \<ge> a}"
immler@69613
  1095
  by (simp add: closed_Collect_le continuous_on_inner continuous_on_const continuous_on_id)
immler@69613
  1096
immler@69613
  1097
lemma closed_interval_left:
immler@69613
  1098
  fixes b :: "'a::euclidean_space"
immler@69613
  1099
  shows "closed {x::'a. \<forall>i\<in>Basis. x\<bullet>i \<le> b\<bullet>i}"
immler@69613
  1100
  by (simp add: Collect_ball_eq closed_INT closed_Collect_le continuous_on_inner continuous_on_const continuous_on_id)
immler@69613
  1101
immler@69613
  1102
lemma closed_interval_right:
immler@69613
  1103
  fixes a :: "'a::euclidean_space"
immler@69613
  1104
  shows "closed {x::'a. \<forall>i\<in>Basis. a\<bullet>i \<le> x\<bullet>i}"
immler@69613
  1105
  by (simp add: Collect_ball_eq closed_INT closed_Collect_le continuous_on_inner continuous_on_const continuous_on_id)
immler@69613
  1106
immler@69613
  1107
lemma continuous_le_on_closure:
immler@69613
  1108
  fixes a::real
immler@69613
  1109
  assumes f: "continuous_on (closure s) f"
immler@69613
  1110
      and x: "x \<in> closure(s)"
immler@69613
  1111
      and xlo: "\<And>x. x \<in> s ==> f(x) \<le> a"
immler@69613
  1112
    shows "f(x) \<le> a"
immler@69613
  1113
    using image_closure_subset [OF f]
immler@69613
  1114
  using image_closure_subset [OF f] closed_halfspace_le [of "1::real" a] assms
immler@69613
  1115
  by force
immler@69613
  1116
immler@69613
  1117
lemma continuous_ge_on_closure:
immler@69613
  1118
  fixes a::real
immler@69613
  1119
  assumes f: "continuous_on (closure s) f"
immler@69613
  1120
      and x: "x \<in> closure(s)"
immler@69613
  1121
      and xlo: "\<And>x. x \<in> s ==> f(x) \<ge> a"
immler@69613
  1122
    shows "f(x) \<ge> a"
immler@69613
  1123
  using image_closure_subset [OF f] closed_halfspace_ge [of a "1::real"] assms
immler@69613
  1124
  by force
immler@69613
  1125
immler@69613
  1126
immler@69613
  1127
subsection%unimportant\<open>Some more convenient intermediate-value theorem formulations\<close>
immler@69613
  1128
immler@69613
  1129
lemma connected_ivt_hyperplane:
immler@69613
  1130
  assumes "connected S" and xy: "x \<in> S" "y \<in> S" and b: "inner a x \<le> b" "b \<le> inner a y"
immler@69613
  1131
  shows "\<exists>z \<in> S. inner a z = b"
immler@69613
  1132
proof (rule ccontr)
immler@69613
  1133
  assume as:"\<not> (\<exists>z\<in>S. inner a z = b)"
immler@69613
  1134
  let ?A = "{x. inner a x < b}"
immler@69613
  1135
  let ?B = "{x. inner a x > b}"
immler@69613
  1136
  have "open ?A" "open ?B"
immler@69613
  1137
    using open_halfspace_lt and open_halfspace_gt by auto
immler@69613
  1138
  moreover have "?A \<inter> ?B = {}" by auto
immler@69613
  1139
  moreover have "S \<subseteq> ?A \<union> ?B" using as by auto
immler@69613
  1140
  ultimately show False
immler@69613
  1141
    using \<open>connected S\<close>[unfolded connected_def not_ex,
immler@69613
  1142
      THEN spec[where x="?A"], THEN spec[where x="?B"]]
immler@69613
  1143
    using xy b by auto
immler@69613
  1144
qed
immler@69613
  1145
immler@69613
  1146
lemma connected_ivt_component:
immler@69613
  1147
  fixes x::"'a::euclidean_space"
immler@69613
  1148
  shows "connected S \<Longrightarrow> x \<in> S \<Longrightarrow> y \<in> S \<Longrightarrow> x\<bullet>k \<le> a \<Longrightarrow> a \<le> y\<bullet>k \<Longrightarrow> (\<exists>z\<in>S.  z\<bullet>k = a)"
immler@69613
  1149
  using connected_ivt_hyperplane[of S x y "k::'a" a]
immler@69613
  1150
  by (auto simp: inner_commute)
immler@69613
  1151
immler@69611
  1152
immler@69611
  1153
subsection \<open>Limit Component Bounds\<close>
himmelma@33175
  1154
immler@69613
  1155
lemma Lim_component_le:
immler@69613
  1156
  fixes f :: "'a \<Rightarrow> 'b::euclidean_space"
immler@69613
  1157
  assumes "(f \<longlongrightarrow> l) net"
immler@69613
  1158
    and "\<not> (trivial_limit net)"
immler@69613
  1159
    and "eventually (\<lambda>x. f(x)\<bullet>i \<le> b) net"
immler@69613
  1160
  shows "l\<bullet>i \<le> b"
immler@69613
  1161
  by (rule tendsto_le[OF assms(2) tendsto_const tendsto_inner[OF assms(1) tendsto_const] assms(3)])
immler@69613
  1162
immler@69613
  1163
lemma Lim_component_ge:
immler@69613
  1164
  fixes f :: "'a \<Rightarrow> 'b::euclidean_space"
immler@69613
  1165
  assumes "(f \<longlongrightarrow> l) net"
immler@69613
  1166
    and "\<not> (trivial_limit net)"
immler@69613
  1167
    and "eventually (\<lambda>x. b \<le> (f x)\<bullet>i) net"
immler@69613
  1168
  shows "b \<le> l\<bullet>i"
immler@69613
  1169
  by (rule tendsto_le[OF assms(2) tendsto_inner[OF assms(1) tendsto_const] tendsto_const assms(3)])
immler@69613
  1170
immler@69613
  1171
lemma Lim_component_eq:
immler@69613
  1172
  fixes f :: "'a \<Rightarrow> 'b::euclidean_space"
immler@69613
  1173
  assumes net: "(f \<longlongrightarrow> l) net" "\<not> trivial_limit net"
immler@69613
  1174
    and ev:"eventually (\<lambda>x. f(x)\<bullet>i = b) net"
immler@69613
  1175
  shows "l\<bullet>i = b"
immler@69613
  1176
  using ev[unfolded order_eq_iff eventually_conj_iff]
immler@69613
  1177
  using Lim_component_ge[OF net, of b i]
immler@69613
  1178
  using Lim_component_le[OF net, of i b]
immler@69613
  1179
  by auto
immler@69613
  1180
immler@56189
  1181
lemma open_box[intro]: "open (box a b)"
immler@56189
  1182
proof -
nipkow@67399
  1183
  have "open (\<Inter>i\<in>Basis. ((\<bullet>) i) -` {a \<bullet> i <..< b \<bullet> i})"
lp15@62533
  1184
    by (auto intro!: continuous_open_vimage continuous_inner continuous_ident continuous_const)
nipkow@67399
  1185
  also have "(\<Inter>i\<in>Basis. ((\<bullet>) i) -` {a \<bullet> i <..< b \<bullet> i}) = box a b"
lp15@66643
  1186
    by (auto simp: box_def inner_commute)
immler@56189
  1187
  finally show ?thesis .
immler@56189
  1188
qed
immler@56189
  1189
immler@56189
  1190
lemma closed_cbox[intro]:
immler@56189
  1191
  fixes a b :: "'a::euclidean_space"
immler@56189
  1192
  shows "closed (cbox a b)"
immler@56189
  1193
proof -
immler@56189
  1194
  have "closed (\<Inter>i\<in>Basis. (\<lambda>x. x\<bullet>i) -` {a\<bullet>i .. b\<bullet>i})"
immler@56189
  1195
    by (intro closed_INT ballI continuous_closed_vimage allI
immler@56189
  1196
      linear_continuous_at closed_real_atLeastAtMost finite_Basis bounded_linear_inner_left)
immler@56189
  1197
  also have "(\<Inter>i\<in>Basis. (\<lambda>x. x\<bullet>i) -` {a\<bullet>i .. b\<bullet>i}) = cbox a b"
lp15@66643
  1198
    by (auto simp: cbox_def)
immler@56189
  1199
  finally show "closed (cbox a b)" .
immler@56189
  1200
qed
immler@56189
  1201
lp15@62618
  1202
lemma interior_cbox [simp]:
immler@56189
  1203
  fixes a b :: "'a::euclidean_space"
immler@56189
  1204
  shows "interior (cbox a b) = box a b" (is "?L = ?R")
immler@56189
  1205
proof(rule subset_antisym)
immler@56189
  1206
  show "?R \<subseteq> ?L"
immler@56189
  1207
    using box_subset_cbox open_box
immler@56189
  1208
    by (rule interior_maximal)
immler@56189
  1209
  {
immler@56189
  1210
    fix x
immler@56189
  1211
    assume "x \<in> interior (cbox a b)"
immler@56189
  1212
    then obtain s where s: "open s" "x \<in> s" "s \<subseteq> cbox a b" ..
immler@56189
  1213
    then obtain e where "e>0" and e:"\<forall>x'. dist x' x < e \<longrightarrow> x' \<in> cbox a b"
immler@56189
  1214
      unfolding open_dist and subset_eq by auto
immler@56189
  1215
    {
immler@56189
  1216
      fix i :: 'a
immler@56189
  1217
      assume i: "i \<in> Basis"
immler@56189
  1218
      have "dist (x - (e / 2) *\<^sub>R i) x < e"
immler@56189
  1219
        and "dist (x + (e / 2) *\<^sub>R i) x < e"
immler@56189
  1220
        unfolding dist_norm
immler@56189
  1221
        apply auto
immler@56189
  1222
        unfolding norm_minus_cancel
wenzelm@60420
  1223
        using norm_Basis[OF i] \<open>e>0\<close>
immler@56189
  1224
        apply auto
immler@56189
  1225
        done
immler@56189
  1226
      then have "a \<bullet> i \<le> (x - (e / 2) *\<^sub>R i) \<bullet> i" and "(x + (e / 2) *\<^sub>R i) \<bullet> i \<le> b \<bullet> i"
immler@56189
  1227
        using e[THEN spec[where x="x - (e/2) *\<^sub>R i"]]
immler@56189
  1228
          and e[THEN spec[where x="x + (e/2) *\<^sub>R i"]]
immler@56189
  1229
        unfolding mem_box
immler@56189
  1230
        using i
immler@56189
  1231
        by blast+
immler@56189
  1232
      then have "a \<bullet> i < x \<bullet> i" and "x \<bullet> i < b \<bullet> i"
wenzelm@60420
  1233
        using \<open>e>0\<close> i
immler@56189
  1234
        by (auto simp: inner_diff_left inner_Basis inner_add_left)
immler@56189
  1235
    }
immler@56189
  1236
    then have "x \<in> box a b"
immler@56189
  1237
      unfolding mem_box by auto
immler@56189
  1238
  }
immler@56189
  1239
  then show "?L \<subseteq> ?R" ..
immler@56189
  1240
qed
immler@56189
  1241
lp15@63928
  1242
lemma bounded_cbox [simp]:
immler@56189
  1243
  fixes a :: "'a::euclidean_space"
immler@56189
  1244
  shows "bounded (cbox a b)"
immler@56189
  1245
proof -
immler@56189
  1246
  let ?b = "\<Sum>i\<in>Basis. \<bar>a\<bullet>i\<bar> + \<bar>b\<bullet>i\<bar>"
immler@56189
  1247
  {
immler@56189
  1248
    fix x :: "'a"
lp15@68120
  1249
    assume "\<And>i. i\<in>Basis \<Longrightarrow> a \<bullet> i \<le> x \<bullet> i \<and> x \<bullet> i \<le> b \<bullet> i"
immler@56189
  1250
    then have "(\<Sum>i\<in>Basis. \<bar>x \<bullet> i\<bar>) \<le> ?b"
lp15@68120
  1251
      by (force simp: intro!: sum_mono)
immler@56189
  1252
    then have "norm x \<le> ?b"
immler@56189
  1253
      using norm_le_l1[of x] by auto
immler@56189
  1254
  }
immler@56189
  1255
  then show ?thesis
lp15@68120
  1256
    unfolding cbox_def bounded_iff by force
immler@56189
  1257
qed
immler@56189
  1258
lp15@62618
  1259
lemma bounded_box [simp]:
immler@56189
  1260
  fixes a :: "'a::euclidean_space"
immler@56189
  1261
  shows "bounded (box a b)"
lp15@68120
  1262
  using bounded_cbox[of a b] box_subset_cbox[of a b] bounded_subset[of "cbox a b" "box a b"]
immler@56189
  1263
  by simp
immler@56189
  1264
lp15@62618
  1265
lemma not_interval_UNIV [simp]:
immler@56189
  1266
  fixes a :: "'a::euclidean_space"
immler@56189
  1267
  shows "cbox a b \<noteq> UNIV" "box a b \<noteq> UNIV"
lp15@62618
  1268
  using bounded_box[of a b] bounded_cbox[of a b] by force+
lp15@62618
  1269
lp15@63945
  1270
lemma not_interval_UNIV2 [simp]:
lp15@63945
  1271
  fixes a :: "'a::euclidean_space"
lp15@63945
  1272
  shows "UNIV \<noteq> cbox a b" "UNIV \<noteq> box a b"
lp15@63945
  1273
  using bounded_box[of a b] bounded_cbox[of a b] by force+
lp15@63945
  1274
immler@56189
  1275
lemma box_midpoint:
immler@56189
  1276
  fixes a :: "'a::euclidean_space"
immler@56189
  1277
  assumes "box a b \<noteq> {}"
immler@56189
  1278
  shows "((1/2) *\<^sub>R (a + b)) \<in> box a b"
immler@56189
  1279
proof -
lp15@68120
  1280
  have "a \<bullet> i < ((1 / 2) *\<^sub>R (a + b)) \<bullet> i \<and> ((1 / 2) *\<^sub>R (a + b)) \<bullet> i < b \<bullet> i" if "i \<in> Basis" for i
lp15@68120
  1281
    using assms that by (auto simp: inner_add_left box_ne_empty)
immler@56189
  1282
  then show ?thesis unfolding mem_box by auto
immler@56189
  1283
qed
immler@56189
  1284
immler@56189
  1285
lemma open_cbox_convex:
immler@56189
  1286
  fixes x :: "'a::euclidean_space"
immler@56189
  1287
  assumes x: "x \<in> box a b"
immler@56189
  1288
    and y: "y \<in> cbox a b"
immler@56189
  1289
    and e: "0 < e" "e \<le> 1"
immler@56189
  1290
  shows "(e *\<^sub>R x + (1 - e) *\<^sub>R y) \<in> box a b"
immler@56189
  1291
proof -
immler@56189
  1292
  {
immler@56189
  1293
    fix i :: 'a
immler@56189
  1294
    assume i: "i \<in> Basis"
immler@56189
  1295
    have "a \<bullet> i = e * (a \<bullet> i) + (1 - e) * (a \<bullet> i)"
immler@56189
  1296
      unfolding left_diff_distrib by simp
immler@56189
  1297
    also have "\<dots> < e * (x \<bullet> i) + (1 - e) * (y \<bullet> i)"
lp15@68120
  1298
    proof (rule add_less_le_mono)
lp15@68120
  1299
      show "e * (a \<bullet> i) < e * (x \<bullet> i)"
lp15@68120
  1300
        using \<open>0 < e\<close> i mem_box(1) x by auto
lp15@68120
  1301
      show "(1 - e) * (a \<bullet> i) \<le> (1 - e) * (y \<bullet> i)"
lp15@68120
  1302
        by (meson diff_ge_0_iff_ge \<open>e \<le> 1\<close> i mem_box(2) mult_left_mono y)
lp15@68120
  1303
    qed
immler@56189
  1304
    finally have "a \<bullet> i < (e *\<^sub>R x + (1 - e) *\<^sub>R y) \<bullet> i"
immler@56189
  1305
      unfolding inner_simps by auto
immler@56189
  1306
    moreover
immler@56189
  1307
    {
immler@56189
  1308
      have "b \<bullet> i = e * (b\<bullet>i) + (1 - e) * (b\<bullet>i)"
immler@56189
  1309
        unfolding left_diff_distrib by simp
immler@56189
  1310
      also have "\<dots> > e * (x \<bullet> i) + (1 - e) * (y \<bullet> i)"
lp15@66827
  1311
      proof (rule add_less_le_mono)
lp15@66827
  1312
        show "e * (x \<bullet> i) < e * (b \<bullet> i)"
lp15@68120
  1313
          using \<open>0 < e\<close> i mem_box(1) x by auto
lp15@66827
  1314
        show "(1 - e) * (y \<bullet> i) \<le> (1 - e) * (b \<bullet> i)"
lp15@68120
  1315
          by (meson diff_ge_0_iff_ge \<open>e \<le> 1\<close> i mem_box(2) mult_left_mono y)
lp15@66827
  1316
      qed
immler@56189
  1317
      finally have "(e *\<^sub>R x + (1 - e) *\<^sub>R y) \<bullet> i < b \<bullet> i"
immler@56189
  1318
        unfolding inner_simps by auto
immler@56189
  1319
    }
immler@56189
  1320
    ultimately have "a \<bullet> i < (e *\<^sub>R x + (1 - e) *\<^sub>R y) \<bullet> i \<and> (e *\<^sub>R x + (1 - e) *\<^sub>R y) \<bullet> i < b \<bullet> i"
immler@56189
  1321
      by auto
immler@56189
  1322
  }
immler@56189
  1323
  then show ?thesis
immler@56189
  1324
    unfolding mem_box by auto
immler@56189
  1325
qed
immler@56189
  1326
lp15@63881
  1327
lemma closure_cbox [simp]: "closure (cbox a b) = cbox a b"
lp15@63881
  1328
  by (simp add: closed_cbox)
lp15@63881
  1329
lp15@63881
  1330
lemma closure_box [simp]:
immler@56189
  1331
  fixes a :: "'a::euclidean_space"
immler@56189
  1332
   assumes "box a b \<noteq> {}"
immler@56189
  1333
  shows "closure (box a b) = cbox a b"
immler@56189
  1334
proof -
immler@56189
  1335
  have ab: "a <e b"
immler@56189
  1336
    using assms by (simp add: eucl_less_def box_ne_empty)
immler@56189
  1337
  let ?c = "(1 / 2) *\<^sub>R (a + b)"
immler@56189
  1338
  {
immler@56189
  1339
    fix x
immler@56189
  1340
    assume as:"x \<in> cbox a b"
wenzelm@63040
  1341
    define f where [abs_def]: "f n = x + (inverse (real n + 1)) *\<^sub>R (?c - x)" for n
immler@56189
  1342
    {
immler@56189
  1343
      fix n
immler@56189
  1344
      assume fn: "f n <e b \<longrightarrow> a <e f n \<longrightarrow> f n = x" and xc: "x \<noteq> ?c"
immler@56189
  1345
      have *: "0 < inverse (real n + 1)" "inverse (real n + 1) \<le> 1"
immler@56189
  1346
        unfolding inverse_le_1_iff by auto
immler@56189
  1347
      have "(inverse (real n + 1)) *\<^sub>R ((1 / 2) *\<^sub>R (a + b)) + (1 - inverse (real n + 1)) *\<^sub>R x =
immler@56189
  1348
        x + (inverse (real n + 1)) *\<^sub>R (((1 / 2) *\<^sub>R (a + b)) - x)"
lp15@66643
  1349
        by (auto simp: algebra_simps)
immler@56189
  1350
      then have "f n <e b" and "a <e f n"
immler@56189
  1351
        using open_cbox_convex[OF box_midpoint[OF assms] as *]
immler@56189
  1352
        unfolding f_def by (auto simp: box_def eucl_less_def)
immler@56189
  1353
      then have False
immler@56189
  1354
        using fn unfolding f_def using xc by auto
immler@56189
  1355
    }
immler@56189
  1356
    moreover
immler@56189
  1357
    {
wenzelm@61973
  1358
      assume "\<not> (f \<longlongrightarrow> x) sequentially"
immler@56189
  1359
      {
immler@56189
  1360
        fix e :: real
immler@56189
  1361
        assume "e > 0"
lp15@61609
  1362
        then obtain N :: nat where N: "inverse (real (N + 1)) < e"
lp15@68120
  1363
          using reals_Archimedean by auto
lp15@61609
  1364
        have "inverse (real n + 1) < e" if "N \<le> n" for n
lp15@61609
  1365
          by (auto intro!: that le_less_trans [OF _ N])
immler@56189
  1366
        then have "\<exists>N::nat. \<forall>n\<ge>N. inverse (real n + 1) < e" by auto
immler@56189
  1367
      }
wenzelm@61973
  1368
      then have "((\<lambda>n. inverse (real n + 1)) \<longlongrightarrow> 0) sequentially"
lp15@66643
  1369
        unfolding lim_sequentially by(auto simp: dist_norm)
wenzelm@61973
  1370
      then have "(f \<longlongrightarrow> x) sequentially"
immler@56189
  1371
        unfolding f_def
immler@56189
  1372
        using tendsto_add[OF tendsto_const, of "\<lambda>n::nat. (inverse (real n + 1)) *\<^sub>R ((1 / 2) *\<^sub>R (a + b) - x)" 0 sequentially x]
immler@56189
  1373
        using tendsto_scaleR [OF _ tendsto_const, of "\<lambda>n::nat. inverse (real n + 1)" 0 sequentially "((1 / 2) *\<^sub>R (a + b) - x)"]
immler@56189
  1374
        by auto
immler@56189
  1375
    }
immler@56189
  1376
    ultimately have "x \<in> closure (box a b)"
lp15@68120
  1377
      using as box_midpoint[OF assms]
lp15@68120
  1378
      unfolding closure_def islimpt_sequential
immler@56189
  1379
      by (cases "x=?c") (auto simp: in_box_eucl_less)
immler@56189
  1380
  }
immler@56189
  1381
  then show ?thesis
immler@56189
  1382
    using closure_minimal[OF box_subset_cbox, of a b] by blast
immler@56189
  1383
qed
immler@56189
  1384
immler@56189
  1385
lemma bounded_subset_box_symmetric:
lp15@68120
  1386
  fixes S :: "('a::euclidean_space) set"
lp15@68120
  1387
  assumes "bounded S"
lp15@68120
  1388
  obtains a where "S \<subseteq> box (-a) a"
immler@56189
  1389
proof -
lp15@68120
  1390
  obtain b where "b>0" and b: "\<forall>x\<in>S. norm x \<le> b"
immler@56189
  1391
    using assms[unfolded bounded_pos] by auto
wenzelm@63040
  1392
  define a :: 'a where "a = (\<Sum>i\<in>Basis. (b + 1) *\<^sub>R i)"
lp15@68120
  1393
  have "(-a)\<bullet>i < x\<bullet>i" and "x\<bullet>i < a\<bullet>i" if "x \<in> S" and i: "i \<in> Basis" for x i
lp15@68120
  1394
    using b Basis_le_norm[OF i, of x] that by (auto simp: a_def)
lp15@68120
  1395
  then have "S \<subseteq> box (-a) a"
lp15@68120
  1396
    by (auto simp: simp add: box_def)
lp15@68120
  1397
  then show ?thesis ..
immler@56189
  1398
qed
immler@56189
  1399
immler@56189
  1400
lemma bounded_subset_cbox_symmetric:
lp15@68120
  1401
  fixes S :: "('a::euclidean_space) set"
lp15@68120
  1402
  assumes "bounded S"
lp15@68120
  1403
  obtains a where "S \<subseteq> cbox (-a) a"
immler@56189
  1404
proof -
lp15@68120
  1405
  obtain a where "S \<subseteq> box (-a) a"
immler@56189
  1406
    using bounded_subset_box_symmetric[OF assms] by auto
immler@56189
  1407
  then show ?thesis
lp15@68120
  1408
    by (meson box_subset_cbox dual_order.trans that)
immler@56189
  1409
qed
immler@56189
  1410
immler@56189
  1411
lemma frontier_cbox:
immler@56189
  1412
  fixes a b :: "'a::euclidean_space"
immler@56189
  1413
  shows "frontier (cbox a b) = cbox a b - box a b"
immler@56189
  1414
  unfolding frontier_def unfolding interior_cbox and closure_closed[OF closed_cbox] ..
immler@56189
  1415
immler@56189
  1416
lemma frontier_box:
immler@56189
  1417
  fixes a b :: "'a::euclidean_space"
immler@56189
  1418
  shows "frontier (box a b) = (if box a b = {} then {} else cbox a b - box a b)"
immler@56189
  1419
proof (cases "box a b = {}")
immler@56189
  1420
  case True
immler@56189
  1421
  then show ?thesis
immler@56189
  1422
    using frontier_empty by auto
immler@56189
  1423
next
immler@56189
  1424
  case False
immler@56189
  1425
  then show ?thesis
immler@56189
  1426
    unfolding frontier_def and closure_box[OF False] and interior_open[OF open_box]
immler@56189
  1427
    by auto
immler@56189
  1428
qed
immler@56189
  1429
lp15@66884
  1430
lemma Int_interval_mixed_eq_empty:
immler@56189
  1431
  fixes a :: "'a::euclidean_space"
immler@56189
  1432
   assumes "box c d \<noteq> {}"
immler@56189
  1433
  shows "box a b \<inter> cbox c d = {} \<longleftrightarrow> box a b \<inter> box c d = {}"
immler@56189
  1434
  unfolding closure_box[OF assms, symmetric]
lp15@62843
  1435
  unfolding open_Int_closure_eq_empty[OF open_box] ..
immler@56189
  1436
immler@69611
  1437
subsection \<open>Class Instances\<close>
immler@69611
  1438
immler@69611
  1439
lemma compact_lemma:
immler@69611
  1440
  fixes f :: "nat \<Rightarrow> 'a::euclidean_space"
immler@69611
  1441
  assumes "bounded (range f)"
immler@69611
  1442
  shows "\<forall>d\<subseteq>Basis. \<exists>l::'a. \<exists> r.
immler@69611
  1443
    strict_mono r \<and> (\<forall>e>0. eventually (\<lambda>n. \<forall>i\<in>d. dist (f (r n) \<bullet> i) (l \<bullet> i) < e) sequentially)"
immler@69611
  1444
  by (rule compact_lemma_general[where unproj="\<lambda>e. \<Sum>i\<in>Basis. e i *\<^sub>R i"])
immler@69611
  1445
     (auto intro!: assms bounded_linear_inner_left bounded_linear_image
immler@69611
  1446
       simp: euclidean_representation)
immler@69611
  1447
immler@69611
  1448
instance%important euclidean_space \<subseteq> heine_borel
immler@69611
  1449
proof%unimportant
immler@69611
  1450
  fix f :: "nat \<Rightarrow> 'a"
immler@69611
  1451
  assume f: "bounded (range f)"
immler@69611
  1452
  then obtain l::'a and r where r: "strict_mono r"
immler@69611
  1453
    and l: "\<forall>e>0. eventually (\<lambda>n. \<forall>i\<in>Basis. dist (f (r n) \<bullet> i) (l \<bullet> i) < e) sequentially"
immler@69611
  1454
    using compact_lemma [OF f] by blast
immler@69611
  1455
  {
immler@69611
  1456
    fix e::real
immler@69611
  1457
    assume "e > 0"
immler@69611
  1458
    hence "e / real_of_nat DIM('a) > 0" by (simp add: DIM_positive)
immler@69611
  1459
    with l have "eventually (\<lambda>n. \<forall>i\<in>Basis. dist (f (r n) \<bullet> i) (l \<bullet> i) < e / (real_of_nat DIM('a))) sequentially"
immler@69611
  1460
      by simp
immler@69611
  1461
    moreover
immler@69611
  1462
    {
immler@69611
  1463
      fix n
immler@69611
  1464
      assume n: "\<forall>i\<in>Basis. dist (f (r n) \<bullet> i) (l \<bullet> i) < e / (real_of_nat DIM('a))"
immler@69611
  1465
      have "dist (f (r n)) l \<le> (\<Sum>i\<in>Basis. dist (f (r n) \<bullet> i) (l \<bullet> i))"
immler@69611
  1466
        apply (subst euclidean_dist_l2)
immler@69611
  1467
        using zero_le_dist
immler@69611
  1468
        apply (rule L2_set_le_sum)
immler@69611
  1469
        done
immler@69611
  1470
      also have "\<dots> < (\<Sum>i\<in>(Basis::'a set). e / (real_of_nat DIM('a)))"
immler@69611
  1471
        apply (rule sum_strict_mono)
immler@69611
  1472
        using n
immler@69611
  1473
        apply auto
immler@69611
  1474
        done
immler@69611
  1475
      finally have "dist (f (r n)) l < e"
immler@69611
  1476
        by auto
immler@69611
  1477
    }
immler@69611
  1478
    ultimately have "eventually (\<lambda>n. dist (f (r n)) l < e) sequentially"
immler@69611
  1479
      by (rule eventually_mono)
immler@69611
  1480
  }
immler@69611
  1481
  then have *: "((f \<circ> r) \<longlongrightarrow> l) sequentially"
immler@69611
  1482
    unfolding o_def tendsto_iff by simp
immler@69611
  1483
  with r show "\<exists>l r. strict_mono r \<and> ((f \<circ> r) \<longlongrightarrow> l) sequentially"
immler@69611
  1484
    by auto
immler@69611
  1485
qed
immler@69611
  1486
immler@69611
  1487
instance%important euclidean_space \<subseteq> banach ..
immler@69611
  1488
immler@69611
  1489
instance euclidean_space \<subseteq> second_countable_topology
immler@69611
  1490
proof
immler@69611
  1491
  define a where "a f = (\<Sum>i\<in>Basis. fst (f i) *\<^sub>R i)" for f :: "'a \<Rightarrow> real \<times> real"
immler@69611
  1492
  then have a: "\<And>f. (\<Sum>i\<in>Basis. fst (f i) *\<^sub>R i) = a f"
immler@69611
  1493
    by simp
immler@69611
  1494
  define b where "b f = (\<Sum>i\<in>Basis. snd (f i) *\<^sub>R i)" for f :: "'a \<Rightarrow> real \<times> real"
immler@69611
  1495
  then have b: "\<And>f. (\<Sum>i\<in>Basis. snd (f i) *\<^sub>R i) = b f"
immler@69611
  1496
    by simp
immler@69611
  1497
  define B where "B = (\<lambda>f. box (a f) (b f)) ` (Basis \<rightarrow>\<^sub>E (\<rat> \<times> \<rat>))"
immler@69611
  1498
immler@69611
  1499
  have "Ball B open" by (simp add: B_def open_box)
immler@69611
  1500
  moreover have "(\<forall>A. open A \<longrightarrow> (\<exists>B'\<subseteq>B. \<Union>B' = A))"
immler@69611
  1501
  proof safe
immler@69611
  1502
    fix A::"'a set"
immler@69611
  1503
    assume "open A"
immler@69611
  1504
    show "\<exists>B'\<subseteq>B. \<Union>B' = A"
immler@69611
  1505
      apply (rule exI[of _ "{b\<in>B. b \<subseteq> A}"])
immler@69611
  1506
      apply (subst (3) open_UNION_box[OF \<open>open A\<close>])
immler@69611
  1507
      apply (auto simp: a b B_def)
immler@69611
  1508
      done
immler@69611
  1509
  qed
immler@69611
  1510
  ultimately
immler@69611
  1511
  have "topological_basis B"
immler@69611
  1512
    unfolding topological_basis_def by blast
immler@69611
  1513
  moreover
immler@69611
  1514
  have "countable B"
immler@69611
  1515
    unfolding B_def
immler@69611
  1516
    by (intro countable_image countable_PiE finite_Basis countable_SIGMA countable_rat)
immler@69611
  1517
  ultimately show "\<exists>B::'a set set. countable B \<and> open = generate_topology B"
immler@69611
  1518
    by (blast intro: topological_basis_imp_subbasis)
immler@69611
  1519
qed
immler@69611
  1520
immler@69611
  1521
instance euclidean_space \<subseteq> polish_space ..
immler@69611
  1522
immler@69611
  1523
immler@69611
  1524
subsection \<open>Compact Boxes\<close>
immler@69611
  1525
immler@69611
  1526
lemma compact_cbox [simp]:
wenzelm@61076
  1527
  fixes a :: "'a::euclidean_space"
immler@69611
  1528
  shows "compact (cbox a b)"
immler@69611
  1529
  using bounded_closed_imp_seq_compact[of "cbox a b"] using bounded_cbox[of a b]
immler@69611
  1530
  by (auto simp: compact_eq_seq_compact_metric)
immler@69611
  1531
immler@69611
  1532
proposition is_interval_compact:
immler@69611
  1533
   "is_interval S \<and> compact S \<longleftrightarrow> (\<exists>a b. S = cbox a b)"   (is "?lhs = ?rhs")
immler@69611
  1534
proof (cases "S = {}")
immler@69611
  1535
  case True
immler@69611
  1536
  with empty_as_interval show ?thesis by auto
immler@69611
  1537
next
immler@69611
  1538
  case False
immler@69611
  1539
  show ?thesis
immler@69611
  1540
  proof
immler@69611
  1541
    assume L: ?lhs
immler@69611
  1542
    then have "is_interval S" "compact S" by auto
immler@69611
  1543
    define a where "a \<equiv> \<Sum>i\<in>Basis. (INF x\<in>S. x \<bullet> i) *\<^sub>R i"
immler@69611
  1544
    define b where "b \<equiv> \<Sum>i\<in>Basis. (SUP x\<in>S. x \<bullet> i) *\<^sub>R i"
immler@69611
  1545
    have 1: "\<And>x i. \<lbrakk>x \<in> S; i \<in> Basis\<rbrakk> \<Longrightarrow> (INF x\<in>S. x \<bullet> i) \<le> x \<bullet> i"
immler@69611
  1546
      by (simp add: cInf_lower bounded_inner_imp_bdd_below compact_imp_bounded L)
immler@69611
  1547
    have 2: "\<And>x i. \<lbrakk>x \<in> S; i \<in> Basis\<rbrakk> \<Longrightarrow> x \<bullet> i \<le> (SUP x\<in>S. x \<bullet> i)"
immler@69611
  1548
      by (simp add: cSup_upper bounded_inner_imp_bdd_above compact_imp_bounded L)
immler@69611
  1549
    have 3: "x \<in> S" if inf: "\<And>i. i \<in> Basis \<Longrightarrow> (INF x\<in>S. x \<bullet> i) \<le> x \<bullet> i"
immler@69611
  1550
                   and sup: "\<And>i. i \<in> Basis \<Longrightarrow> x \<bullet> i \<le> (SUP x\<in>S. x \<bullet> i)" for x
immler@69611
  1551
    proof (rule mem_box_componentwiseI [OF \<open>is_interval S\<close>])
immler@69611
  1552
      fix i::'a
immler@69611
  1553
      assume i: "i \<in> Basis"
immler@69611
  1554
      have cont: "continuous_on S (\<lambda>x. x \<bullet> i)"
immler@69611
  1555
        by (intro continuous_intros)
immler@69611
  1556
      obtain a where "a \<in> S" and a: "\<And>y. y\<in>S \<Longrightarrow> a \<bullet> i \<le> y \<bullet> i"
immler@69611
  1557
        using continuous_attains_inf [OF \<open>compact S\<close> False cont] by blast
immler@69611
  1558
      obtain b where "b \<in> S" and b: "\<And>y. y\<in>S \<Longrightarrow> y \<bullet> i \<le> b \<bullet> i"
immler@69611
  1559
        using continuous_attains_sup [OF \<open>compact S\<close> False cont] by blast
immler@69611
  1560
      have "a \<bullet> i \<le> (INF x\<in>S. x \<bullet> i)"
immler@69611
  1561
        by (simp add: False a cINF_greatest)
immler@69611
  1562
      also have "\<dots> \<le> x \<bullet> i"
immler@69611
  1563
        by (simp add: i inf)
immler@69611
  1564
      finally have ai: "a \<bullet> i \<le> x \<bullet> i" .
immler@69611
  1565
      have "x \<bullet> i \<le> (SUP x\<in>S. x \<bullet> i)"
immler@69611
  1566
        by (simp add: i sup)
immler@69611
  1567
      also have "(SUP x\<in>S. x \<bullet> i) \<le> b \<bullet> i"
immler@69611
  1568
        by (simp add: False b cSUP_least)
immler@69611
  1569
      finally have bi: "x \<bullet> i \<le> b \<bullet> i" .
immler@69611
  1570
      show "x \<bullet> i \<in> (\<lambda>x. x \<bullet> i) ` S"
immler@69611
  1571
        apply (rule_tac x="\<Sum>j\<in>Basis. (if j = i then x \<bullet> i else a \<bullet> j) *\<^sub>R j" in image_eqI)
immler@69611
  1572
        apply (simp add: i)
immler@69611
  1573
        apply (rule mem_is_intervalI [OF \<open>is_interval S\<close> \<open>a \<in> S\<close> \<open>b \<in> S\<close>])
immler@69611
  1574
        using i ai bi apply force
immler@69611
  1575
        done
immler@69611
  1576
    qed
immler@69611
  1577
    have "S = cbox a b"
immler@69611
  1578
      by (auto simp: a_def b_def mem_box intro: 1 2 3)
immler@69611
  1579
    then show ?rhs
immler@69611
  1580
      by blast
immler@69611
  1581
  next
immler@69611
  1582
    assume R: ?rhs
immler@69611
  1583
    then show ?lhs
immler@69611
  1584
      using compact_cbox is_interval_cbox by blast
immler@69611
  1585
  qed
immler@69611
  1586
qed
immler@69611
  1587
immler@69611
  1588
immler@69615
  1589
subsection%unimportant\<open>Componentwise limits and continuity\<close>
immler@69615
  1590
immler@69615
  1591
text\<open>But is the premise really necessary? Need to generalise @{thm euclidean_dist_l2}\<close>
immler@69615
  1592
lemma Euclidean_dist_upper: "i \<in> Basis \<Longrightarrow> dist (x \<bullet> i) (y \<bullet> i) \<le> dist x y"
immler@69615
  1593
  by (metis (no_types) member_le_L2_set euclidean_dist_l2 finite_Basis)
immler@69615
  1594
immler@69615
  1595
text\<open>But is the premise \<^term>\<open>i \<in> Basis\<close> really necessary?\<close>
immler@69615
  1596
lemma open_preimage_inner:
immler@69615
  1597
  assumes "open S" "i \<in> Basis"
immler@69615
  1598
    shows "open {x. x \<bullet> i \<in> S}"
immler@69615
  1599
proof (rule openI, simp)
immler@69615
  1600
  fix x
immler@69615
  1601
  assume x: "x \<bullet> i \<in> S"
immler@69615
  1602
  with assms obtain e where "0 < e" and e: "ball (x \<bullet> i) e \<subseteq> S"
immler@69615
  1603
    by (auto simp: open_contains_ball_eq)
immler@69615
  1604
  have "\<exists>e>0. ball (y \<bullet> i) e \<subseteq> S" if dxy: "dist x y < e / 2" for y
immler@69615
  1605
  proof (intro exI conjI)
immler@69615
  1606
    have "dist (x \<bullet> i) (y \<bullet> i) < e / 2"
immler@69615
  1607
      by (meson \<open>i \<in> Basis\<close> dual_order.trans Euclidean_dist_upper not_le that)
immler@69615
  1608
    then have "dist (x \<bullet> i) z < e" if "dist (y \<bullet> i) z < e / 2" for z
immler@69615
  1609
      by (metis dist_commute dist_triangle_half_l that)
immler@69615
  1610
    then have "ball (y \<bullet> i) (e / 2) \<subseteq> ball (x \<bullet> i) e"
immler@69615
  1611
      using mem_ball by blast
immler@69615
  1612
      with e show "ball (y \<bullet> i) (e / 2) \<subseteq> S"
immler@69615
  1613
        by (metis order_trans)
immler@69615
  1614
  qed (simp add: \<open>0 < e\<close>)
immler@69615
  1615
  then show "\<exists>e>0. ball x e \<subseteq> {s. s \<bullet> i \<in> S}"
immler@69615
  1616
    by (metis (no_types, lifting) \<open>0 < e\<close> \<open>open S\<close> half_gt_zero_iff mem_Collect_eq mem_ball open_contains_ball_eq subsetI)
immler@69615
  1617
qed
immler@69615
  1618
immler@69615
  1619
proposition tendsto_componentwise_iff:
immler@69615
  1620
  fixes f :: "_ \<Rightarrow> 'b::euclidean_space"
immler@69615
  1621
  shows "(f \<longlongrightarrow> l) F \<longleftrightarrow> (\<forall>i \<in> Basis. ((\<lambda>x. (f x \<bullet> i)) \<longlongrightarrow> (l \<bullet> i)) F)"
immler@69615
  1622
         (is "?lhs = ?rhs")
immler@69615
  1623
proof
immler@69615
  1624
  assume ?lhs
immler@69615
  1625
  then show ?rhs
immler@69615
  1626
    unfolding tendsto_def
immler@69615
  1627
    apply clarify
immler@69615
  1628
    apply (drule_tac x="{s. s \<bullet> i \<in> S}" in spec)
immler@69615
  1629
    apply (auto simp: open_preimage_inner)
immler@69615
  1630
    done
immler@69615
  1631
next
immler@69615
  1632
  assume R: ?rhs
immler@69615
  1633
  then have "\<And>e. e > 0 \<Longrightarrow> \<forall>i\<in>Basis. \<forall>\<^sub>F x in F. dist (f x \<bullet> i) (l \<bullet> i) < e"
immler@69615
  1634
    unfolding tendsto_iff by blast
immler@69615
  1635
  then have R': "\<And>e. e > 0 \<Longrightarrow> \<forall>\<^sub>F x in F. \<forall>i\<in>Basis. dist (f x \<bullet> i) (l \<bullet> i) < e"
immler@69615
  1636
      by (simp add: eventually_ball_finite_distrib [symmetric])
immler@69615
  1637
  show ?lhs
immler@69615
  1638
  unfolding tendsto_iff
immler@69615
  1639
  proof clarify
immler@69615
  1640
    fix e::real
immler@69615
  1641
    assume "0 < e"
immler@69615
  1642
    have *: "L2_set (\<lambda>i. dist (f x \<bullet> i) (l \<bullet> i)) Basis < e"
immler@69615
  1643
             if "\<forall>i\<in>Basis. dist (f x \<bullet> i) (l \<bullet> i) < e / real DIM('b)" for x
immler@69615
  1644
    proof -
immler@69615
  1645
      have "L2_set (\<lambda>i. dist (f x \<bullet> i) (l \<bullet> i)) Basis \<le> sum (\<lambda>i. dist (f x \<bullet> i) (l \<bullet> i)) Basis"
immler@69615
  1646
        by (simp add: L2_set_le_sum)
immler@69615
  1647
      also have "... < DIM('b) * (e / real DIM('b))"
immler@69615
  1648
        apply (rule sum_bounded_above_strict)
immler@69615
  1649
        using that by auto
immler@69615
  1650
      also have "... = e"
immler@69615
  1651
        by (simp add: field_simps)
immler@69615
  1652
      finally show "L2_set (\<lambda>i. dist (f x \<bullet> i) (l \<bullet> i)) Basis < e" .
immler@69615
  1653
    qed
immler@69615
  1654
    have "\<forall>\<^sub>F x in F. \<forall>i\<in>Basis. dist (f x \<bullet> i) (l \<bullet> i) < e / DIM('b)"
immler@69615
  1655
      apply (rule R')
immler@69615
  1656
      using \<open>0 < e\<close> by simp
immler@69615
  1657
    then show "\<forall>\<^sub>F x in F. dist (f x) l < e"
immler@69615
  1658
      apply (rule eventually_mono)
immler@69615
  1659
      apply (subst euclidean_dist_l2)
immler@69615
  1660
      using * by blast
immler@69615
  1661
  qed
immler@69615
  1662
qed
immler@69615
  1663
immler@69615
  1664
immler@69615
  1665
corollary continuous_componentwise:
immler@69615
  1666
   "continuous F f \<longleftrightarrow> (\<forall>i \<in> Basis. continuous F (\<lambda>x. (f x \<bullet> i)))"
immler@69615
  1667
by (simp add: continuous_def tendsto_componentwise_iff [symmetric])
immler@69615
  1668
immler@69615
  1669
corollary continuous_on_componentwise:
immler@69615
  1670
  fixes S :: "'a :: t2_space set"
immler@69615
  1671
  shows "continuous_on S f \<longleftrightarrow> (\<forall>i \<in> Basis. continuous_on S (\<lambda>x. (f x \<bullet> i)))"
immler@69615
  1672
  apply (simp add: continuous_on_eq_continuous_within)
immler@69615
  1673
  using continuous_componentwise by blast
immler@69615
  1674
immler@69615
  1675
lemma linear_componentwise_iff:
immler@69615
  1676
     "(linear f') \<longleftrightarrow> (\<forall>i\<in>Basis. linear (\<lambda>x. f' x \<bullet> i))"
immler@69615
  1677
  apply (auto simp: linear_iff inner_left_distrib)
immler@69615
  1678
   apply (metis inner_left_distrib euclidean_eq_iff)
immler@69615
  1679
  by (metis euclidean_eqI inner_scaleR_left)
immler@69615
  1680
immler@69615
  1681
lemma bounded_linear_componentwise_iff:
immler@69615
  1682
     "(bounded_linear f') \<longleftrightarrow> (\<forall>i\<in>Basis. bounded_linear (\<lambda>x. f' x \<bullet> i))"
immler@69615
  1683
     (is "?lhs = ?rhs")
immler@69615
  1684
proof
immler@69615
  1685
  assume ?lhs then show ?rhs
immler@69615
  1686
    by (simp add: bounded_linear_inner_left_comp)
immler@69615
  1687
next
immler@69615
  1688
  assume ?rhs
immler@69615
  1689
  then have "(\<forall>i\<in>Basis. \<exists>K. \<forall>x. \<bar>f' x \<bullet> i\<bar> \<le> norm x * K)" "linear f'"
immler@69615
  1690
    by (auto simp: bounded_linear_def bounded_linear_axioms_def linear_componentwise_iff [symmetric] ball_conj_distrib)
immler@69615
  1691
  then obtain F where F: "\<And>i x. i \<in> Basis \<Longrightarrow> \<bar>f' x \<bullet> i\<bar> \<le> norm x * F i"
immler@69615
  1692
    by metis
immler@69615
  1693
  have "norm (f' x) \<le> norm x * sum F Basis" for x
immler@69615
  1694
  proof -
immler@69615
  1695
    have "norm (f' x) \<le> (\<Sum>i\<in>Basis. \<bar>f' x \<bullet> i\<bar>)"
immler@69615
  1696
      by (rule norm_le_l1)
immler@69615
  1697
    also have "... \<le> (\<Sum>i\<in>Basis. norm x * F i)"
immler@69615
  1698
      by (metis F sum_mono)
immler@69615
  1699
    also have "... = norm x * sum F Basis"
immler@69615
  1700
      by (simp add: sum_distrib_left)
immler@69615
  1701
    finally show ?thesis .
immler@69615
  1702
  qed
immler@69615
  1703
  then show ?lhs
immler@69615
  1704
    by (force simp: bounded_linear_def bounded_linear_axioms_def \<open>linear f'\<close>)
immler@69615
  1705
qed
immler@69615
  1706
immler@69615
  1707
subsection%unimportant \<open>Continuous Extension\<close>
immler@69615
  1708
immler@69615
  1709
definition clamp :: "'a::euclidean_space \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'a" where
immler@69615
  1710
  "clamp a b x = (if (\<forall>i\<in>Basis. a \<bullet> i \<le> b \<bullet> i)
immler@69615
  1711
    then (\<Sum>i\<in>Basis. (if x\<bullet>i < a\<bullet>i then a\<bullet>i else if x\<bullet>i \<le> b\<bullet>i then x\<bullet>i else b\<bullet>i) *\<^sub>R i)
immler@69615
  1712
    else a)"
immler@69615
  1713
immler@69615
  1714
lemma clamp_in_interval[simp]:
immler@69615
  1715
  assumes "\<And>i. i \<in> Basis \<Longrightarrow> a \<bullet> i \<le> b \<bullet> i"
immler@69615
  1716
  shows "clamp a b x \<in> cbox a b"
immler@69615
  1717
  unfolding clamp_def
immler@69615
  1718
  using box_ne_empty(1)[of a b] assms by (auto simp: cbox_def)
immler@69615
  1719
immler@69615
  1720
lemma clamp_cancel_cbox[simp]:
immler@69615
  1721
  fixes x a b :: "'a::euclidean_space"
immler@69615
  1722
  assumes x: "x \<in> cbox a b"
immler@69615
  1723
  shows "clamp a b x = x"
immler@69615
  1724
  using assms
immler@69615
  1725
  by (auto simp: clamp_def mem_box intro!: euclidean_eqI[where 'a='a])
immler@69615
  1726
immler@69615
  1727
lemma clamp_empty_interval:
immler@69615
  1728
  assumes "i \<in> Basis" "a \<bullet> i > b \<bullet> i"
immler@69615
  1729
  shows "clamp a b = (\<lambda>_. a)"
immler@69615
  1730
  using assms
immler@69615
  1731
  by (force simp: clamp_def[abs_def] split: if_splits intro!: ext)
immler@69615
  1732
immler@69615
  1733
lemma dist_clamps_le_dist_args:
immler@69615
  1734
  fixes x :: "'a::euclidean_space"
immler@69615
  1735
  shows "dist (clamp a b y) (clamp a b x) \<le> dist y x"
immler@69615
  1736
proof cases
immler@69615
  1737
  assume le: "(\<forall>i\<in>Basis. a \<bullet> i \<le> b \<bullet> i)"
immler@69615
  1738
  then have "(\<Sum>i\<in>Basis. (dist (clamp a b y \<bullet> i) (clamp a b x \<bullet> i))\<^sup>2) \<le>
immler@69615
  1739
    (\<Sum>i\<in>Basis. (dist (y \<bullet> i) (x \<bullet> i))\<^sup>2)"
immler@69615
  1740
    by (auto intro!: sum_mono simp: clamp_def dist_real_def abs_le_square_iff[symmetric])
immler@69615
  1741
  then show ?thesis
immler@69615
  1742
    by (auto intro: real_sqrt_le_mono
immler@69615
  1743
      simp: euclidean_dist_l2[where y=x] euclidean_dist_l2[where y="clamp a b x"] L2_set_def)
immler@69615
  1744
qed (auto simp: clamp_def)
immler@69615
  1745
immler@69615
  1746
lemma clamp_continuous_at:
immler@69615
  1747
  fixes f :: "'a::euclidean_space \<Rightarrow> 'b::metric_space"
immler@69615
  1748
    and x :: 'a
immler@69615
  1749
  assumes f_cont: "continuous_on (cbox a b) f"
immler@69615
  1750
  shows "continuous (at x) (\<lambda>x. f (clamp a b x))"
immler@69615
  1751
proof cases
immler@69615
  1752
  assume le: "(\<forall>i\<in>Basis. a \<bullet> i \<le> b \<bullet> i)"
immler@69615
  1753
  show ?thesis
immler@69615
  1754
    unfolding continuous_at_eps_delta
immler@69615
  1755
  proof safe
immler@69615
  1756
    fix x :: 'a
immler@69615
  1757
    fix e :: real
immler@69615
  1758
    assume "e > 0"
immler@69615
  1759
    moreover have "clamp a b x \<in> cbox a b"
immler@69615
  1760
      by (simp add: clamp_in_interval le)
immler@69615
  1761
    moreover note f_cont[simplified continuous_on_iff]
immler@69615
  1762
    ultimately
immler@69615
  1763
    obtain d where d: "0 < d"
immler@69615
  1764
      "\<And>x'. x' \<in> cbox a b \<Longrightarrow> dist x' (clamp a b x) < d \<Longrightarrow> dist (f x') (f (clamp a b x)) < e"
immler@69615
  1765
      by force
immler@69615
  1766
    show "\<exists>d>0. \<forall>x'. dist x' x < d \<longrightarrow>
immler@69615
  1767
      dist (f (clamp a b x')) (f (clamp a b x)) < e"
immler@69615
  1768
      using le
immler@69615
  1769
      by (auto intro!: d clamp_in_interval dist_clamps_le_dist_args[THEN le_less_trans])
immler@69615
  1770
  qed
immler@69615
  1771
qed (auto simp: clamp_empty_interval)
immler@69615
  1772
immler@69615
  1773
lemma clamp_continuous_on:
immler@69615
  1774
  fixes f :: "'a::euclidean_space \<Rightarrow> 'b::metric_space"
immler@69615
  1775
  assumes f_cont: "continuous_on (cbox a b) f"
immler@69615
  1776
  shows "continuous_on S (\<lambda>x. f (clamp a b x))"
immler@69615
  1777
  using assms
immler@69615
  1778
  by (auto intro: continuous_at_imp_continuous_on clamp_continuous_at)
immler@69615
  1779
immler@69615
  1780
lemma clamp_bounded:
immler@69615
  1781
  fixes f :: "'a::euclidean_space \<Rightarrow> 'b::metric_space"
immler@69615
  1782
  assumes bounded: "bounded (f ` (cbox a b))"
immler@69615
  1783
  shows "bounded (range (\<lambda>x. f (clamp a b x)))"
immler@69615
  1784
proof cases
immler@69615
  1785
  assume le: "(\<forall>i\<in>Basis. a \<bullet> i \<le> b \<bullet> i)"
immler@69615
  1786
  from bounded obtain c where f_bound: "\<forall>x\<in>f ` cbox a b. dist undefined x \<le> c"
immler@69615
  1787
    by (auto simp: bounded_any_center[where a=undefined])
immler@69615
  1788
  then show ?thesis
immler@69615
  1789
    by (auto intro!: exI[where x=c] clamp_in_interval[OF le[rule_format]]
immler@69615
  1790
        simp: bounded_any_center[where a=undefined])
immler@69615
  1791
qed (auto simp: clamp_empty_interval image_def)
immler@69615
  1792
immler@69615
  1793
immler@69615
  1794
definition ext_cont :: "('a::euclidean_space \<Rightarrow> 'b::metric_space) \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'b"
immler@69615
  1795
  where "ext_cont f a b = (\<lambda>x. f (clamp a b x))"
immler@69615
  1796
immler@69615
  1797
lemma ext_cont_cancel_cbox[simp]:
immler@69615
  1798
  fixes x a b :: "'a::euclidean_space"
immler@69615
  1799
  assumes x: "x \<in> cbox a b"
immler@69615
  1800
  shows "ext_cont f a b x = f x"
immler@69615
  1801
  using assms
immler@69615
  1802
  unfolding ext_cont_def
immler@69615
  1803
  by (auto simp: clamp_def mem_box intro!: euclidean_eqI[where 'a='a] arg_cong[where f=f])
immler@69615
  1804
immler@69615
  1805
lemma continuous_on_ext_cont[continuous_intros]:
immler@69615
  1806
  "continuous_on (cbox a b) f \<Longrightarrow> continuous_on S (ext_cont f a b)"
immler@69615
  1807
  by (auto intro!: clamp_continuous_on simp: ext_cont_def)
immler@69615
  1808
immler@69615
  1809
immler@69615
  1810
subsection \<open>Separability\<close>
immler@69615
  1811
immler@69615
  1812
lemma univ_second_countable_sequence:
immler@69615
  1813
  obtains B :: "nat \<Rightarrow> 'a::euclidean_space set"
immler@69615
  1814
    where "inj B" "\<And>n. open(B n)" "\<And>S. open S \<Longrightarrow> \<exists>k. S = \<Union>{B n |n. n \<in> k}"
immler@69615
  1815
proof -
immler@69615
  1816
  obtain \<B> :: "'a set set"
immler@69615
  1817
  where "countable \<B>"
immler@69615
  1818
    and opn: "\<And>C. C \<in> \<B> \<Longrightarrow> open C"
immler@69615
  1819
    and Un: "\<And>S. open S \<Longrightarrow> \<exists>U. U \<subseteq> \<B> \<and> S = \<Union>U"
immler@69615
  1820
    using univ_second_countable by blast
immler@69615
  1821
  have *: "infinite (range (\<lambda>n. ball (0::'a) (inverse(Suc n))))"
immler@69615
  1822
    apply (rule Infinite_Set.range_inj_infinite)
immler@69615
  1823
    apply (simp add: inj_on_def ball_eq_ball_iff)
immler@69615
  1824
    done
immler@69615
  1825
  have "infinite \<B>"
immler@69615
  1826
  proof
immler@69615
  1827
    assume "finite \<B>"
immler@69615
  1828
    then have "finite (Union ` (Pow \<B>))"
immler@69615
  1829
      by simp
immler@69615
  1830
    then have "finite (range (\<lambda>n. ball (0::'a) (inverse(Suc n))))"
immler@69615
  1831
      apply (rule rev_finite_subset)
immler@69615
  1832
      by (metis (no_types, lifting) PowI image_eqI image_subset_iff Un [OF open_ball])
immler@69615
  1833
    with * show False by simp
immler@69615
  1834
  qed
immler@69615
  1835
  obtain f :: "nat \<Rightarrow> 'a set" where "\<B> = range f" "inj f"
immler@69615
  1836
    by (blast intro: countable_as_injective_image [OF \<open>countable \<B>\<close> \<open>infinite \<B>\<close>])
immler@69615
  1837
  have *: "\<exists>k. S = \<Union>{f n |n. n \<in> k}" if "open S" for S
immler@69615
  1838
    using Un [OF that]
immler@69615
  1839
    apply clarify
immler@69615
  1840
    apply (rule_tac x="f-`U" in exI)
immler@69615
  1841
    using \<open>inj f\<close> \<open>\<B> = range f\<close> apply force
immler@69615
  1842
    done
immler@69615
  1843
  show ?thesis
immler@69615
  1844
    apply (rule that [OF \<open>inj f\<close> _ *])
immler@69615
  1845
    apply (auto simp: \<open>\<B> = range f\<close> opn)
immler@69615
  1846
    done
immler@69615
  1847
qed
immler@69615
  1848
immler@69615
  1849
proposition separable:
immler@69615
  1850
  fixes S :: "'a::{metric_space, second_countable_topology} set"
immler@69615
  1851
  obtains T where "countable T" "T \<subseteq> S" "S \<subseteq> closure T"
immler@69615
  1852
proof -
immler@69615
  1853
  obtain \<B> :: "'a set set"
immler@69615
  1854
    where "countable \<B>"
immler@69615
  1855
      and "{} \<notin> \<B>"
immler@69615
  1856
      and ope: "\<And>C. C \<in> \<B> \<Longrightarrow> openin(subtopology euclidean S) C"
immler@69615
  1857
      and if_ope: "\<And>T. openin(subtopology euclidean S) T \<Longrightarrow> \<exists>\<U>. \<U> \<subseteq> \<B> \<and> T = \<Union>\<U>"
immler@69615
  1858
    by (meson subset_second_countable)
immler@69615
  1859
  then obtain f where f: "\<And>C. C \<in> \<B> \<Longrightarrow> f C \<in> C"
immler@69615
  1860
    by (metis equals0I)
immler@69615
  1861
  show ?thesis
immler@69615
  1862
  proof
immler@69615
  1863
    show "countable (f ` \<B>)"
immler@69615
  1864
      by (simp add: \<open>countable \<B>\<close>)
immler@69615
  1865
    show "f ` \<B> \<subseteq> S"
immler@69615
  1866
      using ope f openin_imp_subset by blast
immler@69615
  1867
    show "S \<subseteq> closure (f ` \<B>)"
immler@69615
  1868
    proof (clarsimp simp: closure_approachable)
immler@69615
  1869
      fix x and e::real
immler@69615
  1870
      assume "x \<in> S" "0 < e"
immler@69615
  1871
      have "openin (subtopology euclidean S) (S \<inter> ball x e)"
immler@69615
  1872
        by (simp add: openin_Int_open)
immler@69615
  1873
      with if_ope obtain \<U> where  \<U>: "\<U> \<subseteq> \<B>" "S \<inter> ball x e = \<Union>\<U>"
immler@69615
  1874
        by meson
immler@69615
  1875
      show "\<exists>C \<in> \<B>. dist (f C) x < e"
immler@69615
  1876
      proof (cases "\<U> = {}")
immler@69615
  1877
        case True
immler@69615
  1878
        then show ?thesis
immler@69615
  1879
          using \<open>0 < e\<close>  \<U> \<open>x \<in> S\<close> by auto
immler@69615
  1880
      next
immler@69615
  1881
        case False
immler@69615
  1882
        then obtain C where "C \<in> \<U>" by blast
immler@69615
  1883
        show ?thesis
immler@69615
  1884
        proof
immler@69615
  1885
          show "dist (f C) x < e"
immler@69615
  1886
            by (metis Int_iff Union_iff \<U> \<open>C \<in> \<U>\<close> dist_commute f mem_ball subsetCE)
immler@69615
  1887
          show "C \<in> \<B>"
immler@69615
  1888
            using \<open>\<U> \<subseteq> \<B>\<close> \<open>C \<in> \<U>\<close> by blast
immler@69615
  1889
        qed
immler@69615
  1890
      qed
immler@69615
  1891
    qed
immler@69615
  1892
  qed
immler@69615
  1893
qed
immler@69615
  1894
immler@69615
  1895
immler@69613
  1896
subsection%unimportant \<open>Diameter\<close>
immler@69613
  1897
immler@69613
  1898
lemma diameter_cball [simp]:
immler@69613
  1899
  fixes a :: "'a::euclidean_space"
immler@69613
  1900
  shows "diameter(cball a r) = (if r < 0 then 0 else 2*r)"
immler@69613
  1901
proof -
immler@69613
  1902
  have "diameter(cball a r) = 2*r" if "r \<ge> 0"
immler@69613
  1903
  proof (rule order_antisym)
immler@69613
  1904
    show "diameter (cball a r) \<le> 2*r"
immler@69613
  1905
    proof (rule diameter_le)
immler@69613
  1906
      fix x y assume "x \<in> cball a r" "y \<in> cball a r"
immler@69613
  1907
      then have "norm (x - a) \<le> r" "norm (a - y) \<le> r"
immler@69613
  1908
        by (auto simp: dist_norm norm_minus_commute)
immler@69613
  1909
      then have "norm (x - y) \<le> r+r"
immler@69613
  1910
        using norm_diff_triangle_le by blast
immler@69613
  1911
      then show "norm (x - y) \<le> 2*r" by simp
immler@69613
  1912
    qed (simp add: that)
immler@69613
  1913
    have "2*r = dist (a + r *\<^sub>R (SOME i. i \<in> Basis)) (a - r *\<^sub>R (SOME i. i \<in> Basis))"
immler@69613
  1914
      apply (simp add: dist_norm)
immler@69613
  1915
      by (metis abs_of_nonneg mult.right_neutral norm_numeral norm_scaleR norm_some_Basis real_norm_def scaleR_2 that)
immler@69613
  1916
    also have "... \<le> diameter (cball a r)"
immler@69613
  1917
      apply (rule diameter_bounded_bound)
immler@69613
  1918
      using that by (auto simp: dist_norm)
immler@69613
  1919
    finally show "2*r \<le> diameter (cball a r)" .
immler@69613
  1920
  qed
immler@69613
  1921
  then show ?thesis by simp
immler@69613
  1922
qed
immler@69613
  1923
immler@69613
  1924
lemma diameter_ball [simp]:
immler@69613
  1925
  fixes a :: "'a::euclidean_space"
immler@69613
  1926
  shows "diameter(ball a r) = (if r < 0 then 0 else 2*r)"
immler@69613
  1927
proof -
immler@69613
  1928
  have "diameter(ball a r) = 2*r" if "r > 0"
immler@69613
  1929
    by (metis bounded_ball diameter_closure closure_ball diameter_cball less_eq_real_def linorder_not_less that)
immler@69613
  1930
  then show ?thesis
immler@69613
  1931
    by (simp add: diameter_def)
immler@69613
  1932
qed
immler@69613
  1933
immler@69613
  1934
lemma diameter_closed_interval [simp]: "diameter {a..b} = (if b < a then 0 else b-a)"
immler@69613
  1935
proof -
immler@69613
  1936
  have "{a .. b} = cball ((a+b)/2) ((b-a)/2)"
immler@69613
  1937
    by (auto simp: dist_norm abs_if divide_simps split: if_split_asm)
immler@69613
  1938
  then show ?thesis
immler@69613
  1939
    by simp
immler@69613
  1940
qed
immler@69613
  1941
immler@69613
  1942
lemma diameter_open_interval [simp]: "diameter {a<..<b} = (if b < a then 0 else b-a)"
immler@69613
  1943
proof -
immler@69613
  1944
  have "{a <..< b} = ball ((a+b)/2) ((b-a)/2)"
immler@69613
  1945
    by (auto simp: dist_norm abs_if divide_simps split: if_split_asm)
immler@69613
  1946
  then show ?thesis
immler@69613
  1947
    by simp
immler@69613
  1948
qed
immler@69613
  1949
immler@69613
  1950
lemma diameter_cbox:
immler@69613
  1951
  fixes a b::"'a::euclidean_space"
immler@69613
  1952
  shows "(\<forall>i \<in> Basis. a \<bullet> i \<le> b \<bullet> i) \<Longrightarrow> diameter (cbox a b) = dist a b"
immler@69613
  1953
  by (force simp: diameter_def intro!: cSup_eq_maximum L2_set_mono
immler@69613
  1954
     simp: euclidean_dist_l2[where 'a='a] cbox_def dist_norm)
immler@69613
  1955
immler@69613
  1956
immler@69617
  1957
subsection%unimportant\<open>Relating linear images to open/closed/interior/closure/connected\<close>
immler@56189
  1958
immler@69611
  1959
proposition open_surjective_linear_image:
immler@69611
  1960
  fixes f :: "'a::real_normed_vector \<Rightarrow> 'b::euclidean_space"
immler@69611
  1961
  assumes "open A" "linear f" "surj f"
immler@69611
  1962
    shows "open(f ` A)"
immler@69611
  1963
unfolding open_dist
immler@69611
  1964
proof clarify
immler@69611
  1965
  fix x
immler@69611
  1966
  assume "x \<in> A"
immler@69611
  1967
  have "bounded (inv f ` Basis)"
immler@69611
  1968
    by (simp add: finite_imp_bounded)
immler@69611
  1969
  with bounded_pos obtain B where "B > 0" and B: "\<And>x. x \<in> inv f ` Basis \<Longrightarrow> norm x \<le> B"
immler@69611
  1970
    by metis
immler@69611
  1971
  obtain e where "e > 0" and e: "\<And>z. dist z x < e \<Longrightarrow> z \<in> A"
immler@69611
  1972
    by (metis open_dist \<open>x \<in> A\<close> \<open>open A\<close>)
immler@69611
  1973
  define \<delta> where "\<delta> \<equiv> e / B / DIM('b)"
immler@69611
  1974
  show "\<exists>e>0. \<forall>y. dist y (f x) < e \<longrightarrow> y \<in> f ` A"
immler@69611
  1975
  proof (intro exI conjI)
immler@69611
  1976
    show "\<delta> > 0"
immler@69611
  1977
      using \<open>e > 0\<close> \<open>B > 0\<close>  by (simp add: \<delta>_def divide_simps)
immler@69611
  1978
    have "y \<in> f ` A" if "dist y (f x) * (B * real DIM('b)) < e" for y
immler@69611
  1979
    proof -
immler@69611
  1980
      define u where "u \<equiv> y - f x"
immler@69611
  1981
      show ?thesis
immler@69611
  1982
      proof (rule image_eqI)
immler@69611
  1983
        show "y = f (x + (\<Sum>i\<in>Basis. (u \<bullet> i) *\<^sub>R inv f i))"
immler@69611
  1984
          apply (simp add: linear_add linear_sum linear.scaleR \<open>linear f\<close> surj_f_inv_f \<open>surj f\<close>)
immler@69611
  1985
          apply (simp add: euclidean_representation u_def)
immler@69611
  1986
          done
immler@69611
  1987
        have "dist (x + (\<Sum>i\<in>Basis. (u \<bullet> i) *\<^sub>R inv f i)) x \<le> (\<Sum>i\<in>Basis. norm ((u \<bullet> i) *\<^sub>R inv f i))"
immler@69611
  1988
          by (simp add: dist_norm sum_norm_le)
immler@69611
  1989
        also have "... = (\<Sum>i\<in>Basis. \<bar>u \<bullet> i\<bar> * norm (inv f i))"
immler@69611
  1990
          by simp
immler@69611
  1991
        also have "... \<le> (\<Sum>i\<in>Basis. \<bar>u \<bullet> i\<bar>) * B"
immler@69611
  1992
          by (simp add: B sum_distrib_right sum_mono mult_left_mono)
immler@69611
  1993
        also have "... \<le> DIM('b) * dist y (f x) * B"
immler@69611
  1994
          apply (rule mult_right_mono [OF sum_bounded_above])
immler@69611
  1995
          using \<open>0 < B\<close> by (auto simp: Basis_le_norm dist_norm u_def)
immler@69611
  1996
        also have "... < e"
immler@69611
  1997
          by (metis mult.commute mult.left_commute that)
immler@69611
  1998
        finally show "x + (\<Sum>i\<in>Basis. (u \<bullet> i) *\<^sub>R inv f i) \<in> A"
immler@69611
  1999
          by (rule e)
immler@69611
  2000
      qed
immler@69611
  2001
    qed
immler@69611
  2002
    then show "\<forall>y. dist y (f x) < \<delta> \<longrightarrow> y \<in> f ` A"
immler@69611
  2003
      using \<open>e > 0\<close> \<open>B > 0\<close>
immler@69611
  2004
      by (auto simp: \<delta>_def divide_simps mult_less_0_iff)
immler@69611
  2005
  qed
immler@69611
  2006
qed
immler@69611
  2007
immler@69611
  2008
corollary open_bijective_linear_image_eq:
immler@69611
  2009
  fixes f :: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space"
immler@69611
  2010
  assumes "linear f" "bij f"
immler@69611
  2011
    shows "open(f ` A) \<longleftrightarrow> open A"
immler@69611
  2012
proof
immler@69611
  2013
  assume "open(f ` A)"
immler@69611
  2014
  then have "open(f -` (f ` A))"
immler@69611
  2015
    using assms by (force simp: linear_continuous_at linear_conv_bounded_linear continuous_open_vimage)
immler@69611
  2016
  then show "open A"
immler@69611
  2017
    by (simp add: assms bij_is_inj inj_vimage_image_eq)
immler@69611
  2018
next
immler@69611
  2019
  assume "open A"
immler@69611
  2020
  then show "open(f ` A)"
immler@69611
  2021
    by (simp add: assms bij_is_surj open_surjective_linear_image)
immler@69611
  2022
qed
immler@69611
  2023
immler@69611
  2024
corollary interior_bijective_linear_image:
immler@69611
  2025
  fixes f :: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space"
immler@69611
  2026
  assumes "linear f" "bij f"
immler@69611
  2027
  shows "interior (f ` S) = f ` interior S"  (is "?lhs = ?rhs")
immler@69611
  2028
proof safe
immler@69611
  2029
  fix x
immler@69611
  2030
  assume x: "x \<in> ?lhs"
immler@69611
  2031
  then obtain T where "open T" and "x \<in> T" and "T \<subseteq> f ` S"
immler@69611
  2032
    by (metis interiorE)
immler@69611
  2033
  then show "x \<in> ?rhs"
immler@69611
  2034
    by (metis (no_types, hide_lams) assms subsetD interior_maximal open_bijective_linear_image_eq subset_image_iff)
immler@69611
  2035
next
immler@69611
  2036
  fix x
immler@69611
  2037
  assume x: "x \<in> interior S"
immler@69611
  2038
  then show "f x \<in> interior (f ` S)"
immler@69611
  2039
    by (meson assms imageI image_mono interiorI interior_subset open_bijective_linear_image_eq open_interior)
immler@69611
  2040
qed
immler@69611
  2041
immler@69611
  2042
lemma interior_injective_linear_image:
immler@69611
  2043
  fixes f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
immler@69611
  2044
  assumes "linear f" "inj f"
immler@69611
  2045
   shows "interior(f ` S) = f ` (interior S)"
immler@69611
  2046
  by (simp add: linear_injective_imp_surjective assms bijI interior_bijective_linear_image)
immler@69611
  2047
immler@69611
  2048
lemma interior_surjective_linear_image:
immler@69611
  2049
  fixes f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
immler@69611
  2050
  assumes "linear f" "surj f"
immler@69611
  2051
   shows "interior(f ` S) = f ` (interior S)"
immler@69611
  2052
  by (simp add: assms interior_injective_linear_image linear_surjective_imp_injective)
immler@69611
  2053
immler@69611
  2054
lemma interior_negations:
immler@69611
  2055
  fixes S :: "'a::euclidean_space set"
immler@69611
  2056
  shows "interior(uminus ` S) = image uminus (interior S)"
immler@69611
  2057
  by (simp add: bij_uminus interior_bijective_linear_image linear_uminus)
immler@56189
  2058
immler@69617
  2059
lemma connected_linear_image:
immler@69617
  2060
  fixes f :: "'a::euclidean_space \<Rightarrow> 'b::real_normed_vector"
immler@69617
  2061
  assumes "linear f" and "connected s"
immler@69617
  2062
  shows "connected (f ` s)"
immler@69617
  2063
using connected_continuous_image assms linear_continuous_on linear_conv_bounded_linear by blast
immler@69617
  2064
immler@69617
  2065
immler@69613
  2066
subsection%unimportant \<open>"Isometry" (up to constant bounds) of Injective Linear Map\<close>
immler@69613
  2067
immler@69613
  2068
proposition injective_imp_isometric:
immler@69613
  2069
  fixes f :: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space"
immler@69613
  2070
  assumes s: "closed s" "subspace s"
immler@69613
  2071
    and f: "bounded_linear f" "\<forall>x\<in>s. f x = 0 \<longrightarrow> x = 0"
immler@69613
  2072
  shows "\<exists>e>0. \<forall>x\<in>s. norm (f x) \<ge> e * norm x"
immler@69613
  2073
proof (cases "s \<subseteq> {0::'a}")
immler@69613
  2074
  case True
immler@69613
  2075
  have "norm x \<le> norm (f x)" if "x \<in> s" for x
immler@69613
  2076
  proof -
immler@69613
  2077
    from True that have "x = 0" by auto
immler@69613
  2078
    then show ?thesis by simp
immler@69613
  2079
  qed
immler@69613
  2080
  then show ?thesis
immler@69613
  2081
    by (auto intro!: exI[where x=1])
immler@69613
  2082
next
immler@69613
  2083
  case False
immler@69613
  2084
  interpret f: bounded_linear f by fact
immler@69613
  2085
  from False obtain a where a: "a \<noteq> 0" "a \<in> s"
immler@69613
  2086
    by auto
immler@69613
  2087
  from False have "s \<noteq> {}"
immler@69613
  2088
    by auto
immler@69613
  2089
  let ?S = "{f x| x. x \<in> s \<and> norm x = norm a}"
immler@69613
  2090
  let ?S' = "{x::'a. x\<in>s \<and> norm x = norm a}"
immler@69613
  2091
  let ?S'' = "{x::'a. norm x = norm a}"
immler@69613
  2092
immler@69613
  2093
  have "?S'' = frontier (cball 0 (norm a))"
immler@69613
  2094
    by (simp add: sphere_def dist_norm)
immler@69613
  2095
  then have "compact ?S''" by (metis compact_cball compact_frontier)
immler@69613
  2096
  moreover have "?S' = s \<inter> ?S''" by auto
immler@69613
  2097
  ultimately have "compact ?S'"
immler@69613
  2098
    using closed_Int_compact[of s ?S''] using s(1) by auto
immler@69613
  2099
  moreover have *:"f ` ?S' = ?S" by auto
immler@69613
  2100
  ultimately have "compact ?S"
immler@69613
  2101
    using compact_continuous_image[OF linear_continuous_on[OF f(1)], of ?S'] by auto
immler@69613
  2102
  then have "closed ?S"
immler@69613
  2103
    using compact_imp_closed by auto
immler@69613
  2104
  moreover from a have "?S \<noteq> {}" by auto
immler@69613
  2105
  ultimately obtain b' where "b'\<in>?S" "\<forall>y\<in>?S. norm b' \<le> norm y"
immler@69613
  2106
    using distance_attains_inf[of ?S 0] unfolding dist_0_norm by auto
immler@69613
  2107
  then obtain b where "b\<in>s"
immler@69613
  2108
    and ba: "norm b = norm a"
immler@69613
  2109
    and b: "\<forall>x\<in>{x \<in> s. norm x = norm a}. norm (f b) \<le> norm (f x)"
immler@69613
  2110
    unfolding *[symmetric] unfolding image_iff by auto
immler@69613
  2111
immler@69613
  2112
  let ?e = "norm (f b) / norm b"
immler@69613
  2113
  have "norm b > 0"
immler@69613
  2114
    using ba and a and norm_ge_zero by auto
immler@69613
  2115
  moreover have "norm (f b) > 0"
immler@69613
  2116
    using f(2)[THEN bspec[where x=b], OF \<open>b\<in>s\<close>]
immler@69613
  2117
    using \<open>norm b >0\<close> by simp
immler@69613
  2118
  ultimately have "0 < norm (f b) / norm b" by simp
immler@69613
  2119
  moreover
immler@69613
  2120
  have "norm (f b) / norm b * norm x \<le> norm (f x)" if "x\<in>s" for x
immler@69613
  2121
  proof (cases "x = 0")
immler@69613
  2122
    case True
immler@69613
  2123
    then show "norm (f b) / norm b * norm x \<le> norm (f x)"
immler@69613
  2124
      by auto
immler@69613
  2125
  next
immler@69613
  2126
    case False
immler@69613
  2127
    with \<open>a \<noteq> 0\<close> have *: "0 < norm a / norm x"
immler@69613
  2128
      unfolding zero_less_norm_iff[symmetric] by simp
immler@69613
  2129
    have "\<forall>x\<in>s. c *\<^sub>R x \<in> s" for c
immler@69613
  2130
      using s[unfolded subspace_def] by simp
immler@69613
  2131
    with \<open>x \<in> s\<close> \<open>x \<noteq> 0\<close> have "(norm a / norm x) *\<^sub>R x \<in> {x \<in> s. norm x = norm a}"
immler@69613
  2132
      by simp
immler@69613
  2133
    with \<open>x \<noteq> 0\<close> \<open>a \<noteq> 0\<close> show "norm (f b) / norm b * norm x \<le> norm (f x)"
immler@69613
  2134
      using b[THEN bspec[where x="(norm a / norm x) *\<^sub>R x"]]
immler@69613
  2135
      unfolding f.scaleR and ba
immler@69613
  2136
      by (auto simp: mult.commute pos_le_divide_eq pos_divide_le_eq)
immler@69613
  2137
  qed
immler@69613
  2138
  ultimately show ?thesis by auto
immler@69613
  2139
qed
immler@69613
  2140
immler@69613
  2141
proposition closed_injective_image_subspace:
immler@69613
  2142
  fixes f :: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space"
immler@69613
  2143
  assumes "subspace s" "bounded_linear f" "\<forall>x\<in>s. f x = 0 \<longrightarrow> x = 0" "closed s"
immler@69613
  2144
  shows "closed(f ` s)"
immler@69613
  2145
proof -
immler@69613
  2146
  obtain e where "e > 0" and e: "\<forall>x\<in>s. e * norm x \<le> norm (f x)"
immler@69613
  2147
    using injective_imp_isometric[OF assms(4,1,2,3)] by auto
immler@69613
  2148
  show ?thesis
immler@69613
  2149
    using complete_isometric_image[OF \<open>e>0\<close> assms(1,2) e] and assms(4)
immler@69613
  2150
    unfolding complete_eq_closed[symmetric] by auto
immler@69613
  2151
qed
immler@69613
  2152
immler@69613
  2153
immler@69613
  2154
subsection%unimportant \<open>Some properties of a canonical subspace\<close>
immler@69613
  2155
immler@69613
  2156
lemma subspace_substandard: "subspace {x::'a::euclidean_space. (\<forall>i\<in>Basis. P i \<longrightarrow> x\<bullet>i = 0)}"
immler@69613
  2157
  by (auto simp: subspace_def inner_add_left)
immler@69613
  2158
immler@69613
  2159
lemma closed_substandard: "closed {x::'a::euclidean_space. \<forall>i\<in>Basis. P i \<longrightarrow> x\<bullet>i = 0}"
immler@69613
  2160
  (is "closed ?A")
immler@69613
  2161
proof -
immler@69613
  2162
  let ?D = "{i\<in>Basis. P i}"
immler@69613
  2163
  have "closed (\<Inter>i\<in>?D. {x::'a. x\<bullet>i = 0})"
immler@69613
  2164
    by (simp add: closed_INT closed_Collect_eq continuous_on_inner
immler@69613
  2165
        continuous_on_const continuous_on_id)
immler@69613
  2166
  also have "(\<Inter>i\<in>?D. {x::'a. x\<bullet>i = 0}) = ?A"
immler@69613
  2167
    by auto
immler@69613
  2168
  finally show "closed ?A" .
immler@69613
  2169
qed
immler@69613
  2170
immler@69613
  2171
lemma dim_substandard:
immler@69613
  2172
  assumes d: "d \<subseteq> Basis"
immler@69613
  2173
  shows "dim {x::'a::euclidean_space. \<forall>i\<in>Basis. i \<notin> d \<longrightarrow> x\<bullet>i = 0} = card d" (is "dim ?A = _")
immler@69613
  2174
proof (rule dim_unique)
immler@69613
  2175
  from d show "d \<subseteq> ?A"
immler@69613
  2176
    by (auto simp: inner_Basis)
immler@69613
  2177
  from d show "independent d"
immler@69613
  2178
    by (rule independent_mono [OF independent_Basis])
immler@69613
  2179
  have "x \<in> span d" if "\<forall>i\<in>Basis. i \<notin> d \<longrightarrow> x \<bullet> i = 0" for x
immler@69613
  2180
  proof -
immler@69613
  2181
    have "finite d"
immler@69613
  2182
      by (rule finite_subset [OF d finite_Basis])
immler@69613
  2183
    then have "(\<Sum>i\<in>d. (x \<bullet> i) *\<^sub>R i) \<in> span d"
immler@69613
  2184
      by (simp add: span_sum span_clauses)
immler@69613
  2185
    also have "(\<Sum>i\<in>d. (x \<bullet> i) *\<^sub>R i) = (\<Sum>i\<in>Basis. (x \<bullet> i) *\<^sub>R i)"
immler@69613
  2186
      by (rule sum.mono_neutral_cong_left [OF finite_Basis d]) (auto simp: that)
immler@69613
  2187
    finally show "x \<in> span d"
immler@69613
  2188
      by (simp only: euclidean_representation)
immler@69613
  2189
  qed
immler@69613
  2190
  then show "?A \<subseteq> span d" by auto
immler@69613
  2191
qed simp
immler@69613
  2192
immler@69613
  2193
text \<open>Hence closure and completeness of all subspaces.\<close>
immler@69613
  2194
lemma ex_card:
immler@69613
  2195
  assumes "n \<le> card A"
immler@69613
  2196
  shows "\<exists>S\<subseteq>A. card S = n"
immler@69613
  2197
proof (cases "finite A")
immler@69613
  2198
  case True
immler@69613
  2199
  from ex_bij_betw_nat_finite[OF this] obtain f where f: "bij_betw f {0..<card A} A" ..
immler@69613
  2200
  moreover from f \<open>n \<le> card A\<close> have "{..< n} \<subseteq> {..< card A}" "inj_on f {..< n}"
immler@69613
  2201
    by (auto simp: bij_betw_def intro: subset_inj_on)
immler@69613
  2202
  ultimately have "f ` {..< n} \<subseteq> A" "card (f ` {..< n}) = n"
immler@69613
  2203
    by (auto simp: bij_betw_def card_image)
immler@69613
  2204
  then show ?thesis by blast
immler@69613
  2205
next
immler@69613
  2206
  case False
immler@69613
  2207
  with \<open>n \<le> card A\<close> show ?thesis by force
immler@69613
  2208
qed
immler@69613
  2209
immler@69613
  2210
lemma closed_subspace:
immler@69613
  2211
  fixes s :: "'a::euclidean_space set"
immler@69613
  2212
  assumes "subspace s"
immler@69613
  2213
  shows "closed s"
immler@69613
  2214
proof -
immler@69613
  2215
  have "dim s \<le> card (Basis :: 'a set)"
immler@69613
  2216
    using dim_subset_UNIV by auto
immler@69613
  2217
  with ex_card[OF this] obtain d :: "'a set" where t: "card d = dim s" and d: "d \<subseteq> Basis"
immler@69613
  2218
    by auto
immler@69613
  2219
  let ?t = "{x::'a. \<forall>i\<in>Basis. i \<notin> d \<longrightarrow> x\<bullet>i = 0}"
immler@69613
  2220
  have "\<exists>f. linear f \<and> f ` {x::'a. \<forall>i\<in>Basis. i \<notin> d \<longrightarrow> x \<bullet> i = 0} = s \<and>
immler@69613
  2221
      inj_on f {x::'a. \<forall>i\<in>Basis. i \<notin> d \<longrightarrow> x \<bullet> i = 0}"
immler@69613
  2222
    using dim_substandard[of d] t d assms
immler@69613
  2223
    by (intro subspace_isomorphism[OF subspace_substandard[of "\<lambda>i. i \<notin> d"]]) (auto simp: inner_Basis)
immler@69613
  2224
  then obtain f where f:
immler@69613
  2225
      "linear f"
immler@69613
  2226
      "f ` {x. \<forall>i\<in>Basis. i \<notin> d \<longrightarrow> x \<bullet> i = 0} = s"
immler@69613
  2227
      "inj_on f {x. \<forall>i\<in>Basis. i \<notin> d \<longrightarrow> x \<bullet> i = 0}"
immler@69613
  2228
    by blast
immler@69613
  2229
  interpret f: bounded_linear f
immler@69613
  2230
    using f by (simp add: linear_conv_bounded_linear)
immler@69613
  2231
  have "x \<in> ?t \<Longrightarrow> f x = 0 \<Longrightarrow> x = 0" for x
immler@69613
  2232
    using f.zero d f(3)[THEN inj_onD, of x 0] by auto
immler@69613
  2233
  moreover have "closed ?t" by (rule closed_substandard)
immler@69613
  2234
  moreover have "subspace ?t" by (rule subspace_substandard)
immler@69613
  2235
  ultimately show ?thesis
immler@69613
  2236
    using closed_injective_image_subspace[of ?t f]
immler@69613
  2237
    unfolding f(2) using f(1) unfolding linear_conv_bounded_linear by auto
immler@69613
  2238
qed
immler@69613
  2239
immler@69613
  2240
lemma complete_subspace: "subspace s \<Longrightarrow> complete s"
immler@69613
  2241
  for s :: "'a::euclidean_space set"
immler@69613
  2242
  using complete_eq_closed closed_subspace by auto
immler@69613
  2243
immler@69613
  2244
lemma closed_span [iff]: "closed (span s)"
immler@69613
  2245
  for s :: "'a::euclidean_space set"
immler@69613
  2246
  by (simp add: closed_subspace subspace_span)
immler@69613
  2247
immler@69613
  2248
lemma dim_closure [simp]: "dim (closure s) = dim s" (is "?dc = ?d")
immler@69613
  2249
  for s :: "'a::euclidean_space set"
immler@69613
  2250
proof -
immler@69613
  2251
  have "?dc \<le> ?d"
immler@69613
  2252
    using closure_minimal[OF span_superset, of s]
immler@69613
  2253
    using closed_subspace[OF subspace_span, of s]
immler@69613
  2254
    using dim_subset[of "closure s" "span s"]
immler@69613
  2255
    by simp
immler@69613
  2256
  then show ?thesis
immler@69613
  2257
    using dim_subset[OF closure_subset, of s]
immler@69613
  2258
    by simp
immler@69613
  2259
qed
immler@69613
  2260
immler@69613
  2261
immler@54775
  2262
no_notation
immler@54775
  2263
  eucl_less (infix "<e" 50)
immler@54775
  2264
himmelma@33175
  2265
end