src/HOL/Nat.thy
changeset 21456 1c2b9df41e98
parent 21411 a9671d4f7c03
child 21672 29c346b165d4
equal deleted inserted replaced
21455:b6be1d1b66c5 21456:1c2b9df41e98
    44   nat = Nat
    44   nat = Nat
    45 proof
    45 proof
    46   show "Zero_Rep : Nat" by (rule Nat.Zero_RepI)
    46   show "Zero_Rep : Nat" by (rule Nat.Zero_RepI)
    47 qed
    47 qed
    48 
    48 
    49 instance nat :: "{ord, zero, one}" ..
       
    50 
       
    51 
       
    52 text {* Abstract constants and syntax *}
    49 text {* Abstract constants and syntax *}
    53 
    50 
    54 consts
    51 consts
    55   Suc :: "nat => nat"
    52   Suc :: "nat => nat"
    56   pred_nat :: "(nat * nat) set"
    53   pred_nat :: "(nat * nat) set"
    57 
    54 
    58 local
    55 local
    59 
    56 
    60 defs
    57 defs
       
    58   Suc_def:      "Suc == (%n. Abs_Nat (Suc_Rep (Rep_Nat n)))"
       
    59   pred_nat_def: "pred_nat == {(m, n). n = Suc m}"
       
    60 
       
    61 instance nat :: "{ord, zero, one}"
    61   Zero_nat_def: "0 == Abs_Nat Zero_Rep"
    62   Zero_nat_def: "0 == Abs_Nat Zero_Rep"
    62   Suc_def:      "Suc == (%n. Abs_Nat (Suc_Rep (Rep_Nat n)))"
    63   One_nat_def [simp]: "1 == Suc 0"
    63   One_nat_def:  "1 == Suc 0"
       
    64 
       
    65   -- {* nat operations *}
       
    66   pred_nat_def: "pred_nat == {(m, n). n = Suc m}"
       
    67 
       
    68   less_def: "m < n == (m, n) : trancl pred_nat"
    64   less_def: "m < n == (m, n) : trancl pred_nat"
    69 
    65   le_def: "m \<le> (n::nat) == ~ (n < m)" ..
    70   le_def: "m \<le> (n::nat) == ~ (n < m)"
       
    71 
       
    72 declare One_nat_def [simp]
       
    73 
       
    74 
    66 
    75 text {* Induction *}
    67 text {* Induction *}
    76 
    68 
    77 theorem nat_induct: "P 0 ==> (!!n. P n ==> P (Suc n)) ==> P n"
    69 theorem nat_induct: "P 0 ==> (!!n. P n ==> P (Suc n)) ==> P n"
    78   apply (unfold Zero_nat_def Suc_def)
    70   apply (unfold Zero_nat_def Suc_def)
   479 class power =
   471 class power =
   480   fixes power :: "'a \<Rightarrow> nat \<Rightarrow> 'a"            (infixr "\<^loc>^" 80)
   472   fixes power :: "'a \<Rightarrow> nat \<Rightarrow> 'a"            (infixr "\<^loc>^" 80)
   481 
   473 
   482 text {* arithmetic operators @{text "+ -"} and @{text "*"} *}
   474 text {* arithmetic operators @{text "+ -"} and @{text "*"} *}
   483 
   475 
   484 instance nat :: "{plus, minus, times, power}" ..
   476 instance nat :: "{plus, minus, times}" ..
   485 
   477 
   486 primrec
   478 primrec
   487   add_0:    "0 + n = n"
   479   add_0:    "0 + n = n"
   488   add_Suc:  "Suc m + n = Suc (m + n)"
   480   add_Suc:  "Suc m + n = Suc (m + n)"
   489 
   481 
  1057   by simp
  1049   by simp
  1058 
  1050 
  1059 instance nat :: eq ..
  1051 instance nat :: eq ..
  1060 
  1052 
  1061 lemma [code func]:
  1053 lemma [code func]:
  1062   "Code_Generator.eq (0\<Colon>nat) 0 = True" unfolding eq_def by auto
  1054   "(0\<Colon>nat) = 0 \<longleftrightarrow> True" by auto
  1063 
  1055 
  1064 lemma [code func]:
  1056 lemma [code func]:
  1065   "Code_Generator.eq (Suc n) (Suc m) = Code_Generator.eq n m" unfolding eq_def by auto
  1057   "Suc n = Suc m \<longleftrightarrow> n = m" by auto
  1066 
  1058 
  1067 lemma [code func]:
  1059 lemma [code func]:
  1068   "Code_Generator.eq (Suc n) 0 = False" unfolding eq_def by auto
  1060   "Suc n = 0 \<longleftrightarrow> False" by auto
  1069 
  1061 
  1070 lemma [code func]:
  1062 lemma [code func]:
  1071   "Code_Generator.eq 0 (Suc m) = False" unfolding eq_def by auto
  1063   "0 = Suc m \<longleftrightarrow> False" by auto
  1072 
  1064 
  1073 
  1065 
  1074 subsection {* Further Arithmetic Facts Concerning the Natural Numbers *}
  1066 subsection {* Further Arithmetic Facts Concerning the Natural Numbers *}
  1075 
  1067 
  1076 use "arith_data.ML"
  1068 use "arith_data.ML"