src/HOL/Probability/Discrete_Topology.thy
changeset 50089 1badf63e5d97
child 50245 dea9363887a6
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/HOL/Probability/Discrete_Topology.thy	Thu Nov 15 15:50:01 2012 +0100
     1.3 @@ -0,0 +1,64 @@
     1.4 +(*  Title:      HOL/Probability/Discrete_Topology.thy
     1.5 +    Author:     Fabian Immler, TU M√ľnchen
     1.6 +*)
     1.7 +
     1.8 +theory Discrete_Topology
     1.9 +imports Multivariate_Analysis
    1.10 +begin
    1.11 +
    1.12 +text {* Copy of discrete types with discrete topology. This space is polish. *}
    1.13 +
    1.14 +typedef 'a discrete = "UNIV::'a set"
    1.15 +morphisms of_discrete discrete
    1.16 +..
    1.17 +
    1.18 +instantiation discrete :: (type) topological_space
    1.19 +begin
    1.20 +
    1.21 +definition open_discrete::"'a discrete set \<Rightarrow> bool"
    1.22 +  where "open_discrete s = True"
    1.23 +
    1.24 +instance proof qed (auto simp: open_discrete_def)
    1.25 +end
    1.26 +
    1.27 +instantiation discrete :: (type) metric_space
    1.28 +begin
    1.29 +
    1.30 +definition dist_discrete::"'a discrete \<Rightarrow> 'a discrete \<Rightarrow> real"
    1.31 +  where "dist_discrete n m = (if n = m then 0 else 1)"
    1.32 +
    1.33 +instance proof qed (auto simp: open_discrete_def dist_discrete_def intro: exI[where x=1])
    1.34 +end
    1.35 +
    1.36 +instance discrete :: (type) complete_space
    1.37 +proof
    1.38 +  fix X::"nat\<Rightarrow>'a discrete" assume "Cauchy X"
    1.39 +  hence "\<exists>n. \<forall>m\<ge>n. X n = X m"
    1.40 +    by (force simp: dist_discrete_def Cauchy_def split: split_if_asm dest:spec[where x=1])
    1.41 +  then guess n ..
    1.42 +  thus "convergent X"
    1.43 +    by (intro convergentI[where L="X n"] tendstoI eventually_sequentiallyI[of n])
    1.44 +       (simp add: dist_discrete_def)
    1.45 +qed
    1.46 +
    1.47 +instance discrete :: (countable) countable
    1.48 +proof
    1.49 +  have "inj (\<lambda>c::'a discrete. to_nat (of_discrete c))"
    1.50 +    by (simp add: inj_on_def of_discrete_inject)
    1.51 +  thus "\<exists>f::'a discrete \<Rightarrow> nat. inj f" by blast
    1.52 +qed
    1.53 +
    1.54 +instance discrete :: (countable) enumerable_basis
    1.55 +proof
    1.56 +  have "topological_basis (range (\<lambda>n::nat. {from_nat n::'a discrete}))"
    1.57 +  proof (intro topological_basisI)
    1.58 +    fix x::"'a discrete" and O' assume "open O'" "x \<in> O'"
    1.59 +    thus "\<exists>B'\<in>range (\<lambda>n. {from_nat n}). x \<in> B' \<and> B' \<subseteq> O'"
    1.60 +      by (auto intro: exI[where x="to_nat x"])
    1.61 +  qed (simp add: open_discrete_def)
    1.62 +  thus "\<exists>f::nat\<Rightarrow>'a discrete set. topological_basis (range f)" by blast
    1.63 +qed
    1.64 +
    1.65 +instance discrete :: (countable) polish_space ..
    1.66 +
    1.67 +end