doc-src/TutorialI/Types/document/Axioms.tex
changeset 10878 b254d5ad6dd4
parent 10845 3696bc935bbd
child 11196 bb4ede27fcb7
equal deleted inserted replaced
10877:6417de2029b0 10878:b254d5ad6dd4
    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