src/HOL/Library/Liminf_Limsup.thy
author haftmann
Tue Mar 18 22:11:46 2014 +0100 (2014-03-18)
changeset 56212 3253aaf73a01
parent 54261 89991ef58448
child 56218 1c3f1f2431f9
permissions -rw-r--r--
consolidated theorem names containing INFI and SUPR: have INF and SUP instead uniformly
hoelzl@51340
     1
(*  Title:      HOL/Library/Liminf_Limsup.thy
hoelzl@51340
     2
    Author:     Johannes Hölzl, TU München
hoelzl@51340
     3
*)
hoelzl@51340
     4
hoelzl@51340
     5
header {* Liminf and Limsup on complete lattices *}
hoelzl@51340
     6
hoelzl@51340
     7
theory Liminf_Limsup
wenzelm@51542
     8
imports Complex_Main
hoelzl@51340
     9
begin
hoelzl@51340
    10
hoelzl@51340
    11
lemma le_Sup_iff_less:
hoelzl@53216
    12
  fixes x :: "'a :: {complete_linorder, dense_linorder}"
hoelzl@51340
    13
  shows "x \<le> (SUP i:A. f i) \<longleftrightarrow> (\<forall>y<x. \<exists>i\<in>A. y \<le> f i)" (is "?lhs = ?rhs")
hoelzl@51340
    14
  unfolding le_SUP_iff
hoelzl@51340
    15
  by (blast intro: less_imp_le less_trans less_le_trans dest: dense)
hoelzl@51340
    16
hoelzl@51340
    17
lemma Inf_le_iff_less:
hoelzl@53216
    18
  fixes x :: "'a :: {complete_linorder, dense_linorder}"
hoelzl@51340
    19
  shows "(INF i:A. f i) \<le> x \<longleftrightarrow> (\<forall>y>x. \<exists>i\<in>A. f i \<le> y)"
hoelzl@51340
    20
  unfolding INF_le_iff
hoelzl@51340
    21
  by (blast intro: less_imp_le less_trans le_less_trans dest: dense)
hoelzl@51340
    22
haftmann@56212
    23
lemma SUP_pair:
hoelzl@54257
    24
  fixes f :: "_ \<Rightarrow> _ \<Rightarrow> _ :: complete_lattice"
hoelzl@54257
    25
  shows "(SUP i : A. SUP j : B. f i j) = (SUP p : A \<times> B. f (fst p) (snd p))"
hoelzl@51340
    26
  by (rule antisym) (auto intro!: SUP_least SUP_upper2)
hoelzl@51340
    27
haftmann@56212
    28
lemma INF_pair:
hoelzl@54257
    29
  fixes f :: "_ \<Rightarrow> _ \<Rightarrow> _ :: complete_lattice"
hoelzl@54257
    30
  shows "(INF i : A. INF j : B. f i j) = (INF p : A \<times> B. f (fst p) (snd p))"
hoelzl@51340
    31
  by (rule antisym) (auto intro!: INF_greatest INF_lower2)
hoelzl@51340
    32
hoelzl@51340
    33
subsubsection {* @{text Liminf} and @{text Limsup} *}
hoelzl@51340
    34
hoelzl@54261
    35
definition Liminf :: "'a filter \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> 'b :: complete_lattice" where
hoelzl@51340
    36
  "Liminf F f = (SUP P:{P. eventually P F}. INF x:{x. P x}. f x)"
hoelzl@51340
    37
hoelzl@54261
    38
definition Limsup :: "'a filter \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> 'b :: complete_lattice" where
hoelzl@51340
    39
  "Limsup F f = (INF P:{P. eventually P F}. SUP x:{x. P x}. f x)"
hoelzl@51340
    40
hoelzl@51340
    41
abbreviation "liminf \<equiv> Liminf sequentially"
hoelzl@51340
    42
hoelzl@51340
    43
abbreviation "limsup \<equiv> Limsup sequentially"
hoelzl@51340
    44
hoelzl@51340
    45
lemma Liminf_eqI:
hoelzl@54261
    46
  "(\<And>P. eventually P F \<Longrightarrow> INFI (Collect P) f \<le> x) \<Longrightarrow>  
hoelzl@51340
    47
    (\<And>y. (\<And>P. eventually P F \<Longrightarrow> INFI (Collect P) f \<le> y) \<Longrightarrow> x \<le> y) \<Longrightarrow> Liminf F f = x"
