src/HOL/Analysis/Convex.thy
changeset 71240 67880e7ee08d
parent 71174 7fac205dd737
child 71242 ec5090faf541
equal deleted inserted replaced
71237:da73ee760643 71240:67880e7ee08d
  2885     apply (rule exI[of _ "int (card B) - (1 :: int)"])
  2885     apply (rule exI[of _ "int (card B) - (1 :: int)"])
  2886     apply (rule exI[of _ "B"], auto)
  2886     apply (rule exI[of _ "B"], auto)
  2887     done
  2887     done
  2888 qed
  2888 qed
  2889 
  2889 
  2890 lemma affine_hull_nonempty: "S \<noteq> {} \<longleftrightarrow> affine hull S \<noteq> {}"
  2890 lemma affine_hull_eq_empty [simp]: "affine hull S = {} \<longleftrightarrow> S = {}"
  2891 proof -
  2891 by (metis affine_empty subset_empty subset_hull)
  2892   have "S = {} \<Longrightarrow> affine hull S = {}"
  2892 
  2893     using affine_hull_empty by auto
  2893 lemma empty_eq_affine_hull[simp]: "{} = affine hull S \<longleftrightarrow> S = {}"
  2894   moreover have "affine hull S = {} \<Longrightarrow> S = {}"
  2894 by (metis affine_hull_eq_empty)
  2895     unfolding hull_def by auto
       
  2896   ultimately show ?thesis by blast
       
  2897 qed
       
  2898 
  2895 
  2899 lemma aff_dim_parallel_subspace_aux:
  2896 lemma aff_dim_parallel_subspace_aux:
  2900   fixes B :: "'n::euclidean_space set"
  2897   fixes B :: "'n::euclidean_space set"
  2901   assumes "\<not> affine_dependent B" "a \<in> B"
  2898   assumes "\<not> affine_dependent B" "a \<in> B"
  2902   shows "finite B \<and> ((card B) - 1 = dim (span ((\<lambda>x. -a+x) ` (B-{a}))))"
  2899   shows "finite B \<and> ((card B) - 1 = dim (span ((\<lambda>x. -a+x) ` (B-{a}))))"
  2937 proof -
  2934 proof -
  2938   obtain B where
  2935   obtain B where
  2939     B: "affine hull B = affine hull V \<and> \<not> affine_dependent B \<and> int (card B) = aff_dim V + 1"
  2936     B: "affine hull B = affine hull V \<and> \<not> affine_dependent B \<and> int (card B) = aff_dim V + 1"
  2940     using aff_dim_basis_exists by auto
  2937     using aff_dim_basis_exists by auto
  2941   then have "B \<noteq> {}"
  2938   then have "B \<noteq> {}"
  2942     using assms B affine_hull_nonempty[of V] affine_hull_nonempty[of B]
  2939     using assms B
  2943     by auto
  2940     by auto
  2944   then obtain a where a: "a \<in> B" by auto
  2941   then obtain a where a: "a \<in> B" by auto
  2945   define Lb where "Lb = span ((\<lambda>x. -a+x) ` (B-{a}))"
  2942   define Lb where "Lb = span ((\<lambda>x. -a+x) ` (B-{a}))"
  2946   moreover have "affine_parallel (affine hull B) Lb"
  2943   moreover have "affine_parallel (affine hull B) Lb"
  2947     using Lb_def B assms affine_hull_span2[of a B] a
  2944     using Lb_def B assms affine_hull_span2[of a B] a
  2949     unfolding affine_parallel_def
  2946     unfolding affine_parallel_def
  2950     by auto
  2947     by auto
  2951   moreover have "subspace Lb"
  2948   moreover have "subspace Lb"
  2952     using Lb_def subspace_span by auto
  2949     using Lb_def subspace_span by auto
  2953   moreover have "affine hull B \<noteq> {}"
  2950   moreover have "affine hull B \<noteq> {}"
  2954     using assms B affine_hull_nonempty[of V] by auto
  2951     using assms B by auto
  2955   ultimately have "L = Lb"
  2952   ultimately have "L = Lb"
  2956     using assms affine_parallel_subspace[of "affine hull B"] affine_affine_hull[of B] B
  2953     using assms affine_parallel_subspace[of "affine hull B"] affine_affine_hull[of B] B
  2957     by auto
  2954     by auto
  2958   then have "dim L = dim Lb"
  2955   then have "dim L = dim Lb"
  2959     by auto
  2956     by auto
  3029     and "\<not> affine_dependent B"
  3026     and "\<not> affine_dependent B"
  3030     and "int (card B) = aff_dim S + 1"
  3027     and "int (card B) = aff_dim S + 1"
  3031     using aff_dim_basis_exists by auto
  3028     using aff_dim_basis_exists by auto
  3032   moreover
  3029   moreover
  3033   from * have "S = {} \<longleftrightarrow> B = {}"
  3030   from * have "S = {} \<longleftrightarrow> B = {}"
  3034     using affine_hull_nonempty[of B] affine_hull_nonempty[of S] by auto
  3031     by auto
  3035   ultimately show ?thesis
  3032   ultimately show ?thesis
  3036     using aff_independent_finite[of B] card_gt_0_iff[of B] by auto
  3033     using aff_independent_finite[of B] card_gt_0_iff[of B] by auto
  3037 qed
  3034 qed
  3038 
  3035 
  3039 lemma aff_dim_empty_eq [simp]: "aff_dim ({}::'a::euclidean_space set) = -1"
  3036 lemma aff_dim_empty_eq [simp]: "aff_dim ({}::'a::euclidean_space set) = -1"
  3052   assumes "affine hull B = affine hull V \<and> \<not> affine_dependent B"
  3049   assumes "affine hull B = affine hull V \<and> \<not> affine_dependent B"
  3053   shows "of_nat (card B) = aff_dim V + 1"
  3050   shows "of_nat (card B) = aff_dim V + 1"
  3054 proof (cases "B = {}")
  3051 proof (cases "B = {}")
  3055   case True
  3052   case True
  3056   then have "V = {}"
  3053   then have "V = {}"
  3057     using affine_hull_nonempty[of V] affine_hull_nonempty[of B] assms
  3054     using assms
  3058     by auto
  3055     by auto
  3059   then have "aff_dim V = (-1::int)"
  3056   then have "aff_dim V = (-1::int)"
  3060     using aff_dim_empty by auto
  3057     using aff_dim_empty by auto
  3061   then show ?thesis
  3058   then show ?thesis
  3062     using \<open>B = {}\<close> by auto
  3059     using \<open>B = {}\<close> by auto
  3138 proof -
  3135 proof -
  3139   {
  3136   {
  3140     assume "T \<noteq> {}" "S \<noteq> {}"
  3137     assume "T \<noteq> {}" "S \<noteq> {}"
  3141     then obtain L where L: "subspace L \<and> affine_parallel (affine hull T) L"
  3138     then obtain L where L: "subspace L \<and> affine_parallel (affine hull T) L"
  3142       using affine_parallel_subspace[of "affine hull T"]
  3139       using affine_parallel_subspace[of "affine hull T"]
  3143         affine_affine_hull[of T] affine_hull_nonempty
  3140         affine_affine_hull[of T]
  3144       by auto
  3141       by auto
  3145     then have "aff_dim T = int (dim L)"
  3142     then have "aff_dim T = int (dim L)"
  3146       using aff_dim_parallel_subspace \<open>T \<noteq> {}\<close> by auto
  3143       using aff_dim_parallel_subspace \<open>T \<noteq> {}\<close> by auto
  3147     moreover have *: "subspace L \<and> affine_parallel (affine hull S) L"
  3144     moreover have *: "subspace L \<and> affine_parallel (affine hull S) L"
  3148        using L affine_parallel_assoc[of "affine hull S" "affine hull T" L] assms by auto
  3145        using L affine_parallel_assoc[of "affine hull S" "affine hull T" L] assms by auto
  3152   }
  3149   }
  3153   moreover
  3150   moreover
  3154   {
  3151   {
  3155     assume "S = {}"
  3152     assume "S = {}"
  3156     then have "S = {}" and "T = {}"
  3153     then have "S = {}" and "T = {}"
  3157       using assms affine_hull_nonempty
  3154       using assms
  3158       unfolding affine_parallel_def
  3155       unfolding affine_parallel_def
  3159       by auto
  3156       by auto
  3160     then have ?thesis using aff_dim_empty by auto
  3157     then have ?thesis using aff_dim_empty by auto
  3161   }
  3158   }
  3162   moreover
  3159   moreover
  3163   {
  3160   {
  3164     assume "T = {}"
  3161     assume "T = {}"
  3165     then have "S = {}" and "T = {}"
  3162     then have "S = {}" and "T = {}"
  3166       using assms affine_hull_nonempty
  3163       using assms
  3167       unfolding affine_parallel_def
  3164       unfolding affine_parallel_def
  3168       by auto
  3165       by auto
  3169     then have ?thesis
  3166     then have ?thesis
  3170       using aff_dim_empty by auto
  3167       using aff_dim_empty by auto
  3171   }
  3168   }