diff -r eacce1cd716a -r 05fc32a23b8b doc-src/TutorialI/Types/document/Axioms.tex --- a/doc-src/TutorialI/Types/document/Axioms.tex Tue Aug 16 13:42:21 2005 +0200 +++ b/doc-src/TutorialI/Types/document/Axioms.tex Tue Aug 16 13:42:23 2005 +0200 @@ -1,7 +1,20 @@ % \begin{isabellebody}% \def\isabellecontext{Axioms}% -\isamarkupfalse% +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory +\isamarkuptrue% % \isamarkupsubsection{Axioms% } @@ -23,12 +36,12 @@ A \emph{partial order} is a subclass of \isa{ordrel} where certain axioms need to hold:% \end{isamarkuptext}% -\isamarkuptrue% +\isamarkupfalse% \isacommand{axclass}\ parord\ {\isacharless}\ ordrel\isanewline refl{\isacharcolon}\ \ \ \ {\isachardoublequote}x\ {\isacharless}{\isacharless}{\isacharequal}\ x{\isachardoublequote}\isanewline trans{\isacharcolon}\ \ \ {\isachardoublequote}{\isasymlbrakk}\ x\ {\isacharless}{\isacharless}{\isacharequal}\ y{\isacharsemicolon}\ y\ {\isacharless}{\isacharless}{\isacharequal}\ z\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ x\ {\isacharless}{\isacharless}{\isacharequal}\ z{\isachardoublequote}\isanewline antisym{\isacharcolon}\ {\isachardoublequote}{\isasymlbrakk}\ x\ {\isacharless}{\isacharless}{\isacharequal}\ y{\isacharsemicolon}\ y\ {\isacharless}{\isacharless}{\isacharequal}\ x\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ x\ {\isacharequal}\ y{\isachardoublequote}\isanewline -less{\isacharunderscore}le{\isacharcolon}\ {\isachardoublequote}x\ {\isacharless}{\isacharless}\ y\ {\isacharequal}\ {\isacharparenleft}x\ {\isacharless}{\isacharless}{\isacharequal}\ y\ {\isasymand}\ x\ {\isasymnoteq}\ y{\isacharparenright}{\isachardoublequote}\isamarkupfalse% +less{\isacharunderscore}le{\isacharcolon}\ {\isachardoublequote}x\ {\isacharless}{\isacharless}\ y\ {\isacharequal}\ {\isacharparenleft}x\ {\isacharless}{\isacharless}{\isacharequal}\ y\ {\isasymand}\ x\ {\isasymnoteq}\ y{\isacharparenright}{\isachardoublequote}\isamarkuptrue% % \begin{isamarkuptext}% \noindent @@ -47,8 +60,14 @@ We can now prove simple theorems in this abstract setting, for example that \isa{{\isacharless}{\isacharless}} is not symmetric:% \end{isamarkuptext}% +\isamarkupfalse% +\isacommand{lemma}\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}x{\isacharcolon}{\isacharcolon}{\isacharprime}a{\isacharcolon}{\isacharcolon}parord{\isacharparenright}\ {\isacharless}{\isacharless}\ y\ {\isasymLongrightarrow}\ {\isacharparenleft}{\isasymnot}\ y\ {\isacharless}{\isacharless}\ x{\isacharparenright}\ {\isacharequal}\ True{\isachardoublequote}% +\isadelimproof +% +\endisadelimproof +% +\isatagproof \isamarkuptrue% -\isacommand{lemma}\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}x{\isacharcolon}{\isacharcolon}{\isacharprime}a{\isacharcolon}{\isacharcolon}parord{\isacharparenright}\ {\isacharless}{\isacharless}\ y\ {\isasymLongrightarrow}\ {\isacharparenleft}{\isasymnot}\ y\ {\isacharless}{\isacharless}\ x{\isacharparenright}\ {\isacharequal}\ True{\isachardoublequote}\isamarkupfalse% % \begin{isamarkuptxt}% \noindent @@ -63,8 +82,15 @@ \isa{{\isacharprime}a{\isacharcolon}{\isacharcolon}ordrel} (as required in the type of \isa{{\isacharless}{\isacharless}}), when the proposition is not a theorem. The proof is easy:% \end{isamarkuptxt}% +\isamarkupfalse% +\isacommand{by}{\isacharparenleft}simp\ add{\isacharcolon}\ less{\isacharunderscore}le\ antisym{\isacharparenright}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof \isamarkuptrue% -\isacommand{by}{\isacharparenleft}simp\ add{\isacharcolon}\ less{\isacharunderscore}le\ antisym{\isacharparenright}\isamarkupfalse% % \begin{isamarkuptext}% We could now continue in this vein and develop a whole theory of @@ -73,10 +99,16 @@ prove that the types in question, for example \isa{bool}, are indeed instances of \isa{parord}:% \end{isamarkuptext}% -\isamarkuptrue% +\isamarkupfalse% \isacommand{instance}\ bool\ {\isacharcolon}{\isacharcolon}\ parord\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof \isamarkupfalse% -\isacommand{apply}\ intro{\isacharunderscore}classes\isamarkupfalse% +\isacommand{apply}\ intro{\isacharunderscore}classes\isamarkuptrue% % \begin{isamarkuptxt}% \noindent @@ -92,10 +124,17 @@ once we have unfolded the definitions of \isa{{\isacharless}{\isacharless}} and \isa{{\isacharless}{\isacharless}{\isacharequal}} at type \isa{bool}:% \end{isamarkuptxt}% -\isamarkuptrue% +\isamarkupfalse% \isacommand{apply}{\isacharparenleft}simp{\isacharunderscore}all\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharunderscore}use{\isacharparenright}\ only{\isacharcolon}\ le{\isacharunderscore}bool{\isacharunderscore}def\ less{\isacharunderscore}bool{\isacharunderscore}def{\isacharparenright}\isanewline \isamarkupfalse% -\isacommand{by}{\isacharparenleft}blast{\isacharcomma}\ blast{\isacharcomma}\ blast{\isacharcomma}\ blast{\isacharparenright}\isamarkupfalse% +\isacommand{by}{\isacharparenleft}blast{\isacharcomma}\ blast{\isacharcomma}\ blast{\isacharcomma}\ blast{\isacharparenright}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isamarkuptrue% % \begin{isamarkuptext}% \noindent @@ -103,10 +142,23 @@ We can now apply our single lemma above in the context of booleans:% \end{isamarkuptext}% -\isamarkuptrue% +\isamarkupfalse% \isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}P{\isacharcolon}{\isacharcolon}bool{\isacharparenright}\ {\isacharless}{\isacharless}\ Q\ {\isasymLongrightarrow}\ {\isasymnot}{\isacharparenleft}Q\ {\isacharless}{\isacharless}\ P{\isacharparenright}{\isachardoublequote}\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof \isamarkupfalse% -\isacommand{by}\ simp\isamarkupfalse% +\isacommand{by}\ simp% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isamarkuptrue% % \begin{isamarkuptext}% \noindent @@ -125,9 +177,9 @@ If any two elements of a partial order are comparable it is a \textbf{linear} or \textbf{total} order:% \end{isamarkuptext}% -\isamarkuptrue% +\isamarkupfalse% \isacommand{axclass}\ linord\ {\isacharless}\ parord\isanewline -linear{\isacharcolon}\ {\isachardoublequote}x\ {\isacharless}{\isacharless}{\isacharequal}\ y\ {\isasymor}\ y\ {\isacharless}{\isacharless}{\isacharequal}\ x{\isachardoublequote}\isamarkupfalse% +linear{\isacharcolon}\ {\isachardoublequote}x\ {\isacharless}{\isacharless}{\isacharequal}\ y\ {\isasymor}\ y\ {\isacharless}{\isacharless}{\isacharequal}\ x{\isachardoublequote}\isamarkuptrue% % \begin{isamarkuptext}% \noindent @@ -135,8 +187,14 @@ Therefore we can show that linearity can be expressed in terms of \isa{{\isacharless}{\isacharless}} as follows:% \end{isamarkuptext}% -\isamarkuptrue% +\isamarkupfalse% \isacommand{lemma}\ {\isachardoublequote}{\isasymAnd}x{\isacharcolon}{\isacharcolon}{\isacharprime}a{\isacharcolon}{\isacharcolon}linord{\isachardot}\ x\ {\isacharless}{\isacharless}\ y\ {\isasymor}\ x\ {\isacharequal}\ y\ {\isasymor}\ y\ {\isacharless}{\isacharless}\ x{\isachardoublequote}\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof \isamarkupfalse% \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ less{\isacharunderscore}le{\isacharparenright}\isanewline \isamarkupfalse% @@ -144,7 +202,14 @@ \isamarkupfalse% \isacommand{apply}\ blast\isanewline \isamarkupfalse% -\isacommand{done}\isamarkupfalse% +\isacommand{done}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isamarkuptrue% % \begin{isamarkuptext}% Linear orders are an example of subclassing\index{subclasses} @@ -163,11 +228,11 @@ An alternative axiomatization of partial orders takes \isa{{\isacharless}{\isacharless}} rather than \isa{{\isacharless}{\isacharless}{\isacharequal}} as the primary concept. The result is a \textbf{strict} order:% \end{isamarkuptext}% -\isamarkuptrue% +\isamarkupfalse% \isacommand{axclass}\ strord\ {\isacharless}\ ordrel\isanewline irrefl{\isacharcolon}\ \ \ \ \ {\isachardoublequote}{\isasymnot}\ x\ {\isacharless}{\isacharless}\ x{\isachardoublequote}\isanewline less{\isacharunderscore}trans{\isacharcolon}\ {\isachardoublequote}{\isasymlbrakk}\ x\ {\isacharless}{\isacharless}\ y{\isacharsemicolon}\ y\ {\isacharless}{\isacharless}\ z\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ x\ {\isacharless}{\isacharless}\ z{\isachardoublequote}\isanewline -le{\isacharunderscore}less{\isacharcolon}\ \ \ \ {\isachardoublequote}x\ {\isacharless}{\isacharless}{\isacharequal}\ y\ {\isacharequal}\ {\isacharparenleft}x\ {\isacharless}{\isacharless}\ y\ {\isasymor}\ x\ {\isacharequal}\ y{\isacharparenright}{\isachardoublequote}\isamarkupfalse% +le{\isacharunderscore}less{\isacharcolon}\ \ \ \ {\isachardoublequote}x\ {\isacharless}{\isacharless}{\isacharequal}\ y\ {\isacharequal}\ {\isacharparenleft}x\ {\isacharless}{\isacharless}\ y\ {\isasymor}\ x\ {\isacharequal}\ y{\isacharparenright}{\isachardoublequote}\isamarkuptrue% % \begin{isamarkuptext}% \noindent @@ -175,10 +240,16 @@ prove one direction, namely that partial orders are a subclass of strict orders.% \end{isamarkuptext}% -\isamarkuptrue% +\isamarkupfalse% \isacommand{instance}\ parord\ {\isacharless}\ strord\isanewline +% +\isadelimproof +% +\endisadelimproof +% +\isatagproof \isamarkupfalse% -\isacommand{apply}\ intro{\isacharunderscore}classes\isamarkupfalse% +\isacommand{apply}\ intro{\isacharunderscore}classes\isamarkuptrue% % \begin{isamarkuptxt}% \noindent @@ -192,14 +263,21 @@ Assuming \isa{{\isacharprime}a\ {\isacharcolon}{\isacharcolon}\ parord}, the three axioms of class \isa{strord} are easily proved:% \end{isamarkuptxt}% -\ \ \isamarkuptrue% +\ \ \isamarkupfalse% \isacommand{apply}{\isacharparenleft}simp{\isacharunderscore}all\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharunderscore}use{\isacharparenright}\ add{\isacharcolon}\ less{\isacharunderscore}le{\isacharparenright}\isanewline \ \isamarkupfalse% \isacommand{apply}{\isacharparenleft}blast\ intro{\isacharcolon}\ trans\ antisym{\isacharparenright}\isanewline \isamarkupfalse% \isacommand{apply}{\isacharparenleft}blast\ intro{\isacharcolon}\ refl{\isacharparenright}\isanewline \isamarkupfalse% -\isacommand{done}\isamarkupfalse% +\isacommand{done}% +\endisatagproof +{\isafoldproof}% +% +\isadelimproof +% +\endisadelimproof +\isamarkuptrue% % \begin{isamarkuptext}% The subclass relation must always be acyclic. Therefore Isabelle will @@ -216,12 +294,12 @@ \bfindex{multiple inheritance}. For example, we could define the classes of well-founded orderings and well-orderings:% \end{isamarkuptext}% -\isamarkuptrue% +\isamarkupfalse% \isacommand{axclass}\ wford\ {\isacharless}\ parord\isanewline wford{\isacharcolon}\ {\isachardoublequote}wf\ {\isacharbraceleft}{\isacharparenleft}y{\isacharcomma}x{\isacharparenright}{\isachardot}\ y\ {\isacharless}{\isacharless}\ x{\isacharbraceright}{\isachardoublequote}\isanewline \isanewline \isamarkupfalse% -\isacommand{axclass}\ wellord\ {\isacharless}\ linord{\isacharcomma}\ wford\isamarkupfalse% +\isacommand{axclass}\ wellord\ {\isacharless}\ linord{\isacharcomma}\ wford\isamarkuptrue% % \begin{isamarkuptext}% \noindent @@ -289,8 +367,19 @@ classes readily become inconsistent in practice. Now we know this need not worry us.% \end{isamarkuptext}% -\isamarkuptrue% -\isamarkupfalse% +% +\isadelimtheory +% +\endisadelimtheory +% +\isatagtheory +% +\endisatagtheory +{\isafoldtheory}% +% +\isadelimtheory +% +\endisadelimtheory \end{isabellebody}% %%% Local Variables: %%% mode: latex