9767
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
9921
|
3 |
\def\isabellecontext{NatClass}%
|
8906
|
4 |
%
|
10395
|
5 |
\isamarkupheader{Defining natural numbers in FOL \label{sec:ex-natclass}%
|
|
6 |
}
|
11964
|
7 |
\isamarkuptrue%
|
|
8 |
\isacommand{theory}\ NatClass\ {\isacharequal}\ FOL{\isacharcolon}\isamarkupfalse%
|
|
9 |
%
|
8906
|
10 |
\begin{isamarkuptext}%
|
|
11 |
\medskip\noindent Axiomatic type classes abstract over exactly one
|
|
12 |
type argument. Thus, any \emph{axiomatic} theory extension where each
|
|
13 |
axiom refers to at most one type variable, may be trivially turned
|
|
14 |
into a \emph{definitional} one.
|
|
15 |
|
|
16 |
We illustrate this with the natural numbers in
|
|
17 |
Isabelle/FOL.\footnote{See also
|
|
18 |
\url{http://isabelle.in.tum.de/library/FOL/ex/NatClass.html}}%
|
|
19 |
\end{isamarkuptext}%
|
11964
|
20 |
\isamarkuptrue%
|
8890
|
21 |
\isacommand{consts}\isanewline
|
10140
|
22 |
\ \ zero\ {\isacharcolon}{\isacharcolon}\ {\isacharprime}a\ \ \ \ {\isacharparenleft}{\isachardoublequote}{\isasymzero}{\isachardoublequote}{\isacharparenright}\isanewline
|
9672
|
23 |
\ \ Suc\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\isanewline
|
|
24 |
\ \ rec\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharparenleft}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isacharparenright}\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\isanewline
|
8890
|
25 |
\isanewline
|
11964
|
26 |
\isamarkupfalse%
|
11099
|
27 |
\isacommand{axclass}\ nat\ {\isasymsubseteq}\ {\isachardoublequote}term{\isachardoublequote}\isanewline
|
10140
|
28 |
\ \ induct{\isacharcolon}\ {\isachardoublequote}P{\isacharparenleft}{\isasymzero}{\isacharparenright}\ {\isasymLongrightarrow}\ {\isacharparenleft}{\isasymAnd}x{\isachardot}\ P{\isacharparenleft}x{\isacharparenright}\ {\isasymLongrightarrow}\ P{\isacharparenleft}Suc{\isacharparenleft}x{\isacharparenright}{\isacharparenright}{\isacharparenright}\ {\isasymLongrightarrow}\ P{\isacharparenleft}n{\isacharparenright}{\isachardoublequote}\isanewline
|
9672
|
29 |
\ \ Suc{\isacharunderscore}inject{\isacharcolon}\ {\isachardoublequote}Suc{\isacharparenleft}m{\isacharparenright}\ {\isacharequal}\ Suc{\isacharparenleft}n{\isacharparenright}\ {\isasymLongrightarrow}\ m\ {\isacharequal}\ n{\isachardoublequote}\isanewline
|
10207
|
30 |
\ \ Suc{\isacharunderscore}neq{\isacharunderscore}{\isadigit{0}}{\isacharcolon}\ {\isachardoublequote}Suc{\isacharparenleft}m{\isacharparenright}\ {\isacharequal}\ {\isasymzero}\ {\isasymLongrightarrow}\ R{\isachardoublequote}\isanewline
|
|
31 |
\ \ rec{\isacharunderscore}{\isadigit{0}}{\isacharcolon}\ {\isachardoublequote}rec{\isacharparenleft}{\isasymzero}{\isacharcomma}\ a{\isacharcomma}\ f{\isacharparenright}\ {\isacharequal}\ a{\isachardoublequote}\isanewline
|
10140
|
32 |
\ \ rec{\isacharunderscore}Suc{\isacharcolon}\ {\isachardoublequote}rec{\isacharparenleft}Suc{\isacharparenleft}m{\isacharparenright}{\isacharcomma}\ a{\isacharcomma}\ f{\isacharparenright}\ {\isacharequal}\ f{\isacharparenleft}m{\isacharcomma}\ rec{\isacharparenleft}m{\isacharcomma}\ a{\isacharcomma}\ f{\isacharparenright}{\isacharparenright}{\isachardoublequote}\isanewline
|
8890
|
33 |
\isanewline
|
11964
|
34 |
\isamarkupfalse%
|
8890
|
35 |
\isacommand{constdefs}\isanewline
|
10207
|
36 |
\ \ add\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a{\isacharcolon}{\isacharcolon}nat\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\ \ \ \ {\isacharparenleft}\isakeyword{infixl}\ {\isachardoublequote}{\isacharplus}{\isachardoublequote}\ {\isadigit{6}}{\isadigit{0}}{\isacharparenright}\isanewline
|
11964
|
37 |
\ \ {\isachardoublequote}m\ {\isacharplus}\ n\ {\isasymequiv}\ rec{\isacharparenleft}m{\isacharcomma}\ n{\isacharcomma}\ {\isasymlambda}x\ y{\isachardot}\ Suc{\isacharparenleft}y{\isacharparenright}{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
38 |
%
|
8906
|
39 |
\begin{isamarkuptext}%
|
10140
|
40 |
This is an abstract version of the plain \isa{Nat} theory in
|
8906
|
41 |
FOL.\footnote{See
|
8907
|
42 |
\url{http://isabelle.in.tum.de/library/FOL/ex/Nat.html}} Basically,
|
10140
|
43 |
we have just replaced all occurrences of type \isa{nat} by \isa{{\isacharprime}a} and used the natural number axioms to define class \isa{nat}.
|
|
44 |
There is only a minor snag, that the original recursion operator
|
|
45 |
\isa{rec} had to be made monomorphic.
|
8906
|
46 |
|
10140
|
47 |
Thus class \isa{nat} contains exactly those types \isa{{\isasymtau}} that
|
|
48 |
are isomorphic to ``the'' natural numbers (with signature \isa{{\isasymzero}}, \isa{Suc}, \isa{rec}).
|
8906
|
49 |
|
|
50 |
\medskip What we have done here can be also viewed as \emph{type
|
|
51 |
specification}. Of course, it still remains open if there is some
|
|
52 |
type at all that meets the class axioms. Now a very nice property of
|
8907
|
53 |
axiomatic type classes is that abstract reasoning is always possible
|
8906
|
54 |
--- independent of satisfiability. The meta-logic won't break, even
|
8907
|
55 |
if some classes (or general sorts) turns out to be empty later ---
|
|
56 |
``inconsistent'' class definitions may be useless, but do not cause
|
|
57 |
any harm.
|
8906
|
58 |
|
|
59 |
Theorems of the abstract natural numbers may be derived in the same
|
|
60 |
way as for the concrete version. The original proof scripts may be
|
8907
|
61 |
re-used with some trivial changes only (mostly adding some type
|
8906
|
62 |
constraints).%
|
|
63 |
\end{isamarkuptext}%
|
11964
|
64 |
\isamarkuptrue%
|
|
65 |
\isacommand{end}\isamarkupfalse%
|
|
66 |
\end{isabellebody}%
|
9145
|
67 |
%%% Local Variables:
|
|
68 |
%%% mode: latex
|
|
69 |
%%% TeX-master: "root"
|
|
70 |
%%% End:
|