src/HOL/Analysis/Convex_Euclidean_Space.thy
changeset 68069 36209dfb981e
parent 68058 69715dfdc286
child 68073 fad29d2a17a5
equal deleted inserted replaced
68065:d2daeef3ce47 68069:36209dfb981e
  3247 proof -
  3247 proof -
  3248   obtain a where a: "a \<in> S"
  3248   obtain a where a: "a \<in> S"
  3249     using assms by auto
  3249     using assms by auto
  3250   then have h0: "independent  ((\<lambda>x. -a + x) ` (S-{a}))"
  3250   then have h0: "independent  ((\<lambda>x. -a + x) ` (S-{a}))"
  3251     using affine_dependent_iff_dependent2 assms by auto
  3251     using affine_dependent_iff_dependent2 assms by auto
  3252   then obtain B where B:
  3252   obtain B where B:
  3253     "(\<lambda>x. -a+x) ` (S - {a}) \<subseteq> B \<and> B \<subseteq> (\<lambda>x. -a+x) ` V \<and> independent B \<and> (\<lambda>x. -a+x) ` V \<subseteq> span B"
  3253     "(\<lambda>x. -a+x) ` (S - {a}) \<subseteq> B \<and> B \<subseteq> (\<lambda>x. -a+x) ` V \<and> independent B \<and> (\<lambda>x. -a+x) ` V \<subseteq> span B"
  3254      using maximal_independent_subset_extend[of "(\<lambda>x. -a+x) ` (S-{a})" "(\<lambda>x. -a + x) ` V"] assms
  3254     using assms
  3255      by blast
  3255     by (blast intro: maximal_independent_subset_extend[OF _ h0, of "(\<lambda>x. -a + x) ` V"])
  3256   define T where "T = (\<lambda>x. a+x) ` insert 0 B"
  3256   define T where "T = (\<lambda>x. a+x) ` insert 0 B"
  3257   then have "T = insert a ((\<lambda>x. a+x) ` B)"
  3257   then have "T = insert a ((\<lambda>x. a+x) ` B)"
  3258     by auto
  3258     by auto
  3259   then have "affine hull T = (\<lambda>x. a+x) ` span B"
  3259   then have "affine hull T = (\<lambda>x. a+x) ` span B"
  3260     using affine_hull_insert_span_gen[of a "((\<lambda>x. a+x) ` B)"] translation_assoc[of "-a" a B]
  3260     using affine_hull_insert_span_gen[of a "((\<lambda>x. a+x) ` B)"] translation_assoc[of "-a" a B]
  3355   next
  3355   next
  3356     case False
  3356     case False
  3357     then have "card ((\<lambda>x. -a + x) ` (B - {a})) > 0"
  3357     then have "card ((\<lambda>x. -a + x) ` (B - {a})) > 0"
  3358       using fin by auto
  3358       using fin by auto
  3359     moreover have h1: "card ((\<lambda>x. -a + x) ` (B-{a})) = card (B-{a})"
  3359     moreover have h1: "card ((\<lambda>x. -a + x) ` (B-{a})) = card (B-{a})"
  3360        apply (rule card_image)
  3360       by (rule card_image) (use translate_inj_on in blast)
  3361        using translate_inj_on
       
  3362        apply (auto simp del: uminus_add_conv_diff)
       
  3363        done
       
  3364     ultimately have "card (B-{a}) > 0" by auto
  3361     ultimately have "card (B-{a}) > 0" by auto
  3365     then have *: "finite (B - {a})"
  3362     then have *: "finite (B - {a})"
  3366       using card_gt_0_iff[of "(B - {a})"] by auto
  3363       using card_gt_0_iff[of "(B - {a})"] by auto
  3367     then have "card (B - {a}) = card B - 1"
  3364     then have "card (B - {a}) = card B - 1"
  3368       using card_Diff_singleton assms by auto
  3365       using card_Diff_singleton assms by auto
  3432     and "S \<subseteq> T"
  3429     and "S \<subseteq> T"
  3433     and "dim S \<ge> dim T"
  3430     and "dim S \<ge> dim T"
  3434   shows "S = T"
  3431   shows "S = T"
  3435 proof -
  3432 proof -
  3436   obtain B where B: "B \<le> S" "independent B \<and> S \<subseteq> span B" "card B = dim S"
  3433   obtain B where B: "B \<le> S" "independent B \<and> S \<subseteq> span B" "card B = dim S"
  3437     using basis_exists[of S] by auto
  3434     using basis_exists[of S] by metis
  3438   then have "span B \<subseteq> S"
  3435   then have "span B \<subseteq> S"
  3439     using span_mono[of B S] span_eq[of S] assms by metis
  3436     using span_mono[of B S] span_eq[of S] assms by metis
  3440   then have "span B = S"
  3437   then have "span B = S"
  3441     using B by auto
  3438     using B by auto
  3442   have "dim S = dim T"
  3439   have "dim S = dim T"
  3448 qed
  3445 qed
  3449 
  3446 
  3450 corollary dim_eq_span:
  3447 corollary dim_eq_span:
  3451   fixes S :: "'a::euclidean_space set"
  3448   fixes S :: "'a::euclidean_space set"
  3452   shows "\<lbrakk>S \<subseteq> T; dim T \<le> dim S\<rbrakk> \<Longrightarrow> span S = span T"
  3449   shows "\<lbrakk>S \<subseteq> T; dim T \<le> dim S\<rbrakk> \<Longrightarrow> span S = span T"
  3453 by (simp add: span_mono subspace_dim_equal subspace_span)
  3450 by (simp add: span_mono subspace_dim_equal)
  3454 
  3451 
  3455 lemma dim_eq_full:
  3452 lemma dim_eq_full:
  3456     fixes S :: "'a :: euclidean_space set"
  3453     fixes S :: "'a :: euclidean_space set"
  3457     shows "dim S = DIM('a) \<longleftrightarrow> span S = UNIV"
  3454     shows "dim S = DIM('a) \<longleftrightarrow> span S = UNIV"
  3458 apply (rule iffI)
  3455 apply (rule iffI)
  6816       done
  6813       done
  6817   qed
  6814   qed
  6818   define k where "k = Max (f ` c)"
  6815   define k where "k = Max (f ` c)"
  6819   have "convex_on (convex hull c) f"
  6816   have "convex_on (convex hull c) f"
  6820     apply(rule convex_on_subset[OF assms(2)])
  6817     apply(rule convex_on_subset[OF assms(2)])
  6821     apply(rule subset_trans[OF _ e(1)])
  6818     apply(rule subset_trans[OF c1 e(1)])
  6822     apply(rule c1)
       
  6823     done
  6819     done
  6824   then have k: "\<forall>y\<in>convex hull c. f y \<le> k"
  6820   then have k: "\<forall>y\<in>convex hull c. f y \<le> k"
  6825     apply (rule_tac convex_on_convex_hull_bound, assumption)
  6821     apply (rule_tac convex_on_convex_hull_bound, assumption)
  6826     by (simp add: k_def c)
  6822     by (simp add: k_def c)
  6827   have "e \<le> e * real DIM('a)"
  6823   have "e \<le> e * real DIM('a)"