src/HOL/Multivariate_Analysis/Convex_Euclidean_Space.thy
changeset 63072 eb5d493a9e03
parent 63040 eb4ddd18d635
child 63075 60a42a4166af
equal deleted inserted replaced
63071:3ca3bc795908 63072:eb5d493a9e03
  2940     using assms by (simp add: ab_group_add_class.ab_left_minus image_iff)
  2940     using assms by (simp add: ab_group_add_class.ab_left_minus image_iff)
  2941   with aff_dim_zero show ?thesis
  2941   with aff_dim_zero show ?thesis
  2942     by (metis aff_dim_translation_eq)
  2942     by (metis aff_dim_translation_eq)
  2943 qed
  2943 qed
  2944 
  2944 
  2945 lemma aff_dim_univ: "aff_dim (UNIV :: 'n::euclidean_space set) = int(DIM('n))"
  2945 lemma aff_dim_UNIV [simp]: "aff_dim (UNIV :: 'n::euclidean_space set) = int(DIM('n))"
  2946   using aff_dim_subspace[of "(UNIV :: 'n::euclidean_space set)"]
  2946   using aff_dim_subspace[of "(UNIV :: 'n::euclidean_space set)"]
  2947     dim_UNIV[where 'a="'n::euclidean_space"]
  2947     dim_UNIV[where 'a="'n::euclidean_space"]
  2948   by auto
  2948   by auto
  2949 
  2949 
  2950 lemma aff_dim_geq:
  2950 lemma aff_dim_geq:
  2988 lemma aff_dim_le_DIM:
  2988 lemma aff_dim_le_DIM:
  2989   fixes S :: "'n::euclidean_space set"
  2989   fixes S :: "'n::euclidean_space set"
  2990   shows "aff_dim S \<le> int (DIM('n))"
  2990   shows "aff_dim S \<le> int (DIM('n))"
  2991 proof -
  2991 proof -
  2992   have "aff_dim (UNIV :: 'n::euclidean_space set) = int(DIM('n))"
  2992   have "aff_dim (UNIV :: 'n::euclidean_space set) = int(DIM('n))"
  2993     using aff_dim_univ by auto
  2993     using aff_dim_UNIV by auto
  2994   then show "aff_dim (S:: 'n::euclidean_space set) \<le> int(DIM('n))"
  2994   then show "aff_dim (S:: 'n::euclidean_space set) \<le> int(DIM('n))"
  2995     using assms aff_dim_subset[of S "(UNIV :: ('n::euclidean_space) set)"] subset_UNIV by auto
  2995     using assms aff_dim_subset[of S "(UNIV :: ('n::euclidean_space) set)"] subset_UNIV by auto
  2996 qed
  2996 qed
  2997 
  2997 
  2998 lemma affine_dim_equal:
  2998 lemma affine_dim_equal:
  3034   have "S \<noteq> {}"
  3034   have "S \<noteq> {}"
  3035     using assms aff_dim_empty[of S] by auto
  3035     using assms aff_dim_empty[of S] by auto
  3036   have h0: "S \<subseteq> affine hull S"
  3036   have h0: "S \<subseteq> affine hull S"
  3037     using hull_subset[of S _] by auto
  3037     using hull_subset[of S _] by auto
  3038   have h1: "aff_dim (UNIV :: ('n::euclidean_space) set) = aff_dim S"
  3038   have h1: "aff_dim (UNIV :: ('n::euclidean_space) set) = aff_dim S"
  3039     using aff_dim_univ assms by auto
  3039     using aff_dim_UNIV assms by auto
  3040   then have h2: "aff_dim (affine hull S) \<le> aff_dim (UNIV :: ('n::euclidean_space) set)"
  3040   then have h2: "aff_dim (affine hull S) \<le> aff_dim (UNIV :: ('n::euclidean_space) set)"
  3041     using aff_dim_le_DIM[of "affine hull S"] assms h0 by auto
  3041     using aff_dim_le_DIM[of "affine hull S"] assms h0 by auto
  3042   have h3: "aff_dim S \<le> aff_dim (affine hull S)"
  3042   have h3: "aff_dim S \<le> aff_dim (affine hull S)"
  3043     using h0 aff_dim_subset[of S "affine hull S"] assms by auto
  3043     using h0 aff_dim_subset[of S "affine hull S"] assms by auto
  3044   then have h4: "aff_dim (affine hull S) = aff_dim (UNIV :: ('n::euclidean_space) set)"
  3044   then have h4: "aff_dim (affine hull S) = aff_dim (UNIV :: ('n::euclidean_space) set)"
  3613   apply auto
  3613   apply auto
  3614   using openin_subopen[of "subtopology euclidean (affine hull S)" S]
  3614   using openin_subopen[of "subtopology euclidean (affine hull S)" S]
  3615   apply auto
  3615   apply auto
  3616   done
  3616   done
  3617 
  3617 
  3618 lemma opein_rel_interior: "openin (subtopology euclidean (affine hull S)) (rel_interior S)"
  3618 lemma openin_rel_interior: "openin (subtopology euclidean (affine hull S)) (rel_interior S)"
  3619   apply (simp add: rel_interior_def)
  3619   apply (simp add: rel_interior_def)
  3620   apply (subst openin_subopen)
  3620   apply (subst openin_subopen)
  3621   apply blast
  3621   apply blast
  3622   done
  3622   done
  3623 
  3623 
  7955   fixes S :: "'n::euclidean_space set"
  7955   fixes S :: "'n::euclidean_space set"
  7956   assumes "convex S"
  7956   assumes "convex S"
  7957   shows "rel_interior (rel_interior S) = rel_interior S"
  7957   shows "rel_interior (rel_interior S) = rel_interior S"
  7958 proof -
  7958 proof -
  7959   have "openin (subtopology euclidean (affine hull (rel_interior S))) (rel_interior S)"
  7959   have "openin (subtopology euclidean (affine hull (rel_interior S))) (rel_interior S)"
  7960     using opein_rel_interior[of S] rel_interior_same_affine_hull[of S] assms by auto
  7960     using openin_rel_interior[of S] rel_interior_same_affine_hull[of S] assms by auto
  7961   then show ?thesis
  7961   then show ?thesis
  7962     using rel_interior_def by auto
  7962     using rel_interior_def by auto
  7963 qed
  7963 qed
  7964 
  7964 
  7965 lemma rel_interior_rel_open:
  7965 lemma rel_interior_rel_open:
  8162   shows "closed (rel_frontier S)"
  8162   shows "closed (rel_frontier S)"
  8163 proof -
  8163 proof -
  8164   have *: "closedin (subtopology euclidean (affine hull S)) (closure S - rel_interior S)"
  8164   have *: "closedin (subtopology euclidean (affine hull S)) (closure S - rel_interior S)"
  8165     apply (rule closedin_diff[of "subtopology euclidean (affine hull S)""closure S" "rel_interior S"])
  8165     apply (rule closedin_diff[of "subtopology euclidean (affine hull S)""closure S" "rel_interior S"])
  8166     using closed_closedin_trans[of "affine hull S" "closure S"] closed_affine_hull[of S]
  8166     using closed_closedin_trans[of "affine hull S" "closure S"] closed_affine_hull[of S]
  8167       closure_affine_hull[of S] opein_rel_interior[of S]
  8167       closure_affine_hull[of S] openin_rel_interior[of S]
  8168     apply auto
  8168     apply auto
  8169     done
  8169     done
  8170   show ?thesis
  8170   show ?thesis
  8171     apply (rule closedin_closed_trans[of "affine hull S" "rel_frontier S"])
  8171     apply (rule closedin_closed_trans[of "affine hull S" "rel_frontier S"])
  8172     unfolding rel_frontier_def
  8172     unfolding rel_frontier_def
  8390         by auto
  8390         by auto
  8391     }
  8391     }
  8392     then have "affine hull S = UNIV"
  8392     then have "affine hull S = UNIV"
  8393       by auto
  8393       by auto
  8394     then have "aff_dim S = int DIM('n)"
  8394     then have "aff_dim S = int DIM('n)"
  8395       using aff_dim_affine_hull[of S] by (simp add: aff_dim_univ)
  8395       using aff_dim_affine_hull[of S] by (simp add: aff_dim_UNIV)
  8396     then have False
  8396     then have False
  8397       using False by auto
  8397       using False by auto
  8398   }
  8398   }
  8399   ultimately show ?thesis by auto
  8399   ultimately show ?thesis by auto
  8400 next
  8400 next
 10887   fixes a :: "'a::euclidean_space"
 10887   fixes a :: "'a::euclidean_space"
 10888   shows "aff_dim {x. a \<bullet> x \<le> r} =
 10888   shows "aff_dim {x. a \<bullet> x \<le> r} =
 10889         (if a = 0 \<and> r < 0 then -1 else DIM('a))"
 10889         (if a = 0 \<and> r < 0 then -1 else DIM('a))"
 10890 proof -
 10890 proof -
 10891   have "int (DIM('a)) = aff_dim (UNIV::'a set)"
 10891   have "int (DIM('a)) = aff_dim (UNIV::'a set)"
 10892     by (simp add: aff_dim_univ)
 10892     by (simp add: aff_dim_UNIV)
 10893   then have "aff_dim (affine hull {x. a \<bullet> x \<le> r}) = DIM('a)" if "(a = 0 \<longrightarrow> r \<ge> 0)"
 10893   then have "aff_dim (affine hull {x. a \<bullet> x \<le> r}) = DIM('a)" if "(a = 0 \<longrightarrow> r \<ge> 0)"
 10894     using that by (simp add: affine_hull_halfspace_le not_less)
 10894     using that by (simp add: affine_hull_halfspace_le not_less)
 10895   then show ?thesis
 10895   then show ?thesis
 10896     by (force simp: aff_dim_affine_hull)
 10896     by (force simp: aff_dim_affine_hull)
 10897 qed
 10897 qed
 11318     using \<open>a \<in> span (op + (- z) ` S)\<close> affine_hull_insert_span_gen apply blast
 11318     using \<open>a \<in> span (op + (- z) ` S)\<close> affine_hull_insert_span_gen apply blast
 11319     apply (simp_all add: \<open>a \<noteq> 0\<close> szx)
 11319     apply (simp_all add: \<open>a \<noteq> 0\<close> szx)
 11320     done
 11320     done
 11321 qed
 11321 qed
 11322 
 11322 
 11323 proposition supporting_hyperplane_relative_boundary:
 11323 proposition supporting_hyperplane_rel_boundary:
 11324   fixes S :: "'a::euclidean_space set"
 11324   fixes S :: "'a::euclidean_space set"
 11325   assumes "convex S" "x \<in> S" and xno: "x \<notin> rel_interior S"
 11325   assumes "convex S" "x \<in> S" and xno: "x \<notin> rel_interior S"
 11326   obtains a where "a \<noteq> 0"
 11326   obtains a where "a \<noteq> 0"
 11327               and "\<And>y. y \<in> S \<Longrightarrow> a \<bullet> x \<le> a \<bullet> y"
 11327               and "\<And>y. y \<in> S \<Longrightarrow> a \<bullet> x \<le> a \<bullet> y"
 11328               and "\<And>y. y \<in> rel_interior S \<Longrightarrow> a \<bullet> x < a \<bullet> y"
 11328               and "\<And>y. y \<in> rel_interior S \<Longrightarrow> a \<bullet> x < a \<bullet> y"
 11372   fixes S :: "'a::euclidean_space set"
 11372   fixes S :: "'a::euclidean_space set"
 11373   assumes "convex S" "x \<in> closure S" "x \<notin> rel_interior S"
 11373   assumes "convex S" "x \<in> closure S" "x \<notin> rel_interior S"
 11374   obtains a where "a \<noteq> 0"
 11374   obtains a where "a \<noteq> 0"
 11375               and "\<And>y. y \<in> closure S \<Longrightarrow> a \<bullet> x \<le> a \<bullet> y"
 11375               and "\<And>y. y \<in> closure S \<Longrightarrow> a \<bullet> x \<le> a \<bullet> y"
 11376               and "\<And>y. y \<in> rel_interior S \<Longrightarrow> a \<bullet> x < a \<bullet> y"
 11376               and "\<And>y. y \<in> rel_interior S \<Longrightarrow> a \<bullet> x < a \<bullet> y"
 11377 using supporting_hyperplane_relative_boundary [of "closure S" x]
 11377 using supporting_hyperplane_rel_boundary [of "closure S" x]
 11378 by (metis assms convex_closure convex_rel_interior_closure)
 11378 by (metis assms convex_closure convex_rel_interior_closure)
 11379 
 11379 
 11380 subsection\<open> Some results on decomposing convex hulls, e.g. simplicial subdivision\<close>
 11380 subsection\<open> Some results on decomposing convex hulls, e.g. simplicial subdivision\<close>
 11381 
 11381 
 11382 lemma 
 11382 lemma 
 11499       by (metis (no_types) aff_dim_affine_hull eq)
 11499       by (metis (no_types) aff_dim_affine_hull eq)
 11500     then have "int (card b) = 1 + aff_dim s"
 11500     then have "int (card b) = 1 + aff_dim s"
 11501       by (simp add: aff_dim_affine_independent indb)
 11501       by (simp add: aff_dim_affine_independent indb)
 11502     then show ?thesis
 11502     then show ?thesis
 11503       using fbc aff
 11503       using fbc aff
 11504       by (simp add: \<open>\<not> affine_dependent c\<close> \<open>b \<subseteq> c\<close> aff_dim_affine_independent aff_dim_univ card_Diff_subset of_nat_diff)
 11504       by (simp add: \<open>\<not> affine_dependent c\<close> \<open>b \<subseteq> c\<close> aff_dim_affine_independent aff_dim_UNIV card_Diff_subset of_nat_diff)
 11505   qed
 11505   qed
 11506   show ?thesis
 11506   show ?thesis
 11507   proof (cases "c = b")
 11507   proof (cases "c = b")
 11508     case True show ?thesis
 11508     case True show ?thesis
 11509       apply (rule_tac f="{}" in that)
 11509       apply (rule_tac f="{}" in that)
 11510       using True affc
 11510       using True affc
 11511       apply (simp_all add: eq [symmetric])
 11511       apply (simp_all add: eq [symmetric])
 11512       by (metis aff_dim_univ aff_dim_affine_hull)
 11512       by (metis aff_dim_UNIV aff_dim_affine_hull)
 11513   next
 11513   next
 11514     case False
 11514     case False
 11515     have ind: "\<not> affine_dependent (\<Union>a\<in>c - b. c - {a})"
 11515     have ind: "\<not> affine_dependent (\<Union>a\<in>c - b. c - {a})"
 11516       by (rule affine_independent_subset [OF indc]) auto
 11516       by (rule affine_independent_subset [OF indc]) auto
 11517     have affeq: "affine hull s = (\<Inter>x\<in>(\<lambda>a. c - {a}) ` (c - b). affine hull x)"
 11517     have affeq: "affine hull s = (\<Inter>x\<in>(\<lambda>a. c - {a}) ` (c - b). affine hull x)"
 11523             if t: "t \<in> c" for t
 11523             if t: "t \<in> c" for t
 11524     proof -
 11524     proof -
 11525       have "insert t c = c"
 11525       have "insert t c = c"
 11526         using t by blast
 11526         using t by blast
 11527       then show ?thesis
 11527       then show ?thesis
 11528         by (metis (full_types) add.commute aff_dim_affine_hull aff_dim_insert aff_dim_univ affc affine_dependent_def indc insert_Diff_single t)
 11528         by (metis (full_types) add.commute aff_dim_affine_hull aff_dim_insert aff_dim_UNIV affc affine_dependent_def indc insert_Diff_single t)
 11529     qed
 11529     qed
 11530     show ?thesis
 11530     show ?thesis
 11531       apply (rule_tac f = "(\<lambda>x. affine hull x) ` ((\<lambda>a. c - {a}) ` (c - b))" in that)
 11531       apply (rule_tac f = "(\<lambda>x. affine hull x) ` ((\<lambda>a. c - {a}) ` (c - b))" in that)
 11532          using \<open>finite c\<close> apply blast
 11532          using \<open>finite c\<close> apply blast
 11533         apply (simp add: imeq card1 card2)
 11533         apply (simp add: imeq card1 card2)