|
0
|
1 |
(* Title: HOL/nat
|
|
|
2 |
ID: $Id$
|
|
|
3 |
Author: Tobias Nipkow, Cambridge University Computer Laboratory
|
|
|
4 |
Copyright 1991 University of Cambridge
|
|
|
5 |
|
|
|
6 |
Definition of types ind and nat.
|
|
|
7 |
|
|
|
8 |
Type nat is defined as a set Nat over type ind.
|
|
|
9 |
*)
|
|
|
10 |
|
|
|
11 |
Nat = WF +
|
|
51
|
12 |
|
|
|
13 |
types
|
|
|
14 |
ind
|
|
|
15 |
nat
|
|
|
16 |
|
|
|
17 |
arities
|
|
|
18 |
ind,nat :: term
|
|
|
19 |
nat :: ord
|
|
0
|
20 |
|
|
|
21 |
consts
|
|
|
22 |
Zero_Rep :: "ind"
|
|
|
23 |
Suc_Rep :: "ind => ind"
|
|
|
24 |
Nat :: "ind set"
|
|
|
25 |
Rep_Nat :: "nat => ind"
|
|
|
26 |
Abs_Nat :: "ind => nat"
|
|
|
27 |
Suc :: "nat => nat"
|
|
|
28 |
nat_case :: "[nat, 'a, nat=>'a] =>'a"
|
|
|
29 |
pred_nat :: "(nat*nat) set"
|
|
|
30 |
nat_rec :: "[nat, 'a, [nat, 'a]=>'a] => 'a"
|
|
|
31 |
"0" :: "nat" ("0")
|
|
|
32 |
|
|
|
33 |
rules
|
|
|
34 |
(*the axiom of infinity in 2 parts*)
|
|
|
35 |
inj_Suc_Rep "inj(Suc_Rep)"
|
|
|
36 |
Suc_Rep_not_Zero_Rep "~(Suc_Rep(x) = Zero_Rep)"
|
|
|
37 |
Nat_def "Nat == lfp(%X. {Zero_Rep} Un (Suc_Rep``X))"
|
|
|
38 |
(*faking a type definition...*)
|
|
|
39 |
Rep_Nat "Rep_Nat(n): Nat"
|
|
|
40 |
Rep_Nat_inverse "Abs_Nat(Rep_Nat(n)) = n"
|
|
|
41 |
Abs_Nat_inverse "i: Nat ==> Rep_Nat(Abs_Nat(i)) = i"
|
|
|
42 |
(*defining the abstract constants*)
|
|
|
43 |
Zero_def "0 == Abs_Nat(Zero_Rep)"
|
|
|
44 |
Suc_def "Suc == (%n. Abs_Nat(Suc_Rep(Rep_Nat(n))))"
|
|
|
45 |
(*nat operations and recursion*)
|
|
|
46 |
nat_case_def "nat_case == (%n a f. @z. (n=0 --> z=a) \
|
|
|
47 |
\ & (!x. n=Suc(x) --> z=f(x)))"
|
|
|
48 |
pred_nat_def "pred_nat == {p. ? n. p = <n, Suc(n)>}"
|
|
|
49 |
|
|
|
50 |
less_def "m<n == <m,n>:trancl(pred_nat)"
|
|
|
51 |
|
|
|
52 |
le_def "m<=n::nat == ~(n<m)"
|
|
|
53 |
|
|
|
54 |
nat_rec_def "nat_rec(n,c,d) == wfrec(pred_nat, n, \
|
|
|
55 |
\ %l g. nat_case(l, c, %m. d(m,g(m))))"
|
|
|
56 |
end
|