src/HOL/Library/Liminf_Limsup.thy
changeset 60500 903bb1495239
parent 58881 b9556a055632
child 61245 b77bf45efe21
equal deleted inserted replaced
60499:54a3db2ed201 60500:903bb1495239
     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