equal
deleted
inserted
replaced
1316 then show ?thesis by (rule monoI1) |
1316 then show ?thesis by (rule monoI1) |
1317 qed |
1317 qed |
1318 |
1318 |
1319 |
1319 |
1320 subsubsection \<open>Subsequence (alternative definition, (e.g. Hoskins)\<close> |
1320 subsubsection \<open>Subsequence (alternative definition, (e.g. Hoskins)\<close> |
1321 |
|
1322 lemma strict_mono_Suc_iff: "strict_mono f \<longleftrightarrow> (\<forall>n. f n < f (Suc n))" |
|
1323 proof (intro iffI strict_monoI) |
|
1324 assume *: "\<forall>n. f n < f (Suc n)" |
|
1325 fix m n :: nat assume "m < n" |
|
1326 thus "f m < f n" |
|
1327 by (induction rule: less_Suc_induct) (use * in auto) |
|
1328 qed (auto simp: strict_mono_def) |
|
1329 |
|
1330 lemma strict_mono_add: "strict_mono (\<lambda>n::'a::linordered_semidom. n + k)" |
|
1331 by (auto simp: strict_mono_def) |
|
1332 |
1321 |
1333 text \<open>For any sequence, there is a monotonic subsequence.\<close> |
1322 text \<open>For any sequence, there is a monotonic subsequence.\<close> |
1334 lemma seq_monosub: |
1323 lemma seq_monosub: |
1335 fixes s :: "nat \<Rightarrow> 'a::linorder" |
1324 fixes s :: "nat \<Rightarrow> 'a::linorder" |
1336 shows "\<exists>f. strict_mono f \<and> monoseq (\<lambda>n. (s (f n)))" |
1325 shows "\<exists>f. strict_mono f \<and> monoseq (\<lambda>n. (s (f n)))" |