equal
deleted
inserted
replaced
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 - |