10 level of classes and the results will be applicable to all types in a class, |
10 level of classes and the results will be applicable to all types in a class, |
11 just as in axiomatic mathematics. These ideas are demonstrated by means of |
11 just as in axiomatic mathematics. These ideas are demonstrated by means of |
12 our above ordering relations.% |
12 our above ordering relations.% |
13 \end{isamarkuptext}% |
13 \end{isamarkuptext}% |
14 % |
14 % |
15 \isamarkupsubsubsection{Partial orders% |
15 \isamarkupsubsubsection{Partial Orders% |
16 } |
16 } |
17 % |
17 % |
18 \begin{isamarkuptext}% |
18 \begin{isamarkuptext}% |
19 A \emph{partial order} is a subclass of \isa{ordrel} |
19 A \emph{partial order} is a subclass of \isa{ordrel} |
20 where certain axioms need to hold:% |
20 where certain axioms need to hold:% |
28 \noindent |
28 \noindent |
29 The first three axioms are the familiar ones, and the final one |
29 The first three axioms are the familiar ones, and the final one |
30 requires that \isa{{\isacharless}{\isacharless}} and \isa{{\isacharless}{\isacharless}{\isacharequal}} are related as expected. |
30 requires that \isa{{\isacharless}{\isacharless}} and \isa{{\isacharless}{\isacharless}{\isacharequal}} are related as expected. |
31 Note that behind the scenes, Isabelle has restricted the axioms to class |
31 Note that behind the scenes, Isabelle has restricted the axioms to class |
32 \isa{parord}. For example, this is what \isa{refl} really looks like: |
32 \isa{parord}. For example, this is what \isa{refl} really looks like: |
33 \isa{{\isacharparenleft}{\isacharquery}x{\isasymColon}{\isacharquery}{\isacharprime}a{\isacharparenright}\ {\isacharless}{\isacharless}{\isacharequal}\ {\isacharquery}x}. |
33 \isa{{\isacharparenleft}{\isacharquery}x{\isasymColon}{\isacharquery}{\isacharprime}a{\isasymColon}parord{\isacharparenright}\ {\isacharless}{\isacharless}{\isacharequal}\ {\isacharquery}x}. |
34 |
34 |
35 We have not made \isa{less{\isacharunderscore}le} a global definition because it would |
35 We have not made \isa{less{\isacharunderscore}le} a global definition because it would |
36 fix once and for all that \isa{{\isacharless}{\isacharless}} is defined in terms of \isa{{\isacharless}{\isacharless}{\isacharequal}}. |
36 fix once and for all that \isa{{\isacharless}{\isacharless}} is defined in terms of \isa{{\isacharless}{\isacharless}{\isacharequal}}. |
37 There are however situations where it is the other way around, which such a |
37 There are however situations where it is the other way around, which such a |
38 definition would complicate. The slight drawback of the above class is that |
38 definition would complicate. The slight drawback of the above class is that |
86 \end{isamarkuptext}% |
86 \end{isamarkuptext}% |
87 \isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}P{\isacharcolon}{\isacharcolon}bool{\isacharparenright}\ {\isacharless}{\isacharless}\ Q\ {\isasymLongrightarrow}\ {\isasymnot}{\isacharparenleft}Q\ {\isacharless}{\isacharless}\ P{\isacharparenright}{\isachardoublequote}\isanewline |
87 \isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}P{\isacharcolon}{\isacharcolon}bool{\isacharparenright}\ {\isacharless}{\isacharless}\ Q\ {\isasymLongrightarrow}\ {\isasymnot}{\isacharparenleft}Q\ {\isacharless}{\isacharless}\ P{\isacharparenright}{\isachardoublequote}\isanewline |
88 \isacommand{by}\ simp% |
88 \isacommand{by}\ simp% |
89 \begin{isamarkuptext}% |
89 \begin{isamarkuptext}% |
90 \noindent |
90 \noindent |
91 The effect is not stunning but demonstrates the principle. It also shows |
91 The effect is not stunning, but it demonstrates the principle. It also shows |
92 that tools like the simplifier can deal with generic rules as well. Moreover, |
92 that tools like the simplifier can deal with generic rules as well. Moreover, |
93 it should be clear that the main advantage of the axiomatic method is that |
93 it should be clear that the main advantage of the axiomatic method is that |
94 theorems can be proved in the abstract and one does not need to repeat the |
94 theorems can be proved in the abstract and one does not need to repeat the |
95 proof for each instance.% |
95 proof for each instance.% |
96 \end{isamarkuptext}% |
96 \end{isamarkuptext}% |
97 % |
97 % |
98 \isamarkupsubsubsection{Linear orders% |
98 \isamarkupsubsubsection{Linear Orders% |
99 } |
99 } |
100 % |
100 % |
101 \begin{isamarkuptext}% |
101 \begin{isamarkuptext}% |
102 If any two elements of a partial order are comparable it is a |
102 If any two elements of a partial order are comparable it is a |
103 \emph{linear} or \emph{total} order:% |
103 \emph{linear} or \emph{total} order:% |
120 common case. It is also possible to prove additional subclass relationships |
120 common case. It is also possible to prove additional subclass relationships |
121 later on, i.e.\ subclassing by proof. This is the topic of the following |
121 later on, i.e.\ subclassing by proof. This is the topic of the following |
122 paragraph.% |
122 paragraph.% |
123 \end{isamarkuptext}% |
123 \end{isamarkuptext}% |
124 % |
124 % |
125 \isamarkupsubsubsection{Strict orders% |
125 \isamarkupsubsubsection{Strict Orders% |
126 } |
126 } |
127 % |
127 % |
128 \begin{isamarkuptext}% |
128 \begin{isamarkuptext}% |
129 An alternative axiomatization of partial orders takes \isa{{\isacharless}{\isacharless}} rather than |
129 An alternative axiomatization of partial orders takes \isa{{\isacharless}{\isacharless}} rather than |
130 \isa{{\isacharless}{\isacharless}{\isacharequal}} as the primary concept. The result is a \emph{strict} order:% |
130 \isa{{\isacharless}{\isacharless}{\isacharequal}} as the primary concept. The result is a \emph{strict} order:% |
148 \begin{isamarkuptext}% |
148 \begin{isamarkuptext}% |
149 The subclass relation must always be acyclic. Therefore Isabelle will |
149 The subclass relation must always be acyclic. Therefore Isabelle will |
150 complain if you also prove the relationship \isa{strord\ {\isacharless}\ parord}.% |
150 complain if you also prove the relationship \isa{strord\ {\isacharless}\ parord}.% |
151 \end{isamarkuptext}% |
151 \end{isamarkuptext}% |
152 % |
152 % |
153 \isamarkupsubsubsection{Multiple inheritance and sorts% |
153 \isamarkupsubsubsection{Multiple Inheritance and Sorts% |
154 } |
154 } |
155 % |
155 % |
156 \begin{isamarkuptext}% |
156 \begin{isamarkuptext}% |
157 A class may inherit from more than one direct superclass. This is called |
157 A class may inherit from more than one direct superclass. This is called |
158 multiple inheritance and is certainly permitted. For example we could define |
158 multiple inheritance and is certainly permitted. For example we could define |
182 \isa{linord} & & & & \isa{wford} \\ |
182 \isa{linord} & & & & \isa{wford} \\ |
183 & \backslash & & / \\ |
183 & \backslash & & / \\ |
184 & & \isa{wellord} |
184 & & \isa{wellord} |
185 \end{array} |
185 \end{array} |
186 \] |
186 \] |
187 \caption{Subclass diagramm} |
187 \caption{Subclass Diagram} |
188 \label{fig:subclass} |
188 \label{fig:subclass} |
189 \end{figure} |
189 \end{figure} |
190 |
190 |
191 Since class \isa{wellord} does not introduce any new axioms, it can simply |
191 Since class \isa{wellord} does not introduce any new axioms, it can simply |
192 be viewed as the intersection of the two classes \isa{linord} and \isa{wford}. Such intersections need not be given a new name but can be created on |
192 be viewed as the intersection of the two classes \isa{linord} and \isa{wford}. Such intersections need not be given a new name but can be created on |