Theory Brouwer_Fixpoint

(*  Author:     John Harrison
    Author:     Robert Himmelmann, TU Muenchen (Translation from HOL light) and LCP
*)

(* At the moment this is just Brouwer's fixpoint theorem. The proof is from  *)
(* Kuhn: "some combinatorial lemmas in topology", IBM J. v4. (1960) p. 518   *)
(* See "http://www.research.ibm.com/journal/rd/045/ibmrd0405K.pdf".          *)
(*                                                                           *)
(* The script below is quite messy, but at least we avoid formalizing any    *)
(* topological machinery; we don't even use barycentric subdivision; this is *)
(* the big advantage of Kuhn's proof over the usual Sperner's lemma one.     *)
(*                                                                           *)
(*              (c) Copyright, John Harrison 1998-2008                       *)

section ‹Brouwer's Fixed Point Theorem›

theory Brouwer_Fixpoint
  imports Homeomorphism Derivative
begin

subsection ‹Retractions›

lemma retract_of_contractible:
  assumes "contractible T" "S retract_of T"
  shows "contractible S"
  using assms
  apply (clarsimp simp add: retract_of_def contractible_def retraction_def homotopic_with image_subset_iff_funcset)
  apply (rule_tac x="r a" in exI)
  apply (rule_tac x="r  h" in exI)
  apply (intro conjI continuous_intros continuous_on_compose)
      apply (erule continuous_on_subset | force)+
  done

lemma retract_of_path_connected:
    "path_connected T; S retract_of T  path_connected S"
  by (metis path_connected_continuous_image retract_of_def retraction)

lemma retract_of_simply_connected:
  assumes T: "simply_connected T" and "S retract_of T"
  shows "simply_connected S"
proof -
  obtain r where r: "retraction T S r"
    using assms by (metis retract_of_def) 
  have "S  T"
    by (meson retraction T S r retraction)
  then have "(λa. a)  S  T"
    by blast
  then show ?thesis
    using simply_connected_retraction_gen [OF T]
    by (metis (no_types) r retraction retraction_refl)
qed

lemma retract_of_homotopically_trivial:
  assumes ts: "T retract_of S"
      and hom: "f g. continuous_on U f; f  U  S;
                       continuous_on U g; g  U  S
                        homotopic_with_canon (λx. True) U S f g"
      and "continuous_on U f" "f  U  T"
      and "continuous_on U g" "g  U  T"
    shows "homotopic_with_canon (λx. True) U T f g"
proof -
  obtain r where "r  S  S" "continuous_on S r" "xS. r (r x) = r x" "T = r ` S"
    using ts by (auto simp: retract_of_def retraction)
  then obtain k where "Retracts S r T k"
    unfolding Retracts_def using continuous_on_id by blast
  then show ?thesis
    by (rule Retracts.homotopically_trivial_retraction_gen) (use assms hom in force)+
qed

lemma retract_of_homotopically_trivial_null:
  assumes ts: "T retract_of S"
      and hom: "f. continuous_on U f; f  U  S
                      c. homotopic_with_canon (λx. True) U S f (λx. c)"
      and "continuous_on U f" "f  U  T"
  obtains c where "homotopic_with_canon (λx. True) U T f (λx. c)"
proof -
  obtain r where "r  S  S" "continuous_on S r" "xS. r (r x) = r x" "T = r ` S"
    using ts by (auto simp: retract_of_def retraction)
  then obtain k where "Retracts S r T k"
    unfolding Retracts_def by fastforce
  then show ?thesis
  proof (rule Retracts.homotopically_trivial_retraction_null_gen)
    show "f. continuous_on U f; f  U  S
          c. homotopic_with_canon (λa. True) U S f (λx. c)"
      using hom by blast
  qed (use assms that in auto)
qed

lemma retraction_openin_vimage_iff:
  "openin (top_of_set S) (S  r -` U)  openin (top_of_set T) U"
  if "retraction S T r" and "U  T"
  by (simp add: retraction_openin_vimage_iff that)

lemma retract_of_locally_compact:
    fixes S :: "'a :: {heine_borel,real_normed_vector} set"
    shows  " locally compact S; T retract_of S  locally compact T"
  by (metis locally_compact_closedin closedin_retract)

lemma homotopic_into_retract:
   "f  S  T; g  S  T; T retract_of U; homotopic_with_canon (λx. True) S U f g
         homotopic_with_canon (λx. True) S T f g"
  apply (subst (asm) homotopic_with_def)
  apply (simp add: homotopic_with retract_of_def retraction_def Pi_iff, clarify)
  apply (rule_tac x="r  h" in exI)
  by (smt (verit, ccfv_SIG) comp_def continuous_on_compose continuous_on_subset image_subset_iff)

lemma retract_of_locally_connected:
  assumes "locally connected T" "S retract_of T"
  shows "locally connected S"
  using assms
  by (metis retraction_openin_vimage_iff idempotent_imp_retraction locally_connected_quotient_image retract_ofE)

lemma retract_of_locally_path_connected:
  assumes "locally path_connected T" "S retract_of T"
  shows "locally path_connected S"
  using assms
  by (metis retraction_openin_vimage_iff idempotent_imp_retraction locally_path_connected_quotient_image retract_ofE)

text ‹A few simple lemmas about deformation retracts›

lemma deformation_retract_imp_homotopy_eqv:
  fixes S :: "'a::euclidean_space set"
  assumes "homotopic_with_canon (λx. True) S S id r" and r: "retraction S T r"
  shows "S homotopy_eqv T"
proof -
  have "homotopic_with_canon (λx. True) S S (id  r) id"
    by (simp add: assms(1) homotopic_with_symD)
  moreover have "homotopic_with_canon (λx. True) T T (r  id) id"
    using r unfolding retraction_def
    by (metis eq_id_iff homotopic_with_id2 topspace_euclidean_subtopology)
  ultimately
  show ?thesis
    unfolding homotopy_equivalent_space_def
    by (smt (verit, del_insts) continuous_map_id continuous_map_subtopology_eu id_def r retraction retraction_comp subset_refl) 
qed

lemma deformation_retract:
  fixes S :: "'a::euclidean_space set"
    shows "(r. homotopic_with_canon (λx. True) S S id r  retraction S T r) 
           T retract_of S  (f. homotopic_with_canon (λx. True) S S id f  f  S  T)"
    (is "?lhs = ?rhs")
proof
  assume ?lhs
  then show ?rhs
    by (auto simp: retract_of_def retraction_def)
next
  assume R: ?rhs
  have "r f. T  S; continuous_on S r; homotopic_with_canon (λx. True) S S id f;
            f  S  T; r  S  T; xT. r x = x
            homotopic_with_canon (λx. True) S S f r"
    apply (rule_tac f = "r  f" and g="r  id" in homotopic_with_eq)
       apply (rule_tac Y=S in homotopic_with_compose_continuous_left)
         apply (auto simp: homotopic_with_sym Pi_iff)
    done
  with R homotopic_with_trans show ?lhs
    unfolding retract_of_def retraction_def by blast
qed

lemma deformation_retract_of_contractible_sing:
  fixes S :: "'a::euclidean_space set"
  assumes "contractible S" "a  S"
  obtains r where "homotopic_with_canon (λx. True) S S id r" "retraction S {a} r"
proof -
  have "{a} retract_of S"
    by (simp add: a  S)
  moreover have "homotopic_with_canon (λx. True) S S id (λx. a)"
      using assms
      by (auto simp: contractible_def homotopic_into_contractible image_subset_iff)
  moreover have "(λx. a)  S  {a}"
    by (simp add: image_subsetI)
  ultimately show ?thesis
    by (metis that deformation_retract)
qed


lemma continuous_on_compact_surface_projection_aux:
  fixes S :: "'a::t2_space set"
  assumes "compact S" "S  T" "image q T  S"
      and contp: "continuous_on T p"
      and "x. x  S  q x = x"
      and [simp]: "x. x  T  q(p x) = q x"
      and "x. x  T  p(q x) = p x"
    shows "continuous_on T q"
proof -
  have *: "image p T = image p S"
    using assms by auto (metis imageI subset_iff)
  have contp': "continuous_on S p"
    by (rule continuous_on_subset [OF contp S  T])
  have "continuous_on (p ` T) q"
    by (simp add: "*" assms(1) assms(2) assms(5) continuous_on_inv contp' rev_subsetD)
  then have "continuous_on T (q  p)"
    by (rule continuous_on_compose [OF contp])
  then show ?thesis
    by (rule continuous_on_eq [of _ "q  p"]) (simp add: o_def)
qed

lemma continuous_on_compact_surface_projection:
  fixes S :: "'a::real_normed_vector set"
  assumes "compact S"
      and S: "S  V - {0}" and "cone V"
      and iff: "x k. x  V - {0}  0 < k  (k *R x)  S  d x = k"
  shows "continuous_on (V - {0}) (λx. d x *R x)"
proof (rule continuous_on_compact_surface_projection_aux [OF compact S S])
  show "(λx. d x *R x) ` (V - {0})  S"
    using iff by auto
  show "continuous_on (V - {0}) (λx. inverse(norm x) *R x)"
    by (intro continuous_intros) force
  show "x. x  S  d x *R x = x"
    by (metis S zero_less_one local.iff scaleR_one subset_eq)
  show "d (x /R norm x) *R (x /R norm x) = d x *R x" if "x  V - {0}" for x
    using iff [of "inverse(norm x) *R x" "norm x * d x", symmetric] iff that cone V
    by (simp add: field_simps cone_def zero_less_mult_iff)
  show "d x *R x /R norm (d x *R x) = x /R norm x" if "x  V - {0}" for x
  proof -
    have "0 < d x"
      using local.iff that by blast
    then show ?thesis
      by simp
  qed
qed

subsection ‹Kuhn Simplices›

lemma bij_betw_singleton_eq:
  assumes f: "bij_betw f A B" and g: "bij_betw g A B" and a: "a  A"
  assumes eq: "(x. x  A  x  a  f x = g x)"
  shows "f a = g a"
proof -
  have "f ` (A - {a}) = g ` (A - {a})"
    by (intro image_cong) (simp_all add: eq)
  then have "B - {f a} = B - {g a}"
    using f g a  by (auto simp: bij_betw_def inj_on_image_set_diff set_eq_iff)
  moreover have "f a  B" "g a  B"
    using f g a by (auto simp: bij_betw_def)
  ultimately show ?thesis
    by auto
qed

lemmas swap_apply1 = swap_apply(1)
lemmas swap_apply2 = swap_apply(2)

lemma pointwise_minimal_pointwise_maximal:
  fixes s :: "(nat  nat) set"
  assumes "finite s"
    and "s  {}"
    and "xs. ys. x  y  y  x"
  shows "as. xs. a  x"
    and "as. xs. x  a"
  using assms
proof (induct s rule: finite_ne_induct)
  case (insert b s)
  assume *: "xinsert b s. yinsert b s. x  y  y  x"
  then obtain u l where "l  s" "bs. l  b" "u  s" "bs. b  u"
    using insert by auto
  with * show "ainsert b s. xinsert b s. a  x" "ainsert b s. xinsert b s. x  a"
    by (metis insert_iff order.trans)+
qed auto

lemma kuhn_labelling_lemma:
  fixes P Q :: "'a::euclidean_space  bool"
  assumes "x. P x  P (f x)"
    and "x. P x  (iBasis. Q i  0  xi  xi  1)"
  shows "l. (x.iBasis. l x i  (1::nat)) 
             (x.iBasis. P x  Q i  (xi = 0)  (l x i = 0)) 
             (x.iBasis. P x  Q i  (xi = 1)  (l x i = 1)) 
             (x.iBasis. P x  Q i  (l x i = 0)  xi  f xi) 
             (x.iBasis. P x  Q i  (l x i = 1)  f xi  xi)"
proof -
  { fix x i
    let ?R = "λy. (P x  Q i  x  i = 0  y = (0::nat)) 
        (P x  Q i  x  i = 1  y = 1) 
        (P x  Q i  y = 0  x  i  f x  i) 
        (P x  Q i  y = 1  f x  i  x  i)"
    { assume "P x" "Q i" "i  Basis" with assms have "0  f x  i  f x  i  1" by auto }
    then have "i  Basis  ?R 0  ?R 1" by auto }
  then show ?thesis
    unfolding all_conj_distrib[symmetric] Ball_def (* FIXME: shouldn't this work by metis? *)
    by (subst choice_iff[symmetric])+ blast
qed


subsubsection ‹The key "counting" observation, somewhat abstracted›

lemma kuhn_counting_lemma:
  fixes bnd compo compo' face S F
  defines "nF s == card {fF. face f s  compo' f}"
  assumes [simp, intro]: "finite F" ― ‹faces› and [simp, intro]: "finite S" ― ‹simplices›
    and "f. f  F  bnd f  card {sS. face f s} = 1"
    and "f. f  F  ¬ bnd f  card {sS. face f s} = 2"
    and "s. s  S  compo s  nF s = 1"
    and "s. s  S  ¬ compo s  nF s = 0  nF s = 2"
    and "odd (card {fF. compo' f  bnd f})"
  shows "odd (card {sS. compo s})"
proof -
  have "(s | s  S  ¬ compo s. nF s) + (s | s  S  compo s. nF s) = (sS. nF s)"
    by (subst sum.union_disjoint[symmetric]) (auto intro!: sum.cong)
  also have " = (sS. card {f  {fF. compo' f  bnd f}. face f s}) +
                  (sS. card {f  {fF. compo' f  ¬ bnd f}. face f s})"
    unfolding sum.distrib[symmetric]
    by (subst card_Un_disjoint[symmetric])
       (auto simp: nF_def intro!: sum.cong arg_cong[where f=card])
  also have " = 1 * card {fF. compo' f  bnd f} + 2 * card {fF. compo' f  ¬ bnd f}"
    using assms(4,5) by (fastforce intro!: arg_cong2[where f="(+)"] sum_multicount)
  finally have "odd ((s | s  S  ¬ compo s. nF s) + card {sS. compo s})"
    using assms(6,8) by simp
  moreover have "(s | s  S  ¬ compo s. nF s) =
    (s | s  S  ¬ compo s  nF s = 0. nF s) + (s | s  S  ¬ compo s  nF s = 2. nF s)"
    using assms(7) by (subst sum.union_disjoint[symmetric]) (fastforce intro!: sum.cong)+
  ultimately show ?thesis
    by auto
qed

subsubsection ‹The odd/even result for faces of complete vertices, generalized›

lemma kuhn_complete_lemma:
  assumes [simp]: "finite simplices"
    and face: "f s. face f s  (as. f = s - {a})"
    and card_s[simp]:  "s. s  simplices  card s = n + 2"
    and rl_bd: "s. s  simplices  rl ` s  {..Suc n}"
    and bnd: "f s. s  simplices  face f s  bnd f  card {ssimplices. face f s} = 1"
    and nbnd: "f s. s  simplices  face f s  ¬ bnd f  card {ssimplices. face f s} = 2"
    and odd_card: "odd (card {f. (ssimplices. face f s)  rl ` f = {..n}  bnd f})"
  shows "odd (card {ssimplices. (rl ` s = {..Suc n})})"
proof (rule kuhn_counting_lemma)
  have finite_s[simp]: "s. s  simplices  finite s"
    by (metis add_is_0 zero_neq_numeral card.infinite assms(3))

  let ?F = "{f. ssimplices. face f s}"
  have F_eq: "?F = (ssimplices. as. {s - {a}})"
    by (auto simp: face)
  show "finite ?F"
    using finite simplices unfolding F_eq by auto

  show "card {s  simplices. face f s} = 1" if "f  ?F" "bnd f" for f
    using bnd that by auto

  show "card {s  simplices. face f s} = 2" if "f  ?F" "¬ bnd f" for f
    using nbnd that by auto

  show "odd (card {f  {f. ssimplices. face f s}. rl ` f = {..n}  bnd f})"
    using odd_card by simp

  fix s assume s[simp]: "s  simplices"
  let ?S = "{f  {f. ssimplices. face f s}. face f s  rl ` f = {..n}}"
  have "?S = (λa. s - {a}) ` {as. rl ` (s - {a}) = {..n}}"
    using s by (fastforce simp: face)
  then have card_S: "card ?S = card {as. rl ` (s - {a}) = {..n}}"
    by (auto intro!: card_image inj_onI)

  { assume rl: "rl ` s = {..Suc n}"
    then have inj_rl: "inj_on rl s"
      by (intro eq_card_imp_inj_on) auto
    moreover obtain a where "rl a = Suc n" "a  s"
      by (metis atMost_iff image_iff le_Suc_eq rl)
    ultimately have n: "{..n} = rl ` (s - {a})"
      by (auto simp: inj_on_image_set_diff rl)
    have "{as. rl ` (s - {a}) = {..n}} = {a}"
      using inj_rl a  s by (auto simp: n inj_on_image_eq_iff[OF inj_rl])
    then show "card ?S = 1"
      unfolding card_S by simp }

  { assume rl: "rl ` s  {..Suc n}"
    show "card ?S = 0  card ?S = 2"
    proof cases
      assume *: "{..n}  rl ` s"
      with rl rl_bd[OF s] have rl_s: "rl ` s = {..n}"
        by (auto simp: atMost_Suc subset_insert_iff split: if_split_asm)
      then have "¬ inj_on rl s"
        by (intro pigeonhole) simp
      then obtain a b where ab: "a  s" "b  s" "rl a = rl b" "a  b"
        by (auto simp: inj_on_def)
      then have eq: "rl ` (s - {a}) = rl ` s"
        by auto
      with ab have inj: "inj_on rl (s - {a})"
        by (intro eq_card_imp_inj_on) (auto simp: rl_s card_Diff_singleton_if)

      { fix x assume "x  s" "x  {a, b}"
        then have "rl ` s - {rl x} = rl ` ((s - {a}) - {x})"
          by (auto simp: eq inj_on_image_set_diff[OF inj])
        also have " = rl ` (s - {x})"
          using ab x  {a, b} by auto
        also assume " = rl ` s"
        finally have False
          using xs by auto }
      moreover
      { fix x assume "x  {a, b}" with ab have "x  s  rl ` (s - {x}) = rl ` s"
          by (simp add: set_eq_iff image_iff Bex_def) metis }
      ultimately have "{as. rl ` (s - {a}) = {..n}} = {a, b}"
        unfolding rl_s[symmetric] by fastforce
      with a  b show "card ?S = 0  card ?S = 2"
        unfolding card_S by simp
    next
      assume "¬ {..n}  rl ` s"
      then have "x. rl ` (s - {x})  {..n}"
        by auto
      then show "card ?S = 0  card ?S = 2"
        unfolding card_S by simp
    qed }
qed fact

locale kuhn_simplex =
  fixes p n and base upd and S :: "(nat  nat) set"
  assumes base: "base  {..< n}  {..< p}"
  assumes base_out: "i. n  i  base i = p"
  assumes upd: "bij_betw upd {..< n} {..< n}"
  assumes s_pre: "S = (λi j. if j  upd`{..< i} then Suc (base j) else base j) ` {.. n}"
begin

definition "enum i j = (if j  upd`{..< i} then Suc (base j) else base j)"

lemma s_eq: "S = enum ` {.. n}"
  unfolding s_pre enum_def[abs_def] ..

lemma upd_space: "i < n  upd i < n"
  using upd by (auto dest!: bij_betwE)

lemma s_space: "S  {..< n}  {.. p}"
proof -
  { fix i assume "i  n" then have "enum i  {..< n}  {.. p}"
    proof (induct i)
      case 0 then show ?case
        using base by (auto simp: Pi_iff less_imp_le enum_def)
    next
      case (Suc i) with base show ?case
        by (auto simp: Pi_iff Suc_le_eq less_imp_le enum_def intro: upd_space)
    qed }
  then show ?thesis
    by (auto simp: s_eq)
qed

lemma inj_upd: "inj_on upd {..< n}"
  using upd by (simp add: bij_betw_def)

lemma inj_enum: "inj_on enum {.. n}"
proof -
  { fix x y :: nat assume "x  y" "x  n" "y  n"
    with upd have "upd ` {..< x}  upd ` {..< y}"
      by (subst inj_on_image_eq_iff[where C="{..< n}"]) (auto simp: bij_betw_def)
    then have "enum x  enum y"
      by (auto simp: enum_def fun_eq_iff) }
  then show ?thesis
    by (auto simp: inj_on_def)
qed

lemma enum_0: "enum 0 = base"
  by (simp add: enum_def[abs_def])

lemma base_in_s: "base  S"
  unfolding s_eq by (subst enum_0[symmetric]) auto

lemma enum_in: "i  n  enum i  S"
  unfolding s_eq by auto

lemma one_step:
  assumes a: "a  S" "j < n"
  assumes *: "a'. a'  S  a'  a  a' j = p'"
  shows "a j  p'"
proof
  assume "a j = p'"
  with * a have "a'. a'  S  a' j = p'"
    by auto
  then have "i. i  n  enum i j = p'"
    unfolding s_eq by auto
  from this[of 0] this[of n] have "j  upd ` {..< n}"
    by (auto simp: enum_def fun_eq_iff split: if_split_asm)
  with upd j < n show False
    by (auto simp: bij_betw_def)
qed

lemma upd_inj: "i < n  j < n  upd i = upd j  i = j"
  using upd by (auto simp: bij_betw_def inj_on_eq_iff)

lemma upd_surj: "upd ` {..< n} = {..< n}"
  using upd by (auto simp: bij_betw_def)

lemma in_upd_image: "A  {..< n}  i < n  upd i  upd ` A  i  A"
  using inj_on_image_mem_iff[of upd "{..< n}"] upd
  by (auto simp: bij_betw_def)

lemma enum_inj: "i  n  j  n  enum i = enum j  i = j"
  using inj_enum by (auto simp: inj_on_eq_iff)

lemma in_enum_image: "A  {.. n}  i  n  enum i  enum ` A  i  A"
  using inj_on_image_mem_iff[OF inj_enum] by auto

lemma enum_mono: "i  n  j  n  enum i  enum j  i  j"
  by (auto simp: enum_def le_fun_def in_upd_image Ball_def[symmetric])

lemma enum_strict_mono: "i  n  j  n  enum i < enum j  i < j"
  using enum_mono[of i j] enum_inj[of i j] by (auto simp: le_less)

lemma chain: "a  S  b  S  a  b  b  a"
  by (auto simp: s_eq enum_mono)

lemma less: "a  S  b  S  a i < b i  a < b"
  using chain[of a b] by (auto simp: less_fun_def le_fun_def not_le[symmetric])

lemma enum_0_bot: "a  S  a = enum 0  (a'S. a  a')"
  unfolding s_eq by (auto simp: enum_mono Ball_def)

lemma enum_n_top: "a  S  a = enum n  (a'S. a'  a)"
  unfolding s_eq by (auto simp: enum_mono Ball_def)

lemma enum_Suc: "i < n  enum (Suc i) = (enum i)(upd i := Suc (enum i (upd i)))"
  by (auto simp: fun_eq_iff enum_def upd_inj)

lemma enum_eq_p: "i  n  n  j  enum i j = p"
  by (induct i) (auto simp: enum_Suc enum_0 base_out upd_space not_less[symmetric])

lemma out_eq_p: "a  S  n  j  a j = p"
  unfolding s_eq by (auto simp: enum_eq_p)

lemma s_le_p: "a  S  a j  p"
  using out_eq_p[of a j] s_space by (cases "j < n") auto

lemma le_Suc_base: "a  S  a j  Suc (base j)"
  unfolding s_eq by (auto simp: enum_def)

lemma base_le: "a  S  base j  a j"
  unfolding s_eq by (auto simp: enum_def)

lemma enum_le_p: "i  n  j < n  enum i j  p"
  using enum_in[of i] s_space by auto

lemma enum_less: "a  S  i < n  enum i < a  enum (Suc i)  a"
  unfolding s_eq by (auto simp: enum_strict_mono enum_mono)

lemma ksimplex_0:
  "n = 0  S = {(λx. p)}"
  using s_eq enum_def base_out by auto

lemma replace_0:
  assumes "j < n" "a  S" and p: "xS - {a}. x j = 0" and "x  S"
  shows "x  a"
proof cases
  assume "x  a"
  have "a j  0"
    using assms by (intro one_step[where a=a]) auto
  with less[OF xS aS, of j] p[rule_format, of x] x  S x  a
  show ?thesis
    by auto
qed simp

lemma replace_1:
  assumes "j < n" "a  S" and p: "xS - {a}. x j = p" and "x  S"
  shows "a  x"
proof cases
  assume "x  a"
  have "a j  p"
    using assms by (intro one_step[where a=a]) auto
  with enum_le_p[of _ j] j < n aS
  have "a j < p"
    by (auto simp: less_le s_eq)
  with less[OF aS xS, of j] p[rule_format, of x] x  S x  a
  show ?thesis
    by auto
qed simp

end

locale kuhn_simplex_pair = s: kuhn_simplex p n b_s u_s s + t: kuhn_simplex p n b_t u_t t
  for p n b_s u_s s b_t u_t t
begin

lemma enum_eq:
  assumes l: "i  l" "l  j" and "j + d  n"
  assumes eq: "s.enum ` {i .. j} = t.enum ` {i + d .. j + d}"
  shows "s.enum l = t.enum (l + d)"
using l proof (induct l rule: dec_induct)
  case base
  then have s: "s.enum i  t.enum ` {i + d .. j + d}" and t: "t.enum (i + d)  s.enum ` {i .. j}"
    using eq by auto
  from t i  j j + d  n have "s.enum i  t.enum (i + d)"
    by (auto simp: s.enum_mono)
  moreover from s i  j j + d  n have "t.enum (i + d)  s.enum i"
    by (auto simp: t.enum_mono)
  ultimately show ?case
    by auto
next
  case (step l)
  moreover from step.prems j + d  n have
      "s.enum l < s.enum (Suc l)"
      "t.enum (l + d) < t.enum (Suc l + d)"
    by (simp_all add: s.enum_strict_mono t.enum_strict_mono)
  moreover have
      "s.enum (Suc l)  t.enum ` {i + d .. j + d}"
      "t.enum (Suc l + d)  s.enum ` {i .. j}"
    using step j + d  n eq by (auto simp: s.enum_inj t.enum_inj)
  ultimately have "s.enum (Suc l) = t.enum (Suc (l + d))"
    using j + d  n
    by (intro antisym s.enum_less[THEN iffD1] t.enum_less[THEN iffD1])
       (auto intro!: s.enum_in t.enum_in)
  then show ?case by simp
qed

lemma ksimplex_eq_bot:
  assumes a: "a  s" "a'. a'  s  a  a'"
  assumes b: "b  t" "b'. b'  t  b  b'"
  assumes eq: "s - {a} = t - {b}"
  shows "s = t"
proof cases
  assume "n = 0" with s.ksimplex_0 t.ksimplex_0 show ?thesis by simp
next
  assume "n  0"
  have "s.enum 0 = (s.enum (Suc 0)) (u_s 0 := s.enum (Suc 0) (u_s 0) - 1)"
       "t.enum 0 = (t.enum (Suc 0)) (u_t 0 := t.enum (Suc 0) (u_t 0) - 1)"
    using n  0 by (simp_all add: s.enum_Suc t.enum_Suc)
  moreover have e0: "a = s.enum 0" "b = t.enum 0"
    using a b by (simp_all add: s.enum_0_bot t.enum_0_bot)
  moreover
  { fix j assume "0 < j" "j  n"
    moreover have "s - {a} = s.enum ` {Suc 0 .. n}" "t - {b} = t.enum ` {Suc 0 .. n}"
      unfolding s.s_eq t.s_eq e0 by (auto simp: s.enum_inj t.enum_inj)
    ultimately have "s.enum j = t.enum j"
      using enum_eq[of "1" j n 0] eq by auto }
  note enum_eq = this
  then have "s.enum (Suc 0) = t.enum (Suc 0)"
    using n  0 by auto
  moreover
  { fix j assume "Suc j < n"
    with enum_eq[of "Suc j"] enum_eq[of "Suc (Suc j)"]
    have "u_s (Suc j) = u_t (Suc j)"
      using s.enum_Suc[of "Suc j"] t.enum_Suc[of "Suc j"]
      by (auto simp: fun_eq_iff split: if_split_asm) }
  then have "j. 0 < j  j < n  u_s j = u_t j"
    by (auto simp: gr0_conv_Suc)
  with n  0 have "u_t 0 = u_s 0"
    by (intro bij_betw_singleton_eq[OF t.upd s.upd, of 0]) auto
  ultimately have "a = b"
    by simp
  with assms show "s = t"
    by auto
qed

lemma ksimplex_eq_top:
  assumes a: "a  s" "a'. a'  s  a'  a"
  assumes b: "b  t" "b'. b'  t  b'  b"
  assumes eq: "s - {a} = t - {b}"
  shows "s = t"
proof (cases n)
  assume "n = 0" with s.ksimplex_0 t.ksimplex_0 show ?thesis by simp
next
  case (Suc n')
  have "s.enum n = (s.enum n') (u_s n' := Suc (s.enum n' (u_s n')))"
       "t.enum n = (t.enum n') (u_t n' := Suc (t.enum n' (u_t n')))"
    using Suc by (simp_all add: s.enum_Suc t.enum_Suc)
  moreover have en: "a = s.enum n" "b = t.enum n"
    using a b by (simp_all add: s.enum_n_top t.enum_n_top)
  moreover
  { fix j assume "j < n"
    moreover have "s - {a} = s.enum ` {0 .. n'}" "t - {b} = t.enum ` {0 .. n'}"
      unfolding s.s_eq t.s_eq en by (auto simp: s.enum_inj t.enum_inj Suc)
    ultimately have "s.enum j = t.enum j"
      using enum_eq[of "0" j n' 0] eq Suc by auto }
  note enum_eq = this
  then have "s.enum n' = t.enum n'"
    using Suc by auto
  moreover
  { fix j assume "j < n'"
    with enum_eq[of j] enum_eq[of "Suc j"]
    have "u_s j = u_t j"
      using s.enum_Suc[of j] t.enum_Suc[of j]
      by (auto simp: Suc fun_eq_iff split: if_split_asm) }
  then have "j. j < n'  u_s j = u_t j"
    by (auto simp: gr0_conv_Suc)
  then have "u_t n' = u_s n'"
    by (intro bij_betw_singleton_eq[OF t.upd s.upd, of n']) (auto simp: Suc)
  ultimately have "a = b"
    by simp
  with assms show "s = t"
    by auto
qed

end

inductive ksimplex for p n :: nat where
  ksimplex: "kuhn_simplex p n base upd s  ksimplex p n s"

lemma finite_ksimplexes: "finite {s. ksimplex p n s}"
proof (rule finite_subset)
  { fix a s assume "ksimplex p n s" "a  s"
    then obtain b u where "kuhn_simplex p n b u s" by (auto elim: ksimplex.cases)
    then interpret kuhn_simplex p n b u s .
    from s_space a  s out_eq_p[OF a  s]
    have "a  (λf x. if n  x then p else f x) ` ({..< n} E {.. p})"
      by (auto simp: image_iff subset_eq Pi_iff split: if_split_asm
               intro!: bexI[of _ "restrict a {..< n}"]) }
  then show "{s. ksimplex p n s}  Pow ((λf x. if n  x then p else f x) ` ({..< n} E {.. p}))"
    by auto
qed (simp add: finite_PiE)

lemma ksimplex_card:
  assumes "ksimplex p n s" shows "card s = Suc n"
using assms proof cases
  case (ksimplex u b)
  then interpret kuhn_simplex p n u b s .
  show ?thesis
    by (simp add: card_image s_eq inj_enum)
qed

lemma simplex_top_face:
  assumes "0 < p" "xs'. x n = p"
  shows "ksimplex p n s'  (s a. ksimplex p (Suc n) s  a  s  s' = s - {a})"
  using assms
proof safe
  fix s a assume "ksimplex p (Suc n) s" and a: "a  s" and na: "xs - {a}. x n = p"
  then show "ksimplex p n (s - {a})"
  proof cases
    case (ksimplex base upd)
    then interpret kuhn_simplex p "Suc n" base upd "s" .

    have "a n < p"
      using one_step[of a n p] na as s_space by (auto simp: less_le)
    then have "a = enum 0"
      using a  s na by (subst enum_0_bot) (auto simp: le_less intro!: less[of a _ n])
    then have s_eq: "s - {a} = enum ` Suc ` {.. n}"
      using s_eq by (simp add: atMost_Suc_eq_insert_0 insert_ident in_enum_image subset_eq)
    then have "enum 1  s - {a}"
      by auto
    then have "upd 0 = n"
      using a n < p a = enum 0 na[rule_format, of "enum 1"]
      by (auto simp: fun_eq_iff enum_Suc split: if_split_asm)
    then have "bij_betw upd (Suc ` {..< n}) {..< n}"
      using upd
      by (subst notIn_Un_bij_betw3[where b=0])
         (auto simp: lessThan_Suc[symmetric] lessThan_Suc_eq_insert_0)
    then have "bij_betw (updSuc) {..<n} {..<n}"
      by (rule bij_betw_trans[rotated]) (auto simp: bij_betw_def)

    have "a n = p - 1"
      using enum_Suc[of 0] na[rule_format, OF enum 1  s - {a}] a = enum 0 by (auto simp: upd 0 = n)

    show ?thesis
    proof (rule ksimplex.intros, standard)
      show "bij_betw (updSuc) {..< n} {..< n}" by fact
      show "base(n := p)  {..<n}  {..<p}" "i. ni  (base(n := p)) i = p"
        using base base_out by (auto simp: Pi_iff)

      have "i. Suc ` {..< i} = {..< Suc i} - {0}"
        by (auto simp: image_iff Ball_def) arith
      then have upd_Suc: "i. i  n  (updSuc) ` {..< i} = upd ` {..< Suc i} - {n}"
        using upd 0 = n upd_inj by (auto simp add: image_iff less_Suc_eq_0_disj)
      have n_in_upd: "i. n  upd ` {..< Suc i}"
        using upd 0 = n by auto

      define f' where "f' i j =
        (if j  (updSuc)`{..< i} then Suc ((base(n := p)) j) else (base(n := p)) j)" for i j
      { fix x i
        assume i [arith]: "i  n"
        with upd_Suc have "(upd  Suc) ` {..<i} = upd ` {..<Suc i} - {n}" .
        with a n < p a = enum 0 upd 0 = n a n = p - 1
        have "enum (Suc i) x = f' i x"
          by (auto simp add: f'_def enum_def)  }
      then show "s - {a} = f' ` {.. n}"
        unfolding s_eq image_comp by (intro image_cong) auto
    qed
  qed
next
  assume "ksimplex p n s'" and *: "xs'. x n = p"
  then show "s a. ksimplex p (Suc n) s  a  s  s' = s - {a}"
  proof cases
    case (ksimplex base upd)
    then interpret kuhn_simplex p n base upd s' .
    define b where "b = base (n := p - 1)"
    define u where "u i = (case i of 0  n | Suc i  upd i)" for i

    have "ksimplex p (Suc n) (s'  {b})"
    proof (rule ksimplex.intros, standard)
      show "b  {..<Suc n}  {..<p}"
        using base 0 < p unfolding lessThan_Suc b_def by (auto simp: PiE_iff)
      show "i. Suc n  i  b i = p"
        using base_out by (auto simp: b_def)

      have "bij_betw u (Suc ` {..< n}  {0}) ({..<n}  {u 0})"
        using upd
        by (intro notIn_Un_bij_betw) (auto simp: u_def bij_betw_def image_comp comp_def inj_on_def)
      then show "bij_betw u {..<Suc n} {..<Suc n}"
        by (simp add: u_def lessThan_Suc[symmetric] lessThan_Suc_eq_insert_0)

      define f' where "f' i j = (if j  u`{..< i} then Suc (b j) else b j)" for i j

      have u_eq: "i. i  n  u ` {..< Suc i} = upd ` {..< i}  { n }"
        by (auto simp: u_def image_iff upd_inj Ball_def split: nat.split) arith

      { fix x have "x  n  n  upd ` {..<x}"
          using upd_space by (simp add: image_iff neq_iff) }
      note n_not_upd = this

      have *: "f' ` {.. Suc n} = f' ` (Suc ` {.. n}  {0})"
        unfolding atMost_Suc_eq_insert_0 by simp
      also have " = (f'  Suc) ` {.. n}  {b}"
        by (auto simp: f'_def)
      also have "(f'  Suc) ` {.. n} = s'"
        using 0 < p base_out[of n]
        unfolding s_eq enum_def[abs_def] f'_def[abs_def] upd_space
        by (intro image_cong) (simp_all add: u_eq b_def fun_eq_iff n_not_upd)
      finally show "s'  {b} = f' ` {.. Suc n}" ..
    qed
    moreover have "b  s'"
      using * 0 < p by (auto simp: b_def)
    ultimately show ?thesis by auto
  qed
qed

lemma ksimplex_replace_0:
  assumes s: "ksimplex p n s" and a: "a  s"
  assumes j: "j < n" and p: "xs - {a}. x j = 0"
  shows "card {s'. ksimplex p n s'  (bs'. s' - {b} = s - {a})} = 1"
  using s
proof cases
  case (ksimplex b_s u_s)

  { fix t b assume "ksimplex p n t"
    then obtain b_t u_t where "kuhn_simplex p n b_t u_t t"
      by (auto elim: ksimplex.cases)
    interpret kuhn_simplex_pair p n b_s u_s s b_t u_t t
      by intro_locales fact+

    assume b: "b  t" "t - {b} = s - {a}"
    with a j p s.replace_0[of _ a] t.replace_0[of _ b] have "s = t"
      by (intro ksimplex_eq_top[of a b]) auto }
  then have "{s'. ksimplex p n s'  (bs'. s' - {b} = s - {a})} = {s}"
    using s a  s by auto
  then show ?thesis
    by simp
qed

lemma ksimplex_replace_1:
  assumes s: "ksimplex p n s" and a: "a  s"
  assumes j: "j < n" and p: "xs - {a}. x j = p"
  shows "card {s'. ksimplex p n s'  (bs'. s' - {b} = s - {a})} = 1"
  using s
proof cases
  case (ksimplex b_s u_s)

  { fix t b assume "ksimplex p n t"
    then obtain b_t u_t where "kuhn_simplex p n b_t u_t t"
      by (auto elim: ksimplex.cases)
    interpret kuhn_simplex_pair p n b_s u_s s b_t u_t t
      by intro_locales fact+

    assume b: "b  t" "t - {b} = s - {a}"
    with a j p s.replace_1[of _ a] t.replace_1[of _ b] have "s = t"
      by (intro ksimplex_eq_bot[of a b]) auto }
  then have "{s'. ksimplex p n s'  (bs'. s' - {b} = s - {a})} = {s}"
    using s a  s by auto
  then show ?thesis
    by simp
qed

lemma ksimplex_replace_2:
  assumes s: "ksimplex p n s" and "a  s" and "n  0"
    and lb: "j<n. xs - {a}. x j  0"
    and ub: "j<n. xs - {a}. x j  p"
  shows "card {s'. ksimplex p n s'  (bs'. s' - {b} = s - {a})} = 2"
  using s
proof cases
  case (ksimplex base upd)
  then interpret kuhn_simplex p n base upd s .

  from a  s obtain i where "i  n" "a = enum i"
    unfolding s_eq by auto

  from i  n have "i = 0  i = n  (0 < i  i < n)"
    by linarith
  then have "∃!s'. s'  s  ksimplex p n s'  (bs'. s - {a} = s'- {b})"
  proof (elim disjE conjE)
    assume "i = 0"
    define rot where [abs_def]: "rot i = (if i + 1 = n then 0 else i + 1)" for i
    let ?upd = "upd  rot"

    have rot: "bij_betw rot {..< n} {..< n}"
      by (auto simp: bij_betw_def inj_on_def image_iff Ball_def rot_def)
         arith+
    from rot upd have "bij_betw ?upd {..<n} {..<n}"
      by (rule bij_betw_trans)

    define f' where [abs_def]: "f' i j =
      (if j  ?upd`{..< i} then Suc (enum (Suc 0) j) else enum (Suc 0) j)" for i j

    interpret b: kuhn_simplex p n "enum (Suc 0)" "upd  rot" "f' ` {.. n}"
    proof
      from a = enum i ub n  0 i = 0
      obtain i' where "i'  n" "enum i'  enum 0" "enum i' (upd 0)  p"
        unfolding s_eq by (auto intro: upd_space simp: enum_inj)
      then have "enum 1  enum i'" "enum i' (upd 0) < p"
        using enum_le_p[of i' "upd 0"] by (auto simp: enum_inj enum_mono upd_space)
      then have "enum 1 (upd 0) < p"
        by (auto simp: le_fun_def intro: le_less_trans)
      then show "enum (Suc 0)  {..<n}  {..<p}"
        using base n  0 by (auto simp: enum_0 enum_Suc PiE_iff extensional_def upd_space)

      { fix i assume "n  i" then show "enum (Suc 0) i = p"
        using n  0 by (auto simp: enum_eq_p) }
      show "bij_betw ?upd {..<n} {..<n}" by fact
    qed (simp add: f'_def)
    have ks_f': "ksimplex p n (f' ` {.. n})"
      by rule unfold_locales

    have b_enum: "b.enum = f'" unfolding f'_def b.enum_def[abs_def] ..
    with b.inj_enum have inj_f': "inj_on f' {.. n}" by simp

    have f'_eq_enum: "f' j = enum (Suc j)" if "j < n" for j
    proof -
      from that have "rot ` {..< j} = {0 <..< Suc j}"
        by (auto simp: rot_def image_Suc_lessThan cong: image_cong_simp)
      with that n  0 show ?thesis
        by (simp only: f'_def enum_def fun_eq_iff image_comp [symmetric])
          (auto simp add: upd_inj)
    qed
    then have "enum ` Suc ` {..< n} = f' ` {..< n}"
      by (force simp: enum_inj)
    also have "Suc ` {..< n} = {.. n} - {0}"
      by (auto simp: image_iff Ball_def) arith
    also have "{..< n} = {.. n} - {n}"
      by auto
    finally have eq: "s - {a} = f' ` {.. n} - {f' n}"
      unfolding s_eq a = enum i i = 0
      by (simp add: inj_on_image_set_diff[OF inj_enum] inj_on_image_set_diff[OF inj_f'])

    have "enum 0 < f' 0"
      using n  0 by (simp add: enum_strict_mono f'_eq_enum)
    also have " < f' n"
      using n  0 b.enum_strict_mono[of 0 n] unfolding b_enum by simp
    finally have "a  f' n"
      using a = enum i i = 0 by auto

    { fix t c assume "ksimplex p n t" "c  t" and eq_sma: "s - {a} = t - {c}"
      obtain b u where "kuhn_simplex p n b u t"
        using ksimplex p n t by (auto elim: ksimplex.cases)
      then interpret t: kuhn_simplex p n b u t .

      { fix x assume "x  s" "x  a"
         then have "x (upd 0) = enum (Suc 0) (upd 0)"
           by (auto simp: a = enum i i = 0 s_eq enum_def enum_inj) }
      then have eq_upd0: "xt-{c}. x (upd 0) = enum (Suc 0) (upd 0)"
        unfolding eq_sma[symmetric] by auto
      then have "c (upd 0)  enum (Suc 0) (upd 0)"
        using n  0 by (intro t.one_step[OF ct ]) (auto simp: upd_space)
      then have "c (upd 0) < enum (Suc 0) (upd 0)  c (upd 0) > enum (Suc 0) (upd 0)"
        by auto
      then have "t = s  t = f' ` {..n}"
      proof (elim disjE conjE)
        assume *: "c (upd 0) < enum (Suc 0) (upd 0)"
        interpret st: kuhn_simplex_pair p n base upd s b u t ..
        { fix x assume "x  t" with * ct eq_upd0[rule_format, of x] have "c  x"
            by (auto simp: le_less intro!: t.less[of _ _ "upd 0"]) }
        note top = this
        have "s = t"
          using a = enum i i = 0 c  t
          by (intro st.ksimplex_eq_bot[OF _ _ _ _ eq_sma])
             (auto simp: s_eq enum_mono t.s_eq t.enum_mono top)
        then show ?thesis by simp
      next
        assume *: "c (upd 0) > enum (Suc 0) (upd 0)"
        interpret st: kuhn_simplex_pair p n "enum (Suc 0)" "upd  rot" "f' ` {.. n}" b u t ..
        have eq: "f' ` {..n} - {f' n} = t - {c}"
          using eq_sma eq by simp
        { fix x assume "x  t" with * ct eq_upd0[rule_format, of x] have "x  c"
            by (auto simp: le_less intro!: t.less[of _ _ "upd 0"]) }
        note top = this
        have "f' ` {..n} = t"
          using a = enum i i = 0 c  t
          by (intro st.ksimplex_eq_top[OF _ _ _ _ eq])
             (auto simp: b.s_eq b.enum_mono t.s_eq t.enum_mono b_enum[symmetric] top)
        then show ?thesis by simp
      qed }
    with ks_f' eq a  f' n n  0 show ?thesis
      apply (intro ex1I[of _ "f' ` {.. n}"])
       apply auto []
      apply metis
      done
  next
    assume "i = n"
    from n  0 obtain n' where n': "n = Suc n'"
      by (cases n) auto

    define rot where "rot i = (case i of 0  n' | Suc i  i)" for i
    let ?upd = "upd  rot"

    have rot: "bij_betw rot {..< n} {..< n}"
      by (auto simp: bij_betw_def inj_on_def image_iff Bex_def rot_def n' split: nat.splits)
         arith
    from rot upd have "bij_betw ?upd {..<n} {..<n}"
      by (rule bij_betw_trans)

    define b where "b = base (upd n' := base (upd n') - 1)"
    define f' where [abs_def]: "f' i j = (if j  ?upd`{..< i} then Suc (b j) else b j)" for i j

    interpret b: kuhn_simplex p n b "upd  rot" "f' ` {.. n}"
    proof
      { fix i assume "n  i" then show "b i = p"
          using base_out[of i] upd_space[of n'] by (auto simp: b_def n') }
      show "b  {..<n}  {..<p}"
        using base n  0 upd_space[of n']
        by (auto simp: b_def PiE_def Pi_iff Ball_def upd_space extensional_def n')

      show "bij_betw ?upd {..<n} {..<n}" by fact
    qed (simp add: f'_def)
    have f': "b.enum = f'" unfolding f'_def b.enum_def[abs_def] ..
    have ks_f': "ksimplex p n (b.enum ` {.. n})"
      unfolding f' by rule unfold_locales

    have "0 < n"
      using n  0 by auto

    { from a = enum i n  0 i = n lb upd_space[of n']
      obtain i' where "i'  n" "enum i'  enum n" "0 < enum i' (upd n')"
        unfolding s_eq by (auto simp: enum_inj n')
      moreover have "enum i' (upd n') = base (upd n')"
        unfolding enum_def using i'  n enum i'  enum n by (auto simp: n' upd_inj enum_inj)
      ultimately have "0 < base (upd n')"
        by auto }
    then have benum1: "b.enum (Suc 0) = base"
      unfolding b.enum_Suc[OF 0<n] b.enum_0 by (auto simp: b_def rot_def)

    have [simp]: "j. Suc j < n  rot ` {..< Suc j} = {n'}  {..< j}"
      by (auto simp: rot_def image_iff Ball_def split: nat.splits)
    have rot_simps: "j. rot (Suc j) = j" "rot 0 = n'"
      by (simp_all add: rot_def)

    { fix j assume j: "Suc j  n" then have "b.enum (Suc j) = enum j"
        by (induct j) (auto simp: benum1 enum_0 b.enum_Suc enum_Suc rot_simps) }
    note b_enum_eq_enum = this
    then have "enum ` {..< n} = b.enum ` Suc ` {..< n}"
      by (auto simp: image_comp intro!: image_cong)
    also have "Suc ` {..< n} = {.. n} - {0}"
      by (auto simp: image_iff Ball_def) arith
    also have "{..< n} = {.. n} - {n}"
      by auto
    finally have eq: "s - {a} = b.enum ` {.. n} - {b.enum 0}"
      unfolding s_eq a = enum i i = n
      using inj_on_image_set_diff[OF inj_enum Diff_subset, of "{n}"]
            inj_on_image_set_diff[OF b.inj_enum Diff_subset, of "{0}"]
      by (simp add: comp_def)

    have "b.enum 0  b.enum n"
      by (simp add: b.enum_mono)
    also have "b.enum n < enum n"
      using n  0 by (simp add: enum_strict_mono b_enum_eq_enum n')
    finally have "a  b.enum 0"
      using a = enum i i = n by auto

    { fix t c assume "ksimplex p n t" "c  t" and eq_sma: "s - {a} = t - {c}"
      obtain b' u where "kuhn_simplex p n b' u t"
        using ksimplex p n t by (auto elim: ksimplex.cases)
      then interpret t: kuhn_simplex p n b' u t .

      { fix x assume "x  s" "x  a"
         then have "x (upd n') = enum n' (upd n')"
           by (auto simp: a = enum i n' i = n s_eq enum_def enum_inj in_upd_image) }
      then have eq_upd0: "xt-{c}. x (upd n') = enum n' (upd n')"
        unfolding eq_sma[symmetric] by auto
      then have "c (upd n')  enum n' (upd n')"
        using n  0 by (intro t.one_step[OF ct ]) (auto simp: n' upd_space[unfolded n'])
      then have "c (upd n') < enum n' (upd n')  c (upd n') > enum n' (upd n')"
        by auto
      then have "t = s  t = b.enum ` {..n}"
      proof (elim disjE conjE)
        assume *: "c (upd n') > enum n' (upd n')"
        interpret st: kuhn_simplex_pair p n base upd s b' u t ..
        { fix x assume "x  t" with * ct eq_upd0[rule_format, of x] have "x  c"
            by (auto simp: le_less intro!: t.less[of _ _ "upd n'"]) }
        note top = this
        have "s = t"
          using a = enum i i = n c  t
          by (intro st.ksimplex_eq_top[OF _ _ _ _ eq_sma])
             (auto simp: s_eq enum_mono t.s_eq t.enum_mono top)
        then show ?thesis by simp
      next
        assume *: "c (upd n') < enum n' (upd n')"
        interpret st: kuhn_simplex_pair p n b "upd  rot" "f' ` {.. n}" b' u t ..
        have eq: "f' ` {..n} - {b.enum 0} = t - {c}"
          using eq_sma eq f' by simp
        { fix x assume "x  t" with * ct eq_upd0[rule_format, of x] have "c  x"
            by (auto simp: le_less intro!: t.less[of _ _ "upd n'"]) }
        note bot = this
        have "f' ` {..n} = t"
          using a = enum i i = n c  t
          by (intro st.ksimplex_eq_bot[OF _ _ _ _ eq])
             (auto simp: b.s_eq b.enum_mono t.s_eq t.enum_mono bot)
        with f' show ?thesis by simp
      qed }
    with ks_f' eq a  b.enum 0 n  0 show ?thesis
      apply (intro ex1I[of _ "b.enum ` {.. n}"])
      apply fastforce
      apply metis
      done
  next
    assume i: "0 < i" "i < n"
    define i' where "i' = i - 1"
    with i have "Suc i' < n"
      by simp
    with i have Suc_i': "Suc i' = i"
      by (simp add: i'_def)

    let ?upd = "Fun.swap i' i upd"
    from i upd have "bij_betw ?upd {..< n} {..< n}"
      by (subst bij_betw_swap_iff) (auto simp: i'_def)

    define f' where [abs_def]: "f' i j = (if j  ?upd`{..< i} then Suc (base j) else base j)"
      for i j
    interpret b: kuhn_simplex p n base ?upd "f' ` {.. n}"
    proof
      show "base  {..<n}  {..<p}" by (rule base)
      { fix i assume "n  i" then show "base i = p" by (rule base_out) }
      show "bij_betw ?upd {..<n} {..<n}" by fact
    qed (simp add: f'_def)
    have f': "b.enum = f'" unfolding f'_def b.enum_def[abs_def] ..
    have ks_f': "ksimplex p n (b.enum ` {.. n})"
      unfolding f' by rule unfold_locales

    have "{i}  {..n}"
      using i by auto
    { fix j assume "j  n"
      with i Suc_i' have "enum j = b.enum j  j  i"
        unfolding fun_eq_iff enum_def b.enum_def image_comp [symmetric]
        apply (cases i = j)
         apply (metis imageI in_upd_image lessI lessThan_iff lessThan_subset_iff order_less_le transpose_apply_first)
        by (metis lessThan_iff linorder_not_less not_less_eq_eq order_less_le transpose_image_eq)
      }
    note enum_eq_benum = this
    then have "enum ` ({.. n} - {i}) = b.enum ` ({.. n} - {i})"
      by (intro image_cong) auto
    then have eq: "s - {a} = b.enum ` {.. n} - {b.enum i}"
      unfolding s_eq a = enum i
      using inj_on_image_set_diff[OF inj_enum Diff_subset {i}  {..n}]
            inj_on_image_set_diff[OF b.inj_enum Diff_subset {i}  {..n}]
      by (simp add: comp_def)

    have "a  b.enum i"
      using a = enum i enum_eq_benum i by auto

    { fix t c assume "ksimplex p n t" "c  t" and eq_sma: "s - {a} = t - {c}"
      obtain b' u where "kuhn_simplex p n b' u t"
        using ksimplex p n t by (auto elim: ksimplex.cases)
      then interpret t: kuhn_simplex p n b' u t .
      have "enum i'  s - {a}" "enum (i + 1)  s - {a}"
        using a = enum i i enum_in by (auto simp: enum_inj i'_def)
      then obtain l k where
        l: "t.enum l = enum i'" "l  n" "t.enum l  c" and
        k: "t.enum k = enum (i + 1)" "k  n" "t.enum k  c"
        unfolding eq_sma by (auto simp: t.s_eq)
      with i have "t.enum l < t.enum k"
        by (simp add: enum_strict_mono i'_def)
      with l  n k  n have "l < k"
        by (simp add: t.enum_strict_mono)
      { assume "Suc l = k"
        have "enum (Suc (Suc i')) = t.enum (Suc l)"
          using i by (simp add: k Suc l = k i'_def)
        then have False
          using l < k k  n Suc i' < n
          by (auto simp: t.enum_Suc enum_Suc l upd_inj fun_eq_iff split: if_split_asm)
             (metis Suc_lessD n_not_Suc_n upd_inj) }
      with l < k have "Suc l < k"
        by arith
      have c_eq: "c = t.enum (Suc l)"
      proof (rule ccontr)
        assume "c  t.enum (Suc l)"
        then have "t.enum (Suc l)  s - {a}"
          using l < k k  n by (simp add: t.s_eq eq_sma)
        then obtain j where "t.enum (Suc l) = enum j" "j  n" "enum j  enum i"
          unfolding s_eq a = enum i by auto
        with i have "t.enum (Suc l)  t.enum l  t.enum k  t.enum (Suc l)"
          by (auto simp: i'_def enum_mono enum_inj l k)
        with Suc l < k k  n show False
          by (simp add: t.enum_mono)
      qed

      { have "t.enum (Suc (Suc l))  s - {a}"
          unfolding eq_sma c_eq t.s_eq using Suc l < k k  n by (auto simp: t.enum_inj)
        then obtain j where eq: "t.enum (Suc (Suc l)) = enum j" and "j  n" "j  i"
          by (auto simp: s_eq a = enum i)
        moreover have "enum i' < t.enum (Suc (Suc l))"
          unfolding l(1)[symmetric] using Suc l < k k  n by (auto simp: t.enum_strict_mono)
        ultimately have "i' < j"
          using i by (simp add: enum_strict_mono i'_def)
        with j  i j  n have "t.enum k  t.enum (Suc (Suc l))"
          unfolding i'_def by (simp add: enum_mono k eq)
        then have "k  Suc (Suc l)"
          using k  n Suc l < k by (simp add: t.enum_mono) }
      with Suc l < k have "Suc (Suc l) = k" by simp
      then have "enum (Suc (Suc i')) = t.enum (Suc (Suc l))"
        using i by (simp add: k i'_def)
      also have " = (enum i') (u l := Suc (enum i' (u l)), u (Suc l) := Suc (enum i' (u (Suc l))))"
        using Suc l < k k  n by (simp add: t.enum_Suc l t.upd_inj)
      finally have "(u l = upd i'  u (Suc l) = upd (Suc i')) 
        (u l = upd (Suc i')  u (Suc l) = upd i')"
        using Suc i' < n by (auto simp: enum_Suc fun_eq_iff split: if_split_asm)

      then have "t = s  t = b.enum ` {..n}"
      proof (elim disjE conjE)
        assume u: "u l = upd i'"
        have "c = t.enum (Suc l)" unfolding c_eq ..
        also have "t.enum (Suc l) = enum (Suc i')"
          using u l < k k  n Suc i' < n by (simp add: enum_Suc t.enum_Suc l)
        also have " = a"
          using a = enum i i by (simp add: i'_def)
        finally show ?thesis
          using eq_sma a  s c  t by auto
      next
        assume u: "u l = upd (Suc i')"
        define B where "B = b.enum ` {..n}"
        have "b.enum i' = enum i'"
          using enum_eq_benum[of i'] i by (auto simp: i'_def gr0_conv_Suc)
        have "c = t.enum (Suc l)" unfolding c_eq ..
        also have "t.enum (Suc l) = b.enum (Suc i')"
          using u l < k k  n Suc i' < n
          by (simp_all add: enum_Suc t.enum_Suc l b.enum_Suc b.enum i' = enum i')
             (simp add: Suc_i')
        also have " = b.enum i"
          using i by (simp add: i'_def)
        finally have "c = b.enum i" .
        then have "t - {c} = B - {c}" "c  B"
          unfolding eq_sma[symmetric] eq B_def using i by auto
        with c  t have "t = B"
          by auto
        then show ?thesis
          by (simp add: B_def)
      qed }
    with ks_f' eq a  b.enum i n  0 i  n show ?thesis
      apply (intro ex1I[of _ "b.enum ` {.. n}"])
      apply auto []
      apply metis
      done
  qed
  then show ?thesis
    using s a  s by (simp add: card_2_iff' Ex1_def) metis
qed

text ‹Hence another step towards concreteness.›

lemma kuhn_simplex_lemma:
  assumes "s. ksimplex p (Suc n) s  rl ` s  {.. Suc n}"
    and "odd (card {f. s a. ksimplex p (Suc n) s  a  s  (f = s - {a}) 
      rl ` f = {..n}  ((jn. xf. x j = 0)  (jn. xf. x j = p))})"
  shows "odd (card {s. ksimplex p (Suc n) s  rl ` s = {..Suc n}})"
proof (rule kuhn_complete_lemma[OF finite_ksimplexes refl, unfolded mem_Collect_eq,
    where bnd="λf. (j{..n}. xf. x j = 0)  (j{..n}. xf. x j = p)"],
    safe del: notI)

  have *: "x y. x = y  odd (card x)  odd (card y)"
    by auto
  show "odd (card {f. (s{s. ksimplex p (Suc n) s}. as. f = s - {a}) 
    rl ` f = {..n}  ((j{..n}. xf. x j = 0)  (j{..n}. xf. x j = p))})"
    apply (rule *[OF _ assms(2)])
    apply (auto simp: atLeast0AtMost)
    done

next

  fix s assume s: "ksimplex p (Suc n) s"
  then show "card s = n + 2"
    by (simp add: ksimplex_card)

  fix a assume a: "a  s" then show "rl a  Suc n"
    using assms(1) s by (auto simp: subset_eq)

  let ?S = "{t. ksimplex p (Suc n) t  (bt. s - {a} = t - {b})}"
  { fix j assume j: "j  n" "xs - {a}. x j = 0"
    with s a show "card ?S = 1"
      using ksimplex_replace_0[of p "n + 1" s a j]
      by (subst eq_commute) simp }

  { fix j assume j: "j  n" "xs - {a}. x j = p"
    with s a show "card ?S = 1"
      using ksimplex_replace_1[of p "n + 1" s a j]
      by (subst eq_commute) simp }

  { assume "card ?S  2" "¬ (j{..n}. xs - {a}. x j = p)"
    with s a show "j{..n}. xs - {a}. x j = 0"
      using ksimplex_replace_2[of p "n + 1" s a]
      by (subst (asm) eq_commute) auto }
qed

subsubsection ‹Reduced labelling›

definition reduced :: "nat  (nat  nat)  nat" where "reduced n x = (LEAST k. k = n  x k  0)"

lemma reduced_labelling:
  shows "reduced n x  n"
    and "i<reduced n x. x i = 0"
    and "reduced n x = n  x (reduced n x)  0"
proof -
  show "reduced n x  n"
    unfolding reduced_def by (rule LeastI2_wellorder[where a=n]) auto
  show "i<reduced n x. x i = 0"
    unfolding reduced_def by (rule LeastI2_wellorder[where a=n]) fastforce+
  show "reduced n x = n  x (reduced n x)  0"
    unfolding reduced_def by (rule LeastI2_wellorder[where a=n]) fastforce+
qed

lemma reduced_labelling_unique:
  "r  n  i<r. x i = 0  r = n  x r  0  reduced n x = r"
  by (metis linorder_less_linear linorder_not_le reduced_labelling)

lemma reduced_labelling_zero: "j < n  x j = 0  reduced n x  j"
  using reduced_labelling[of n x] by auto

lemma reduce_labelling_zero[simp]: "reduced 0 x = 0"
  by (rule reduced_labelling_unique) auto

lemma reduced_labelling_nonzero: "j < n  x j  0  reduced n x  j"
  using reduced_labelling[of n x] by (elim allE[where x=j]) auto

lemma reduced_labelling_Suc: "reduced (Suc n) x  Suc n  reduced (Suc n) x = reduced n x"
  using reduced_labelling[of "Suc n" x]
  by (intro reduced_labelling_unique[symmetric]) auto

lemma complete_face_top:
  assumes "xf. jn. x j = 0  lab x j = 0"
    and "xf. jn. x j = p  lab x j = 1"
    and eq: "(reduced (Suc n)  lab) ` f = {..n}"
  shows "((jn. xf. x j = 0)  (jn. xf. x j = p))  (xf. x n = p)"
proof (safe del: disjCI)
  fix x j assume j: "j  n" "xf. x j = 0"
  { fix x assume "x  f" with assms j have "reduced (Suc n) (lab x)  j"
      by (intro reduced_labelling_zero) auto }
  moreover have "j  (reduced (Suc n)  lab) ` f"
    using j eq by auto
  ultimately show "x n = p"
    by force
next
  fix x j assume j: "j  n" "xf. x j = p" and x: "x  f"
  have "j = n"
  proof (rule ccontr)
    assume "¬ ?thesis"
    { fix x assume "x  f"
      with assms j have "reduced (Suc n) (lab x)  j"
        by (intro reduced_labelling_nonzero) auto
      then have "reduced (Suc n) (lab x)  n"
        using j  n j  n by simp }
    moreover
    have "n  (reduced (Suc n)  lab) ` f"
      using eq by auto
    ultimately show False
      by force
  qed
  moreover have "j  (reduced (Suc n)  lab) ` f"
    using j eq by auto
  ultimately show "x n = p"
    using j x by auto
qed auto

text ‹Hence we get just about the nice induction.›

lemma kuhn_induction:
  assumes "0 < p"
    and lab_0: "x. jn. (j. x j  p)  x j = 0  lab x j = 0"
    and lab_1: "x. jn. (j. x j  p)  x j = p  lab x j = 1"
    and odd: "odd (card {s. ksimplex p n s  (reduced nlab) ` s = {..n}})"
  shows "odd (card {s. ksimplex p (Suc n) s  (reduced (Suc n)lab) ` s = {..Suc n}})"
proof -
  let ?rl = "reduced (Suc n)  lab" and ?ext = "λf v. jn. xf. x j = v"
  let ?ext = "λs. (jn. xs. x j = 0)  (jn. xs. x j = p)"
  have "s. ksimplex p (Suc n) s  ?rl ` s  {..Suc n}"
    by (simp add: reduced_labelling subset_eq)
  moreover
  have "{s. ksimplex p n s  (reduced n  lab) ` s = {..n}} =
        {f. s a. ksimplex p (Suc n) s  a  s  f = s - {a}  ?rl ` f = {..n}  ?ext f}"
  proof (intro set_eqI, safe del: disjCI equalityI disjE)
    fix s assume s: "ksimplex p n s" and rl: "(reduced n  lab) ` s = {..n}"
    from s obtain u b where "kuhn_simplex p n u b s" by (auto elim: ksimplex.cases)
    then interpret kuhn_simplex p n u b s .
    have all_eq_p: "xs. x n = p"
      by (auto simp: out_eq_p)
    moreover
    { fix x assume "x  s"
      with lab_1[rule_format, of n x] all_eq_p s_le_p[of x] 
      have "?rl x  n"
        by (auto intro!: reduced_labelling_nonzero)
      then have "?rl x = reduced n (lab x)"
        by (auto intro!: reduced_labelling_Suc) }
    then have "?rl ` s = {..n}"
      using rl by (simp cong: image_cong)
    moreover
    obtain t a where "ksimplex p (Suc n) t" "a  t" "s = t - {a}"
      using s unfolding simplex_top_face[OF 0 < p all_eq_p] by auto
    ultimately
    show "t a. ksimplex p (Suc n) t  a  t  s = t - {a}  ?rl ` s = {..n}  ?ext s"
      by auto
  next
    fix x s a assume s: "ksimplex p (Suc n) s" and rl: "?rl ` (s - {a}) = {.. n}"
      and a: "a  s" and "?ext (s - {a})"
    from s obtain u b where "kuhn_simplex p (Suc n) u b s" by (auto elim: ksimplex.cases)
    then interpret kuhn_simplex p "Suc n" u b s .
    have all_eq_p: "xs. x (Suc n) = p"
      by (auto simp: out_eq_p)

    { fix x assume "x  s - {a}"
      then have "?rl x  ?rl ` (s - {a})"
        by auto
      then have "?rl x  n"
        unfolding rl by auto
      then have "?rl x = reduced n (lab x)"
        by (auto intro!: reduced_labelling_Suc) }
    then show rl': "(reduced nlab) ` (s - {a}) = {..n}"
      unfolding rl[symmetric] by (intro image_cong) auto

    from ?ext (s - {a})
    have all_eq_p: "xs - {a}. x n = p"
    proof (elim disjE exE conjE)
      fix j assume "j  n" "xs - {a}. x j = 0"
      with lab_0[rule_format, of j] all_eq_p s_le_p
      have "x. x  s - {a}  reduced (Suc n) (lab x)  j"
        by (intro reduced_labelling_zero) auto
      moreover have "j  ?rl ` (s - {a})"
        using j  n unfolding rl by auto
      ultimately show ?thesis
        by force
    next
      fix j assume "j  n" and eq_p: "xs - {a}. x j = p"
      show ?thesis
      proof cases
        assume "j = n" with eq_p show ?thesis by simp
      next
        assume "j  n"
        { fix x assume x: "x  s - {a}"
          have "reduced n (lab x)  j"
          proof (rule reduced_labelling_nonzero)
            show "lab x j  0"
              using lab_1[rule_format, of j x] x s_le_p[of x] eq_p j  n by auto
            show "j < n"
              using j  n j  n by simp
          qed
          then have "reduced n (lab x)  n"
            using j  n j  n by simp }
        moreover have "n  (reduced nlab) ` (s - {a})"
          unfolding rl' by auto
        ultimately show ?thesis
          by force
      qed
    qed
    show "ksimplex p n (s - {a})"
      unfolding simplex_top_face[OF 0 < p all_eq_p] using s a by auto
  qed
  ultimately show ?thesis
    using assms by (intro kuhn_simplex_lemma) auto
qed

text ‹And so we get the final combinatorial result.›

lemma ksimplex_0: "ksimplex p 0 s  s = {(λx. p)}"
proof
  assume "ksimplex p 0 s" then show "s = {(λx. p)}"
    by (blast dest: kuhn_simplex.ksimplex_0 elim: ksimplex.cases)
next
  assume s: "s = {(λx. p)}"
  show "ksimplex p 0 s"
  proof (intro ksimplex, unfold_locales)
    show "(λ_. p)  {..<0::nat}  {..<p}" by auto
    show "bij_betw id {..<0} {..<0}"
      by simp
  qed (auto simp: s)
qed

lemma kuhn_combinatorial:
  assumes "0 < p"
    and "x j. (j. x j  p)  j < n  x j = 0  lab x j = 0"
    and "x j. (j. x j  p)  j < n   x j = p  lab x j = 1"
  shows "odd (card {s. ksimplex p n s  (reduced nlab) ` s = {..n}})"
    (is "odd (card (?M n))")
  using assms
proof (induct n)
  case 0 then show ?case
    by (simp add: ksimplex_0 cong: conj_cong)
next
  case (Suc n)
  then have "odd (card (?M n))"
    by force
  with Suc show ?case
    using kuhn_induction[of p n] by (auto simp: comp_def)
qed

lemma kuhn_lemma:
  fixes n p :: nat
  assumes "0 < p"
    and "x. (i<n. x i  p)  (i<n. label x i = (0::nat)  label x i = 1)"
    and "x. (i<n. x i  p)  (i<n. x i = 0  label x i = 0)"
    and "x. (i<n. x i  p)  (i<n. x i = p  label x i = 1)"
  obtains q where "i<n. q i < p"
    and "i<n. r s. (j<n. q j  r j  r j  q j + 1)  (j<n. q j  s j  s j  q j + 1)  label r i  label s i"
proof -
  let ?rl = "reduced n  label"
  let ?A = "{s. ksimplex p n s  ?rl ` s = {..n}}"
  have "odd (card ?A)"
    using assms by (intro kuhn_combinatorial[of p n label]) auto
  then have "?A  {}"
    by (rule odd_card_imp_not_empty)
  then obtain s b u where "kuhn_simplex p n b u s" and rl: "?rl ` s = {..n}"
    by (auto elim: ksimplex.cases)
  interpret kuhn_simplex p n b u s by fact

  show ?thesis
  proof (intro that[of b] allI impI)
    fix i
    assume "i < n"
    then show "b i < p"
      using base by auto
  next
    fix i
    assume "i < n"
    then have "i  {.. n}" "Suc i  {.. n}"
      by auto
    then obtain u v where u: "u  s" "Suc i = ?rl u" and v: "v  s" "i = ?rl v"
      unfolding rl[symmetric] by blast

    have "label u i  label v i"
      using reduced_labelling [of n "label u"] reduced_labelling [of n "label v"]
        u(2)[symmetric] v(2)[symmetric] i < n
      by auto
    moreover
    have "b j  u j" "u j  b j + 1" "b j  v j" "v j  b j + 1" if "j < n" for j
      using that base_le[OF us] le_Suc_base[OF us] base_le[OF vs] le_Suc_base[OF vs]
      by auto
    ultimately show "r s. (j<n. b j  r j  r j  b j + 1) 
        (j<n. b j  s j  s j  b j + 1)  label r i  label s i"
      by blast
  qed
qed

subsubsection ‹Main result for the unit cube›

lemma kuhn_labelling_lemma':
  assumes "(x::natreal. P x  P (f x))"
    and "x. P x  (i::nat. Q i  0  x i  x i  1)"
  shows "l. (x i. l x i  (1::nat)) 
             (x i. P x  Q i  x i = 0  l x i = 0) 
             (x i. P x  Q i  x i = 1  l x i = 1) 
             (x i. P x  Q i  l x i = 0  x i  f x i) 
             (x i. P x  Q i  l x i = 1  f x i  x i)"
  unfolding all_conj_distrib [symmetric] 
  apply (subst choice_iff[symmetric])+
  by (metis assms choice_iff bot_nat_0.extremum nle_le zero_neq_one)

subsection ‹Brouwer's fixed point theorem›

text ‹We start proving Brouwer's fixed point theorem for the unit cube = cbox 0 One›.›

lemma brouwer_cube:
  fixes f :: "'a::euclidean_space  'a"
  assumes "continuous_on (cbox 0 One) f"
    and "f ` cbox 0 One  cbox 0 One"
  shows "xcbox 0 One. f x = x"
proof (rule ccontr)
  define n where "n = DIM('a)"
  have n: "1  n" "0 < n" "n  0"
    unfolding n_def by (auto simp: Suc_le_eq)
  assume "¬ ?thesis"
  then have *: "¬ (xcbox 0 One. f x - x = 0)"
    by auto
  obtain d where
      d: "d > 0" "x. x  cbox 0 One  d  norm (f x - x)"
    using brouwer_compactness_lemma[OF compact_cbox _ *] assms
    by (metis (no_types, lifting) continuous_on_cong continuous_on_diff continuous_on_id)
  have *: "x. x  cbox 0 One  f x  cbox 0 One"
    "x. x  (cbox 0 One::'a set)  (iBasis. True  0  x  i  x  i  1)"
    using assms(2)[unfolded image_subset_iff Ball_def]
    unfolding cbox_def
    by auto
  obtain label :: "'a  'a  nat" where label [rule_format]:
    "x. iBasis. label x i  1"
    "x. iBasis. x  cbox 0 One  x  i = 0  label x i = 0"
    "x. iBasis. x  cbox 0 One  x  i = 1  label x i = 1"
    "x. iBasis. x  cbox 0 One  label x i = 0  x  i  f x  i"
    "x. iBasis. x  cbox 0 One  label x i = 1  f x  i  x  i"
    using kuhn_labelling_lemma[OF *] by auto
  note label = this [rule_format]
  have lem1: "xcbox 0 One. ycbox 0 One. iBasis. label x i  label y i 
    ¦f x  i - x  i¦  norm (f y - f x) + norm (y - x)"
  proof safe
    fix x y :: 'a
    assume x: "x  cbox 0 One" and y: "y  cbox 0 One"
    fix i
    assume i: "label x i  label y i" "i  Basis"
    have *: "x y fx fy :: real. x  fx  fy  y  fx  x  y  fy 
      ¦fx - x¦  ¦fy - fx¦ + ¦y - x¦" by auto
    have "¦(f x - x)  i¦  ¦(f y - f x)i¦ + ¦(y - x)i¦"
    proof (cases "label x i = 0")
      case True
      then have fxy: "¬ f y  i  y  i  f x  i  x  i"
        by (metis True i label(1) label(5) le_antisym less_one not_le_imp_less y)
      show ?thesis
      unfolding inner_simps         
      by (rule *) (auto simp: True i label x y fxy)
    next
      case False
      then show ?thesis
        using label [OF i  Basis] i(1) x y
        by (smt (verit, ccfv_threshold) inner_diff_left less_one order_le_less)
    qed
    also have "  norm (f y - f x) + norm (y - x)"
      by (simp add: add_mono i(2) norm_bound_Basis_le)
    finally show "¦f x  i - x  i¦  norm (f y - f x) + norm (y - x)"
      unfolding inner_simps .
  qed
  have "e>0. xcbox 0 One. ycbox 0 One. zcbox 0 One. iBasis.
    norm (x - z) < e  norm (y - z) < e  label x i  label y i 
      ¦(f(z) - z)i¦ < d / (real n)"
  proof -
    have d': "d / real n / 8 > 0"
      using d(1) by (simp add: n_def)
    have *: "uniformly_continuous_on (cbox 0 One) f"
      by (rule compact_uniformly_continuous[OF assms(1) compact_cbox])
    obtain e where e:
        "e > 0"
        "x x'. x  cbox 0 One 
          x'  cbox 0 One 
          norm (x' - x) < e 
          norm (f x' - f x) < d / real n / 8"
      using *[unfolded uniformly_continuous_on_def,rule_format,OF d']
      unfolding dist_norm
      by blast
    show ?thesis
    proof (intro exI conjI ballI impI)
      show "0 < min (e / 2) (d / real n / 8)"
        using d' e by auto
      fix x y z i
      assume as:
        "x  cbox 0 One" "y  cbox 0 One" "z  cbox 0 One"
        "norm (x - z) < min (e / 2) (d / real n / 8)"
        "norm (y - z) < min (e / 2) (d / real n / 8)"
        "label x i  label y i"
      assume i: "i  Basis"
      have *: "z fz x fx n1 n2 n3 n4 d4 d :: real. ¦fx - x¦  n1 + n2 
        ¦fx - fz¦  n3  ¦x - z¦  n4 
        n1 < d4  n2 < 2 * d4  n3 < d4  n4 < d4 
        (8 * d4 = d)  ¦fz - z¦ < d"
        by auto
      show "¦(f z - z)  i¦ < d / real n"
        unfolding inner_simps
      proof (rule *)
        show "¦f x  i - x  i¦  norm (f y -f x) + norm (y - x)"
          using as(1) as(2) as(6) i lem1 by blast
        show "norm (f x - f z) < d / real n / 8"
          using d' e as by auto
        show "¦f x  i - f z  i¦  norm (f x - f z)" "¦x  i - z  i¦  norm (x - z)"
          unfolding inner_diff_left[symmetric]
          by (rule Basis_le_norm[OF i])+
        have tria: "norm (y - x)  norm (y - z) + norm (x - z)"
          using dist_triangle[of y x z, unfolded dist_norm]
          unfolding norm_minus_commute
          by auto
        also have " < e / 2 + e / 2"
          using as(4) as(5) by auto
        finally show "norm (f y - f x) < d / real n / 8"
          using as(1) as(2) e(2) by auto
        have "norm (y - z) + norm (x - z) < d / real n / 8 + d / real n / 8"
          using as(4) as(5) by auto
        with tria show "norm (y - x) < 2 * (d / real n / 8)"
          by auto
      qed (use as in auto)
    qed
  qed
  then
  obtain e where e:
    "e > 0"
    "x y z i. x  cbox 0 One 
      y  cbox 0 One 
      z  cbox 0 One 
      i  Basis 
      norm (x - z) < e  norm (y - z) < e  label x i  label y i 
      ¦(f z - z)  i¦ < d / real n"
    by blast
  obtain p :: nat where p: "1 + real n / e  real p"
    using real_arch_simple ..
  have "1 + real n / e > 0"
    using e(1) n by (simp add: add_pos_pos)
  then have "p > 0"
    using p by auto

  obtain b :: "nat  'a" where b: "bij_betw b {..< n} Basis"
    by atomize_elim (auto simp: n_def intro!: finite_same_card_bij)
  define b' where "b' = inv_into {..< n} b"
  then have b': "bij_betw b' Basis {..< n}"
    using bij_betw_inv_into[OF b] by auto
  then have b'_Basis: "i. i  Basis  b' i  {..< n}"
    unfolding bij_betw_def by (auto simp: set_eq_iff)
  have bb'[simp]:"i. i  Basis  b (b' i) = i"
    unfolding b'_def
    using b
    by (auto simp: f_inv_into_f bij_betw_def)
  have b'b[simp]:"i. i < n  b' (b i) = i"
    unfolding b'_def
    using b
    by (auto simp: inv_into_f_eq bij_betw_def)
  have *: "x :: nat. x = 0  x = 1  x  1"
    by auto
  have b'': "j. j < n  b j  Basis"
    using b unfolding bij_betw_def by auto
  have q1: "0 < p" "x. (i<n. x i  p) 
    (i<n. (label (iBasis. (real (x (b' i)) / real p) *R i)  b) i = 0 
           (label (iBasis. (real (x (b' i)) / real p) *R i)  b) i = 1)"
    unfolding *
    using p > 0 n > 0
    using label(1)[OF b'']
    by auto
  { fix x :: "nat  nat" and i assume "i<n. x i  p" "i < n" "x i = p  x i = 0"
    then have "(iBasis. (real (x (b' i)) / real p) *R i)  (cbox 0 One::'a set)"
      using b'_Basis
      by (auto simp: cbox_def bij_betw_def zero_le_divide_iff divide_le_eq_1) }
  note cube = this
  have q2: "x. (i<n. x i  p)  (i<n. x i = 0 
      (label (iBasis. (real (x (b' i)) / real p) *R i)  b) i = 0)"
    unfolding o_def using cube p > 0 by (intro allI impI label(2)) (auto simp: b'')
  have q3: "x. (i<n. x i  p)  (i<n. x i = p 
      (label (iBasis. (real (x (b' i)) / real p) *R i)  b) i = 1)"
    using cube p > 0 unfolding o_def by (intro allI impI label(3)) (auto simp: b'')
  obtain q where q:
      "i<n. q i < p"
      "i<n.
         r s. (j<n. q j  r j  r j  q j + 1) 
               (j<n. q j  s j  s j  q j + 1) 
               (label (iBasis. (real (r (b' i)) / real p) *R i)  b) i 
               (label (iBasis. (real (s (b' i)) / real p) *R i)  b) i"
    by (rule kuhn_lemma[OF q1 q2 q3])
  define z :: 'a where "z = (iBasis. (real (q (b' i)) / real p) *R i)"
  have "iBasis. d / real n  ¦(f z - z)i¦"
  proof (rule ccontr)
    have "iBasis. q (b' i)  {0..p}"
      using q(1) b'
      by (auto intro: less_imp_le simp: bij_betw_def)
    then have "z  cbox 0 One"
      unfolding z_def cbox_def
      using b'_Basis
      by (auto simp: bij_betw_def zero_le_divide_iff divide_le_eq_1)
    then have d_fz_z: "d  norm (f z - z)"
      by (rule d)
    assume "¬ ?thesis"
    then have as: "iBasis. ¦f z  i - z  i¦ < d / real n"
      using n > 0
      by (auto simp: not_le inner_diff)
    have "norm (f z - z)  (iBasis. ¦f z  i - z  i¦)"
      unfolding inner_diff_left[symmetric]
      by (rule norm_le_l1)
    also have " < ((i::'a)  Basis. d / real n)"
      by (meson as finite_Basis nonempty_Basis sum_strict_mono)
    also have " = d"
      using DIM_positive[where 'a='a] by (auto simp: n_def)
    finally show False
      using d_fz_z by auto
  qed
  then obtain i where i: "i  Basis" "d / real n  ¦(f z - z)  i¦" ..
  have *: "b' i < n"
    using i and b'[unfolded bij_betw_def]
    by auto
  obtain r s where rs:
    "j. j < n  q j  r j  r j  q j + 1"
    "j. j < n  q j  s j  s j  q j + 1"
    "(label (iBasis. (real (r (b' i)) / real p) *R i)  b) (b' i) 
      (label (iBasis. (real (s (b' i)) / real p) *R i)  b) (b' i)"
    using q(2)[rule_format,OF *] by blast
  have b'_im: "i. i  Basis   b' i < n"
    using b' unfolding bij_betw_def by auto
  define r' ::'a where "r' = (iBasis. (real (r (b' i)) / real p) *R i)"
  have "i. i  Basis  r (b' i)  p"
    using b'_im q(1) rs(1) by fastforce
  then have "r'  cbox 0 One"
    unfolding r'_def cbox_def
    using b'_Basis
    by (auto simp: bij_betw_def zero_le_divide_iff divide_le_eq_1)
  define s' :: 'a where "s' = (iBasis. (real (s (b' i)) / real p) *R i)"
  have "i. i  Basis  s (b' i)  p"
    using b'_im q(1) rs(2) by fastforce
  then have "s'  cbox 0 One"
    unfolding s'_def cbox_def
    using b'_Basis by (auto simp: bij_betw_def zero_le_divide_iff divide_le_eq_1)
  have "z  cbox 0 One"
    unfolding z_def cbox_def
    using b'_Basis q(1)[rule_format,OF b'_im] p > 0
    by (auto simp: bij_betw_def zero_le_divide_iff divide_le_eq_1 less_imp_le)
  {
    have "(iBasis. ¦real (r (b' i)) - real (q (b' i))¦)  ((i::'a)Basis. 1)"
      by (rule sum_mono) (use rs(1)[OF b'_im] in force)
    also have " < e * real p"
      using p e > 0 p > 0
      by (auto simp: field_simps n_def)
    finally have "(iBasis. ¦real (r (b' i)) - real (q (b' i))¦) < e * real p" .
  }
  moreover
  {
    have "(iBasis. ¦real (s (b' i)) - real (q (b' i))¦)  ((i::'a)Basis. 1)"
      by (rule sum_mono) (use rs(2)[OF b'_im] in force)
    also have " < e * real p"
      using p e > 0 p > 0
      by (auto simp: field_simps n_def)
    finally have "(iBasis. ¦real (s (b' i)) - real (q (b' i))¦) < e * real p" .
  }
  ultimately
  have "norm (r' - z) < e" and "norm (s' - z) < e"
    unfolding r'_def s'_def z_def
    using p > 0
    apply (rule_tac[!] le_less_trans[OF norm_le_l1])
    apply (auto simp: field_simps sum_divide_distrib[symmetric] inner_diff_left)
    done
  then have "¦(f z - z)  i¦ < d / real n"
    using rs(3) i
    unfolding r'_def[symmetric] s'_def[symmetric] o_def bb'
    by (intro e(2)[OF r'cbox 0 One s'cbox 0 One zcbox 0 One]) auto
  then show False
    using i by auto
qed

text ‹Next step is to prove it for nonempty interiors.›

lemma brouwer_weak:
  fixes f :: "'a::euclidean_space  'a"
  assumes "compact S"
    and "convex S"
    and "interior S  {}"
    and "continuous_on S f"
    and "f  S  S"
  obtains x where "x  S" and "f x = x"
proof -
  let ?U = "cbox 0 One :: 'a set"
  have "Basis /R 2  interior ?U"
  proof (rule interiorI)
    let ?I = "(iBasis. {x::'a. 0 < x  i}  {x. x  i < 1})"
    show "open ?I"
      by (intro open_INT finite_Basis ballI open_Int, auto intro: open_Collect_less simp: continuous_on_inner)
    show "Basis /R 2  ?I"
      by simp
    show "?I  cbox 0 One"
      unfolding cbox_def by force
  qed
  then have *: "interior ?U  {}" by fast
  have *: "?U homeomorphic S"
    using homeomorphic_convex_compact[OF convex_box(1) compact_cbox * assms(2,1,3)] .
  have "f. continuous_on ?U f  f  ?U  ?U  (x?U. f x = x)"
    using brouwer_cube by auto
  then show ?thesis
    unfolding homeomorphic_fixpoint_property[OF *]
    using assms
    by (auto intro: that)
qed

text ‹Then the particular case for closed balls.›

lemma brouwer_ball:
  fixes f :: "'a::euclidean_space  'a"
  assumes "e > 0"
    and "continuous_on (cball a e) f"
    and "f  cball a e  cball a e"
  obtains x where "x  cball a e" and "f x = x"
  using brouwer_weak[OF compact_cball convex_cball, of a e f]
  unfolding interior_cball ball_eq_empty
  using assms by auto

text ‹And finally we prove Brouwer's fixed point theorem in its general version.›

theorem brouwer:
  fixes f :: "'a::euclidean_space  'a"
  assumes S: "compact S" "convex S" "S  {}"
    and contf: "continuous_on S f"
    and fim: "f  S  S"
  obtains x where "x  S" and "f x = x"
proof -
  have "e>0. S  cball 0 e"
    using compact_imp_bounded[OF compact S]  unfolding bounded_pos
    by auto
  then obtain e where e: "e > 0" "S  cball 0 e"
    by blast
  have "x cball 0 e. (f  closest_point S) x = x"
  proof (rule_tac brouwer_ball[OF e(1)])
    show "continuous_on (cball 0 e) (f  closest_point S)"
      by (meson assms closest_point_in_set compact_eq_bounded_closed contf continuous_on_closest_point
          continuous_on_compose continuous_on_subset image_subsetI)
    show "f  closest_point S  cball 0 e  cball 0 e"
      by (smt (verit) Pi_iff assms(1) assms(3) closest_point_in_set comp_apply compact_eq_bounded_closed e(2) fim subset_eq)
  qed (use assms in auto)
  then obtain x where x: "x  cball 0 e" "(f  closest_point S) x = x" ..
  with S have "x  S"
    by (metis PiE closest_point_in_set comp_apply compact_imp_closed fim)
  then have *: "closest_point S x = x"
    by (rule closest_point_self)
  show thesis
  proof
    show "closest_point S x  S"
      by (simp add: "*" x  S)
    show "f (closest_point S x) = closest_point S x"
      using "*" x by auto
  qed
qed

subsection ‹Applications›

text ‹So we get the no-retraction theorem.›

corollary no_retraction_cball:
  fixes a :: "'a::euclidean_space"
  assumes "e > 0"
  shows "¬ (frontier (cball a e) retract_of (cball a e))"
proof
  assume *: "frontier (cball a e) retract_of (cball a e)"
  have **: "xa. a - (2 *R a - xa) = - (a - xa)"
    using scaleR_left_distrib[of 1 1 a] by auto
  obtain x where x: "x  {x. norm (a - x) = e}" "2 *R a - x = x"
  proof (rule retract_fixpoint_property[OF *, of "λx. scaleR 2 a - x"])
    show "continuous_on (frontier (cball a e)) ((-) (2 *R a))"
      by (intro continuous_intros)
    show "(-) (2 *R a)  frontier (cball a e)  frontier (cball a e)"
      by clarsimp (metis "**" dist_norm norm_minus_cancel)
  qed (auto simp: dist_norm intro: brouwer_ball[OF assms])
  then have "scaleR 2 a = scaleR 1 x + scaleR 1 x"
    by (auto simp: algebra_simps)
  then have "a = x"
    unfolding scaleR_left_distrib[symmetric] by auto
  then show False
    using x assms by auto
qed

corollary contractible_sphere:
  fixes a :: "'a::euclidean_space"
  shows "contractible(sphere a r)  r  0"
proof (cases "0 < r")
  case True
  then show ?thesis
    unfolding contractible_def nullhomotopic_from_sphere_extension
    using no_retraction_cball [OF True, of a]
    by (auto simp: retract_of_def retraction_def)
next
  case False
  then show ?thesis
    unfolding contractible_def nullhomotopic_from_sphere_extension
    using less_eq_real_def by auto
qed

corollary connected_sphere_eq:
  fixes a :: "'a :: euclidean_space"
  shows "connected(sphere a r)  2  DIM('a)  r  0"
    (is "?lhs = ?rhs")
proof (cases r "0::real" rule: linorder_cases)
  case less
  then show ?thesis by auto
next
  case equal
  then show ?thesis by auto
next
  case greater
  show ?thesis
  proof
    assume L: ?lhs
    have "False" if 1: "DIM('a) = 1"
    proof -
      obtain x y where xy: "sphere a r = {x,y}" "x  y"
        using sphere_1D_doubleton [OF 1 greater]
        by (metis dist_self greater insertI1 less_add_same_cancel1 mem_sphere mult_2 not_le zero_le_dist)
      then have "finite (sphere a r)"
        by auto
      with L r > 0 xy show "False"
        using connected_finite_iff_sing by auto
    qed
    with greater show ?rhs
      by (metis DIM_ge_Suc0 One_nat_def Suc_1 le_antisym not_less_eq_eq)
  next
    assume ?rhs
    then show ?lhs
      using connected_sphere greater by auto
  qed
qed

corollary path_connected_sphere_eq:
  fixes a :: "'a :: euclidean_space"
  shows "path_connected(sphere a r)  2  DIM('a)  r  0"
         (is "?lhs = ?rhs")
proof
  assume ?lhs
  then show ?rhs
    using connected_sphere_eq path_connected_imp_connected by blast
next
  assume R: ?rhs
  then show ?lhs
    by (auto simp: contractible_imp_path_connected contractible_sphere path_connected_sphere)
qed

proposition frontier_subset_retraction:
  fixes S :: "'a::euclidean_space set"
  assumes "bounded S" and fros: "frontier S  T"
      and contf: "continuous_on (closure S) f"
      and fim: "f  S  T"
      and fid: "x. x  T  f x = x"
    shows "S  T"
proof (rule ccontr)
  assume "¬ S  T"
  then obtain a where "a  S" "a  T" by blast
  define g where "g  λz. if z  closure S then f z else z"
  have "continuous_on (closure S  closure(-S)) g"
    unfolding g_def using fros fid frontier_closures
    by (intro continuous_on_cases) (auto simp: contf)
  moreover have "closure S  closure(- S) = UNIV"
    using closure_Un by fastforce
  ultimately have contg: "continuous_on UNIV g" by metis
  obtain B where "0 < B" and B: "closure S  ball a B"
    using bounded S bounded_subset_ballD by blast
  have notga: "g x  a" for x
    unfolding g_def using fros fim a  T
    by (metis PiE Un_iff a  S closure_Un_frontier fid subsetD)
  define h where "h  (λy. a + (B / norm(y - a)) *R (y - a))  g"
  have "¬ (frontier (cball a B) retract_of (cball a B))"
    by (metis no_retraction_cball 0 < B)
  then have "k. ¬ retraction (cball a B) (frontier (cball a B)) k"
    by (simp add: retract_of_def)
  moreover have "retraction (cball a B) (frontier (cball a B)) h"
    unfolding retraction_def
  proof (intro conjI ballI)
    show "frontier (cball a B)  cball a B"
      by force
    show "continuous_on (cball a B) h"
      unfolding h_def
      by (intro continuous_intros) (use contg continuous_on_subset notga in auto)
    show "h  cball a B  frontier (cball a B)"
      using 0 < B by (auto simp: h_def notga dist_norm)
    show "x. x  frontier (cball a B)  h x = x"
      using notga 0 < B
      apply (simp add: g_def h_def field_simps)
      by (metis B dist_commute dist_norm mem_ball order_less_irrefl subset_eq)
  qed
  ultimately show False by simp
qed

subsubsection ‹Punctured affine hulls, etc›

lemma rel_frontier_deformation_retract_of_punctured_convex:
  fixes S :: "'a::euclidean_space set"
  assumes "convex S" "convex T" "bounded S"
      and arelS: "a  rel_interior S"
      and relS: "rel_frontier S  T"
      and affS: "T  affine hull S"
  obtains r where "homotopic_with_canon (λx. True) (T - {a}) (T - {a}) id r"
                  "retraction (T - {a}) (rel_frontier S) r"
proof -
  have "d. 0 < d  (a + d *R l)  rel_frontier S 
            (e. 0  e  e < d  (a + e *R l)  rel_interior S)"
    if "(a + l)  affine hull S" "l  0" for l
    using ray_to_rel_frontier [OF bounded S arelS] that by metis
  then obtain dd
    where dd1: "l. (a + l)  affine hull S; l  0  0 < dd l  (a + dd l *R l)  rel_frontier S"
      and dd2: "l e. (a + l)  affine hull S; e < dd l; 0  e; l  0
                       (a + e *R l)  rel_interior S"
    by metis+
  have aaffS: "a  affine hull S"
    by (meson arelS subsetD hull_inc rel_interior_subset)
  have "((λz. z - a) ` (affine hull S - {a})) = ((λz. z - a) ` (affine hull S)) - {0}"
    by auto
  moreover have "continuous_on (((λz. z - a) ` (affine hull S)) - {0}) (λx. dd x *R x)"
  proof (rule continuous_on_compact_surface_projection)
    show "compact (rel_frontier ((λz. z - a) ` S))"
      by (simp add: bounded S bounded_translation_minus compact_rel_frontier_bounded)
    have releq: "rel_frontier ((λz. z - a) ` S) = (λz. z - a) ` rel_frontier S"
      using rel_frontier_translation [of "-a"] add.commute by simp
    also have "  (λz. z - a) ` (affine hull S) - {0}"
      using rel_frontier_affine_hull arelS rel_frontier_def by fastforce
    finally show "rel_frontier ((λz. z - a) ` S)  (λz. z - a) ` (affine hull S) - {0}" .
    show "cone ((λz. z - a) ` (affine hull S))"
      by (rule subspace_imp_cone)
         (use aaffS in simp add: subspace_affine image_comp o_def affine_translation_aux [of a])
    show "(0 < k  k *R x  rel_frontier ((λz. z - a) ` S))  (dd x = k)"
         if x: "x  (λz. z - a) ` (affine hull S) - {0}" for k x
    proof
      show "dd x = k  0 < k  k *R x  rel_frontier ((λz. z - a) ` S)"
      using dd1 [of x] that image_iff by (fastforce simp add: releq)
    next
      assume k: "0 < k  k *R x  rel_frontier ((λz. z - a) ` S)"
      have False if "dd x < k"
      proof -
        have "k  0" "a + k *R x  closure S"
          using k closure_translation [of "-a"]
          by (auto simp: rel_frontier_def cong: image_cong_simp)
        then have segsub: "open_segment a (a + k *R x)  rel_interior S"
          by (metis rel_interior_closure_convex_segment [OF convex S arelS])
        have "x  0" and xaffS: "a + x  affine hull S"
          using x by auto
        then have "0 < dd x" and inS: "a + dd x *R x  rel_frontier S"
          using dd1 by auto
        moreover have "a + dd x *R x  open_segment a (a + k *R x)"
          unfolding in_segment
        proof (intro conjI exI)
          show "a + dd x *R x = (1 - dd x / k) *R a + (dd x / k) *R (a + k *R x)"
            using k by (simp add: that algebra_simps)
        qed (use x  0 0 < dd x that in auto)
        ultimately show ?thesis
          using segsub by (auto simp: rel_frontier_def)
      qed
      moreover have False if "k < dd x"
        using x k that rel_frontier_def
        by (fastforce simp: algebra_simps releq dest!: dd2)
      ultimately show "dd x = k"
        by fastforce
    qed
  qed
  ultimately have *: "continuous_on ((λz. z - a) ` (affine hull S - {a})) (λx. dd x *R x)"
    by auto
  have "continuous_on (affine hull S - {a}) ((λx. a + dd x *R x)  (λz. z - a))"
    by (intro * continuous_intros continuous_on_compose)
  with affS have contdd: "continuous_on (T - {a}) ((λx. a + dd x *R x)  (λz. z - a))"
    by (blast intro: continuous_on_subset)
  show ?thesis
  proof
    show "homotopic_with_canon (λx. True) (T - {a}) (T - {a}) id (λx. a + dd (x-a) *R (x-a))"
    proof (rule homotopic_with_linear)
      show "continuous_on (T - {a}) id"
        by (intro continuous_intros continuous_on_compose)
      show "continuous_on (T - {a}) (λx. a + dd (x-a) *R (x-a))"
        using contdd by (simp add: o_def)
      show "closed_segment (id x) (a + dd (x-a) *R (x-a))  T - {a}"
           if "x  T - {a}" for x
      proof (clarsimp simp: in_segment, intro conjI)
        fix u::real assume u: "0  u" "u  1"
        have "a + dd (x-a) *R (x-a)  T"
          by (metis DiffD1 DiffD2 add.commute add.right_neutral affS dd1 diff_add_cancel relS singletonI subsetCE that)
        then show "(1 - u) *R x + u *R (a + dd (x-a) *R (x-a))  T"
          using convexD [OF convex T] that u by simp
        have iff: "(1 - u) *R x + u *R (a + d *R (x-a)) = a 
                  (1 - u + u * d) *R (x-a) = 0" for d
          by (auto simp: algebra_simps)
        have "x  T" "x  a" using that by auto
        then have axa: "a + (x-a)  affine hull S"
           by (metis (no_types) add.commute affS diff_add_cancel rev_subsetD)
        then have "¬ dd (x-a)  0  a + dd (x-a) *R (x-a)  rel_frontier S"
          using x  a dd1 by fastforce
        with x  a show "(1 - u) *R x + u *R (a + dd (x-a) *R (x-a))  a"
          using less_eq_real_def mult_le_0_iff not_less u by (fastforce simp: iff)
      qed
    qed
    show "retraction (T - {a}) (rel_frontier S) (λx. a + dd (x-a) *R (x-a))"
    proof (simp add: retraction_def, intro conjI ballI)
      show "rel_frontier S  T - {a}"
        using arelS relS rel_frontier_def by fastforce
      show "continuous_on (T - {a}) (λx. a + dd (x-a) *R (x-a))"
        using contdd by (simp add: o_def)
      show "(λx. a + dd (x-a) *R (x-a))  (T - {a})  rel_frontier S"
        unfolding Pi_iff using affS dd1 subset_eq by force
      show "a + dd (x-a) *R (x-a) = x" if x: "x  rel_frontier S" for x
      proof -
        have "x  a"
          using that arelS by (auto simp: rel_frontier_def)
        have False if "dd (x-a) < 1"
        proof -
          have "x  closure S"
            using x by (auto simp: rel_frontier_def)
          then have segsub: "open_segment a x  rel_interior S"
            by (metis rel_interior_closure_convex_segment [OF convex S arelS])
          have  xaffS: "x  affine hull S"
            using affS relS x by auto
          then have "0 < dd (x-a)" and inS: "a + dd (x-a) *R (x-a)  rel_frontier S"
            using dd1 by (auto simp: x  a)
          moreover have "a + dd (x-a) *R (x-a)  open_segment a x"
            unfolding in_segment
          proof (intro exI conjI)
            show "a + dd (x-a) *R (x-a) = (1 - dd (x-a)) *R a + (dd (x-a)) *R x"
              by (simp add: algebra_simps)
          qed (use  x  a 0 < dd (x-a) that in auto)
          ultimately show ?thesis
            using segsub by (auto simp: rel_frontier_def)
        qed
        moreover have False if "1 < dd (x-a)"
          using x that dd2 [of "x - a" 1] x  a closure_affine_hull
          by (auto simp: rel_frontier_def)
        ultimately have "dd (x-a) = 1" ― ‹similar to another proof above›
          by fastforce
        with that show ?thesis
          by (simp add: rel_frontier_def)
      qed
    qed
  qed
qed

corollary rel_frontier_retract_of_punctured_affine_hull:
  fixes S :: "'a::euclidean_space set"
  assumes "bounded S" "convex S" "a  rel_interior S"
    shows "rel_frontier S retract_of (affine hull S - {a})"
  by (meson assms convex_affine_hull dual_order.refl rel_frontier_affine_hull 
      rel_frontier_deformation_retract_of_punctured_convex retract_of_def)

corollary rel_boundary_retract_of_punctured_affine_hull:
  fixes S :: "'a::euclidean_space set"
  assumes "compact S" "convex S" "a  rel_interior S"
    shows "(S - rel_interior S) retract_of (affine hull S - {a})"
by (metis assms closure_closed compact_eq_bounded_closed rel_frontier_def
          rel_frontier_retract_of_punctured_affine_hull)

lemma homotopy_eqv_rel_frontier_punctured_convex:
  fixes S :: "'a::euclidean_space set"
  assumes "convex S" "bounded S" "a  rel_interior S" "convex T" "rel_frontier S  T" "T  affine hull S"
  shows "(rel_frontier S) homotopy_eqv (T - {a})"
  by (meson assms deformation_retract_imp_homotopy_eqv homotopy_equivalent_space_sym 
      rel_frontier_deformation_retract_of_punctured_convex[of S T])

lemma homotopy_eqv_rel_frontier_punctured_affine_hull:
  fixes S :: "'a::euclidean_space set"
  assumes "convex S" "bounded S" "a  rel_interior S"
    shows "(rel_frontier S) homotopy_eqv (affine hull S - {a})"
  by (simp add: assms homotopy_eqv_rel_frontier_punctured_convex rel_frontier_affine_hull)

lemma path_connected_sphere_gen:
  assumes "convex S" "bounded S" "aff_dim S  1"
  shows "path_connected(rel_frontier S)"
proof -
  have "convex (closure S)" 
    using assms by auto
  then show ?thesis
    by (metis Diff_empty aff_dim_affine_hull assms convex_affine_hull convex_imp_path_connected equals0I 
       path_connected_punctured_convex rel_frontier_def rel_frontier_retract_of_punctured_affine_hull retract_of_path_connected)
qed

lemma connected_sphere_gen:
  assumes "convex S" "bounded S" "aff_dim S  1"
  shows "connected(rel_frontier S)"
  by (simp add: assms path_connected_imp_connected path_connected_sphere_gen)

subsubsection‹Borsuk-style characterization of separation›

lemma continuous_on_Borsuk_map:
   "a  S   continuous_on S (λx. inverse(norm (x-a)) *R (x-a))"
by (rule continuous_intros | force)+

lemma Borsuk_map_into_sphere:
   "(λx. inverse(norm (x-a)) *R (x-a))  S  sphere 0 1  (a  S)"
proof -
  have "x. a  S; x  S  inverse (norm (x-a)) * norm (x-a) = 1"
    by (metis left_inverse norm_eq_zero right_minus_eq)
  then show ?thesis
    by force
qed

lemma Borsuk_maps_homotopic_in_path_component:
  assumes "path_component (- S) a b"
    shows "homotopic_with_canon (λx. True) S (sphere 0 1)
                   (λx. inverse(norm(x-a)) *R (x-a))
                   (λx. inverse(norm(x - b)) *R (x - b))"
proof -
  obtain g where g: "path g" "path_image g  -S" "pathstart g = a" "pathfinish g = b"
    using assms by (auto simp: path_component_def)
  define h where "h  λz. (snd z - (g  fst) z) /R norm (snd z - (g  fst) z)"
  have "continuous_on ({0..1} × S) h"
    unfolding h_def using g by (intro continuous_intros) (auto simp: path_defs)
  moreover
  have "h ` ({0..1} × S)  sphere 0 1"
    unfolding h_def using g  by (auto simp: divide_simps path_defs)
  ultimately show ?thesis
    using g by (auto simp: h_def path_defs homotopic_with_def)
qed

lemma non_extensible_Borsuk_map:
  fixes a :: "'a :: euclidean_space"
  assumes "compact S" and cin: "C  components(- S)" and boc: "bounded C" and "a  C"
    shows "¬ (g. continuous_on (S  C) g 
                  g  (S  C)  sphere 0 1 
                  (x  S. g x = inverse(norm(x-a)) *R (x-a)))"
proof -
  have "closed S" using assms by (simp add: compact_imp_closed)
  have "C  -S"
    using assms by (simp add: in_components_subset)
  with a  C have "a  S" by blast
  then have ceq: "C = connected_component_set (- S) a"
    by (metis a  C cin components_iff connected_component_eq)
  then have "bounded (S  connected_component_set (- S) a)"
    using compact S boc compact_imp_bounded by auto
  with bounded_subset_ballD obtain r where "0 < r" and r: "(S  connected_component_set (- S) a)  ball a r"
    by blast
  { fix g
    assume "continuous_on (S  C) g"
            "g  (S  C)  sphere 0 1"
       and [simp]: "x. x  S  g x = (x-a) /R norm (x-a)"
    then have norm_g1[simp]: "x. x  S  C  norm (g x) = 1"
      by force
    have cb_eq: "cball a r = (S  connected_component_set (- S) a) 
                      (cball a r - connected_component_set (- S) a)"
      using ball_subset_cball [of a r] r by auto
    have cont1: "continuous_on (S  connected_component_set (- S) a)
                     (λx. a + r *R g x)"
      using continuous_on (S  C) g ceq
      by (intro continuous_intros) blast
    have cont2: "continuous_on (cball a r - connected_component_set (- S) a)
            (λx. a + r *R ((x-a) /R norm (x-a)))"
      by (rule continuous_intros | force simp: a  S)+
    have 1: "continuous_on (cball a r)
             (λx. if connected_component (- S) a x
                  then a + r *R g x
                  else a + r *R ((x-a) /R norm (x-a)))"
      apply (subst cb_eq)
      apply (rule continuous_on_cases [OF _ _ cont1 cont2])
      using closed S ceq cin 
      by (force simp: closed_Diff open_Compl closed_Un_complement_component open_connected_component)+
    have 2: "(λx. a + r *R g x) ` (cball a r  connected_component_set (- S) a)
              sphere a r "
      using 0 < r by (force simp: dist_norm ceq)
    have "retraction (cball a r) (sphere a r)
            (λx. if x  connected_component_set (- S) a
                 then a + r *R g x
                 else a + r *R ((x-a) /R norm (x-a)))"
      using  0 < r a  S a  C r
      by (auto simp: norm_minus_commute retraction_def Pi_iff ceq dist_norm abs_if 
          mult_less_0_iff divide_simps 1 2)
    then have False
      using no_retraction_cball
             [OF 0 < r, of a, unfolded retract_of_def, simplified, rule_format,
              of "λx. if x  connected_component_set (- S) a
                      then a + r *R g x
                      else a + r *R inverse(norm(x-a)) *R (x-a)"]
      by blast
  }
  then show ?thesis
    by blast
qed

subsubsection ‹Proving surjectivity via Brouwer fixpoint theorem›

lemma brouwer_surjective:
  fixes f :: "'n::euclidean_space  'n"
  assumes T: "compact T" "convex T" "T  {}"
    and f: "continuous_on T f"
    and "x y. xS; yT  x + (y - f y)  T"
    and "x  S"
  shows "yT. f y = x"
proof -
  have *: "x y. f y = x  x + (y - f y) = y"
    by (auto simp add: algebra_simps)
  show ?thesis
    unfolding *
  proof (rule brouwer[OF T])
    show "continuous_on T (λy. x + (y - f y))"
      by (intro continuous_intros f)
  qed (use assms in auto)
qed

lemma brouwer_surjective_cball:
  fixes f :: "'n::euclidean_space  'n"
  assumes "continuous_on (cball a e) f"
    and "e > 0"
    and "x  S"
    and "x y. xS; ycball a e  x + (y - f y)  cball a e"
  shows "ycball a e. f y = x"
  by (smt (verit, best) assms brouwer_surjective cball_eq_empty compact_cball convex_cball)

subsubsection ‹Inverse function theorem›

text ‹See Sussmann: "Multidifferential calculus", Theorem 2.1.1›

lemma sussmann_open_mapping:
  fixes f :: "'a::real_normed_vector  'b::euclidean_space"
  assumes "open S"
    and contf: "continuous_on S f"
    and "x  S"
    and derf: "(f has_derivative f') (at x)"
    and "bounded_linear g'" "f'  g' = id"
    and "T  S"
    and x: "x  interior T"
  shows "f x  interior (f ` T)"
proof -
  interpret f': bounded_linear f'
    using assms unfolding has_derivative_def by auto
  interpret g': bounded_linear g'
    using assms by auto
  obtain B where B: "0 < B" "x. norm (g' x)  norm x * B"
    using bounded_linear.pos_bounded[OF assms(5)] by blast
  hence *: "1 / (2 * B) > 0" by auto
  obtain e0 where e0:
      "0 < e0"
      "y. norm (y - x) < e0  norm (f y - f x - f' (y - x))  1 / (2 * B) * norm (y - x)"
    using derf unfolding has_derivative_at_alt
    using * by blast
  obtain e1 where e1: "0 < e1" "cball x e1  T"
    using mem_interior_cball x by blast
  have *: "0 < e0 / B" "0 < e1 / B" using e0 e1 B by auto
  obtain e where e: "0 < e" "e < e0 / B" "e < e1 / B"
    using field_lbound_gt_zero[OF *] by blast
  have lem: "ycball (f x) e. f (x + g' (y - f x)) = z" if "zcball (f x) (e / 2)" for z
  proof (rule brouwer_surjective_cball)
    have z: "z  S" if as: "y cball (f x) e" "z = x + (g' y - g' (f x))" for y z
    proof-
      have "dist x z = norm (g' (f x) - g' y)"
        unfolding as(2) and dist_norm by auto
      also have "  norm (f x - y) * B"
        by (metis B(2) g'.diff)
      also have "  e * B"
        by (metis B(1) dist_norm mem_cball mult_le_cancel_right_pos that(1))
      also have "  e1"
        using B(1) e(3) pos_less_divide_eq by fastforce
      finally have "z  cball x e1"
        by force
      then show "z  S"
        using e1 assms(7) by auto
    qed
    show "continuous_on (cball (f x) e) (λy. f (x + g' (y - f x)))"
      unfolding g'.diff
    proof (rule continuous_on_compose2 [OF _ _ order_refl, of _ _ f])
      show "continuous_on ((λy. x + (g' y - g' (f x))) ` cball (f x) e) f"
        by (rule continuous_on_subset[OF contf]) (use z in blast)
      show "continuous_on (cball (f x) e) (λy. x + (g' y - g' (f x)))"
        by (intro continuous_intros linear_continuous_on[OF bounded_linear g'])
    qed
  next
    fix y z
    assume y: "y  cball (f x) (e / 2)" and z: "z  cball (f x) e"
    have "norm (g' (z - f x))  norm (z - f x) * B"
      using B by auto
    also have "  e * B"
      by (metis B(1) z dist_norm mem_cball norm_minus_commute mult_le_cancel_right_pos)
    also have " < e0"
      using B(1) e(2) pos_less_divide_eq by blast
    finally have *: "norm (x + g' (z - f x) - x) < e0"
      by auto
    have **: "f x + f' (x + g' (z - f x) - x) = z"
      using assms(6)[unfolded o_def id_def,THEN cong]
      by auto
    have "norm (f x - (y + (z - f (x + g' (z - f x))))) 
          norm (f (x + g' (z - f x)) - z) + norm (f x - y)"
      using norm_triangle_ineq[of "f (x + g'(z - f x)) - z" "f x - y"]
      by (auto simp add: algebra_simps)
    also have "  1 / (B * 2) * norm (g' (z - f x)) + norm (f x - y)"
      using e0(2)[rule_format, OF *]
      by (simp only: algebra_simps **) auto
    also have "  1 / (B * 2) * norm (g' (z - f x)) + e/2"
      using y by (auto simp: dist_norm)
    also have "  1 / (B * 2) * B * norm (z - f x) + e/2"
      using * B by (auto simp add: field_simps)
    also have "  1 / 2 * norm (z - f x) + e/2"
      by auto
    also have "  e/2 + e/2"
      using B(1) norm (z - f x) * B  e * B by auto
    finally show "y + (z - f (x + g' (z - f x)))  cball (f x) e"
      by (auto simp: dist_norm)
  qed (use e that in auto) 
  show ?thesis
    unfolding mem_interior
  proof (intro exI conjI subsetI)
    fix y
    assume "y  ball (f x) (e / 2)"
    then have *: "y  cball (f x) (e / 2)"
      by auto
    obtain z where z: "z  cball (f x) e" "f (x + g' (z - f x)) = y"
      using lem * by blast
    then have "norm (g' (z - f x))  norm (z - f x) * B"
      using B
      by (auto simp add: field_simps)
    also have "  e * B"
      by (metis B(1) dist_norm mem_cball norm_minus_commute mult_le_cancel_right_pos z(1))
    also have "  e1"
      using e B unfolding less_divide_eq by auto
    finally have "x + g'(z - f x)  T"
      by (metis add_diff_cancel diff_diff_add dist_norm e1(2) mem_cball norm_minus_commute subset_eq)
    then show "y  f ` T"
      using z by auto
  qed (use e in auto)
qed

text ‹Hence the following eccentric variant of the inverse function theorem.
  This has no continuity assumptions, but we do need the inverse function.
  We could put f' ∘ g = I› but this happens to fit with the minimal linear
  algebra theory I've set up so far.›

lemma has_derivative_inverse_strong:
  fixes f :: "'n::euclidean_space  'n"
  assumes S: "open S" "x  S"
    and contf: "continuous_on S f"
    and gf: "x. x  S  g (f x) = x"
    and derf: "(f has_derivative f') (at x)"
    and id: "f'  g' = id"
  shows "(g has_derivative g') (at (f x))"
proof -
  have linf: "bounded_linear f'"
    using derf unfolding has_derivative_def by auto
  then have ling: "bounded_linear g'"
    unfolding linear_conv_bounded_linear[symmetric]
    using id right_inverse_linear by blast
  moreover have "g'  f' = id"
    using id linear_inverse_left linear_linear linf ling by blast
  moreover have *: "T. T  S; x  interior T  f x  interior (f ` T)"
    using S derf contf id ling sussmann_open_mapping by blast
  have "continuous (at (f x)) g"
    unfolding continuous_at Lim_at
  proof (intro strip)
    fix e :: real
    assume "e > 0"
    then have "f x  interior (f ` (ball x e  S))"
      by (simp add: "*" S interior_open)
    then obtain d where d: "0 < d" "ball (f x) d  f ` (ball x e  S)"
      unfolding mem_interior by blast
    show "d>0. y. 0 < dist y (f x)  dist y (f x) < d  dist (g y) (g (f x)) < e"
    proof (intro exI allI impI conjI)
      fix y
      assume "0 < dist y (f x)  dist y (f x) < d"
      then have "g y  g ` f ` (ball x e  S)"
        by (metis d(2) dist_commute mem_ball rev_image_eqI subset_iff)
      then show "dist (g y) (g (f x)) < e"
        using x  S by (simp add: gf dist_commute image_iff)
    qed (use d in auto)
  qed
  moreover have "f x  interior (f ` S)"
    using "*" S interior_eq by blast
  moreover have "f (g y) = y" if "y  interior (f ` S)" for y
    by (metis gf imageE interiorE subsetD that)
  ultimately show ?thesis using assms
    by (metis has_derivative_inverse_basic_x open_interior)
qed

text ‹A rewrite based on the other domain.›

lemma has_derivative_inverse_strong_x:
  fixes f :: "'a::euclidean_space  'a"
  assumes "open S"
    and "g y  S"
    and "continuous_on S f"
    and "x. x  S  g (f x) = x"
    and "(f has_derivative f') (at (g y))"
    and "f'  g' = id"
    and f: "f (g y) = y"
  shows "(g has_derivative g') (at y)"
  using has_derivative_inverse_strong[OF assms(1-6)] by (simp add: f)

text ‹On a region.›

theorem has_derivative_inverse_on:
  fixes f :: "'n::euclidean_space  'n"
  assumes "open S"
    and "x. x  S  (f has_derivative f'(x)) (at x)"
    and "x. x  S  g (f x) = x"
    and "f' x  g' x = id"
    and "x  S"
  shows "(g has_derivative g'(x)) (at (f x))"
  by (meson assms continuous_on_eq_continuous_at has_derivative_continuous has_derivative_inverse_strong)

end