237 obtains S where "incseq S" "(\<Union>j. S j) = X" "range S \<subseteq> union_closed_basis" |
237 obtains S where "incseq S" "(\<Union>j. S j) = X" "range S \<subseteq> union_closed_basis" |
238 using open_imp_Union_of_incseq assms by atomize_elim |
238 using open_imp_Union_of_incseq assms by atomize_elim |
239 |
239 |
240 end |
240 end |
241 |
241 |
|
242 class first_countable_topology = topological_space + |
|
243 assumes first_countable_basis: |
|
244 "\<exists>A. countable A \<and> (\<forall>a\<in>A. x \<in> a \<and> open a) \<and> (\<forall>S. open S \<and> x \<in> S \<longrightarrow> (\<exists>a\<in>A. a \<subseteq> S))" |
|
245 |
|
246 lemma (in first_countable_topology) countable_basis_at_decseq: |
|
247 obtains A :: "nat \<Rightarrow> 'a set" where |
|
248 "\<And>i. open (A i)" "\<And>i. x \<in> (A i)" |
|
249 "\<And>S. open S \<Longrightarrow> x \<in> S \<Longrightarrow> eventually (\<lambda>i. A i \<subseteq> S) sequentially" |
|
250 proof atomize_elim |
|
251 from first_countable_basis[of x] obtain A |
|
252 where "countable A" |
|
253 and nhds: "\<And>a. a \<in> A \<Longrightarrow> open a" "\<And>a. a \<in> A \<Longrightarrow> x \<in> a" |
|
254 and incl: "\<And>S. open S \<Longrightarrow> x \<in> S \<Longrightarrow> \<exists>a\<in>A. a \<subseteq> S" by auto |
|
255 then have "A \<noteq> {}" by auto |
|
256 with `countable A` have r: "A = range (from_nat_into A)" by auto |
|
257 def F \<equiv> "\<lambda>n. \<Inter>i\<le>n. from_nat_into A i" |
|
258 show "\<exists>A. (\<forall>i. open (A i)) \<and> (\<forall>i. x \<in> A i) \<and> |
|
259 (\<forall>S. open S \<longrightarrow> x \<in> S \<longrightarrow> eventually (\<lambda>i. A i \<subseteq> S) sequentially)" |
|
260 proof (safe intro!: exI[of _ F]) |
|
261 fix i |
|
262 show "open (F i)" using nhds(1) r by (auto simp: F_def intro!: open_INT) |
|
263 show "x \<in> F i" using nhds(2) r by (auto simp: F_def) |
|
264 next |
|
265 fix S assume "open S" "x \<in> S" |
|
266 from incl[OF this] obtain i where "F i \<subseteq> S" |
|
267 by (subst (asm) r) (auto simp: F_def) |
|
268 moreover have "\<And>j. i \<le> j \<Longrightarrow> F j \<subseteq> F i" |
|
269 by (auto simp: F_def) |
|
270 ultimately show "eventually (\<lambda>i. F i \<subseteq> S) sequentially" |
|
271 by (auto simp: eventually_sequentially) |
|
272 qed |
|
273 qed |
|
274 |
|
275 lemma (in first_countable_topology) first_countable_basisE: |
|
276 obtains A where "countable A" "\<And>a. a \<in> A \<Longrightarrow> x \<in> a" "\<And>a. a \<in> A \<Longrightarrow> open a" |
|
277 "\<And>S. open S \<Longrightarrow> x \<in> S \<Longrightarrow> (\<exists>a\<in>A. a \<subseteq> S)" |
|
278 using first_countable_basis[of x] |
|
279 by atomize_elim auto |
|
280 |
|
281 instance prod :: (first_countable_topology, first_countable_topology) first_countable_topology |
|
282 proof |
|
283 fix x :: "'a \<times> 'b" |
|
284 from first_countable_basisE[of "fst x"] guess A :: "'a set set" . note A = this |
|
285 from first_countable_basisE[of "snd x"] guess B :: "'b set set" . note B = this |
|
286 show "\<exists>A::('a\<times>'b) set set. countable A \<and> (\<forall>a\<in>A. x \<in> a \<and> open a) \<and> (\<forall>S. open S \<and> x \<in> S \<longrightarrow> (\<exists>a\<in>A. a \<subseteq> S))" |
|
287 proof (intro exI[of _ "(\<lambda>(a, b). a \<times> b) ` (A \<times> B)"], safe) |
|
288 fix a b assume x: "a \<in> A" "b \<in> B" |
|
289 with A(2, 3)[of a] B(2, 3)[of b] show "x \<in> a \<times> b" "open (a \<times> b)" |
|
290 unfolding mem_Times_iff by (auto intro: open_Times) |
|
291 next |
|
292 fix S assume "open S" "x \<in> S" |
|
293 from open_prod_elim[OF this] guess a' b' . |
|
294 moreover with A(4)[of a'] B(4)[of b'] |
|
295 obtain a b where "a \<in> A" "a \<subseteq> a'" "b \<in> B" "b \<subseteq> b'" by auto |
|
296 ultimately show "\<exists>a\<in>(\<lambda>(a, b). a \<times> b) ` (A \<times> B). a \<subseteq> S" |
|
297 by (auto intro!: bexI[of _ "a \<times> b"] bexI[of _ a] bexI[of _ b]) |
|
298 qed (simp add: A B) |
|
299 qed |
|
300 |
|
301 instance metric_space \<subseteq> first_countable_topology |
|
302 proof |
|
303 fix x :: 'a |
|
304 show "\<exists>A. countable A \<and> (\<forall>a\<in>A. x \<in> a \<and> open a) \<and> (\<forall>S. open S \<and> x \<in> S \<longrightarrow> (\<exists>a\<in>A. a \<subseteq> S))" |
|
305 proof (intro exI, safe) |
|
306 fix S assume "open S" "x \<in> S" |
|
307 then obtain r where "0 < r" "{y. dist x y < r} \<subseteq> S" |
|
308 by (auto simp: open_dist dist_commute subset_eq) |
|
309 moreover from reals_Archimedean[OF `0 < r`] guess n .. |
|
310 moreover |
|
311 then have "{y. dist x y < inverse (Suc n)} \<subseteq> {y. dist x y < r}" |
|
312 by (auto simp: inverse_eq_divide) |
|
313 ultimately show "\<exists>a\<in>range (\<lambda>n. {y. dist x y < inverse (Suc n)}). a \<subseteq> S" |
|
314 by auto |
|
315 qed (auto intro: open_ball) |
|
316 qed |
|
317 |
242 class second_countable_topology = topological_space + |
318 class second_countable_topology = topological_space + |
243 assumes ex_countable_basis: |
319 assumes ex_countable_basis: |
244 "\<exists>B::'a::topological_space set set. countable B \<and> topological_basis B" |
320 "\<exists>B::'a::topological_space set set. countable B \<and> topological_basis B" |
245 |
321 |
246 sublocale second_countable_topology < countable_basis "SOME B. countable B \<and> topological_basis B" |
322 sublocale second_countable_topology < countable_basis "SOME B. countable B \<and> topological_basis B" |
253 moreover |
329 moreover |
254 obtain B :: "'b set set" where "countable B" "topological_basis B" |
330 obtain B :: "'b set set" where "countable B" "topological_basis B" |
255 using ex_countable_basis by auto |
331 using ex_countable_basis by auto |
256 ultimately show "\<exists>B::('a \<times> 'b) set set. countable B \<and> topological_basis B" |
332 ultimately show "\<exists>B::('a \<times> 'b) set set. countable B \<and> topological_basis B" |
257 by (auto intro!: exI[of _ "(\<lambda>(a, b). a \<times> b) ` (A \<times> B)"] topological_basis_prod) |
333 by (auto intro!: exI[of _ "(\<lambda>(a, b). a \<times> b) ` (A \<times> B)"] topological_basis_prod) |
|
334 qed |
|
335 |
|
336 instance second_countable_topology \<subseteq> first_countable_topology |
|
337 proof |
|
338 fix x :: 'a |
|
339 def B \<equiv> "SOME B::'a set set. countable B \<and> topological_basis B" |
|
340 then have B: "countable B" "topological_basis B" |
|
341 using countable_basis is_basis |
|
342 by (auto simp: countable_basis is_basis) |
|
343 then show "\<exists>A. countable A \<and> (\<forall>a\<in>A. x \<in> a \<and> open a) \<and> (\<forall>S. open S \<and> x \<in> S \<longrightarrow> (\<exists>a\<in>A. a \<subseteq> S))" |
|
344 by (intro exI[of _ "{b\<in>B. x \<in> b}"]) |
|
345 (fastforce simp: topological_space_class.topological_basis_def) |
258 qed |
346 qed |
259 |
347 |
260 subsection {* Polish spaces *} |
348 subsection {* Polish spaces *} |
261 |
349 |
262 text {* Textbooks define Polish spaces as completely metrizable. |
350 text {* Textbooks define Polish spaces as completely metrizable. |
1348 qed |
1436 qed |
1349 |
1437 |
1350 text{* Another limit point characterization. *} |
1438 text{* Another limit point characterization. *} |
1351 |
1439 |
1352 lemma islimpt_sequential: |
1440 lemma islimpt_sequential: |
1353 fixes x :: "'a::metric_space" |
1441 fixes x :: "'a::first_countable_topology" |
1354 shows "x islimpt S \<longleftrightarrow> (\<exists>f. (\<forall>n::nat. f n \<in> S -{x}) \<and> (f ---> x) sequentially)" |
1442 shows "x islimpt S \<longleftrightarrow> (\<exists>f. (\<forall>n::nat. f n \<in> S - {x}) \<and> (f ---> x) sequentially)" |
1355 (is "?lhs = ?rhs") |
1443 (is "?lhs = ?rhs") |
1356 proof |
1444 proof |
1357 assume ?lhs |
1445 assume ?lhs |
1358 then obtain f where f:"\<forall>y. y>0 \<longrightarrow> f y \<in> S \<and> f y \<noteq> x \<and> dist (f y) x < y" |
1446 from countable_basis_at_decseq[of x] guess A . note A = this |
1359 unfolding islimpt_approachable |
1447 def f \<equiv> "\<lambda>n. SOME y. y \<in> S \<and> y \<in> A n \<and> x \<noteq> y" |
1360 using choice[of "\<lambda>e y. e>0 \<longrightarrow> y\<in>S \<and> y\<noteq>x \<and> dist y x < e"] by auto |
1448 { fix n |
1361 let ?I = "\<lambda>n. inverse (real (Suc n))" |
1449 from `?lhs` have "\<exists>y. y \<in> S \<and> y \<in> A n \<and> x \<noteq> y" |
1362 have "\<forall>n. f (?I n) \<in> S - {x}" using f by simp |
1450 unfolding islimpt_def using A(1,2)[of n] by auto |
1363 moreover have "(\<lambda>n. f (?I n)) ----> x" |
1451 then have "f n \<in> S \<and> f n \<in> A n \<and> x \<noteq> f n" |
1364 proof (rule metric_tendsto_imp_tendsto) |
1452 unfolding f_def by (rule someI_ex) |
1365 show "?I ----> 0" |
1453 then have "f n \<in> S" "f n \<in> A n" "x \<noteq> f n" by auto } |
1366 by (rule LIMSEQ_inverse_real_of_nat) |
1454 then have "\<forall>n. f n \<in> S - {x}" by auto |
1367 show "eventually (\<lambda>n. dist (f (?I n)) x \<le> dist (?I n) 0) sequentially" |
1455 moreover have "(\<lambda>n. f n) ----> x" |
1368 by (simp add: norm_conv_dist [symmetric] less_imp_le f) |
1456 proof (rule topological_tendstoI) |
|
1457 fix S assume "open S" "x \<in> S" |
|
1458 from A(3)[OF this] `\<And>n. f n \<in> A n` |
|
1459 show "eventually (\<lambda>x. f x \<in> S) sequentially" by (auto elim!: eventually_elim1) |
1369 qed |
1460 qed |
1370 ultimately show ?rhs by fast |
1461 ultimately show ?rhs by fast |
1371 next |
1462 next |
1372 assume ?rhs |
1463 assume ?rhs |
1373 then obtain f::"nat\<Rightarrow>'a" where f:"(\<forall>n. f n \<in> S - {x})" "(\<forall>e>0. \<exists>N. \<forall>n\<ge>N. dist (f n) x < e)" unfolding LIMSEQ_def by auto |
1464 then obtain f :: "nat \<Rightarrow> 'a" where f: "\<And>n. f n \<in> S - {x}" and lim: "f ----> x" by auto |
1374 { fix e::real assume "e>0" |
1465 show ?lhs |
1375 then obtain N where "dist (f N) x < e" using f(2) by auto |
1466 unfolding islimpt_def |
1376 moreover have "f N\<in>S" "f N \<noteq> x" using f(1) by auto |
1467 proof safe |
1377 ultimately have "\<exists>x'\<in>S. x' \<noteq> x \<and> dist x' x < e" by auto |
1468 fix T assume "open T" "x \<in> T" |
1378 } |
1469 from lim[THEN topological_tendstoD, OF this] f |
1379 thus ?lhs unfolding islimpt_approachable by auto |
1470 show "\<exists>y\<in>S. y \<in> T \<and> y \<noteq> x" |
|
1471 unfolding eventually_sequentially by auto |
|
1472 qed |
1380 qed |
1473 qed |
1381 |
1474 |
1382 lemma Lim_inv: (* TODO: delete *) |
1475 lemma Lim_inv: (* TODO: delete *) |
1383 fixes f :: "'a \<Rightarrow> real" and A :: "'a filter" |
1476 fixes f :: "'a \<Rightarrow> real" and A :: "'a filter" |
1384 assumes "(f ---> l) A" and "l \<noteq> 0" |
1477 assumes "(f ---> l) A" and "l \<noteq> 0" |
2776 qed |
2869 qed |
2777 |
2870 |
2778 subsubsection {* Complete the chain of compactness variants *} |
2871 subsubsection {* Complete the chain of compactness variants *} |
2779 |
2872 |
2780 lemma islimpt_range_imp_convergent_subsequence: |
2873 lemma islimpt_range_imp_convergent_subsequence: |
2781 fixes f :: "nat \<Rightarrow> 'a::metric_space" |
2874 fixes l :: "'a :: {t1_space, first_countable_topology}" |
2782 assumes "l islimpt (range f)" |
2875 assumes l: "l islimpt (range f)" |
2783 shows "\<exists>r. subseq r \<and> ((f \<circ> r) ---> l) sequentially" |
2876 shows "\<exists>r. subseq r \<and> ((f \<circ> r) ---> l) sequentially" |
2784 proof (intro exI conjI) |
2877 proof - |
2785 have *: "\<And>e. 0 < e \<Longrightarrow> \<exists>n. 0 < dist (f n) l \<and> dist (f n) l < e" |
2878 from first_countable_topology_class.countable_basis_at_decseq[of l] guess A . note A = this |
2786 using assms unfolding islimpt_def |
2879 |
2787 by (drule_tac x="ball l e" in spec) |
2880 def s \<equiv> "\<lambda>n i. SOME j. i < j \<and> f j \<in> A (Suc n)" |
2788 (auto simp add: zero_less_dist_iff dist_commute) |
2881 { fix n i |
2789 |
2882 have "\<exists>a. i < a \<and> f a \<in> A (Suc n)" |
2790 def t \<equiv> "\<lambda>e. LEAST n. 0 < dist (f n) l \<and> dist (f n) l < e" |
2883 by (rule l[THEN islimptE, of "A (Suc n) - (f ` {.. i} - {l})"]) |
2791 have f_t_neq: "\<And>e. 0 < e \<Longrightarrow> 0 < dist (f (t e)) l" |
2884 (auto simp: not_le[symmetric] finite_imp_closed A(1,2)) |
2792 unfolding t_def by (rule LeastI2_ex [OF * conjunct1]) |
2885 then have "i < s n i" "f (s n i) \<in> A (Suc n)" |
2793 have f_t_closer: "\<And>e. 0 < e \<Longrightarrow> dist (f (t e)) l < e" |
2886 unfolding s_def by (auto intro: someI2_ex) } |
2794 unfolding t_def by (rule LeastI2_ex [OF * conjunct2]) |
2887 note s = this |
2795 have t_le: "\<And>n e. 0 < dist (f n) l \<Longrightarrow> dist (f n) l < e \<Longrightarrow> t e \<le> n" |
2888 def r \<equiv> "nat_rec (s 0 0) s" |
2796 unfolding t_def by (simp add: Least_le) |
2889 have "subseq r" |
2797 have less_tD: "\<And>n e. n < t e \<Longrightarrow> 0 < dist (f n) l \<Longrightarrow> e \<le> dist (f n) l" |
2890 by (auto simp: r_def s subseq_Suc_iff) |
2798 unfolding t_def by (drule not_less_Least) simp |
2891 moreover |
2799 have t_antimono: "\<And>e e'. 0 < e \<Longrightarrow> e \<le> e' \<Longrightarrow> t e' \<le> t e" |
2892 have "(\<lambda>n. f (r n)) ----> l" |
2800 apply (rule t_le) |
2893 proof (rule topological_tendstoI) |
2801 apply (erule f_t_neq) |
2894 fix S assume "open S" "l \<in> S" |
2802 apply (erule (1) less_le_trans [OF f_t_closer]) |
2895 with A(3) have "eventually (\<lambda>i. A i \<subseteq> S) sequentially" by auto |
2803 done |
2896 moreover |
2804 have t_dist_f_neq: "\<And>n. 0 < dist (f n) l \<Longrightarrow> t (dist (f n) l) \<noteq> n" |
2897 { fix i assume "Suc 0 \<le> i" then have "f (r i) \<in> A i" |
2805 by (drule f_t_closer) auto |
2898 by (cases i) (simp_all add: r_def s) } |
2806 have t_less: "\<And>e. 0 < e \<Longrightarrow> t e < t (dist (f (t e)) l)" |
2899 then have "eventually (\<lambda>i. f (r i) \<in> A i) sequentially" by (auto simp: eventually_sequentially) |
2807 apply (subst less_le) |
2900 ultimately show "eventually (\<lambda>i. f (r i) \<in> S) sequentially" |
2808 apply (rule conjI) |
2901 by eventually_elim auto |
2809 apply (rule t_antimono) |
2902 qed |
2810 apply (erule f_t_neq) |
2903 ultimately show "\<exists>r. subseq r \<and> (f \<circ> r) ----> l" |
2811 apply (erule f_t_closer [THEN less_imp_le]) |
2904 by (auto simp: convergent_def comp_def) |
2812 apply (rule t_dist_f_neq [symmetric]) |
|
2813 apply (erule f_t_neq) |
|
2814 done |
|
2815 have dist_f_t_less': |
|
2816 "\<And>e e'. 0 < e \<Longrightarrow> 0 < e' \<Longrightarrow> t e \<le> t e' \<Longrightarrow> dist (f (t e')) l < e" |
|
2817 apply (simp add: le_less) |
|
2818 apply (erule disjE) |
|
2819 apply (rule less_trans) |
|
2820 apply (erule f_t_closer) |
|
2821 apply (rule le_less_trans) |
|
2822 apply (erule less_tD) |
|
2823 apply (erule f_t_neq) |
|
2824 apply (erule f_t_closer) |
|
2825 apply (erule subst) |
|
2826 apply (erule f_t_closer) |
|
2827 done |
|
2828 |
|
2829 def r \<equiv> "nat_rec (t 1) (\<lambda>_ x. t (dist (f x) l))" |
|
2830 have r_simps: "r 0 = t 1" "\<And>n. r (Suc n) = t (dist (f (r n)) l)" |
|
2831 unfolding r_def by simp_all |
|
2832 have f_r_neq: "\<And>n. 0 < dist (f (r n)) l" |
|
2833 by (induct_tac n) (simp_all add: r_simps f_t_neq) |
|
2834 |
|
2835 show "subseq r" |
|
2836 unfolding subseq_Suc_iff |
|
2837 apply (rule allI) |
|
2838 apply (case_tac n) |
|
2839 apply (simp_all add: r_simps) |
|
2840 apply (rule t_less, rule zero_less_one) |
|
2841 apply (rule t_less, rule f_r_neq) |
|
2842 done |
|
2843 show "((f \<circ> r) ---> l) sequentially" |
|
2844 unfolding LIMSEQ_def o_def |
|
2845 apply (clarify, rename_tac e, rule_tac x="t e" in exI, clarify) |
|
2846 apply (drule le_trans, rule seq_suble [OF `subseq r`]) |
|
2847 apply (case_tac n, simp_all add: r_simps dist_f_t_less' f_r_neq) |
|
2848 done |
|
2849 qed |
2905 qed |
2850 |
2906 |
2851 lemma finite_range_imp_infinite_repeats: |
2907 lemma finite_range_imp_infinite_repeats: |
2852 fixes f :: "nat \<Rightarrow> 'a" |
2908 fixes f :: "nat \<Rightarrow> 'a" |
2853 assumes "finite (range f)" |
2909 assumes "finite (range f)" |