src/HOL/Nat.thy
changeset 69593 3dda49e08b9d
parent 68618 3db8520941a4
child 69605 a96320074298
equal deleted inserted replaced
69592:a80d8ec6c998 69593:3dda49e08b9d
   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
  1452   fix m q :: nat
  1452   fix m q :: nat
  1453   assume "m \<le> q"
  1453   assume "m \<le> q"
  1454   with assms show "n * m \<le> n * q" by simp
  1454   with assms show "n * m \<le> n * q" by simp
  1455 qed
  1455 qed
  1456 
  1456 
  1457 text \<open>The lattice order on @{typ nat}.\<close>
  1457 text \<open>The lattice order on \<^typ>\<open>nat\<close>.\<close>
  1458 
  1458 
  1459 instantiation nat :: distrib_lattice
  1459 instantiation nat :: distrib_lattice
  1460 begin
  1460 begin
  1461 
  1461 
  1462 definition "(inf :: nat \<Rightarrow> nat \<Rightarrow> nat) = min"
  1462 definition "(inf :: nat \<Rightarrow> nat \<Rightarrow> nat) = min"
  1700   show "?lhs \<le> ?rhs"
  1700   show "?lhs \<le> ?rhs"
  1701     using Kleene_iter_gpfp[OF assms(1)] gfp_unfold[OF assms(1)] by simp
  1701     using Kleene_iter_gpfp[OF assms(1)] gfp_unfold[OF assms(1)] by simp
  1702 qed
  1702 qed
  1703 
  1703 
  1704 
  1704 
  1705 subsection \<open>Embedding of the naturals into any \<open>semiring_1\<close>: @{term of_nat}\<close>
  1705 subsection \<open>Embedding of the naturals into any \<open>semiring_1\<close>: \<^term>\<open>of_nat\<close>\<close>
  1706 
  1706 
  1707 context semiring_1
  1707 context semiring_1
  1708 begin
  1708 begin
  1709 
  1709 
  1710 definition of_nat :: "nat \<Rightarrow> 'a"
  1710 definition of_nat :: "nat \<Rightarrow> 'a"
  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"