hoelzl@51340
    48
  unfolding Liminf_def by (auto intro!: SUP_eqI)
hoelzl@51340
    49
hoelzl@51340
    50
lemma Limsup_eqI:
hoelzl@54261
    51
  "(\<And>P. eventually P F \<Longrightarrow> x \<le> SUPR (Collect P) f) \<Longrightarrow>  
hoelzl@51340
    52
    (\<And>y. (\<And>P. eventually P F \<Longrightarrow> y \<le> SUPR (Collect P) f) \<Longrightarrow> y \<le> x) \<Longrightarrow> Limsup F f = x"
hoelzl@51340
    53
  unfolding Limsup_def by (auto intro!: INF_eqI)
hoelzl@51340
    54
haftmann@56212
    55
lemma liminf_SUP_INF: "liminf f = (SUP n. INF m:{n..}. f m)"
hoelzl@51340
    56
  unfolding Liminf_def eventually_sequentially
haftmann@56212
    57
  by (rule SUP_eq) (auto simp: atLeast_def intro!: INF_mono)
hoelzl@51340
    58
haftmann@56212
    59
lemma limsup_INF_SUP: "limsup f = (INF n. SUP m:{n..}. f m)"
hoelzl@51340
    60
  unfolding Limsup_def eventually_sequentially
haftmann@56212
    61
  by (rule INF_eq) (auto simp: atLeast_def intro!: SUP_mono)
hoelzl@51340
    62
hoelzl@51340
    63
lemma Limsup_const: 
hoelzl@51340
    64
  assumes ntriv: "\<not> trivial_limit F"
hoelzl@54261
    65
  shows "Limsup F (\<lambda>x. c) = c"
hoelzl@51340
    66
proof -
hoelzl@51340
    67
  have *: "\<And>P. Ex P \<longleftrightarrow> P \<noteq> (\<lambda>x. False)" by auto
hoelzl@51340
    68
  have "\<And>P. eventually P F \<Longrightarrow> (SUP x : {x. P x}. c) = c"
hoelzl@51340
    69
    using ntriv by (intro SUP_const) (auto simp: eventually_False *)
hoelzl@51340
    70
  then show ?thesis
hoelzl@51340
    71
    unfolding Limsup_def using eventually_True
hoelzl@51340
    72
    by (subst INF_cong[where D="\<lambda>x. c"])
hoelzl@51340
    73
       (auto intro!: INF_const simp del: eventually_True)
hoelzl@51340
    74
qed
hoelzl@51340
    75
hoelzl@51340
    76
lemma Liminf_const:
hoelzl@51340
    77
  assumes ntriv: "\<not> trivial_limit F"
hoelzl@54261
    78
  shows "Liminf F (\<lambda>x. c) = c"
hoelzl@51340
    79
proof -
hoelzl@51340
    80
  have *: "\<And>P. Ex P \<longleftrightarrow> P \<noteq> (\<lambda>x. False)" by auto
hoelzl@51340
    81
  have "\<And>P. eventually P F \<Longrightarrow> (INF x : {x. P x}. c) = c"
hoelzl@51340
    82
    using ntriv by (intro INF_const) (auto simp: eventually_False *)
hoelzl@51340
    83
  then show ?thesis
hoelzl@51340
    84
    unfolding Liminf_def using eventually_True
hoelzl@51340
    85
    by (subst SUP_cong[where D="\<lambda>x. c"])
hoelzl@51340
    86
       (auto intro!: SUP_const simp del: eventually_True)
hoelzl@51340
    87
qed
hoelzl@51340
    88
hoelzl@51340
    89
lemma Liminf_mono:
hoelzl@51340
    90
  assumes ev: "eventually (\<lambda>x. f x \<le> g x) F"
hoelzl@51340
    91
  shows "Liminf F f \<le> Liminf F g"
hoelzl@51340
    92
  unfolding Liminf_def
hoelzl@51340
    93
proof (safe intro!: SUP_mono)
hoelzl@51340
    94
  fix P assume "eventually P F"
hoelzl@51340
    95
  with ev have "eventually (\<lambda>x. f x \<le> g x \<and> P x) F" (is "eventually ?Q F") by (rule eventually_conj)
hoelzl@51340
    96
  then show "\<exists>Q\<in>{P. eventually P F}. INFI (Collect P) f \<le> INFI (Collect Q) g"
