Theory Nat

(*  Title:      Sequents/LK/Nat.thy
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1999  University of Cambridge
*)

section ‹Theory of the natural numbers: Peano's axioms, primitive recursion›

theory Nat
imports "../LK"
begin

typedecl nat
instance nat :: "term" ..

axiomatization
  Zero :: nat      (‹0›) and
  Suc :: "nat ⇒ nat" and
  rec :: "[nat, 'a, [nat,'a] ⇒ 'a] ⇒ 'a"
where
  induct:  "⟦$H ⊢ $E, P(0), $F;
             ⋀x. $H, P(x) ⊢ $E, P(Suc(x)), $F⟧ ⟹ $H ⊢ $E, P(n), $F" and

  Suc_inject:  "⊢ Suc(m) = Suc(n) ⟶ m = n" and
  Suc_neq_0:   "⊢ Suc(m) ≠ 0" and
  rec_0:       "⊢ rec(0,a,f) = a" and
  rec_Suc:     "⊢ rec(Suc(m), a, f) = f(m, rec(m,a,f))"

definition add :: "[nat, nat] ⇒ nat"  (infixl ‹+› 60)
  where "m + n == rec(m, n, λx y. Suc(y))"


declare Suc_neq_0 [simp]

lemma Suc_inject_rule: "$H, $G, m = n ⊢ $E ⟹ $H, Suc(m) = Suc(n), $G ⊢ $E"
  by (rule L_of_imp [OF Suc_inject])

lemma Suc_n_not_n: "⊢ Suc(k) ≠ k"
  apply (rule_tac n = k in induct)
  apply simp
  apply (fast add!: Suc_inject_rule)
  done

lemma add_0: "⊢ 0 + n = n"
  apply (unfold add_def)
  apply (rule rec_0)
  done

lemma add_Suc: "⊢ Suc(m) + n = Suc(m + n)"
  apply (unfold add_def)
  apply (rule rec_Suc)
  done

declare add_0 [simp] add_Suc [simp]

lemma add_assoc: "⊢ (k + m) + n = k + (m + n)"
  apply (rule_tac n = "k" in induct)
  apply simp_all
  done

lemma add_0_right: "⊢ m + 0 = m"
  apply (rule_tac n = "m" in induct)
  apply simp_all
  done

lemma add_Suc_right: "⊢ m + Suc(n) = Suc(m + n)"
  apply (rule_tac n = "m" in induct)
  apply simp_all
  done

lemma "(⋀n. ⊢ f(Suc(n)) = Suc(f(n))) ⟹ ⊢ f(i + j) = i + f(j)"
  apply (rule_tac n = "i" in induct)
  apply simp_all
  done

end