src/HOL/Analysis/Convex_Euclidean_Space.thy
changeset 69508 2a4c8a2a3f8e
parent 69260 0a9688695a1b
child 69510 0f31dd2e540d
equal deleted inserted replaced
69506:7d59af98af29 69508:2a4c8a2a3f8e
  1341 
  1341 
  1342 lemma affine_hyperplane: "affine {x. a \<bullet> x = b}"
  1342 lemma affine_hyperplane: "affine {x. a \<bullet> x = b}"
  1343   by (simp add: affine_def algebra_simps) (metis distrib_right mult.left_neutral)
  1343   by (simp add: affine_def algebra_simps) (metis distrib_right mult.left_neutral)
  1344 
  1344 
  1345 
  1345 
  1346 subsubsection%unimportant \<open>Some explicit formulations (from Lars Schewe)\<close>
  1346 subsubsection%unimportant \<open>Some explicit formulations\<close>
       
  1347 
       
  1348 text "Formalized by Lars Schewe."
  1347 
  1349 
  1348 lemma affine:
  1350 lemma affine:
  1349   fixes V::"'a::real_vector set"
  1351   fixes V::"'a::real_vector set"
  1350   shows "affine V \<longleftrightarrow>
  1352   shows "affine V \<longleftrightarrow>
  1351          (\<forall>S u. finite S \<and> S \<noteq> {} \<and> S \<subseteq> V \<and> sum u S = 1 \<longrightarrow> (\<Sum>x\<in>S. u x *\<^sub>R x) \<in> V)"
  1353          (\<forall>S u. finite S \<and> S \<noteq> {} \<and> S \<subseteq> V \<and> sum u S = 1 \<longrightarrow> (\<Sum>x\<in>S. u x *\<^sub>R x) \<in> V)"
  2068   then show ?thesis
  2070   then show ?thesis
  2069     using False cone_iff[of "closure S"] by auto
  2071     using False cone_iff[of "closure S"] by auto
  2070 qed
  2072 qed
  2071 
  2073 
  2072 
  2074 
  2073 subsection \<open>Affine dependence and consequential theorems (from Lars Schewe)\<close>
  2075 subsection \<open>Affine dependence and consequential theorems\<close>
       
  2076 
       
  2077 text "Formalized by Lars Schewe."
  2074 
  2078 
  2075 definition%important affine_dependent :: "'a::real_vector set \<Rightarrow> bool"
  2079 definition%important affine_dependent :: "'a::real_vector set \<Rightarrow> bool"
  2076   where "affine_dependent s \<longleftrightarrow> (\<exists>x\<in>s. x \<in> affine hull (s - {x}))"
  2080   where "affine_dependent s \<longleftrightarrow> (\<exists>x\<in>s. x \<in> affine hull (s - {x}))"
  2077 
  2081 
  2078 lemma affine_dependent_subset:
  2082 lemma affine_dependent_subset:
  2080 apply (simp add: affine_dependent_def Bex_def)
  2084 apply (simp add: affine_dependent_def Bex_def)
  2081 apply (blast dest: hull_mono [OF Diff_mono [OF _ subset_refl]])
  2085 apply (blast dest: hull_mono [OF Diff_mono [OF _ subset_refl]])
  2082 done
  2086 done
  2083 
  2087 
  2084 lemma affine_independent_subset:
  2088 lemma affine_independent_subset:
  2085   shows "\<lbrakk>~ affine_dependent t; s \<subseteq> t\<rbrakk> \<Longrightarrow> ~ affine_dependent s"
  2089   shows "\<lbrakk>\<not> affine_dependent t; s \<subseteq> t\<rbrakk> \<Longrightarrow> \<not> affine_dependent s"
  2086 by (metis affine_dependent_subset)
  2090 by (metis affine_dependent_subset)
  2087 
  2091 
  2088 lemma affine_independent_Diff:
  2092 lemma affine_independent_Diff:
  2089    "~ affine_dependent s \<Longrightarrow> ~ affine_dependent(s - t)"
  2093    "\<not> affine_dependent s \<Longrightarrow> \<not> affine_dependent(s - t)"
  2090 by (meson Diff_subset affine_dependent_subset)
  2094 by (meson Diff_subset affine_dependent_subset)
  2091 
  2095 
  2092 proposition affine_dependent_explicit:
  2096 proposition affine_dependent_explicit:
  2093   "affine_dependent p \<longleftrightarrow>
  2097   "affine_dependent p \<longleftrightarrow>
  2094     (\<exists>S u. finite S \<and> S \<subseteq> p \<and> sum u S = 0 \<and> (\<exists>v\<in>S. u v \<noteq> 0) \<and> sum (\<lambda>v. u v *\<^sub>R v) S = 0)"
  2098     (\<exists>S u. finite S \<and> S \<subseteq> p \<and> sum u S = 0 \<and> (\<exists>v\<in>S. u v \<noteq> 0) \<and> sum (\<lambda>v. u v *\<^sub>R v) S = 0)"
  2599              (\<Sum>x\<in>S. uc x *\<^sub>R x) = u *\<^sub>R (\<Sum>x\<in>S. ux x *\<^sub>R x) + v *\<^sub>R (\<Sum>x\<in>S. uy x *\<^sub>R x)"
  2603              (\<Sum>x\<in>S. uc x *\<^sub>R x) = u *\<^sub>R (\<Sum>x\<in>S. ux x *\<^sub>R x) + v *\<^sub>R (\<Sum>x\<in>S. uy x *\<^sub>R x)"
  2600     by (rule_tac x="\<lambda>x. u * ux x + v * uy x" in exI, auto)
  2604     by (rule_tac x="\<lambda>x. u * ux x + v * uy x" in exI, auto)
  2601 qed (use assms in \<open>auto simp: convex_explicit\<close>)
  2605 qed (use assms in \<open>auto simp: convex_explicit\<close>)
  2602 
  2606 
  2603 
  2607 
  2604 subsubsection%unimportant \<open>Another formulation from Lars Schewe\<close>
  2608 subsubsection%unimportant \<open>Another formulation\<close>
       
  2609 
       
  2610 text "Formalized by Lars Schewe."
  2605 
  2611 
  2606 lemma convex_hull_explicit:
  2612 lemma convex_hull_explicit:
  2607   fixes p :: "'a::real_vector set"
  2613   fixes p :: "'a::real_vector set"
  2608   shows "convex hull p =
  2614   shows "convex hull p =
  2609     {y. \<exists>S u. finite S \<and> S \<subseteq> p \<and> (\<forall>x\<in>S. 0 \<le> u x) \<and> sum u S = 1 \<and> sum (\<lambda>v. u v *\<^sub>R v) S = y}"
  2615     {y. \<exists>S u. finite S \<and> S \<subseteq> p \<and> (\<forall>x\<in>S. 0 \<le> u x) \<and> sum u S = 1 \<and> sum (\<lambda>v. u v *\<^sub>R v) S = y}"
  3425   shows "of_nat (card B) = aff_dim B + 1"
  3431   shows "of_nat (card B) = aff_dim B + 1"
  3426   using aff_dim_unique[of B B] assms by auto
  3432   using aff_dim_unique[of B B] assms by auto
  3427 
  3433 
  3428 lemma affine_independent_iff_card:
  3434 lemma affine_independent_iff_card:
  3429     fixes s :: "'a::euclidean_space set"
  3435     fixes s :: "'a::euclidean_space set"
  3430     shows "~ affine_dependent s \<longleftrightarrow> finite s \<and> aff_dim s = int(card s) - 1"
  3436     shows "\<not> affine_dependent s \<longleftrightarrow> finite s \<and> aff_dim s = int(card s) - 1"
  3431   apply (rule iffI)
  3437   apply (rule iffI)
  3432   apply (simp add: aff_dim_affine_independent aff_independent_finite)
  3438   apply (simp add: aff_dim_affine_independent aff_independent_finite)
  3433   by (metis affine_basis_exists [of s] aff_dim_unique card_subset_eq diff_add_cancel of_nat_eq_iff)
  3439   by (metis affine_basis_exists [of s] aff_dim_unique card_subset_eq diff_add_cancel of_nat_eq_iff)
  3434 
  3440 
  3435 lemma aff_dim_sing [simp]:
  3441 lemma aff_dim_sing [simp]:
  3650     by (rule that[OF \<open>a \<noteq> 0\<close>])
  3656     by (rule that[OF \<open>a \<noteq> 0\<close>])
  3651 qed
  3657 qed
  3652 
  3658 
  3653 lemma affine_independent_card_dim_diffs:
  3659 lemma affine_independent_card_dim_diffs:
  3654   fixes S :: "'a :: euclidean_space set"
  3660   fixes S :: "'a :: euclidean_space set"
  3655   assumes "~ affine_dependent S" "a \<in> S"
  3661   assumes "\<not> affine_dependent S" "a \<in> S"
  3656     shows "card S = dim {x - a|x. x \<in> S} + 1"
  3662     shows "card S = dim {x - a|x. x \<in> S} + 1"
  3657 proof -
  3663 proof -
  3658   have 1: "{b - a|b. b \<in> (S - {a})} \<subseteq> {x - a|x. x \<in> S}" by auto
  3664   have 1: "{b - a|b. b \<in> (S - {a})} \<subseteq> {x - a|x. x \<in> S}" by auto
  3659   have 2: "x - a \<in> span {b - a |b. b \<in> S - {a}}" if "x \<in> S" for x
  3665   have 2: "x - a \<in> span {b - a |b. b \<in> S - {a}}" if "x \<in> S" for x
  3660   proof (cases "x = a")
  3666   proof (cases "x = a")
  3764   case False
  3770   case False
  3765   then obtain a where "a \<in> S" by auto
  3771   then obtain a where "a \<in> S" by auto
  3766   show ?thesis
  3772   show ?thesis
  3767   proof safe
  3773   proof safe
  3768     assume 0: "aff_dim S = 0"
  3774     assume 0: "aff_dim S = 0"
  3769     have "~ {a,b} \<subseteq> S" if "b \<noteq> a" for b
  3775     have "\<not> {a,b} \<subseteq> S" if "b \<noteq> a" for b
  3770       by (metis "0" aff_dim_2 aff_dim_subset not_one_le_zero that)
  3776       by (metis "0" aff_dim_2 aff_dim_subset not_one_le_zero that)
  3771     then show "\<exists>a. S = {a}"
  3777     then show "\<exists>a. S = {a}"
  3772       using \<open>a \<in> S\<close> by blast
  3778       using \<open>a \<in> S\<close> by blast
  3773   qed auto
  3779   qed auto
  3774 qed
  3780 qed
  3796     by auto
  3802     by auto
  3797 qed
  3803 qed
  3798 
  3804 
  3799 lemma disjoint_affine_hull:
  3805 lemma disjoint_affine_hull:
  3800   fixes s :: "'n::euclidean_space set"
  3806   fixes s :: "'n::euclidean_space set"
  3801   assumes "~ affine_dependent s" "t \<subseteq> s" "u \<subseteq> s" "t \<inter> u = {}"
  3807   assumes "\<not> affine_dependent s" "t \<subseteq> s" "u \<subseteq> s" "t \<inter> u = {}"
  3802     shows "(affine hull t) \<inter> (affine hull u) = {}"
  3808     shows "(affine hull t) \<inter> (affine hull u) = {}"
  3803 proof -
  3809 proof -
  3804   have "finite s" using assms by (simp add: aff_independent_finite)
  3810   have "finite s" using assms by (simp add: aff_independent_finite)
  3805   then have "finite t" "finite u" using assms finite_subset by blast+
  3811   then have "finite t" "finite u" using assms finite_subset by blast+
  3806   { fix y
  3812   { fix y
  3811       by (auto simp: affine_hull_finite \<open>finite t\<close> \<open>finite u\<close>)
  3817       by (auto simp: affine_hull_finite \<open>finite t\<close> \<open>finite u\<close>)
  3812     define c where "c x = (if x \<in> t then a x else if x \<in> u then -(b x) else 0)" for x
  3818     define c where "c x = (if x \<in> t then a x else if x \<in> u then -(b x) else 0)" for x
  3813     have [simp]: "s \<inter> t = t" "s \<inter> - t \<inter> u = u" using assms by auto
  3819     have [simp]: "s \<inter> t = t" "s \<inter> - t \<inter> u = u" using assms by auto
  3814     have "sum c s = 0"
  3820     have "sum c s = 0"
  3815       by (simp add: c_def comm_monoid_add_class.sum.If_cases \<open>finite s\<close> sum_negf)
  3821       by (simp add: c_def comm_monoid_add_class.sum.If_cases \<open>finite s\<close> sum_negf)
  3816     moreover have "~ (\<forall>v\<in>s. c v = 0)"
  3822     moreover have "\<not> (\<forall>v\<in>s. c v = 0)"
  3817       by (metis (no_types) IntD1 \<open>s \<inter> t = t\<close> a1 c_def sum_not_0 zero_neq_one)
  3823       by (metis (no_types) IntD1 \<open>s \<inter> t = t\<close> a1 c_def sum_not_0 zero_neq_one)
  3818     moreover have "(\<Sum>v\<in>s. c v *\<^sub>R v) = 0"
  3824     moreover have "(\<Sum>v\<in>s. c v *\<^sub>R v) = 0"
  3819       by (simp add: c_def if_smult sum_negf
  3825       by (simp add: c_def if_smult sum_negf
  3820              comm_monoid_add_class.sum.If_cases \<open>finite s\<close>)
  3826              comm_monoid_add_class.sum.If_cases \<open>finite s\<close>)
  3821     ultimately have False
  3827     ultimately have False
  5745     apply (erule_tac x="-b" in allE, auto)
  5751     apply (erule_tac x="-b" in allE, auto)
  5746     done
  5752     done
  5747 qed auto
  5753 qed auto
  5748 
  5754 
  5749 
  5755 
  5750 subsection \<open>Radon's theorem (from Lars Schewe)\<close>
  5756 subsection \<open>Radon's theorem\<close>
       
  5757 
       
  5758 text "Formalized by Lars Schewe."
  5751 
  5759 
  5752 lemma radon_ex_lemma:
  5760 lemma radon_ex_lemma:
  5753   assumes "finite c" "affine_dependent c"
  5761   assumes "finite c" "affine_dependent c"
  5754   shows "\<exists>u. sum u c = 0 \<and> (\<exists>v\<in>c. u v \<noteq> 0) \<and> sum (\<lambda>v. u v *\<^sub>R v) c = 0"
  5762   shows "\<exists>u. sum u c = 0 \<and> (\<exists>v\<in>c. u v \<noteq> 0) \<and> sum (\<lambda>v. u v *\<^sub>R v) c = 0"
  5755 proof -
  5763 proof -