140 nat_induct0 |
140 nat_induct0 |
141 |
141 |
142 ML \<open> |
142 ML \<open> |
143 val nat_basic_lfp_sugar = |
143 val nat_basic_lfp_sugar = |
144 let |
144 let |
145 val ctr_sugar = the (Ctr_Sugar.ctr_sugar_of_global @{theory} @{type_name nat}); |
145 val ctr_sugar = the (Ctr_Sugar.ctr_sugar_of_global \<^theory> \<^type_name>\<open>nat\<close>); |
146 val recx = Logic.varify_types_global @{term rec_nat}; |
146 val recx = Logic.varify_types_global \<^term>\<open>rec_nat\<close>; |
147 val C = body_type (fastype_of recx); |
147 val C = body_type (fastype_of recx); |
148 in |
148 in |
149 {T = HOLogic.natT, fp_res_index = 0, C = C, fun_arg_Tsss = [[], [[HOLogic.natT, C]]], |
149 {T = HOLogic.natT, fp_res_index = 0, C = C, fun_arg_Tsss = [[], [[HOLogic.natT, C]]], |
150 ctr_sugar = ctr_sugar, recx = recx, rec_thms = @{thms nat.rec}} |
150 ctr_sugar = ctr_sugar, recx = recx, rec_thms = @{thms nat.rec}} |
151 end; |
151 end; |
152 \<close> |
152 \<close> |
153 |
153 |
154 setup \<open> |
154 setup \<open> |
155 let |
155 let |
156 fun basic_lfp_sugars_of _ [@{typ nat}] _ _ ctxt = |
156 fun basic_lfp_sugars_of _ [\<^typ>\<open>nat\<close>] _ _ ctxt = |
157 ([], [0], [nat_basic_lfp_sugar], [], [], [], TrueI (*dummy*), [], false, ctxt) |
157 ([], [0], [nat_basic_lfp_sugar], [], [], [], TrueI (*dummy*), [], false, ctxt) |
158 | basic_lfp_sugars_of bs arg_Ts callers callssss ctxt = |
158 | basic_lfp_sugars_of bs arg_Ts callers callssss ctxt = |
159 BNF_LFP_Rec_Sugar.default_basic_lfp_sugars_of bs arg_Ts callers callssss ctxt; |
159 BNF_LFP_Rec_Sugar.default_basic_lfp_sugars_of bs arg_Ts callers callssss ctxt; |
160 in |
160 in |
161 BNF_LFP_Rec_Sugar.register_lfp_rec_extension |
161 BNF_LFP_Rec_Sugar.register_lfp_rec_extension |
259 by (induct n) simp_all |
259 by (induct n) simp_all |
260 |
260 |
261 lemma Suc_n_not_n: "Suc n \<noteq> n" |
261 lemma Suc_n_not_n: "Suc n \<noteq> n" |
262 by (rule not_sym) (rule n_not_Suc_n) |
262 by (rule not_sym) (rule n_not_Suc_n) |
263 |
263 |
264 text \<open>A special form of induction for reasoning about @{term "m < n"} and @{term "m - n"}.\<close> |
264 text \<open>A special form of induction for reasoning about \<^term>\<open>m < n\<close> and \<^term>\<open>m - n\<close>.\<close> |
265 lemma diff_induct: |
265 lemma diff_induct: |
266 assumes "\<And>x. P x 0" |
266 assumes "\<And>x. P x 0" |
267 and "\<And>y. P 0 (Suc y)" |
267 and "\<And>y. P 0 (Suc y)" |
268 and "\<And>x y. P x y \<Longrightarrow> P (Suc x) (Suc y)" |
268 and "\<And>x y. P x y \<Longrightarrow> P (Suc x) (Suc y)" |
269 shows "P m n" |
269 shows "P m n" |
462 |
462 |
463 lemma Suc_mult_cancel1: "Suc k * m = Suc k * n \<longleftrightarrow> m = n" |
463 lemma Suc_mult_cancel1: "Suc k * m = Suc k * n \<longleftrightarrow> m = n" |
464 by (subst mult_cancel1) simp |
464 by (subst mult_cancel1) simp |
465 |
465 |
466 |
466 |
467 subsection \<open>Orders on @{typ nat}\<close> |
467 subsection \<open>Orders on \<^typ>\<open>nat\<close>\<close> |
468 |
468 |
469 subsubsection \<open>Operation definition\<close> |
469 subsubsection \<open>Operation definition\<close> |
470 |
470 |
471 instantiation nat :: linorder |
471 instantiation nat :: linorder |
472 begin |
472 begin |
686 case (Suc k) |
686 case (Suc k) |
687 with le show ?case |
687 with le show ?case |
688 by simp (auto simp add: less_Suc_eq dest: Suc_lessD) |
688 by simp (auto simp add: less_Suc_eq dest: Suc_lessD) |
689 qed |
689 qed |
690 |
690 |
691 text \<open>Can be used with \<open>less_Suc_eq\<close> to get @{prop "n = m \<or> n < m"}.\<close> |
691 text \<open>Can be used with \<open>less_Suc_eq\<close> to get \<^prop>\<open>n = m \<or> n < m\<close>.\<close> |
692 lemma not_less_eq: "\<not> m < n \<longleftrightarrow> n < Suc m" |
692 lemma not_less_eq: "\<not> m < n \<longleftrightarrow> n < Suc m" |
693 by (simp only: not_less less_Suc_eq_le) |
693 by (simp only: not_less less_Suc_eq_le) |
694 |
694 |
695 lemma not_less_eq_eq: "\<not> m \<le> n \<longleftrightarrow> Suc n \<le> m" |
695 lemma not_less_eq_eq: "\<not> m \<le> n \<longleftrightarrow> Suc n \<le> m" |
696 by (simp only: not_le Suc_le_eq) |
696 by (simp only: not_le Suc_le_eq) |
881 with \<open>i < j\<close> show ?case |
881 with \<open>i < j\<close> show ?case |
882 by (cases k) (simp_all add: add_less_mono) |
882 by (cases k) (simp_all add: add_less_mono) |
883 qed |
883 qed |
884 |
884 |
885 text \<open>Addition is the inverse of subtraction: |
885 text \<open>Addition is the inverse of subtraction: |
886 if @{term "n \<le> m"} then @{term "n + (m - n) = m"}.\<close> |
886 if \<^term>\<open>n \<le> m\<close> then \<^term>\<open>n + (m - n) = m\<close>.\<close> |
887 lemma add_diff_inverse_nat: "\<not> m < n \<Longrightarrow> n + (m - n) = m" |
887 lemma add_diff_inverse_nat: "\<not> m < n \<Longrightarrow> n + (m - n) = m" |
888 for m n :: nat |
888 for m n :: nat |
889 by (induct m n rule: diff_induct) simp_all |
889 by (induct m n rule: diff_induct) simp_all |
890 |
890 |
891 lemma nat_le_iff_add: "m \<le> n \<longleftrightarrow> (\<exists>k. n = m + k)" |
891 lemma nat_le_iff_add: "m \<le> n \<longleftrightarrow> (\<exists>k. n = m + k)" |
919 |
919 |
920 instance nat :: ordered_cancel_comm_monoid_add .. |
920 instance nat :: ordered_cancel_comm_monoid_add .. |
921 instance nat :: ordered_cancel_comm_monoid_diff .. |
921 instance nat :: ordered_cancel_comm_monoid_diff .. |
922 |
922 |
923 |
923 |
924 subsubsection \<open>@{term min} and @{term max}\<close> |
924 subsubsection \<open>\<^term>\<open>min\<close> and \<^term>\<open>max\<close>\<close> |
925 |
925 |
926 lemma mono_Suc: "mono Suc" |
926 lemma mono_Suc: "mono Suc" |
927 by (rule monoI) simp |
927 by (rule monoI) simp |
928 |
928 |
929 lemma min_0L [simp]: "min 0 n = 0" |
929 lemma min_0L [simp]: "min 0 n = 0" |
987 for m n q :: nat |
987 for m n q :: nat |
988 by (simp add: max_def not_le) |
988 by (simp add: max_def not_le) |
989 (auto dest: mult_left_le_imp_le mult_left_less_imp_less le_less_trans) |
989 (auto dest: mult_left_le_imp_le mult_left_less_imp_less le_less_trans) |
990 |
990 |
991 |
991 |
992 subsubsection \<open>Additional theorems about @{term "(\<le>)"}\<close> |
992 subsubsection \<open>Additional theorems about \<^term>\<open>(\<le>)\<close>\<close> |
993 |
993 |
994 text \<open>Complete induction, aka course-of-values induction\<close> |
994 text \<open>Complete induction, aka course-of-values induction\<close> |
995 |
995 |
996 instance nat :: wellorder |
996 instance nat :: wellorder |
997 proof |
997 proof |
2343 lemma antimono_funpow: "mono Q \<Longrightarrow> antimono (\<lambda>i. (Q ^^ i) \<top>)" |
2343 lemma antimono_funpow: "mono Q \<Longrightarrow> antimono (\<lambda>i. (Q ^^ i) \<top>)" |
2344 for Q :: "'a::{lattice,order_top} \<Rightarrow> 'a" |
2344 for Q :: "'a::{lattice,order_top} \<Rightarrow> 'a" |
2345 by (auto intro!: funpow_increasing simp: antimono_def) |
2345 by (auto intro!: funpow_increasing simp: antimono_def) |
2346 |
2346 |
2347 |
2347 |
2348 subsection \<open>The divides relation on @{typ nat}\<close> |
2348 subsection \<open>The divides relation on \<^typ>\<open>nat\<close>\<close> |
2349 |
2349 |
2350 lemma dvd_1_left [iff]: "Suc 0 dvd k" |
2350 lemma dvd_1_left [iff]: "Suc 0 dvd k" |
2351 by (simp add: dvd_def) |
2351 by (simp add: dvd_def) |
2352 |
2352 |
2353 lemma dvd_1_iff_1 [simp]: "m dvd Suc 0 \<longleftrightarrow> m = Suc 0" |
2353 lemma dvd_1_iff_1 [simp]: "m dvd Suc 0 \<longleftrightarrow> m = Suc 0" |