1 |
1 |
2 header {* Defining natural numbers in FOL \label{sec:ex-natclass} *}; |
2 header {* Defining natural numbers in FOL \label{sec:ex-natclass} *} |
3 |
3 |
4 theory NatClass = FOL:; |
4 theory NatClass = FOL: |
5 |
5 |
6 text {* |
6 text {* |
7 \medskip\noindent Axiomatic type classes abstract over exactly one |
7 \medskip\noindent Axiomatic type classes abstract over exactly one |
8 type argument. Thus, any \emph{axiomatic} theory extension where each |
8 type argument. Thus, any \emph{axiomatic} theory extension where each |
9 axiom refers to at most one type variable, may be trivially turned |
9 axiom refers to at most one type variable, may be trivially turned |
10 into a \emph{definitional} one. |
10 into a \emph{definitional} one. |
11 |
11 |
12 We illustrate this with the natural numbers in |
12 We illustrate this with the natural numbers in |
13 Isabelle/FOL.\footnote{See also |
13 Isabelle/FOL.\footnote{See also |
14 \url{http://isabelle.in.tum.de/library/FOL/ex/NatClass.html}} |
14 \url{http://isabelle.in.tum.de/library/FOL/ex/NatClass.html}} |
15 *}; |
15 *} |
16 |
16 |
17 consts |
17 consts |
18 zero :: 'a ("0") |
18 zero :: 'a ("0") |
19 Suc :: "'a \\<Rightarrow> 'a" |
19 Suc :: "'a \\<Rightarrow> 'a" |
20 rec :: "'a \\<Rightarrow> 'a \\<Rightarrow> ('a \\<Rightarrow> 'a \\<Rightarrow> 'a) \\<Rightarrow> 'a"; |
20 rec :: "'a \\<Rightarrow> 'a \\<Rightarrow> ('a \\<Rightarrow> 'a \\<Rightarrow> 'a) \\<Rightarrow> 'a" |
21 |
21 |
22 axclass |
22 axclass |
23 nat < "term" |
23 nat < "term" |
24 induct: "P(0) \\<Longrightarrow> (\\<And>x. P(x) \\<Longrightarrow> P(Suc(x))) \\<Longrightarrow> P(n)" |
24 induct: "P(0) \\<Longrightarrow> (\\<And>x. P(x) \\<Longrightarrow> P(Suc(x))) \\<Longrightarrow> P(n)" |
25 Suc_inject: "Suc(m) = Suc(n) \\<Longrightarrow> m = n" |
25 Suc_inject: "Suc(m) = Suc(n) \\<Longrightarrow> m = n" |
26 Suc_neq_0: "Suc(m) = 0 \\<Longrightarrow> R" |
26 Suc_neq_0: "Suc(m) = 0 \\<Longrightarrow> R" |
27 rec_0: "rec(0, a, f) = a" |
27 rec_0: "rec(0, a, f) = a" |
28 rec_Suc: "rec(Suc(m), a, f) = f(m, rec(m, a, f))"; |
28 rec_Suc: "rec(Suc(m), a, f) = f(m, rec(m, a, f))" |
29 |
29 |
30 constdefs |
30 constdefs |
31 add :: "'a::nat \\<Rightarrow> 'a \\<Rightarrow> 'a" (infixl "+" 60) |
31 add :: "'a::nat \\<Rightarrow> 'a \\<Rightarrow> 'a" (infixl "+" 60) |
32 "m + n \\<equiv> rec(m, n, \\<lambda>x y. Suc(y))"; |
32 "m + n \\<equiv> rec(m, n, \\<lambda>x y. Suc(y))" |
33 |
33 |
34 text {* |
34 text {* |
35 This is an abstract version of the plain $Nat$ theory in |
35 This is an abstract version of the plain $Nat$ theory in |
36 FOL.\footnote{See |
36 FOL.\footnote{See |
37 \url{http://isabelle.in.tum.de/library/FOL/ex/Nat.html}} Basically, |
37 \url{http://isabelle.in.tum.de/library/FOL/ex/Nat.html}} Basically, |