hoelzl@51340
    97
    by (intro bexI[of _ ?Q]) (auto intro!: INF_mono)
hoelzl@51340
    98
qed
hoelzl@51340
    99
hoelzl@51340
   100
lemma Liminf_eq:
hoelzl@51340
   101
  assumes "eventually (\<lambda>x. f x = g x) F"
hoelzl@51340
   102
  shows "Liminf F f = Liminf F g"
hoelzl@51340
   103
  by (intro antisym Liminf_mono eventually_mono[OF _ assms]) auto
hoelzl@51340
   104
hoelzl@51340
   105
lemma Limsup_mono:
hoelzl@51340
   106
  assumes ev: "eventually (\<lambda>x. f x \<le> g x) F"
hoelzl@51340
   107
  shows "Limsup F f \<le> Limsup F g"
hoelzl@51340
   108
  unfolding Limsup_def
hoelzl@51340
   109
proof (safe intro!: INF_mono)
hoelzl@51340
   110
  fix P assume "eventually P F"
hoelzl@51340
   111
  with ev have "eventually (\<lambda>x. f x \<le> g x \<and> P x) F" (is "eventually ?Q F") by (rule eventually_conj)
hoelzl@51340
   112
  then show "\<exists>Q\<in>{P. eventually P F}. SUPR (Collect Q) f \<le> SUPR (Collect P) g"
hoelzl@51340
   113
    by (intro bexI[of _ ?Q]) (auto intro!: SUP_mono)
hoelzl@51340
   114
qed
hoelzl@51340
   115
hoelzl@51340
   116
lemma Limsup_eq:
hoelzl@51340
   117
  assumes "eventually (\<lambda>x. f x = g x) net"
hoelzl@51340
   118
  shows "Limsup net f = Limsup net g"
hoelzl@51340
   119
  by (intro antisym Limsup_mono eventually_mono[OF _ assms]) auto
hoelzl@51340
   120
hoelzl@51340
   121
lemma Liminf_le_Limsup:
hoelzl@51340
   122
  assumes ntriv: "\<not> trivial_limit F"
hoelzl@51340
   123
  shows "Liminf F f \<le> Limsup F f"
hoelzl@51340
   124
  unfolding Limsup_def Liminf_def
hoelzl@54261
   125
  apply (rule SUP_least)
hoelzl@54261
   126
  apply (rule INF_greatest)
hoelzl@51340
   127
proof safe
hoelzl@51340
   128
  fix P Q assume "eventually P F" "eventually Q F"
hoelzl@51340
   129
  then have "eventually (\<lambda>x. P x \<and> Q x) F" (is "eventually ?C F") by (rule eventually_conj)
hoelzl@51340
   130
  then have not_False: "(\<lambda>x. P x \<and> Q x) \<noteq> (\<lambda>x. False)"
hoelzl@51340
   131
    using ntriv by (auto simp add: eventually_False)
hoelzl@51340
   132
  have "INFI (Collect P) f \<le> INFI (Collect ?C) f"
hoelzl@51340
   133
    by (rule INF_mono) auto
hoelzl@51340
   134
  also have "\<dots> \<le> SUPR (Collect ?C) f"
hoelzl@51340
   135
    using not_False by (intro INF_le_SUP) auto
hoelzl@51340
   136
  also have "\<dots> \<le> SUPR (Collect Q) f"
hoelzl@51340
   137
    by (rule SUP_mono) auto
hoelzl@51340
   138
  finally show "INFI (Collect P) f \<le> SUPR (Collect Q) f" .
hoelzl@51340
   139
qed
hoelzl@51340
   140
hoelzl@51340
   141
lemma Liminf_bounded:
hoelzl@51340
   142
  assumes ntriv: "\<not> trivial_limit F"
hoelzl@51340
   143
  assumes le: "eventually (\<lambda>n. C \<le> X n) F"
hoelzl@51340
   144
  shows "C \<le> Liminf F X"
hoelzl@51340
   145
  using Liminf_mono[OF le] Liminf_const[OF ntriv, of C] by simp
hoelzl@51340
   146
hoelzl@51340
   147
lemma Limsup_bounded:
hoelzl@51340
   148
  assumes ntriv: "\<not> trivial_limit F"
hoelzl@51340
   149
  assumes le: "eventually (\<lambda>n. X n \<le> C) F"
