equal
deleted
inserted
replaced
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" |