src/HOL/Analysis/Brouwer_Fixpoint.thy
changeset 67968 a5ad4c015d1c
parent 67682 00c436488398
child 68017 e99f9b3962bf
equal deleted inserted replaced
67967:5a4280946a25 67968:a5ad4c015d1c
    14 (* the big advantage of Kuhn's proof over the usual Sperner's lemma one.     *)
    14 (* the big advantage of Kuhn's proof over the usual Sperner's lemma one.     *)
    15 (*                                                                           *)
    15 (*                                                                           *)
    16 (*              (c) Copyright, John Harrison 1998-2008                       *)
    16 (*              (c) Copyright, John Harrison 1998-2008                       *)
    17 (* ========================================================================= *)
    17 (* ========================================================================= *)
    18 
    18 
    19 section \<open>Results connected with topological dimension.\<close>
    19 section \<open>Results connected with topological dimension\<close>
    20 
    20 
    21 theory Brouwer_Fixpoint
    21 theory Brouwer_Fixpoint
    22 imports Path_Connected Homeomorphism
    22 imports Path_Connected Homeomorphism
    23 begin
    23 begin
    24 
    24 
   115     unfolding all_conj_distrib[symmetric] Ball_def (* FIXME: shouldn't this work by metis? *)
   115     unfolding all_conj_distrib[symmetric] Ball_def (* FIXME: shouldn't this work by metis? *)
   116     by (subst choice_iff[symmetric])+ blast
   116     by (subst choice_iff[symmetric])+ blast
   117 qed
   117 qed
   118 
   118 
   119 
   119 
   120 subsection \<open>The key "counting" observation, somewhat abstracted.\<close>
   120 subsection \<open>The key "counting" observation, somewhat abstracted\<close>
   121 
   121 
   122 lemma kuhn_counting_lemma:
   122 lemma kuhn_counting_lemma:
   123   fixes bnd compo compo' face S F
   123   fixes bnd compo compo' face S F
   124   defines "nF s == card {f\<in>F. face f s \<and> compo' f}"
   124   defines "nF s == card {f\<in>F. face f s \<and> compo' f}"
   125   assumes [simp, intro]: "finite F" \<comment> \<open>faces\<close> and [simp, intro]: "finite S" \<comment> \<open>simplices\<close>
   125   assumes [simp, intro]: "finite F" \<comment> \<open>faces\<close> and [simp, intro]: "finite S" \<comment> \<open>simplices\<close>
   146     using assms(7) by (subst sum.union_disjoint[symmetric]) (fastforce intro!: sum.cong)+
   146     using assms(7) by (subst sum.union_disjoint[symmetric]) (fastforce intro!: sum.cong)+
   147   ultimately show ?thesis
   147   ultimately show ?thesis
   148     by auto
   148     by auto
   149 qed
   149 qed
   150 
   150 
   151 subsection \<open>The odd/even result for faces of complete vertices, generalized.\<close>
   151 subsection \<open>The odd/even result for faces of complete vertices, generalized\<close>
   152 
   152 
   153 lemma kuhn_complete_lemma:
   153 lemma kuhn_complete_lemma:
   154   assumes [simp]: "finite simplices"
   154   assumes [simp]: "finite simplices"
   155     and face: "\<And>f s. face f s \<longleftrightarrow> (\<exists>a\<in>s. f = s - {a})"
   155     and face: "\<And>f s. face f s \<longleftrightarrow> (\<exists>a\<in>s. f = s - {a})"
   156     and card_s[simp]:  "\<And>s. s \<in> simplices \<Longrightarrow> card s = n + 2"
   156     and card_s[simp]:  "\<And>s. s \<in> simplices \<Longrightarrow> card s = n + 2"
  2365   ultimately show ?thesis
  2365   ultimately show ?thesis
  2366     using that deformation_retract  by metis
  2366     using that deformation_retract  by metis
  2367 qed
  2367 qed
  2368 
  2368 
  2369 
  2369 
  2370 subsection\<open>Punctured affine hulls, etc.\<close>
  2370 subsection\<open>Punctured affine hulls, etc\<close>
  2371 
  2371 
  2372 lemma continuous_on_compact_surface_projection_aux:
  2372 lemma continuous_on_compact_surface_projection_aux:
  2373   fixes S :: "'a::t2_space set"
  2373   fixes S :: "'a::t2_space set"
  2374   assumes "compact S" "S \<subseteq> T" "image q T \<subseteq> S"
  2374   assumes "compact S" "S \<subseteq> T" "image q T \<subseteq> S"
  2375       and contp: "continuous_on T p"
  2375       and contp: "continuous_on T p"
  2714   }
  2714   }
  2715   then show ?thesis
  2715   then show ?thesis
  2716     by blast
  2716     by blast
  2717 qed
  2717 qed
  2718 
  2718 
  2719 subsection\<open>Absolute retracts, Etc.\<close>
  2719 subsection\<open>Absolute retracts, etc\<close>
  2720 
  2720 
  2721 text\<open>Absolute retracts (AR), absolute neighbourhood retracts (ANR) and also
  2721 text\<open>Absolute retracts (AR), absolute neighbourhood retracts (ANR) and also
  2722  Euclidean neighbourhood retracts (ENR). We define AR and ANR by
  2722  Euclidean neighbourhood retracts (ENR). We define AR and ANR by
  2723  specializing the standard definitions for a set to embedding in
  2723  specializing the standard definitions for a set to embedding in
  2724 spaces of higher dimension. \<close>
  2724 spaces of higher dimension. \<close>
  3108 lemma homeomorphic_ANR_iff_ANR:
  3108 lemma homeomorphic_ANR_iff_ANR:
  3109   fixes S :: "'a::euclidean_space set" and T :: "'b::euclidean_space set"
  3109   fixes S :: "'a::euclidean_space set" and T :: "'b::euclidean_space set"
  3110   shows "S homeomorphic T \<Longrightarrow> ANR S \<longleftrightarrow> ANR T"
  3110   shows "S homeomorphic T \<Longrightarrow> ANR S \<longleftrightarrow> ANR T"
  3111 by (metis ANR_homeomorphic_ANR homeomorphic_sym)
  3111 by (metis ANR_homeomorphic_ANR homeomorphic_sym)
  3112 
  3112 
  3113 subsection\<open> Analogous properties of ENRs.\<close>
  3113 subsection\<open> Analogous properties of ENRs\<close>
  3114 
  3114 
  3115 proposition ENR_imp_absolute_neighbourhood_retract:
  3115 proposition ENR_imp_absolute_neighbourhood_retract:
  3116   fixes S :: "'a::euclidean_space set" and S' :: "'b::euclidean_space set"
  3116   fixes S :: "'a::euclidean_space set" and S' :: "'b::euclidean_space set"
  3117   assumes "ENR S" and hom: "S homeomorphic S'"
  3117   assumes "ENR S" and hom: "S homeomorphic S'"
  3118       and "S' \<subseteq> U"
  3118       and "S' \<subseteq> U"
  4272   fixes S :: "'a::euclidean_space set"
  4272   fixes S :: "'a::euclidean_space set"
  4273   assumes "ANR S" "c \<in> components S"
  4273   assumes "ANR S" "c \<in> components S"
  4274   shows "ANR c"
  4274   shows "ANR c"
  4275   by (metis ANR_connected_component_ANR assms componentsE)
  4275   by (metis ANR_connected_component_ANR assms componentsE)
  4276 
  4276 
  4277 subsection\<open>Original ANR material, now for ENRs.\<close>
  4277 subsection\<open>Original ANR material, now for ENRs\<close>
  4278 
  4278 
  4279 lemma ENR_bounded:
  4279 lemma ENR_bounded:
  4280   fixes S :: "'a::euclidean_space set"
  4280   fixes S :: "'a::euclidean_space set"
  4281   assumes "bounded S"
  4281   assumes "bounded S"
  4282   shows "ENR S \<longleftrightarrow> (\<exists>U. open U \<and> bounded U \<and> S retract_of U)"
  4282   shows "ENR S \<longleftrightarrow> (\<exists>U. open U \<and> bounded U \<and> S retract_of U)"
  4436   fixes a :: "'a::euclidean_space"
  4436   fixes a :: "'a::euclidean_space"
  4437   shows "ANR(sphere a r)"
  4437   shows "ANR(sphere a r)"
  4438   by (simp add: ENR_imp_ANR ENR_sphere)
  4438   by (simp add: ENR_imp_ANR ENR_sphere)
  4439 
  4439 
  4440 
  4440 
  4441 subsection\<open>Spheres are connected, etc.\<close>
  4441 subsection\<open>Spheres are connected, etc\<close>
  4442 
  4442 
  4443 lemma locally_path_connected_sphere_gen:
  4443 lemma locally_path_connected_sphere_gen:
  4444   fixes S :: "'a::euclidean_space set"
  4444   fixes S :: "'a::euclidean_space set"
  4445   assumes "bounded S" and "convex S" 
  4445   assumes "bounded S" and "convex S" 
  4446   shows "locally path_connected (rel_frontier S)"
  4446   shows "locally path_connected (rel_frontier S)"