hoelzl@51340
   150
  shows "Limsup F X \<le> C"
hoelzl@51340
   151
  using Limsup_mono[OF le] Limsup_const[OF ntriv, of C] by simp
hoelzl@51340
   152
hoelzl@51340
   153
lemma le_Liminf_iff:
hoelzl@51340
   154
  fixes X :: "_ \<Rightarrow> _ :: complete_linorder"
hoelzl@51340
   155
  shows "C \<le> Liminf F X \<longleftrightarrow> (\<forall>y<C. eventually (\<lambda>x. y < X x) F)"
hoelzl@51340
   156
proof -
hoelzl@51340
   157
  { fix y P assume "eventually P F" "y < INFI (Collect P) X"
hoelzl@51340
   158
    then have "eventually (\<lambda>x. y < X x) F"
hoelzl@51340
   159
      by (auto elim!: eventually_elim1 dest: less_INF_D) }
hoelzl@51340
   160
  moreover
hoelzl@51340
   161
  { fix y P assume "y < C" and y: "\<forall>y<C. eventually (\<lambda>x. y < X x) F"
hoelzl@51340
   162
    have "\<exists>P. eventually P F \<and> y < INFI (Collect P) X"
wenzelm@53381
   163
    proof (cases "\<exists>z. y < z \<and> z < C")
wenzelm@53381
   164
      case True
wenzelm@53381
   165
      then obtain z where z: "y < z \<and> z < C" ..
wenzelm@53374
   166
      moreover from z have "z \<le> INFI {x. z < X x} X"
hoelzl@51340
   167
        by (auto intro!: INF_greatest)
hoelzl@51340
   168
      ultimately show ?thesis
hoelzl@51340
   169
        using y by (intro exI[of _ "\<lambda>x. z < X x"]) auto
hoelzl@51340
   170
    next
wenzelm@53381
   171
      case False
hoelzl@51340
   172
      then have "C \<le> INFI {x. y < X x} X"
hoelzl@51340
   173
        by (intro INF_greatest) auto
hoelzl@51340
   174
      with `y < C` show ?thesis
hoelzl@51340
   175
        using y by (intro exI[of _ "\<lambda>x. y < X x"]) auto
hoelzl@51340
   176
    qed }
hoelzl@51340
   177
  ultimately show ?thesis
hoelzl@51340
   178
    unfolding Liminf_def le_SUP_iff by auto
hoelzl@51340
   179
qed
hoelzl@51340
   180
hoelzl@51340
   181
lemma lim_imp_Liminf:
hoelzl@51340
   182
  fixes f :: "'a \<Rightarrow> _ :: {complete_linorder, linorder_topology}"
hoelzl@51340
   183
  assumes ntriv: "\<not> trivial_limit F"
hoelzl@51340
   184
  assumes lim: "(f ---> f0) F"
hoelzl@51340
   185
  shows "Liminf F f = f0"
hoelzl@51340
   186
proof (intro Liminf_eqI)
hoelzl@51340
   187
  fix P assume P: "eventually P F"
hoelzl@51340
   188
  then have "eventually (\<lambda>x. INFI (Collect P) f \<le> f x) F"
hoelzl@51340
   189
    by eventually_elim (auto intro!: INF_lower)
hoelzl@51340
   190
  then show "INFI (Collect P) f \<le> f0"
hoelzl@51340
   191
    by (rule tendsto_le[OF ntriv lim tendsto_const])
hoelzl@51340
   192
next
hoelzl@51340
   193
  fix y assume upper: "\<And>P. eventually P F \<Longrightarrow> INFI (Collect P) f \<le> y"
hoelzl@51340
   194
  show "f0 \<le> y"
hoelzl@51340
   195
  proof cases
hoelzl@51340
   196
    assume "\<exists>z. y < z \<and> z < f0"
wenzelm@53374
   197
    then obtain z where "y < z \<and> z < f0" ..
hoelzl@51340
   198
    moreover have "z \<le> INFI {x. z < f x} f"
hoelzl@51340
   199
      by (rule INF_greatest) simp
hoelzl@51340
   200
    ultimately show ?thesis
hoelzl@51340
   201
      using lim[THEN topological_tendstoD, THEN upper, of "{z <..}"] by auto
hoelzl@51340
   202
  next
hoelzl@51340
   203
    assume discrete: "\<not> (\<exists>z. y < z \<and> z < f0)"
