equal
deleted
inserted
replaced
166 qed |
166 qed |
167 qed |
167 qed |
168 |
168 |
169 text {* |
169 text {* |
170 For a set of natural numbers to be infinite, it is enough |
170 For a set of natural numbers to be infinite, it is enough |
171 to know that for any number larger than some $k$, there |
171 to know that for any number larger than some @{text k}, there |
172 is some larger number that is an element of the set. |
172 is some larger number that is an element of the set. |
173 *} |
173 *} |
174 |
174 |
175 lemma unbounded_k_infinite: |
175 lemma unbounded_k_infinite: |
176 assumes k: "\<forall>m. k<m \<longrightarrow> (\<exists>n. m<n \<and> n\<in>S)" |
176 assumes k: "\<forall>m. k<m \<longrightarrow> (\<exists>n. m<n \<and> n\<in>S)" |
196 "finite (UNIV::nat set) \<Longrightarrow> R" |
196 "finite (UNIV::nat set) \<Longrightarrow> R" |
197 by simp |
197 by simp |
198 |
198 |
199 text {* |
199 text {* |
200 Every infinite set contains a countable subset. More precisely |
200 Every infinite set contains a countable subset. More precisely |
201 we show that a set $S$ is infinite if and only if there exists |
201 we show that a set @{text S} is infinite if and only if there exists |
202 an injective function from the naturals into $S$. |
202 an injective function from the naturals into @{text S}. |
203 *} |
203 *} |
204 |
204 |
205 lemma range_inj_infinite: |
205 lemma range_inj_infinite: |
206 "inj (f::nat \<Rightarrow> 'a) \<Longrightarrow> infinite (range f)" |
206 "inj (f::nat \<Rightarrow> 'a) \<Longrightarrow> infinite (range f)" |
207 proof |
207 proof |
213 qed |
213 qed |
214 |
214 |
215 text {* |
215 text {* |
216 The ``only if'' direction is harder because it requires the |
216 The ``only if'' direction is harder because it requires the |
217 construction of a sequence of pairwise different elements of |
217 construction of a sequence of pairwise different elements of |
218 an infinite set $S$. The idea is to construct a sequence of |
218 an infinite set @{text S}. The idea is to construct a sequence of |
219 non-empty and infinite subsets of $S$ obtained by successively |
219 non-empty and infinite subsets of @{text S} obtained by successively |
220 removing elements of $S$. |
220 removing elements of @{text S}. |
221 *} |
221 *} |
222 |
222 |
223 lemma linorder_injI: |
223 lemma linorder_injI: |
224 assumes hyp: "\<forall>x y. x < (y::'a::linorder) \<longrightarrow> f x \<noteq> f y" |
224 assumes hyp: "\<forall>x y. x < (y::'a::linorder) \<longrightarrow> f x \<noteq> f y" |
225 shows "inj f" |
225 shows "inj f" |