10 Proof commands perform transitions of Isar/VM machine
11 configurations, which are block-structured, consisting of a stack of
12 nodes with three main components: logical proof context, current
13 facts, and open goals. Isar/VM transitions are \emph{typed}
14 according to the following three different modes of operation:
18 \item @{text "proof(prove)"} means that a new goal has just been
19 stated that is now to be \emph{proven}; the next command may refine
20 it by some proof method, and enter a sub-proof to establish the
23 \item @{text "proof(state)"} is like a nested theory mode: the
24 context may be augmented by \emph{stating} additional assumptions,
25 intermediate results etc.
27 \item @{text "proof(chain)"} is intermediate between @{text
28 "proof(state)"} and @{text "proof(prove)"}: existing facts (i.e.\
29 the contents of the special ``@{fact_ref this}'' register) have been
30 just picked up in order to be used when refining the goal claimed
35 The proof mode indicator may be read as a verb telling the writer
36 what kind of operation may be performed next. The corresponding
37 typings of proof commands restricts the shape of well-formed proof
38 texts to particular command sequences. So dynamic arrangements of
39 commands eventually turn out as static texts of a certain structure.
40 \Appref{ap:refcard} gives a simplified grammar of the overall
41 (extensible) language emerging that way.
45 section {* Proof structure *}
47 subsection {* Blocks *}
50 \begin{matharray}{rcl}
51 @{command_def "next"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
52 @{command_def "{"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
53 @{command_def "}"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
56 While Isar is inherently block-structured, opening and closing
57 blocks is mostly handled rather casually, with little explicit
58 user-intervention. Any local goal statement automatically opens
59 \emph{two} internal blocks, which are closed again when concluding
60 the sub-proof (by @{command "qed"} etc.). Sections of different
61 context within a sub-proof may be switched via @{command "next"},
62 which is just a single block-close followed by block-open again.
63 The effect of @{command "next"} is to reset the local proof context;
64 there is no goal focus involved here!
66 For slightly more advanced applications, there are explicit block
67 parentheses as well. These typically achieve a stronger forward
72 \item @{command "next"} switches to a fresh block within a
73 sub-proof, resetting the local context to the initial one.
75 \item @{command "{"} and @{command "}"} explicitly open and close
76 blocks. Any current facts pass through ``@{command "{"}''
77 unchanged, while ``@{command "}"}'' causes any result to be
78 \emph{exported} into the enclosing context. Thus fixed variables
79 are generalized, assumptions discharged, and local definitions
80 unfolded (cf.\ \secref{sec:proof-context}). There is no difference
81 of @{command "assume"} and @{command "presume"} in this mode of
82 forward reasoning --- in contrast to plain backward reasoning with
83 the result exported at @{command "show"} time.
89 subsection {* Omitting proofs *}
92 \begin{matharray}{rcl}
93 @{command_def "oops"} & : & @{text "proof \<rightarrow> local_theory | theory"} \\
96 The @{command "oops"} command discontinues the current proof
97 attempt, while considering the partial proof text as properly
98 processed. This is conceptually quite different from ``faking''
99 actual proofs via @{command_ref "sorry"} (see
100 \secref{sec:proof-steps}): @{command "oops"} does not observe the
101 proof structure at all, but goes back right to the theory level.
102 Furthermore, @{command "oops"} does not produce any result theorem
103 --- there is no intended claim to be able to complete the proof
106 A typical application of @{command "oops"} is to explain Isar proofs
107 \emph{within} the system itself, in conjunction with the document
108 preparation tools of Isabelle described in \chref{ch:document-prep}.
109 Thus partial or even wrong proof attempts can be discussed in a
110 logically sound manner. Note that the Isabelle {\LaTeX} macros can
111 be easily adapted to print something like ``@{text "\<dots>"}'' instead of
112 the keyword ``@{command "oops"}''.
114 \medskip The @{command "oops"} command is undo-able, unlike
115 @{command_ref "kill"} (see \secref{sec:history}). The effect is to
116 get back to the theory just before the opening of the proof.
120 section {* Statements *}
122 subsection {* Context elements \label{sec:proof-context} *}
125 \begin{matharray}{rcl}
126 @{command_def "fix"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
127 @{command_def "assume"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
128 @{command_def "presume"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
129 @{command_def "def"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
132 The logical proof context consists of fixed variables and
133 assumptions. The former closely correspond to Skolem constants, or
134 meta-level universal quantification as provided by the Isabelle/Pure
135 logical framework. Introducing some \emph{arbitrary, but fixed}
136 variable via ``@{command "fix"}~@{text x}'' results in a local value
137 that may be used in the subsequent proof as any other variable or
138 constant. Furthermore, any result @{text "\<turnstile> \<phi>[x]"} exported from
139 the context will be universally closed wrt.\ @{text x} at the
140 outermost level: @{text "\<turnstile> \<And>x. \<phi>[x]"} (this is expressed in normal
141 form using Isabelle's meta-variables).
143 Similarly, introducing some assumption @{text \<chi>} has two effects.
144 On the one hand, a local theorem is created that may be used as a
145 fact in subsequent proof steps. On the other hand, any result
146 @{text "\<chi> \<turnstile> \<phi>"} exported from the context becomes conditional wrt.\
147 the assumption: @{text "\<turnstile> \<chi> \<Longrightarrow> \<phi>"}. Thus, solving an enclosing goal
148 using such a result would basically introduce a new subgoal stemming
149 from the assumption. How this situation is handled depends on the
150 version of assumption command used: while @{command "assume"}
151 insists on solving the subgoal by unification with some premise of
152 the goal, @{command "presume"} leaves the subgoal unchanged in order
153 to be proved later by the user.
155 Local definitions, introduced by ``@{command "def"}~@{text "x \<equiv>
156 t"}'', are achieved by combining ``@{command "fix"}~@{text x}'' with
157 another version of assumption that causes any hypothetical equation
158 @{text "x \<equiv> t"} to be eliminated by the reflexivity rule. Thus,
159 exporting some result @{text "x \<equiv> t \<turnstile> \<phi>[x]"} yields @{text "\<turnstile>
165 ('assume' | 'presume') (props + 'and')
169 def: thmdecl? \\ name ('==' | equiv) term termpat?
175 \item @{command "fix"}~@{text x} introduces a local variable @{text
176 x} that is \emph{arbitrary, but fixed.}
178 \item @{command "assume"}~@{text "a: \<phi>"} and @{command
179 "presume"}~@{text "a: \<phi>"} introduce a local fact @{text "\<phi> \<turnstile> \<phi>"} by
180 assumption. Subsequent results applied to an enclosing goal (e.g.\
181 by @{command_ref "show"}) are handled as follows: @{command
182 "assume"} expects to be able to unify with existing premises in the
183 goal, while @{command "presume"} leaves @{text \<phi>} as new subgoals.
185 Several lists of assumptions may be given (separated by
186 @{keyword_ref "and"}; the resulting list of current facts consists
187 of all of these concatenated.
189 \item @{command "def"}~@{text "x \<equiv> t"} introduces a local
190 (non-polymorphic) definition. In results exported from the context,
191 @{text x} is replaced by @{text t}. Basically, ``@{command
192 "def"}~@{text "x \<equiv> t"}'' abbreviates ``@{command "fix"}~@{text
193 x}~@{command "assume"}~@{text "x \<equiv> t"}'', with the resulting
194 hypothetical equation solved by reflexivity.
196 The default name for the definitional equation is @{text x_def}.
197 Several simultaneous definitions may be given at the same time.
201 The special name @{fact_ref prems} refers to all assumptions of the
202 current context as a list of theorems. This feature should be used
203 with great care! It is better avoided in final proof texts.
207 subsection {* Term abbreviations \label{sec:term-abbrev} *}
210 \begin{matharray}{rcl}
211 @{command_def "let"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
212 @{keyword_def "is"} & : & syntax \\
215 Abbreviations may be either bound by explicit @{command
216 "let"}~@{text "p \<equiv> t"} statements, or by annotating assumptions or
217 goal statements with a list of patterns ``@{text "(\<IS> p\<^sub>1 \<dots>
218 p\<^sub>n)"}''. In both cases, higher-order matching is invoked to
219 bind extra-logical term variables, which may be either named
220 schematic variables of the form @{text ?x}, or nameless dummies
221 ``@{variable _}'' (underscore). Note that in the @{command "let"}
222 form the patterns occur on the left-hand side, while the @{keyword
223 "is"} patterns are in postfix position.
225 Polymorphism of term bindings is handled in Hindley-Milner style,
226 similar to ML. Type variables referring to local assumptions or
227 open goal statements are \emph{fixed}, while those of finished
228 results or bound by @{command "let"} may occur in \emph{arbitrary}
229 instances later. Even though actual polymorphism should be rarely
230 used in practice, this mechanism is essential to achieve proper
231 incremental type-inference, as the user proceeds to build up the
232 Isar proof text from left to right.
234 \medskip Term abbreviations are quite different from local
235 definitions as introduced via @{command "def"} (see
236 \secref{sec:proof-context}). The latter are visible within the
237 logic as actual equations, while abbreviations disappear during the
238 input process just after type checking. Also note that @{command
239 "def"} does not support polymorphism.
242 'let' ((term + 'and') '=' term + 'and')
246 The syntax of @{keyword "is"} patterns follows \railnonterm{termpat}
247 or \railnonterm{proppat} (see \secref{sec:term-decls}).
251 \item @{command "let"}~@{text "p\<^sub>1 = t\<^sub>1 \<AND> \<dots> p\<^sub>n = t\<^sub>n"} binds any
252 text variables in patterns @{text "p\<^sub>1, \<dots>, p\<^sub>n"} by simultaneous
253 higher-order matching against terms @{text "t\<^sub>1, \<dots>, t\<^sub>n"}.
255 \item @{text "(\<IS> p\<^sub>1 \<dots> p\<^sub>n)"} resembles @{command "let"}, but
256 matches @{text "p\<^sub>1, \<dots>, p\<^sub>n"} against the preceding statement. Also
257 note that @{keyword "is"} is not a separate command, but part of
258 others (such as @{command "assume"}, @{command "have"} etc.).
262 Some \emph{implicit} term abbreviations\index{term abbreviations}
263 for goals and facts are available as well. For any open goal,
264 @{variable_ref thesis} refers to its object-level statement,
265 abstracted over any meta-level parameters (if present). Likewise,
266 @{variable_ref this} is bound for fact statements resulting from
267 assumptions or finished goals. In case @{variable this} refers to
268 an object-logic statement that is an application @{text "f t"}, then
269 @{text t} is bound to the special text variable ``@{variable "\<dots>"}''
270 (three dots). The canonical application of this convenience are
271 calculational proofs (see \secref{sec:calculation}).
275 subsection {* Facts and forward chaining *}
278 \begin{matharray}{rcl}
279 @{command_def "note"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
280 @{command_def "then"} & : & @{text "proof(state) \<rightarrow> proof(chain)"} \\
281 @{command_def "from"} & : & @{text "proof(state) \<rightarrow> proof(chain)"} \\
282 @{command_def "with"} & : & @{text "proof(state) \<rightarrow> proof(chain)"} \\
283 @{command_def "using"} & : & @{text "proof(prove) \<rightarrow> proof(prove)"} \\
284 @{command_def "unfolding"} & : & @{text "proof(prove) \<rightarrow> proof(prove)"} \\
287 New facts are established either by assumption or proof of local
288 statements. Any fact will usually be involved in further proofs,
289 either as explicit arguments of proof methods, or when forward
290 chaining towards the next goal via @{command "then"} (and variants);
291 @{command "from"} and @{command "with"} are composite forms
292 involving @{command "note"}. The @{command "using"} elements
293 augments the collection of used facts \emph{after} a goal has been
294 stated. Note that the special theorem name @{fact_ref this} refers
295 to the most recently established facts, but only \emph{before}
296 issuing a follow-up claim.
299 'note' (thmdef? thmrefs + 'and')
301 ('from' | 'with' | 'using' | 'unfolding') (thmrefs + 'and')
307 \item @{command "note"}~@{text "a = b\<^sub>1 \<dots> b\<^sub>n"} recalls existing facts
308 @{text "b\<^sub>1, \<dots>, b\<^sub>n"}, binding the result as @{text a}. Note that
309 attributes may be involved as well, both on the left and right hand
312 \item @{command "then"} indicates forward chaining by the current
313 facts in order to establish the goal to be claimed next. The
314 initial proof method invoked to refine that will be offered the
315 facts to do ``anything appropriate'' (see also
316 \secref{sec:proof-steps}). For example, method @{method_ref rule}
317 (see \secref{sec:pure-meth-att}) would typically do an elimination
318 rather than an introduction. Automatic methods usually insert the
319 facts into the goal state before operation. This provides a simple
320 scheme to control relevance of facts in automated proof search.
322 \item @{command "from"}~@{text b} abbreviates ``@{command
323 "note"}~@{text b}~@{command "then"}''; thus @{command "then"} is
324 equivalent to ``@{command "from"}~@{text this}''.
326 \item @{command "with"}~@{text "b\<^sub>1 \<dots> b\<^sub>n"} abbreviates ``@{command
327 "from"}~@{text "b\<^sub>1 \<dots> b\<^sub>n \<AND> this"}''; thus the forward chaining
328 is from earlier facts together with the current ones.
330 \item @{command "using"}~@{text "b\<^sub>1 \<dots> b\<^sub>n"} augments the facts being
331 currently indicated for use by a subsequent refinement step (such as
332 @{command_ref "apply"} or @{command_ref "proof"}).
334 \item @{command "unfolding"}~@{text "b\<^sub>1 \<dots> b\<^sub>n"} is structurally
335 similar to @{command "using"}, but unfolds definitional equations
336 @{text "b\<^sub>1, \<dots> b\<^sub>n"} throughout the goal state and facts.
340 Forward chaining with an empty list of theorems is the same as not
341 chaining at all. Thus ``@{command "from"}~@{text nothing}'' has no
342 effect apart from entering @{text "prove(chain)"} mode, since
343 @{fact_ref nothing} is bound to the empty list of theorems.
345 Basic proof methods (such as @{method_ref rule}) expect multiple
346 facts to be given in their proper order, corresponding to a prefix
347 of the premises of the rule involved. Note that positions may be
348 easily skipped using something like @{command "from"}~@{text "_
349 \<AND> a \<AND> b"}, for example. This involves the trivial rule
350 @{text "PROP \<psi> \<Longrightarrow> PROP \<psi>"}, which is bound in Isabelle/Pure as
351 ``@{fact_ref "_"}'' (underscore).
353 Automated methods (such as @{method simp} or @{method auto}) just
354 insert any given facts before their usual operation. Depending on
355 the kind of procedure involved, the order of facts is less
360 subsection {* Goals \label{sec:goals} *}
363 \begin{matharray}{rcl}
364 @{command_def "lemma"} & : & @{text "local_theory \<rightarrow> proof(prove)"} \\
365 @{command_def "theorem"} & : & @{text "local_theory \<rightarrow> proof(prove)"} \\
366 @{command_def "corollary"} & : & @{text "local_theory \<rightarrow> proof(prove)"} \\
367 @{command_def "have"} & : & @{text "proof(state) | proof(chain) \<rightarrow> proof(prove)"} \\
368 @{command_def "show"} & : & @{text "proof(state) | proof(chain) \<rightarrow> proof(prove)"} \\
369 @{command_def "hence"} & : & @{text "proof(state) \<rightarrow> proof(prove)"} \\
370 @{command_def "thus"} & : & @{text "proof(state) \<rightarrow> proof(prove)"} \\
371 @{command_def "print_statement"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
374 From a theory context, proof mode is entered by an initial goal
375 command such as @{command "lemma"}, @{command "theorem"}, or
376 @{command "corollary"}. Within a proof, new claims may be
377 introduced locally as well; four variants are available here to
378 indicate whether forward chaining of facts should be performed
379 initially (via @{command_ref "then"}), and whether the final result
380 is meant to solve some pending goal.
382 Goals may consist of multiple statements, resulting in a list of
383 facts eventually. A pending multi-goal is internally represented as
384 a meta-level conjunction (printed as @{text "&&"}), which is usually
385 split into the corresponding number of sub-goals prior to an initial
386 method application, via @{command_ref "proof"}
387 (\secref{sec:proof-steps}) or @{command_ref "apply"}
388 (\secref{sec:tactic-commands}). The @{method_ref induct} method
389 covered in \secref{sec:cases-induct} acts on multiple claims
392 Claims at the theory level may be either in short or long form. A
393 short goal merely consists of several simultaneous propositions
394 (often just one). A long goal includes an explicit context
395 specification for the subsequent conclusion, involving local
396 parameters and assumptions. Here the role of each part of the
397 statement is explicitly marked by separate keywords (see also
398 \secref{sec:locale}); the local assumptions being introduced here
399 are available as @{fact_ref assms} in the proof. Moreover, there
400 are two kinds of conclusions: @{element_def "shows"} states several
401 simultaneous propositions (essentially a big conjunction), while
402 @{element_def "obtains"} claims several simultaneous simultaneous
403 contexts of (essentially a big disjunction of eliminated parameters
404 and assumptions, cf.\ \secref{sec:obtain}).
407 ('lemma' | 'theorem' | 'corollary') target? (goal | longgoal)
409 ('have' | 'show' | 'hence' | 'thus') goal
411 'print\_statement' modes? thmrefs
414 goal: (props + 'and')
416 longgoal: thmdecl? (contextelem *) conclusion
418 conclusion: 'shows' goal | 'obtains' (parname? case + '|')
420 case: (vars + 'and') 'where' (props + 'and')
426 \item @{command "lemma"}~@{text "a: \<phi>"} enters proof mode with
427 @{text \<phi>} as main goal, eventually resulting in some fact @{text "\<turnstile>
428 \<phi>"} to be put back into the target context. An additional
429 \railnonterm{context} specification may build up an initial proof
430 context for the subsequent claim; this includes local definitions
431 and syntax as well, see the definition of @{syntax contextelem} in
434 \item @{command "theorem"}~@{text "a: \<phi>"} and @{command
435 "corollary"}~@{text "a: \<phi>"} are essentially the same as @{command
436 "lemma"}~@{text "a: \<phi>"}, but the facts are internally marked as
437 being of a different kind. This discrimination acts like a formal
440 \item @{command "have"}~@{text "a: \<phi>"} claims a local goal,
441 eventually resulting in a fact within the current logical context.
442 This operation is completely independent of any pending sub-goals of
443 an enclosing goal statements, so @{command "have"} may be freely
444 used for experimental exploration of potential results within a
447 \item @{command "show"}~@{text "a: \<phi>"} is like @{command
448 "have"}~@{text "a: \<phi>"} plus a second stage to refine some pending
449 sub-goal for each one of the finished result, after having been
450 exported into the corresponding context (at the head of the
451 sub-proof of this @{command "show"} command).
453 To accommodate interactive debugging, resulting rules are printed
454 before being applied internally. Even more, interactive execution
455 of @{command "show"} predicts potential failure and displays the
456 resulting error as a warning beforehand. Watch out for the
459 %FIXME proper antiquitation
461 Problem! Local statement will fail to solve any pending goal
464 \item @{command "hence"} abbreviates ``@{command "then"}~@{command
465 "have"}'', i.e.\ claims a local goal to be proven by forward
466 chaining the current facts. Note that @{command "hence"} is also
467 equivalent to ``@{command "from"}~@{text this}~@{command "have"}''.
469 \item @{command "thus"} abbreviates ``@{command "then"}~@{command
470 "show"}''. Note that @{command "thus"} is also equivalent to
471 ``@{command "from"}~@{text this}~@{command "show"}''.
473 \item @{command "print_statement"}~@{text a} prints facts from the
474 current theory or proof context in long statement form, according to
475 the syntax for @{command "lemma"} given above.
479 Any goal statement causes some term abbreviations (such as
480 @{variable_ref "?thesis"}) to be bound automatically, see also
481 \secref{sec:term-abbrev}.
483 The optional case names of @{element_ref "obtains"} have a twofold
484 meaning: (1) during the of this claim they refer to the the local
485 context introductions, (2) the resulting rule is annotated
486 accordingly to support symbolic case splits when used with the
487 @{method_ref cases} method (cf.\ \secref{sec:cases-induct}).
492 Isabelle/Isar suffers theory-level goal statements to contain
493 \emph{unbound schematic variables}, although this does not conform
494 to the aim of human-readable proof documents! The main problem
495 with schematic goals is that the actual outcome is usually hard to
496 predict, depending on the behavior of the proof methods applied
497 during the course of reasoning. Note that most semi-automated
498 methods heavily depend on several kinds of implicit rule
499 declarations within the current theory context. As this would
500 also result in non-compositional checking of sub-proofs,
501 \emph{local goals} are not allowed to be schematic at all.
502 Nevertheless, schematic goals do have their use in Prolog-style
503 interactive synthesis of proven results, usually by stepwise
504 refinement via emulation of traditional Isabelle tactic scripts
505 (see also \secref{sec:tactic-commands}). In any case, users
506 should know what they are doing.
511 section {* Refinement steps *}
513 subsection {* Proof method expressions \label{sec:proof-meth} *}
516 Proof methods are either basic ones, or expressions composed of
517 methods via ``@{verbatim ","}'' (sequential composition),
518 ``@{verbatim "|"}'' (alternative choices), ``@{verbatim "?"}''
519 (try), ``@{verbatim "+"}'' (repeat at least once), ``@{verbatim
520 "["}@{text n}@{verbatim "]"}'' (restriction to first @{text n}
521 sub-goals, with default @{text "n = 1"}). In practice, proof
522 methods are usually just a comma separated list of
523 \railqtok{nameref}~\railnonterm{args} specifications. Note that
524 parentheses may be dropped for single method specifications (with no
527 \indexouternonterm{method}
529 method: (nameref | '(' methods ')') (() | '?' | '+' | '[' nat? ']')
531 methods: (nameref args | method) + (',' | '|')
535 Proper Isar proof methods do \emph{not} admit arbitrary goal
536 addressing, but refer either to the first sub-goal or all sub-goals
537 uniformly. The goal restriction operator ``@{text "[n]"}''
538 evaluates a method expression within a sandbox consisting of the
539 first @{text n} sub-goals (which need to exist). For example, the
540 method ``@{text "simp_all[3]"}'' simplifies the first three
541 sub-goals, while ``@{text "(rule foo, simp_all)[]"}'' simplifies all
542 new goals that emerge from applying rule @{text "foo"} to the
543 originally first one.
545 Improper methods, notably tactic emulations, offer a separate
546 low-level goal addressing scheme as explicit argument to the
547 individual tactic being involved. Here ``@{text "[!]"}'' refers to
548 all goals, and ``@{text "[n-]"}'' to all goals starting from @{text
551 \indexouternonterm{goalspec}
553 goalspec: '[' (nat '-' nat | nat '-' | nat | '!' ) ']'
559 subsection {* Initial and terminal proof steps \label{sec:proof-steps} *}
562 \begin{matharray}{rcl}
563 @{command_def "proof"} & : & @{text "proof(prove) \<rightarrow> proof(state)"} \\
564 @{command_def "qed"} & : & @{text "proof(state) \<rightarrow> proof(state) | local_theory | theory"} \\
565 @{command_def "by"} & : & @{text "proof(prove) \<rightarrow> proof(state) | local_theory | theory"} \\
566 @{command_def ".."} & : & @{text "proof(prove) \<rightarrow> proof(state) | local_theory | theory"} \\
567 @{command_def "."} & : & @{text "proof(prove) \<rightarrow> proof(state) | local_theory | theory"} \\
568 @{command_def "sorry"} & : & @{text "proof(prove) \<rightarrow> proof(state) | local_theory | theory"} \\
571 Arbitrary goal refinement via tactics is considered harmful.
572 Structured proof composition in Isar admits proof methods to be
573 invoked in two places only.
577 \item An \emph{initial} refinement step @{command_ref
578 "proof"}~@{text "m\<^sub>1"} reduces a newly stated goal to a number
579 of sub-goals that are to be solved later. Facts are passed to
580 @{text "m\<^sub>1"} for forward chaining, if so indicated by @{text
581 "proof(chain)"} mode.
583 \item A \emph{terminal} conclusion step @{command_ref "qed"}~@{text
584 "m\<^sub>2"} is intended to solve remaining goals. No facts are
585 passed to @{text "m\<^sub>2"}.
589 The only other (proper) way to affect pending goals in a proof body
590 is by @{command_ref "show"}, which involves an explicit statement of
591 what is to be solved eventually. Thus we avoid the fundamental
592 problem of unstructured tactic scripts that consist of numerous
593 consecutive goal transformations, with invisible effects.
595 \medskip As a general rule of thumb for good proof style, initial
596 proof methods should either solve the goal completely, or constitute
597 some well-understood reduction to new sub-goals. Arbitrary
598 automatic proof tools that are prone leave a large number of badly
599 structured sub-goals are no help in continuing the proof document in
600 an intelligible manner.
602 Unless given explicitly by the user, the default initial method is
603 ``@{method_ref rule}'', which applies a single standard elimination
604 or introduction rule according to the topmost symbol involved.
605 There is no separate default terminal method. Any remaining goals
606 are always solved by assumption in the very last step.
615 ('.' | '..' | 'sorry')
621 \item @{command "proof"}~@{text "m\<^sub>1"} refines the goal by proof
622 method @{text "m\<^sub>1"}; facts for forward chaining are passed if so
623 indicated by @{text "proof(chain)"} mode.
625 \item @{command "qed"}~@{text "m\<^sub>2"} refines any remaining goals by
626 proof method @{text "m\<^sub>2"} and concludes the sub-proof by assumption.
627 If the goal had been @{text "show"} (or @{text "thus"}), some
628 pending sub-goal is solved as well by the rule resulting from the
629 result \emph{exported} into the enclosing goal context. Thus @{text
630 "qed"} may fail for two reasons: either @{text "m\<^sub>2"} fails, or the
631 resulting rule does not fit to any pending goal\footnote{This
632 includes any additional ``strong'' assumptions as introduced by
633 @{command "assume"}.} of the enclosing context. Debugging such a
634 situation might involve temporarily changing @{command "show"} into
635 @{command "have"}, or weakening the local context by replacing
636 occurrences of @{command "assume"} by @{command "presume"}.
638 \item @{command "by"}~@{text "m\<^sub>1 m\<^sub>2"} is a \emph{terminal
639 proof}\index{proof!terminal}; it abbreviates @{command
640 "proof"}~@{text "m\<^sub>1"}~@{text "qed"}~@{text "m\<^sub>2"}, but with
641 backtracking across both methods. Debugging an unsuccessful
642 @{command "by"}~@{text "m\<^sub>1 m\<^sub>2"} command can be done by expanding its
643 definition; in many cases @{command "proof"}~@{text "m\<^sub>1"} (or even
644 @{text "apply"}~@{text "m\<^sub>1"}) is already sufficient to see the
647 \item ``@{command ".."}'' is a \emph{default
648 proof}\index{proof!default}; it abbreviates @{command "by"}~@{text
651 \item ``@{command "."}'' is a \emph{trivial
652 proof}\index{proof!trivial}; it abbreviates @{command "by"}~@{text
655 \item @{command "sorry"} is a \emph{fake proof}\index{proof!fake}
656 pretending to solve the pending claim without further ado. This
657 only works in interactive development, or if the @{ML
658 quick_and_dirty} flag is enabled (in ML). Facts emerging from fake
659 proofs are not the real thing. Internally, each theorem container
660 is tainted by an oracle invocation, which is indicated as ``@{text
661 "[!]"}'' in the printed result.
663 The most important application of @{command "sorry"} is to support
664 experimentation and top-down proof development.
670 subsection {* Fundamental methods and attributes \label{sec:pure-meth-att} *}
673 The following proof methods and attributes refer to basic logical
674 operations of Isar. Further methods and attributes are provided by
675 several generic and object-logic specific tools and packages (see
676 \chref{ch:gen-tools} and \chref{ch:hol}).
678 \begin{matharray}{rcl}
679 @{method_def "-"} & : & @{text method} \\
680 @{method_def "fact"} & : & @{text method} \\
681 @{method_def "assumption"} & : & @{text method} \\
682 @{method_def "this"} & : & @{text method} \\
683 @{method_def "rule"} & : & @{text method} \\
684 @{method_def "iprover"} & : & @{text method} \\[0.5ex]
685 @{attribute_def (Pure) "intro"} & : & @{text attribute} \\
686 @{attribute_def (Pure) "elim"} & : & @{text attribute} \\
687 @{attribute_def (Pure) "dest"} & : & @{text attribute} \\
688 @{attribute_def "rule"} & : & @{text attribute} \\[0.5ex]
689 @{attribute_def "OF"} & : & @{text attribute} \\
690 @{attribute_def "of"} & : & @{text attribute} \\
691 @{attribute_def "where"} & : & @{text attribute} \\
699 'iprover' ('!' ?) (rulemod *)
701 rulemod: ('intro' | 'elim' | 'dest') ((('!' | () | '?') nat?) | 'del') ':' thmrefs
703 ('intro' | 'elim' | 'dest') ('!' | () | '?') nat?
709 'of' insts ('concl' ':' insts)?
711 'where' ((name | var | typefree | typevar) '=' (type | term) * 'and')
717 \item ``@{method "-"}'' (minus) does nothing but insert the forward
718 chaining facts as premises into the goal. Note that command
719 @{command_ref "proof"} without any method actually performs a single
720 reduction step using the @{method_ref rule} method; thus a plain
721 \emph{do-nothing} proof step would be ``@{command "proof"}~@{text
722 "-"}'' rather than @{command "proof"} alone.
724 \item @{method "fact"}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} composes some fact from
725 @{text "a\<^sub>1, \<dots>, a\<^sub>n"} (or implicitly from the current proof context)
726 modulo unification of schematic type and term variables. The rule
727 structure is not taken into account, i.e.\ meta-level implication is
728 considered atomic. This is the same principle underlying literal
729 facts (cf.\ \secref{sec:syn-att}): ``@{command "have"}~@{text
730 "\<phi>"}~@{command "by"}~@{text fact}'' is equivalent to ``@{command
731 "note"}~@{verbatim "`"}@{text \<phi>}@{verbatim "`"}'' provided that
732 @{text "\<turnstile> \<phi>"} is an instance of some known @{text "\<turnstile> \<phi>"} in the
735 \item @{method assumption} solves some goal by a single assumption
736 step. All given facts are guaranteed to participate in the
737 refinement; this means there may be only 0 or 1 in the first place.
738 Recall that @{command "qed"} (\secref{sec:proof-steps}) already
739 concludes any remaining sub-goals by assumption, so structured
740 proofs usually need not quote the @{method assumption} method at
743 \item @{method this} applies all of the current facts directly as
744 rules. Recall that ``@{command "."}'' (dot) abbreviates ``@{command
745 "by"}~@{text this}''.
747 \item @{method rule}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} applies some rule given as
748 argument in backward manner; facts are used to reduce the rule
749 before applying it to the goal. Thus @{method rule} without facts
750 is plain introduction, while with facts it becomes elimination.
752 When no arguments are given, the @{method rule} method tries to pick
753 appropriate rules automatically, as declared in the current context
754 using the @{attribute (Pure) intro}, @{attribute (Pure) elim},
755 @{attribute (Pure) dest} attributes (see below). This is the
756 default behavior of @{command "proof"} and ``@{command ".."}''
757 (double-dot) steps (see \secref{sec:proof-steps}).
759 \item @{method iprover} performs intuitionistic proof search,
760 depending on specifically declared rules from the context, or given
761 as explicit arguments. Chained facts are inserted into the goal
762 before commencing proof search; ``@{method iprover}@{text "!"}''
763 means to include the current @{fact prems} as well.
765 Rules need to be classified as @{attribute (Pure) intro},
766 @{attribute (Pure) elim}, or @{attribute (Pure) dest}; here the
767 ``@{text "!"}'' indicator refers to ``safe'' rules, which may be
768 applied aggressively (without considering back-tracking later).
769 Rules declared with ``@{text "?"}'' are ignored in proof search (the
770 single-step @{method rule} method still observes these). An
771 explicit weight annotation may be given as well; otherwise the
772 number of rule premises will be taken into account here.
774 \item @{attribute (Pure) intro}, @{attribute (Pure) elim}, and
775 @{attribute (Pure) dest} declare introduction, elimination, and
776 destruct rules, to be used with the @{method rule} and @{method
777 iprover} methods. Note that the latter will ignore rules declared
778 with ``@{text "?"}'', while ``@{text "!"}'' are used most
781 The classical reasoner (see \secref{sec:classical}) introduces its
782 own variants of these attributes; use qualified names to access the
783 present versions of Isabelle/Pure, i.e.\ @{attribute (Pure)
786 \item @{attribute rule}~@{text del} undeclares introduction,
787 elimination, or destruct rules.
789 \item @{attribute OF}~@{text "a\<^sub>1 \<dots> a\<^sub>n"} applies some theorem to all
790 of the given rules @{text "a\<^sub>1, \<dots>, a\<^sub>n"} (in parallel). This
791 corresponds to the @{ML [source=false] "op MRS"} operation in ML,
792 but note the reversed order. Positions may be effectively skipped
793 by including ``@{text _}'' (underscore) as argument.
795 \item @{attribute of}~@{text "t\<^sub>1 \<dots> t\<^sub>n"} performs positional
796 instantiation of term variables. The terms @{text "t\<^sub>1, \<dots>, t\<^sub>n"} are
797 substituted for any schematic variables occurring in a theorem from
798 left to right; ``@{text _}'' (underscore) indicates to skip a
799 position. Arguments following a ``@{text "concl:"}'' specification
800 refer to positions of the conclusion of a rule.
802 \item @{attribute "where"}~@{text "x\<^sub>1 = t\<^sub>1 \<AND> \<dots> x\<^sub>n = t\<^sub>n"}
803 performs named instantiation of schematic type and term variables
804 occurring in a theorem. Schematic variables have to be specified on
805 the left-hand side (e.g.\ @{text "?x1.3"}). The question mark may
806 be omitted if the variable name is a plain identifier without index.
807 As type instantiations are inferred from term instantiations,
808 explicit type instantiations are seldom necessary.
814 subsection {* Emulating tactic scripts \label{sec:tactic-commands} *}
817 The Isar provides separate commands to accommodate tactic-style
818 proof scripts within the same system. While being outside the
819 orthodox Isar proof language, these might come in handy for
820 interactive exploration and debugging, or even actual tactical proof
821 within new-style theories (to benefit from document preparation, for
822 example). See also \secref{sec:tactics} for actual tactics, that
823 have been encapsulated as proof methods. Proper proof methods may
824 be used in scripts, too.
826 \begin{matharray}{rcl}
827 @{command_def "apply"}@{text "\<^sup>*"} & : & @{text "proof(prove) \<rightarrow> proof(prove)"} \\
828 @{command_def "apply_end"}@{text "\<^sup>*"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
829 @{command_def "done"}@{text "\<^sup>*"} & : & @{text "proof(prove) \<rightarrow> proof(state) | local_theory | theory"} \\
830 @{command_def "defer"}@{text "\<^sup>*"} & : & @{text "proof \<rightarrow> proof"} \\
831 @{command_def "prefer"}@{text "\<^sup>*"} & : & @{text "proof \<rightarrow> proof"} \\
832 @{command_def "back"}@{text "\<^sup>*"} & : & @{text "proof \<rightarrow> proof"} \\
836 ( 'apply' | 'apply\_end' ) method
846 \item @{command "apply"}~@{text m} applies proof method @{text m} in
847 initial position, but unlike @{command "proof"} it retains ``@{text
848 "proof(prove)"}'' mode. Thus consecutive method applications may be
849 given just as in tactic scripts.
851 Facts are passed to @{text m} as indicated by the goal's
852 forward-chain mode, and are \emph{consumed} afterwards. Thus any
853 further @{command "apply"} command would always work in a purely
856 \item @{command "apply_end"}~@{text "m"} applies proof method @{text
857 m} as if in terminal position. Basically, this simulates a
858 multi-step tactic script for @{command "qed"}, but may be given
859 anywhere within the proof body.
861 No facts are passed to @{text m} here. Furthermore, the static
862 context is that of the enclosing goal (as for actual @{command
863 "qed"}). Thus the proof method may not refer to any assumptions
864 introduced in the current body, for example.
866 \item @{command "done"} completes a proof script, provided that the
867 current goal state is solved completely. Note that actual
868 structured proof commands (e.g.\ ``@{command "."}'' or @{command
869 "sorry"}) may be used to conclude proof scripts as well.
871 \item @{command "defer"}~@{text n} and @{command "prefer"}~@{text n}
872 shuffle the list of pending goals: @{command "defer"} puts off
873 sub-goal @{text n} to the end of the list (@{text "n = 1"} by
874 default), while @{command "prefer"} brings sub-goal @{text n} to the
877 \item @{command "back"} does back-tracking over the result sequence
878 of the latest proof command. Basically, any proof command may
879 return multiple results.
883 Any proper Isar proof method may be used with tactic script commands
884 such as @{command "apply"}. A few additional emulations of actual
885 tactics are provided as well; these would be never used in actual
886 structured proofs, of course.
890 subsection {* Defining proof methods *}
893 \begin{matharray}{rcl}
894 @{command_def "method_setup"} & : & @{text "theory \<rightarrow> theory"} \\
898 'method\_setup' name '=' text text
904 \item @{command "method_setup"}~@{text "name = text description"}
905 defines a proof method in the current theory. The given @{text
906 "text"} has to be an ML expression of type @{ML_type [source=false]
907 "Args.src -> Proof.context -> Proof.method"}. Parsing concrete
908 method syntax from @{ML_type Args.src} input can be quite tedious in
909 general. The following simple examples are for methods without any
910 explicit arguments, or a list of theorems, respectively.
912 %FIXME proper antiquotations
915 Method.no_args (Method.METHOD (fn facts => foobar_tac))
916 Method.thms_args (fn thms => Method.METHOD (fn facts => foobar_tac))
917 Method.ctxt_args (fn ctxt => Method.METHOD (fn facts => foobar_tac))
918 Method.thms_ctxt_args (fn thms => fn ctxt =>
919 Method.METHOD (fn facts => foobar_tac))
923 Note that mere tactic emulations may ignore the @{text facts}
924 parameter above. Proper proof methods would do something
925 appropriate with the list of current facts, though. Single-rule
926 methods usually do strict forward-chaining (e.g.\ by using @{ML
927 Drule.multi_resolves}), while automatic ones just insert the facts
928 using @{ML Method.insert_tac} before applying the main tactic.
934 section {* Generalized elimination \label{sec:obtain} *}
937 \begin{matharray}{rcl}
938 @{command_def "obtain"} & : & @{text "proof(state) | proof(chain) \<rightarrow> proof(prove)"} \\
939 @{command_def "guess"}@{text "\<^sup>*"} & : & @{text "proof(state) | proof(chain) \<rightarrow> proof(prove)"} \\
942 Generalized elimination means that additional elements with certain
943 properties may be introduced in the current context, by virtue of a
944 locally proven ``soundness statement''. Technically speaking, the
945 @{command "obtain"} language element is like a declaration of
946 @{command "fix"} and @{command "assume"} (see also see
947 \secref{sec:proof-context}), together with a soundness proof of its
948 additional claim. According to the nature of existential reasoning,
949 assumptions get eliminated from any result exported from the context
950 later, provided that the corresponding parameters do \emph{not}
951 occur in the conclusion.
954 'obtain' parname? (vars + 'and') 'where' (props + 'and')
956 'guess' (vars + 'and')
960 The derived Isar command @{command "obtain"} is defined as follows
961 (where @{text "b\<^sub>1, \<dots>, b\<^sub>k"} shall refer to (optional)
962 facts indicated for forward chaining).
964 @{text "\<langle>using b\<^sub>1 \<dots> b\<^sub>k\<rangle>"}~~@{command "obtain"}~@{text "x\<^sub>1 \<dots> x\<^sub>m \<WHERE> a: \<phi>\<^sub>1 \<dots> \<phi>\<^sub>n \<langle>proof\<rangle> \<equiv>"} \\[1ex]
965 \quad @{command "have"}~@{text "\<And>thesis. (\<And>x\<^sub>1 \<dots> x\<^sub>m. \<phi>\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> thesis) \<Longrightarrow> thesis"} \\
966 \quad @{command "proof"}~@{text succeed} \\
967 \qquad @{command "fix"}~@{text thesis} \\
968 \qquad @{command "assume"}~@{text "that [Pure.intro?]: \<And>x\<^sub>1 \<dots> x\<^sub>m. \<phi>\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> thesis"} \\
969 \qquad @{command "then"}~@{command "show"}~@{text thesis} \\
970 \quad\qquad @{command "apply"}~@{text -} \\
971 \quad\qquad @{command "using"}~@{text "b\<^sub>1 \<dots> b\<^sub>k \<langle>proof\<rangle>"} \\
972 \quad @{command "qed"} \\
973 \quad @{command "fix"}~@{text "x\<^sub>1 \<dots> x\<^sub>m"}~@{command "assume"}@{text "\<^sup>* a: \<phi>\<^sub>1 \<dots> \<phi>\<^sub>n"} \\
976 Typically, the soundness proof is relatively straight-forward, often
977 just by canonical automated tools such as ``@{command "by"}~@{text
978 simp}'' or ``@{command "by"}~@{text blast}''. Accordingly, the
979 ``@{text that}'' reduction above is declared as simplification and
982 In a sense, @{command "obtain"} represents at the level of Isar
983 proofs what would be meta-logical existential quantifiers and
984 conjunctions. This concept has a broad range of useful
985 applications, ranging from plain elimination (or introduction) of
986 object-level existential and conjunctions, to elimination over
987 results of symbolic evaluation of recursive definitions, for
988 example. Also note that @{command "obtain"} without parameters acts
989 much like @{command "have"}, where the result is treated as a
992 An alternative name to be used instead of ``@{text that}'' above may
993 be given in parentheses.
995 \medskip The improper variant @{command "guess"} is similar to
996 @{command "obtain"}, but derives the obtained statement from the
997 course of reasoning! The proof starts with a fixed goal @{text
998 thesis}. The subsequent proof may refine this to anything of the
999 form like @{text "\<And>x\<^sub>1 \<dots> x\<^sub>m. \<phi>\<^sub>1 \<Longrightarrow> \<dots>
1000 \<phi>\<^sub>n \<Longrightarrow> thesis"}, but must not introduce new subgoals. The
1001 final goal state is then used as reduction rule for the obtain
1002 scheme described above. Obtained parameters @{text "x\<^sub>1, \<dots>,
1003 x\<^sub>m"} are marked as internal by default, which prevents the
1004 proof context from being polluted by ad-hoc variables. The variable
1005 names and type constraints given as arguments for @{command "guess"}
1006 specify a prefix of obtained parameters explicitly in the text.
1008 It is important to note that the facts introduced by @{command
1009 "obtain"} and @{command "guess"} may not be polymorphic: any
1010 type-variables occurring here are fixed in the present context!
1014 section {* Calculational reasoning \label{sec:calculation} *}
1017 \begin{matharray}{rcl}
1018 @{command_def "also"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
1019 @{command_def "finally"} & : & @{text "proof(state) \<rightarrow> proof(chain)"} \\
1020 @{command_def "moreover"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
1021 @{command_def "ultimately"} & : & @{text "proof(state) \<rightarrow> proof(chain)"} \\
1022 @{command_def "print_trans_rules"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
1023 @{attribute trans} & : & @{text attribute} \\
1024 @{attribute sym} & : & @{text attribute} \\
1025 @{attribute symmetric} & : & @{text attribute} \\
1028 Calculational proof is forward reasoning with implicit application
1029 of transitivity rules (such those of @{text "="}, @{text "\<le>"},
1030 @{text "<"}). Isabelle/Isar maintains an auxiliary fact register
1031 @{fact_ref calculation} for accumulating results obtained by
1032 transitivity composed with the current result. Command @{command
1033 "also"} updates @{fact calculation} involving @{fact this}, while
1034 @{command "finally"} exhibits the final @{fact calculation} by
1035 forward chaining towards the next goal statement. Both commands
1036 require valid current facts, i.e.\ may occur only after commands
1037 that produce theorems such as @{command "assume"}, @{command
1038 "note"}, or some finished proof of @{command "have"}, @{command
1039 "show"} etc. The @{command "moreover"} and @{command "ultimately"}
1040 commands are similar to @{command "also"} and @{command "finally"},
1041 but only collect further results in @{fact calculation} without
1042 applying any rules yet.
1044 Also note that the implicit term abbreviation ``@{text "\<dots>"}'' has
1045 its canonical application with calculational proofs. It refers to
1046 the argument of the preceding statement. (The argument of a curried
1047 infix expression happens to be its right-hand side.)
1049 Isabelle/Isar calculations are implicitly subject to block structure
1050 in the sense that new threads of calculational reasoning are
1051 commenced for any new block (as opened by a local goal, for
1052 example). This means that, apart from being able to nest
1053 calculations, there is no separate \emph{begin-calculation} command
1056 \medskip The Isar calculation proof commands may be defined as
1057 follows:\footnote{We suppress internal bookkeeping such as proper
1058 handling of block-structure.}
1060 \begin{matharray}{rcl}
1061 @{command "also"}@{text "\<^sub>0"} & \equiv & @{command "note"}~@{text "calculation = this"} \\
1062 @{command "also"}@{text "\<^sub>n\<^sub>+\<^sub>1"} & \equiv & @{command "note"}~@{text "calculation = trans [OF calculation this]"} \\[0.5ex]
1063 @{command "finally"} & \equiv & @{command "also"}~@{command "from"}~@{text calculation} \\[0.5ex]
1064 @{command "moreover"} & \equiv & @{command "note"}~@{text "calculation = calculation this"} \\
1065 @{command "ultimately"} & \equiv & @{command "moreover"}~@{command "from"}~@{text calculation} \\
1069 ('also' | 'finally') ('(' thmrefs ')')?
1071 'trans' (() | 'add' | 'del')
1077 \item @{command "also"}~@{text "(a\<^sub>1 \<dots> a\<^sub>n)"} maintains the auxiliary
1078 @{fact calculation} register as follows. The first occurrence of
1079 @{command "also"} in some calculational thread initializes @{fact
1080 calculation} by @{fact this}. Any subsequent @{command "also"} on
1081 the same level of block-structure updates @{fact calculation} by
1082 some transitivity rule applied to @{fact calculation} and @{fact
1083 this} (in that order). Transitivity rules are picked from the
1084 current context, unless alternative rules are given as explicit
1087 \item @{command "finally"}~@{text "(a\<^sub>1 \<dots> a\<^sub>n)"} maintaining @{fact
1088 calculation} in the same way as @{command "also"}, and concludes the
1089 current calculational thread. The final result is exhibited as fact
1090 for forward chaining towards the next goal. Basically, @{command
1091 "finally"} just abbreviates @{command "also"}~@{command
1092 "from"}~@{fact calculation}. Typical idioms for concluding
1093 calculational proofs are ``@{command "finally"}~@{command
1094 "show"}~@{text ?thesis}~@{command "."}'' and ``@{command
1095 "finally"}~@{command "have"}~@{text \<phi>}~@{command "."}''.
1097 \item @{command "moreover"} and @{command "ultimately"} are
1098 analogous to @{command "also"} and @{command "finally"}, but collect
1099 results only, without applying rules.
1101 \item @{command "print_trans_rules"} prints the list of transitivity
1102 rules (for calculational commands @{command "also"} and @{command
1103 "finally"}) and symmetry rules (for the @{attribute symmetric}
1104 operation and single step elimination patters) of the current
1107 \item @{attribute trans} declares theorems as transitivity rules.
1109 \item @{attribute sym} declares symmetry rules, as well as
1110 @{attribute "Pure.elim"}@{text "?"} rules.
1112 \item @{attribute symmetric} resolves a theorem with some rule
1113 declared as @{attribute sym} in the current context. For example,
1114 ``@{command "assume"}~@{text "[symmetric]: x = y"}'' produces a
1115 swapped fact derived from that assumption.
1117 In structured proof texts it is often more appropriate to use an
1118 explicit single-step elimination proof, such as ``@{command
1119 "assume"}~@{text "x = y"}~@{command "then"}~@{command "have"}~@{text
1120 "y = x"}~@{command ".."}''.
1126 section {* Proof by cases and induction \label{sec:cases-induct} *}
1128 subsection {* Rule contexts *}
1131 \begin{matharray}{rcl}
1132 @{command_def "case"} & : & @{text "proof(state) \<rightarrow> proof(state)"} \\
1133 @{command_def "print_cases"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
1134 @{attribute_def case_names} & : & @{text attribute} \\
1135 @{attribute_def case_conclusion} & : & @{text attribute} \\
1136 @{attribute_def params} & : & @{text attribute} \\
1137 @{attribute_def consumes} & : & @{text attribute} \\
1140 The puristic way to build up Isar proof contexts is by explicit
1141 language elements like @{command "fix"}, @{command "assume"},
1142 @{command "let"} (see \secref{sec:proof-context}). This is adequate
1143 for plain natural deduction, but easily becomes unwieldy in concrete
1144 verification tasks, which typically involve big induction rules with
1147 The @{command "case"} command provides a shorthand to refer to a
1148 local context symbolically: certain proof methods provide an
1149 environment of named ``cases'' of the form @{text "c: x\<^sub>1, \<dots>,
1150 x\<^sub>m, \<phi>\<^sub>1, \<dots>, \<phi>\<^sub>n"}; the effect of ``@{command
1151 "case"}~@{text c}'' is then equivalent to ``@{command "fix"}~@{text
1152 "x\<^sub>1 \<dots> x\<^sub>m"}~@{command "assume"}~@{text "c: \<phi>\<^sub>1 \<dots>
1153 \<phi>\<^sub>n"}''. Term bindings may be covered as well, notably
1154 @{variable ?case} for the main conclusion.
1156 By default, the ``terminology'' @{text "x\<^sub>1, \<dots>, x\<^sub>m"} of
1157 a case value is marked as hidden, i.e.\ there is no way to refer to
1158 such parameters in the subsequent proof text. After all, original
1159 rule parameters stem from somewhere outside of the current proof
1160 text. By using the explicit form ``@{command "case"}~@{text "(c
1161 y\<^sub>1 \<dots> y\<^sub>m)"}'' instead, the proof author is able to
1162 chose local names that fit nicely into the current context.
1164 \medskip It is important to note that proper use of @{command
1165 "case"} does not provide means to peek at the current goal state,
1166 which is not directly observable in Isar! Nonetheless, goal
1167 refinement commands do provide named cases @{text "goal\<^sub>i"}
1168 for each subgoal @{text "i = 1, \<dots>, n"} of the resulting goal state.
1169 Using this extra feature requires great care, because some bits of
1170 the internal tactical machinery intrude the proof text. In
1171 particular, parameter names stemming from the left-over of automated
1172 reasoning tools are usually quite unpredictable.
1174 Under normal circumstances, the text of cases emerge from standard
1175 elimination or induction rules, which in turn are derived from
1176 previous theory specifications in a canonical way (say from
1177 @{command "inductive"} definitions).
1179 \medskip Proper cases are only available if both the proof method
1180 and the rules involved support this. By using appropriate
1181 attributes, case names, conclusions, and parameters may be also
1182 declared by hand. Thus variant versions of rules that have been
1183 derived manually become ready to use in advanced case analysis
1187 'case' (caseref | '(' caseref ((name | underscore) +) ')')
1189 caseref: nameref attributes?
1192 'case\_names' (name +)
1194 'case\_conclusion' name (name *)
1196 'params' ((name *) + 'and')
1204 \item @{command "case"}~@{text "(c x\<^sub>1 \<dots> x\<^sub>m)"} invokes a named local
1205 context @{text "c: x\<^sub>1, \<dots>, x\<^sub>m, \<phi>\<^sub>1, \<dots>, \<phi>\<^sub>m"}, as provided by an
1206 appropriate proof method (such as @{method_ref cases} and
1207 @{method_ref induct}). The command ``@{command "case"}~@{text "(c
1208 x\<^sub>1 \<dots> x\<^sub>m)"}'' abbreviates ``@{command "fix"}~@{text "x\<^sub>1 \<dots>
1209 x\<^sub>m"}~@{command "assume"}~@{text "c: \<phi>\<^sub>1 \<dots> \<phi>\<^sub>n"}''.
1211 \item @{command "print_cases"} prints all local contexts of the
1212 current state, using Isar proof language notation.
1214 \item @{attribute case_names}~@{text "c\<^sub>1 \<dots> c\<^sub>k"} declares names for
1215 the local contexts of premises of a theorem; @{text "c\<^sub>1, \<dots>, c\<^sub>k"}
1216 refers to the \emph{suffix} of the list of premises.
1218 \item @{attribute case_conclusion}~@{text "c d\<^sub>1 \<dots> d\<^sub>k"} declares
1219 names for the conclusions of a named premise @{text c}; here @{text
1220 "d\<^sub>1, \<dots>, d\<^sub>k"} refers to the prefix of arguments of a logical formula
1221 built by nesting a binary connective (e.g.\ @{text "\<or>"}).
1223 Note that proof methods such as @{method induct} and @{method
1224 coinduct} already provide a default name for the conclusion as a
1225 whole. The need to name subformulas only arises with cases that
1226 split into several sub-cases, as in common co-induction rules.
1228 \item @{attribute params}~@{text "p\<^sub>1 \<dots> p\<^sub>m \<AND> \<dots> q\<^sub>1 \<dots> q\<^sub>n"} renames
1229 the innermost parameters of premises @{text "1, \<dots>, n"} of some
1230 theorem. An empty list of names may be given to skip positions,
1231 leaving the present parameters unchanged.
1233 Note that the default usage of case rules does \emph{not} directly
1234 expose parameters to the proof context.
1236 \item @{attribute consumes}~@{text n} declares the number of ``major
1237 premises'' of a rule, i.e.\ the number of facts to be consumed when
1238 it is applied by an appropriate proof method. The default value of
1239 @{attribute consumes} is @{text "n = 1"}, which is appropriate for
1240 the usual kind of cases and induction rules for inductive sets (cf.\
1241 \secref{sec:hol-inductive}). Rules without any @{attribute
1242 consumes} declaration given are treated as if @{attribute
1243 consumes}~@{text 0} had been specified.
1245 Note that explicit @{attribute consumes} declarations are only
1246 rarely needed; this is already taken care of automatically by the
1247 higher-level @{attribute cases}, @{attribute induct}, and
1248 @{attribute coinduct} declarations.
1254 subsection {* Proof methods *}
1257 \begin{matharray}{rcl}
1258 @{method_def cases} & : & @{text method} \\
1259 @{method_def induct} & : & @{text method} \\
1260 @{method_def coinduct} & : & @{text method} \\
1263 The @{method cases}, @{method induct}, and @{method coinduct}
1264 methods provide a uniform interface to common proof techniques over
1265 datatypes, inductive predicates (or sets), recursive functions etc.
1266 The corresponding rules may be specified and instantiated in a
1267 casual manner. Furthermore, these methods provide named local
1268 contexts that may be invoked via the @{command "case"} proof command
1269 within the subsequent proof text. This accommodates compact proof
1270 texts even when reasoning about large specifications.
1272 The @{method induct} method also provides some additional
1273 infrastructure in order to be applicable to structure statements
1274 (either using explicit meta-level connectives, or including facts
1275 and parameters separately). This avoids cumbersome encoding of
1276 ``strengthened'' inductive statements within the object-logic.
1279 'cases' (insts * 'and') rule?
1281 'induct' (definsts * 'and') \\ arbitrary? taking? rule?
1283 'coinduct' insts taking rule?
1286 rule: ('type' | 'pred' | 'set') ':' (nameref +) | 'rule' ':' (thmref +)
1288 definst: name ('==' | equiv) term | inst
1290 definsts: ( definst *)
1292 arbitrary: 'arbitrary' ':' ((term *) 'and' +)
1294 taking: 'taking' ':' insts
1300 \item @{method cases}~@{text "insts R"} applies method @{method
1301 rule} with an appropriate case distinction theorem, instantiated to
1302 the subjects @{text insts}. Symbolic case names are bound according
1303 to the rule's local contexts.
1305 The rule is determined as follows, according to the facts and
1306 arguments passed to the @{method cases} method:
1309 \begin{tabular}{llll}
1310 facts & & arguments & rule \\\hline
1311 & @{method cases} & & classical case split \\
1312 & @{method cases} & @{text t} & datatype exhaustion (type of @{text t}) \\
1313 @{text "\<turnstile> A t"} & @{method cases} & @{text "\<dots>"} & inductive predicate/set elimination (of @{text A}) \\
1314 @{text "\<dots>"} & @{method cases} & @{text "\<dots> rule: R"} & explicit rule @{text R} \\
1318 Several instantiations may be given, referring to the \emph{suffix}
1319 of premises of the case rule; within each premise, the \emph{prefix}
1320 of variables is instantiated. In most situations, only a single
1321 term needs to be specified; this refers to the first variable of the
1322 last premise (it is usually the same for all cases).
1324 \item @{method induct}~@{text "insts R"} is analogous to the
1325 @{method cases} method, but refers to induction rules, which are
1326 determined as follows:
1329 \begin{tabular}{llll}
1330 facts & & arguments & rule \\\hline
1331 & @{method induct} & @{text "P x"} & datatype induction (type of @{text x}) \\
1332 @{text "\<turnstile> A x"} & @{method induct} & @{text "\<dots>"} & predicate/set induction (of @{text A}) \\
1333 @{text "\<dots>"} & @{method induct} & @{text "\<dots> rule: R"} & explicit rule @{text R} \\
1337 Several instantiations may be given, each referring to some part of
1338 a mutual inductive definition or datatype --- only related partial
1339 induction rules may be used together, though. Any of the lists of
1340 terms @{text "P, x, \<dots>"} refers to the \emph{suffix} of variables
1341 present in the induction rule. This enables the writer to specify
1342 only induction variables, or both predicates and variables, for
1345 Instantiations may be definitional: equations @{text "x \<equiv> t"}
1346 introduce local definitions, which are inserted into the claim and
1347 discharged after applying the induction rule. Equalities reappear
1348 in the inductive cases, but have been transformed according to the
1349 induction principle being involved here. In order to achieve
1350 practically useful induction hypotheses, some variables occurring in
1351 @{text t} need to be fixed (see below).
1353 The optional ``@{text "arbitrary: x\<^sub>1 \<dots> x\<^sub>m"}''
1354 specification generalizes variables @{text "x\<^sub>1, \<dots>,
1355 x\<^sub>m"} of the original goal before applying induction. Thus
1356 induction hypotheses may become sufficiently general to get the
1357 proof through. Together with definitional instantiations, one may
1358 effectively perform induction over expressions of a certain
1361 The optional ``@{text "taking: t\<^sub>1 \<dots> t\<^sub>n"}''
1362 specification provides additional instantiations of a prefix of
1363 pending variables in the rule. Such schematic induction rules
1364 rarely occur in practice, though.
1366 \item @{method coinduct}~@{text "inst R"} is analogous to the
1367 @{method induct} method, but refers to coinduction rules, which are
1368 determined as follows:
1371 \begin{tabular}{llll}
1372 goal & & arguments & rule \\\hline
1373 & @{method coinduct} & @{text x} & type coinduction (type of @{text x}) \\
1374 @{text "A x"} & @{method coinduct} & @{text "\<dots>"} & predicate/set coinduction (of @{text A}) \\
1375 @{text "\<dots>"} & @{method coinduct} & @{text "\<dots> rule: R"} & explicit rule @{text R} \\
1378 Coinduction is the dual of induction. Induction essentially
1379 eliminates @{text "A x"} towards a generic result @{text "P x"},
1380 while coinduction introduces @{text "A x"} starting with @{text "B
1381 x"}, for a suitable ``bisimulation'' @{text B}. The cases of a
1382 coinduct rule are typically named after the predicates or sets being
1383 covered, while the conclusions consist of several alternatives being
1384 named after the individual destructor patterns.
1386 The given instantiation refers to the \emph{suffix} of variables
1387 occurring in the rule's major premise, or conclusion if unavailable.
1388 An additional ``@{text "taking: t\<^sub>1 \<dots> t\<^sub>n"}''
1389 specification may be required in order to specify the bisimulation
1390 to be used in the coinduction step.
1394 Above methods produce named local contexts, as determined by the
1395 instantiated rule as given in the text. Beyond that, the @{method
1396 induct} and @{method coinduct} methods guess further instantiations
1397 from the goal specification itself. Any persisting unresolved
1398 schematic variables of the resulting rule will render the the
1399 corresponding case invalid. The term binding @{variable ?case} for
1400 the conclusion will be provided with each case, provided that term
1403 The @{command "print_cases"} command prints all named cases present
1404 in the current proof state.
1406 \medskip Despite the additional infrastructure, both @{method cases}
1407 and @{method coinduct} merely apply a certain rule, after
1408 instantiation, while conforming due to the usual way of monotonic
1409 natural deduction: the context of a structured statement @{text
1410 "\<And>x\<^sub>1 \<dots> x\<^sub>m. \<phi>\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> \<dots>"}
1411 reappears unchanged after the case split.
1413 The @{method induct} method is fundamentally different in this
1414 respect: the meta-level structure is passed through the
1415 ``recursive'' course involved in the induction. Thus the original
1416 statement is basically replaced by separate copies, corresponding to
1417 the induction hypotheses and conclusion; the original goal context
1418 is no longer available. Thus local assumptions, fixed parameters
1419 and definitions effectively participate in the inductive rephrasing
1420 of the original statement.
1422 In induction proofs, local assumptions introduced by cases are split
1423 into two different kinds: @{text hyps} stemming from the rule and
1424 @{text prems} from the goal statement. This is reflected in the
1425 extracted cases accordingly, so invoking ``@{command "case"}~@{text
1426 c}'' will provide separate facts @{text c.hyps} and @{text c.prems},
1427 as well as fact @{text c} to hold the all-inclusive list.
1429 \medskip Facts presented to either method are consumed according to
1430 the number of ``major premises'' of the rule involved, which is
1431 usually 0 for plain cases and induction rules of datatypes etc.\ and
1432 1 for rules of inductive predicates or sets and the like. The
1433 remaining facts are inserted into the goal verbatim before the
1434 actual @{text cases}, @{text induct}, or @{text coinduct} rule is
1439 subsection {* Declaring rules *}
1442 \begin{matharray}{rcl}
1443 @{command_def "print_induct_rules"}@{text "\<^sup>*"} & : & @{text "context \<rightarrow>"} \\
1444 @{attribute_def cases} & : & @{text attribute} \\
1445 @{attribute_def induct} & : & @{text attribute} \\
1446 @{attribute_def coinduct} & : & @{text attribute} \\
1457 spec: (('type' | 'pred' | 'set') ':' nameref) | 'del'
1463 \item @{command "print_induct_rules"} prints cases and induct rules
1464 for predicates (or sets) and types of the current context.
1466 \item @{attribute cases}, @{attribute induct}, and @{attribute
1467 coinduct} (as attributes) declare rules for reasoning about
1468 (co)inductive predicates (or sets) and types, using the
1469 corresponding methods of the same name. Certain definitional
1470 packages of object-logics usually declare emerging cases and
1471 induction rules as expected, so users rarely need to intervene.
1473 Rules may be deleted via the @{text "del"} specification, which
1474 covers all of the @{text "type"}/@{text "pred"}/@{text "set"}
1475 sub-categories simultaneously. For example, @{attribute
1476 cases}~@{text del} removes any @{attribute cases} rules declared for
1477 some type, predicate, or set.
1479 Manual rule declarations usually refer to the @{attribute
1480 case_names} and @{attribute params} attributes to adjust names of
1481 cases and parameters of a rule; the @{attribute consumes}
1482 declaration is taken care of automatically: @{attribute
1483 consumes}~@{text 0} is specified for ``type'' rules and @{attribute
1484 consumes}~@{text 1} for ``predicate'' / ``set'' rules.