hoelzl@51340
   204
    show ?thesis
hoelzl@51340
   205
    proof (rule classical)
hoelzl@51340
   206
      assume "\<not> f0 \<le> y"
hoelzl@51340
   207
      then have "eventually (\<lambda>x. y < f x) F"
hoelzl@51340
   208
        using lim[THEN topological_tendstoD, of "{y <..}"] by auto
hoelzl@51340
   209
      then have "eventually (\<lambda>x. f0 \<le> f x) F"
hoelzl@51340
   210
        using discrete by (auto elim!: eventually_elim1)
hoelzl@51340
   211
      then have "INFI {x. f0 \<le> f x} f \<le> y"
hoelzl@51340
   212
        by (rule upper)
hoelzl@51340
   213
      moreover have "f0 \<le> INFI {x. f0 \<le> f x} f"
hoelzl@51340
   214
        by (intro INF_greatest) simp
hoelzl@51340
   215
      ultimately show "f0 \<le> y" by simp
hoelzl@51340
   216
    qed
hoelzl@51340
   217
  qed
hoelzl@51340
   218
qed
hoelzl@51340
   219
hoelzl@51340
   220
lemma lim_imp_Limsup:
hoelzl@51340
   221
  fixes f :: "'a \<Rightarrow> _ :: {complete_linorder, linorder_topology}"
hoelzl@51340
   222
  assumes ntriv: "\<not> trivial_limit F"
hoelzl@51340
   223
  assumes lim: "(f ---> f0) F"
hoelzl@51340
   224
  shows "Limsup F f = f0"
hoelzl@51340
   225
proof (intro Limsup_eqI)
hoelzl@51340
   226
  fix P assume P: "eventually P F"
hoelzl@51340
   227
  then have "eventually (\<lambda>x. f x \<le> SUPR (Collect P) f) F"
hoelzl@51340
   228
    by eventually_elim (auto intro!: SUP_upper)
hoelzl@51340
   229
  then show "f0 \<le> SUPR (Collect P) f"
hoelzl@51340
   230
    by (rule tendsto_le[OF ntriv tendsto_const lim])
hoelzl@51340
   231
next
hoelzl@51340
   232
  fix y assume lower: "\<And>P. eventually P F \<Longrightarrow> y \<le> SUPR (Collect P) f"
hoelzl@51340
   233
  show "y \<le> f0"
wenzelm@53381
   234
  proof (cases "\<exists>z. f0 < z \<and> z < y")
wenzelm@53381
   235
    case True
wenzelm@53381
   236
    then obtain z where "f0 < z \<and> z < y" ..
hoelzl@51340
   237
    moreover have "SUPR {x. f x < z} f \<le> z"
hoelzl@51340
   238
      by (rule SUP_least) simp
hoelzl@51340
   239
    ultimately show ?thesis
hoelzl@51340
   240
      using lim[THEN topological_tendstoD, THEN lower, of "{..< z}"] by auto
hoelzl@51340
   241
  next
wenzelm@53381
   242
    case False
hoelzl@51340
   243
    show ?thesis
hoelzl@51340
   244
    proof (rule classical)
hoelzl@51340
   245
      assume "\<not> y \<le> f0"
hoelzl@51340
   246
      then have "eventually (\<lambda>x. f x < y) F"
hoelzl@51340
   247
        using lim[THEN topological_tendstoD, of "{..< y}"] by auto
hoelzl@51340
   248
      then have "eventually (\<lambda>x. f x \<le> f0) F"
wenzelm@53381
   249
        using False by (auto elim!: eventually_elim1 simp: not_less)
hoelzl@51340
   250
      then have "y \<le> SUPR {x. f x \<le> f0} f"
hoelzl@51340
   251
        by (rule lower)
hoelzl@51340
   252
      moreover have "SUPR {x. f x \<le> f0} f \<le> f0"
hoelzl@51340
   253
        by (intro SUP_least) simp
hoelzl@51340
   254
      ultimately show "y \<le> f0" by simp
hoelzl@51340
   255
    qed
hoelzl@51340
   256
  qed
hoelzl@51340
   257
qed
hoelzl@51340
   258
hoelzl@51340
   259
lemma Liminf_eq_Limsup:
hoelzl@51340
   260
  fixes f0 :: "'a :: {complete_linorder, linorder_topology}"
