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" |