src/HOL/Analysis/Extended_Real_Limits.thy
changeset 69677 a06b204527e6
parent 69661 a03a63b81f44
child 69680 96a43caa4902
equal deleted inserted replaced
69661:a03a63b81f44 69677:a06b204527e6
    14   "HOL-Library.Extended_Real"
    14   "HOL-Library.Extended_Real"
    15   "HOL-Library.Extended_Nonnegative_Real"
    15   "HOL-Library.Extended_Nonnegative_Real"
    16   "HOL-Library.Indicator_Function"
    16   "HOL-Library.Indicator_Function"
    17 begin
    17 begin
    18 
    18 
    19 lemma%important compact_UNIV:
    19 lemma compact_UNIV:
    20   "compact (UNIV :: 'a::{complete_linorder,linorder_topology,second_countable_topology} set)"
    20   "compact (UNIV :: 'a::{complete_linorder,linorder_topology,second_countable_topology} set)"
    21   using%unimportant compact_complete_linorder
    21   using compact_complete_linorder
    22   by (auto simp: seq_compact_eq_compact[symmetric] seq_compact_def)
    22   by (auto simp: seq_compact_eq_compact[symmetric] seq_compact_def)
    23 
    23 
    24 lemma%important compact_eq_closed:
    24 lemma compact_eq_closed:
    25   fixes S :: "'a::{complete_linorder,linorder_topology,second_countable_topology} set"
    25   fixes S :: "'a::{complete_linorder,linorder_topology,second_countable_topology} set"
    26   shows "compact S \<longleftrightarrow> closed S"
    26   shows "compact S \<longleftrightarrow> closed S"
    27   using%unimportant closed_Int_compact[of S, OF _ compact_UNIV] compact_imp_closed
    27   using%unimportant closed_Int_compact[of S, OF _ compact_UNIV] compact_imp_closed
    28   by auto
    28   by auto
    29 
    29 
    30 lemma%important closed_contains_Sup_cl:
    30 lemma closed_contains_Sup_cl:
    31   fixes S :: "'a::{complete_linorder,linorder_topology,second_countable_topology} set"
    31   fixes S :: "'a::{complete_linorder,linorder_topology,second_countable_topology} set"
    32   assumes "closed S"
    32   assumes "closed S"
    33     and "S \<noteq> {}"
    33     and "S \<noteq> {}"
    34   shows "Sup S \<in> S"
    34   shows "Sup S \<in> S"
    35 proof%unimportant -
    35 proof -
    36   from compact_eq_closed[of S] compact_attains_sup[of S] assms
    36   from compact_eq_closed[of S] compact_attains_sup[of S] assms
    37   obtain s where S: "s \<in> S" "\<forall>t\<in>S. t \<le> s"
    37   obtain s where S: "s \<in> S" "\<forall>t\<in>S. t \<le> s"
    38     by auto
    38     by auto
    39   then have "Sup S = s"
    39   then have "Sup S = s"
    40     by (auto intro!: Sup_eqI)
    40     by (auto intro!: Sup_eqI)
    41   with S show ?thesis
    41   with S show ?thesis
    42     by simp
    42     by simp
    43 qed
    43 qed
    44 
    44 
    45 lemma%important closed_contains_Inf_cl:
    45 lemma closed_contains_Inf_cl:
    46   fixes S :: "'a::{complete_linorder,linorder_topology,second_countable_topology} set"
    46   fixes S :: "'a::{complete_linorder,linorder_topology,second_countable_topology} set"
    47   assumes "closed S"
    47   assumes "closed S"
    48     and "S \<noteq> {}"
    48     and "S \<noteq> {}"
    49   shows "Inf S \<in> S"
    49   shows "Inf S \<in> S"
    50 proof%unimportant -
    50 proof -
    51   from compact_eq_closed[of S] compact_attains_inf[of S] assms
    51   from compact_eq_closed[of S] compact_attains_inf[of S] assms
    52   obtain s where S: "s \<in> S" "\<forall>t\<in>S. s \<le> t"
    52   obtain s where S: "s \<in> S" "\<forall>t\<in>S. s \<le> t"
    53     by auto
    53     by auto
    54   then have "Inf S = s"
    54   then have "Inf S = s"
    55     by (auto intro!: Inf_eqI)
    55     by (auto intro!: Inf_eqI)
    56   with S show ?thesis
    56   with S show ?thesis
    57     by simp
    57     by simp
    58 qed
    58 qed
    59 
    59 
    60 instance enat :: second_countable_topology
    60 instance%unimportant enat :: second_countable_topology
    61 proof
    61 proof
    62   show "\<exists>B::enat set set. countable B \<and> open = generate_topology B"
    62   show "\<exists>B::enat set set. countable B \<and> open = generate_topology B"
    63   proof (intro exI conjI)
    63   proof (intro exI conjI)
    64     show "countable (range lessThan \<union> range greaterThan::enat set set)"
    64     show "countable (range lessThan \<union> range greaterThan::enat set set)"
    65       by auto
    65       by auto
    66   qed (simp add: open_enat_def)
    66   qed (simp add: open_enat_def)
    67 qed
    67 qed
    68 
    68 
    69 instance%important ereal :: second_countable_topology
    69 instance%unimportant ereal :: second_countable_topology
    70 proof%unimportant (standard, intro exI conjI)
    70 proof (standard, intro exI conjI)
    71   let ?B = "(\<Union>r\<in>\<rat>. {{..< r}, {r <..}} :: ereal set set)"
    71   let ?B = "(\<Union>r\<in>\<rat>. {{..< r}, {r <..}} :: ereal set set)"
    72   show "countable ?B"
    72   show "countable ?B"
    73     by (auto intro: countable_rat)
    73     by (auto intro: countable_rat)
    74   show "open = generate_topology ?B"
    74   show "open = generate_topology ?B"
    75   proof (intro ext iffI)
    75   proof (intro ext iffI)
    96   qed
    96   qed
    97 qed
    97 qed
    98 
    98 
    99 text \<open>This is a copy from \<open>ereal :: second_countable_topology\<close>. Maybe find a common super class of
    99 text \<open>This is a copy from \<open>ereal :: second_countable_topology\<close>. Maybe find a common super class of
   100 topological spaces where the rational numbers are densely embedded ?\<close>
   100 topological spaces where the rational numbers are densely embedded ?\<close>
   101 instance%important ennreal :: second_countable_topology
   101 instance ennreal :: second_countable_topology
   102 proof%unimportant (standard, intro exI conjI)
   102 proof (standard, intro exI conjI)
   103   let ?B = "(\<Union>r\<in>\<rat>. {{..< r}, {r <..}} :: ennreal set set)"
   103   let ?B = "(\<Union>r\<in>\<rat>. {{..< r}, {r <..}} :: ennreal set set)"
   104   show "countable ?B"
   104   show "countable ?B"
   105     by (auto intro: countable_rat)
   105     by (auto intro: countable_rat)
   106   show "open = generate_topology ?B"
   106   show "open = generate_topology ?B"
   107   proof (intro ext iffI)
   107   proof (intro ext iffI)
   126     then show "open S"
   126     then show "open S"
   127       by induct auto
   127       by induct auto
   128   qed
   128   qed
   129 qed
   129 qed
   130 
   130 
   131 lemma%important ereal_open_closed_aux:
   131 lemma ereal_open_closed_aux:
   132   fixes S :: "ereal set"
   132   fixes S :: "ereal set"
   133   assumes "open S"
   133   assumes "open S"
   134     and "closed S"
   134     and "closed S"
   135     and S: "(-\<infinity>) \<notin> S"
   135     and S: "(-\<infinity>) \<notin> S"
   136   shows "S = {}"
   136   shows "S = {}"
   137 proof%unimportant (rule ccontr)
   137 proof (rule ccontr)
   138   assume "\<not> ?thesis"
   138   assume "\<not> ?thesis"
   139   then have *: "Inf S \<in> S"
   139   then have *: "Inf S \<in> S"
   140 
   140 
   141     by (metis assms(2) closed_contains_Inf_cl)
   141     by (metis assms(2) closed_contains_Inf_cl)
   142   {
   142   {
   170   }
   170   }
   171   ultimately show False
   171   ultimately show False
   172     by auto
   172     by auto
   173 qed
   173 qed
   174 
   174 
   175 lemma%important ereal_open_closed:
   175 lemma ereal_open_closed:
   176   fixes S :: "ereal set"
   176   fixes S :: "ereal set"
   177   shows "open S \<and> closed S \<longleftrightarrow> S = {} \<or> S = UNIV"
   177   shows "open S \<and> closed S \<longleftrightarrow> S = {} \<or> S = UNIV"
   178 proof%unimportant -
   178 proof -
   179   {
   179   {
   180     assume lhs: "open S \<and> closed S"
   180     assume lhs: "open S \<and> closed S"
   181     {
   181     {
   182       assume "-\<infinity> \<notin> S"
   182       assume "-\<infinity> \<notin> S"
   183       then have "S = {}"
   183       then have "S = {}"
   194   }
   194   }
   195   then show ?thesis
   195   then show ?thesis
   196     by auto
   196     by auto
   197 qed
   197 qed
   198 
   198 
   199 lemma%important ereal_open_atLeast:
   199 lemma ereal_open_atLeast:
   200   fixes x :: ereal
   200   fixes x :: ereal
   201   shows "open {x..} \<longleftrightarrow> x = -\<infinity>"
   201   shows "open {x..} \<longleftrightarrow> x = -\<infinity>"
   202 proof%unimportant
   202 proof
   203   assume "x = -\<infinity>"
   203   assume "x = -\<infinity>"
   204   then have "{x..} = UNIV"
   204   then have "{x..} = UNIV"
   205     by auto
   205     by auto
   206   then show "open {x..}"
   206   then show "open {x..}"
   207     by auto
   207     by auto
   213     unfolding ereal_open_closed by auto
   213     unfolding ereal_open_closed by auto
   214   then show "x = -\<infinity>"
   214   then show "x = -\<infinity>"
   215     by (simp add: bot_ereal_def atLeast_eq_UNIV_iff)
   215     by (simp add: bot_ereal_def atLeast_eq_UNIV_iff)
   216 qed
   216 qed
   217 
   217 
   218 lemma%important mono_closed_real:
   218 lemma mono_closed_real:
   219   fixes S :: "real set"
   219   fixes S :: "real set"
   220   assumes mono: "\<forall>y z. y \<in> S \<and> y \<le> z \<longrightarrow> z \<in> S"
   220   assumes mono: "\<forall>y z. y \<in> S \<and> y \<le> z \<longrightarrow> z \<in> S"
   221     and "closed S"
   221     and "closed S"
   222   shows "S = {} \<or> S = UNIV \<or> (\<exists>a. S = {a..})"
   222   shows "S = {} \<or> S = UNIV \<or> (\<exists>a. S = {a..})"
   223 proof%unimportant -
   223 proof -
   224   {
   224   {
   225     assume "S \<noteq> {}"
   225     assume "S \<noteq> {}"
   226     { assume ex: "\<exists>B. \<forall>x\<in>S. B \<le> x"
   226     { assume ex: "\<exists>B. \<forall>x\<in>S. B \<le> x"
   227       then have *: "\<forall>x\<in>S. Inf S \<le> x"
   227       then have *: "\<forall>x\<in>S. Inf S \<le> x"
   228         using cInf_lower[of _ S] ex by (metis bdd_below_def)
   228         using cInf_lower[of _ S] ex by (metis bdd_below_def)
   259   }
   259   }
   260   then show ?thesis
   260   then show ?thesis
   261     by blast
   261     by blast
   262 qed
   262 qed
   263 
   263 
   264 lemma%important mono_closed_ereal:
   264 lemma mono_closed_ereal:
   265   fixes S :: "real set"
   265   fixes S :: "real set"
   266   assumes mono: "\<forall>y z. y \<in> S \<and> y \<le> z \<longrightarrow> z \<in> S"
   266   assumes mono: "\<forall>y z. y \<in> S \<and> y \<le> z \<longrightarrow> z \<in> S"
   267     and "closed S"
   267     and "closed S"
   268   shows "\<exists>a. S = {x. a \<le> ereal x}"
   268   shows "\<exists>a. S = {x. a \<le> ereal x}"
   269 proof%unimportant -
   269 proof -
   270   {
   270   {
   271     assume "S = {}"
   271     assume "S = {}"
   272     then have ?thesis
   272     then have ?thesis
   273       apply (rule_tac x=PInfty in exI)
   273       apply (rule_tac x=PInfty in exI)
   274       apply auto
   274       apply auto
   294   }
   294   }
   295   ultimately show ?thesis
   295   ultimately show ?thesis
   296     using mono_closed_real[of S] assms by auto
   296     using mono_closed_real[of S] assms by auto
   297 qed
   297 qed
   298 
   298 
   299 lemma%important Liminf_within:
   299 lemma Liminf_within:
   300   fixes f :: "'a::metric_space \<Rightarrow> 'b::complete_lattice"
   300   fixes f :: "'a::metric_space \<Rightarrow> 'b::complete_lattice"
   301   shows "Liminf (at x within S) f = (SUP e\<in>{0<..}. INF y\<in>(S \<inter> ball x e - {x}). f y)"
   301   shows "Liminf (at x within S) f = (SUP e\<in>{0<..}. INF y\<in>(S \<inter> ball x e - {x}). f y)"
   302   unfolding Liminf_def eventually_at
   302   unfolding Liminf_def eventually_at
   303 proof%unimportant (rule SUP_eq, simp_all add: Ball_def Bex_def, safe)
   303 proof (rule SUP_eq, simp_all add: Ball_def Bex_def, safe)
   304   fix P d
   304   fix P d
   305   assume "0 < d" and "\<forall>y. y \<in> S \<longrightarrow> y \<noteq> x \<and> dist y x < d \<longrightarrow> P y"
   305   assume "0 < d" and "\<forall>y. y \<in> S \<longrightarrow> y \<noteq> x \<and> dist y x < d \<longrightarrow> P y"
   306   then have "S \<inter> ball x d - {x} \<subseteq> {x. P x}"
   306   then have "S \<inter> ball x d - {x} \<subseteq> {x. P x}"
   307     by (auto simp: zero_less_dist_iff dist_commute)
   307     by (auto simp: zero_less_dist_iff dist_commute)
   308   then show "\<exists>r>0. Inf (f ` (Collect P)) \<le> Inf (f ` (S \<inter> ball x r - {x}))"
   308   then show "\<exists>r>0. Inf (f ` (Collect P)) \<le> Inf (f ` (S \<inter> ball x r - {x}))"
   314     Inf (f ` (S \<inter> ball x d - {x})) \<le> Inf (f ` (Collect P))"
   314     Inf (f ` (S \<inter> ball x d - {x})) \<le> Inf (f ` (Collect P))"
   315     by (intro exI[of _ "\<lambda>y. y \<in> S \<inter> ball x d - {x}"])
   315     by (intro exI[of _ "\<lambda>y. y \<in> S \<inter> ball x d - {x}"])
   316        (auto intro!: INF_mono exI[of _ d] simp: dist_commute)
   316        (auto intro!: INF_mono exI[of _ d] simp: dist_commute)
   317 qed
   317 qed
   318 
   318 
   319 lemma%important Limsup_within:
   319 lemma Limsup_within:
   320   fixes f :: "'a::metric_space \<Rightarrow> 'b::complete_lattice"
   320   fixes f :: "'a::metric_space \<Rightarrow> 'b::complete_lattice"
   321   shows "Limsup (at x within S) f = (INF e\<in>{0<..}. SUP y\<in>(S \<inter> ball x e - {x}). f y)"
   321   shows "Limsup (at x within S) f = (INF e\<in>{0<..}. SUP y\<in>(S \<inter> ball x e - {x}). f y)"
   322   unfolding Limsup_def eventually_at
   322   unfolding Limsup_def eventually_at
   323 proof%unimportant (rule INF_eq, simp_all add: Ball_def Bex_def, safe)
   323 proof (rule INF_eq, simp_all add: Ball_def Bex_def, safe)
   324   fix P d
   324   fix P d
   325   assume "0 < d" and "\<forall>y. y \<in> S \<longrightarrow> y \<noteq> x \<and> dist y x < d \<longrightarrow> P y"
   325   assume "0 < d" and "\<forall>y. y \<in> S \<longrightarrow> y \<noteq> x \<and> dist y x < d \<longrightarrow> P y"
   326   then have "S \<inter> ball x d - {x} \<subseteq> {x. P x}"
   326   then have "S \<inter> ball x d - {x} \<subseteq> {x. P x}"
   327     by (auto simp: zero_less_dist_iff dist_commute)
   327     by (auto simp: zero_less_dist_iff dist_commute)
   328   then show "\<exists>r>0. Sup (f ` (S \<inter> ball x r - {x})) \<le> Sup (f ` (Collect P))"
   328   then show "\<exists>r>0. Sup (f ` (S \<inter> ball x r - {x})) \<le> Sup (f ` (Collect P))"
   355   apply auto
   355   apply auto
   356   apply (metis (no_types, lifting) INF_insert centre_in_ball greaterThan_iff image_cong inf_commute insert_Diff)
   356   apply (metis (no_types, lifting) INF_insert centre_in_ball greaterThan_iff image_cong inf_commute insert_Diff)
   357   done
   357   done
   358 
   358 
   359 
   359 
   360 subsection%important \<open>Extended-Real.thy\<close> (*FIX title *)
   360 subsection%important \<open>Extended-Real.thy\<close> (*FIX ME change title *)
   361 
   361 
   362 lemma sum_constant_ereal:
   362 lemma sum_constant_ereal:
   363   fixes a::ereal
   363   fixes a::ereal
   364   shows "(\<Sum>i\<in>I. a) = a * card I"
   364   shows "(\<Sum>i\<in>I. a) = a * card I"
   365 apply (cases "finite I", induct set: finite, simp_all)
   365 apply (cases "finite I", induct set: finite, simp_all)
   375   ultimately have "eventually (\<lambda>n. u n \<in> {-\<infinity><..<(\<infinity>::ereal)}) F" using assms tendsto_def by blast
   375   ultimately have "eventually (\<lambda>n. u n \<in> {-\<infinity><..<(\<infinity>::ereal)}) F" using assms tendsto_def by blast
   376   moreover have "\<And>x. x \<in> {-\<infinity><..<(\<infinity>::ereal)} \<Longrightarrow> x = ereal(real_of_ereal x)" using ereal_real by auto
   376   moreover have "\<And>x. x \<in> {-\<infinity><..<(\<infinity>::ereal)} \<Longrightarrow> x = ereal(real_of_ereal x)" using ereal_real by auto
   377   ultimately show ?thesis by (metis (mono_tags, lifting) eventually_mono)
   377   ultimately show ?thesis by (metis (mono_tags, lifting) eventually_mono)
   378 qed
   378 qed
   379 
   379 
   380 lemma%important ereal_Inf_cmult:
   380 lemma ereal_Inf_cmult:
   381   assumes "c>(0::real)"
   381   assumes "c>(0::real)"
   382   shows "Inf {ereal c * x |x. P x} = ereal c * Inf {x. P x}"
   382   shows "Inf {ereal c * x |x. P x} = ereal c * Inf {x. P x}"
   383 proof%unimportant -
   383 proof -
   384   have "(\<lambda>x::ereal. c * x) (Inf {x::ereal. P x}) = Inf ((\<lambda>x::ereal. c * x)`{x::ereal. P x})"
   384   have "(\<lambda>x::ereal. c * x) (Inf {x::ereal. P x}) = Inf ((\<lambda>x::ereal. c * x)`{x::ereal. P x})"
   385     apply (rule mono_bij_Inf)
   385     apply (rule mono_bij_Inf)
   386     apply (simp add: assms ereal_mult_left_mono less_imp_le mono_def)
   386     apply (simp add: assms ereal_mult_left_mono less_imp_le mono_def)
   387     apply (rule bij_betw_byWitness[of _ "\<lambda>x. (x::ereal) / c"], auto simp add: assms ereal_mult_divide)
   387     apply (rule bij_betw_byWitness[of _ "\<lambda>x. (x::ereal) / c"], auto simp add: assms ereal_mult_divide)
   388     using assms ereal_divide_eq apply auto
   388     using assms ereal_divide_eq apply auto
   397 in \<open>tendsto_add_ereal_general\<close> which essentially says that the addition
   397 in \<open>tendsto_add_ereal_general\<close> which essentially says that the addition
   398 is continuous on ereal times ereal, except at \<open>(-\<infinity>, \<infinity>)\<close> and \<open>(\<infinity>, -\<infinity>)\<close>.
   398 is continuous on ereal times ereal, except at \<open>(-\<infinity>, \<infinity>)\<close> and \<open>(\<infinity>, -\<infinity>)\<close>.
   399 It is much more convenient in many situations, see for instance the proof of
   399 It is much more convenient in many situations, see for instance the proof of
   400 \<open>tendsto_sum_ereal\<close> below.\<close>
   400 \<open>tendsto_sum_ereal\<close> below.\<close>
   401 
   401 
   402 lemma%important tendsto_add_ereal_PInf:
   402 lemma tendsto_add_ereal_PInf:
   403   fixes y :: ereal
   403   fixes y :: ereal
   404   assumes y: "y \<noteq> -\<infinity>"
   404   assumes y: "y \<noteq> -\<infinity>"
   405   assumes f: "(f \<longlongrightarrow> \<infinity>) F" and g: "(g \<longlongrightarrow> y) F"
   405   assumes f: "(f \<longlongrightarrow> \<infinity>) F" and g: "(g \<longlongrightarrow> y) F"
   406   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> \<infinity>) F"
   406   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> \<infinity>) F"
   407 proof%unimportant -
   407 proof -
   408   have "\<exists>C. eventually (\<lambda>x. g x > ereal C) F"
   408   have "\<exists>C. eventually (\<lambda>x. g x > ereal C) F"
   409   proof (cases y)
   409   proof (cases y)
   410     case (real r)
   410     case (real r)
   411     have "y > y-1" using y real by (simp add: ereal_between(1))
   411     have "y > y-1" using y real by (simp add: ereal_between(1))
   412     then have "eventually (\<lambda>x. g x > y - 1) F" using g y order_tendsto_iff by auto
   412     then have "eventually (\<lambda>x. g x > y - 1) F" using g y order_tendsto_iff by auto
   435 
   435 
   436 text\<open>One would like to deduce the next lemma from the previous one, but the fact
   436 text\<open>One would like to deduce the next lemma from the previous one, but the fact
   437 that \<open>- (x + y)\<close> is in general different from \<open>(- x) + (- y)\<close> in ereal creates difficulties,
   437 that \<open>- (x + y)\<close> is in general different from \<open>(- x) + (- y)\<close> in ereal creates difficulties,
   438 so it is more efficient to copy the previous proof.\<close>
   438 so it is more efficient to copy the previous proof.\<close>
   439 
   439 
   440 lemma%important tendsto_add_ereal_MInf:
   440 lemma tendsto_add_ereal_MInf:
   441   fixes y :: ereal
   441   fixes y :: ereal
   442   assumes y: "y \<noteq> \<infinity>"
   442   assumes y: "y \<noteq> \<infinity>"
   443   assumes f: "(f \<longlongrightarrow> -\<infinity>) F" and g: "(g \<longlongrightarrow> y) F"
   443   assumes f: "(f \<longlongrightarrow> -\<infinity>) F" and g: "(g \<longlongrightarrow> y) F"
   444   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> -\<infinity>) F"
   444   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> -\<infinity>) F"
   445 proof%unimportant -
   445 proof -
   446   have "\<exists>C. eventually (\<lambda>x. g x < ereal C) F"
   446   have "\<exists>C. eventually (\<lambda>x. g x < ereal C) F"
   447   proof (cases y)
   447   proof (cases y)
   448     case (real r)
   448     case (real r)
   449     have "y < y+1" using y real by (simp add: ereal_between(1))
   449     have "y < y+1" using y real by (simp add: ereal_between(1))
   450     then have "eventually (\<lambda>x. g x < y + 1) F" using g y order_tendsto_iff by force
   450     then have "eventually (\<lambda>x. g x < y + 1) F" using g y order_tendsto_iff by force
   468     ultimately have "eventually (\<lambda>x. f x + g x < ereal M) F" using eventually_mono by force
   468     ultimately have "eventually (\<lambda>x. f x + g x < ereal M) F" using eventually_mono by force
   469   }
   469   }
   470   then show ?thesis by (simp add: tendsto_MInfty)
   470   then show ?thesis by (simp add: tendsto_MInfty)
   471 qed
   471 qed
   472 
   472 
   473 lemma%important tendsto_add_ereal_general1:
   473 lemma tendsto_add_ereal_general1:
   474   fixes x y :: ereal
   474   fixes x y :: ereal
   475   assumes y: "\<bar>y\<bar> \<noteq> \<infinity>"
   475   assumes y: "\<bar>y\<bar> \<noteq> \<infinity>"
   476   assumes f: "(f \<longlongrightarrow> x) F" and g: "(g \<longlongrightarrow> y) F"
   476   assumes f: "(f \<longlongrightarrow> x) F" and g: "(g \<longlongrightarrow> y) F"
   477   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> x + y) F"
   477   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> x + y) F"
   478 proof%unimportant (cases x)
   478 proof (cases x)
   479   case (real r)
   479   case (real r)
   480   have a: "\<bar>x\<bar> \<noteq> \<infinity>" by (simp add: real)
   480   have a: "\<bar>x\<bar> \<noteq> \<infinity>" by (simp add: real)
   481   show ?thesis by (rule tendsto_add_ereal[OF a, OF y, OF f, OF g])
   481   show ?thesis by (rule tendsto_add_ereal[OF a, OF y, OF f, OF g])
   482 next
   482 next
   483   case PInf
   483   case PInf
   486   case MInf
   486   case MInf
   487   then show ?thesis using tendsto_add_ereal_MInf assms
   487   then show ?thesis using tendsto_add_ereal_MInf assms
   488     by (metis abs_ereal.simps(3) ereal_MInfty_eq_plus)
   488     by (metis abs_ereal.simps(3) ereal_MInfty_eq_plus)
   489 qed
   489 qed
   490 
   490 
   491 lemma%important tendsto_add_ereal_general2:
   491 lemma tendsto_add_ereal_general2:
   492   fixes x y :: ereal
   492   fixes x y :: ereal
   493   assumes x: "\<bar>x\<bar> \<noteq> \<infinity>"
   493   assumes x: "\<bar>x\<bar> \<noteq> \<infinity>"
   494       and f: "(f \<longlongrightarrow> x) F" and g: "(g \<longlongrightarrow> y) F"
   494       and f: "(f \<longlongrightarrow> x) F" and g: "(g \<longlongrightarrow> y) F"
   495   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> x + y) F"
   495   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> x + y) F"
   496 proof%unimportant -
   496 proof -
   497   have "((\<lambda>x. g x + f x) \<longlongrightarrow> x + y) F"
   497   have "((\<lambda>x. g x + f x) \<longlongrightarrow> x + y) F"
   498     using tendsto_add_ereal_general1[OF x, OF g, OF f] add.commute[of "y", of "x"] by simp
   498     using tendsto_add_ereal_general1[OF x, OF g, OF f] add.commute[of "y", of "x"] by simp
   499   moreover have "\<And>x. g x + f x = f x + g x" using add.commute by auto
   499   moreover have "\<And>x. g x + f x = f x + g x" using add.commute by auto
   500   ultimately show ?thesis by simp
   500   ultimately show ?thesis by simp
   501 qed
   501 qed
   502 
   502 
   503 text \<open>The next lemma says that the addition is continuous on \<open>ereal\<close>, except at
   503 text \<open>The next lemma says that the addition is continuous on \<open>ereal\<close>, except at
   504 the pairs \<open>(-\<infinity>, \<infinity>)\<close> and \<open>(\<infinity>, -\<infinity>)\<close>.\<close>
   504 the pairs \<open>(-\<infinity>, \<infinity>)\<close> and \<open>(\<infinity>, -\<infinity>)\<close>.\<close>
   505 
   505 
   506 lemma%important tendsto_add_ereal_general [tendsto_intros]:
   506 lemma tendsto_add_ereal_general [tendsto_intros]:
   507   fixes x y :: ereal
   507   fixes x y :: ereal
   508   assumes "\<not>((x=\<infinity> \<and> y=-\<infinity>) \<or> (x=-\<infinity> \<and> y=\<infinity>))"
   508   assumes "\<not>((x=\<infinity> \<and> y=-\<infinity>) \<or> (x=-\<infinity> \<and> y=\<infinity>))"
   509       and f: "(f \<longlongrightarrow> x) F" and g: "(g \<longlongrightarrow> y) F"
   509       and f: "(f \<longlongrightarrow> x) F" and g: "(g \<longlongrightarrow> y) F"
   510   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> x + y) F"
   510   shows "((\<lambda>x. f x + g x) \<longlongrightarrow> x + y) F"
   511 proof%unimportant (cases x)
   511 proof (cases x)
   512   case (real r)
   512   case (real r)
   513   show ?thesis
   513   show ?thesis
   514     apply (rule tendsto_add_ereal_general2) using real assms by auto
   514     apply (rule tendsto_add_ereal_general2) using real assms by auto
   515 next
   515 next
   516   case (PInf)
   516   case (PInf)
   526 
   526 
   527 text \<open>In the same way as for addition, we prove that the multiplication is continuous on
   527 text \<open>In the same way as for addition, we prove that the multiplication is continuous on
   528 ereal times ereal, except at \<open>(\<infinity>, 0)\<close> and \<open>(-\<infinity>, 0)\<close> and \<open>(0, \<infinity>)\<close> and \<open>(0, -\<infinity>)\<close>,
   528 ereal times ereal, except at \<open>(\<infinity>, 0)\<close> and \<open>(-\<infinity>, 0)\<close> and \<open>(0, \<infinity>)\<close> and \<open>(0, -\<infinity>)\<close>,
   529 starting with specific situations.\<close>
   529 starting with specific situations.\<close>
   530 
   530 
   531 lemma%important tendsto_mult_real_ereal:
   531 lemma tendsto_mult_real_ereal:
   532   assumes "(u \<longlongrightarrow> ereal l) F" "(v \<longlongrightarrow> ereal m) F"
   532   assumes "(u \<longlongrightarrow> ereal l) F" "(v \<longlongrightarrow> ereal m) F"
   533   shows "((\<lambda>n. u n * v n) \<longlongrightarrow> ereal l * ereal m) F"
   533   shows "((\<lambda>n. u n * v n) \<longlongrightarrow> ereal l * ereal m) F"
   534 proof%unimportant -
   534 proof -
   535   have ureal: "eventually (\<lambda>n. u n = ereal(real_of_ereal(u n))) F" by (rule real_lim_then_eventually_real[OF assms(1)])
   535   have ureal: "eventually (\<lambda>n. u n = ereal(real_of_ereal(u n))) F" by (rule real_lim_then_eventually_real[OF assms(1)])
   536   then have "((\<lambda>n. ereal(real_of_ereal(u n))) \<longlongrightarrow> ereal l) F" using assms by auto
   536   then have "((\<lambda>n. ereal(real_of_ereal(u n))) \<longlongrightarrow> ereal l) F" using assms by auto
   537   then have limu: "((\<lambda>n. real_of_ereal(u n)) \<longlongrightarrow> l) F" by auto
   537   then have limu: "((\<lambda>n. real_of_ereal(u n)) \<longlongrightarrow> l) F" by auto
   538   have vreal: "eventually (\<lambda>n. v n = ereal(real_of_ereal(v n))) F" by (rule real_lim_then_eventually_real[OF assms(2)])
   538   have vreal: "eventually (\<lambda>n. v n = ereal(real_of_ereal(v n))) F" by (rule real_lim_then_eventually_real[OF assms(2)])
   539   then have "((\<lambda>n. ereal(real_of_ereal(v n))) \<longlongrightarrow> ereal m) F" using assms by auto
   539   then have "((\<lambda>n. ereal(real_of_ereal(v n))) \<longlongrightarrow> ereal m) F" using assms by auto
   549   have "((\<lambda>n. real_of_ereal(u n) * real_of_ereal(v n)) \<longlongrightarrow> l * m) F" using tendsto_mult[OF limu limv] by auto
   549   have "((\<lambda>n. real_of_ereal(u n) * real_of_ereal(v n)) \<longlongrightarrow> l * m) F" using tendsto_mult[OF limu limv] by auto
   550   then have "((\<lambda>n. ereal(real_of_ereal(u n)) * real_of_ereal(v n)) \<longlongrightarrow> ereal(l * m)) F" by auto
   550   then have "((\<lambda>n. ereal(real_of_ereal(u n)) * real_of_ereal(v n)) \<longlongrightarrow> ereal(l * m)) F" by auto
   551   then show ?thesis using * filterlim_cong by fastforce
   551   then show ?thesis using * filterlim_cong by fastforce
   552 qed
   552 qed
   553 
   553 
   554 lemma%important tendsto_mult_ereal_PInf:
   554 lemma tendsto_mult_ereal_PInf:
   555   fixes f g::"_ \<Rightarrow> ereal"
   555   fixes f g::"_ \<Rightarrow> ereal"
   556   assumes "(f \<longlongrightarrow> l) F" "l>0" "(g \<longlongrightarrow> \<infinity>) F"
   556   assumes "(f \<longlongrightarrow> l) F" "l>0" "(g \<longlongrightarrow> \<infinity>) F"
   557   shows "((\<lambda>x. f x * g x) \<longlongrightarrow> \<infinity>) F"
   557   shows "((\<lambda>x. f x * g x) \<longlongrightarrow> \<infinity>) F"
   558 proof%unimportant -
   558 proof -
   559   obtain a::real where "0 < ereal a" "a < l" using assms(2) using ereal_dense2 by blast
   559   obtain a::real where "0 < ereal a" "a < l" using assms(2) using ereal_dense2 by blast
   560   have *: "eventually (\<lambda>x. f x > a) F" using \<open>a < l\<close> assms(1) by (simp add: order_tendsto_iff)
   560   have *: "eventually (\<lambda>x. f x > a) F" using \<open>a < l\<close> assms(1) by (simp add: order_tendsto_iff)
   561   {
   561   {
   562     fix K::real
   562     fix K::real
   563     define M where "M = max K 1"
   563     define M where "M = max K 1"
   577     then have "eventually (\<lambda>x. f x * g x > K) F" using eventually_mono Imp by force
   577     then have "eventually (\<lambda>x. f x * g x > K) F" using eventually_mono Imp by force
   578   }
   578   }
   579   then show ?thesis by (auto simp add: tendsto_PInfty)
   579   then show ?thesis by (auto simp add: tendsto_PInfty)
   580 qed
   580 qed
   581 
   581 
   582 lemma%important tendsto_mult_ereal_pos:
   582 lemma tendsto_mult_ereal_pos:
   583   fixes f g::"_ \<Rightarrow> ereal"
   583   fixes f g::"_ \<Rightarrow> ereal"
   584   assumes "(f \<longlongrightarrow> l) F" "(g \<longlongrightarrow> m) F" "l>0" "m>0"
   584   assumes "(f \<longlongrightarrow> l) F" "(g \<longlongrightarrow> m) F" "l>0" "m>0"
   585   shows "((\<lambda>x. f x * g x) \<longlongrightarrow> l * m) F"
   585   shows "((\<lambda>x. f x * g x) \<longlongrightarrow> l * m) F"
   586 proof%unimportant (cases)
   586 proof (cases)
   587   assume *: "l = \<infinity> \<or> m = \<infinity>"
   587   assume *: "l = \<infinity> \<or> m = \<infinity>"
   588   then show ?thesis
   588   then show ?thesis
   589   proof (cases)
   589   proof (cases)
   590     assume "m = \<infinity>"
   590     assume "m = \<infinity>"
   591     then show ?thesis using tendsto_mult_ereal_PInf assms by auto
   591     then show ?thesis using tendsto_mult_ereal_PInf assms by auto
   616 lemma sgn_squared_ereal:
   616 lemma sgn_squared_ereal:
   617   assumes "l \<noteq> (0::ereal)"
   617   assumes "l \<noteq> (0::ereal)"
   618   shows "sgn(l) * sgn(l) = 1"
   618   shows "sgn(l) * sgn(l) = 1"
   619 apply (cases l) using assms by (auto simp add: one_ereal_def sgn_if)
   619 apply (cases l) using assms by (auto simp add: one_ereal_def sgn_if)
   620 
   620 
   621 lemma%important tendsto_mult_ereal [tendsto_intros]:
   621 lemma tendsto_mult_ereal [tendsto_intros]:
   622   fixes f g::"_ \<Rightarrow> ereal"
   622   fixes f g::"_ \<Rightarrow> ereal"
   623   assumes "(f \<longlongrightarrow> l) F" "(g \<longlongrightarrow> m) F" "\<not>((l=0 \<and> abs(m) = \<infinity>) \<or> (m=0 \<and> abs(l) = \<infinity>))"
   623   assumes "(f \<longlongrightarrow> l) F" "(g \<longlongrightarrow> m) F" "\<not>((l=0 \<and> abs(m) = \<infinity>) \<or> (m=0 \<and> abs(l) = \<infinity>))"
   624   shows "((\<lambda>x. f x * g x) \<longlongrightarrow> l * m) F"
   624   shows "((\<lambda>x. f x * g x) \<longlongrightarrow> l * m) F"
   625 proof%unimportant (cases)
   625 proof (cases)
   626   assume "l=0 \<or> m=0"
   626   assume "l=0 \<or> m=0"
   627   then have "abs(l) \<noteq> \<infinity>" "abs(m) \<noteq> \<infinity>" using assms(3) by auto
   627   then have "abs(l) \<noteq> \<infinity>" "abs(m) \<noteq> \<infinity>" using assms(3) by auto
   628   then obtain lr mr where "l = ereal lr" "m = ereal mr" by auto
   628   then obtain lr mr where "l = ereal lr" "m = ereal mr" by auto
   629   then show ?thesis using tendsto_mult_real_ereal assms by auto
   629   then show ?thesis using tendsto_mult_real_ereal assms by auto
   630 next
   630 next
   659 by (cases "c = 0", auto simp add: assms tendsto_mult_ereal)
   659 by (cases "c = 0", auto simp add: assms tendsto_mult_ereal)
   660 
   660 
   661 
   661 
   662 subsubsection%important \<open>Continuity of division\<close>
   662 subsubsection%important \<open>Continuity of division\<close>
   663 
   663 
   664 lemma%important tendsto_inverse_ereal_PInf:
   664 lemma tendsto_inverse_ereal_PInf:
   665   fixes u::"_ \<Rightarrow> ereal"
   665   fixes u::"_ \<Rightarrow> ereal"
   666   assumes "(u \<longlongrightarrow> \<infinity>) F"
   666   assumes "(u \<longlongrightarrow> \<infinity>) F"
   667   shows "((\<lambda>x. 1/ u x) \<longlongrightarrow> 0) F"
   667   shows "((\<lambda>x. 1/ u x) \<longlongrightarrow> 0) F"
   668 proof%unimportant -
   668 proof -
   669   {
   669   {
   670     fix e::real assume "e>0"
   670     fix e::real assume "e>0"
   671     have "1/e < \<infinity>" by auto
   671     have "1/e < \<infinity>" by auto
   672     then have "eventually (\<lambda>n. u n > 1/e) F" using assms(1) by (simp add: tendsto_PInfty)
   672     then have "eventually (\<lambda>n. u n > 1/e) F" using assms(1) by (simp add: tendsto_PInfty)
   673     moreover
   673     moreover
   700 lemma tendsto_inverse_real [tendsto_intros]:
   700 lemma tendsto_inverse_real [tendsto_intros]:
   701   fixes u::"_ \<Rightarrow> real"
   701   fixes u::"_ \<Rightarrow> real"
   702   shows "(u \<longlongrightarrow> l) F \<Longrightarrow> l \<noteq> 0 \<Longrightarrow> ((\<lambda>x. 1/ u x) \<longlongrightarrow> 1/l) F"
   702   shows "(u \<longlongrightarrow> l) F \<Longrightarrow> l \<noteq> 0 \<Longrightarrow> ((\<lambda>x. 1/ u x) \<longlongrightarrow> 1/l) F"
   703   using tendsto_inverse unfolding inverse_eq_divide .
   703   using tendsto_inverse unfolding inverse_eq_divide .
   704 
   704 
   705 lemma%important tendsto_inverse_ereal [tendsto_intros]:
   705 lemma tendsto_inverse_ereal [tendsto_intros]:
   706   fixes u::"_ \<Rightarrow> ereal"
   706   fixes u::"_ \<Rightarrow> ereal"
   707   assumes "(u \<longlongrightarrow> l) F" "l \<noteq> 0"
   707   assumes "(u \<longlongrightarrow> l) F" "l \<noteq> 0"
   708   shows "((\<lambda>x. 1/ u x) \<longlongrightarrow> 1/l) F"
   708   shows "((\<lambda>x. 1/ u x) \<longlongrightarrow> 1/l) F"
   709 proof%unimportant (cases l)
   709 proof (cases l)
   710   case (real r)
   710   case (real r)
   711   then have "r \<noteq> 0" using assms(2) by auto
   711   then have "r \<noteq> 0" using assms(2) by auto
   712   then have "1/l = ereal(1/r)" using real by (simp add: one_ereal_def)
   712   then have "1/l = ereal(1/r)" using real by (simp add: one_ereal_def)
   713   define v where "v = (\<lambda>n. real_of_ereal(u n))"
   713   define v where "v = (\<lambda>n. real_of_ereal(u n))"
   714   have ureal: "eventually (\<lambda>n. u n = ereal(v n)) F" unfolding v_def using real_lim_then_eventually_real assms(1) real by auto
   714   have ureal: "eventually (\<lambda>n. u n = ereal(v n)) F" unfolding v_def using real_lim_then_eventually_real assms(1) real by auto
   745   then have "((\<lambda>n. 1/v n) \<longlongrightarrow> 0) F" using tendsto_inverse_ereal_PInf by auto
   745   then have "((\<lambda>n. 1/v n) \<longlongrightarrow> 0) F" using tendsto_inverse_ereal_PInf by auto
   746   then have "((\<lambda>n. -1/v n) \<longlongrightarrow> 0) F" using tendsto_uminus_ereal by fastforce
   746   then have "((\<lambda>n. -1/v n) \<longlongrightarrow> 0) F" using tendsto_uminus_ereal by fastforce
   747   then show ?thesis unfolding v_def using Lim_transform_eventually[OF *] \<open> 1/l = 0 \<close> by auto
   747   then show ?thesis unfolding v_def using Lim_transform_eventually[OF *] \<open> 1/l = 0 \<close> by auto
   748 qed
   748 qed
   749 
   749 
   750 lemma%important tendsto_divide_ereal [tendsto_intros]:
   750 lemma tendsto_divide_ereal [tendsto_intros]:
   751   fixes f g::"_ \<Rightarrow> ereal"
   751   fixes f g::"_ \<Rightarrow> ereal"
   752   assumes "(f \<longlongrightarrow> l) F" "(g \<longlongrightarrow> m) F" "m \<noteq> 0" "\<not>(abs(l) = \<infinity> \<and> abs(m) = \<infinity>)"
   752   assumes "(f \<longlongrightarrow> l) F" "(g \<longlongrightarrow> m) F" "m \<noteq> 0" "\<not>(abs(l) = \<infinity> \<and> abs(m) = \<infinity>)"
   753   shows "((\<lambda>x. f x / g x) \<longlongrightarrow> l / m) F"
   753   shows "((\<lambda>x. f x / g x) \<longlongrightarrow> l / m) F"
   754 proof%unimportant -
   754 proof -
   755   define h where "h = (\<lambda>x. 1/ g x)"
   755   define h where "h = (\<lambda>x. 1/ g x)"
   756   have *: "(h \<longlongrightarrow> 1/m) F" unfolding h_def using assms(2) assms(3) tendsto_inverse_ereal by auto
   756   have *: "(h \<longlongrightarrow> 1/m) F" unfolding h_def using assms(2) assms(3) tendsto_inverse_ereal by auto
   757   have "((\<lambda>x. f x * h x) \<longlongrightarrow> l * (1/m)) F"
   757   have "((\<lambda>x. f x * h x) \<longlongrightarrow> l * (1/m)) F"
   758     apply (rule tendsto_mult_ereal[OF assms(1) *]) using assms(3) assms(4) by (auto simp add: divide_ereal_def)
   758     apply (rule tendsto_mult_ereal[OF assms(1) *]) using assms(3) assms(4) by (auto simp add: divide_ereal_def)
   759   moreover have "f x * h x = f x / g x" for x unfolding h_def by (simp add: divide_ereal_def)
   759   moreover have "f x * h x = f x / g x" for x unfolding h_def by (simp add: divide_ereal_def)
   764 
   764 
   765 subsubsection%important \<open>Further limits\<close>
   765 subsubsection%important \<open>Further limits\<close>
   766 
   766 
   767 text \<open>The assumptions of @{thm tendsto_diff_ereal} are too strong, we weaken them here.\<close>
   767 text \<open>The assumptions of @{thm tendsto_diff_ereal} are too strong, we weaken them here.\<close>
   768 
   768 
   769 lemma%important tendsto_diff_ereal_general [tendsto_intros]:
   769 lemma tendsto_diff_ereal_general [tendsto_intros]:
   770   fixes u v::"'a \<Rightarrow> ereal"
   770   fixes u v::"'a \<Rightarrow> ereal"
   771   assumes "(u \<longlongrightarrow> l) F" "(v \<longlongrightarrow> m) F" "\<not>((l = \<infinity> \<and> m = \<infinity>) \<or> (l = -\<infinity> \<and> m = -\<infinity>))"
   771   assumes "(u \<longlongrightarrow> l) F" "(v \<longlongrightarrow> m) F" "\<not>((l = \<infinity> \<and> m = \<infinity>) \<or> (l = -\<infinity> \<and> m = -\<infinity>))"
   772   shows "((\<lambda>n. u n - v n) \<longlongrightarrow> l - m) F"
   772   shows "((\<lambda>n. u n - v n) \<longlongrightarrow> l - m) F"
   773 proof%unimportant -
   773 proof -
   774   have "((\<lambda>n. u n + (-v n)) \<longlongrightarrow> l + (-m)) F"
   774   have "((\<lambda>n. u n + (-v n)) \<longlongrightarrow> l + (-m)) F"
   775     apply (intro tendsto_intros assms) using assms by (auto simp add: ereal_uminus_eq_reorder)
   775     apply (intro tendsto_intros assms) using assms by (auto simp add: ereal_uminus_eq_reorder)
   776   then show ?thesis by (simp add: minus_ereal_def)
   776   then show ?thesis by (simp add: minus_ereal_def)
   777 qed
   777 qed
   778 
   778 
   779 lemma id_nat_ereal_tendsto_PInf [tendsto_intros]:
   779 lemma id_nat_ereal_tendsto_PInf [tendsto_intros]:
   780   "(\<lambda> n::nat. real n) \<longlonglongrightarrow> \<infinity>"
   780   "(\<lambda> n::nat. real n) \<longlonglongrightarrow> \<infinity>"
   781 by (simp add: filterlim_real_sequentially tendsto_PInfty_eq_at_top)
   781 by (simp add: filterlim_real_sequentially tendsto_PInfty_eq_at_top)
   782 
   782 
   783 lemma%important tendsto_at_top_pseudo_inverse [tendsto_intros]:
   783 lemma tendsto_at_top_pseudo_inverse [tendsto_intros]:
   784   fixes u::"nat \<Rightarrow> nat"
   784   fixes u::"nat \<Rightarrow> nat"
   785   assumes "LIM n sequentially. u n :> at_top"
   785   assumes "LIM n sequentially. u n :> at_top"
   786   shows "LIM n sequentially. Inf {N. u N \<ge> n} :> at_top"
   786   shows "LIM n sequentially. Inf {N. u N \<ge> n} :> at_top"
   787 proof%unimportant -
   787 proof -
   788   {
   788   {
   789     fix C::nat
   789     fix C::nat
   790     define M where "M = Max {u n| n. n \<le> C}+1"
   790     define M where "M = Max {u n| n. n \<le> C}+1"
   791     {
   791     {
   792       fix n assume "n \<ge> M"
   792       fix n assume "n \<ge> M"
   809       using eventually_sequentially by auto
   809       using eventually_sequentially by auto
   810   }
   810   }
   811   then show ?thesis using filterlim_at_top by auto
   811   then show ?thesis using filterlim_at_top by auto
   812 qed
   812 qed
   813 
   813 
   814 lemma%important pseudo_inverse_finite_set:
   814 lemma pseudo_inverse_finite_set:
   815   fixes u::"nat \<Rightarrow> nat"
   815   fixes u::"nat \<Rightarrow> nat"
   816   assumes "LIM n sequentially. u n :> at_top"
   816   assumes "LIM n sequentially. u n :> at_top"
   817   shows "finite {N. u N \<le> n}"
   817   shows "finite {N. u N \<le> n}"
   818 proof%unimportant -
   818 proof -
   819   fix n
   819   fix n
   820   have "eventually (\<lambda>N. u N \<ge> n+1) sequentially" using assms
   820   have "eventually (\<lambda>N. u N \<ge> n+1) sequentially" using assms
   821     by (simp add: filterlim_at_top)
   821     by (simp add: filterlim_at_top)
   822   then obtain N1 where N1: "\<And>N. N \<ge> N1 \<Longrightarrow> u N \<ge> n + 1"
   822   then obtain N1 where N1: "\<And>N. N \<ge> N1 \<Longrightarrow> u N \<ge> n + 1"
   823     using eventually_sequentially by auto
   823     using eventually_sequentially by auto
   858   case (MInf)
   858   case (MInf)
   859   then have "min x n = x" for n::nat by (auto simp add: min_def)
   859   then have "min x n = x" for n::nat by (auto simp add: min_def)
   860   then show ?thesis by auto
   860   then show ?thesis by auto
   861 qed
   861 qed
   862 
   862 
   863 lemma%important ereal_truncation_real_top [tendsto_intros]:
   863 lemma ereal_truncation_real_top [tendsto_intros]:
   864   fixes x::ereal
   864   fixes x::ereal
   865   assumes "x \<noteq> - \<infinity>"
   865   assumes "x \<noteq> - \<infinity>"
   866   shows "(\<lambda>n::nat. real_of_ereal(min x n)) \<longlonglongrightarrow> x"
   866   shows "(\<lambda>n::nat. real_of_ereal(min x n)) \<longlonglongrightarrow> x"
   867 proof%unimportant (cases x)
   867 proof (cases x)
   868   case (real r)
   868   case (real r)
   869   then obtain K::nat where "K>0" "K > abs(r)" using reals_Archimedean2 gr0I by auto
   869   then obtain K::nat where "K>0" "K > abs(r)" using reals_Archimedean2 gr0I by auto
   870   then have "min x n = x" if "n \<ge> K" for n apply (subst real, subst real, auto) using that eq_iff by fastforce
   870   then have "min x n = x" if "n \<ge> K" for n apply (subst real, subst real, auto) using that eq_iff by fastforce
   871   then have "real_of_ereal(min x n) = r" if "n \<ge> K" for n using real that by auto
   871   then have "real_of_ereal(min x n) = r" if "n \<ge> K" for n using real that by auto
   872   then have "eventually (\<lambda>n. real_of_ereal(min x n) = r) sequentially" using eventually_at_top_linorder by blast
   872   then have "eventually (\<lambda>n. real_of_ereal(min x n) = r) sequentially" using eventually_at_top_linorder by blast
   876   case (PInf)
   876   case (PInf)
   877   then have "real_of_ereal(min x n) = n" for n::nat by (auto simp add: min_def)
   877   then have "real_of_ereal(min x n) = n" for n::nat by (auto simp add: min_def)
   878   then show ?thesis using id_nat_ereal_tendsto_PInf PInf by auto
   878   then show ?thesis using id_nat_ereal_tendsto_PInf PInf by auto
   879 qed (simp add: assms)
   879 qed (simp add: assms)
   880 
   880 
   881 lemma%important ereal_truncation_bottom [tendsto_intros]:
   881 lemma ereal_truncation_bottom [tendsto_intros]:
   882   fixes x::ereal
   882   fixes x::ereal
   883   shows "(\<lambda>n::nat. max x (- real n)) \<longlonglongrightarrow> x"
   883   shows "(\<lambda>n::nat. max x (- real n)) \<longlonglongrightarrow> x"
   884 proof%unimportant (cases x)
   884 proof (cases x)
   885   case (real r)
   885   case (real r)
   886   then obtain K::nat where "K>0" "K > abs(r)" using reals_Archimedean2 gr0I by auto
   886   then obtain K::nat where "K>0" "K > abs(r)" using reals_Archimedean2 gr0I by auto
   887   then have "max x (-real n) = x" if "n \<ge> K" for n apply (subst real, subst real, auto) using that eq_iff by fastforce
   887   then have "max x (-real n) = x" if "n \<ge> K" for n apply (subst real, subst real, auto) using that eq_iff by fastforce
   888   then have "eventually (\<lambda>n. max x (-real n) = x) sequentially" using eventually_at_top_linorder by blast
   888   then have "eventually (\<lambda>n. max x (-real n) = x) sequentially" using eventually_at_top_linorder by blast
   889   then show ?thesis by (simp add: Lim_eventually)
   889   then show ?thesis by (simp add: Lim_eventually)
   897   case (PInf)
   897   case (PInf)
   898   then have "max x (-real n) = x" for n::nat by (auto simp add: max_def)
   898   then have "max x (-real n) = x" for n::nat by (auto simp add: max_def)
   899   then show ?thesis by auto
   899   then show ?thesis by auto
   900 qed
   900 qed
   901 
   901 
   902 lemma%important ereal_truncation_real_bottom [tendsto_intros]:
   902 lemma ereal_truncation_real_bottom [tendsto_intros]:
   903   fixes x::ereal
   903   fixes x::ereal
   904   assumes "x \<noteq> \<infinity>"
   904   assumes "x \<noteq> \<infinity>"
   905   shows "(\<lambda>n::nat. real_of_ereal(max x (- real n))) \<longlonglongrightarrow> x"
   905   shows "(\<lambda>n::nat. real_of_ereal(max x (- real n))) \<longlonglongrightarrow> x"
   906 proof%unimportant (cases x)
   906 proof (cases x)
   907   case (real r)
   907   case (real r)
   908   then obtain K::nat where "K>0" "K > abs(r)" using reals_Archimedean2 gr0I by auto
   908   then obtain K::nat where "K>0" "K > abs(r)" using reals_Archimedean2 gr0I by auto
   909   then have "max x (-real n) = x" if "n \<ge> K" for n apply (subst real, subst real, auto) using that eq_iff by fastforce
   909   then have "max x (-real n) = x" if "n \<ge> K" for n apply (subst real, subst real, auto) using that eq_iff by fastforce
   910   then have "real_of_ereal(max x (-real n)) = r" if "n \<ge> K" for n using real that by auto
   910   then have "real_of_ereal(max x (-real n)) = r" if "n \<ge> K" for n using real that by auto
   911   then have "eventually (\<lambda>n. real_of_ereal(max x (-real n)) = r) sequentially" using eventually_at_top_linorder by blast
   911   then have "eventually (\<lambda>n. real_of_ereal(max x (-real n)) = r) sequentially" using eventually_at_top_linorder by blast
   929   assume "finite S" then show ?thesis using assms
   929   assume "finite S" then show ?thesis using assms
   930     by (induct, simp, simp add: tendsto_add_ereal_general2 assms)
   930     by (induct, simp, simp add: tendsto_add_ereal_general2 assms)
   931 qed(simp)
   931 qed(simp)
   932 
   932 
   933 
   933 
   934 lemma%important continuous_ereal_abs:
   934 lemma continuous_ereal_abs:
   935   "continuous_on (UNIV::ereal set) abs"
   935   "continuous_on (UNIV::ereal set) abs"
   936 proof%unimportant -
   936 proof -
   937   have "continuous_on ({..0} \<union> {(0::ereal)..}) abs"
   937   have "continuous_on ({..0} \<union> {(0::ereal)..}) abs"
   938     apply (rule continuous_on_closed_Un, auto)
   938     apply (rule continuous_on_closed_Un, auto)
   939     apply (rule iffD1[OF continuous_on_cong, of "{..0}" _ "\<lambda>x. -x"])
   939     apply (rule iffD1[OF continuous_on_cong, of "{..0}" _ "\<lambda>x. -x"])
   940     using less_eq_ereal_def apply (auto simp add: continuous_uminus_ereal)
   940     using less_eq_ereal_def apply (auto simp add: continuous_uminus_ereal)
   941     apply (rule iffD1[OF continuous_on_cong, of "{0..}" _ "\<lambda>x. x"])
   941     apply (rule iffD1[OF continuous_on_cong, of "{0..}" _ "\<lambda>x. x"])
   968   have "((\<lambda>n. e2ennreal(enn2ereal(u n) - enn2ereal(v n))) \<longlongrightarrow> e2ennreal(enn2ereal l - enn2ereal m)) F"
   968   have "((\<lambda>n. e2ennreal(enn2ereal(u n) - enn2ereal(v n))) \<longlongrightarrow> e2ennreal(enn2ereal l - enn2ereal m)) F"
   969     apply (intro tendsto_intros) using assms by  auto
   969     apply (intro tendsto_intros) using assms by  auto
   970   then show ?thesis by auto
   970   then show ?thesis by auto
   971 qed
   971 qed
   972 
   972 
   973 lemma%important tendsto_mult_ennreal [tendsto_intros]:
   973 lemma tendsto_mult_ennreal [tendsto_intros]:
   974   fixes l m::ennreal
   974   fixes l m::ennreal
   975   assumes "(u \<longlongrightarrow> l) F" "(v \<longlongrightarrow> m) F" "\<not>((l = 0 \<and> m = \<infinity>) \<or> (l = \<infinity> \<and> m = 0))"
   975   assumes "(u \<longlongrightarrow> l) F" "(v \<longlongrightarrow> m) F" "\<not>((l = 0 \<and> m = \<infinity>) \<or> (l = \<infinity> \<and> m = 0))"
   976   shows "((\<lambda>n. u n * v n) \<longlongrightarrow> l * m) F"
   976   shows "((\<lambda>n. u n * v n) \<longlongrightarrow> l * m) F"
   977 proof%unimportant -
   977 proof -
   978   have "((\<lambda>n. e2ennreal(enn2ereal (u n) * enn2ereal (v n))) \<longlongrightarrow> e2ennreal(enn2ereal l * enn2ereal m)) F"
   978   have "((\<lambda>n. e2ennreal(enn2ereal (u n) * enn2ereal (v n))) \<longlongrightarrow> e2ennreal(enn2ereal l * enn2ereal m)) F"
   979     apply (intro tendsto_intros) using assms apply auto
   979     apply (intro tendsto_intros) using assms apply auto
   980     using enn2ereal_inject zero_ennreal.rep_eq by fastforce+
   980     using enn2ereal_inject zero_ennreal.rep_eq by fastforce+
   981   moreover have "e2ennreal(enn2ereal (u n) * enn2ereal (v n)) = u n * v n" for n
   981   moreover have "e2ennreal(enn2ereal (u n) * enn2ereal (v n)) = u n * v n" for n
   982     by (subst times_ennreal.abs_eq[symmetric], auto simp add: eq_onp_same_args)
   982     by (subst times_ennreal.abs_eq[symmetric], auto simp add: eq_onp_same_args)
   985   ultimately show ?thesis
   985   ultimately show ?thesis
   986     by auto
   986     by auto
   987 qed
   987 qed
   988 
   988 
   989 
   989 
   990 subsection%important \<open>monoset\<close>
   990 subsection%important \<open>monoset\<close> (*FIX ME title *)
   991 
   991 
   992 definition%important (in order) mono_set:
   992 definition (in order) mono_set:
   993   "mono_set S \<longleftrightarrow> (\<forall>x y. x \<le> y \<longrightarrow> x \<in> S \<longrightarrow> y \<in> S)"
   993   "mono_set S \<longleftrightarrow> (\<forall>x y. x \<le> y \<longrightarrow> x \<in> S \<longrightarrow> y \<in> S)"
   994 
   994 
   995 lemma (in order) mono_greaterThan [intro, simp]: "mono_set {B<..}" unfolding mono_set by auto
   995 lemma (in order) mono_greaterThan [intro, simp]: "mono_set {B<..}" unfolding mono_set by auto
   996 lemma (in order) mono_atLeast [intro, simp]: "mono_set {B..}" unfolding mono_set by auto
   996 lemma (in order) mono_atLeast [intro, simp]: "mono_set {B..}" unfolding mono_set by auto
   997 lemma (in order) mono_UNIV [intro, simp]: "mono_set UNIV" unfolding mono_set by auto
   997 lemma (in order) mono_UNIV [intro, simp]: "mono_set UNIV" unfolding mono_set by auto
   998 lemma (in order) mono_empty [intro, simp]: "mono_set {}" unfolding mono_set by auto
   998 lemma (in order) mono_empty [intro, simp]: "mono_set {}" unfolding mono_set by auto
   999 
   999 
  1000 lemma%important (in complete_linorder) mono_set_iff:
  1000 lemma (in complete_linorder) mono_set_iff:
  1001   fixes S :: "'a set"
  1001   fixes S :: "'a set"
  1002   defines "a \<equiv> Inf S"
  1002   defines "a \<equiv> Inf S"
  1003   shows "mono_set S \<longleftrightarrow> S = {a <..} \<or> S = {a..}" (is "_ = ?c")
  1003   shows "mono_set S \<longleftrightarrow> S = {a <..} \<or> S = {a..}" (is "_ = ?c")
  1004 proof%unimportant
  1004 proof
  1005   assume "mono_set S"
  1005   assume "mono_set S"
  1006   then have mono: "\<And>x y. x \<le> y \<Longrightarrow> x \<in> S \<Longrightarrow> y \<in> S"
  1006   then have mono: "\<And>x y. x \<le> y \<Longrightarrow> x \<in> S \<Longrightarrow> y \<in> S"
  1007     by (auto simp: mono_set)
  1007     by (auto simp: mono_set)
  1008   show ?c
  1008   show ?c
  1009   proof cases
  1009   proof cases
  1041   fixes S :: "ereal set"
  1041   fixes S :: "ereal set"
  1042   shows "closed S \<and> mono_set S \<longleftrightarrow> S = {} \<or> S = {Inf S ..}"
  1042   shows "closed S \<and> mono_set S \<longleftrightarrow> S = {} \<or> S = {Inf S ..}"
  1043   by (metis Inf_UNIV atLeast_eq_UNIV_iff closed_ereal_atLeast
  1043   by (metis Inf_UNIV atLeast_eq_UNIV_iff closed_ereal_atLeast
  1044     ereal_open_closed mono_empty mono_set_iff open_ereal_greaterThan)
  1044     ereal_open_closed mono_empty mono_set_iff open_ereal_greaterThan)
  1045 
  1045 
  1046 lemma%important ereal_Liminf_Sup_monoset:
  1046 lemma ereal_Liminf_Sup_monoset:
  1047   fixes f :: "'a \<Rightarrow> ereal"
  1047   fixes f :: "'a \<Rightarrow> ereal"
  1048   shows "Liminf net f =
  1048   shows "Liminf net f =
  1049     Sup {l. \<forall>S. open S \<longrightarrow> mono_set S \<longrightarrow> l \<in> S \<longrightarrow> eventually (\<lambda>x. f x \<in> S) net}"
  1049     Sup {l. \<forall>S. open S \<longrightarrow> mono_set S \<longrightarrow> l \<in> S \<longrightarrow> eventually (\<lambda>x. f x \<in> S) net}"
  1050     (is "_ = Sup ?A")
  1050     (is "_ = Sup ?A")
  1051 proof%unimportant (safe intro!: Liminf_eqI complete_lattice_class.Sup_upper complete_lattice_class.Sup_least)
  1051 proof (safe intro!: Liminf_eqI complete_lattice_class.Sup_upper complete_lattice_class.Sup_least)
  1052   fix P
  1052   fix P
  1053   assume P: "eventually P net"
  1053   assume P: "eventually P net"
  1054   fix S
  1054   fix S
  1055   assume S: "mono_set S" "Inf (f ` (Collect P)) \<in> S"
  1055   assume S: "mono_set S" "Inf (f ` (Collect P)) \<in> S"
  1056   {
  1056   {
  1080     ultimately show "B \<le> y"
  1080     ultimately show "B \<le> y"
  1081       by simp
  1081       by simp
  1082   qed
  1082   qed
  1083 qed
  1083 qed
  1084 
  1084 
  1085 lemma%important ereal_Limsup_Inf_monoset:
  1085 lemma ereal_Limsup_Inf_monoset:
  1086   fixes f :: "'a \<Rightarrow> ereal"
  1086   fixes f :: "'a \<Rightarrow> ereal"
  1087   shows "Limsup net f =
  1087   shows "Limsup net f =
  1088     Inf {l. \<forall>S. open S \<longrightarrow> mono_set (uminus ` S) \<longrightarrow> l \<in> S \<longrightarrow> eventually (\<lambda>x. f x \<in> S) net}"
  1088     Inf {l. \<forall>S. open S \<longrightarrow> mono_set (uminus ` S) \<longrightarrow> l \<in> S \<longrightarrow> eventually (\<lambda>x. f x \<in> S) net}"
  1089     (is "_ = Inf ?A")
  1089     (is "_ = Inf ?A")
  1090 proof%unimportant (safe intro!: Limsup_eqI complete_lattice_class.Inf_lower complete_lattice_class.Inf_greatest)
  1090 proof (safe intro!: Limsup_eqI complete_lattice_class.Inf_lower complete_lattice_class.Inf_greatest)
  1091   fix P
  1091   fix P
  1092   assume P: "eventually P net"
  1092   assume P: "eventually P net"
  1093   fix S
  1093   fix S
  1094   assume S: "mono_set (uminus`S)" "Sup (f ` (Collect P)) \<in> S"
  1094   assume S: "mono_set (uminus`S)" "Sup (f ` (Collect P)) \<in> S"
  1095   {
  1095   {
  1119     ultimately show "y \<le> B"
  1119     ultimately show "y \<le> B"
  1120       by simp
  1120       by simp
  1121   qed
  1121   qed
  1122 qed
  1122 qed
  1123 
  1123 
  1124 lemma%important liminf_bounded_open:
  1124 lemma liminf_bounded_open:
  1125   fixes x :: "nat \<Rightarrow> ereal"
  1125   fixes x :: "nat \<Rightarrow> ereal"
  1126   shows "x0 \<le> liminf x \<longleftrightarrow> (\<forall>S. open S \<longrightarrow> mono_set S \<longrightarrow> x0 \<in> S \<longrightarrow> (\<exists>N. \<forall>n\<ge>N. x n \<in> S))"
  1126   shows "x0 \<le> liminf x \<longleftrightarrow> (\<forall>S. open S \<longrightarrow> mono_set S \<longrightarrow> x0 \<in> S \<longrightarrow> (\<exists>N. \<forall>n\<ge>N. x n \<in> S))"
  1127   (is "_ \<longleftrightarrow> ?P x0")
  1127   (is "_ \<longleftrightarrow> ?P x0")
  1128 proof%unimportant
  1128 proof
  1129   assume "?P x0"
  1129   assume "?P x0"
  1130   then show "x0 \<le> liminf x"
  1130   then show "x0 \<le> liminf x"
  1131     unfolding ereal_Liminf_Sup_monoset eventually_sequentially
  1131     unfolding ereal_Liminf_Sup_monoset eventually_sequentially
  1132     by (intro complete_lattice_class.Sup_upper) auto
  1132     by (intro complete_lattice_class.Sup_upper) auto
  1133 next
  1133 next
  1157   }
  1157   }
  1158   then show "?P x0"
  1158   then show "?P x0"
  1159     by auto
  1159     by auto
  1160 qed
  1160 qed
  1161 
  1161 
  1162 lemma%important limsup_finite_then_bounded:
  1162 lemma limsup_finite_then_bounded:
  1163   fixes u::"nat \<Rightarrow> real"
  1163   fixes u::"nat \<Rightarrow> real"
  1164   assumes "limsup u < \<infinity>"
  1164   assumes "limsup u < \<infinity>"
  1165   shows "\<exists>C. \<forall>n. u n \<le> C"
  1165   shows "\<exists>C. \<forall>n. u n \<le> C"
  1166 proof%unimportant -
  1166 proof -
  1167   obtain C where C: "limsup u < C" "C < \<infinity>" using assms ereal_dense2 by blast
  1167   obtain C where C: "limsup u < C" "C < \<infinity>" using assms ereal_dense2 by blast
  1168   then have "C = ereal(real_of_ereal C)" using ereal_real by force
  1168   then have "C = ereal(real_of_ereal C)" using ereal_real by force
  1169   have "eventually (\<lambda>n. u n < C) sequentially" using C(1) unfolding Limsup_def
  1169   have "eventually (\<lambda>n. u n < C) sequentially" using C(1) unfolding Limsup_def
  1170     apply (auto simp add: INF_less_iff)
  1170     apply (auto simp add: INF_less_iff)
  1171     using SUP_lessD eventually_mono by fastforce
  1171     using SUP_lessD eventually_mono by fastforce
  1271   case (Suc k)
  1271   case (Suc k)
  1272   have "liminf (\<lambda>n. u (n+k+1)) = liminf (\<lambda>n. u (n+k))" using liminf_shift[where ?u="\<lambda>n. u(n+k)"] by simp
  1272   have "liminf (\<lambda>n. u (n+k+1)) = liminf (\<lambda>n. u (n+k))" using liminf_shift[where ?u="\<lambda>n. u(n+k)"] by simp
  1273   then show ?case using Suc.IH by simp
  1273   then show ?case using Suc.IH by simp
  1274 qed (auto)
  1274 qed (auto)
  1275 
  1275 
  1276 lemma%important Limsup_obtain:
  1276 lemma Limsup_obtain:
  1277   fixes u::"_ \<Rightarrow> 'a :: complete_linorder"
  1277   fixes u::"_ \<Rightarrow> 'a :: complete_linorder"
  1278   assumes "Limsup F u > c"
  1278   assumes "Limsup F u > c"
  1279   shows "\<exists>i. u i > c"
  1279   shows "\<exists>i. u i > c"
  1280 proof%unimportant -
  1280 proof -
  1281   have "(INF P\<in>{P. eventually P F}. SUP x\<in>{x. P x}. u x) > c" using assms by (simp add: Limsup_def)
  1281   have "(INF P\<in>{P. eventually P F}. SUP x\<in>{x. P x}. u x) > c" using assms by (simp add: Limsup_def)
  1282   then show ?thesis by (metis eventually_True mem_Collect_eq less_INF_D less_SUP_iff)
  1282   then show ?thesis by (metis eventually_True mem_Collect_eq less_INF_D less_SUP_iff)
  1283 qed
  1283 qed
  1284 
  1284 
  1285 text \<open>The next lemma is extremely useful, as it often makes it possible to reduce statements
  1285 text \<open>The next lemma is extremely useful, as it often makes it possible to reduce statements
  1286 about limsups to statements about limits.\<close>
  1286 about limsups to statements about limits.\<close>
  1287 
  1287 
  1288 lemma%important limsup_subseq_lim:
  1288 lemma limsup_subseq_lim:
  1289   fixes u::"nat \<Rightarrow> 'a :: {complete_linorder, linorder_topology}"
  1289   fixes u::"nat \<Rightarrow> 'a :: {complete_linorder, linorder_topology}"
  1290   shows "\<exists>r::nat\<Rightarrow>nat. strict_mono r \<and> (u o r) \<longlonglongrightarrow> limsup u"
  1290   shows "\<exists>r::nat\<Rightarrow>nat. strict_mono r \<and> (u o r) \<longlonglongrightarrow> limsup u"
  1291 proof%unimportant (cases)
  1291 proof (cases)
  1292   assume "\<forall>n. \<exists>p>n. \<forall>m\<ge>p. u m \<le> u p"
  1292   assume "\<forall>n. \<exists>p>n. \<forall>m\<ge>p. u m \<le> u p"
  1293   then have "\<exists>r. \<forall>n. (\<forall>m\<ge>r n. u m \<le> u (r n)) \<and> r n < r (Suc n)"
  1293   then have "\<exists>r. \<forall>n. (\<forall>m\<ge>r n. u m \<le> u (r n)) \<and> r n < r (Suc n)"
  1294     by (intro dependent_nat_choice) (auto simp: conj_commute)
  1294     by (intro dependent_nat_choice) (auto simp: conj_commute)
  1295   then obtain r :: "nat \<Rightarrow> nat" where "strict_mono r" and mono: "\<And>n m. r n \<le> m \<Longrightarrow> u m \<le> u (r n)"
  1295   then obtain r :: "nat \<Rightarrow> nat" where "strict_mono r" and mono: "\<And>n m. r n \<le> m \<Longrightarrow> u m \<le> u (r n)"
  1296     by (auto simp: strict_mono_Suc_iff)
  1296     by (auto simp: strict_mono_Suc_iff)
  1376   then have "limsup u = (SUP n. (u o r) n)" using \<open>(SUP n. (u o r) n) \<le> limsup u\<close> by simp
  1376   then have "limsup u = (SUP n. (u o r) n)" using \<open>(SUP n. (u o r) n) \<le> limsup u\<close> by simp
  1377   then have "(u o r) \<longlonglongrightarrow> limsup u" using \<open>(u o r) \<longlonglongrightarrow> (SUP n. (u o r) n)\<close> by simp
  1377   then have "(u o r) \<longlonglongrightarrow> limsup u" using \<open>(u o r) \<longlonglongrightarrow> (SUP n. (u o r) n)\<close> by simp
  1378   then show ?thesis using \<open>strict_mono r\<close> by auto
  1378   then show ?thesis using \<open>strict_mono r\<close> by auto
  1379 qed
  1379 qed
  1380 
  1380 
  1381 lemma%important liminf_subseq_lim:
  1381 lemma liminf_subseq_lim:
  1382   fixes u::"nat \<Rightarrow> 'a :: {complete_linorder, linorder_topology}"
  1382   fixes u::"nat \<Rightarrow> 'a :: {complete_linorder, linorder_topology}"
  1383   shows "\<exists>r::nat\<Rightarrow>nat. strict_mono r \<and> (u o r) \<longlonglongrightarrow> liminf u"
  1383   shows "\<exists>r::nat\<Rightarrow>nat. strict_mono r \<and> (u o r) \<longlonglongrightarrow> liminf u"
  1384 proof%unimportant (cases)
  1384 proof (cases)
  1385   assume "\<forall>n. \<exists>p>n. \<forall>m\<ge>p. u m \<ge> u p"
  1385   assume "\<forall>n. \<exists>p>n. \<forall>m\<ge>p. u m \<ge> u p"
  1386   then have "\<exists>r. \<forall>n. (\<forall>m\<ge>r n. u m \<ge> u (r n)) \<and> r n < r (Suc n)"
  1386   then have "\<exists>r. \<forall>n. (\<forall>m\<ge>r n. u m \<ge> u (r n)) \<and> r n < r (Suc n)"
  1387     by (intro dependent_nat_choice) (auto simp: conj_commute)
  1387     by (intro dependent_nat_choice) (auto simp: conj_commute)
  1388   then obtain r :: "nat \<Rightarrow> nat" where "strict_mono r" and mono: "\<And>n m. r n \<le> m \<Longrightarrow> u m \<ge> u (r n)"
  1388   then obtain r :: "nat \<Rightarrow> nat" where "strict_mono r" and mono: "\<And>n m. r n \<le> m \<Longrightarrow> u m \<ge> u (r n)"
  1389     by (auto simp: strict_mono_Suc_iff)
  1389     by (auto simp: strict_mono_Suc_iff)
  1474 
  1474 
  1475 text \<open>The following statement about limsups is reduced to a statement about limits using
  1475 text \<open>The following statement about limsups is reduced to a statement about limits using
  1476 subsequences thanks to \<open>limsup_subseq_lim\<close>. The statement for limits follows for instance from
  1476 subsequences thanks to \<open>limsup_subseq_lim\<close>. The statement for limits follows for instance from
  1477 \<open>tendsto_add_ereal_general\<close>.\<close>
  1477 \<open>tendsto_add_ereal_general\<close>.\<close>
  1478 
  1478 
  1479 lemma%important ereal_limsup_add_mono:
  1479 lemma ereal_limsup_add_mono:
  1480   fixes u v::"nat \<Rightarrow> ereal"
  1480   fixes u v::"nat \<Rightarrow> ereal"
  1481   shows "limsup (\<lambda>n. u n + v n) \<le> limsup u + limsup v"
  1481   shows "limsup (\<lambda>n. u n + v n) \<le> limsup u + limsup v"
  1482 proof%unimportant (cases)
  1482 proof (cases)
  1483   assume "(limsup u = \<infinity>) \<or> (limsup v = \<infinity>)"
  1483   assume "(limsup u = \<infinity>) \<or> (limsup v = \<infinity>)"
  1484   then have "limsup u + limsup v = \<infinity>" by simp
  1484   then have "limsup u + limsup v = \<infinity>" by simp
  1485   then show ?thesis by auto
  1485   then show ?thesis by auto
  1486 next
  1486 next
  1487   assume "\<not>((limsup u = \<infinity>) \<or> (limsup v = \<infinity>))"
  1487   assume "\<not>((limsup u = \<infinity>) \<or> (limsup v = \<infinity>))"
  1520 
  1520 
  1521 text \<open>There is an asymmetry between liminfs and limsups in \<open>ereal\<close>, as \<open>\<infinity> + (-\<infinity>) = \<infinity>\<close>.
  1521 text \<open>There is an asymmetry between liminfs and limsups in \<open>ereal\<close>, as \<open>\<infinity> + (-\<infinity>) = \<infinity>\<close>.
  1522 This explains why there are more assumptions in the next lemma dealing with liminfs that in the
  1522 This explains why there are more assumptions in the next lemma dealing with liminfs that in the
  1523 previous one about limsups.\<close>
  1523 previous one about limsups.\<close>
  1524 
  1524 
  1525 lemma%important ereal_liminf_add_mono:
  1525 lemma ereal_liminf_add_mono:
  1526   fixes u v::"nat \<Rightarrow> ereal"
  1526   fixes u v::"nat \<Rightarrow> ereal"
  1527   assumes "\<not>((liminf u = \<infinity> \<and> liminf v = -\<infinity>) \<or> (liminf u = -\<infinity> \<and> liminf v = \<infinity>))"
  1527   assumes "\<not>((liminf u = \<infinity> \<and> liminf v = -\<infinity>) \<or> (liminf u = -\<infinity> \<and> liminf v = \<infinity>))"
  1528   shows "liminf (\<lambda>n. u n + v n) \<ge> liminf u + liminf v"
  1528   shows "liminf (\<lambda>n. u n + v n) \<ge> liminf u + liminf v"
  1529 proof%unimportant (cases)
  1529 proof (cases)
  1530   assume "(liminf u = -\<infinity>) \<or> (liminf v = -\<infinity>)"
  1530   assume "(liminf u = -\<infinity>) \<or> (liminf v = -\<infinity>)"
  1531   then have *: "liminf u + liminf v = -\<infinity>" using assms by auto
  1531   then have *: "liminf u + liminf v = -\<infinity>" using assms by auto
  1532   show ?thesis by (simp add: *)
  1532   show ?thesis by (simp add: *)
  1533 next
  1533 next
  1534   assume "\<not>((liminf u = -\<infinity>) \<or> (liminf v = -\<infinity>))"
  1534   assume "\<not>((liminf u = -\<infinity>) \<or> (liminf v = -\<infinity>))"
  1563   then have "liminf w \<ge> liminf u + liminf v"
  1563   then have "liminf w \<ge> liminf u + liminf v"
  1564     using \<open>liminf (u o r) \<ge> liminf u\<close> \<open>liminf (v o r o s) \<ge> liminf v\<close> add_mono by simp
  1564     using \<open>liminf (u o r) \<ge> liminf u\<close> \<open>liminf (v o r o s) \<ge> liminf v\<close> add_mono by simp
  1565   then show ?thesis unfolding w_def by simp
  1565   then show ?thesis unfolding w_def by simp
  1566 qed
  1566 qed
  1567 
  1567 
  1568 lemma%important ereal_limsup_lim_add:
  1568 lemma ereal_limsup_lim_add:
  1569   fixes u v::"nat \<Rightarrow> ereal"
  1569   fixes u v::"nat \<Rightarrow> ereal"
  1570   assumes "u \<longlonglongrightarrow> a" "abs(a) \<noteq> \<infinity>"
  1570   assumes "u \<longlonglongrightarrow> a" "abs(a) \<noteq> \<infinity>"
  1571   shows "limsup (\<lambda>n. u n + v n) = a + limsup v"
  1571   shows "limsup (\<lambda>n. u n + v n) = a + limsup v"
  1572 proof%unimportant -
  1572 proof -
  1573   have "limsup u = a" using assms(1) using tendsto_iff_Liminf_eq_Limsup trivial_limit_at_top_linorder by blast
  1573   have "limsup u = a" using assms(1) using tendsto_iff_Liminf_eq_Limsup trivial_limit_at_top_linorder by blast
  1574   have "(\<lambda>n. -u n) \<longlonglongrightarrow> -a" using assms(1) by auto
  1574   have "(\<lambda>n. -u n) \<longlonglongrightarrow> -a" using assms(1) by auto
  1575   then have "limsup (\<lambda>n. -u n) = -a" using tendsto_iff_Liminf_eq_Limsup trivial_limit_at_top_linorder by blast
  1575   then have "limsup (\<lambda>n. -u n) = -a" using tendsto_iff_Liminf_eq_Limsup trivial_limit_at_top_linorder by blast
  1576 
  1576 
  1577   have "limsup (\<lambda>n. u n + v n) \<le> limsup u + limsup v"
  1577   have "limsup (\<lambda>n. u n + v n) \<le> limsup u + limsup v"
  1594   then have "limsup v \<le> limsup (\<lambda>n. u n + v n) -a" using a \<open>limsup (\<lambda>n. -u n) = -a\<close> by (simp add: minus_ereal_def)
  1594   then have "limsup v \<le> limsup (\<lambda>n. u n + v n) -a" using a \<open>limsup (\<lambda>n. -u n) = -a\<close> by (simp add: minus_ereal_def)
  1595   then have "limsup (\<lambda>n. u n + v n) \<ge> a + limsup v" using assms(2) by (metis add.commute ereal_le_minus)
  1595   then have "limsup (\<lambda>n. u n + v n) \<ge> a + limsup v" using assms(2) by (metis add.commute ereal_le_minus)
  1596   then show ?thesis using up by simp
  1596   then show ?thesis using up by simp
  1597 qed
  1597 qed
  1598 
  1598 
  1599 lemma%important ereal_limsup_lim_mult:
  1599 lemma ereal_limsup_lim_mult:
  1600   fixes u v::"nat \<Rightarrow> ereal"
  1600   fixes u v::"nat \<Rightarrow> ereal"
  1601   assumes "u \<longlonglongrightarrow> a" "a>0" "a \<noteq> \<infinity>"
  1601   assumes "u \<longlonglongrightarrow> a" "a>0" "a \<noteq> \<infinity>"
  1602   shows "limsup (\<lambda>n. u n * v n) = a * limsup v"
  1602   shows "limsup (\<lambda>n. u n * v n) = a * limsup v"
  1603 proof%unimportant -
  1603 proof -
  1604   define w where "w = (\<lambda>n. u n * v n)"
  1604   define w where "w = (\<lambda>n. u n * v n)"
  1605   obtain r where r: "strict_mono r" "(v o r) \<longlonglongrightarrow> limsup v" using limsup_subseq_lim by auto
  1605   obtain r where r: "strict_mono r" "(v o r) \<longlonglongrightarrow> limsup v" using limsup_subseq_lim by auto
  1606   have "(u o r) \<longlonglongrightarrow> a" using assms(1) LIMSEQ_subseq_LIMSEQ r by auto
  1606   have "(u o r) \<longlonglongrightarrow> a" using assms(1) LIMSEQ_subseq_LIMSEQ r by auto
  1607   with tendsto_mult_ereal[OF this r(2)] have "(\<lambda>n. (u o r) n * (v o r) n) \<longlonglongrightarrow> a * limsup v" using assms(2) assms(3) by auto
  1607   with tendsto_mult_ereal[OF this r(2)] have "(\<lambda>n. (u o r) n * (v o r) n) \<longlonglongrightarrow> a * limsup v" using assms(2) assms(3) by auto
  1608   moreover have "\<And>n. (w o r) n = (u o r) n * (v o r) n" unfolding w_def by auto
  1608   moreover have "\<And>n. (w o r) n = (u o r) n * (v o r) n" unfolding w_def by auto
  1624   then have "limsup v \<ge> (limsup w) / a" by (metis limsup_subseq_mono s(1))
  1624   then have "limsup v \<ge> (limsup w) / a" by (metis limsup_subseq_mono s(1))
  1625   then have "a * limsup v \<ge> limsup w" using assms(2) assms(3) by (simp add: ereal_divide_le_pos)
  1625   then have "a * limsup v \<ge> limsup w" using assms(2) assms(3) by (simp add: ereal_divide_le_pos)
  1626   then show ?thesis using I unfolding w_def by auto
  1626   then show ?thesis using I unfolding w_def by auto
  1627 qed
  1627 qed
  1628 
  1628 
  1629 lemma%important ereal_liminf_lim_mult:
  1629 lemma ereal_liminf_lim_mult:
  1630   fixes u v::"nat \<Rightarrow> ereal"
  1630   fixes u v::"nat \<Rightarrow> ereal"
  1631   assumes "u \<longlonglongrightarrow> a" "a>0" "a \<noteq> \<infinity>"
  1631   assumes "u \<longlonglongrightarrow> a" "a>0" "a \<noteq> \<infinity>"
  1632   shows "liminf (\<lambda>n. u n * v n) = a * liminf v"
  1632   shows "liminf (\<lambda>n. u n * v n) = a * liminf v"
  1633 proof%unimportant -
  1633 proof -
  1634   define w where "w = (\<lambda>n. u n * v n)"
  1634   define w where "w = (\<lambda>n. u n * v n)"
  1635   obtain r where r: "strict_mono r" "(v o r) \<longlonglongrightarrow> liminf v" using liminf_subseq_lim by auto
  1635   obtain r where r: "strict_mono r" "(v o r) \<longlonglongrightarrow> liminf v" using liminf_subseq_lim by auto
  1636   have "(u o r) \<longlonglongrightarrow> a" using assms(1) LIMSEQ_subseq_LIMSEQ r by auto
  1636   have "(u o r) \<longlonglongrightarrow> a" using assms(1) LIMSEQ_subseq_LIMSEQ r by auto
  1637   with tendsto_mult_ereal[OF this r(2)] have "(\<lambda>n. (u o r) n * (v o r) n) \<longlonglongrightarrow> a * liminf v" using assms(2) assms(3) by auto
  1637   with tendsto_mult_ereal[OF this r(2)] have "(\<lambda>n. (u o r) n * (v o r) n) \<longlonglongrightarrow> a * liminf v" using assms(2) assms(3) by auto
  1638   moreover have "\<And>n. (w o r) n = (u o r) n * (v o r) n" unfolding w_def by auto
  1638   moreover have "\<And>n. (w o r) n = (u o r) n * (v o r) n" unfolding w_def by auto
  1654   then have "liminf v \<le> (liminf w) / a" by (metis liminf_subseq_mono s(1))
  1654   then have "liminf v \<le> (liminf w) / a" by (metis liminf_subseq_mono s(1))
  1655   then have "a * liminf v \<le> liminf w" using assms(2) assms(3) by (simp add: ereal_le_divide_pos)
  1655   then have "a * liminf v \<le> liminf w" using assms(2) assms(3) by (simp add: ereal_le_divide_pos)
  1656   then show ?thesis using I unfolding w_def by auto
  1656   then show ?thesis using I unfolding w_def by auto
  1657 qed
  1657 qed
  1658 
  1658 
  1659 lemma%important ereal_liminf_lim_add:
  1659 lemma ereal_liminf_lim_add:
  1660   fixes u v::"nat \<Rightarrow> ereal"
  1660   fixes u v::"nat \<Rightarrow> ereal"
  1661   assumes "u \<longlonglongrightarrow> a" "abs(a) \<noteq> \<infinity>"
  1661   assumes "u \<longlonglongrightarrow> a" "abs(a) \<noteq> \<infinity>"
  1662   shows "liminf (\<lambda>n. u n + v n) = a + liminf v"
  1662   shows "liminf (\<lambda>n. u n + v n) = a + liminf v"
  1663 proof%unimportant -
  1663 proof -
  1664   have "liminf u = a" using assms(1) tendsto_iff_Liminf_eq_Limsup trivial_limit_at_top_linorder by blast
  1664   have "liminf u = a" using assms(1) tendsto_iff_Liminf_eq_Limsup trivial_limit_at_top_linorder by blast
  1665   then have *: "abs(liminf u) \<noteq> \<infinity>" using assms(2) by auto
  1665   then have *: "abs(liminf u) \<noteq> \<infinity>" using assms(2) by auto
  1666   have "(\<lambda>n. -u n) \<longlonglongrightarrow> -a" using assms(1) by auto
  1666   have "(\<lambda>n. -u n) \<longlonglongrightarrow> -a" using assms(1) by auto
  1667   then have "liminf (\<lambda>n. -u n) = -a" using tendsto_iff_Liminf_eq_Limsup trivial_limit_at_top_linorder by blast
  1667   then have "liminf (\<lambda>n. -u n) = -a" using tendsto_iff_Liminf_eq_Limsup trivial_limit_at_top_linorder by blast
  1668   then have **: "abs(liminf (\<lambda>n. -u n)) \<noteq> \<infinity>" using assms(2) by auto
  1668   then have **: "abs(liminf (\<lambda>n. -u n)) \<noteq> \<infinity>" using assms(2) by auto
  1687   then have "liminf v \<ge> liminf (\<lambda>n. u n + v n) -a" using a \<open>liminf (\<lambda>n. -u n) = -a\<close> by (simp add: minus_ereal_def)
  1687   then have "liminf v \<ge> liminf (\<lambda>n. u n + v n) -a" using a \<open>liminf (\<lambda>n. -u n) = -a\<close> by (simp add: minus_ereal_def)
  1688   then have "liminf (\<lambda>n. u n + v n) \<le> a + liminf v" using assms(2) by (metis add.commute ereal_minus_le)
  1688   then have "liminf (\<lambda>n. u n + v n) \<le> a + liminf v" using assms(2) by (metis add.commute ereal_minus_le)
  1689   then show ?thesis using up by simp
  1689   then show ?thesis using up by simp
  1690 qed
  1690 qed
  1691 
  1691 
  1692 lemma%important ereal_liminf_limsup_add:
  1692 lemma ereal_liminf_limsup_add:
  1693   fixes u v::"nat \<Rightarrow> ereal"
  1693   fixes u v::"nat \<Rightarrow> ereal"
  1694   shows "liminf (\<lambda>n. u n + v n) \<le> liminf u + limsup v"
  1694   shows "liminf (\<lambda>n. u n + v n) \<le> liminf u + limsup v"
  1695 proof%unimportant (cases)
  1695 proof (cases)
  1696   assume "limsup v = \<infinity> \<or> liminf u = \<infinity>"
  1696   assume "limsup v = \<infinity> \<or> liminf u = \<infinity>"
  1697   then show ?thesis by auto
  1697   then show ?thesis by auto
  1698 next
  1698 next
  1699   assume "\<not>(limsup v = \<infinity> \<or> liminf u = \<infinity>)"
  1699   assume "\<not>(limsup v = \<infinity> \<or> liminf u = \<infinity>)"
  1700   then have "limsup v < \<infinity>" "liminf u < \<infinity>" by auto
  1700   then have "limsup v < \<infinity>" "liminf u < \<infinity>" by auto
  1739   using ereal_Limsup_uminus[of sequentially "\<lambda>n. - v n"]
  1739   using ereal_Limsup_uminus[of sequentially "\<lambda>n. - v n"]
  1740   apply (simp add: add.commute)
  1740   apply (simp add: add.commute)
  1741   done
  1741   done
  1742 
  1742 
  1743 
  1743 
  1744 lemma%important liminf_minus_ennreal:
  1744 lemma liminf_minus_ennreal:
  1745   fixes u v::"nat \<Rightarrow> ennreal"
  1745   fixes u v::"nat \<Rightarrow> ennreal"
  1746   shows "(\<And>n. v n \<le> u n) \<Longrightarrow> liminf (\<lambda>n. u n - v n) \<le> limsup u - limsup v"
  1746   shows "(\<And>n. v n \<le> u n) \<Longrightarrow> liminf (\<lambda>n. u n - v n) \<le> limsup u - limsup v"
  1747   unfolding liminf_SUP_INF limsup_INF_SUP
  1747   unfolding liminf_SUP_INF limsup_INF_SUP
  1748   including ennreal.lifting
  1748   including ennreal.lifting
  1749 proof%unimportant (transfer, clarsimp)
  1749 proof (transfer, clarsimp)
  1750   fix v u :: "nat \<Rightarrow> ereal" assume *: "\<forall>x. 0 \<le> v x" "\<forall>x. 0 \<le> u x" "\<And>n. v n \<le> u n"
  1750   fix v u :: "nat \<Rightarrow> ereal" assume *: "\<forall>x. 0 \<le> v x" "\<forall>x. 0 \<le> u x" "\<And>n. v n \<le> u n"
  1751   moreover have "0 \<le> limsup u - limsup v"
  1751   moreover have "0 \<le> limsup u - limsup v"
  1752     using * by (intro ereal_diff_positive Limsup_mono always_eventually) simp
  1752     using * by (intro ereal_diff_positive Limsup_mono always_eventually) simp
  1753   moreover have "0 \<le> Sup (u ` {x..})" for x
  1753   moreover have "0 \<le> Sup (u ` {x..})" for x
  1754     using * by (intro SUP_upper2[of x]) auto
  1754     using * by (intro SUP_upper2[of x]) auto
  1757   ultimately show "(SUP n. INF n\<in>{n..}. max 0 (u n - v n))
  1757   ultimately show "(SUP n. INF n\<in>{n..}. max 0 (u n - v n))
  1758             \<le> max 0 ((INF x. max 0 (Sup (u ` {x..}))) - (INF x. max 0 (Sup (v ` {x..}))))"
  1758             \<le> max 0 ((INF x. max 0 (Sup (u ` {x..}))) - (INF x. max 0 (Sup (v ` {x..}))))"
  1759     by (auto simp: * ereal_diff_positive max.absorb2 liminf_SUP_INF[symmetric] limsup_INF_SUP[symmetric] ereal_liminf_limsup_minus)
  1759     by (auto simp: * ereal_diff_positive max.absorb2 liminf_SUP_INF[symmetric] limsup_INF_SUP[symmetric] ereal_liminf_limsup_minus)
  1760 qed
  1760 qed
  1761 
  1761 
  1762 subsection%unimportant "Relate extended reals and the indicator function"
  1762 subsection%important "Relate extended reals and the indicator function"
  1763 
  1763 
  1764 lemma ereal_indicator_le_0: "(indicator S x::ereal) \<le> 0 \<longleftrightarrow> x \<notin> S"
  1764 lemma ereal_indicator_le_0: "(indicator S x::ereal) \<le> 0 \<longleftrightarrow> x \<notin> S"
  1765   by (auto split: split_indicator simp: one_ereal_def)
  1765   by (auto split: split_indicator simp: one_ereal_def)
  1766 
  1766 
  1767 lemma ereal_indicator: "ereal (indicator A x) = indicator A x"
  1767 lemma ereal_indicator: "ereal (indicator A x) = indicator A x"