equal
deleted
inserted
replaced
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: |