equal
deleted
inserted
replaced
1 (* Title: HOL/Library/Liminf_Limsup.thy |
1 (* Title: HOL/Library/Liminf_Limsup.thy |
2 Author: Johannes Hölzl, TU München |
2 Author: Johannes Hölzl, TU München |
3 *) |
3 *) |
4 |
4 |
5 section {* Liminf and Limsup on complete lattices *} |
5 section \<open>Liminf and Limsup on complete lattices\<close> |
6 |
6 |
7 theory Liminf_Limsup |
7 theory Liminf_Limsup |
8 imports Complex_Main |
8 imports Complex_Main |
9 begin |
9 begin |
10 |
10 |
28 lemma INF_pair: |
28 lemma INF_pair: |
29 fixes f :: "_ \<Rightarrow> _ \<Rightarrow> _ :: complete_lattice" |
29 fixes f :: "_ \<Rightarrow> _ \<Rightarrow> _ :: complete_lattice" |
30 shows "(INF i : A. INF j : B. f i j) = (INF p : A \<times> B. f (fst p) (snd p))" |
30 shows "(INF i : A. INF j : B. f i j) = (INF p : A \<times> B. f (fst p) (snd p))" |
31 by (rule antisym) (auto intro!: INF_greatest INF_lower2) |
31 by (rule antisym) (auto intro!: INF_greatest INF_lower2) |
32 |
32 |
33 subsubsection {* @{text Liminf} and @{text Limsup} *} |
33 subsubsection \<open>@{text Liminf} and @{text Limsup}\<close> |
34 |
34 |
35 definition Liminf :: "'a filter \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> 'b :: complete_lattice" where |
35 definition Liminf :: "'a filter \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> 'b :: complete_lattice" where |
36 "Liminf F f = (SUP P:{P. eventually P F}. INF x:{x. P x}. f x)" |
36 "Liminf F f = (SUP P:{P. eventually P F}. INF x:{x. P x}. f x)" |
37 |
37 |
38 definition Limsup :: "'a filter \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> 'b :: complete_lattice" where |
38 definition Limsup :: "'a filter \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> 'b :: complete_lattice" where |
169 using y by (intro exI[of _ "\<lambda>x. z < X x"]) auto |
169 using y by (intro exI[of _ "\<lambda>x. z < X x"]) auto |
170 next |
170 next |
171 case False |
171 case False |
172 then have "C \<le> INFIMUM {x. y < X x} X" |
172 then have "C \<le> INFIMUM {x. y < X x} X" |
173 by (intro INF_greatest) auto |
173 by (intro INF_greatest) auto |
174 with `y < C` show ?thesis |
174 with \<open>y < C\<close> show ?thesis |
175 using y by (intro exI[of _ "\<lambda>x. y < X x"]) auto |
175 using y by (intro exI[of _ "\<lambda>x. y < X x"]) auto |
176 qed } |
176 qed } |
177 ultimately show ?thesis |
177 ultimately show ?thesis |
178 unfolding Liminf_def le_SUP_iff by auto |
178 unfolding Liminf_def le_SUP_iff by auto |
179 qed |
179 qed |
288 shows "liminf X \<le> liminf (X \<circ> r) " |
288 shows "liminf X \<le> liminf (X \<circ> r) " |
289 proof- |
289 proof- |
290 have "\<And>n. (INF m:{n..}. X m) \<le> (INF m:{n..}. (X \<circ> r) m)" |
290 have "\<And>n. (INF m:{n..}. X m) \<le> (INF m:{n..}. (X \<circ> r) m)" |
291 proof (safe intro!: INF_mono) |
291 proof (safe intro!: INF_mono) |
292 fix n m :: nat assume "n \<le> m" then show "\<exists>ma\<in>{n..}. X ma \<le> (X \<circ> r) m" |
292 fix n m :: nat assume "n \<le> m" then show "\<exists>ma\<in>{n..}. X ma \<le> (X \<circ> r) m" |
293 using seq_suble[OF `subseq r`, of m] by (intro bexI[of _ "r m"]) auto |
293 using seq_suble[OF \<open>subseq r\<close>, of m] by (intro bexI[of _ "r m"]) auto |
294 qed |
294 qed |
295 then show ?thesis by (auto intro!: SUP_mono simp: liminf_SUP_INF comp_def) |
295 then show ?thesis by (auto intro!: SUP_mono simp: liminf_SUP_INF comp_def) |
296 qed |
296 qed |
297 |
297 |
298 lemma limsup_subseq_mono: |
298 lemma limsup_subseq_mono: |
301 shows "limsup (X \<circ> r) \<le> limsup X" |
301 shows "limsup (X \<circ> r) \<le> limsup X" |
302 proof- |
302 proof- |
303 have "\<And>n. (SUP m:{n..}. (X \<circ> r) m) \<le> (SUP m:{n..}. X m)" |
303 have "\<And>n. (SUP m:{n..}. (X \<circ> r) m) \<le> (SUP m:{n..}. X m)" |
304 proof (safe intro!: SUP_mono) |
304 proof (safe intro!: SUP_mono) |
305 fix n m :: nat assume "n \<le> m" then show "\<exists>ma\<in>{n..}. (X \<circ> r) m \<le> X ma" |
305 fix n m :: nat assume "n \<le> m" then show "\<exists>ma\<in>{n..}. (X \<circ> r) m \<le> X ma" |
306 using seq_suble[OF `subseq r`, of m] by (intro bexI[of _ "r m"]) auto |
306 using seq_suble[OF \<open>subseq r\<close>, of m] by (intro bexI[of _ "r m"]) auto |
307 qed |
307 qed |
308 then show ?thesis by (auto intro!: INF_mono simp: limsup_INF_SUP comp_def) |
308 then show ?thesis by (auto intro!: INF_mono simp: limsup_INF_SUP comp_def) |
309 qed |
309 qed |
310 |
310 |
311 end |
311 end |