src/HOL/Multivariate_Analysis/Convex_Euclidean_Space.thy
changeset 37647 a5400b94d2dd
parent 37489 44e42d392c6e
child 37673 f69f4b079275
equal deleted inserted replaced
37646:dbdbebec57df 37647:a5400b94d2dd
    56 
    56 
    57 lemma norm_minus_eqI:"x = - y \<Longrightarrow> norm x = norm y" by auto
    57 lemma norm_minus_eqI:"x = - y \<Longrightarrow> norm x = norm y" by auto
    58 
    58 
    59 lemma Min_grI: assumes "finite A" "A \<noteq> {}" "\<forall>a\<in>A. x < a" shows "x < Min A"
    59 lemma Min_grI: assumes "finite A" "A \<noteq> {}" "\<forall>a\<in>A. x < a" shows "x < Min A"
    60   unfolding Min_gr_iff[OF assms(1,2)] using assms(3) by auto
    60   unfolding Min_gr_iff[OF assms(1,2)] using assms(3) by auto
    61 
       
    62 lemma dimindex_ge_1:"CARD(_::finite) \<ge> 1"
       
    63   using one_le_card_finite by auto
       
    64 
    61 
    65 lemma norm_lt: "norm x < norm y \<longleftrightarrow> inner x x < inner y y"
    62 lemma norm_lt: "norm x < norm y \<longleftrightarrow> inner x x < inner y y"
    66   unfolding norm_eq_sqrt_inner by simp
    63   unfolding norm_eq_sqrt_inner by simp
    67 
    64 
    68 lemma norm_le: "norm x \<le> norm y \<longleftrightarrow> inner x x \<le> inner y y"
    65 lemma norm_le: "norm x \<le> norm y \<longleftrightarrow> inner x x \<le> inner y y"
  1646       thus "x\<in>\<Inter>h" using X[THEN bspec[where x=y]] using * f by auto next
  1643       thus "x\<in>\<Inter>h" using X[THEN bspec[where x=y]] using * f by auto next
  1647       fix x assume "x\<in>X ` h" then guess y unfolding image_iff ..
  1644       fix x assume "x\<in>X ` h" then guess y unfolding image_iff ..
  1648       thus "x\<in>\<Inter>g" using X[THEN bspec[where x=y]] using * f by auto
  1645       thus "x\<in>\<Inter>g" using X[THEN bspec[where x=y]] using * f by auto
  1649     qed(auto)
  1646     qed(auto)
  1650     thus ?thesis unfolding f using mp(3)[unfolded gh] by blast qed
  1647     thus ?thesis unfolding f using mp(3)[unfolded gh] by blast qed
  1651 qed(insert dimindex_ge_1, auto) qed(auto)
  1648 qed(auto) qed(auto)
  1652 
  1649 
  1653 lemma helly: fixes f::"('a::euclidean_space) set set"
  1650 lemma helly: fixes f::"('a::euclidean_space) set set"
  1654   assumes "card f \<ge> DIM('a) + 1" "\<forall>s\<in>f. convex s"
  1651   assumes "card f \<ge> DIM('a) + 1" "\<forall>s\<in>f. convex s"
  1655           "\<forall>t\<subseteq>f. card t = DIM('a) + 1 \<longrightarrow> \<Inter> t \<noteq> {}"
  1652           "\<forall>t\<subseteq>f. card t = DIM('a) + 1 \<longrightarrow> \<Inter> t \<noteq> {}"
  1656   shows "\<Inter> f \<noteq>{}"
  1653   shows "\<Inter> f \<noteq>{}"
  2225   let ?d = "(\<chi>\<chi> i. d)::'a"
  2222   let ?d = "(\<chi>\<chi> i. d)::'a"
  2226   obtain c where c:"finite c" "{x - ?d..x + ?d} = convex hull c" using cube_convex_hull[OF `d>0`, of x] by auto
  2223   obtain c where c:"finite c" "{x - ?d..x + ?d} = convex hull c" using cube_convex_hull[OF `d>0`, of x] by auto
  2227   have "x\<in>{x - ?d..x + ?d}" using `d>0` unfolding mem_interval by(auto simp add:euclidean_simps)
  2224   have "x\<in>{x - ?d..x + ?d}" using `d>0` unfolding mem_interval by(auto simp add:euclidean_simps)
  2228   hence "c\<noteq>{}" using c by auto
  2225   hence "c\<noteq>{}" using c by auto
  2229   def k \<equiv> "Max (f ` c)"
  2226   def k \<equiv> "Max (f ` c)"
  2230   have real_dimindex_ge_1:"real (CARD('n::finite)) \<ge> 1" 
       
  2231     by(metis dimindex_ge_1 real_eq_of_nat real_of_nat_1 real_of_nat_le_iff) 
       
  2232   have "convex_on {x - ?d..x + ?d} f" apply(rule convex_on_subset[OF assms(2)])
  2227   have "convex_on {x - ?d..x + ?d} f" apply(rule convex_on_subset[OF assms(2)])
  2233     apply(rule subset_trans[OF _ e(1)]) unfolding subset_eq mem_cball proof 
  2228     apply(rule subset_trans[OF _ e(1)]) unfolding subset_eq mem_cball proof 
  2234     fix z assume z:"z\<in>{x - ?d..x + ?d}"
  2229     fix z assume z:"z\<in>{x - ?d..x + ?d}"
  2235     have e:"e = setsum (\<lambda>i. d) {..<DIM('a)}" unfolding setsum_constant d_def using dimge1
  2230     have e:"e = setsum (\<lambda>i. d) {..<DIM('a)}" unfolding setsum_constant d_def using dimge1
  2236       unfolding real_eq_of_nat by auto
  2231       unfolding real_eq_of_nat by auto
  2237     show "dist x z \<le> e" unfolding dist_norm e apply(rule_tac order_trans[OF norm_le_l1], rule setsum_mono)
  2232     show "dist x z \<le> e" unfolding dist_norm e apply(rule_tac order_trans[OF norm_le_l1], rule setsum_mono)
  2238       using z[unfolded mem_interval] apply(erule_tac x=i in allE) by(auto simp add:euclidean_simps) qed
  2233       using z[unfolded mem_interval] apply(erule_tac x=i in allE) by(auto simp add:euclidean_simps) qed
  2239   hence k:"\<forall>y\<in>{x - ?d..x + ?d}. f y \<le> k" unfolding c(2) apply(rule_tac convex_on_convex_hull_bound) apply assumption
  2234   hence k:"\<forall>y\<in>{x - ?d..x + ?d}. f y \<le> k" unfolding c(2) apply(rule_tac convex_on_convex_hull_bound) apply assumption
  2240     unfolding k_def apply(rule, rule Max_ge) using c(1) by auto
  2235     unfolding k_def apply(rule, rule Max_ge) using c(1) by auto
  2241   have "d \<le> e" unfolding d_def apply(rule mult_imp_div_pos_le) using `e>0` dimge1 unfolding mult_le_cancel_left1 using real_dimindex_ge_1 by auto
  2236   have "d \<le> e" unfolding d_def apply(rule mult_imp_div_pos_le) using `e>0` dimge1 unfolding mult_le_cancel_left1 by auto
  2242   hence dsube:"cball x d \<subseteq> cball x e" unfolding subset_eq Ball_def mem_cball by auto
  2237   hence dsube:"cball x d \<subseteq> cball x e" unfolding subset_eq Ball_def mem_cball by auto
  2243   have conv:"convex_on (cball x d) f" apply(rule convex_on_subset, rule convex_on_subset[OF assms(2)]) apply(rule e(1)) using dsube by auto
  2238   have conv:"convex_on (cball x d) f" apply(rule convex_on_subset, rule convex_on_subset[OF assms(2)]) apply(rule e(1)) using dsube by auto
  2244   hence "\<forall>y\<in>cball x d. abs (f y) \<le> k + 2 * abs (f x)" apply(rule_tac convex_bounds_lemma) apply assumption proof
  2239   hence "\<forall>y\<in>cball x d. abs (f y) \<le> k + 2 * abs (f x)" apply(rule_tac convex_bounds_lemma) apply assumption proof
  2245     fix y assume y:"y\<in>cball x d"
  2240     fix y assume y:"y\<in>cball x d"
  2246     { fix i assume "i<DIM('a)" hence "x $$ i - d \<le> y $$ i"  "y $$ i \<le> x $$ i + d" 
  2241     { fix i assume "i<DIM('a)" hence "x $$ i - d \<le> y $$ i"  "y $$ i \<le> x $$ i + d" 
  2517     finally show "setsum (op $$ x) {..<DIM('a)} < 1" by auto qed
  2512     finally show "setsum (op $$ x) {..<DIM('a)} < 1" by auto qed
  2518 next fix x::"'a" assume as:"\<forall>i<DIM('a). 0 < x $$ i" "setsum (op $$ x) {..<DIM('a)} < 1"
  2513 next fix x::"'a" assume as:"\<forall>i<DIM('a). 0 < x $$ i" "setsum (op $$ x) {..<DIM('a)} < 1"
  2519   guess a using UNIV_witness[where 'a='b] ..
  2514   guess a using UNIV_witness[where 'a='b] ..
  2520   let ?d = "(1 - setsum (op $$ x) {..<DIM('a)}) / real (DIM('a))"
  2515   let ?d = "(1 - setsum (op $$ x) {..<DIM('a)}) / real (DIM('a))"
  2521   have "Min ((op $$ x) ` {..<DIM('a)}) > 0" apply(rule Min_grI) using as(1) by auto
  2516   have "Min ((op $$ x) ` {..<DIM('a)}) > 0" apply(rule Min_grI) using as(1) by auto
  2522   moreover have"?d > 0" apply(rule divide_pos_pos) using as(2) using dimindex_ge_1 by(auto simp add: Suc_le_eq)
  2517   moreover have"?d > 0" apply(rule divide_pos_pos) using as(2) by(auto simp add: Suc_le_eq)
  2523   ultimately show "\<exists>e>0. \<forall>y. dist x y < e \<longrightarrow> (\<forall>i<DIM('a). 0 \<le> y $$ i) \<and> setsum (op $$ y) {..<DIM('a)} \<le> 1"
  2518   ultimately show "\<exists>e>0. \<forall>y. dist x y < e \<longrightarrow> (\<forall>i<DIM('a). 0 \<le> y $$ i) \<and> setsum (op $$ y) {..<DIM('a)} \<le> 1"
  2524     apply(rule_tac x="min (Min ((op $$ x) ` {..<DIM('a)})) ?D" in exI) apply rule defer apply(rule,rule) proof-
  2519     apply(rule_tac x="min (Min ((op $$ x) ` {..<DIM('a)})) ?D" in exI) apply rule defer apply(rule,rule) proof-
  2525     fix y assume y:"dist x y < min (Min (op $$ x ` {..<DIM('a)})) ?d"
  2520     fix y assume y:"dist x y < min (Min (op $$ x ` {..<DIM('a)})) ?d"
  2526     have "setsum (op $$ y) {..<DIM('a)} \<le> setsum (\<lambda>i. x$$i + ?d) {..<DIM('a)}" proof(rule setsum_mono)
  2521     have "setsum (op $$ y) {..<DIM('a)} \<le> setsum (\<lambda>i. x$$i + ?d) {..<DIM('a)}" proof(rule setsum_mono)
  2527       fix i assume "i\<in>{..<DIM('a)}" hence "abs (y$$i - x$$i) < ?d" apply-apply(rule le_less_trans)
  2522       fix i assume "i\<in>{..<DIM('a)}" hence "abs (y$$i - x$$i) < ?d" apply-apply(rule le_less_trans)
  2528         using component_le_norm[of "y - x" i]
  2523         using component_le_norm[of "y - x" i]
  2529         using y[unfolded min_less_iff_conj dist_norm, THEN conjunct2] by(auto simp add: norm_minus_commute)
  2524         using y[unfolded min_less_iff_conj dist_norm, THEN conjunct2] by(auto simp add: norm_minus_commute)
  2530       thus "y $$ i \<le> x $$ i + ?d" by auto qed
  2525       thus "y $$ i \<le> x $$ i + ?d" by auto qed
  2531     also have "\<dots> \<le> 1" unfolding setsum_addf setsum_constant card_enum real_eq_of_nat using dimindex_ge_1 by(auto simp add: Suc_le_eq)
  2526     also have "\<dots> \<le> 1" unfolding setsum_addf setsum_constant card_enum real_eq_of_nat by(auto simp add: Suc_le_eq)
  2532     finally show "(\<forall>i<DIM('a). 0 \<le> y $$ i) \<and> setsum (op $$ y) {..<DIM('a)} \<le> 1" 
  2527     finally show "(\<forall>i<DIM('a). 0 \<le> y $$ i) \<and> setsum (op $$ y) {..<DIM('a)} \<le> 1" 
  2533     proof safe fix i assume i:"i<DIM('a)"
  2528     proof safe fix i assume i:"i<DIM('a)"
  2534       have "norm (x - y) < x$$i" apply(rule less_le_trans) 
  2529       have "norm (x - y) < x$$i" apply(rule less_le_trans) 
  2535         apply(rule y[unfolded min_less_iff_conj dist_norm, THEN conjunct1]) using i by auto
  2530         apply(rule y[unfolded min_less_iff_conj dist_norm, THEN conjunct1]) using i by auto
  2536       thus "0 \<le> y$$i" using component_le_norm[of "x - y" i] and as(1)[rule_format, of i] by auto
  2531       thus "0 \<le> y$$i" using component_le_norm[of "x - y" i] and as(1)[rule_format, of i] by auto