equal
deleted
inserted
replaced
11 subsection "Infinite Sets" |
11 subsection "Infinite Sets" |
12 |
12 |
13 text \<open> |
13 text \<open> |
14 Some elementary facts about infinite sets, mostly by Stephan Merz. |
14 Some elementary facts about infinite sets, mostly by Stephan Merz. |
15 Beware! Because "infinite" merely abbreviates a negation, these |
15 Beware! Because "infinite" merely abbreviates a negation, these |
16 lemmas may not work well with @{text "blast"}. |
16 lemmas may not work well with \<open>blast\<close>. |
17 \<close> |
17 \<close> |
18 |
18 |
19 abbreviation infinite :: "'a set \<Rightarrow> bool" |
19 abbreviation infinite :: "'a set \<Rightarrow> bool" |
20 where "infinite S \<equiv> \<not> finite S" |
20 where "infinite S \<equiv> \<not> finite S" |
21 |
21 |
94 lemma finite_nat_bounded: "finite (S::nat set) \<Longrightarrow> \<exists>k. S \<subseteq> {..<k}" |
94 lemma finite_nat_bounded: "finite (S::nat set) \<Longrightarrow> \<exists>k. S \<subseteq> {..<k}" |
95 by (simp add: finite_nat_iff_bounded) |
95 by (simp add: finite_nat_iff_bounded) |
96 |
96 |
97 text \<open> |
97 text \<open> |
98 For a set of natural numbers to be infinite, it is enough to know |
98 For a set of natural numbers to be infinite, it is enough to know |
99 that for any number larger than some @{text k}, there is some larger |
99 that for any number larger than some \<open>k\<close>, there is some larger |
100 number that is an element of the set. |
100 number that is an element of the set. |
101 \<close> |
101 \<close> |
102 |
102 |
103 lemma unbounded_k_infinite: "\<forall>m>k. \<exists>n>m. n \<in> S \<Longrightarrow> infinite (S::nat set)" |
103 lemma unbounded_k_infinite: "\<forall>m>k. \<exists>n>m. n \<in> S \<Longrightarrow> infinite (S::nat set)" |
104 by (metis (full_types) infinite_nat_iff_unbounded_le le_imp_less_Suc not_less |
104 by (metis (full_types) infinite_nat_iff_unbounded_le le_imp_less_Suc not_less |