src/Doc/Implementation/Proof.thy
changeset 61477 e467ae7aa808
parent 61458 987533262fc2
child 61493 0debd22f0c0e
equal deleted inserted replaced
61476:1884c40f1539 61477:e467ae7aa808
     9 text \<open>
     9 text \<open>
    10   Any variable that is not explicitly bound by @{text "\<lambda>"}-abstraction
    10   Any variable that is not explicitly bound by @{text "\<lambda>"}-abstraction
    11   is considered as ``free''.  Logically, free variables act like
    11   is considered as ``free''.  Logically, free variables act like
    12   outermost universal quantification at the sequent level: @{text
    12   outermost universal quantification at the sequent level: @{text
    13   "A\<^sub>1(x), \<dots>, A\<^sub>n(x) \<turnstile> B(x)"} means that the result
    13   "A\<^sub>1(x), \<dots>, A\<^sub>n(x) \<turnstile> B(x)"} means that the result
    14   holds \emph{for all} values of @{text "x"}.  Free variables for
    14   holds \<^emph>\<open>for all\<close> values of @{text "x"}.  Free variables for
    15   terms (not types) can be fully internalized into the logic: @{text
    15   terms (not types) can be fully internalized into the logic: @{text
    16   "\<turnstile> B(x)"} and @{text "\<turnstile> \<And>x. B(x)"} are interchangeable, provided
    16   "\<turnstile> B(x)"} and @{text "\<turnstile> \<And>x. B(x)"} are interchangeable, provided
    17   that @{text "x"} does not occur elsewhere in the context.
    17   that @{text "x"} does not occur elsewhere in the context.
    18   Inspecting @{text "\<turnstile> \<And>x. B(x)"} more closely, we see that inside the
    18   Inspecting @{text "\<turnstile> \<And>x. B(x)"} more closely, we see that inside the
    19   quantifier, @{text "x"} is essentially ``arbitrary, but fixed'',
    19   quantifier, @{text "x"} is essentially ``arbitrary, but fixed'',
    20   while from outside it appears as a place-holder for instantiation
    20   while from outside it appears as a place-holder for instantiation
    21   (thanks to @{text "\<And>"} elimination).
    21   (thanks to @{text "\<And>"} elimination).
    22 
    22 
    23   The Pure logic represents the idea of variables being either inside
    23   The Pure logic represents the idea of variables being either inside
    24   or outside the current scope by providing separate syntactic
    24   or outside the current scope by providing separate syntactic
    25   categories for \emph{fixed variables} (e.g.\ @{text "x"}) vs.\
    25   categories for \<^emph>\<open>fixed variables\<close> (e.g.\ @{text "x"}) vs.\
    26   \emph{schematic variables} (e.g.\ @{text "?x"}).  Incidently, a
    26   \<^emph>\<open>schematic variables\<close> (e.g.\ @{text "?x"}).  Incidently, a
    27   universal result @{text "\<turnstile> \<And>x. B(x)"} has the HHF normal form @{text
    27   universal result @{text "\<turnstile> \<And>x. B(x)"} has the HHF normal form @{text
    28   "\<turnstile> B(?x)"}, which represents its generality without requiring an
    28   "\<turnstile> B(?x)"}, which represents its generality without requiring an
    29   explicit quantifier.  The same principle works for type variables:
    29   explicit quantifier.  The same principle works for type variables:
    30   @{text "\<turnstile> B(?\<alpha>)"} represents the idea of ``@{text "\<turnstile> \<forall>\<alpha>. B(\<alpha>)"}''
    30   @{text "\<turnstile> B(?\<alpha>)"} represents the idea of ``@{text "\<turnstile> \<forall>\<alpha>. B(\<alpha>)"}''
    31   without demanding a truly polymorphic framework.
    31   without demanding a truly polymorphic framework.
    38   would demand the context to be constructed in stages as follows:
    38   would demand the context to be constructed in stages as follows:
    39   @{text "\<Gamma> = \<alpha>: type, x: \<alpha>, a: A(x\<^sub>\<alpha>)"}.
    39   @{text "\<Gamma> = \<alpha>: type, x: \<alpha>, a: A(x\<^sub>\<alpha>)"}.
    40 
    40 
    41   We allow a slightly less formalistic mode of operation: term
    41   We allow a slightly less formalistic mode of operation: term
    42   variables @{text "x"} are fixed without specifying a type yet
    42   variables @{text "x"} are fixed without specifying a type yet
    43   (essentially \emph{all} potential occurrences of some instance
    43   (essentially \<^emph>\<open>all\<close> potential occurrences of some instance
    44   @{text "x\<^sub>\<tau>"} are fixed); the first occurrence of @{text "x"}
    44   @{text "x\<^sub>\<tau>"} are fixed); the first occurrence of @{text "x"}
    45   within a specific term assigns its most general type, which is then
    45   within a specific term assigns its most general type, which is then
    46   maintained consistently in the context.  The above example becomes
    46   maintained consistently in the context.  The above example becomes
    47   @{text "\<Gamma> = x: term, \<alpha>: type, A(x\<^sub>\<alpha>)"}, where type @{text
    47   @{text "\<Gamma> = x: term, \<alpha>: type, A(x\<^sub>\<alpha>)"}, where type @{text
    48   "\<alpha>"} is fixed \emph{after} term @{text "x"}, and the constraint
    48   "\<alpha>"} is fixed \<^emph>\<open>after\<close> term @{text "x"}, and the constraint
    49   @{text "x :: \<alpha>"} is an implicit consequence of the occurrence of
    49   @{text "x :: \<alpha>"} is an implicit consequence of the occurrence of
    50   @{text "x\<^sub>\<alpha>"} in the subsequent proposition.
    50   @{text "x\<^sub>\<alpha>"} in the subsequent proposition.
    51 
    51 
    52   This twist of dependencies is also accommodated by the reverse
    52   This twist of dependencies is also accommodated by the reverse
    53   operation of exporting results from a context: a type variable
    53   operation of exporting results from a context: a type variable
   217 
   217 
   218 
   218 
   219 section \<open>Assumptions \label{sec:assumptions}\<close>
   219 section \<open>Assumptions \label{sec:assumptions}\<close>
   220 
   220 
   221 text \<open>
   221 text \<open>
   222   An \emph{assumption} is a proposition that it is postulated in the
   222   An \<^emph>\<open>assumption\<close> is a proposition that it is postulated in the
   223   current context.  Local conclusions may use assumptions as
   223   current context.  Local conclusions may use assumptions as
   224   additional facts, but this imposes implicit hypotheses that weaken
   224   additional facts, but this imposes implicit hypotheses that weaken
   225   the overall statement.
   225   the overall statement.
   226 
   226 
   227   Assumptions are restricted to fixed non-schematic statements, i.e.\
   227   Assumptions are restricted to fixed non-schematic statements, i.e.\