doc-src/TutorialI/Inductive/advanced-examples.tex
changeset 11421 364088045fa9
parent 11411 c315dda16748
child 12333 ef43a3d6e962
equal deleted inserted replaced
11420:9529d31f39e0 11421:364088045fa9
   146 
   146 
   147 We must cite the theorem \isa{lists_mono} in order to justify 
   147 We must cite the theorem \isa{lists_mono} in order to justify 
   148 using the function \isa{lists}. 
   148 using the function \isa{lists}. 
   149 \begin{isabelle}
   149 \begin{isabelle}
   150 A\ \isasymsubseteq\ B\ \isasymLongrightarrow \ lists\ A\ \isasymsubseteq
   150 A\ \isasymsubseteq\ B\ \isasymLongrightarrow \ lists\ A\ \isasymsubseteq
   151 \ lists\ B\rulename{lists_mono}
   151 \ lists\ B\rulenamedx{lists_mono}
   152 \end{isabelle}
   152 \end{isabelle}
   153 %
   153 %
   154 Why must the function be monotone?  An inductive definition describes
   154 Why must the function be monotone?  An inductive definition describes
   155 an iterative construction: each element of the set is constructed by a
   155 an iterative construction: each element of the set is constructed by a
   156 finite number of introduction rule applications.  For example, the
   156 finite number of introduction rule applications.  For example, the
   207 us an element of \isa{well_formed_gterm\ arity} on which to perform 
   207 us an element of \isa{well_formed_gterm\ arity} on which to perform 
   208 induction.  The resulting subgoal can be proved automatically:
   208 induction.  The resulting subgoal can be proved automatically:
   209 \begin{isabelle}
   209 \begin{isabelle}
   210 {\isadigit{1}}{\isachardot}\ {\isasymAnd}x\ args\ f{\isachardot}\isanewline
   210 {\isadigit{1}}{\isachardot}\ {\isasymAnd}x\ args\ f{\isachardot}\isanewline
   211 \ \ \ \ \ \ {\isasymlbrakk}{\isasymforall}t{\isasymin}set\ args{\isachardot}\isanewline
   211 \ \ \ \ \ \ {\isasymlbrakk}{\isasymforall}t{\isasymin}set\ args{\isachardot}\isanewline
   212 \ \ \ \ \ \ \ \ \ \ t\ {\isasymin}\ well{\isacharunderscore}formed{\isacharunderscore}gterm\ arity\ {\isasymand}\ t\ {\isasymin}\ well{\isacharunderscore}formed{\isacharunderscore}gterm{\isacharprime}\ arity{\isacharsemicolon}\isanewline
   212 \ \ \ \ \ \ \ \ \ \ t\ {\isasymin}\ well\_formed\_gterm\ arity\ {\isasymand}\ t\ {\isasymin}\ well\_formed\_gterm{\isacharprime}\ arity{\isacharsemicolon}\isanewline
   213 \ \ \ \ \ \ \ length\ args\ {\isacharequal}\ arity\ f{\isasymrbrakk}\isanewline
   213 \ \ \ \ \ \ \ length\ args\ {\isacharequal}\ arity\ f{\isasymrbrakk}\isanewline
   214 \ \ \ \ \ \ {\isasymLongrightarrow}\ Apply\ f\ args\ {\isasymin}\ well{\isacharunderscore}formed{\isacharunderscore}gterm{\isacharprime}\ arity%
   214 \ \ \ \ \ \ {\isasymLongrightarrow}\ Apply\ f\ args\ {\isasymin}\ well\_formed\_gterm{\isacharprime}\ arity%
   215 \end{isabelle}
   215 \end{isabelle}
   216 %
   216 %
   217 This proof resembles the one given in
   217 This proof resembles the one given in
   218 {\S}\ref{sec:gterm-datatype} above, especially in the form of the
   218 {\S}\ref{sec:gterm-datatype} above, especially in the form of the
   219 induction hypothesis.  Next, we consider the opposite inclusion:
   219 induction hypothesis.  Next, we consider the opposite inclusion: