127 fixes K::"nat set" |
127 fixes K::"nat set" |
128 assumes "K \<noteq> {}" |
128 assumes "K \<noteq> {}" |
129 shows "Inf K \<in> K" |
129 shows "Inf K \<in> K" |
130 by (auto simp add: Min_def Inf_nat_def) (meson LeastI assms bot.extremum_unique subsetI) |
130 by (auto simp add: Min_def Inf_nat_def) (meson LeastI assms bot.extremum_unique subsetI) |
131 |
131 |
132 subsection {*Liminf-Limsup.thy*} |
132 subsection \<open>Liminf-Limsup.thy\<close> |
133 |
133 |
134 lemma limsup_shift: |
134 lemma limsup_shift: |
135 "limsup (\<lambda>n. u (n+1)) = limsup u" |
135 "limsup (\<lambda>n. u (n+1)) = limsup u" |
136 proof - |
136 proof - |
137 have "(SUP m:{n+1..}. u m) = (SUP m:{n..}. u (m + 1))" for n |
137 have "(SUP m:{n+1..}. u m) = (SUP m:{n..}. u (m + 1))" for n |
138 apply (rule SUP_eq) using Suc_le_D by auto |
138 apply (rule SUP_eq) using Suc_le_D by auto |
139 then have a: "(INF n. SUP m:{n..}. u (m + 1)) = (INF n. (SUP m:{n+1..}. u m))" by auto |
139 then have a: "(INF n. SUP m:{n..}. u (m + 1)) = (INF n. (SUP m:{n+1..}. u m))" by auto |
140 have b: "(INF n. (SUP m:{n+1..}. u m)) = (INF n:{1..}. (SUP m:{n..}. u m))" |
140 have b: "(INF n. (SUP m:{n+1..}. u m)) = (INF n:{1..}. (SUP m:{n..}. u m))" |
141 apply (rule INF_eq) using Suc_le_D by auto |
141 apply (rule INF_eq) using Suc_le_D by auto |
142 have "(INF n:{1..}. v n) = (INF n. v n)" if "decseq v" for v::"nat \<Rightarrow> 'a" |
142 have "(INF n:{1..}. v n) = (INF n. v n)" if "decseq v" for v::"nat \<Rightarrow> 'a" |
143 apply (rule INF_eq) using `decseq v` decseq_Suc_iff by auto |
143 apply (rule INF_eq) using \<open>decseq v\<close> decseq_Suc_iff by auto |
144 moreover have "decseq (\<lambda>n. (SUP m:{n..}. u m))" by (simp add: SUP_subset_mono decseq_def) |
144 moreover have "decseq (\<lambda>n. (SUP m:{n..}. u m))" by (simp add: SUP_subset_mono decseq_def) |
145 ultimately have c: "(INF n:{1..}. (SUP m:{n..}. u m)) = (INF n. (SUP m:{n..}. u m))" by simp |
145 ultimately have c: "(INF n:{1..}. (SUP m:{n..}. u m)) = (INF n. (SUP m:{n..}. u m))" by simp |
146 have "(INF n. SUPREMUM {n..} u) = (INF n. SUP m:{n..}. u (m + 1))" using a b c by simp |
146 have "(INF n. SUPREMUM {n..} u) = (INF n. SUP m:{n..}. u (m + 1))" using a b c by simp |
147 then show ?thesis by (auto cong: limsup_INF_SUP) |
147 then show ?thesis by (auto cong: limsup_INF_SUP) |
148 qed |
148 qed |
201 then obtain r where "subseq r" and mono: "\<And>n m. r n \<le> m \<Longrightarrow> u m \<le> u (r n)" |
201 then obtain r where "subseq r" and mono: "\<And>n m. r n \<le> m \<Longrightarrow> u m \<le> u (r n)" |
202 by (auto simp: subseq_Suc_iff) |
202 by (auto simp: subseq_Suc_iff) |
203 define umax where "umax = (\<lambda>n. (SUP m:{n..}. u m))" |
203 define umax where "umax = (\<lambda>n. (SUP m:{n..}. u m))" |
204 have "decseq umax" unfolding umax_def by (simp add: SUP_subset_mono antimono_def) |
204 have "decseq umax" unfolding umax_def by (simp add: SUP_subset_mono antimono_def) |
205 then have "umax \<longlonglongrightarrow> limsup u" unfolding umax_def by (metis LIMSEQ_INF limsup_INF_SUP) |
205 then have "umax \<longlonglongrightarrow> limsup u" unfolding umax_def by (metis LIMSEQ_INF limsup_INF_SUP) |
206 then have *: "(umax o r) \<longlonglongrightarrow> limsup u" by (simp add: LIMSEQ_subseq_LIMSEQ `subseq r`) |
206 then have *: "(umax o r) \<longlonglongrightarrow> limsup u" by (simp add: LIMSEQ_subseq_LIMSEQ \<open>subseq r\<close>) |
207 have "\<And>n. umax(r n) = u(r n)" unfolding umax_def using mono |
207 have "\<And>n. umax(r n) = u(r n)" unfolding umax_def using mono |
208 by (metis SUP_le_iff antisym atLeast_def mem_Collect_eq order_refl) |
208 by (metis SUP_le_iff antisym atLeast_def mem_Collect_eq order_refl) |
209 then have "umax o r = u o r" unfolding o_def by simp |
209 then have "umax o r = u o r" unfolding o_def by simp |
210 then have "(u o r) \<longlonglongrightarrow> limsup u" using * by simp |
210 then have "(u o r) \<longlonglongrightarrow> limsup u" using * by simp |
211 then show ?thesis using `subseq r` by blast |
211 then show ?thesis using \<open>subseq r\<close> by blast |
212 next |
212 next |
213 assume "\<not> (\<forall>n. \<exists>p>n. (\<forall>m\<ge>p. u m \<le> u p))" |
213 assume "\<not> (\<forall>n. \<exists>p>n. (\<forall>m\<ge>p. u m \<le> u p))" |
214 then obtain N where N: "\<And>p. p > N \<Longrightarrow> \<exists>m>p. u p < u m" by (force simp: not_le le_less) |
214 then obtain N where N: "\<And>p. p > N \<Longrightarrow> \<exists>m>p. u p < u m" by (force simp: not_le le_less) |
215 have "\<exists>r. \<forall>n. N < r n \<and> r n < r (Suc n) \<and> (\<forall>i\<in> {N<..r (Suc n)}. u i \<le> u (r (Suc n)))" |
215 have "\<exists>r. \<forall>n. N < r n \<and> r n < r (Suc n) \<and> (\<forall>i\<in> {N<..r (Suc n)}. u i \<le> u (r (Suc n)))" |
216 proof (rule dependent_nat_choice) |
216 proof (rule dependent_nat_choice) |
217 fix x assume "N < x" |
217 fix x assume "N < x" |
218 then have a: "finite {N<..x}" "{N<..x} \<noteq> {}" by simp_all |
218 then have a: "finite {N<..x}" "{N<..x} \<noteq> {}" by simp_all |
219 have "Max {u i |i. i \<in> {N<..x}} \<in> {u i |i. i \<in> {N<..x}}" apply (rule Max_in) using a by (auto) |
219 have "Max {u i |i. i \<in> {N<..x}} \<in> {u i |i. i \<in> {N<..x}}" apply (rule Max_in) using a by (auto) |
220 then obtain p where "p \<in> {N<..x}" and upmax: "u p = Max{u i |i. i \<in> {N<..x}}" by auto |
220 then obtain p where "p \<in> {N<..x}" and upmax: "u p = Max{u i |i. i \<in> {N<..x}}" by auto |
221 define U where "U = {m. m > p \<and> u p < u m}" |
221 define U where "U = {m. m > p \<and> u p < u m}" |
222 have "U \<noteq> {}" unfolding U_def using N[of p] `p \<in> {N<..x}` by auto |
222 have "U \<noteq> {}" unfolding U_def using N[of p] \<open>p \<in> {N<..x}\<close> by auto |
223 define y where "y = Inf U" |
223 define y where "y = Inf U" |
224 then have "y \<in> U" using `U \<noteq> {}` by (simp add: Inf_nat_def1) |
224 then have "y \<in> U" using \<open>U \<noteq> {}\<close> by (simp add: Inf_nat_def1) |
225 have a: "\<And>i. i \<in> {N<..x} \<Longrightarrow> u i \<le> u p" |
225 have a: "\<And>i. i \<in> {N<..x} \<Longrightarrow> u i \<le> u p" |
226 proof - |
226 proof - |
227 fix i assume "i \<in> {N<..x}" |
227 fix i assume "i \<in> {N<..x}" |
228 then have "u i \<in> {u i |i. i \<in> {N<..x}}" by blast |
228 then have "u i \<in> {u i |i. i \<in> {N<..x}}" by blast |
229 then show "u i \<le> u p" using upmax by simp |
229 then show "u i \<le> u p" using upmax by simp |
230 qed |
230 qed |
231 moreover have "u p < u y" using `y \<in> U` U_def by auto |
231 moreover have "u p < u y" using \<open>y \<in> U\<close> U_def by auto |
232 ultimately have "y \<notin> {N<..x}" using not_le by blast |
232 ultimately have "y \<notin> {N<..x}" using not_le by blast |
233 moreover have "y > N" using `y \<in> U` U_def `p \<in> {N<..x}` by auto |
233 moreover have "y > N" using \<open>y \<in> U\<close> U_def \<open>p \<in> {N<..x}\<close> by auto |
234 ultimately have "y > x" by auto |
234 ultimately have "y > x" by auto |
235 |
235 |
236 have "\<And>i. i \<in> {N<..y} \<Longrightarrow> u i \<le> u y" |
236 have "\<And>i. i \<in> {N<..y} \<Longrightarrow> u i \<le> u y" |
237 proof - |
237 proof - |
238 fix i assume "i \<in> {N<..y}" show "u i \<le> u y" |
238 fix i assume "i \<in> {N<..y}" show "u i \<le> u y" |
239 proof (cases) |
239 proof (cases) |
240 assume "i = y" |
240 assume "i = y" |
241 then show ?thesis by simp |
241 then show ?thesis by simp |
242 next |
242 next |
243 assume "\<not>(i=y)" |
243 assume "\<not>(i=y)" |
244 then have i:"i \<in> {N<..<y}" using `i \<in> {N<..y}` by simp |
244 then have i:"i \<in> {N<..<y}" using \<open>i \<in> {N<..y}\<close> by simp |
245 have "u i \<le> u p" |
245 have "u i \<le> u p" |
246 proof (cases) |
246 proof (cases) |
247 assume "i \<le> x" |
247 assume "i \<le> x" |
248 then have "i \<in> {N<..x}" using i by simp |
248 then have "i \<in> {N<..x}" using i by simp |
249 then show ?thesis using a by simp |
249 then show ?thesis using a by simp |
250 next |
250 next |
251 assume "\<not>(i \<le> x)" |
251 assume "\<not>(i \<le> x)" |
252 then have "i > x" by simp |
252 then have "i > x" by simp |
253 then have *: "i > p" using `p \<in> {N<..x}` by simp |
253 then have *: "i > p" using \<open>p \<in> {N<..x}\<close> by simp |
254 have "i < Inf U" using i y_def by simp |
254 have "i < Inf U" using i y_def by simp |
255 then have "i \<notin> U" using Inf_nat_def not_less_Least by auto |
255 then have "i \<notin> U" using Inf_nat_def not_less_Least by auto |
256 then show ?thesis using U_def * by auto |
256 then show ?thesis using U_def * by auto |
257 qed |
257 qed |
258 then show "u i \<le> u y" using `u p < u y` by auto |
258 then show "u i \<le> u y" using \<open>u p < u y\<close> by auto |
259 qed |
259 qed |
260 qed |
260 qed |
261 then have "N < y \<and> x < y \<and> (\<forall>i\<in>{N<..y}. u i \<le> u y)" using `y > x` `y > N` by auto |
261 then have "N < y \<and> x < y \<and> (\<forall>i\<in>{N<..y}. u i \<le> u y)" using \<open>y > x\<close> \<open>y > N\<close> by auto |
262 then show "\<exists>y>N. x < y \<and> (\<forall>i\<in>{N<..y}. u i \<le> u y)" by auto |
262 then show "\<exists>y>N. x < y \<and> (\<forall>i\<in>{N<..y}. u i \<le> u y)" by auto |
263 qed (auto) |
263 qed (auto) |
264 then obtain r where r: "\<forall>n. N < r n \<and> r n < r (Suc n) \<and> (\<forall>i\<in> {N<..r (Suc n)}. u i \<le> u (r (Suc n)))" by auto |
264 then obtain r where r: "\<forall>n. N < r n \<and> r n < r (Suc n) \<and> (\<forall>i\<in> {N<..r (Suc n)}. u i \<le> u (r (Suc n)))" by auto |
265 have "subseq r" using r by (auto simp: subseq_Suc_iff) |
265 have "subseq r" using r by (auto simp: subseq_Suc_iff) |
266 have "incseq (u o r)" unfolding o_def using r by (simp add: incseq_SucI order.strict_implies_order) |
266 have "incseq (u o r)" unfolding o_def using r by (simp add: incseq_SucI order.strict_implies_order) |
267 then have "(u o r) \<longlonglongrightarrow> (SUP n. (u o r) n)" using LIMSEQ_SUP by blast |
267 then have "(u o r) \<longlonglongrightarrow> (SUP n. (u o r) n)" using LIMSEQ_SUP by blast |
268 then have "limsup (u o r) = (SUP n. (u o r) n)" by (simp add: lim_imp_Limsup) |
268 then have "limsup (u o r) = (SUP n. (u o r) n)" by (simp add: lim_imp_Limsup) |
269 moreover have "limsup (u o r) \<le> limsup u" using `subseq r` by (simp add: limsup_subseq_mono) |
269 moreover have "limsup (u o r) \<le> limsup u" using \<open>subseq r\<close> by (simp add: limsup_subseq_mono) |
270 ultimately have "(SUP n. (u o r) n) \<le> limsup u" by simp |
270 ultimately have "(SUP n. (u o r) n) \<le> limsup u" by simp |
271 |
271 |
272 { |
272 { |
273 fix i assume i: "i \<in> {N<..}" |
273 fix i assume i: "i \<in> {N<..}" |
274 obtain n where "i < r (Suc n)" using `subseq r` using Suc_le_eq seq_suble by blast |
274 obtain n where "i < r (Suc n)" using \<open>subseq r\<close> using Suc_le_eq seq_suble by blast |
275 then have "i \<in> {N<..r(Suc n)}" using i by simp |
275 then have "i \<in> {N<..r(Suc n)}" using i by simp |
276 then have "u i \<le> u (r(Suc n))" using r by simp |
276 then have "u i \<le> u (r(Suc n))" using r by simp |
277 then have "u i \<le> (SUP n. (u o r) n)" unfolding o_def by (meson SUP_upper2 UNIV_I) |
277 then have "u i \<le> (SUP n. (u o r) n)" unfolding o_def by (meson SUP_upper2 UNIV_I) |
278 } |
278 } |
279 then have "(SUP i:{N<..}. u i) \<le> (SUP n. (u o r) n)" using SUP_least by blast |
279 then have "(SUP i:{N<..}. u i) \<le> (SUP n. (u o r) n)" using SUP_least by blast |
280 then have "limsup u \<le> (SUP n. (u o r) n)" unfolding Limsup_def |
280 then have "limsup u \<le> (SUP n. (u o r) n)" unfolding Limsup_def |
281 by (metis (mono_tags, lifting) INF_lower2 atLeast_Suc_greaterThan atLeast_def eventually_ge_at_top mem_Collect_eq) |
281 by (metis (mono_tags, lifting) INF_lower2 atLeast_Suc_greaterThan atLeast_def eventually_ge_at_top mem_Collect_eq) |
282 then have "limsup u = (SUP n. (u o r) n)" using `(SUP n. (u o r) n) \<le> limsup u` by simp |
282 then have "limsup u = (SUP n. (u o r) n)" using \<open>(SUP n. (u o r) n) \<le> limsup u\<close> by simp |
283 then have "(u o r) \<longlonglongrightarrow> limsup u" using `(u o r) \<longlonglongrightarrow> (SUP n. (u o r) n)` by simp |
283 then have "(u o r) \<longlonglongrightarrow> limsup u" using \<open>(u o r) \<longlonglongrightarrow> (SUP n. (u o r) n)\<close> by simp |
284 then show ?thesis using `subseq r` by auto |
284 then show ?thesis using \<open>subseq r\<close> by auto |
285 qed |
285 qed |
286 |
286 |
287 lemma liminf_subseq_lim: |
287 lemma liminf_subseq_lim: |
288 fixes u::"nat \<Rightarrow> 'a :: {complete_linorder, linorder_topology}" |
288 fixes u::"nat \<Rightarrow> 'a :: {complete_linorder, linorder_topology}" |
289 shows "\<exists>r. subseq r \<and> (u o r) \<longlonglongrightarrow> liminf u" |
289 shows "\<exists>r. subseq r \<and> (u o r) \<longlonglongrightarrow> liminf u" |
294 then obtain r where "subseq r" and mono: "\<And>n m. r n \<le> m \<Longrightarrow> u m \<ge> u (r n)" |
294 then obtain r where "subseq r" and mono: "\<And>n m. r n \<le> m \<Longrightarrow> u m \<ge> u (r n)" |
295 by (auto simp: subseq_Suc_iff) |
295 by (auto simp: subseq_Suc_iff) |
296 define umin where "umin = (\<lambda>n. (INF m:{n..}. u m))" |
296 define umin where "umin = (\<lambda>n. (INF m:{n..}. u m))" |
297 have "incseq umin" unfolding umin_def by (simp add: INF_superset_mono incseq_def) |
297 have "incseq umin" unfolding umin_def by (simp add: INF_superset_mono incseq_def) |
298 then have "umin \<longlonglongrightarrow> liminf u" unfolding umin_def by (metis LIMSEQ_SUP liminf_SUP_INF) |
298 then have "umin \<longlonglongrightarrow> liminf u" unfolding umin_def by (metis LIMSEQ_SUP liminf_SUP_INF) |
299 then have *: "(umin o r) \<longlonglongrightarrow> liminf u" by (simp add: LIMSEQ_subseq_LIMSEQ `subseq r`) |
299 then have *: "(umin o r) \<longlonglongrightarrow> liminf u" by (simp add: LIMSEQ_subseq_LIMSEQ \<open>subseq r\<close>) |
300 have "\<And>n. umin(r n) = u(r n)" unfolding umin_def using mono |
300 have "\<And>n. umin(r n) = u(r n)" unfolding umin_def using mono |
301 by (metis le_INF_iff antisym atLeast_def mem_Collect_eq order_refl) |
301 by (metis le_INF_iff antisym atLeast_def mem_Collect_eq order_refl) |
302 then have "umin o r = u o r" unfolding o_def by simp |
302 then have "umin o r = u o r" unfolding o_def by simp |
303 then have "(u o r) \<longlonglongrightarrow> liminf u" using * by simp |
303 then have "(u o r) \<longlonglongrightarrow> liminf u" using * by simp |
304 then show ?thesis using `subseq r` by blast |
304 then show ?thesis using \<open>subseq r\<close> by blast |
305 next |
305 next |
306 assume "\<not> (\<forall>n. \<exists>p>n. (\<forall>m\<ge>p. u m \<ge> u p))" |
306 assume "\<not> (\<forall>n. \<exists>p>n. (\<forall>m\<ge>p. u m \<ge> u p))" |
307 then obtain N where N: "\<And>p. p > N \<Longrightarrow> \<exists>m>p. u p > u m" by (force simp: not_le le_less) |
307 then obtain N where N: "\<And>p. p > N \<Longrightarrow> \<exists>m>p. u p > u m" by (force simp: not_le le_less) |
308 have "\<exists>r. \<forall>n. N < r n \<and> r n < r (Suc n) \<and> (\<forall>i\<in> {N<..r (Suc n)}. u i \<ge> u (r (Suc n)))" |
308 have "\<exists>r. \<forall>n. N < r n \<and> r n < r (Suc n) \<and> (\<forall>i\<in> {N<..r (Suc n)}. u i \<ge> u (r (Suc n)))" |
309 proof (rule dependent_nat_choice) |
309 proof (rule dependent_nat_choice) |
310 fix x assume "N < x" |
310 fix x assume "N < x" |
311 then have a: "finite {N<..x}" "{N<..x} \<noteq> {}" by simp_all |
311 then have a: "finite {N<..x}" "{N<..x} \<noteq> {}" by simp_all |
312 have "Min {u i |i. i \<in> {N<..x}} \<in> {u i |i. i \<in> {N<..x}}" apply (rule Min_in) using a by (auto) |
312 have "Min {u i |i. i \<in> {N<..x}} \<in> {u i |i. i \<in> {N<..x}}" apply (rule Min_in) using a by (auto) |
313 then obtain p where "p \<in> {N<..x}" and upmin: "u p = Min{u i |i. i \<in> {N<..x}}" by auto |
313 then obtain p where "p \<in> {N<..x}" and upmin: "u p = Min{u i |i. i \<in> {N<..x}}" by auto |
314 define U where "U = {m. m > p \<and> u p > u m}" |
314 define U where "U = {m. m > p \<and> u p > u m}" |
315 have "U \<noteq> {}" unfolding U_def using N[of p] `p \<in> {N<..x}` by auto |
315 have "U \<noteq> {}" unfolding U_def using N[of p] \<open>p \<in> {N<..x}\<close> by auto |
316 define y where "y = Inf U" |
316 define y where "y = Inf U" |
317 then have "y \<in> U" using `U \<noteq> {}` by (simp add: Inf_nat_def1) |
317 then have "y \<in> U" using \<open>U \<noteq> {}\<close> by (simp add: Inf_nat_def1) |
318 have a: "\<And>i. i \<in> {N<..x} \<Longrightarrow> u i \<ge> u p" |
318 have a: "\<And>i. i \<in> {N<..x} \<Longrightarrow> u i \<ge> u p" |
319 proof - |
319 proof - |
320 fix i assume "i \<in> {N<..x}" |
320 fix i assume "i \<in> {N<..x}" |
321 then have "u i \<in> {u i |i. i \<in> {N<..x}}" by blast |
321 then have "u i \<in> {u i |i. i \<in> {N<..x}}" by blast |
322 then show "u i \<ge> u p" using upmin by simp |
322 then show "u i \<ge> u p" using upmin by simp |
323 qed |
323 qed |
324 moreover have "u p > u y" using `y \<in> U` U_def by auto |
324 moreover have "u p > u y" using \<open>y \<in> U\<close> U_def by auto |
325 ultimately have "y \<notin> {N<..x}" using not_le by blast |
325 ultimately have "y \<notin> {N<..x}" using not_le by blast |
326 moreover have "y > N" using `y \<in> U` U_def `p \<in> {N<..x}` by auto |
326 moreover have "y > N" using \<open>y \<in> U\<close> U_def \<open>p \<in> {N<..x}\<close> by auto |
327 ultimately have "y > x" by auto |
327 ultimately have "y > x" by auto |
328 |
328 |
329 have "\<And>i. i \<in> {N<..y} \<Longrightarrow> u i \<ge> u y" |
329 have "\<And>i. i \<in> {N<..y} \<Longrightarrow> u i \<ge> u y" |
330 proof - |
330 proof - |
331 fix i assume "i \<in> {N<..y}" show "u i \<ge> u y" |
331 fix i assume "i \<in> {N<..y}" show "u i \<ge> u y" |
332 proof (cases) |
332 proof (cases) |
333 assume "i = y" |
333 assume "i = y" |
334 then show ?thesis by simp |
334 then show ?thesis by simp |
335 next |
335 next |
336 assume "\<not>(i=y)" |
336 assume "\<not>(i=y)" |
337 then have i:"i \<in> {N<..<y}" using `i \<in> {N<..y}` by simp |
337 then have i:"i \<in> {N<..<y}" using \<open>i \<in> {N<..y}\<close> by simp |
338 have "u i \<ge> u p" |
338 have "u i \<ge> u p" |
339 proof (cases) |
339 proof (cases) |
340 assume "i \<le> x" |
340 assume "i \<le> x" |
341 then have "i \<in> {N<..x}" using i by simp |
341 then have "i \<in> {N<..x}" using i by simp |
342 then show ?thesis using a by simp |
342 then show ?thesis using a by simp |
343 next |
343 next |
344 assume "\<not>(i \<le> x)" |
344 assume "\<not>(i \<le> x)" |
345 then have "i > x" by simp |
345 then have "i > x" by simp |
346 then have *: "i > p" using `p \<in> {N<..x}` by simp |
346 then have *: "i > p" using \<open>p \<in> {N<..x}\<close> by simp |
347 have "i < Inf U" using i y_def by simp |
347 have "i < Inf U" using i y_def by simp |
348 then have "i \<notin> U" using Inf_nat_def not_less_Least by auto |
348 then have "i \<notin> U" using Inf_nat_def not_less_Least by auto |
349 then show ?thesis using U_def * by auto |
349 then show ?thesis using U_def * by auto |
350 qed |
350 qed |
351 then show "u i \<ge> u y" using `u p > u y` by auto |
351 then show "u i \<ge> u y" using \<open>u p > u y\<close> by auto |
352 qed |
352 qed |
353 qed |
353 qed |
354 then have "N < y \<and> x < y \<and> (\<forall>i\<in>{N<..y}. u i \<ge> u y)" using `y > x` `y > N` by auto |
354 then have "N < y \<and> x < y \<and> (\<forall>i\<in>{N<..y}. u i \<ge> u y)" using \<open>y > x\<close> \<open>y > N\<close> by auto |
355 then show "\<exists>y>N. x < y \<and> (\<forall>i\<in>{N<..y}. u i \<ge> u y)" by auto |
355 then show "\<exists>y>N. x < y \<and> (\<forall>i\<in>{N<..y}. u i \<ge> u y)" by auto |
356 qed (auto) |
356 qed (auto) |
357 then obtain r where r: "\<forall>n. N < r n \<and> r n < r (Suc n) \<and> (\<forall>i\<in> {N<..r (Suc n)}. u i \<ge> u (r (Suc n)))" by auto |
357 then obtain r where r: "\<forall>n. N < r n \<and> r n < r (Suc n) \<and> (\<forall>i\<in> {N<..r (Suc n)}. u i \<ge> u (r (Suc n)))" by auto |
358 have "subseq r" using r by (auto simp: subseq_Suc_iff) |
358 have "subseq r" using r by (auto simp: subseq_Suc_iff) |
359 have "decseq (u o r)" unfolding o_def using r by (simp add: decseq_SucI order.strict_implies_order) |
359 have "decseq (u o r)" unfolding o_def using r by (simp add: decseq_SucI order.strict_implies_order) |
360 then have "(u o r) \<longlonglongrightarrow> (INF n. (u o r) n)" using LIMSEQ_INF by blast |
360 then have "(u o r) \<longlonglongrightarrow> (INF n. (u o r) n)" using LIMSEQ_INF by blast |
361 then have "liminf (u o r) = (INF n. (u o r) n)" by (simp add: lim_imp_Liminf) |
361 then have "liminf (u o r) = (INF n. (u o r) n)" by (simp add: lim_imp_Liminf) |
362 moreover have "liminf (u o r) \<ge> liminf u" using `subseq r` by (simp add: liminf_subseq_mono) |
362 moreover have "liminf (u o r) \<ge> liminf u" using \<open>subseq r\<close> by (simp add: liminf_subseq_mono) |
363 ultimately have "(INF n. (u o r) n) \<ge> liminf u" by simp |
363 ultimately have "(INF n. (u o r) n) \<ge> liminf u" by simp |
364 |
364 |
365 { |
365 { |
366 fix i assume i: "i \<in> {N<..}" |
366 fix i assume i: "i \<in> {N<..}" |
367 obtain n where "i < r (Suc n)" using `subseq r` using Suc_le_eq seq_suble by blast |
367 obtain n where "i < r (Suc n)" using \<open>subseq r\<close> using Suc_le_eq seq_suble by blast |
368 then have "i \<in> {N<..r(Suc n)}" using i by simp |
368 then have "i \<in> {N<..r(Suc n)}" using i by simp |
369 then have "u i \<ge> u (r(Suc n))" using r by simp |
369 then have "u i \<ge> u (r(Suc n))" using r by simp |
370 then have "u i \<ge> (INF n. (u o r) n)" unfolding o_def by (meson INF_lower2 UNIV_I) |
370 then have "u i \<ge> (INF n. (u o r) n)" unfolding o_def by (meson INF_lower2 UNIV_I) |
371 } |
371 } |
372 then have "(INF i:{N<..}. u i) \<ge> (INF n. (u o r) n)" using INF_greatest by blast |
372 then have "(INF i:{N<..}. u i) \<ge> (INF n. (u o r) n)" using INF_greatest by blast |
373 then have "liminf u \<ge> (INF n. (u o r) n)" unfolding Liminf_def |
373 then have "liminf u \<ge> (INF n. (u o r) n)" unfolding Liminf_def |
374 by (metis (mono_tags, lifting) SUP_upper2 atLeast_Suc_greaterThan atLeast_def eventually_ge_at_top mem_Collect_eq) |
374 by (metis (mono_tags, lifting) SUP_upper2 atLeast_Suc_greaterThan atLeast_def eventually_ge_at_top mem_Collect_eq) |
375 then have "liminf u = (INF n. (u o r) n)" using `(INF n. (u o r) n) \<ge> liminf u` by simp |
375 then have "liminf u = (INF n. (u o r) n)" using \<open>(INF n. (u o r) n) \<ge> liminf u\<close> by simp |
376 then have "(u o r) \<longlonglongrightarrow> liminf u" using `(u o r) \<longlonglongrightarrow> (INF n. (u o r) n)` by simp |
376 then have "(u o r) \<longlonglongrightarrow> liminf u" using \<open>(u o r) \<longlonglongrightarrow> (INF n. (u o r) n)\<close> by simp |
377 then show ?thesis using `subseq r` by auto |
377 then show ?thesis using \<open>subseq r\<close> by auto |
378 qed |
378 qed |
379 |
379 |
380 |
380 |
381 subsection {*Extended-Real.thy*} |
381 subsection \<open>Extended-Real.thy\<close> |
382 |
382 |
383 text{* The proof of this one is copied from \verb+ereal_add_mono+. *} |
383 text\<open>The proof of this one is copied from \verb+ereal_add_mono+.\<close> |
384 lemma ereal_add_strict_mono2: |
384 lemma ereal_add_strict_mono2: |
385 fixes a b c d :: ereal |
385 fixes a b c d :: ereal |
386 assumes "a < b" |
386 assumes "a < b" |
387 and "c < d" |
387 and "c < d" |
388 shows "a + c < b + d" |
388 shows "a + c < b + d" |
629 fixes f g::"_ \<Rightarrow> ereal" |
629 fixes f g::"_ \<Rightarrow> ereal" |
630 assumes "(f \<longlongrightarrow> l) F" "l>0" "(g \<longlongrightarrow> \<infinity>) F" |
630 assumes "(f \<longlongrightarrow> l) F" "l>0" "(g \<longlongrightarrow> \<infinity>) F" |
631 shows "((\<lambda>x. f x * g x) \<longlongrightarrow> \<infinity>) F" |
631 shows "((\<lambda>x. f x * g x) \<longlongrightarrow> \<infinity>) F" |
632 proof - |
632 proof - |
633 obtain a::real where "0 < ereal a" "a < l" using assms(2) using ereal_dense2 by blast |
633 obtain a::real where "0 < ereal a" "a < l" using assms(2) using ereal_dense2 by blast |
634 have *: "eventually (\<lambda>x. f x > a) F" using `a < l` assms(1) by (simp add: order_tendsto_iff) |
634 have *: "eventually (\<lambda>x. f x > a) F" using \<open>a < l\<close> assms(1) by (simp add: order_tendsto_iff) |
635 { |
635 { |
636 fix K::real |
636 fix K::real |
637 define M where "M = max K 1" |
637 define M where "M = max K 1" |
638 then have "M > 0" by simp |
638 then have "M > 0" by simp |
639 then have "ereal(M/a) > 0" using `ereal a > 0` by simp |
639 then have "ereal(M/a) > 0" using \<open>ereal a > 0\<close> by simp |
640 then have "\<And>x. ((f x > a) \<and> (g x > M/a)) \<Longrightarrow> (f x * g x > ereal a * ereal(M/a))" |
640 then have "\<And>x. ((f x > a) \<and> (g x > M/a)) \<Longrightarrow> (f x * g x > ereal a * ereal(M/a))" |
641 using ereal_mult_mono_strict'[where ?c = "M/a", OF `0 < ereal a`] by auto |
641 using ereal_mult_mono_strict'[where ?c = "M/a", OF \<open>0 < ereal a\<close>] by auto |
642 moreover have "ereal a * ereal(M/a) = M" using `ereal a > 0` by simp |
642 moreover have "ereal a * ereal(M/a) = M" using \<open>ereal a > 0\<close> by simp |
643 ultimately have "\<And>x. ((f x > a) \<and> (g x > M/a)) \<Longrightarrow> (f x * g x > M)" by simp |
643 ultimately have "\<And>x. ((f x > a) \<and> (g x > M/a)) \<Longrightarrow> (f x * g x > M)" by simp |
644 moreover have "M \<ge> K" unfolding M_def by simp |
644 moreover have "M \<ge> K" unfolding M_def by simp |
645 ultimately have Imp: "\<And>x. ((f x > a) \<and> (g x > M/a)) \<Longrightarrow> (f x * g x > K)" |
645 ultimately have Imp: "\<And>x. ((f x > a) \<and> (g x > M/a)) \<Longrightarrow> (f x * g x > K)" |
646 using ereal_less_eq(3) le_less_trans by blast |
646 using ereal_less_eq(3) le_less_trans by blast |
647 |
647 |
718 ultimately have *: "((\<lambda>x. (sgn(l) * f x) * (sgn(m) * g x)) \<longlongrightarrow> (sgn(l) * l) * (sgn(m) * m)) F" |
718 ultimately have *: "((\<lambda>x. (sgn(l) * f x) * (sgn(m) * g x)) \<longlongrightarrow> (sgn(l) * l) * (sgn(m) * m)) F" |
719 using tendsto_mult_ereal_pos by force |
719 using tendsto_mult_ereal_pos by force |
720 have "((\<lambda>x. (sgn(l) * sgn(m)) * ((sgn(l) * f x) * (sgn(m) * g x))) \<longlongrightarrow> (sgn(l) * sgn(m)) * ((sgn(l) * l) * (sgn(m) * m))) F" |
720 have "((\<lambda>x. (sgn(l) * sgn(m)) * ((sgn(l) * f x) * (sgn(m) * g x))) \<longlongrightarrow> (sgn(l) * sgn(m)) * ((sgn(l) * l) * (sgn(m) * m))) F" |
721 by (rule tendsto_cmult_ereal, auto simp add: sgn_finite2 *) |
721 by (rule tendsto_cmult_ereal, auto simp add: sgn_finite2 *) |
722 moreover have "\<And>x. (sgn(l) * sgn(m)) * ((sgn(l) * f x) * (sgn(m) * g x)) = f x * g x" |
722 moreover have "\<And>x. (sgn(l) * sgn(m)) * ((sgn(l) * f x) * (sgn(m) * g x)) = f x * g x" |
723 by (metis mult.left_neutral sgn_squared_ereal[OF `l \<noteq> 0`] sgn_squared_ereal[OF `m \<noteq> 0`] mult.assoc mult.commute) |
723 by (metis mult.left_neutral sgn_squared_ereal[OF \<open>l \<noteq> 0\<close>] sgn_squared_ereal[OF \<open>m \<noteq> 0\<close>] mult.assoc mult.commute) |
724 moreover have "(sgn(l) * sgn(m)) * ((sgn(l) * l) * (sgn(m) * m)) = l * m" |
724 moreover have "(sgn(l) * sgn(m)) * ((sgn(l) * l) * (sgn(m) * m)) = l * m" |
725 by (metis mult.left_neutral sgn_squared_ereal[OF `l \<noteq> 0`] sgn_squared_ereal[OF `m \<noteq> 0`] mult.assoc mult.commute) |
725 by (metis mult.left_neutral sgn_squared_ereal[OF \<open>l \<noteq> 0\<close>] sgn_squared_ereal[OF \<open>m \<noteq> 0\<close>] mult.assoc mult.commute) |
726 ultimately show ?thesis by auto |
726 ultimately show ?thesis by auto |
727 qed |
727 qed |
728 |
728 |
729 lemma tendsto_cmult_ereal_general [tendsto_intros]: |
729 lemma tendsto_cmult_ereal_general [tendsto_intros]: |
730 fixes f::"_ \<Rightarrow> ereal" and c::ereal |
730 fixes f::"_ \<Rightarrow> ereal" and c::ereal |
731 assumes "(f \<longlongrightarrow> l) F" "\<not> (l=0 \<and> abs(c) = \<infinity>)" |
731 assumes "(f \<longlongrightarrow> l) F" "\<not> (l=0 \<and> abs(c) = \<infinity>)" |
732 shows "((\<lambda>x. c * f x) \<longlongrightarrow> c * l) F" |
732 shows "((\<lambda>x. c * f x) \<longlongrightarrow> c * l) F" |
733 by (cases "c = 0", auto simp add: assms tendsto_mult_ereal) |
733 by (cases "c = 0", auto simp add: assms tendsto_mult_ereal) |
734 |
734 |
735 |
735 |
736 subsubsection {*Continuity of division*} |
736 subsubsection \<open>Continuity of division\<close> |
737 |
737 |
738 lemma tendsto_inverse_ereal_PInf: |
738 lemma tendsto_inverse_ereal_PInf: |
739 fixes u::"_ \<Rightarrow> ereal" |
739 fixes u::"_ \<Rightarrow> ereal" |
740 assumes "(u \<longlongrightarrow> \<infinity>) F" |
740 assumes "(u \<longlongrightarrow> \<infinity>) F" |
741 shows "((\<lambda>x. 1/ u x) \<longlongrightarrow> 0) F" |
741 shows "((\<lambda>x. 1/ u x) \<longlongrightarrow> 0) F" |
979 moreover have "(\<lambda>n. (-1)* ereal(real n)) \<longlonglongrightarrow> -\<infinity>" |
979 moreover have "(\<lambda>n. (-1)* ereal(real n)) \<longlonglongrightarrow> -\<infinity>" |
980 using tendsto_cmult_ereal[of "-1", OF _ id_nat_ereal_tendsto_PInf] by (simp add: one_ereal_def) |
980 using tendsto_cmult_ereal[of "-1", OF _ id_nat_ereal_tendsto_PInf] by (simp add: one_ereal_def) |
981 ultimately show ?thesis using MInf by auto |
981 ultimately show ?thesis using MInf by auto |
982 qed (simp add: assms) |
982 qed (simp add: assms) |
983 |
983 |
984 text {* the next one is copied from \verb+tendsto_sum+. *} |
984 text \<open>the next one is copied from \verb+tendsto_sum+.\<close> |
985 lemma tendsto_sum_ereal [tendsto_intros]: |
985 lemma tendsto_sum_ereal [tendsto_intros]: |
986 fixes f :: "'a \<Rightarrow> 'b \<Rightarrow> ereal" |
986 fixes f :: "'a \<Rightarrow> 'b \<Rightarrow> ereal" |
987 assumes "\<And>i. i \<in> S \<Longrightarrow> (f i \<longlongrightarrow> a i) F" |
987 assumes "\<And>i. i \<in> S \<Longrightarrow> (f i \<longlongrightarrow> a i) F" |
988 "\<And>i. abs(a i) \<noteq> \<infinity>" |
988 "\<And>i. abs(a i) \<noteq> \<infinity>" |
989 shows "((\<lambda>x. \<Sum>i\<in>S. f i x) \<longlongrightarrow> (\<Sum>i\<in>S. a i)) F" |
989 shows "((\<lambda>x. \<Sum>i\<in>S. f i x) \<longlongrightarrow> (\<Sum>i\<in>S. a i)) F" |
990 proof (cases "finite S") |
990 proof (cases "finite S") |
991 assume "finite S" then show ?thesis using assms |
991 assume "finite S" then show ?thesis using assms |
992 by (induct, simp, simp add: tendsto_add_ereal_general2 assms) |
992 by (induct, simp, simp add: tendsto_add_ereal_general2 assms) |
993 qed(simp) |
993 qed(simp) |
994 |
994 |
995 subsubsection {*Limsups and liminfs*} |
995 subsubsection \<open>Limsups and liminfs\<close> |
996 |
996 |
997 lemma limsup_finite_then_bounded: |
997 lemma limsup_finite_then_bounded: |
998 fixes u::"nat \<Rightarrow> real" |
998 fixes u::"nat \<Rightarrow> real" |
999 assumes "limsup u < \<infinity>" |
999 assumes "limsup u < \<infinity>" |
1000 shows "\<exists>C. \<forall>n. u n \<le> C" |
1000 shows "\<exists>C. \<forall>n. u n \<le> C" |
1089 apply (metis (no_types, lifting) s(2) t(1) LIMSEQ_subseq_LIMSEQ a_def comp_assoc) |
1089 apply (metis (no_types, lifting) s(2) t(1) LIMSEQ_subseq_LIMSEQ a_def comp_assoc) |
1090 apply (metis (no_types, lifting) t(2) a_def comp_assoc) |
1090 apply (metis (no_types, lifting) t(2) a_def comp_assoc) |
1091 done |
1091 done |
1092 |
1092 |
1093 have "limsup (u o r) \<le> limsup u" by (simp add: limsup_subseq_mono r(1)) |
1093 have "limsup (u o r) \<le> limsup u" by (simp add: limsup_subseq_mono r(1)) |
1094 then have a: "limsup (u o r) \<noteq> \<infinity>" using `limsup u < \<infinity>` by auto |
1094 then have a: "limsup (u o r) \<noteq> \<infinity>" using \<open>limsup u < \<infinity>\<close> by auto |
1095 have "limsup (v o r o s) \<le> limsup v" by (simp add: comp_assoc limsup_subseq_mono r(1) s(1) subseq_o) |
1095 have "limsup (v o r o s) \<le> limsup v" by (simp add: comp_assoc limsup_subseq_mono r(1) s(1) subseq_o) |
1096 then have b: "limsup (v o r o s) \<noteq> \<infinity>" using `limsup v < \<infinity>` by auto |
1096 then have b: "limsup (v o r o s) \<noteq> \<infinity>" using \<open>limsup v < \<infinity>\<close> by auto |
1097 |
1097 |
1098 have "(\<lambda>n. (u o a) n + (v o a) n) \<longlonglongrightarrow> limsup (u o r) + limsup (v o r o s)" |
1098 have "(\<lambda>n. (u o a) n + (v o a) n) \<longlonglongrightarrow> limsup (u o r) + limsup (v o r o s)" |
1099 using l tendsto_add_ereal_general a b by fastforce |
1099 using l tendsto_add_ereal_general a b by fastforce |
1100 moreover have "(\<lambda>n. (u o a) n + (v o a) n) = (w o a)" unfolding w_def by auto |
1100 moreover have "(\<lambda>n. (u o a) n + (v o a) n) = (w o a)" unfolding w_def by auto |
1101 ultimately have "(w o a) \<longlonglongrightarrow> limsup (u o r) + limsup (v o r o s)" by simp |
1101 ultimately have "(w o a) \<longlonglongrightarrow> limsup (u o r) + limsup (v o r o s)" by simp |
1102 then have "limsup w = limsup (u o r) + limsup (v o r o s)" using l(1) LIMSEQ_unique by blast |
1102 then have "limsup w = limsup (u o r) + limsup (v o r o s)" using l(1) LIMSEQ_unique by blast |
1103 then have "limsup w \<le> limsup u + limsup v" |
1103 then have "limsup w \<le> limsup u + limsup v" |
1104 using `limsup (u o r) \<le> limsup u` `limsup (v o r o s) \<le> limsup v` ereal_add_mono by simp |
1104 using \<open>limsup (u o r) \<le> limsup u\<close> \<open>limsup (v o r o s) \<le> limsup v\<close> ereal_add_mono by simp |
1105 then show ?thesis unfolding w_def by simp |
1105 then show ?thesis unfolding w_def by simp |
1106 qed |
1106 qed |
1107 |
1107 |
1108 text {* There is an asymmetry between liminfs and limsups in ereal, as $\infty + (-\infty) = \infty$. |
1108 text \<open>There is an asymmetry between liminfs and limsups in ereal, as $\infty + (-\infty) = \infty$. |
1109 This explains why there are more assumptions in the next lemma dealing with liminfs that in the |
1109 This explains why there are more assumptions in the next lemma dealing with liminfs that in the |
1110 previous one about limsups.*} |
1110 previous one about limsups.\<close> |
1111 |
1111 |
1112 lemma ereal_liminf_add_mono: |
1112 lemma ereal_liminf_add_mono: |
1113 fixes u v::"nat \<Rightarrow> ereal" |
1113 fixes u v::"nat \<Rightarrow> ereal" |
1114 assumes "\<not>((liminf u = \<infinity> \<and> liminf v = -\<infinity>) \<or> (liminf u = -\<infinity> \<and> liminf v = \<infinity>))" |
1114 assumes "\<not>((liminf u = \<infinity> \<and> liminf v = -\<infinity>) \<or> (liminf u = -\<infinity> \<and> liminf v = \<infinity>))" |
1115 shows "liminf (\<lambda>n. u n + v n) \<ge> liminf u + liminf v" |
1115 shows "liminf (\<lambda>n. u n + v n) \<ge> liminf u + liminf v" |
1135 apply (metis (no_types, lifting) s(2) t(1) LIMSEQ_subseq_LIMSEQ a_def comp_assoc) |
1135 apply (metis (no_types, lifting) s(2) t(1) LIMSEQ_subseq_LIMSEQ a_def comp_assoc) |
1136 apply (metis (no_types, lifting) t(2) a_def comp_assoc) |
1136 apply (metis (no_types, lifting) t(2) a_def comp_assoc) |
1137 done |
1137 done |
1138 |
1138 |
1139 have "liminf (u o r) \<ge> liminf u" by (simp add: liminf_subseq_mono r(1)) |
1139 have "liminf (u o r) \<ge> liminf u" by (simp add: liminf_subseq_mono r(1)) |
1140 then have a: "liminf (u o r) \<noteq> -\<infinity>" using `liminf u > -\<infinity>` by auto |
1140 then have a: "liminf (u o r) \<noteq> -\<infinity>" using \<open>liminf u > -\<infinity>\<close> by auto |
1141 have "liminf (v o r o s) \<ge> liminf v" by (simp add: comp_assoc liminf_subseq_mono r(1) s(1) subseq_o) |
1141 have "liminf (v o r o s) \<ge> liminf v" by (simp add: comp_assoc liminf_subseq_mono r(1) s(1) subseq_o) |
1142 then have b: "liminf (v o r o s) \<noteq> -\<infinity>" using `liminf v > -\<infinity>` by auto |
1142 then have b: "liminf (v o r o s) \<noteq> -\<infinity>" using \<open>liminf v > -\<infinity>\<close> by auto |
1143 |
1143 |
1144 have "(\<lambda>n. (u o a) n + (v o a) n) \<longlonglongrightarrow> liminf (u o r) + liminf (v o r o s)" |
1144 have "(\<lambda>n. (u o a) n + (v o a) n) \<longlonglongrightarrow> liminf (u o r) + liminf (v o r o s)" |
1145 using l tendsto_add_ereal_general a b by fastforce |
1145 using l tendsto_add_ereal_general a b by fastforce |
1146 moreover have "(\<lambda>n. (u o a) n + (v o a) n) = (w o a)" unfolding w_def by auto |
1146 moreover have "(\<lambda>n. (u o a) n + (v o a) n) = (w o a)" unfolding w_def by auto |
1147 ultimately have "(w o a) \<longlonglongrightarrow> liminf (u o r) + liminf (v o r o s)" by simp |
1147 ultimately have "(w o a) \<longlonglongrightarrow> liminf (u o r) + liminf (v o r o s)" by simp |
1148 then have "liminf w = liminf (u o r) + liminf (v o r o s)" using l(1) LIMSEQ_unique by blast |
1148 then have "liminf w = liminf (u o r) + liminf (v o r o s)" using l(1) LIMSEQ_unique by blast |
1149 then have "liminf w \<ge> liminf u + liminf v" |
1149 then have "liminf w \<ge> liminf u + liminf v" |
1150 using `liminf (u o r) \<ge> liminf u` `liminf (v o r o s) \<ge> liminf v` ereal_add_mono by simp |
1150 using \<open>liminf (u o r) \<ge> liminf u\<close> \<open>liminf (v o r o s) \<ge> liminf v\<close> ereal_add_mono by simp |
1151 then show ?thesis unfolding w_def by simp |
1151 then show ?thesis unfolding w_def by simp |
1152 qed |
1152 qed |
1153 |
1153 |
1154 lemma ereal_limsup_lim_add: |
1154 lemma ereal_limsup_lim_add: |
1155 fixes u v::"nat \<Rightarrow> ereal" |
1155 fixes u v::"nat \<Rightarrow> ereal" |
1300 apply (metis (no_types, lifting) t(2) a_def comp_assoc) |
1300 apply (metis (no_types, lifting) t(2) a_def comp_assoc) |
1301 done |
1301 done |
1302 |
1302 |
1303 have "liminf (w o r) \<ge> liminf w" by (simp add: liminf_subseq_mono r(1)) |
1303 have "liminf (w o r) \<ge> liminf w" by (simp add: liminf_subseq_mono r(1)) |
1304 have "limsup (v o r o s) \<le> limsup v" by (simp add: comp_assoc limsup_subseq_mono r(1) s(1) subseq_o) |
1304 have "limsup (v o r o s) \<le> limsup v" by (simp add: comp_assoc limsup_subseq_mono r(1) s(1) subseq_o) |
1305 then have b: "limsup (v o r o s) < \<infinity>" using `limsup v < \<infinity>` by auto |
1305 then have b: "limsup (v o r o s) < \<infinity>" using \<open>limsup v < \<infinity>\<close> by auto |
1306 |
1306 |
1307 have "(\<lambda>n. (u o a) n + (v o a) n) \<longlonglongrightarrow> liminf u + limsup (v o r o s)" |
1307 have "(\<lambda>n. (u o a) n + (v o a) n) \<longlonglongrightarrow> liminf u + limsup (v o r o s)" |
1308 apply (rule tendsto_add_ereal_general) using b `liminf u < \<infinity>` l(1) l(3) by force+ |
1308 apply (rule tendsto_add_ereal_general) using b \<open>liminf u < \<infinity>\<close> l(1) l(3) by force+ |
1309 moreover have "(\<lambda>n. (u o a) n + (v o a) n) = (w o a)" unfolding w_def by auto |
1309 moreover have "(\<lambda>n. (u o a) n + (v o a) n) = (w o a)" unfolding w_def by auto |
1310 ultimately have "(w o a) \<longlonglongrightarrow> liminf u + limsup (v o r o s)" by simp |
1310 ultimately have "(w o a) \<longlonglongrightarrow> liminf u + limsup (v o r o s)" by simp |
1311 then have "liminf (w o r) = liminf u + limsup (v o r o s)" using l(2) using LIMSEQ_unique by blast |
1311 then have "liminf (w o r) = liminf u + limsup (v o r o s)" using l(2) using LIMSEQ_unique by blast |
1312 then have "liminf w \<le> liminf u + limsup v" |
1312 then have "liminf w \<le> liminf u + limsup v" |
1313 using `liminf (w o r) \<ge> liminf w` `limsup (v o r o s) \<le> limsup v` |
1313 using \<open>liminf (w o r) \<ge> liminf w\<close> \<open>limsup (v o r o s) \<le> limsup v\<close> |
1314 by (metis add_mono_thms_linordered_semiring(2) le_less_trans not_less) |
1314 by (metis add_mono_thms_linordered_semiring(2) le_less_trans not_less) |
1315 then show ?thesis unfolding w_def by simp |
1315 then show ?thesis unfolding w_def by simp |
1316 qed |
1316 qed |
1317 |
1317 |
1318 lemma ereal_liminf_limsup_minus: |
1318 lemma ereal_liminf_limsup_minus: |
1919 moreover have "(\<Sum>n. f x * indicator (B n) x) = f x * indicator (\<Union>n. B n) x" for x |
1919 moreover have "(\<Sum>n. f x * indicator (B n) x) = f x * indicator (\<Union>n. B n) x" for x |
1920 proof (cases) |
1920 proof (cases) |
1921 assume "x \<in> (\<Union>n. B n)" |
1921 assume "x \<in> (\<Union>n. B n)" |
1922 then obtain n where "x \<in> B n" by blast |
1922 then obtain n where "x \<in> B n" by blast |
1923 have a: "finite {n}" by simp |
1923 have a: "finite {n}" by simp |
1924 have "\<And>i. i \<noteq> n \<Longrightarrow> x \<notin> B i" using `x \<in> B n` assms(3) disjoint_family_on_def |
1924 have "\<And>i. i \<noteq> n \<Longrightarrow> x \<notin> B i" using \<open>x \<in> B n\<close> assms(3) disjoint_family_on_def |
1925 by (metis IntI UNIV_I empty_iff) |
1925 by (metis IntI UNIV_I empty_iff) |
1926 then have "\<And>i. i \<notin> {n} \<Longrightarrow> indicator (B i) x = (0::ennreal)" using indicator_def by simp |
1926 then have "\<And>i. i \<notin> {n} \<Longrightarrow> indicator (B i) x = (0::ennreal)" using indicator_def by simp |
1927 then have b: "\<And>i. i \<notin> {n} \<Longrightarrow> f x * indicator (B i) x = (0::ennreal)" by simp |
1927 then have b: "\<And>i. i \<notin> {n} \<Longrightarrow> f x * indicator (B i) x = (0::ennreal)" by simp |
1928 |
1928 |
1929 define h where "h = (\<lambda>i. f x * indicator (B i) x)" |
1929 define h where "h = (\<lambda>i. f x * indicator (B i) x)" |
1930 then have "\<And>i. i \<notin> {n} \<Longrightarrow> h i = 0" using b by simp |
1930 then have "\<And>i. i \<notin> {n} \<Longrightarrow> h i = 0" using b by simp |
1931 then have "(\<Sum>i. h i) = (\<Sum>i\<in>{n}. h i)" |
1931 then have "(\<Sum>i. h i) = (\<Sum>i\<in>{n}. h i)" |
1932 by (metis sums_unique[OF sums_finite[OF a]]) |
1932 by (metis sums_unique[OF sums_finite[OF a]]) |
1933 then have "(\<Sum>i. h i) = h n" by simp |
1933 then have "(\<Sum>i. h i) = h n" by simp |
1934 then have "(\<Sum>n. f x * indicator (B n) x) = f x * indicator (B n) x" using h_def by simp |
1934 then have "(\<Sum>n. f x * indicator (B n) x) = f x * indicator (B n) x" using h_def by simp |
1935 then have "(\<Sum>n. f x * indicator (B n) x) = f x" using `x \<in> B n` indicator_def by simp |
1935 then have "(\<Sum>n. f x * indicator (B n) x) = f x" using \<open>x \<in> B n\<close> indicator_def by simp |
1936 then show ?thesis using `x \<in> (\<Union>n. B n)` by auto |
1936 then show ?thesis using \<open>x \<in> (\<Union>n. B n)\<close> by auto |
1937 next |
1937 next |
1938 assume "x \<notin> (\<Union>n. B n)" |
1938 assume "x \<notin> (\<Union>n. B n)" |
1939 then have "\<And>n. f x * indicator (B n) x = 0" by simp |
1939 then have "\<And>n. f x * indicator (B n) x = 0" by simp |
1940 have "(\<Sum>n. f x * indicator (B n) x) = 0" |
1940 have "(\<Sum>n. f x * indicator (B n) x) = 0" |
1941 by (simp add: `\<And>n. f x * indicator (B n) x = 0`) |
1941 by (simp add: \<open>\<And>n. f x * indicator (B n) x = 0\<close>) |
1942 then show ?thesis using `x \<notin> (\<Union>n. B n)` by auto |
1942 then show ?thesis using \<open>x \<notin> (\<Union>n. B n)\<close> by auto |
1943 qed |
1943 qed |
1944 ultimately show ?thesis by simp |
1944 ultimately show ?thesis by simp |
1945 qed |
1945 qed |
1946 |
1946 |
1947 lemma nn_set_integral_add: |
1947 lemma nn_set_integral_add: |
2033 and "AE x\<in>A in M. f x > 0" "(\<integral>x\<in>A. f x \<partial>M) = (0::real)" |
2033 and "AE x\<in>A in M. f x > 0" "(\<integral>x\<in>A. f x \<partial>M) = (0::real)" |
2034 shows "A \<in> null_sets M" |
2034 shows "A \<in> null_sets M" |
2035 proof - |
2035 proof - |
2036 have "AE x in M. indicator A x * f x = 0" |
2036 have "AE x in M. indicator A x * f x = 0" |
2037 apply (subst integral_nonneg_eq_0_iff_AE[symmetric]) |
2037 apply (subst integral_nonneg_eq_0_iff_AE[symmetric]) |
2038 using assms integrable_mult_indicator[OF `A \<in> sets M` assms(1)] by auto |
2038 using assms integrable_mult_indicator[OF \<open>A \<in> sets M\<close> assms(1)] by auto |
2039 then have "AE x\<in>A in M. f x = 0" by auto |
2039 then have "AE x\<in>A in M. f x = 0" by auto |
2040 then have "AE x\<in>A in M. False" using assms(3) by auto |
2040 then have "AE x\<in>A in M. False" using assms(3) by auto |
2041 then show "A \<in> null_sets M" using assms(2) by (simp add: AE_iff_null_sets) |
2041 then show "A \<in> null_sets M" using assms(2) by (simp add: AE_iff_null_sets) |
2042 qed |
2042 qed |
2043 |
2043 |
2044 text{*The next lemma is a variant of \<open>density_unique\<close>. Note that it uses the notation |
2044 text\<open>The next lemma is a variant of \<open>density_unique\<close>. Note that it uses the notation |
2045 for nonnegative set integrals introduced earlier.*} |
2045 for nonnegative set integrals introduced earlier.\<close> |
2046 |
2046 |
2047 lemma (in sigma_finite_measure) density_unique2: |
2047 lemma (in sigma_finite_measure) density_unique2: |
2048 assumes [measurable]: "f \<in> borel_measurable M" "f' \<in> borel_measurable M" |
2048 assumes [measurable]: "f \<in> borel_measurable M" "f' \<in> borel_measurable M" |
2049 assumes density_eq: "\<And>A. A \<in> sets M \<Longrightarrow> (\<integral>\<^sup>+ x \<in> A. f x \<partial>M) = (\<integral>\<^sup>+ x \<in> A. f' x \<partial>M)" |
2049 assumes density_eq: "\<And>A. A \<in> sets M \<Longrightarrow> (\<integral>\<^sup>+ x \<in> A. f x \<partial>M) = (\<integral>\<^sup>+ x \<in> A. f' x \<partial>M)" |
2050 shows "AE x in M. f x = f' x" |
2050 shows "AE x in M. f x = f' x" |
2052 show "density M f = density M f'" |
2052 show "density M f = density M f'" |
2053 by (intro measure_eqI) (auto simp: emeasure_density intro!: density_eq) |
2053 by (intro measure_eqI) (auto simp: emeasure_density intro!: density_eq) |
2054 qed (auto simp add: assms) |
2054 qed (auto simp add: assms) |
2055 |
2055 |
2056 |
2056 |
2057 text {* The next lemma implies the same statement for Banach-space valued functions |
2057 text \<open>The next lemma implies the same statement for Banach-space valued functions |
2058 using Hahn-Banach theorem and linear forms. Since they are not yet easily available, I |
2058 using Hahn-Banach theorem and linear forms. Since they are not yet easily available, I |
2059 only formulate it for real-valued functions.*} |
2059 only formulate it for real-valued functions.\<close> |
2060 |
2060 |
2061 lemma density_unique_real: |
2061 lemma density_unique_real: |
2062 fixes f f'::"_ \<Rightarrow> real" |
2062 fixes f f'::"_ \<Rightarrow> real" |
2063 assumes [measurable]: "integrable M f" "integrable M f'" |
2063 assumes [measurable]: "integrable M f" "integrable M f'" |
2064 assumes density_eq: "\<And>A. A \<in> sets M \<Longrightarrow> (\<integral>x \<in> A. f x \<partial>M) = (\<integral>x \<in> A. f' x \<partial>M)" |
2064 assumes density_eq: "\<And>A. A \<in> sets M \<Longrightarrow> (\<integral>x \<in> A. f x \<partial>M) = (\<integral>x \<in> A. f' x \<partial>M)" |
2065 shows "AE x in M. f x = f' x" |
2065 shows "AE x in M. f x = f' x" |
2066 proof - |
2066 proof - |
2067 define A where "A = {x \<in> space M. f x < f' x}" |
2067 define A where "A = {x \<in> space M. f x < f' x}" |
2068 then have [measurable]: "A \<in> sets M" by simp |
2068 then have [measurable]: "A \<in> sets M" by simp |
2069 have "(\<integral>x \<in> A. (f' x - f x) \<partial>M) = (\<integral>x \<in> A. f' x \<partial>M) - (\<integral>x \<in> A. f x \<partial>M)" |
2069 have "(\<integral>x \<in> A. (f' x - f x) \<partial>M) = (\<integral>x \<in> A. f' x \<partial>M) - (\<integral>x \<in> A. f x \<partial>M)" |
2070 using `A \<in> sets M` assms(1) assms(2) integrable_mult_indicator by blast |
2070 using \<open>A \<in> sets M\<close> assms(1) assms(2) integrable_mult_indicator by blast |
2071 then have "(\<integral>x \<in> A. (f' x - f x) \<partial>M) = 0" using assms(3) by simp |
2071 then have "(\<integral>x \<in> A. (f' x - f x) \<partial>M) = 0" using assms(3) by simp |
2072 then have "A \<in> null_sets M" |
2072 then have "A \<in> null_sets M" |
2073 using A_def null_if_pos_func_has_zero_int[where ?f = "\<lambda>x. f' x - f x" and ?A = A] assms by auto |
2073 using A_def null_if_pos_func_has_zero_int[where ?f = "\<lambda>x. f' x - f x" and ?A = A] assms by auto |
2074 then have "AE x in M. x \<notin> A" by (simp add: AE_not_in) |
2074 then have "AE x in M. x \<notin> A" by (simp add: AE_not_in) |
2075 then have *: "AE x in M. f' x \<le> f x" unfolding A_def by auto |
2075 then have *: "AE x in M. f' x \<le> f x" unfolding A_def by auto |
2076 |
2076 |
2077 |
2077 |
2078 define B where "B = {x \<in> space M. f' x < f x}" |
2078 define B where "B = {x \<in> space M. f' x < f x}" |
2079 then have [measurable]: "B \<in> sets M" by simp |
2079 then have [measurable]: "B \<in> sets M" by simp |
2080 have "(\<integral>x \<in> B. (f x - f' x) \<partial>M) = (\<integral>x \<in> B. f x \<partial>M) - (\<integral>x \<in> B. f' x \<partial>M)" |
2080 have "(\<integral>x \<in> B. (f x - f' x) \<partial>M) = (\<integral>x \<in> B. f x \<partial>M) - (\<integral>x \<in> B. f' x \<partial>M)" |
2081 using `B \<in> sets M` assms(1) assms(2) integrable_mult_indicator by blast |
2081 using \<open>B \<in> sets M\<close> assms(1) assms(2) integrable_mult_indicator by blast |
2082 then have "(\<integral>x \<in> B. (f x - f' x) \<partial>M) = 0" using assms(3) by simp |
2082 then have "(\<integral>x \<in> B. (f x - f' x) \<partial>M) = 0" using assms(3) by simp |
2083 then have "B \<in> null_sets M" |
2083 then have "B \<in> null_sets M" |
2084 using B_def null_if_pos_func_has_zero_int[where ?f = "\<lambda>x. f x - f' x" and ?A = B] assms by auto |
2084 using B_def null_if_pos_func_has_zero_int[where ?f = "\<lambda>x. f x - f' x" and ?A = B] assms by auto |
2085 then have "AE x in M. x \<notin> B" by (simp add: AE_not_in) |
2085 then have "AE x in M. x \<notin> B" by (simp add: AE_not_in) |
2086 then have "AE x in M. f' x \<ge> f x" unfolding B_def by auto |
2086 then have "AE x in M. f' x \<ge> f x" unfolding B_def by auto |
2087 |
2087 |
2088 then show ?thesis using * by auto |
2088 then show ?thesis using * by auto |
2089 qed |
2089 qed |
2090 |
2090 |
2091 text {* The next lemma shows that $L^1$ convergence of a sequence of functions follows from almost |
2091 text \<open>The next lemma shows that $L^1$ convergence of a sequence of functions follows from almost |
2092 everywhere convergence and the weaker condition of the convergence of the integrated norms (or even |
2092 everywhere convergence and the weaker condition of the convergence of the integrated norms (or even |
2093 just the nontrivial inequality about them). Useful in a lot of contexts! This statement (or its |
2093 just the nontrivial inequality about them). Useful in a lot of contexts! This statement (or its |
2094 variations) are known as Scheffe lemma. |
2094 variations) are known as Scheffe lemma. |
2095 |
2095 |
2096 The formalization is more painful as one should jump back and forth between reals and ereals and justify |
2096 The formalization is more painful as one should jump back and forth between reals and ereals and justify |
2097 all the time positivity or integrability (thankfully, measurability is handled more or less automatically).*} |
2097 all the time positivity or integrability (thankfully, measurability is handled more or less automatically).\<close> |
2098 |
2098 |
2099 lemma Scheffe_lemma1: |
2099 lemma Scheffe_lemma1: |
2100 assumes "\<And>n. integrable M (F n)" "integrable M f" |
2100 assumes "\<And>n. integrable M (F n)" "integrable M f" |
2101 "AE x in M. (\<lambda>n. F n x) \<longlonglongrightarrow> f x" |
2101 "AE x in M. (\<lambda>n. F n x) \<longlonglongrightarrow> f x" |
2102 "limsup (\<lambda>n. \<integral>\<^sup>+ x. norm(F n x) \<partial>M) \<le> (\<integral>\<^sup>+ x. norm(f x) \<partial>M)" |
2102 "limsup (\<lambda>n. \<integral>\<^sup>+ x. norm(F n x) \<partial>M) \<le> (\<integral>\<^sup>+ x. norm(f x) \<partial>M)" |