hoelzl@51340
   261
  assumes ntriv: "\<not> trivial_limit F"
hoelzl@51340
   262
    and lim: "Liminf F f = f0" "Limsup F f = f0"
hoelzl@51340
   263
  shows "(f ---> f0) F"
hoelzl@51340
   264
proof (rule order_tendstoI)
hoelzl@51340
   265
  fix a assume "f0 < a"
hoelzl@51340
   266
  with assms have "Limsup F f < a" by simp
hoelzl@51340
   267
  then obtain P where "eventually P F" "SUPR (Collect P) f < a"
hoelzl@51340
   268
    unfolding Limsup_def INF_less_iff by auto
hoelzl@51340
   269
  then show "eventually (\<lambda>x. f x < a) F"
hoelzl@51340
   270
    by (auto elim!: eventually_elim1 dest: SUP_lessD)
hoelzl@51340
   271
next
hoelzl@51340
   272
  fix a assume "a < f0"
hoelzl@51340
   273
  with assms have "a < Liminf F f" by simp
hoelzl@51340
   274
  then obtain P where "eventually P F" "a < INFI (Collect P) f"
hoelzl@51340
   275
    unfolding Liminf_def less_SUP_iff by auto
hoelzl@51340
   276
  then show "eventually (\<lambda>x. a < f x) F"
hoelzl@51340
   277
    by (auto elim!: eventually_elim1 dest: less_INF_D)
hoelzl@51340
   278
qed
hoelzl@51340
   279
hoelzl@51340
   280
lemma tendsto_iff_Liminf_eq_Limsup:
hoelzl@51340
   281
  fixes f0 :: "'a :: {complete_linorder, linorder_topology}"
hoelzl@51340
   282
  shows "\<not> trivial_limit F \<Longrightarrow> (f ---> f0) F \<longleftrightarrow> (Liminf F f = f0 \<and> Limsup F f = f0)"
hoelzl@51340
   283
  by (metis Liminf_eq_Limsup lim_imp_Limsup lim_imp_Liminf)
hoelzl@51340
   284
hoelzl@51340
   285
lemma liminf_subseq_mono:
hoelzl@51340
   286
  fixes X :: "nat \<Rightarrow> 'a :: complete_linorder"
hoelzl@51340
   287
  assumes "subseq r"
hoelzl@51340
   288
  shows "liminf X \<le> liminf (X \<circ> r) "
hoelzl@51340
   289
proof-
hoelzl@51340
   290
  have "\<And>n. (INF m:{n..}. X m) \<le> (INF m:{n..}. (X \<circ> r) m)"
hoelzl@51340
   291
  proof (safe intro!: INF_mono)
hoelzl@51340
   292
    fix n m :: nat assume "n \<le> m" then show "\<exists>ma\<in>{n..}. X ma \<le> (X \<circ> r) m"
hoelzl@51340
   293
      using seq_suble[OF `subseq r`, of m] by (intro bexI[of _ "r m"]) auto
hoelzl@51340
   294
  qed
haftmann@56212
   295
  then show ?thesis by (auto intro!: SUP_mono simp: liminf_SUP_INF comp_def)
hoelzl@51340
   296
qed
hoelzl@51340
   297
hoelzl@51340
   298
lemma limsup_subseq_mono:
hoelzl@51340
   299
  fixes X :: "nat \<Rightarrow> 'a :: complete_linorder"
hoelzl@51340
   300
  assumes "subseq r"
hoelzl@51340
   301
  shows "limsup (X \<circ> r) \<le> limsup X"
hoelzl@51340
   302
proof-
hoelzl@51340
   303
  have "\<And>n. (SUP m:{n..}. (X \<circ> r) m) \<le> (SUP m:{n..}. X m)"
hoelzl@51340
   304
  proof (safe intro!: SUP_mono)
hoelzl@51340
   305
    fix n m :: nat assume "n \<le> m" then show "\<exists>ma\<in>{n..}. (X \<circ> r) m \<le> X ma"
hoelzl@51340
   306
      using seq_suble[OF `subseq r`, of m] by (intro bexI[of _ "r m"]) auto
hoelzl@51340
   307
  qed
haftmann@56212
   308
  then show ?thesis by (auto intro!: INF_mono simp: limsup_INF_SUP comp_def)
hoelzl@51340
   309
qed
hoelzl@51340
   310
hoelzl@51340
   311
end