doc-src/IsarImplementation/Thy/document/proof.tex

updated;

%
\begin{isabellebody}%
\def\isabellecontext{proof}%
%
\isadelimtheory
\isanewline
\isanewline
\isanewline
%
\endisadelimtheory
%
\isatagtheory
\isacommand{theory}\isamarkupfalse%
\ {\isachardoublequoteopen}proof{\isachardoublequoteclose}\ \isakeyword{imports}\ base\ \isakeyword{begin}%
\endisatagtheory
{\isafoldtheory}%
%
\isadelimtheory
%
\endisadelimtheory
%
\isamarkupchapter{Structured proofs%
}
\isamarkuptrue%
%
\isamarkupsection{Variables%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
Any variable that is not explicitly bound by \isa{{\isasymlambda}}-abstraction
  is considered as ``free''.  Logically, free variables act like
  outermost universal quantification (at the sequent level): \isa{A\isactrlisub {\isadigit{1}}{\isacharparenleft}x{\isacharparenright}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ A\isactrlisub n{\isacharparenleft}x{\isacharparenright}\ {\isasymturnstile}\ B{\isacharparenleft}x{\isacharparenright}} means that the result
  holds \emph{for all} values of \isa{x}.  Free variables for
  terms (not types) can be fully internalized into the logic: \isa{{\isasymturnstile}\ B{\isacharparenleft}x{\isacharparenright}} and \isa{{\isasymturnstile}\ {\isasymAnd}x{\isachardot}\ B{\isacharparenleft}x{\isacharparenright}} are interchangeable provided that
  \isa{x} does not occur elsewhere in the context.  Inspecting
  \isa{{\isasymturnstile}\ {\isasymAnd}x{\isachardot}\ B{\isacharparenleft}x{\isacharparenright}} more closely, we see that inside the
  quantifier, \isa{x} is essentially ``arbitrary, but fixed'',
  while from outside it appears as a place-holder for instantiation
  (thanks to \isa{{\isasymAnd}}-elimination).

  The Pure logic represents the notion of variables being either
  inside or outside the current scope by providing separate syntactic
  categories for \emph{fixed variables} (e.g.\ \isa{x}) vs.\
  \emph{schematic variables} (e.g.\ \isa{{\isacharquery}x}).  Incidently, a
  universal result \isa{{\isasymturnstile}\ {\isasymAnd}x{\isachardot}\ B{\isacharparenleft}x{\isacharparenright}} has the canonical form \isa{{\isasymturnstile}\ B{\isacharparenleft}{\isacharquery}x{\isacharparenright}}, which represents its generality nicely without requiring
  an explicit quantifier.  The same principle works for type variables
  as well: \isa{{\isasymturnstile}\ B{\isacharparenleft}{\isacharquery}{\isasymalpha}{\isacharparenright}} expresses the idea of ``\isa{{\isasymturnstile}\ {\isasymforall}{\isasymalpha}{\isachardot}\ B{\isacharparenleft}{\isasymalpha}{\isacharparenright}}'' without demanding a truly polymorphic framework.

  \medskip Additional care is required to treat type variables in a
  way that facilitates type-inference.  In principle, term variables
  depend on type variables, which means that type variables would have
  to be declared first.  For example, a raw type-theoretic framework
  would demand the context to be constructed in stages as follows:
  \isa{{\isasymGamma}\ {\isacharequal}\ {\isasymalpha}{\isacharcolon}\ type{\isacharcomma}\ x{\isacharcolon}\ {\isasymalpha}{\isacharcomma}\ a{\isacharcolon}\ A{\isacharparenleft}x\isactrlisub {\isasymalpha}{\isacharparenright}}.

  We allow a slightly less formalistic mode of operation: term
  variables \isa{x} are fixed without specifying a type yet
  (essentially \emph{all} potential occurrences of some instance
  \isa{x\isactrlisub {\isasymtau}} will be fixed); the first occurrence of \isa{x} within a specific term assigns its most general type, which is
  then maintained consistently in the context.  The above example
  becomes \isa{{\isasymGamma}\ {\isacharequal}\ x{\isacharcolon}\ term{\isacharcomma}\ {\isasymalpha}{\isacharcolon}\ type{\isacharcomma}\ A{\isacharparenleft}x\isactrlisub {\isasymalpha}{\isacharparenright}}, where type
  \isa{{\isasymalpha}} is fixed \emph{after} term \isa{x}, and the
  constraint \isa{x{\isacharcolon}\ {\isasymalpha}} is an implicit consequence of the
  occurrence of \isa{x\isactrlisub {\isasymalpha}} in the subsequent proposition.

  This twist of dependencies is also accommodated by the reverse
  operation of exporting results from a context: a type variable
  \isa{{\isasymalpha}} is considered fixed as long as it occurs in some fixed
  term variable of the context.  For example, exporting \isa{x{\isacharcolon}\ term{\isacharcomma}\ {\isasymalpha}{\isacharcolon}\ type\ {\isasymturnstile}\ x\isactrlisub {\isasymalpha}\ {\isacharequal}\ x\isactrlisub {\isasymalpha}} produces \isa{x{\isacharcolon}\ term\ {\isasymturnstile}\ x\isactrlisub {\isasymalpha}\ {\isacharequal}\ x\isactrlisub {\isasymalpha}} for fixed \isa{{\isasymalpha}} in the first step,
  and \isa{{\isasymturnstile}\ {\isacharquery}x\isactrlisub {\isacharquery}\isactrlisub {\isasymalpha}\ {\isacharequal}\ {\isacharquery}x\isactrlisub {\isacharquery}\isactrlisub {\isasymalpha}} for
  schematic \isa{{\isacharquery}x} and \isa{{\isacharquery}{\isasymalpha}} only in the second step.

  \medskip The Isabelle/Isar proof context manages the gory details of
  term vs.\ type variables, with high-level principles for moving the
  frontier between fixed and schematic variables.  By observing a
  simple discipline of fixing variables and declaring terms
  explicitly, the fine points are treated by the \isa{export}
  operation.

  There is also a separate \isa{import} operation makes a
  generalized fact a genuine part of the context, by inventing fixed
  variables for the schematic ones.  The effect can be reversed by
  using \isa{export} later, with a potentially extended context,
  but the result will be only equivalent modulo renaming of schematic
  variables.

  The \isa{focus} operation provides a variant of \isa{import}
  for nested propositions (with explicit quantification): \isa{{\isasymAnd}x{\isachardot}\ B{\isacharparenleft}x{\isacharparenright}} is decomposed by inventing a fixed variable \isa{x}
  and for the body \isa{B{\isacharparenleft}x{\isacharparenright}}.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isadelimmlref
%
\endisadelimmlref
%
\isatagmlref
%
\begin{isamarkuptext}%
\begin{mldecls}
  \indexml{Variable.add-fixes}\verb|Variable.add_fixes: string list -> Proof.context -> string list * Proof.context| \\
  \indexml{Variable.invent-fixes}\verb|Variable.invent_fixes: string list -> Proof.context -> string list * Proof.context| \\
  \indexml{Variable.declare-term}\verb|Variable.declare_term: term -> Proof.context -> Proof.context| \\
  \indexml{Variable.declare-constraints}\verb|Variable.declare_constraints: term -> Proof.context -> Proof.context| \\
  \indexml{Variable.export}\verb|Variable.export: Proof.context -> Proof.context -> thm list -> thm list| \\
  \indexml{Variable.polymorphic}\verb|Variable.polymorphic: Proof.context -> term list -> term list| \\
  \indexml{Variable.import}\verb|Variable.import: bool ->|\isasep\isanewline%
\verb|  thm list -> Proof.context -> ((ctyp list * cterm list) * thm list) * Proof.context| \\
  \indexml{Variable.focus}\verb|Variable.focus: cterm -> Proof.context -> (cterm list * cterm) * Proof.context| \\
  \end{mldecls}

  \begin{description}

  \item \verb|Variable.add_fixes|~\isa{xs\ ctxt} fixes term
  variables \isa{xs}, returning the resulting internal names.  By
  default, the internal representation coincides with the external
  one, which also means that the given variables must not have been
  fixed already.  Within a local proof body, the given names are just
  hints for newly invented Skolem variables.

  \item \verb|Variable.invent_fixes| is similar to \verb|Variable.add_fixes|, but always produces fresh variants of the given
  hints.

  \item \verb|Variable.declare_term|~\isa{t\ ctxt} declares term
  \isa{t} to belong to the context.  This automatically fixes new
  type variables, but not term variables.  Syntactic constraints for
  type and term variables are declared uniformly.

  \item \verb|Variable.declare_constraints|~\isa{t\ ctxt} derives
  type-inference information from term \isa{t}, without making it
  part of the context yet.

  \item \verb|Variable.export|~\isa{inner\ outer\ thms} generalizes
  fixed type and term variables in \isa{thms} according to the
  difference of the \isa{inner} and \isa{outer} context,
  following the principles sketched above.

  \item \verb|Variable.polymorphic|~\isa{ctxt\ ts} generalizes type
  variables in \isa{ts} as far as possible, even those occurring
  in fixed term variables.  The default policy of type-inference is to
  fix newly introduced type variables; this is essentially reversed
  with \verb|Variable.polymorphic|, the given terms are detached from
  the context as far as possible.

  \item \verb|Variable.import|~\isa{open\ thms\ ctxt} augments the
  context by new fixes for the schematic type and term variables
  occurring in \isa{thms}.  The \isa{open} flag indicates
  whether the fixed names should be accessible to the user, otherwise
  internal names are chosen.

  \verb|Variable.export| essentially reverses the effect of \verb|Variable.import|, modulo renaming of schematic variables.

  \item \verb|Variable.focus|~\isa{{\isasymAnd}x\isactrlisub {\isadigit{1}}\ {\isasymdots}\ x\isactrlisub n{\isachardot}\ B{\isacharparenleft}x\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ x\isactrlisub n{\isacharparenright}} invents fixed variables
  for \isa{x\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ x\isactrlisub n} and replaces these in the
  body.

  \end{description}%
\end{isamarkuptext}%
\isamarkuptrue%
%
\endisatagmlref
{\isafoldmlref}%
%
\isadelimmlref
%
\endisadelimmlref
%
\begin{isamarkuptext}%
FIXME%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsection{Assumptions%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
An \emph{assumption} is a proposition that it is postulated in the
  current context.  Local conclusions may use assumptions as
  additional facts, but this imposes implicit hypotheses that weaken
  the overall statement.

  Assumptions are restricted to fixed non-schematic statements, all
  generality needs to be expressed by explicit quantifiers.
  Nevertheless, the result will be in HHF normal form with outermost
  quantifiers stripped.  For example, by assuming \isa{{\isasymAnd}x\ {\isacharcolon}{\isacharcolon}\ {\isasymalpha}{\isachardot}\ P\ x} we get \isa{{\isasymAnd}x\ {\isacharcolon}{\isacharcolon}\ {\isasymalpha}{\isachardot}\ P\ x\ {\isasymturnstile}\ P\ {\isacharquery}x} for arbitrary \isa{{\isacharquery}x}
  of the fixed type \isa{{\isasymalpha}}.  Local derivations accumulate more
  and more explicit references to hypotheses: \isa{A\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ A\isactrlisub n\ {\isasymturnstile}\ B} where \isa{A\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ A\isactrlisub n} needs to
  be covered by the assumptions of the current context.

  \medskip The \isa{add{\isacharunderscore}assms} operation augments the context by
  local assumptions, which are parameterized by an arbitrary \isa{export} rule (see below).

  The \isa{export} operation moves facts from a (larger) inner
  context into a (smaller) outer context, by discharging the
  difference of the assumptions as specified by the associated export
  rules.  Note that the discharged portion is determined by the
  difference contexts, not the facts being exported!  There is a
  separate flag to indicate a goal context, where the result is meant
  to refine an enclosing sub-goal of a structured proof state (cf.\
  \secref{sec:isar-proof-state}).

  \medskip The most basic export rule discharges assumptions directly
  by means of the \isa{{\isasymLongrightarrow}} introduction rule:
  \[
  \infer[(\isa{{\isasymLongrightarrow}{\isacharunderscore}intro})]{\isa{{\isasymGamma}\ {\isacharbackslash}\ A\ {\isasymturnstile}\ A\ {\isasymLongrightarrow}\ B}}{\isa{{\isasymGamma}\ {\isasymturnstile}\ B}}
  \]

  The variant for goal refinements marks the newly introduced
  premises, which causes the builtin goal refinement scheme of Isar to
  enforce unification with local premises within the goal:
  \[
  \infer[(\isa{{\isacharhash}{\isasymLongrightarrow}{\isacharunderscore}intro})]{\isa{{\isasymGamma}\ {\isacharbackslash}\ A\ {\isasymturnstile}\ {\isacharhash}A\ {\isasymLongrightarrow}\ B}}{\isa{{\isasymGamma}\ {\isasymturnstile}\ B}}
  \]

  \medskip Alternative assumptions may perform arbitrary
  transformations on export, as long as a particular portion of
  hypotheses is removed from the given facts.  For example, a local
  definition works by fixing \isa{x} and assuming \isa{x\ {\isasymequiv}\ t},
  with the following export rule to reverse the effect:
  \[
  \infer{\isa{{\isasymGamma}\ {\isacharbackslash}\ x\ {\isasymequiv}\ t\ {\isasymturnstile}\ B\ t}}{\isa{{\isasymGamma}\ {\isasymturnstile}\ B\ x}}
  \]

  \medskip The general concept supports block-structured reasoning
  nicely, with arbitrary mechanisms for introducing local assumptions.
  The common reasoning pattern is as follows:

  \medskip
  \begin{tabular}{l}
  \isa{add{\isacharunderscore}assms\ e\isactrlisub {\isadigit{1}}\ A\isactrlisub {\isadigit{1}}} \\
  \isa{{\isasymdots}} \\
  \isa{add{\isacharunderscore}assms\ e\isactrlisub n\ A\isactrlisub n} \\
  \isa{export} \\
  \end{tabular}
  \medskip

  \noindent The final \isa{export} will turn any fact \isa{A\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ A\isactrlisub n\ {\isasymturnstile}\ B} into some \isa{{\isasymturnstile}\ B{\isacharprime}}, by
  applying the export rules \isa{e\isactrlisub {\isadigit{1}}{\isacharcomma}\ {\isasymdots}{\isacharcomma}\ e\isactrlisub n}
  inside-out.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isadelimmlref
%
\endisadelimmlref
%
\isatagmlref
%
\begin{isamarkuptext}%
\begin{mldecls}
  \indexmltype{Assumption.export}\verb|type Assumption.export| \\
  \indexml{Assumption.assume}\verb|Assumption.assume: cterm -> thm| \\
  \indexml{Assumption.add-assms}\verb|Assumption.add_assms: Assumption.export ->|\isasep\isanewline%
\verb|  cterm list -> Proof.context -> thm list * Proof.context| \\
  \indexml{Assumption.add-assumes}\verb|Assumption.add_assumes: |\isasep\isanewline%
\verb|  cterm list -> Proof.context -> thm list * Proof.context| \\
  \indexml{Assumption.export}\verb|Assumption.export: bool -> Proof.context -> Proof.context -> thm -> thm| \\
  \end{mldecls}

  \begin{description}

  \item \verb|Assumption.export| represents arbitrary export
  rules, which is any function of type \verb|bool -> cterm list -> thm -> thm|,
  where the \verb|bool| indicates goal mode, and the \verb|cterm list| the collection of assumptions to be discharged
  simultaneously.

  \item \verb|Assumption.assume|~\isa{A} turns proposition \isa{A} into a raw assumption \isa{A\ {\isasymturnstile}\ A{\isacharprime}}, where the conclusion
  \isa{A{\isacharprime}} is in HHF normal form.

  \item \verb|Assumption.add_assms|~\isa{e\ As} augments the context
  by assumptions \isa{As} with export rule \isa{e}.  The
  resulting facts are hypothetical theorems as produced by \verb|Assumption.assume|.

  \item \verb|Assumption.add_assumes|~\isa{As} is a special case of
  \verb|Assumption.add_assms| where the export rule performs \isa{{\isasymLongrightarrow}{\isacharunderscore}intro} or \isa{{\isacharhash}{\isasymLongrightarrow}{\isacharunderscore}intro}, depending on goal mode.

  \item \verb|Assumption.export|~\isa{is{\isacharunderscore}goal\ inner\ outer\ th}
  exports result \isa{th} from the the \isa{inner} context
  back into the \isa{outer} one; \isa{is{\isacharunderscore}goal\ {\isacharequal}\ true} means
  this is a goal context.  The result is in HHF normal form.  Note
  that \verb|ProofContext.export| combines \verb|Variable.export|
  and \verb|Assumption.export| in the canonical way.

  \end{description}%
\end{isamarkuptext}%
\isamarkuptrue%
%
\endisatagmlref
{\isafoldmlref}%
%
\isadelimmlref
%
\endisadelimmlref
%
\isamarkupsection{Conclusions%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
FIXME%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsection{Proof states \label{sec:isar-proof-state}%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
FIXME

\glossary{Proof state}{The whole configuration of a structured proof,
consisting of a \seeglossary{proof context} and an optional
\seeglossary{structured goal}.  Internally, an Isar proof state is
organized as a stack to accomodate block structure of proof texts.
For historical reasons, a low-level \seeglossary{tactical goal} is
occasionally called ``proof state'' as well.}

\glossary{Structured goal}{FIXME}

\glossary{Goal}{See \seeglossary{tactical goal} or \seeglossary{structured goal}. \norefpage}%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsection{Proof methods%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
FIXME%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsection{Attributes%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
FIXME ?!%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isadelimtheory
%
\endisadelimtheory
%
\isatagtheory
\isacommand{end}\isamarkupfalse%
%
\endisatagtheory
{\isafoldtheory}%
%
\isadelimtheory
%
\endisadelimtheory
\isanewline
\end{isabellebody}%
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "root"
%%% End: