0

1 
(* Title: FOLP/ex/nat.thy


2 
ID: $Id$


3 
Author: Lawrence C Paulson, Cambridge University Computer Laboratory


4 
Copyright 1992 University of Cambridge


5 


6 
Examples for the manual "Introduction to Isabelle"


7 


8 
Theory of the natural numbers: Peano's axioms, primitive recursion


9 
*)


10 


11 
Nat = IFOLP +

353

12 
types nat

0

13 
arities nat :: term


14 
consts "0" :: "nat" ("0")


15 
Suc :: "nat=>nat"


16 
rec :: "[nat, 'a, [nat,'a]=>'a] => 'a"


17 
"+" :: "[nat, nat] => nat" (infixl 60)


18 


19 
(*Proof terms*)


20 
nrec :: "[nat,p,[nat,p]=>p]=>p"


21 
ninj,nneq :: "p=>p"


22 
rec0, recSuc :: "p"


23 


24 
rules

1149

25 
induct "[ b:P(0); !!x u. u:P(x) ==> c(x,u):P(Suc(x))


26 
] ==> nrec(n,b,c):P(n)"

0

27 


28 
Suc_inject "p:Suc(m)=Suc(n) ==> ninj(p) : m=n"


29 
Suc_neq_0 "p:Suc(m)=0 ==> nneq(p) : R"


30 
rec_0 "rec0 : rec(0,a,f) = a"


31 
rec_Suc "recSuc : rec(Suc(m), a, f) = f(m, rec(m,a,f))"


32 
add_def "m+n == rec(m, n, %x y. Suc(y))"


33 


34 
nrecB0 "b: A ==> nrec(0,b,c) = b : A"


35 
nrecBSuc "c(n,nrec(n,b,c)) : A ==> nrec(Suc(n),b,c) = c(n,nrec(n,b,c)) : A"


36 
end
