src/HOL/Multivariate_Analysis/Brouwer_Fixpoint.thy
changeset 62393 a620a8756b7c
parent 62381 a6479cb85944
parent 62390 842917225d56
child 62843 313d3b697c9a
equal deleted inserted replaced
62385:7891843d79bb 62393:a620a8756b7c
   220   { assume rl: "rl ` s \<noteq> {..Suc n}"
   220   { assume rl: "rl ` s \<noteq> {..Suc n}"
   221     show "card ?S = 0 \<or> card ?S = 2"
   221     show "card ?S = 0 \<or> card ?S = 2"
   222     proof cases
   222     proof cases
   223       assume *: "{..n} \<subseteq> rl ` s"
   223       assume *: "{..n} \<subseteq> rl ` s"
   224       with rl rl_bd[OF s] have rl_s: "rl ` s = {..n}"
   224       with rl rl_bd[OF s] have rl_s: "rl ` s = {..n}"
   225         by (auto simp add: atMost_Suc subset_insert_iff split: split_if_asm)
   225         by (auto simp add: atMost_Suc subset_insert_iff split: if_split_asm)
   226       then have "\<not> inj_on rl s"
   226       then have "\<not> inj_on rl s"
   227         by (intro pigeonhole) simp
   227         by (intro pigeonhole) simp
   228       then obtain a b where ab: "a \<in> s" "b \<in> s" "rl a = rl b" "a \<noteq> b"
   228       then obtain a b where ab: "a \<in> s" "b \<in> s" "rl a = rl b" "a \<noteq> b"
   229         by (auto simp: inj_on_def)
   229         by (auto simp: inj_on_def)
   230       then have eq: "rl ` (s - {a}) = rl ` s"
   230       then have eq: "rl ` (s - {a}) = rl ` s"
   318   with * a have "\<And>a'. a' \<in> s \<Longrightarrow> a' j = p'"
   318   with * a have "\<And>a'. a' \<in> s \<Longrightarrow> a' j = p'"
   319     by auto
   319     by auto
   320   then have "\<And>i. i \<le> n \<Longrightarrow> enum i j = p'"
   320   then have "\<And>i. i \<le> n \<Longrightarrow> enum i j = p'"
   321     unfolding s_eq by auto
   321     unfolding s_eq by auto
   322   from this[of 0] this[of n] have "j \<notin> upd ` {..< n}"
   322   from this[of 0] this[of n] have "j \<notin> upd ` {..< n}"
   323     by (auto simp: enum_def fun_eq_iff split: split_if_asm)
   323     by (auto simp: enum_def fun_eq_iff split: if_split_asm)
   324   with upd \<open>j < n\<close> show False
   324   with upd \<open>j < n\<close> show False
   325     by (auto simp: bij_betw_def)
   325     by (auto simp: bij_betw_def)
   326 qed
   326 qed
   327 
   327 
   328 lemma upd_inj: "i < n \<Longrightarrow> j < n \<Longrightarrow> upd i = upd j \<longleftrightarrow> i = j"
   328 lemma upd_inj: "i < n \<Longrightarrow> j < n \<Longrightarrow> upd i = upd j \<longleftrightarrow> i = j"
   477   moreover
   477   moreover
   478   { fix j assume "Suc j < n"
   478   { fix j assume "Suc j < n"
   479     with enum_eq[of "Suc j"] enum_eq[of "Suc (Suc j)"]
   479     with enum_eq[of "Suc j"] enum_eq[of "Suc (Suc j)"]
   480     have "u_s (Suc j) = u_t (Suc j)"
   480     have "u_s (Suc j) = u_t (Suc j)"
   481       using s.enum_Suc[of "Suc j"] t.enum_Suc[of "Suc j"]
   481       using s.enum_Suc[of "Suc j"] t.enum_Suc[of "Suc j"]
   482       by (auto simp: fun_eq_iff split: split_if_asm) }
   482       by (auto simp: fun_eq_iff split: if_split_asm) }
   483   then have "\<And>j. 0 < j \<Longrightarrow> j < n \<Longrightarrow> u_s j = u_t j"
   483   then have "\<And>j. 0 < j \<Longrightarrow> j < n \<Longrightarrow> u_s j = u_t j"
   484     by (auto simp: gr0_conv_Suc)
   484     by (auto simp: gr0_conv_Suc)
   485   with \<open>n \<noteq> 0\<close> have "u_t 0 = u_s 0"
   485   with \<open>n \<noteq> 0\<close> have "u_t 0 = u_s 0"
   486     by (intro bij_betw_singleton_eq[OF t.upd s.upd, of 0]) auto
   486     by (intro bij_betw_singleton_eq[OF t.upd s.upd, of 0]) auto
   487   ultimately have "a = b"
   487   ultimately have "a = b"
   516   moreover
   516   moreover
   517   { fix j assume "j < n'"
   517   { fix j assume "j < n'"
   518     with enum_eq[of j] enum_eq[of "Suc j"]
   518     with enum_eq[of j] enum_eq[of "Suc j"]
   519     have "u_s j = u_t j"
   519     have "u_s j = u_t j"
   520       using s.enum_Suc[of j] t.enum_Suc[of j]
   520       using s.enum_Suc[of j] t.enum_Suc[of j]
   521       by (auto simp: Suc fun_eq_iff split: split_if_asm) }
   521       by (auto simp: Suc fun_eq_iff split: if_split_asm) }
   522   then have "\<And>j. j < n' \<Longrightarrow> u_s j = u_t j"
   522   then have "\<And>j. j < n' \<Longrightarrow> u_s j = u_t j"
   523     by (auto simp: gr0_conv_Suc)
   523     by (auto simp: gr0_conv_Suc)
   524   then have "u_t n' = u_s n'"
   524   then have "u_t n' = u_s n'"
   525     by (intro bij_betw_singleton_eq[OF t.upd s.upd, of n']) (auto simp: Suc)
   525     by (intro bij_betw_singleton_eq[OF t.upd s.upd, of n']) (auto simp: Suc)
   526   ultimately have "a = b"
   526   ultimately have "a = b"
   539   { fix a s assume "ksimplex p n s" "a \<in> s"
   539   { fix a s assume "ksimplex p n s" "a \<in> s"
   540     then obtain b u where "kuhn_simplex p n b u s" by (auto elim: ksimplex.cases)
   540     then obtain b u where "kuhn_simplex p n b u s" by (auto elim: ksimplex.cases)
   541     then interpret kuhn_simplex p n b u s .
   541     then interpret kuhn_simplex p n b u s .
   542     from s_space \<open>a \<in> s\<close> out_eq_p[OF \<open>a \<in> s\<close>]
   542     from s_space \<open>a \<in> s\<close> out_eq_p[OF \<open>a \<in> s\<close>]
   543     have "a \<in> (\<lambda>f x. if n \<le> x then p else f x) ` ({..< n} \<rightarrow>\<^sub>E {.. p})"
   543     have "a \<in> (\<lambda>f x. if n \<le> x then p else f x) ` ({..< n} \<rightarrow>\<^sub>E {.. p})"
   544       by (auto simp: image_iff subset_eq Pi_iff split: split_if_asm
   544       by (auto simp: image_iff subset_eq Pi_iff split: if_split_asm
   545                intro!: bexI[of _ "restrict a {..< n}"]) }
   545                intro!: bexI[of _ "restrict a {..< n}"]) }
   546   then show "{s. ksimplex p n s} \<subseteq> Pow ((\<lambda>f x. if n \<le> x then p else f x) ` ({..< n} \<rightarrow>\<^sub>E {.. p}))"
   546   then show "{s. ksimplex p n s} \<subseteq> Pow ((\<lambda>f x. if n \<le> x then p else f x) ` ({..< n} \<rightarrow>\<^sub>E {.. p}))"
   547     by auto
   547     by auto
   548 qed (simp add: finite_PiE)
   548 qed (simp add: finite_PiE)
   549 
   549 
   575       using s_eq by (simp add: atMost_Suc_eq_insert_0 insert_ident Zero_notin_Suc in_enum_image subset_eq)
   575       using s_eq by (simp add: atMost_Suc_eq_insert_0 insert_ident Zero_notin_Suc in_enum_image subset_eq)
   576     then have "enum 1 \<in> s - {a}"
   576     then have "enum 1 \<in> s - {a}"
   577       by auto
   577       by auto
   578     then have "upd 0 = n"
   578     then have "upd 0 = n"
   579       using \<open>a n < p\<close> \<open>a = enum 0\<close> na[rule_format, of "enum 1"]
   579       using \<open>a n < p\<close> \<open>a = enum 0\<close> na[rule_format, of "enum 1"]
   580       by (auto simp: fun_eq_iff enum_Suc split: split_if_asm)
   580       by (auto simp: fun_eq_iff enum_Suc split: if_split_asm)
   581     then have "bij_betw upd (Suc ` {..< n}) {..< n}"
   581     then have "bij_betw upd (Suc ` {..< n}) {..< n}"
   582       using upd
   582       using upd
   583       by (subst notIn_Un_bij_betw3[where b=0])
   583       by (subst notIn_Un_bij_betw3[where b=0])
   584          (auto simp: lessThan_Suc[symmetric] lessThan_Suc_eq_insert_0)
   584          (auto simp: lessThan_Suc[symmetric] lessThan_Suc_eq_insert_0)
   585     then have "bij_betw (upd\<circ>Suc) {..<n} {..<n}"
   585     then have "bij_betw (upd\<circ>Suc) {..<n} {..<n}"
  1004       { assume "Suc l = k"
  1004       { assume "Suc l = k"
  1005         have "enum (Suc (Suc i')) = t.enum (Suc l)"
  1005         have "enum (Suc (Suc i')) = t.enum (Suc l)"
  1006           using i by (simp add: k \<open>Suc l = k\<close> i'_def)
  1006           using i by (simp add: k \<open>Suc l = k\<close> i'_def)
  1007         then have False
  1007         then have False
  1008           using \<open>l < k\<close> \<open>k \<le> n\<close> \<open>Suc i' < n\<close>
  1008           using \<open>l < k\<close> \<open>k \<le> n\<close> \<open>Suc i' < n\<close>
  1009           by (auto simp: t.enum_Suc enum_Suc l upd_inj fun_eq_iff split: split_if_asm)
  1009           by (auto simp: t.enum_Suc enum_Suc l upd_inj fun_eq_iff split: if_split_asm)
  1010              (metis Suc_lessD n_not_Suc_n upd_inj) }
  1010              (metis Suc_lessD n_not_Suc_n upd_inj) }
  1011       with \<open>l < k\<close> have "Suc l < k"
  1011       with \<open>l < k\<close> have "Suc l < k"
  1012         by arith
  1012         by arith
  1013       have c_eq: "c = t.enum (Suc l)"
  1013       have c_eq: "c = t.enum (Suc l)"
  1014       proof (rule ccontr)
  1014       proof (rule ccontr)
  1040         using i by (simp add: k i'_def)
  1040         using i by (simp add: k i'_def)
  1041       also have "\<dots> = (enum i') (u l := Suc (enum i' (u l)), u (Suc l) := Suc (enum i' (u (Suc l))))"
  1041       also have "\<dots> = (enum i') (u l := Suc (enum i' (u l)), u (Suc l) := Suc (enum i' (u (Suc l))))"
  1042         using \<open>Suc l < k\<close> \<open>k \<le> n\<close> by (simp add: t.enum_Suc l t.upd_inj)
  1042         using \<open>Suc l < k\<close> \<open>k \<le> n\<close> by (simp add: t.enum_Suc l t.upd_inj)
  1043       finally have "(u l = upd i' \<and> u (Suc l) = upd (Suc i')) \<or>
  1043       finally have "(u l = upd i' \<and> u (Suc l) = upd (Suc i')) \<or>
  1044         (u l = upd (Suc i') \<and> u (Suc l) = upd i')"
  1044         (u l = upd (Suc i') \<and> u (Suc l) = upd i')"
  1045         using \<open>Suc i' < n\<close> by (auto simp: enum_Suc fun_eq_iff split: split_if_asm)
  1045         using \<open>Suc i' < n\<close> by (auto simp: enum_Suc fun_eq_iff split: if_split_asm)
  1046 
  1046 
  1047       then have "t = s \<or> t = b.enum ` {..n}"
  1047       then have "t = s \<or> t = b.enum ` {..n}"
  1048       proof (elim disjE conjE)
  1048       proof (elim disjE conjE)
  1049         assume u: "u l = upd i'"
  1049         assume u: "u l = upd i'"
  1050         have "c = t.enum (Suc l)" unfolding c_eq ..
  1050         have "c = t.enum (Suc l)" unfolding c_eq ..