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 |