src/FOLP/ex/Nat.thy
 changeset 17480 fd19f77dcf60 parent 1477 4c51ab632cda child 25991 31b38a39e589
equal inserted replaced
17479:68a7acb5f22e 17480:fd19f77dcf60
`     1 (*  Title:      FOLP/ex/nat.thy`
`     1 (*  Title:      FOLP/ex/nat.thy`
`     2     ID:         \$Id\$`
`     2     ID:         \$Id\$`
`     3     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory`
`     3     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory`
`     4     Copyright   1992  University of Cambridge`
`     4     Copyright   1992  University of Cambridge`
`     9 *)`
`     5 *)`
`    10 `
`     6 `
`    11 Nat = IFOLP +`
`     7 header {* Theory of the natural numbers: Peano's axioms, primitive recursion *}`
`    12 types   nat`
`     8 `
`    13 arities nat         :: term`
`     9 theory Nat`
`       `
`    10 imports FOLP`
`       `
`    11 begin`
`       `
`    12 `
`       `
`    13 typedecl nat`
`       `
`    14 arities nat         :: "term"`
`    14 consts  "0"         :: "nat"    ("0")`
`    15 consts  "0"         :: "nat"    ("0")`
`    15         Suc         :: "nat=>nat"`
`    16         Suc         :: "nat=>nat"`
`    16         rec         :: "[nat, 'a, [nat,'a]=>'a] => 'a"`
`    17         rec         :: "[nat, 'a, [nat,'a]=>'a] => 'a"`
`    17         "+"         :: "[nat, nat] => nat"              (infixl 60)`
`    18         "+"         :: "[nat, nat] => nat"              (infixl 60)`
`    18 `
`    19 `
`    19   (*Proof terms*)`
`    20   (*Proof terms*)`
`    20        nrec         :: "[nat,p,[nat,p]=>p]=>p"`
`    21        nrec         :: "[nat,p,[nat,p]=>p]=>p"`
`    21        ninj,nneq    :: "p=>p"`
`    22        ninj         :: "p=>p"`
`    22        rec0, recSuc :: "p"`
`    23        nneq         :: "p=>p"`
`       `
`    24        rec0         :: "p"`
`       `
`    25        recSuc       :: "p"`
`    23 `
`    26 `
`    24 rules   `
`    27 axioms`
`    25   induct     "[| b:P(0); !!x u. u:P(x) ==> c(x,u):P(Suc(x)) `
`    28   induct:     "[| b:P(0); !!x u. u:P(x) ==> c(x,u):P(Suc(x))`
`    26              |] ==> nrec(n,b,c):P(n)"`
`    29               |] ==> nrec(n,b,c):P(n)"`
`    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 `
`    30 `
`    34   nrecB0     "b: A ==> nrec(0,b,c) = b : A"`
`    31   Suc_inject: "p:Suc(m)=Suc(n) ==> ninj(p) : m=n"`
`    35   nrecBSuc   "c(n,nrec(n,b,c)) : A ==> nrec(Suc(n),b,c) = c(n,nrec(n,b,c)) : A"`
`    32   Suc_neq_0:  "p:Suc(m)=0      ==> nneq(p) : R"`
`       `
`    33   rec_0:      "rec0 : rec(0,a,f) = a"`
`       `
`    34   rec_Suc:    "recSuc : rec(Suc(m), a, f) = f(m, rec(m,a,f))"`
`       `
`    35   add_def:    "m+n == rec(m, n, %x y. Suc(y))"`
`       `
`    36 `
`       `
`    37   nrecB0:     "b: A ==> nrec(0,b,c) = b : A"`
`       `
`    38   nrecBSuc:   "c(n,nrec(n,b,c)) : A ==> nrec(Suc(n),b,c) = c(n,nrec(n,b,c)) : A"`
`       `
`    39 `
`       `
`    40 ML {* use_legacy_bindings (the_context ()) *}`
`       `
`    41 `
`    36 end`
`    42 end`