Quelle  Nat.thy

(*  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