18537
|
1 |
|
|
2 |
(* $Id$ *)
|
|
3 |
|
|
4 |
theory "proof" imports base begin
|
|
5 |
|
20451
|
6 |
chapter {* Structured proofs *}
|
18537
|
7 |
|
20460
|
8 |
section {* Variables *}
|
20026
|
9 |
|
20470
|
10 |
text {*
|
|
11 |
Any variable that is not explicitly bound by @{text "\<lambda>"}-abstraction
|
|
12 |
is considered as ``free''. Logically, free variables act like
|
|
13 |
outermost universal quantification (at the sequent level): @{text
|
|
14 |
"A\<^isub>1(x), \<dots>, A\<^isub>n(x) \<turnstile> B(x)"} means that the result
|
|
15 |
holds \emph{for all} values of @{text "x"}. Free variables for
|
|
16 |
terms (not types) can be fully internalized into the logic: @{text
|
|
17 |
"\<turnstile> B(x)"} and @{text "\<turnstile> \<And>x. B(x)"} are interchangeable provided that
|
|
18 |
@{text "x"} does not occur elsewhere in the context. Inspecting
|
|
19 |
@{text "\<turnstile> \<And>x. B(x)"} more closely, we see that inside the
|
|
20 |
quantifier, @{text "x"} is essentially ``arbitrary, but fixed'',
|
|
21 |
while from outside it appears as a place-holder for instantiation
|
|
22 |
(thanks to @{text "\<And>"}-elimination).
|
|
23 |
|
|
24 |
The Pure logic represents the notion of variables being either
|
|
25 |
inside or outside the current scope by providing separate syntactic
|
|
26 |
categories for \emph{fixed variables} (e.g.\ @{text "x"}) vs.\
|
|
27 |
\emph{schematic variables} (e.g.\ @{text "?x"}). Incidently, a
|
|
28 |
universal result @{text "\<turnstile> \<And>x. B(x)"} has the canonical form @{text
|
|
29 |
"\<turnstile> B(?x)"}, which represents its generality nicely without requiring
|
|
30 |
an explicit quantifier. The same principle works for type variables
|
|
31 |
as well: @{text "\<turnstile> B(?\<alpha>)"} expresses the idea of ``@{text "\<turnstile>
|
|
32 |
\<forall>\<alpha>. B(\<alpha>)"}'' without demanding a truly polymorphic framework.
|
|
33 |
|
|
34 |
\medskip Additional care is required to treat type variables in a
|
|
35 |
way that facilitates type-inference. In principle, term variables
|
|
36 |
depend on type variables, which means that type variables would have
|
|
37 |
to be declared first. For example, a raw type-theoretic framework
|
|
38 |
would demand the context to be constructed in stages as follows:
|
|
39 |
@{text "\<Gamma> = \<alpha>: type, x: \<alpha>, a: A(x\<^isub>\<alpha>)"}.
|
|
40 |
|
|
41 |
We allow a slightly less formalistic mode of operation: term
|
|
42 |
variables @{text "x"} are fixed without specifying a type yet
|
|
43 |
(essentially \emph{all} potential occurrences of some instance
|
|
44 |
@{text "x\<^isub>\<tau>"} will be fixed); the first occurrence of @{text
|
|
45 |
"x"} within a specific term assigns its most general type, which is
|
|
46 |
then maintained consistently in the context. The above example
|
|
47 |
becomes @{text "\<Gamma> = x: term, \<alpha>: type, A(x\<^isub>\<alpha>)"}, where type
|
|
48 |
@{text "\<alpha>"} is fixed \emph{after} term @{text "x"}, and the
|
|
49 |
constraint @{text "x: \<alpha>"} is an implicit consequence of the
|
|
50 |
occurrence of @{text "x\<^isub>\<alpha>"} in the subsequent proposition.
|
|
51 |
|
|
52 |
This twist of dependencies is also accommodated by the reverse
|
|
53 |
operation of exporting results from a context: a type variable
|
|
54 |
@{text "\<alpha>"} is considered fixed as long as it occurs in some fixed
|
|
55 |
term variable of the context. For example, exporting @{text "x:
|
|
56 |
term, \<alpha>: type \<turnstile> x\<^isub>\<alpha> = x\<^isub>\<alpha>"} produces @{text "x: term \<turnstile>
|
|
57 |
x\<^isub>\<alpha> = x\<^isub>\<alpha>"} for fixed @{text "\<alpha>"} in the first step,
|
|
58 |
and @{text "\<turnstile> ?x\<^isub>?\<^isub>\<alpha> = ?x\<^isub>?\<^isub>\<alpha>"} for
|
|
59 |
schematic @{text "?x"} and @{text "?\<alpha>"} only in the second step.
|
|
60 |
|
|
61 |
\medskip The Isabelle/Isar proof context manages the gory details of
|
|
62 |
term vs.\ type variables, with high-level principles for moving the
|
|
63 |
frontier between fixed and schematic variables. By observing a
|
|
64 |
simple discipline of fixing variables and declaring terms
|
|
65 |
explicitly, the fine points are treated by the @{text "export"}
|
|
66 |
operation.
|
|
67 |
|
|
68 |
There is also a separate @{text "import"} operation makes a
|
|
69 |
generalized fact a genuine part of the context, by inventing fixed
|
|
70 |
variables for the schematic ones. The effect can be reversed by
|
|
71 |
using @{text "export"} later, with a potentially extended context,
|
|
72 |
but the result will be only equivalent modulo renaming of schematic
|
|
73 |
variables.
|
|
74 |
|
|
75 |
The @{text "focus"} operation provides a variant of @{text "import"}
|
|
76 |
for nested propositions (with explicit quantification): @{text
|
|
77 |
"\<And>x. B(x)"} is decomposed by inventing a fixed variable @{text "x"}
|
|
78 |
and for the body @{text "B(x)"}.
|
|
79 |
*}
|
20064
|
80 |
|
20026
|
81 |
text %mlref {*
|
|
82 |
\begin{mldecls}
|
20470
|
83 |
@{index_ML Variable.add_fixes: "string list -> Proof.context -> string list * Proof.context"} \\
|
|
84 |
@{index_ML Variable.invent_fixes: "string list -> Proof.context -> string list * Proof.context"} \\
|
20026
|
85 |
@{index_ML Variable.declare_term: "term -> Proof.context -> Proof.context"} \\
|
20470
|
86 |
@{index_ML Variable.declare_constraints: "term -> Proof.context -> Proof.context"} \\
|
|
87 |
@{index_ML Variable.export: "Proof.context -> Proof.context -> thm list -> thm list"} \\
|
|
88 |
@{index_ML Variable.polymorphic: "Proof.context -> term list -> term list"} \\
|
20459
|
89 |
@{index_ML Variable.import: "bool ->
|
|
90 |
thm list -> Proof.context -> ((ctyp list * cterm list) * thm list) * Proof.context"} \\
|
20470
|
91 |
@{index_ML Variable.focus: "cterm -> Proof.context -> (cterm list * cterm) * Proof.context"} \\
|
20026
|
92 |
\end{mldecls}
|
|
93 |
|
|
94 |
\begin{description}
|
|
95 |
|
20064
|
96 |
\item @{ML Variable.add_fixes}~@{text "xs ctxt"} fixes term
|
20470
|
97 |
variables @{text "xs"}, returning the resulting internal names. By
|
|
98 |
default, the internal representation coincides with the external
|
|
99 |
one, which also means that the given variables must not have been
|
|
100 |
fixed already. Within a local proof body, the given names are just
|
|
101 |
hints for newly invented Skolem variables.
|
20064
|
102 |
|
|
103 |
\item @{ML Variable.invent_fixes} is similar to @{ML
|
20470
|
104 |
Variable.add_fixes}, but always produces fresh variants of the given
|
|
105 |
hints.
|
|
106 |
|
|
107 |
\item @{ML Variable.declare_term}~@{text "t ctxt"} declares term
|
|
108 |
@{text "t"} to belong to the context. This automatically fixes new
|
|
109 |
type variables, but not term variables. Syntactic constraints for
|
|
110 |
type and term variables are declared uniformly.
|
|
111 |
|
|
112 |
\item @{ML Variable.declare_constraints}~@{text "t ctxt"} derives
|
|
113 |
type-inference information from term @{text "t"}, without making it
|
|
114 |
part of the context yet.
|
20026
|
115 |
|
20470
|
116 |
\item @{ML Variable.export}~@{text "inner outer thms"} generalizes
|
|
117 |
fixed type and term variables in @{text "thms"} according to the
|
|
118 |
difference of the @{text "inner"} and @{text "outer"} context,
|
|
119 |
following the principles sketched above.
|
|
120 |
|
|
121 |
\item @{ML Variable.polymorphic}~@{text "ctxt ts"} generalizes type
|
|
122 |
variables in @{text "ts"} as far as possible, even those occurring
|
|
123 |
in fixed term variables. The default policy of type-inference is to
|
|
124 |
fix newly introduced type variables; this is essentially reversed
|
|
125 |
with @{ML Variable.polymorphic}, the given terms are detached from
|
|
126 |
the context as far as possible.
|
|
127 |
|
|
128 |
\item @{ML Variable.import}~@{text "open thms ctxt"} augments the
|
20064
|
129 |
context by new fixes for the schematic type and term variables
|
20470
|
130 |
occurring in @{text "thms"}. The @{text "open"} flag indicates
|
20064
|
131 |
whether the fixed names should be accessible to the user, otherwise
|
|
132 |
internal names are chosen.
|
20026
|
133 |
|
20470
|
134 |
@{ML Variable.export} essentially reverses the effect of @{ML
|
|
135 |
Variable.import}, modulo renaming of schematic variables.
|
20064
|
136 |
|
20470
|
137 |
\item @{ML Variable.focus}~@{text "\<And>x\<^isub>1 \<dots>
|
|
138 |
x\<^isub>n. B(x\<^isub>1, \<dots>, x\<^isub>n)"} invents fixed variables
|
|
139 |
for @{text "x\<^isub>1, \<dots>, x\<^isub>n"} and replaces these in the
|
|
140 |
body.
|
20026
|
141 |
|
|
142 |
\end{description}
|
|
143 |
*}
|
|
144 |
|
18537
|
145 |
text FIXME
|
|
146 |
|
20451
|
147 |
|
|
148 |
section {* Assumptions *}
|
|
149 |
|
20458
|
150 |
text {*
|
|
151 |
An \emph{assumption} is a proposition that it is postulated in the
|
|
152 |
current context. Local conclusions may use assumptions as
|
|
153 |
additional facts, but this imposes implicit hypotheses that weaken
|
|
154 |
the overall statement.
|
|
155 |
|
|
156 |
Assumptions are restricted to fixed non-schematic statements, all
|
|
157 |
generality needs to be expressed by explicit quantifiers.
|
|
158 |
Nevertheless, the result will be in HHF normal form with outermost
|
|
159 |
quantifiers stripped. For example, by assuming @{text "\<And>x :: \<alpha>. P
|
|
160 |
x"} we get @{text "\<And>x :: \<alpha>. P x \<turnstile> P ?x"} for arbitrary @{text "?x"}
|
|
161 |
of the fixed type @{text "\<alpha>"}. Local derivations accumulate more
|
|
162 |
and more explicit references to hypotheses: @{text "A\<^isub>1, \<dots>,
|
|
163 |
A\<^isub>n \<turnstile> B"} where @{text "A\<^isub>1, \<dots>, A\<^isub>n"} needs to
|
|
164 |
be covered by the assumptions of the current context.
|
|
165 |
|
20459
|
166 |
\medskip The @{text "add_assms"} operation augments the context by
|
|
167 |
local assumptions, which are parameterized by an arbitrary @{text
|
|
168 |
"export"} rule (see below).
|
20458
|
169 |
|
|
170 |
The @{text "export"} operation moves facts from a (larger) inner
|
|
171 |
context into a (smaller) outer context, by discharging the
|
|
172 |
difference of the assumptions as specified by the associated export
|
|
173 |
rules. Note that the discharged portion is determined by the
|
20459
|
174 |
difference contexts, not the facts being exported! There is a
|
|
175 |
separate flag to indicate a goal context, where the result is meant
|
|
176 |
to refine an enclosing sub-goal of a structured proof state (cf.\
|
|
177 |
\secref{sec:isar-proof-state}).
|
20458
|
178 |
|
|
179 |
\medskip The most basic export rule discharges assumptions directly
|
|
180 |
by means of the @{text "\<Longrightarrow>"} introduction rule:
|
|
181 |
\[
|
|
182 |
\infer[(@{text "\<Longrightarrow>_intro"})]{@{text "\<Gamma> \\ A \<turnstile> A \<Longrightarrow> B"}}{@{text "\<Gamma> \<turnstile> B"}}
|
|
183 |
\]
|
|
184 |
|
|
185 |
The variant for goal refinements marks the newly introduced
|
|
186 |
premises, which causes the builtin goal refinement scheme of Isar to
|
|
187 |
enforce unification with local premises within the goal:
|
|
188 |
\[
|
|
189 |
\infer[(@{text "#\<Longrightarrow>_intro"})]{@{text "\<Gamma> \\ A \<turnstile> #A \<Longrightarrow> B"}}{@{text "\<Gamma> \<turnstile> B"}}
|
|
190 |
\]
|
|
191 |
|
20459
|
192 |
\medskip Alternative assumptions may perform arbitrary
|
|
193 |
transformations on export, as long as a particular portion of
|
|
194 |
hypotheses is removed from the given facts. For example, a local
|
|
195 |
definition works by fixing @{text "x"} and assuming @{text "x \<equiv> t"},
|
|
196 |
with the following export rule to reverse the effect:
|
20458
|
197 |
\[
|
|
198 |
\infer{@{text "\<Gamma> \\ x \<equiv> t \<turnstile> B t"}}{@{text "\<Gamma> \<turnstile> B x"}}
|
|
199 |
\]
|
|
200 |
|
|
201 |
\medskip The general concept supports block-structured reasoning
|
|
202 |
nicely, with arbitrary mechanisms for introducing local assumptions.
|
|
203 |
The common reasoning pattern is as follows:
|
|
204 |
|
|
205 |
\medskip
|
|
206 |
\begin{tabular}{l}
|
20459
|
207 |
@{text "add_assms e\<^isub>1 A\<^isub>1"} \\
|
20458
|
208 |
@{text "\<dots>"} \\
|
20459
|
209 |
@{text "add_assms e\<^isub>n A\<^isub>n"} \\
|
20458
|
210 |
@{text "export"} \\
|
|
211 |
\end{tabular}
|
|
212 |
\medskip
|
|
213 |
|
|
214 |
\noindent The final @{text "export"} will turn any fact @{text
|
|
215 |
"A\<^isub>1, \<dots>, A\<^isub>n \<turnstile> B"} into some @{text "\<turnstile> B'"}, by
|
|
216 |
applying the export rules @{text "e\<^isub>1, \<dots>, e\<^isub>n"}
|
|
217 |
inside-out.
|
|
218 |
*}
|
|
219 |
|
|
220 |
text %mlref {*
|
|
221 |
\begin{mldecls}
|
|
222 |
@{index_ML_type Assumption.export} \\
|
|
223 |
@{index_ML Assumption.assume: "cterm -> thm"} \\
|
|
224 |
@{index_ML Assumption.add_assms:
|
20459
|
225 |
"Assumption.export ->
|
|
226 |
cterm list -> Proof.context -> thm list * Proof.context"} \\
|
|
227 |
@{index_ML Assumption.add_assumes: "
|
|
228 |
cterm list -> Proof.context -> thm list * Proof.context"} \\
|
20458
|
229 |
@{index_ML Assumption.export: "bool -> Proof.context -> Proof.context -> thm -> thm"} \\
|
|
230 |
\end{mldecls}
|
|
231 |
|
|
232 |
\begin{description}
|
|
233 |
|
20459
|
234 |
\item @{ML_type Assumption.export} represents arbitrary export
|
|
235 |
rules, which is any function of type @{ML_type "bool -> cterm list -> thm -> thm"},
|
|
236 |
where the @{ML_type "bool"} indicates goal mode, and the @{ML_type
|
|
237 |
"cterm list"} the collection of assumptions to be discharged
|
|
238 |
simultaneously.
|
20458
|
239 |
|
20459
|
240 |
\item @{ML Assumption.assume}~@{text "A"} turns proposition @{text
|
|
241 |
"A"} into a raw assumption @{text "A \<turnstile> A'"}, where the conclusion
|
|
242 |
@{text "A'"} is in HHF normal form.
|
20458
|
243 |
|
|
244 |
\item @{ML Assumption.add_assms}~@{text "e As"} augments the context
|
20459
|
245 |
by assumptions @{text "As"} with export rule @{text "e"}. The
|
|
246 |
resulting facts are hypothetical theorems as produced by @{ML
|
|
247 |
Assumption.assume}.
|
|
248 |
|
|
249 |
\item @{ML Assumption.add_assumes}~@{text "As"} is a special case of
|
|
250 |
@{ML Assumption.add_assms} where the export rule performs @{text
|
|
251 |
"\<Longrightarrow>_intro"} or @{text "#\<Longrightarrow>_intro"}, depending on goal mode.
|
20458
|
252 |
|
|
253 |
\item @{ML Assumption.export}~@{text "is_goal inner outer th"}
|
|
254 |
exports result @{text "th"} from the the @{text "inner"} context
|
20459
|
255 |
back into the @{text "outer"} one; @{text "is_goal = true"} means
|
|
256 |
this is a goal context. The result is in HHF normal form. Note
|
|
257 |
that @{ML "ProofContext.export"} combines @{ML "Variable.export"}
|
|
258 |
and @{ML "Assumption.export"} in the canonical way.
|
20458
|
259 |
|
|
260 |
\end{description}
|
|
261 |
*}
|
20451
|
262 |
|
|
263 |
|
|
264 |
section {* Conclusions *}
|
|
265 |
|
18537
|
266 |
text {*
|
20472
|
267 |
Local results are established by monotonic reasoning from facts
|
|
268 |
within a context. This admits arbitrary combination of theorems,
|
|
269 |
e.g.\ using @{text "\<And>/\<Longrightarrow>"} elimination, resolution rules, or
|
|
270 |
equational reasoning. Unaccounted context manipulations should be
|
|
271 |
ruled out, such as raw @{text "\<And>/\<Longrightarrow>"} introduction or ad-hoc
|
|
272 |
references to free variables or assumptions not present in the proof
|
|
273 |
context.
|
18537
|
274 |
|
20472
|
275 |
\medskip The @{text "prove"} operation provides a separate interface
|
|
276 |
for structured backwards reasoning under program control, with some
|
|
277 |
explicit sanity checks of the result. The goal context can be
|
|
278 |
augmented locally by given fixed variables and assumptions, which
|
|
279 |
will be available as local facts during the proof and discharged
|
|
280 |
into implications in the result.
|
18537
|
281 |
|
20472
|
282 |
The @{text "prove_multi"} operation handles several simultaneous
|
|
283 |
claims within a single goal statement, by using meta-level
|
|
284 |
conjunction internally.
|
18537
|
285 |
|
20472
|
286 |
\medskip The tactical proof of a local claim may be structured
|
|
287 |
further by decomposing a sub-goal: @{text "(\<And>x. A(x) \<Longrightarrow> B(x)) \<Longrightarrow> \<dots>"}
|
|
288 |
is turned into @{text "B(x) \<Longrightarrow> \<dots>"} after fixing @{text "x"} and
|
|
289 |
assuming @{text "A(x)"}.
|
18537
|
290 |
*}
|
|
291 |
|
20472
|
292 |
text %mlref {*
|
|
293 |
\begin{mldecls}
|
|
294 |
@{index_ML Goal.prove: "Proof.context -> string list -> term list -> term ->
|
|
295 |
({prems: thm list, context: Proof.context} -> tactic) -> thm"} \\
|
|
296 |
@{index_ML Goal.prove_multi: "Proof.context -> string list -> term list -> term list ->
|
|
297 |
({prems: thm list, context: Proof.context} -> tactic) -> thm list"} \\
|
|
298 |
@{index_ML SUBPROOF:
|
|
299 |
"({context: Proof.context, schematics: ctyp list * cterm list,
|
|
300 |
params: cterm list, asms: cterm list, concl: cterm,
|
|
301 |
prems: thm list} -> tactic) -> Proof.context -> int -> tactic"}
|
|
302 |
\end{mldecls}
|
18537
|
303 |
|
20472
|
304 |
\begin{description}
|
18537
|
305 |
|
20472
|
306 |
\item @{ML Goal.prove}~@{text "ctxt xs As C tac"} states goal @{text
|
|
307 |
"C"} in the context of fixed variables @{text "xs"} and assumptions
|
|
308 |
@{text "As"} and applies tactic @{text "tac"} to solve it. The
|
|
309 |
latter may depend on the local assumptions being presented as facts.
|
|
310 |
The result is essentially @{text "\<And>xs. As \<Longrightarrow> C"}, but is normalized
|
|
311 |
by pulling @{text "\<And>"} before @{text "\<Longrightarrow>"} (the conclusion @{text
|
|
312 |
"C"} itself may be a rule statement), turning the quantifier prefix
|
|
313 |
into schematic variables, and generalizing implicit type-variables.
|
18537
|
314 |
|
20472
|
315 |
\item @{ML Goal.prove_multi} is simular to @{ML Goal.prove}, but
|
|
316 |
states several conclusions simultaneously. @{ML
|
|
317 |
Tactic.conjunction_tac} may be used to split these into individual
|
|
318 |
subgoals before commencing the actual proof.
|
|
319 |
|
|
320 |
\item @{ML SUBPROOF}~@{text "tac"} decomposes the structure of a
|
|
321 |
particular sub-goal, producing an extended context and a reduced
|
|
322 |
goal, which needs to be solved by the given tactic. All schematic
|
|
323 |
parameters of the goal are imported into the context as fixed ones,
|
|
324 |
which may not be instantiated in the sub-proof.
|
|
325 |
|
|
326 |
\end{description}
|
|
327 |
*}
|
18537
|
328 |
|
|
329 |
end
|