src/HOL/Infinite_Set.thy
changeset 14957 0e94a1ccc6ae
parent 14896 985133486546
child 15045 d59f7e2e18d3
equal deleted inserted replaced
14956:70ec4b8aef8d 14957:0e94a1ccc6ae
   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"