# Theory Natural_Numbers

Up to index of Isabelle/FOL/ex

theory Natural_Numbers
imports FOL
begin

    (*  Title:      FOL/ex/Natural_Numbers.thy
        ID:         $Id: Natural_Numbers.thy,v 1.8 2005/06/17 14:15:09 haftmann Exp $
        Author:     Markus Wenzel, TU Munich
    *)

    header {* Natural numbers *}

    theory Natural_Numbers imports FOL begin

    text {*
      Theory of the natural numbers: Peano's axioms, primitive recursion.
      (Modernized version of Larry Paulson's theory "Nat".)  \medskip
    *}

    typedecl nat
    arities nat :: "term"

    consts
      Zero :: nat    ("0")
      Suc :: "nat => nat"
      rec :: "[nat, 'a, [nat, 'a] => 'a] => 'a"

    axioms
      induct [case_names 0 Suc, induct type: nat]:
        "P(0) ==> (!!x. P(x) ==> P(Suc(x))) ==> P(n)"
      Suc_inject: "Suc(m) = Suc(n) ==> m = n"
      Suc_neq_0: "Suc(m) = 0 ==> R"
      rec_0: "rec(0, a, f) = a"
      rec_Suc: "rec(Suc(m), a, f) = f(m, rec(m, a, f))"

    lemma Suc_n_not_n: "Suc(k) ≠ k"
    proof (induct k)
      show "Suc(0) ≠ 0"
      proof
        assume "Suc(0) = 0"
        thus False by (rule Suc_neq_0)
      qed
      fix n assume hyp: "Suc(n) ≠ n"
      show "Suc(Suc(n)) ≠ Suc(n)"
      proof
        assume "Suc(Suc(n)) = Suc(n)"
        hence "Suc(n) = n" by (rule Suc_inject)
        with hyp show False by contradiction
      qed
    qed

    constdefs
      add :: "[nat, nat] => nat"    (infixl "+" 60)
      "m + n == rec(m, n, λx y. Suc(y))"

    lemma add_0 [simp]: "0 + n = n"
      by (unfold add_def) (rule rec_0)

    lemma add_Suc [simp]: "Suc(m) + n = Suc(m + n)"
      by (unfold add_def) (rule rec_Suc)

    lemma add_assoc: "(k + m) + n = k + (m + n)"
      by (induct k) simp_all

    lemma add_0_right: "m + 0 = m"
      by (induct m) simp_all

    lemma add_Suc_right: "m + Suc(n) = Suc(m + n)"
      by (induct m) simp_all

    lemma "(!!n. f(Suc(n)) = Suc(f(n))) ==> f(i + j) = i + f(j)"
    proof -
      assume "!!n. f(Suc(n)) = Suc(f(n))"
      thus ?thesis by (induct i) simp_all
    qed

    end

lemma Suc_n_not_n:

      Suc(k) ≠ k

lemma add_0:

      0 + n = n

lemma add_Suc:

      Suc(m) + n = Suc(m + n)

lemma add_assoc:

      k + m + n = k + (m + n)

lemma add_0_right:

      m + 0 = m

lemma add_Suc_right:

      m + Suc(n) = Suc(m + n)

lemma

      (!!n. f(Suc(n)) = Suc(f(n))) ==> f(i + j) = i + f(j)