src/HOL/Analysis/Fashoda_Theorem.thy
changeset 69681 689997a8a582
parent 69680 96a43caa4902
child 69683 8b3458ca0762
equal deleted inserted replaced
69680:96a43caa4902 69681:689997a8a582
    28 lemma continuous_on_interval_bij: "continuous_on s (interval_bij (a, b) (u, v))"
    28 lemma continuous_on_interval_bij: "continuous_on s (interval_bij (a, b) (u, v))"
    29   apply(rule continuous_at_imp_continuous_on)
    29   apply(rule continuous_at_imp_continuous_on)
    30   apply (rule, rule continuous_interval_bij)
    30   apply (rule, rule continuous_interval_bij)
    31   done
    31   done
    32 
    32 
    33 lemma%important in_interval_interval_bij:
    33 lemma in_interval_interval_bij:
    34   fixes a b u v x :: "'a::euclidean_space"
    34   fixes a b u v x :: "'a::euclidean_space"
    35   assumes "x \<in> cbox a b"
    35   assumes "x \<in> cbox a b"
    36     and "cbox u v \<noteq> {}"
    36     and "cbox u v \<noteq> {}"
    37   shows "interval_bij (a, b) (u, v) x \<in> cbox u v"
    37   shows "interval_bij (a, b) (u, v) x \<in> cbox u v"
    38   apply (simp only: interval_bij_def split_conv mem_box inner_sum_left_Basis cong: ball_cong)
    38   apply (simp only: interval_bij_def split_conv mem_box inner_sum_left_Basis cong: ball_cong)
    39   apply safe
    39   apply safe
    40 proof%unimportant -
    40 proof -
    41   fix i :: 'a
    41   fix i :: 'a
    42   assume i: "i \<in> Basis"
    42   assume i: "i \<in> Basis"
    43   have "cbox a b \<noteq> {}"
    43   have "cbox a b \<noteq> {}"
    44     using assms by auto
    44     using assms by auto
    45   with i have *: "a\<bullet>i \<le> b\<bullet>i" "u\<bullet>i \<le> v\<bullet>i"
    45   with i have *: "a\<bullet>i \<le> b\<bullet>i" "u\<bullet>i \<le> v\<bullet>i"
    87   fixes x :: "real^2"
    87   fixes x :: "real^2"
    88   assumes "infnorm x = 1"
    88   assumes "infnorm x = 1"
    89   shows "\<bar>x$1\<bar> \<le> 1" and "\<bar>x$2\<bar> \<le> 1"
    89   shows "\<bar>x$1\<bar> \<le> 1" and "\<bar>x$2\<bar> \<le> 1"
    90   using assms unfolding infnorm_eq_1_2 by auto
    90   using assms unfolding infnorm_eq_1_2 by auto
    91 
    91 
    92 lemma%important fashoda_unit:
    92 proposition fashoda_unit:
    93   fixes f g :: "real \<Rightarrow> real^2"
    93   fixes f g :: "real \<Rightarrow> real^2"
    94   assumes "f ` {-1 .. 1} \<subseteq> cbox (-1) 1"
    94   assumes "f ` {-1 .. 1} \<subseteq> cbox (-1) 1"
    95     and "g ` {-1 .. 1} \<subseteq> cbox (-1) 1"
    95     and "g ` {-1 .. 1} \<subseteq> cbox (-1) 1"
    96     and "continuous_on {-1 .. 1} f"
    96     and "continuous_on {-1 .. 1} f"
    97     and "continuous_on {-1 .. 1} g"
    97     and "continuous_on {-1 .. 1} g"
    98     and "f (- 1)$1 = - 1"
    98     and "f (- 1)$1 = - 1"
    99     and "f 1$1 = 1" "g (- 1) $2 = -1"
    99     and "f 1$1 = 1" "g (- 1) $2 = -1"
   100     and "g 1 $2 = 1"
   100     and "g 1 $2 = 1"
   101   shows "\<exists>s\<in>{-1 .. 1}. \<exists>t\<in>{-1 .. 1}. f s = g t"
   101   shows "\<exists>s\<in>{-1 .. 1}. \<exists>t\<in>{-1 .. 1}. f s = g t"
   102 proof%unimportant (rule ccontr)
   102 proof (rule ccontr)
   103   assume "\<not> ?thesis"
   103   assume "\<not> ?thesis"
   104   note as = this[unfolded bex_simps,rule_format]
   104   note as = this[unfolded bex_simps,rule_format]
   105   define sqprojection
   105   define sqprojection
   106     where [abs_def]: "sqprojection z = (inverse (infnorm z)) *\<^sub>R z" for z :: "real^2"
   106     where [abs_def]: "sqprojection z = (inverse (infnorm z)) *\<^sub>R z" for z :: "real^2"
   107   define negatex :: "real^2 \<Rightarrow> real^2"
   107   define negatex :: "real^2 \<Rightarrow> real^2"
   254       unfolding iff[OF nz] vector_component_simps * mem_box_cart
   254       unfolding iff[OF nz] vector_component_simps * mem_box_cart
   255       by (erule_tac x=2 in allE) auto
   255       by (erule_tac x=2 in allE) auto
   256   qed 
   256   qed 
   257 qed
   257 qed
   258 
   258 
   259 lemma%important fashoda_unit_path:
   259 proposition fashoda_unit_path:
   260   fixes f g :: "real \<Rightarrow> real^2"
   260   fixes f g :: "real \<Rightarrow> real^2"
   261   assumes "path f"
   261   assumes "path f"
   262     and "path g"
   262     and "path g"
   263     and "path_image f \<subseteq> cbox (-1) 1"
   263     and "path_image f \<subseteq> cbox (-1) 1"
   264     and "path_image g \<subseteq> cbox (-1) 1"
   264     and "path_image g \<subseteq> cbox (-1) 1"
   265     and "(pathstart f)$1 = -1"
   265     and "(pathstart f)$1 = -1"
   266     and "(pathfinish f)$1 = 1"
   266     and "(pathfinish f)$1 = 1"
   267     and "(pathstart g)$2 = -1"
   267     and "(pathstart g)$2 = -1"
   268     and "(pathfinish g)$2 = 1"
   268     and "(pathfinish g)$2 = 1"
   269   obtains z where "z \<in> path_image f" and "z \<in> path_image g"
   269   obtains z where "z \<in> path_image f" and "z \<in> path_image g"
   270 proof%unimportant -
   270 proof -
   271   note assms=assms[unfolded path_def pathstart_def pathfinish_def path_image_def]
   271   note assms=assms[unfolded path_def pathstart_def pathfinish_def path_image_def]
   272   define iscale where [abs_def]: "iscale z = inverse 2 *\<^sub>R (z + 1)" for z :: real
   272   define iscale where [abs_def]: "iscale z = inverse 2 *\<^sub>R (z + 1)" for z :: real
   273   have isc: "iscale ` {- 1..1} \<subseteq> {0..1}"
   273   have isc: "iscale ` {- 1..1} \<subseteq> {0..1}"
   274     unfolding iscale_def by auto
   274     unfolding iscale_def by auto
   275   have "\<exists>s\<in>{- 1..1}. \<exists>t\<in>{- 1..1}. (f \<circ> iscale) s = (g \<circ> iscale) t"
   275   have "\<exists>s\<in>{- 1..1}. \<exists>t\<in>{- 1..1}. (f \<circ> iscale) s = (g \<circ> iscale) t"
   310     using isc[unfolded subset_eq, rule_format]
   310     using isc[unfolded subset_eq, rule_format]
   311     apply auto
   311     apply auto
   312     done
   312     done
   313 qed
   313 qed
   314 
   314 
   315 lemma%important fashoda:
   315 theorem fashoda:
   316   fixes b :: "real^2"
   316   fixes b :: "real^2"
   317   assumes "path f"
   317   assumes "path f"
   318     and "path g"
   318     and "path g"
   319     and "path_image f \<subseteq> cbox a b"
   319     and "path_image f \<subseteq> cbox a b"
   320     and "path_image g \<subseteq> cbox a b"
   320     and "path_image g \<subseteq> cbox a b"
   321     and "(pathstart f)$1 = a$1"
   321     and "(pathstart f)$1 = a$1"
   322     and "(pathfinish f)$1 = b$1"
   322     and "(pathfinish f)$1 = b$1"
   323     and "(pathstart g)$2 = a$2"
   323     and "(pathstart g)$2 = a$2"
   324     and "(pathfinish g)$2 = b$2"
   324     and "(pathfinish g)$2 = b$2"
   325   obtains z where "z \<in> path_image f" and "z \<in> path_image g"
   325   obtains z where "z \<in> path_image f" and "z \<in> path_image g"
   326 proof%unimportant -
   326 proof -
   327   fix P Q S
   327   fix P Q S
   328   presume "P \<or> Q \<or> S" "P \<Longrightarrow> thesis" and "Q \<Longrightarrow> thesis" and "S \<Longrightarrow> thesis"
   328   presume "P \<or> Q \<or> S" "P \<Longrightarrow> thesis" and "Q \<Longrightarrow> thesis" and "S \<Longrightarrow> thesis"
   329   then show thesis
   329   then show thesis
   330     by auto
   330     by auto
   331 next
   331 next
   630 qed
   630 qed
   631 
   631 
   632 
   632 
   633 subsection%important \<open>Useful Fashoda corollary pointed out to me by Tom Hales\<close>(*FIXME change title? *)
   633 subsection%important \<open>Useful Fashoda corollary pointed out to me by Tom Hales\<close>(*FIXME change title? *)
   634 
   634 
   635 lemma%important fashoda_interlace:
   635 corollary fashoda_interlace:
   636   fixes a :: "real^2"
   636   fixes a :: "real^2"
   637   assumes "path f"
   637   assumes "path f"
   638     and "path g"
   638     and "path g"
   639     and paf: "path_image f \<subseteq> cbox a b"
   639     and paf: "path_image f \<subseteq> cbox a b"
   640     and pag: "path_image g \<subseteq> cbox a b"
   640     and pag: "path_image g \<subseteq> cbox a b"
   644     and "(pathfinish g)$2 = a$2"
   644     and "(pathfinish g)$2 = a$2"
   645     and "(pathstart f)$1 < (pathstart g)$1"
   645     and "(pathstart f)$1 < (pathstart g)$1"
   646     and "(pathstart g)$1 < (pathfinish f)$1"
   646     and "(pathstart g)$1 < (pathfinish f)$1"
   647     and "(pathfinish f)$1 < (pathfinish g)$1"
   647     and "(pathfinish f)$1 < (pathfinish g)$1"
   648   obtains z where "z \<in> path_image f" and "z \<in> path_image g"
   648   obtains z where "z \<in> path_image f" and "z \<in> path_image g"
   649 proof%unimportant -
   649 proof -
   650   have "cbox a b \<noteq> {}"
   650   have "cbox a b \<noteq> {}"
   651     using path_image_nonempty[of f] using assms(3) by auto
   651     using path_image_nonempty[of f] using assms(3) by auto
   652   note ab=this[unfolded interval_eq_empty_cart not_ex forall_2 not_less]
   652   note ab=this[unfolded interval_eq_empty_cart not_ex forall_2 not_less]
   653   have "pathstart f \<in> cbox a b"
   653   have "pathstart f \<in> cbox a b"
   654     and "pathfinish f \<in> cbox a b"
   654     and "pathfinish f \<in> cbox a b"