src/HOL/Multivariate_Analysis/Brouwer_Fixpoint.thy
changeset 61945 1135b8de26c3
parent 61808 fc1556774cfe
child 62061 bd2ccef8209b
equal deleted inserted replaced
61944:5d06ecfdb472 61945:1135b8de26c3
  1471     "\<forall>x. \<forall>i\<in>Basis. x \<in> unit_cube \<and> True \<and> label x i = 0 \<longrightarrow> x \<bullet> i \<le> f x \<bullet> i"
  1471     "\<forall>x. \<forall>i\<in>Basis. x \<in> unit_cube \<and> True \<and> label x i = 0 \<longrightarrow> x \<bullet> i \<le> f x \<bullet> i"
  1472     "\<forall>x. \<forall>i\<in>Basis. x \<in> unit_cube \<and> True \<and> label x i = 1 \<longrightarrow> f x \<bullet> i \<le> x \<bullet> i"
  1472     "\<forall>x. \<forall>i\<in>Basis. x \<in> unit_cube \<and> True \<and> label x i = 1 \<longrightarrow> f x \<bullet> i \<le> x \<bullet> i"
  1473     using kuhn_labelling_lemma[OF *] by blast
  1473     using kuhn_labelling_lemma[OF *] by blast
  1474   note label = this [rule_format]
  1474   note label = this [rule_format]
  1475   have lem1: "\<forall>x\<in>unit_cube. \<forall>y\<in>unit_cube. \<forall>i\<in>Basis. label x i \<noteq> label y i \<longrightarrow>
  1475   have lem1: "\<forall>x\<in>unit_cube. \<forall>y\<in>unit_cube. \<forall>i\<in>Basis. label x i \<noteq> label y i \<longrightarrow>
  1476     abs (f x \<bullet> i - x \<bullet> i) \<le> norm (f y - f x) + norm (y - x)"
  1476     \<bar>f x \<bullet> i - x \<bullet> i\<bar> \<le> norm (f y - f x) + norm (y - x)"
  1477   proof safe
  1477   proof safe
  1478     fix x y :: 'a
  1478     fix x y :: 'a
  1479     assume x: "x \<in> unit_cube"
  1479     assume x: "x \<in> unit_cube"
  1480     assume y: "y \<in> unit_cube"
  1480     assume y: "y \<in> unit_cube"
  1481     fix i
  1481     fix i
  1482     assume i: "label x i \<noteq> label y i" "i \<in> Basis"
  1482     assume i: "label x i \<noteq> label y i" "i \<in> Basis"
  1483     have *: "\<And>x y fx fy :: real. x \<le> fx \<and> fy \<le> y \<or> fx \<le> x \<and> y \<le> fy \<Longrightarrow>
  1483     have *: "\<And>x y fx fy :: real. x \<le> fx \<and> fy \<le> y \<or> fx \<le> x \<and> y \<le> fy \<Longrightarrow>
  1484       abs (fx - x) \<le> abs (fy - fx) + abs (y - x)" by auto
  1484       \<bar>fx - x\<bar> \<le> \<bar>fy - fx\<bar> + \<bar>y - x\<bar>" by auto
  1485     have "\<bar>(f x - x) \<bullet> i\<bar> \<le> abs ((f y - f x)\<bullet>i) + abs ((y - x)\<bullet>i)"
  1485     have "\<bar>(f x - x) \<bullet> i\<bar> \<le> \<bar>(f y - f x)\<bullet>i\<bar> + \<bar>(y - x)\<bullet>i\<bar>"
  1486       unfolding inner_simps
  1486       unfolding inner_simps
  1487       apply (rule *)
  1487       apply (rule *)
  1488       apply (cases "label x i = 0")
  1488       apply (cases "label x i = 0")
  1489       apply (rule disjI1)
  1489       apply (rule disjI1)
  1490       apply rule
  1490       apply rule
  1529     finally show "\<bar>f x \<bullet> i - x \<bullet> i\<bar> \<le> norm (f y - f x) + norm (y - x)"
  1529     finally show "\<bar>f x \<bullet> i - x \<bullet> i\<bar> \<le> norm (f y - f x) + norm (y - x)"
  1530       unfolding inner_simps .
  1530       unfolding inner_simps .
  1531   qed
  1531   qed
  1532   have "\<exists>e>0. \<forall>x\<in>unit_cube. \<forall>y\<in>unit_cube. \<forall>z\<in>unit_cube. \<forall>i\<in>Basis.
  1532   have "\<exists>e>0. \<forall>x\<in>unit_cube. \<forall>y\<in>unit_cube. \<forall>z\<in>unit_cube. \<forall>i\<in>Basis.
  1533     norm (x - z) < e \<and> norm (y - z) < e \<and> label x i \<noteq> label y i \<longrightarrow>
  1533     norm (x - z) < e \<and> norm (y - z) < e \<and> label x i \<noteq> label y i \<longrightarrow>
  1534       abs ((f(z) - z)\<bullet>i) < d / (real n)"
  1534       \<bar>(f(z) - z)\<bullet>i\<bar> < d / (real n)"
  1535   proof -
  1535   proof -
  1536     have d': "d / real n / 8 > 0"
  1536     have d': "d / real n / 8 > 0"
  1537       using d(1) by (simp add: n_def DIM_positive)
  1537       using d(1) by (simp add: n_def DIM_positive)
  1538     have *: "uniformly_continuous_on unit_cube f"
  1538     have *: "uniformly_continuous_on unit_cube f"
  1539       by (rule compact_uniformly_continuous[OF assms(1) compact_unit_cube])
  1539       by (rule compact_uniformly_continuous[OF assms(1) compact_unit_cube])
  1557         "x \<in> unit_cube" "y \<in> unit_cube" "z \<in> unit_cube"
  1557         "x \<in> unit_cube" "y \<in> unit_cube" "z \<in> unit_cube"
  1558         "norm (x - z) < min (e / 2) (d / real n / 8)"
  1558         "norm (x - z) < min (e / 2) (d / real n / 8)"
  1559         "norm (y - z) < min (e / 2) (d / real n / 8)"
  1559         "norm (y - z) < min (e / 2) (d / real n / 8)"
  1560         "label x i \<noteq> label y i"
  1560         "label x i \<noteq> label y i"
  1561       assume i: "i \<in> Basis"
  1561       assume i: "i \<in> Basis"
  1562       have *: "\<And>z fz x fx n1 n2 n3 n4 d4 d :: real. abs(fx - x) \<le> n1 + n2 \<Longrightarrow>
  1562       have *: "\<And>z fz x fx n1 n2 n3 n4 d4 d :: real. \<bar>fx - x\<bar> \<le> n1 + n2 \<Longrightarrow>
  1563         abs (fx - fz) \<le> n3 \<Longrightarrow> abs (x - z) \<le> n4 \<Longrightarrow>
  1563         \<bar>fx - fz\<bar> \<le> n3 \<Longrightarrow> \<bar>x - z\<bar> \<le> n4 \<Longrightarrow>
  1564         n1 < d4 \<Longrightarrow> n2 < 2 * d4 \<Longrightarrow> n3 < d4 \<Longrightarrow> n4 < d4 \<Longrightarrow>
  1564         n1 < d4 \<Longrightarrow> n2 < 2 * d4 \<Longrightarrow> n3 < d4 \<Longrightarrow> n4 < d4 \<Longrightarrow>
  1565         (8 * d4 = d) \<Longrightarrow> abs(fz - z) < d"
  1565         (8 * d4 = d) \<Longrightarrow> \<bar>fz - z\<bar> < d"
  1566         by auto
  1566         by auto
  1567       show "\<bar>(f z - z) \<bullet> i\<bar> < d / real n"
  1567       show "\<bar>(f z - z) \<bullet> i\<bar> < d / real n"
  1568         unfolding inner_simps
  1568         unfolding inner_simps
  1569       proof (rule *)
  1569       proof (rule *)
  1570         show "\<bar>f x \<bullet> i - x \<bullet> i\<bar> \<le> norm (f y -f x) + norm (y - x)"
  1570         show "\<bar>f x \<bullet> i - x \<bullet> i\<bar> \<le> norm (f y -f x) + norm (y - x)"
  1667                (\<forall>j<n. q j \<le> s j \<and> s j \<le> q j + 1) \<and>
  1667                (\<forall>j<n. q j \<le> s j \<and> s j \<le> q j + 1) \<and>
  1668                (label (\<Sum>i\<in>Basis. (real (r (b' i)) / real p) *\<^sub>R i) \<circ> b) i \<noteq>
  1668                (label (\<Sum>i\<in>Basis. (real (r (b' i)) / real p) *\<^sub>R i) \<circ> b) i \<noteq>
  1669                (label (\<Sum>i\<in>Basis. (real (s (b' i)) / real p) *\<^sub>R i) \<circ> b) i"
  1669                (label (\<Sum>i\<in>Basis. (real (s (b' i)) / real p) *\<^sub>R i) \<circ> b) i"
  1670     by (rule kuhn_lemma[OF q1 q2 q3])
  1670     by (rule kuhn_lemma[OF q1 q2 q3])
  1671   def z \<equiv> "(\<Sum>i\<in>Basis. (real (q (b' i)) / real p) *\<^sub>R i)::'a"
  1671   def z \<equiv> "(\<Sum>i\<in>Basis. (real (q (b' i)) / real p) *\<^sub>R i)::'a"
  1672   have "\<exists>i\<in>Basis. d / real n \<le> abs ((f z - z)\<bullet>i)"
  1672   have "\<exists>i\<in>Basis. d / real n \<le> \<bar>(f z - z)\<bullet>i\<bar>"
  1673   proof (rule ccontr)
  1673   proof (rule ccontr)
  1674     have "\<forall>i\<in>Basis. q (b' i) \<in> {0..p}"
  1674     have "\<forall>i\<in>Basis. q (b' i) \<in> {0..p}"
  1675       using q(1) b'
  1675       using q(1) b'
  1676       by (auto intro: less_imp_le simp: bij_betw_def)
  1676       by (auto intro: less_imp_le simp: bij_betw_def)
  1677     then have "z \<in> unit_cube"
  1677     then have "z \<in> unit_cube"