src/HOL/Library/Countable.thy
changeset 61115 3a4400985780
parent 61076 bdc1e2f0a86a
child 62087 44841d07ef1d
equal deleted inserted replaced
61114:dcfc28144858 61115:3a4400985780
    64 qed
    64 qed
    65 
    65 
    66 
    66 
    67 subsection \<open>Automatically proving countability of old-style datatypes\<close>
    67 subsection \<open>Automatically proving countability of old-style datatypes\<close>
    68 
    68 
    69 inductive finite_item :: "'a Old_Datatype.item \<Rightarrow> bool" where
    69 context
       
    70 begin
       
    71 
       
    72 qualified inductive finite_item :: "'a Old_Datatype.item \<Rightarrow> bool" where
    70   undefined: "finite_item undefined"
    73   undefined: "finite_item undefined"
    71 | In0: "finite_item x \<Longrightarrow> finite_item (Old_Datatype.In0 x)"
    74 | In0: "finite_item x \<Longrightarrow> finite_item (Old_Datatype.In0 x)"
    72 | In1: "finite_item x \<Longrightarrow> finite_item (Old_Datatype.In1 x)"
    75 | In1: "finite_item x \<Longrightarrow> finite_item (Old_Datatype.In1 x)"
    73 | Leaf: "finite_item (Old_Datatype.Leaf a)"
    76 | Leaf: "finite_item (Old_Datatype.Leaf a)"
    74 | Scons: "\<lbrakk>finite_item x; finite_item y\<rbrakk> \<Longrightarrow> finite_item (Old_Datatype.Scons x y)"
    77 | Scons: "\<lbrakk>finite_item x; finite_item y\<rbrakk> \<Longrightarrow> finite_item (Old_Datatype.Scons x y)"
    75 
    78 
    76 function
    79 qualified function nth_item :: "nat \<Rightarrow> ('a::countable) Old_Datatype.item"
    77   nth_item :: "nat \<Rightarrow> ('a::countable) Old_Datatype.item"
       
    78 where
    80 where
    79   "nth_item 0 = undefined"
    81   "nth_item 0 = undefined"
    80 | "nth_item (Suc n) =
    82 | "nth_item (Suc n) =
    81   (case sum_decode n of
    83   (case sum_decode n of
    82     Inl i \<Rightarrow>
    84     Inl i \<Rightarrow>
    95 unfolding sum_encode_def by simp
    97 unfolding sum_encode_def by simp
    96 
    98 
    97 lemma le_sum_encode_Inr: "x \<le> y \<Longrightarrow> x \<le> sum_encode (Inr y)"
    99 lemma le_sum_encode_Inr: "x \<le> y \<Longrightarrow> x \<le> sum_encode (Inr y)"
    98 unfolding sum_encode_def by simp
   100 unfolding sum_encode_def by simp
    99 
   101 
   100 termination
   102 qualified termination
   101 by (relation "measure id")
   103 by (relation "measure id")
   102   (auto simp add: sum_encode_eq [symmetric] prod_encode_eq [symmetric]
   104   (auto simp add: sum_encode_eq [symmetric] prod_encode_eq [symmetric]
   103     le_imp_less_Suc le_sum_encode_Inl le_sum_encode_Inr
   105     le_imp_less_Suc le_sum_encode_Inl le_sum_encode_Inr
   104     le_prod_encode_1 le_prod_encode_2)
   106     le_prod_encode_1 le_prod_encode_2)
   105 
   107 
   191            eresolve_tac ctxt [induct_thm'] i,
   193            eresolve_tac ctxt [induct_thm'] i,
   192            REPEAT (resolve_tac ctxt rules i ORELSE assume_tac ctxt i)]) 1
   194            REPEAT (resolve_tac ctxt rules i ORELSE assume_tac ctxt i)]) 1
   193       end)
   195       end)
   194 \<close>
   196 \<close>
   195 
   197 
   196 hide_const (open) finite_item nth_item
   198 end
   197 
   199 
   198 
   200 
   199 subsection \<open>Automatically proving countability of datatypes\<close>
   201 subsection \<open>Automatically proving countability of datatypes\<close>
   200 
   202 
   201 ML_file "bnf_lfp_countable.ML"
   203 ML_file "bnf_lfp_countable.ML"