doc-src/Logics/HOL.tex

Documents directory Induct; stylistic improvements

%% $Id$
\chapter{Higher-Order Logic}
\index{higher-order logic|(}
\index{HOL system@{\sc hol} system}

The theory~\thydx{HOL} implements higher-order logic.  It is based on
Gordon's~{\sc hol} system~\cite{mgordon-hol}, which itself is based on
Church's original paper~\cite{church40}.  Andrews's book~\cite{andrews86} is
a full description of higher-order logic.  Experience with the {\sc hol}
system has demonstrated that higher-order logic is widely applicable in many
areas of mathematics and computer science, not just hardware verification,
{\sc hol}'s original {\it raison d'\^etre\/}.  It is weaker than {\ZF} set
theory but for most applications this does not matter.  If you prefer {\ML}
to Lisp, you will probably prefer \HOL\ to~{\ZF}.

The syntax of \HOL\footnote{Earlier versions of Isabelle's \HOL\ used a
different syntax. Ancient releases of Isabelle included still another version
of~\HOL, with explicit type inference rules~\cite{paulson-COLOG}.  This
version no longer exists, but \thydx{ZF} supports a similar style of
reasoning.} follows $\lambda$-calculus and functional programming.  Function
application is curried.  To apply the function~$f$ of type
$\tau@1\To\tau@2\To\tau@3$ to the arguments~$a$ and~$b$ in \HOL, you simply
write $f\,a\,b$. There is no `apply' operator as in \thydx{ZF}. Note that
$f(a,b)$ means ``$f$ applied to the pair $(a,b)$'' in \HOL.  We write ordered
pairs as $(a,b)$, not $\langle a,b\rangle$ as in {\ZF}.

\HOL\ has a distinct feel, compared with {\ZF} and {\CTT}.  It
identifies object-level types with meta-level types, taking advantage of
Isabelle's built-in type checker.  It identifies object-level functions
with meta-level functions, so it uses Isabelle's operations for abstraction
and application.

These identifications allow Isabelle to support \HOL\ particularly nicely,
but they also mean that \HOL\ requires more sophistication from the user
--- in particular, an understanding of Isabelle's type system.  Beginners
should work with {\tt show_types} set to {\tt true}.
%  Gain experience by
%working in first-order logic before attempting to use higher-order logic.
%This chapter assumes familiarity with~{\FOL{}}.


\begin{figure}
\begin{constants}
  \it name      &\it meta-type  & \it description \\
  \cdx{Trueprop}& $bool\To prop$                & coercion to $prop$\\
  \cdx{Not}     & $bool\To bool$                & negation ($\neg$) \\
  \cdx{True}    & $bool$                        & tautology ($\top$) \\
  \cdx{False}   & $bool$                        & absurdity ($\bot$) \\
  \cdx{If}      & $[bool,\alpha,\alpha]\To\alpha$ & conditional \\
  \cdx{Let}     & $[\alpha,\alpha\To\beta]\To\beta$ & let binder
\end{constants}
\subcaption{Constants}

\begin{constants}
\index{"@@{\tt\at} symbol}
\index{*"! symbol}\index{*"? symbol}
\index{*"?"! symbol}\index{*"E"X"! symbol}
  \it symbol &\it name     &\it meta-type & \it description \\
  \tt\at & \cdx{Eps}  & $(\alpha\To bool)\To\alpha$ & 
        Hilbert description ($\varepsilon$) \\
  {\tt!~} or \sdx{ALL}  & \cdx{All}  & $(\alpha\To bool)\To bool$ & 
        universal quantifier ($\forall$) \\
  {\tt?~} or \sdx{EX}   & \cdx{Ex}   & $(\alpha\To bool)\To bool$ & 
        existential quantifier ($\exists$) \\
  {\tt?!} or {\tt EX!}  & \cdx{Ex1}  & $(\alpha\To bool)\To bool$ & 
        unique existence ($\exists!$)\\
  {\tt LEAST}  & \cdx{Least}  & $(\alpha\To bool)\To\alpha$ & 
        least element
\end{constants}
\subcaption{Binders} 

\begin{constants}
\index{*"= symbol}
\index{&@{\tt\&} symbol}
\index{*"| symbol}
\index{*"-"-"> symbol}
  \it symbol    & \it meta-type & \it priority & \it description \\ 
  \sdx{o}       & $[\beta\To\gamma,\alpha\To\beta]\To (\alpha\To\gamma)$ & 
        Left 55 & composition ($\circ$) \\
  \tt =         & $[\alpha,\alpha]\To bool$ & Left 50 & equality ($=$) \\
  \tt <         & $[\alpha::ord,\alpha]\To bool$ & Left 50 & less than ($<$) \\
  \tt <=        & $[\alpha::ord,\alpha]\To bool$ & Left 50 & 
                less than or equals ($\leq$)\\
  \tt \&        & $[bool,bool]\To bool$ & Right 35 & conjunction ($\conj$) \\
  \tt |         & $[bool,bool]\To bool$ & Right 30 & disjunction ($\disj$) \\
  \tt -->       & $[bool,bool]\To bool$ & Right 25 & implication ($\imp$)
\end{constants}
\subcaption{Infixes}
\caption{Syntax of {\tt HOL}} \label{hol-constants}
\end{figure}


\begin{figure}
\index{*let symbol}
\index{*in symbol}
\dquotes
\[\begin{array}{rclcl}
    term & = & \hbox{expression of class~$term$} \\
         & | & "\at~" id " . " formula \\
         & | & 
    \multicolumn{3}{l}{"let"~id~"="~term";"\dots";"~id~"="~term~"in"~term} \\
         & | & 
    \multicolumn{3}{l}{"if"~formula~"then"~term~"else"~term} \\
         & | & "LEAST"~ id " . " formula \\[2ex]
 formula & = & \hbox{expression of type~$bool$} \\
         & | & term " = " term \\
         & | & term " \ttilde= " term \\
         & | & term " < " term \\
         & | & term " <= " term \\
         & | & "\ttilde\ " formula \\
         & | & formula " \& " formula \\
         & | & formula " | " formula \\
         & | & formula " --> " formula \\
         & | & "!~~~" id~id^* " . " formula 
         & | & "ALL~" id~id^* " . " formula \\
         & | & "?~~~" id~id^* " . " formula 
         & | & "EX~~" id~id^* " . " formula \\
         & | & "?!~~" id~id^* " . " formula 
         & | & "EX!~" id~id^* " . " formula
  \end{array}
\]
\caption{Full grammar for \HOL} \label{hol-grammar}
\end{figure} 


\section{Syntax}

Figure~\ref{hol-constants} lists the constants (including infixes and
binders), while Fig.\ts\ref{hol-grammar} presents the grammar of
higher-order logic.  Note that $a$\verb|~=|$b$ is translated to
$\neg(a=b)$.

\begin{warn}
  \HOL\ has no if-and-only-if connective; logical equivalence is expressed
  using equality.  But equality has a high priority, as befitting a
  relation, while if-and-only-if typically has the lowest priority.  Thus,
  $\neg\neg P=P$ abbreviates $\neg\neg (P=P)$ and not $(\neg\neg P)=P$.
  When using $=$ to mean logical equivalence, enclose both operands in
  parentheses.
\end{warn}

\subsection{Types and classes}
The type class of higher-order terms is called~\cldx{term}.  By default,
explicit type variables have class \cldx{term}.  In particular the equality
symbol and quantifiers are polymorphic over class {\tt term}.

The type of formulae, \tydx{bool}, belongs to class \cldx{term}; thus,
formulae are terms.  The built-in type~\tydx{fun}, which constructs function
types, is overloaded with arity {\tt(term,term)term}.  Thus, $\sigma\To\tau$
belongs to class~{\tt term} if $\sigma$ and~$\tau$ do, allowing quantification
over functions.

HOL offers various methods for introducing new
types. See~\S\ref{sec:HOL:Types} and~\S\ref{sec:HOL:datatype}.

Theory \thydx{Ord} defines the class \cldx{ord} of all ordered types; the
relations $<$ and $\leq$ are polymorphic over this class, as are the functions
\cdx{mono}, \cdx{min} and \cdx{max}, and the least element operator
\cdx{LEAST}. \thydx{Ord} also defines the subclass \cldx{order} of \cldx{ord}
which axiomatizes partially ordered types (w.r.t.\ $\le$). 

Three other type classes --- \cldx{plus}, \cldx{minus} and \cldx{times} ---
permit overloading of the operators {\tt+},\index{*"+ symbol}
{\tt-}\index{*"- symbol} and {\tt*}.\index{*"* symbol} In particular, {\tt-}
is overloaded for set difference and subtraction.

If you state a goal containing overloaded functions, you may need to include
type constraints.  Type inference may otherwise make the goal more
polymorphic than you intended, with confusing results. For example, the
variables $i$, $j$ and $k$ in the goal $i \le j \Imp i \le j+k$ have type
$\alpha::\{ord,plus\}$, although you may have expected them to have some
numeric type, e.g. $nat$. Instead you should have stated the goal as
$(i::nat) \le j \Imp i \le j+k$, which causes all three variables to have
type $nat$.

\begin{warn}
  If resolution fails for no obvious reason, try setting
  \ttindex{show_types} to {\tt true}, causing Isabelle to display types of
  terms.  Possibly set \ttindex{show_sorts} to {\tt true} as well, causing
  Isabelle to display sorts.

  \index{unification!incompleteness of}
  Where function types are involved, Isabelle's unification code does not
  guarantee to find instantiations for type variables automatically.  Be
  prepared to use \ttindex{res_inst_tac} instead of {\tt resolve_tac},
  possibly instantiating type variables.  Setting
  \ttindex{Unify.trace_types} to {\tt true} causes Isabelle to report
  omitted search paths during unification.\index{tracing!of unification}
\end{warn}


\subsection{Binders}
Hilbert's {\bf description} operator~$\varepsilon x.P$ stands for some~$x$
satisfying~$P$, if such exists.  Since all terms in \HOL\ denote
something, a description is always meaningful, but we do not know its value
unless $P$ defines it uniquely.  We may write descriptions as
\cdx{Eps}($\lambda x.P$) or use the syntax \hbox{\tt \at $x$.$P$}.

Existential quantification is defined by
\[ \exists x.P~x \;\equiv\; P(\varepsilon x.P~x). \]
The unique existence quantifier, $\exists!x.P$, is defined in terms
of~$\exists$ and~$\forall$.  An Isabelle binder, it admits nested
quantifications.  For instance, $\exists!x\,y.P\,x\,y$ abbreviates
$\exists!x. \exists!y.P~x~y$; note that this does not mean that there
exists a unique pair $(x,y)$ satisfying~$P~x~y$.

\index{*"! symbol}\index{*"? symbol}\index{HOL system@{\sc hol} system}
Quantifiers have two notations.  As in Gordon's {\sc hol} system, \HOL\
uses~{\tt!}\ and~{\tt?}\ to stand for $\forall$ and $\exists$.  The
existential quantifier must be followed by a space; thus {\tt?x} is an
unknown, while \verb'? x.f x=y' is a quantification.  Isabelle's usual
notation for quantifiers, \sdx{ALL} and \sdx{EX}, is also
available.  Both notations are accepted for input.  The {\ML} reference
\ttindexbold{HOL_quantifiers} governs the output notation.  If set to {\tt
true}, then~{\tt!}\ and~{\tt?}\ are displayed; this is the default.  If set
to {\tt false}, then~{\tt ALL} and~{\tt EX} are displayed.

If $\tau$ is a type of class \cldx{ord}, $P$ a formula and $x$ a variable of
type $\tau$, then the term \cdx{LEAST}~$x.P~x$ denotes the least (w.r.t.\
$\le$) $x$ such that $P~x$ holds (see Fig.~\ref{hol-defs}). Note that
unless $\le$ is a linear order, the result is not uniquely defined.

All these binders have priority 10. 

\begin{warn}
The low priority of binders means that they need to be enclosed in
parenthesis when they occur in the context of other operations. For example,
instead of $P \land \forall x.Q$ you need to write $P \land (\forall x.Q)$.
\end{warn}


\subsection{The \sdx{let} and \sdx{case} constructions}
Local abbreviations can be introduced by a {\tt let} construct whose
syntax appears in Fig.\ts\ref{hol-grammar}.  Internally it is translated into
the constant~\cdx{Let}.  It can be expanded by rewriting with its
definition, \tdx{Let_def}.

\HOL\ also defines the basic syntax
\[\dquotes"case"~e~"of"~c@1~"=>"~e@1~"|" \dots "|"~c@n~"=>"~e@n\] 
as a uniform means of expressing {\tt case} constructs.  Therefore {\tt case}
and \sdx{of} are reserved words.  Initially, this is mere syntax and has no
logical meaning.  By declaring translations, you can cause instances of the
{\tt case} construct to denote applications of particular case operators.
This is what happens automatically for each {\tt datatype} declaration
(see~\S\ref{sec:HOL:datatype}).

\begin{warn}
Both {\tt if} and {\tt case} constructs have as low a priority as
quantifiers, which requires additional enclosing parenthesis in the context
of most other operations. For example, instead of $f~x = if \dots then \dots
else \dots$ you need to write $f~x = (if \dots then \dots else
\dots)$.
\end{warn}

\section{Rules of inference}

\begin{figure}
\begin{ttbox}\makeatother
\tdx{refl}           t = t
\tdx{subst}          [| s=t; P s |] ==> P t
\tdx{ext}            (!!x. f x = g x) ==> (\%x.f x) = (\%x.g x)
\tdx{impI}           (P ==> Q) ==> P-->Q
\tdx{mp}             [| P-->Q;  P |] ==> Q
\tdx{iff}            (P-->Q) --> (Q-->P) --> (P=Q)
\tdx{selectI}        P(x) ==> P(@x.P x)
\tdx{True_or_False}  (P=True) | (P=False)
\end{ttbox}
\caption{The {\tt HOL} rules} \label{hol-rules}
\end{figure}

Figure~\ref{hol-rules} shows the inference rules of~\HOL{}, with their~{\ML}
names.  Some of the rules deserve additional comments:
\begin{ttdescription}
\item[\tdx{ext}] expresses extensionality of functions.
\item[\tdx{iff}] asserts that logically equivalent formulae are
  equal.
\item[\tdx{selectI}] gives the defining property of the Hilbert
  $\varepsilon$-operator.  It is a form of the Axiom of Choice.  The derived rule
  \tdx{select_equality} (see below) is often easier to use.
\item[\tdx{True_or_False}] makes the logic classical.\footnote{In
    fact, the $\varepsilon$-operator already makes the logic classical, as
    shown by Diaconescu; see Paulson~\cite{paulson-COLOG} for details.}
\end{ttdescription}


\begin{figure}\hfuzz=4pt%suppress "Overfull \hbox" message
\begin{ttbox}\makeatother
\tdx{True_def}   True     == ((\%x::bool.x)=(\%x.x))
\tdx{All_def}    All      == (\%P. P = (\%x.True))
\tdx{Ex_def}     Ex       == (\%P. P(@x.P x))
\tdx{False_def}  False    == (!P.P)
\tdx{not_def}    not      == (\%P. P-->False)
\tdx{and_def}    op &     == (\%P Q. !R. (P-->Q-->R) --> R)
\tdx{or_def}     op |     == (\%P Q. !R. (P-->R) --> (Q-->R) --> R)
\tdx{Ex1_def}    Ex1      == (\%P. ? x. P x & (! y. P y --> y=x))

\tdx{o_def}      op o     == (\%f g x. f(g x))
\tdx{if_def}     If P x y == (\%P x y.@z.(P=True --> z=x) & (P=False --> z=y))
\tdx{Let_def}    Let s f  == f s
\tdx{Least_def}  Least P  == @x. P(x) & (ALL y. y<x --> ~P(y))
\end{ttbox}
\caption{The {\tt HOL} definitions} \label{hol-defs}
\end{figure}


\HOL{} follows standard practice in higher-order logic: only a few
connectives are taken as primitive, with the remainder defined obscurely
(Fig.\ts\ref{hol-defs}).  Gordon's {\sc hol} system expresses the
corresponding definitions \cite[page~270]{mgordon-hol} using
object-equality~({\tt=}), which is possible because equality in
higher-order logic may equate formulae and even functions over formulae.
But theory~\HOL{}, like all other Isabelle theories, uses
meta-equality~({\tt==}) for definitions.
\begin{warn}
The definitions above should never be expanded and are shown for completeness
only. Instead users should reason in terms of the derived rules shown below
or, better still, using high-level tactics
(see~\S\ref{sec:HOL:generic-packages}).
\end{warn}

Some of the rules mention type variables; for example, {\tt refl}
mentions the type variable~{\tt'a}.  This allows you to instantiate
type variables explicitly by calling {\tt res_inst_tac}.


\begin{figure}
\begin{ttbox}
\tdx{sym}         s=t ==> t=s
\tdx{trans}       [| r=s; s=t |] ==> r=t
\tdx{ssubst}      [| t=s; P s |] ==> P t
\tdx{box_equals}  [| a=b;  a=c;  b=d |] ==> c=d  
\tdx{arg_cong}    x = y ==> f x = f y
\tdx{fun_cong}    f = g ==> f x = g x
\tdx{cong}        [| f = g; x = y |] ==> f x = g y
\tdx{not_sym}     t ~= s ==> s ~= t
\subcaption{Equality}

\tdx{TrueI}       True 
\tdx{FalseE}      False ==> P

\tdx{conjI}       [| P; Q |] ==> P&Q
\tdx{conjunct1}   [| P&Q |] ==> P
\tdx{conjunct2}   [| P&Q |] ==> Q 
\tdx{conjE}       [| P&Q;  [| P; Q |] ==> R |] ==> R

\tdx{disjI1}      P ==> P|Q
\tdx{disjI2}      Q ==> P|Q
\tdx{disjE}       [| P | Q; P ==> R; Q ==> R |] ==> R

\tdx{notI}        (P ==> False) ==> ~ P
\tdx{notE}        [| ~ P;  P |] ==> R
\tdx{impE}        [| P-->Q;  P;  Q ==> R |] ==> R
\subcaption{Propositional logic}

\tdx{iffI}        [| P ==> Q;  Q ==> P |] ==> P=Q
\tdx{iffD1}       [| P=Q; P |] ==> Q
\tdx{iffD2}       [| P=Q; Q |] ==> P
\tdx{iffE}        [| P=Q; [| P --> Q; Q --> P |] ==> R |] ==> R
%
%\tdx{eqTrueI}     P ==> P=True 
%\tdx{eqTrueE}     P=True ==> P 
\subcaption{Logical equivalence}

\end{ttbox}
\caption{Derived rules for \HOL} \label{hol-lemmas1}
\end{figure}


\begin{figure}
\begin{ttbox}\makeatother
\tdx{allI}      (!!x. P x) ==> !x. P x
\tdx{spec}      !x.P x ==> P x
\tdx{allE}      [| !x.P x;  P x ==> R |] ==> R
\tdx{all_dupE}  [| !x.P x;  [| P x; !x.P x |] ==> R |] ==> R

\tdx{exI}       P x ==> ? x. P x
\tdx{exE}       [| ? x. P x; !!x. P x ==> Q |] ==> Q

\tdx{ex1I}      [| P a;  !!x. P x ==> x=a |] ==> ?! x. P x
\tdx{ex1E}      [| ?! x.P x;  !!x. [| P x;  ! y. P y --> y=x |] ==> R 
          |] ==> R

\tdx{select_equality} [| P a;  !!x. P x ==> x=a |] ==> (@x.P x) = a
\subcaption{Quantifiers and descriptions}

\tdx{ccontr}          (~P ==> False) ==> P
\tdx{classical}       (~P ==> P) ==> P
\tdx{excluded_middle} ~P | P

\tdx{disjCI}          (~Q ==> P) ==> P|Q
\tdx{exCI}            (! x. ~ P x ==> P a) ==> ? x.P x
\tdx{impCE}           [| P-->Q; ~ P ==> R; Q ==> R |] ==> R
\tdx{iffCE}           [| P=Q;  [| P;Q |] ==> R;  [| ~P; ~Q |] ==> R |] ==> R
\tdx{notnotD}         ~~P ==> P
\tdx{swap}            ~P ==> (~Q ==> P) ==> Q
\subcaption{Classical logic}

%\tdx{if_True}         (if True then x else y) = x
%\tdx{if_False}        (if False then x else y) = y
\tdx{if_P}            P ==> (if P then x else y) = x
\tdx{if_not_P}        ~ P ==> (if P then x else y) = y
\tdx{expand_if}       P(if Q then x else y) = ((Q --> P x) & (~Q --> P y))
\subcaption{Conditionals}
\end{ttbox}
\caption{More derived rules} \label{hol-lemmas2}
\end{figure}

Some derived rules are shown in Figures~\ref{hol-lemmas1}
and~\ref{hol-lemmas2}, with their {\ML} names.  These include natural rules
for the logical connectives, as well as sequent-style elimination rules for
conjunctions, implications, and universal quantifiers.  

Note the equality rules: \tdx{ssubst} performs substitution in
backward proofs, while \tdx{box_equals} supports reasoning by
simplifying both sides of an equation.

The following simple tactics are occasionally useful:
\begin{ttdescription}
\item[\ttindexbold{strip_tac} $i$] applies {\tt allI} and {\tt impI}
  repeatedly to remove all outermost universal quantifiers and implications
  from subgoal $i$.
\item[\ttindexbold{case_tac} {\tt"}$P${\tt"} $i$] performs case distinction
  on $P$ for subgoal $i$: the latter is replaced by two identical subgoals
  with the added assumptions $P$ and $\neg P$, respectively.
\end{ttdescription}


\begin{figure} 
\begin{center}
\begin{tabular}{rrr}
  \it name      &\it meta-type  & \it description \\ 
\index{{}@\verb'{}' symbol}
  \verb|{}|     & $\alpha\,set$         & the empty set \\
  \cdx{insert}  & $[\alpha,\alpha\,set]\To \alpha\,set$
        & insertion of element \\
  \cdx{Collect} & $(\alpha\To bool)\To\alpha\,set$
        & comprehension \\
  \cdx{Compl}   & $(\alpha\,set)\To\alpha\,set$
        & complement \\
  \cdx{INTER} & $[\alpha\,set,\alpha\To\beta\,set]\To\beta\,set$
        & intersection over a set\\
  \cdx{UNION} & $[\alpha\,set,\alpha\To\beta\,set]\To\beta\,set$
        & union over a set\\
  \cdx{Inter} & $(\alpha\,set)set\To\alpha\,set$
        &set of sets intersection \\
  \cdx{Union} & $(\alpha\,set)set\To\alpha\,set$
        &set of sets union \\
  \cdx{Pow}   & $\alpha\,set \To (\alpha\,set)set$
        & powerset \\[1ex]
  \cdx{range}   & $(\alpha\To\beta )\To\beta\,set$
        & range of a function \\[1ex]
  \cdx{Ball}~~\cdx{Bex} & $[\alpha\,set,\alpha\To bool]\To bool$
        & bounded quantifiers
\end{tabular}
\end{center}
\subcaption{Constants}

\begin{center}
\begin{tabular}{llrrr} 
  \it symbol &\it name     &\it meta-type & \it priority & \it description \\
  \sdx{INT}  & \cdx{INTER1}  & $(\alpha\To\beta\,set)\To\beta\,set$ & 10 & 
        intersection over a type\\
  \sdx{UN}  & \cdx{UNION1}  & $(\alpha\To\beta\,set)\To\beta\,set$ & 10 & 
        union over a type
\end{tabular}
\end{center}
\subcaption{Binders} 

\begin{center}
\index{*"`"` symbol}
\index{*": symbol}
\index{*"<"= symbol}
\begin{tabular}{rrrr} 
  \it symbol    & \it meta-type & \it priority & \it description \\ 
  \tt ``        & $[\alpha\To\beta ,\alpha\,set]\To  (\beta\,set)$
        & Left 90 & image \\
  \sdx{Int}     & $[\alpha\,set,\alpha\,set]\To\alpha\,set$
        & Left 70 & intersection ($\inter$) \\
  \sdx{Un}      & $[\alpha\,set,\alpha\,set]\To\alpha\,set$
        & Left 65 & union ($\union$) \\
  \tt:          & $[\alpha ,\alpha\,set]\To bool$       
        & Left 50 & membership ($\in$) \\
  \tt <=        & $[\alpha\,set,\alpha\,set]\To bool$
        & Left 50 & subset ($\subseteq$) 
\end{tabular}
\end{center}
\subcaption{Infixes}
\caption{Syntax of the theory {\tt Set}} \label{hol-set-syntax}
\end{figure} 


\begin{figure} 
\begin{center} \tt\frenchspacing
\index{*"! symbol}
\begin{tabular}{rrr} 
  \it external          & \it internal  & \it description \\ 
  $a$ \ttilde: $b$      & \ttilde($a$ : $b$)    & \rm non-membership\\
  \{$a@1$, $\ldots$\}  &  insert $a@1$ $\ldots$ \{\} & \rm finite set \\
  \{$x$.$P[x]$\}        &  Collect($\lambda x.P[x]$) &
        \rm comprehension \\
  \sdx{INT} $x$:$A$.$B[x]$      & INTER $A$ $\lambda x.B[x]$ &
        \rm intersection \\
  \sdx{UN}{\tt\ }  $x$:$A$.$B[x]$      & UNION $A$ $\lambda x.B[x]$ &
        \rm union \\
  \tt ! $x$:$A$.$P[x]$ or \sdx{ALL} $x$:$A$.$P[x]$ & 
        Ball $A$ $\lambda x.P[x]$ & 
        \rm bounded $\forall$ \\
  \sdx{?} $x$:$A$.$P[x]$ or \sdx{EX}{\tt\ } $x$:$A$.$P[x]$ & 
        Bex $A$ $\lambda x.P[x]$ & \rm bounded $\exists$
\end{tabular}
\end{center}
\subcaption{Translations}

\dquotes
\[\begin{array}{rclcl}
    term & = & \hbox{other terms\ldots} \\
         & | & "\{\}" \\
         & | & "\{ " term\; ("," term)^* " \}" \\
         & | & "\{ " id " . " formula " \}" \\
         & | & term " `` " term \\
         & | & term " Int " term \\
         & | & term " Un " term \\
         & | & "INT~~"  id ":" term " . " term \\
         & | & "UN~~~"  id ":" term " . " term \\
         & | & "INT~~"  id~id^* " . " term \\
         & | & "UN~~~"  id~id^* " . " term \\[2ex]
 formula & = & \hbox{other formulae\ldots} \\
         & | & term " : " term \\
         & | & term " \ttilde: " term \\
         & | & term " <= " term \\
         & | & "!~" id ":" term " . " formula 
         & | & "ALL " id ":" term " . " formula \\
         & | & "?~" id ":" term " . " formula 
         & | & "EX~~" id ":" term " . " formula
  \end{array}
\]
\subcaption{Full Grammar}
\caption{Syntax of the theory {\tt Set} (continued)} \label{hol-set-syntax2}
\end{figure} 


\section{A formulation of set theory}
Historically, higher-order logic gives a foundation for Russell and
Whitehead's theory of classes.  Let us use modern terminology and call them
{\bf sets}, but note that these sets are distinct from those of {\ZF} set
theory, and behave more like {\ZF} classes.
\begin{itemize}
\item
Sets are given by predicates over some type~$\sigma$.  Types serve to
define universes for sets, but type checking is still significant.
\item
There is a universal set (for each type).  Thus, sets have complements, and
may be defined by absolute comprehension.
\item
Although sets may contain other sets as elements, the containing set must
have a more complex type.
\end{itemize}
Finite unions and intersections have the same behaviour in \HOL\ as they
do in~{\ZF}.  In \HOL\ the intersection of the empty set is well-defined,
denoting the universal set for the given type.

\subsection{Syntax of set theory}\index{*set type}
\HOL's set theory is called \thydx{Set}.  The type $\alpha\,set$ is
essentially the same as $\alpha\To bool$.  The new type is defined for
clarity and to avoid complications involving function types in unification.
The isomorphisms between the two types are declared explicitly.  They are
very natural: {\tt Collect} maps $\alpha\To bool$ to $\alpha\,set$, while
\hbox{\tt op :} maps in the other direction (ignoring argument order).

Figure~\ref{hol-set-syntax} lists the constants, infixes, and syntax
translations.  Figure~\ref{hol-set-syntax2} presents the grammar of the new
constructs.  Infix operators include union and intersection ($A\union B$
and $A\inter B$), the subset and membership relations, and the image
operator~{\tt``}\@.  Note that $a$\verb|~:|$b$ is translated to
$\neg(a\in b)$.  

The {\tt\{\ldots\}} notation abbreviates finite sets constructed in the
obvious manner using~{\tt insert} and~$\{\}$:
\begin{eqnarray*}
  \{a@1, \ldots, a@n\}  & \equiv &  
  {\tt insert}~a@1~({\tt insert}\ldots({\tt insert}~a@n~\{\})\ldots)
\end{eqnarray*}

The set \hbox{\tt\{$x$.$P[x]$\}} consists of all $x$ (of suitable type)
that satisfy~$P[x]$, where $P[x]$ is a formula that may contain free
occurrences of~$x$.  This syntax expands to \cdx{Collect}$(\lambda
x.P[x])$.  It defines sets by absolute comprehension, which is impossible
in~{\ZF}; the type of~$x$ implicitly restricts the comprehension.

The set theory defines two {\bf bounded quantifiers}:
\begin{eqnarray*}
   \forall x\in A.P[x] &\hbox{abbreviates}& \forall x. x\in A\imp P[x] \\
   \exists x\in A.P[x] &\hbox{abbreviates}& \exists x. x\in A\conj P[x]
\end{eqnarray*}
The constants~\cdx{Ball} and~\cdx{Bex} are defined
accordingly.  Instead of {\tt Ball $A$ $P$} and {\tt Bex $A$ $P$} we may
write\index{*"! symbol}\index{*"? symbol}
\index{*ALL symbol}\index{*EX symbol} 
%
\hbox{\tt !~$x$:$A$.$P[x]$} and \hbox{\tt ?~$x$:$A$.$P[x]$}.  Isabelle's
usual quantifier symbols, \sdx{ALL} and \sdx{EX}, are also accepted
for input.  As with the primitive quantifiers, the {\ML} reference
\ttindex{HOL_quantifiers} specifies which notation to use for output.

Unions and intersections over sets, namely $\bigcup@{x\in A}B[x]$ and
$\bigcap@{x\in A}B[x]$, are written 
\sdx{UN}~\hbox{\tt$x$:$A$.$B[x]$} and
\sdx{INT}~\hbox{\tt$x$:$A$.$B[x]$}.  

Unions and intersections over types, namely $\bigcup@x B[x]$ and $\bigcap@x
B[x]$, are written \sdx{UN}~\hbox{\tt$x$.$B[x]$} and
\sdx{INT}~\hbox{\tt$x$.$B[x]$}.  They are equivalent to the previous
union and intersection operators when $A$ is the universal set.

The operators $\bigcup A$ and $\bigcap A$ act upon sets of sets.  They are
not binders, but are equal to $\bigcup@{x\in A}x$ and $\bigcap@{x\in A}x$,
respectively.



\begin{figure} \underscoreon
\begin{ttbox}
\tdx{mem_Collect_eq}    (a : \{x.P x\}) = P a
\tdx{Collect_mem_eq}    \{x.x:A\} = A

\tdx{empty_def}         \{\}          == \{x.False\}
\tdx{insert_def}        insert a B  == \{x.x=a\} Un B
\tdx{Ball_def}          Ball A P    == ! x. x:A --> P x
\tdx{Bex_def}           Bex A P     == ? x. x:A & P x
\tdx{subset_def}        A <= B      == ! x:A. x:B
\tdx{Un_def}            A Un B      == \{x.x:A | x:B\}
\tdx{Int_def}           A Int B     == \{x.x:A & x:B\}
\tdx{set_diff_def}      A - B       == \{x.x:A & x~:B\}
\tdx{Compl_def}         Compl A     == \{x. ~ x:A\}
\tdx{INTER_def}         INTER A B   == \{y. ! x:A. y: B x\}
\tdx{UNION_def}         UNION A B   == \{y. ? x:A. y: B x\}
\tdx{INTER1_def}        INTER1 B    == INTER \{x.True\} B 
\tdx{UNION1_def}        UNION1 B    == UNION \{x.True\} B 
\tdx{Inter_def}         Inter S     == (INT x:S. x)
\tdx{Union_def}         Union S     == (UN  x:S. x)
\tdx{Pow_def}           Pow A       == \{B. B <= A\}
\tdx{image_def}         f``A        == \{y. ? x:A. y=f x\}
\tdx{range_def}         range f     == \{y. ? x. y=f x\}
\end{ttbox}
\caption{Rules of the theory {\tt Set}} \label{hol-set-rules}
\end{figure}


\begin{figure} \underscoreon
\begin{ttbox}
\tdx{CollectI}        [| P a |] ==> a : \{x.P x\}
\tdx{CollectD}        [| a : \{x.P x\} |] ==> P a
\tdx{CollectE}        [| a : \{x.P x\};  P a ==> W |] ==> W

\tdx{ballI}           [| !!x. x:A ==> P x |] ==> ! x:A. P x
\tdx{bspec}           [| ! x:A. P x;  x:A |] ==> P x
\tdx{ballE}           [| ! x:A. P x;  P x ==> Q;  ~ x:A ==> Q |] ==> Q

\tdx{bexI}            [| P x;  x:A |] ==> ? x:A. P x
\tdx{bexCI}           [| ! x:A. ~ P x ==> P a;  a:A |] ==> ? x:A.P x
\tdx{bexE}            [| ? x:A. P x;  !!x. [| x:A; P x |] ==> Q  |] ==> Q
\subcaption{Comprehension and Bounded quantifiers}

\tdx{subsetI}         (!!x.x:A ==> x:B) ==> A <= B
\tdx{subsetD}         [| A <= B;  c:A |] ==> c:B
\tdx{subsetCE}        [| A <= B;  ~ (c:A) ==> P;  c:B ==> P |] ==> P

\tdx{subset_refl}     A <= A
\tdx{subset_trans}    [| A<=B;  B<=C |] ==> A<=C

\tdx{equalityI}       [| A <= B;  B <= A |] ==> A = B
\tdx{equalityD1}      A = B ==> A<=B
\tdx{equalityD2}      A = B ==> B<=A
\tdx{equalityE}       [| A = B;  [| A<=B; B<=A |] ==> P |]  ==>  P

\tdx{equalityCE}      [| A = B;  [| c:A; c:B |] ==> P;  
                           [| ~ c:A; ~ c:B |] ==> P 
                |]  ==>  P
\subcaption{The subset and equality relations}
\end{ttbox}
\caption{Derived rules for set theory} \label{hol-set1}
\end{figure}


\begin{figure} \underscoreon
\begin{ttbox}
\tdx{emptyE}   a : \{\} ==> P

\tdx{insertI1} a : insert a B
\tdx{insertI2} a : B ==> a : insert b B
\tdx{insertE}  [| a : insert b A;  a=b ==> P;  a:A ==> P |] ==> P

\tdx{ComplI}   [| c:A ==> False |] ==> c : Compl A
\tdx{ComplD}   [| c : Compl A |] ==> ~ c:A

\tdx{UnI1}     c:A ==> c : A Un B
\tdx{UnI2}     c:B ==> c : A Un B
\tdx{UnCI}     (~c:B ==> c:A) ==> c : A Un B
\tdx{UnE}      [| c : A Un B;  c:A ==> P;  c:B ==> P |] ==> P

\tdx{IntI}     [| c:A;  c:B |] ==> c : A Int B
\tdx{IntD1}    c : A Int B ==> c:A
\tdx{IntD2}    c : A Int B ==> c:B
\tdx{IntE}     [| c : A Int B;  [| c:A; c:B |] ==> P |] ==> P

\tdx{UN_I}     [| a:A;  b: B a |] ==> b: (UN x:A. B x)
\tdx{UN_E}     [| b: (UN x:A. B x);  !!x.[| x:A;  b:B x |] ==> R |] ==> R

\tdx{INT_I}    (!!x. x:A ==> b: B x) ==> b : (INT x:A. B x)
\tdx{INT_D}    [| b: (INT x:A. B x);  a:A |] ==> b: B a
\tdx{INT_E}    [| b: (INT x:A. B x);  b: B a ==> R;  ~ a:A ==> R |] ==> R

\tdx{UnionI}   [| X:C;  A:X |] ==> A : Union C
\tdx{UnionE}   [| A : Union C;  !!X.[| A:X;  X:C |] ==> R |] ==> R

\tdx{InterI}   [| !!X. X:C ==> A:X |] ==> A : Inter C
\tdx{InterD}   [| A : Inter C;  X:C |] ==> A:X
\tdx{InterE}   [| A : Inter C;  A:X ==> R;  ~ X:C ==> R |] ==> R

\tdx{PowI}     A<=B ==> A: Pow B
\tdx{PowD}     A: Pow B ==> A<=B

\tdx{imageI}   [| x:A |] ==> f x : f``A
\tdx{imageE}   [| b : f``A;  !!x.[| b=f x;  x:A |] ==> P |] ==> P

\tdx{rangeI}   f x : range f
\tdx{rangeE}   [| b : range f;  !!x.[| b=f x |] ==> P |] ==> P
\end{ttbox}
\caption{Further derived rules for set theory} \label{hol-set2}
\end{figure}


\subsection{Axioms and rules of set theory}
Figure~\ref{hol-set-rules} presents the rules of theory \thydx{Set}.  The
axioms \tdx{mem_Collect_eq} and \tdx{Collect_mem_eq} assert
that the functions {\tt Collect} and \hbox{\tt op :} are isomorphisms.  Of
course, \hbox{\tt op :} also serves as the membership relation.

All the other axioms are definitions.  They include the empty set, bounded
quantifiers, unions, intersections, complements and the subset relation.
They also include straightforward constructions on functions: image~({\tt``})
and {\tt range}.

%The predicate \cdx{inj_onto} is used for simulating type definitions.
%The statement ${\tt inj_onto}~f~A$ asserts that $f$ is injective on the
%set~$A$, which specifies a subset of its domain type.  In a type
%definition, $f$ is the abstraction function and $A$ is the set of valid
%representations; we should not expect $f$ to be injective outside of~$A$.

%\begin{figure} \underscoreon
%\begin{ttbox}
%\tdx{Inv_f_f}    inj f ==> Inv f (f x) = x
%\tdx{f_Inv_f}    y : range f ==> f(Inv f y) = y
%
%\tdx{Inv_injective}
%    [| Inv f x=Inv f y; x: range f;  y: range f |] ==> x=y
%
%
%\tdx{monoI}      [| !!A B. A <= B ==> f A <= f B |] ==> mono f
%\tdx{monoD}      [| mono f;  A <= B |] ==> f A <= f B
%
%\tdx{injI}       [| !! x y. f x = f y ==> x=y |] ==> inj f
%\tdx{inj_inverseI}              (!!x. g(f x) = x) ==> inj f
%\tdx{injD}       [| inj f; f x = f y |] ==> x=y
%
%\tdx{inj_ontoI}  (!!x y. [| f x=f y; x:A; y:A |] ==> x=y) ==> inj_onto f A
%\tdx{inj_ontoD}  [| inj_onto f A;  f x=f y;  x:A;  y:A |] ==> x=y
%
%\tdx{inj_onto_inverseI}
%    (!!x. x:A ==> g(f x) = x) ==> inj_onto f A
%\tdx{inj_onto_contraD}
%    [| inj_onto f A;  x~=y;  x:A;  y:A |] ==> ~ f x=f y
%\end{ttbox}
%\caption{Derived rules involving functions} \label{hol-fun}
%\end{figure}


\begin{figure} \underscoreon
\begin{ttbox}
\tdx{Union_upper}     B:A ==> B <= Union A
\tdx{Union_least}     [| !!X. X:A ==> X<=C |] ==> Union A <= C

\tdx{Inter_lower}     B:A ==> Inter A <= B
\tdx{Inter_greatest}  [| !!X. X:A ==> C<=X |] ==> C <= Inter A

\tdx{Un_upper1}       A <= A Un B
\tdx{Un_upper2}       B <= A Un B
\tdx{Un_least}        [| A<=C;  B<=C |] ==> A Un B <= C

\tdx{Int_lower1}      A Int B <= A
\tdx{Int_lower2}      A Int B <= B
\tdx{Int_greatest}    [| C<=A;  C<=B |] ==> C <= A Int B
\end{ttbox}
\caption{Derived rules involving subsets} \label{hol-subset}
\end{figure}


\begin{figure} \underscoreon   \hfuzz=4pt%suppress "Overfull \hbox" message
\begin{ttbox}
\tdx{Int_absorb}        A Int A = A
\tdx{Int_commute}       A Int B = B Int A
\tdx{Int_assoc}         (A Int B) Int C  =  A Int (B Int C)
\tdx{Int_Un_distrib}    (A Un B)  Int C  =  (A Int C) Un (B Int C)

\tdx{Un_absorb}         A Un A = A
\tdx{Un_commute}        A Un B = B Un A
\tdx{Un_assoc}          (A Un B)  Un C  =  A Un (B Un C)
\tdx{Un_Int_distrib}    (A Int B) Un C  =  (A Un C) Int (B Un C)

\tdx{Compl_disjoint}    A Int (Compl A) = \{x.False\}
\tdx{Compl_partition}   A Un  (Compl A) = \{x.True\}
\tdx{double_complement} Compl(Compl A) = A
\tdx{Compl_Un}          Compl(A Un B)  = (Compl A) Int (Compl B)
\tdx{Compl_Int}         Compl(A Int B) = (Compl A) Un (Compl B)

\tdx{Union_Un_distrib}  Union(A Un B) = (Union A) Un (Union B)
\tdx{Int_Union}         A Int (Union B) = (UN C:B. A Int C)
\tdx{Un_Union_image}    (UN x:C.(A x) Un (B x)) = Union(A``C) Un Union(B``C)

\tdx{Inter_Un_distrib}  Inter(A Un B) = (Inter A) Int (Inter B)
\tdx{Un_Inter}          A Un (Inter B) = (INT C:B. A Un C)
\tdx{Int_Inter_image}   (INT x:C.(A x) Int (B x)) = Inter(A``C) Int Inter(B``C)
\end{ttbox}
\caption{Set equalities} \label{hol-equalities}
\end{figure}


Figures~\ref{hol-set1} and~\ref{hol-set2} present derived rules.  Most are
obvious and resemble rules of Isabelle's {\ZF} set theory.  Certain rules,
such as \tdx{subsetCE}, \tdx{bexCI} and \tdx{UnCI},
are designed for classical reasoning; the rules \tdx{subsetD},
\tdx{bexI}, \tdx{Un1} and~\tdx{Un2} are not
strictly necessary but yield more natural proofs.  Similarly,
\tdx{equalityCE} supports classical reasoning about extensionality,
after the fashion of \tdx{iffCE}.  See the file {\tt HOL/Set.ML} for
proofs pertaining to set theory.

Figure~\ref{hol-subset} presents lattice properties of the subset relation.
Unions form least upper bounds; non-empty intersections form greatest lower
bounds.  Reasoning directly about subsets often yields clearer proofs than
reasoning about the membership relation.  See the file {\tt HOL/subset.ML}.

Figure~\ref{hol-equalities} presents many common set equalities.  They
include commutative, associative and distributive laws involving unions,
intersections and complements.  For a complete listing see the file {\tt
HOL/equalities.ML}.

\begin{warn}
\texttt{Blast_tac} proves many set-theoretic theorems automatically.
Hence you seldom need to refer to the theorems above.
\end{warn}

\begin{figure}
\begin{center}
\begin{tabular}{rrr}
  \it name      &\it meta-type  & \it description \\ 
  \cdx{inj}~~\cdx{surj}& $(\alpha\To\beta )\To bool$
        & injective/surjective \\
  \cdx{inj_onto}        & $[\alpha\To\beta ,\alpha\,set]\To bool$
        & injective over subset\\
  \cdx{inv} & $(\alpha\To\beta)\To(\beta\To\alpha)$ & inverse function
\end{tabular}
\end{center}

\underscoreon
\begin{ttbox}
\tdx{inj_def}           inj f        == ! x y. f x=f y --> x=y
\tdx{surj_def}          surj f       == ! y. ? x. y=f x
\tdx{inj_onto_def}      inj_onto f A == !x:A. !y:A. f x=f y --> x=y
\tdx{inv_def}           inv f        == (\%y. @x. f(x)=y)
\end{ttbox}
\caption{Theory \thydx{Fun}} \label{fig:HOL:Fun}
\end{figure}

\subsection{Properties of functions}\nopagebreak
Figure~\ref{fig:HOL:Fun} presents a theory of simple properties of functions.
Note that ${\tt inv}~f$ uses Hilbert's $\varepsilon$ to yield an inverse
of~$f$. See the file {\tt HOL/Fun.ML} for a complete listing of the derived
rules.  Reasoning about function composition (the operator~\sdx{o}) and the
predicate~\cdx{surj} is done simply by expanding the definitions.

There is also a large collection of monotonicity theorems for constructions
on sets in the file {\tt HOL/mono.ML}.

\section{Generic packages}
\label{sec:HOL:generic-packages}

\HOL\ instantiates most of Isabelle's generic packages, making available the
simplifier and the classical reasoner.

\subsection{Substitution and simplification}

The simplifier is available in \HOL.  Tactics such as {\tt Asm_simp_tac} and
{\tt 
Full_simp_tac} use the default simpset ({\tt!simpset}), which works for most
purposes.  A minimal simplification set for higher-order logic
is~\ttindexbold{HOL_ss}.  Equality~($=$), which also expresses logical
equivalence, may be used for rewriting.  See the file {\tt HOL/simpdata.ML}
for a complete listing of the basic simplification rules.

See \iflabelundefined{chap:classical}{the {\em Reference Manual\/}}%
{Chaps.\ts\ref{substitution} and~\ref{simp-chap}} for details of substitution
and simplification.

\begin{warn}\index{simplification!of conjunctions}%
  Reducing $a=b\conj P(a)$ to $a=b\conj P(b)$ is sometimes advantageous.  The
  left part of a conjunction helps in simplifying the right part.  This effect
  is not available by default: it can be slow.  It can be obtained by
  including \ttindex{conj_cong} in a simpset, \verb$addcongs [conj_cong]$.
\end{warn}

If the simplifier cannot use a certain rewrite rule---either because of
nontermination or because its left-hand side is too flexible---then you might
try {\tt stac}:
\begin{ttdescription}
\item[\ttindexbold{stac} $thm$ $i,$] where $thm$ is of the form $lhs = rhs$,
  replaces in subgoal $i$ instances of $lhs$ by corresponding instances of
  $rhs$. In case of multiple instances of $lhs$ in subgoal $i$, backtracking
  may be necessary to select the desired ones.

If $thm$ is a conditional equality, the instantiated condition becomes an
additional (first) subgoal.
\end{ttdescription}

 \HOL{} provides the tactic \ttindex{hyp_subst_tac}, which substitutes
  for an equality throughout a subgoal and its hypotheses.  This tactic uses
  \HOL's general substitution rule.


\subsection{Classical reasoning}

\HOL\ derives classical introduction rules for $\disj$ and~$\exists$, as
well as classical elimination rules for~$\imp$ and~$\bimp$, and the swap
rule; recall Fig.\ts\ref{hol-lemmas2} above.

The classical reasoner is installed.  Tactics such as {\tt Blast_tac} and {\tt
Best_tac} use the default claset ({\tt!claset}), which works for most
purposes.  Named clasets include \ttindexbold{prop_cs}, which includes the
propositional rules, and \ttindexbold{HOL_cs}, which also includes quantifier
rules.  See the file {\tt HOL/cladata.ML} for lists of the classical rules,
and \iflabelundefined{chap:classical}{the {\em Reference Manual\/}}%
{Chap.\ts\ref{chap:classical}} for more discussion of classical proof methods.


\section{Types}\label{sec:HOL:Types}
This section describes HOL's basic predefined types (\verb$*$, \verb$+$, {\tt
  nat} and {\tt list}) and ways for introducing new types. The most important
type construction, the {\tt datatype}, is treated separately in
\S\ref{sec:HOL:datatype}.

\subsection{Product and sum types}\index{*"* type}\index{*"+ type}
\label{subsec:prod-sum}

\begin{figure}[htbp]
\begin{constants}
  \it symbol    & \it meta-type &           & \it description \\ 
  \cdx{Pair}    & $[\alpha,\beta]\To \alpha\times\beta$
        & & ordered pairs $(a,b)$ \\
  \cdx{fst}     & $\alpha\times\beta \To \alpha$        & & first projection\\
  \cdx{snd}     & $\alpha\times\beta \To \beta$         & & second projection\\
  \cdx{split}   & $[[\alpha,\beta]\To\gamma, \alpha\times\beta] \To \gamma$ 
        & & generalized projection\\
  \cdx{Sigma}  & 
        $[\alpha\,set, \alpha\To\beta\,set]\To(\alpha\times\beta)set$ &
        & general sum of sets
\end{constants}
\begin{ttbox}\makeatletter
%\tdx{fst_def}      fst p     == @a. ? b. p = (a,b)
%\tdx{snd_def}      snd p     == @b. ? a. p = (a,b)
%\tdx{split_def}    split c p == c (fst p) (snd p)
\tdx{Sigma_def}    Sigma A B == UN x:A. UN y:B x. \{(x,y)\}

\tdx{Pair_eq}      ((a,b) = (a',b')) = (a=a' & b=b')
\tdx{Pair_inject}  [| (a, b) = (a',b');  [| a=a';  b=b' |] ==> R |] ==> R
\tdx{PairE}        [| !!x y. p = (x,y) ==> Q |] ==> Q

\tdx{fst_conv}     fst (a,b) = a
\tdx{snd_conv}     snd (a,b) = b
\tdx{surjective_pairing}  p = (fst p,snd p)

\tdx{split}        split c (a,b) = c a b
\tdx{expand_split} R(split c p) = (! x y. p = (x,y) --> R(c x y))

\tdx{SigmaI}    [| a:A;  b:B a |] ==> (a,b) : Sigma A B
\tdx{SigmaE}    [| c:Sigma A B; !!x y.[| x:A; y:B x; c=(x,y) |] ==> P |] ==> P
\end{ttbox}
\caption{Type $\alpha\times\beta$}\label{hol-prod}
\end{figure} 

Theory \thydx{Prod} (Fig.\ts\ref{hol-prod}) defines the product type
$\alpha\times\beta$, with the ordered pair syntax {\tt($a$,$b$)}. Tuples are
simulated by pairs nested to the right:
\begin{center}
\begin{tabular}{|c|c|}
\hline
external & internal \\
\hline
$\tau@1 * \dots * \tau@n$ & $\tau@1 * (\dots (\tau@{n-1} * \tau@n)\dots)$ \\
\hline
$(t@1,\dots,t@n)$ & $(t@1,(\dots,(t@{n-1},t@n)\dots)$ \\
\hline
\end{tabular}
\end{center}
In addition, it is possible to use tuples
as patterns in abstractions:
\begin{center}
{\tt\%($x$,$y$).$t$} \quad stands for\quad {\tt split(\%$x$ $y$.$t$)} 
\end{center}
Nested patterns are also supported. They are translated stepwise:
{\tt\%($x$,$y$,$z$).$t$} $\leadsto$ {\tt\%($x$,($y$,$z$)).$t$} $\leadsto$
{\tt split(\%$x$.\%($y$,$z$).$t$)} $\leadsto$ {\tt split(\%$x$.split(\%$y$
  $z$.$t$))}. The reverse translation is performed upon printing.
\begin{warn}
  The translation between patterns and {\tt split} is performed automatically
  by the parser and printer.  Thus the internal and external form of a term
  may differ, which can affects proofs.  For example the term {\tt
  (\%(x,y).(y,x))(a,b)} requires the theorem {\tt split} (which is in the
  default simpset) to rewrite to {\tt(b,a)}.
\end{warn}
In addition to explicit $\lambda$-abstractions, patterns can be used in any
variable binding construct which is internally described by a
$\lambda$-abstraction. Some important examples are
\begin{description}
\item[Let:] {\tt let {\it pattern} = $t$ in $u$}
\item[Quantifiers:] {\tt !~{\it pattern}:$A$.~$P$}
\item[Choice:] {\underscoreon \tt @~{\it pattern}~.~$P$}
\item[Set operations:] {\tt UN~{\it pattern}:$A$.~$B$}
\item[Sets:] {\tt \{~{\it pattern}~.~$P$~\}}
\end{description}

There is a simple tactic which supports reasoning about patterns:
\begin{ttdescription}
\item[\ttindexbold{split_all_tac} $i$] replaces in subgoal $i$ all
  {\tt!!}-quantified variables of product type by individual variables for
  each component. A simple example:
\begin{ttbox}
{\out 1. !!p. (\%(x,y,z). (x, y, z)) p = p}
by(split_all_tac 1);
{\out 1. !!x xa ya. (\%(x,y,z). (x, y, z)) (x, xa, ya) = (x, xa, ya)}
\end{ttbox}
\end{ttdescription}

Theory {\tt Prod} also introduces the degenerate product type {\tt unit}
which contains only a single element named {\tt()} with the property
\begin{ttbox}
\tdx{unit_eq}       u = ()
\end{ttbox}
\bigskip

Theory \thydx{Sum} (Fig.~\ref{hol-sum}) defines the sum type $\alpha+\beta$
which associates to the right and has a lower priority than $*$: $\tau@1 +
\tau@2 + \tau@3*\tau@4$ means $\tau@1 + (\tau@2 + (\tau@3*\tau@4))$.

The definition of products and sums in terms of existing types is not shown.
The constructions are fairly standard and can be found in the respective {\tt
  thy}-files.

\begin{figure}
\begin{constants}
  \it symbol    & \it meta-type &           & \it description \\ 
  \cdx{Inl}     & $\alpha \To \alpha+\beta$    & & first injection\\
  \cdx{Inr}     & $\beta \To \alpha+\beta$     & & second injection\\
  \cdx{sum_case} & $[\alpha\To\gamma, \beta\To\gamma, \alpha+\beta] \To\gamma$
        & & conditional
\end{constants}
\begin{ttbox}\makeatletter
%\tdx{sum_case_def}   sum_case == (\%f g p. @z. (!x. p=Inl x --> z=f x) &
%                                        (!y. p=Inr y --> z=g y))
%
\tdx{Inl_not_Inr}    ~ Inl a=Inr b

\tdx{inj_Inl}        inj Inl
\tdx{inj_Inr}        inj Inr

\tdx{sumE}           [| !!x. P(Inl x);  !!y. P(Inr y) |] ==> P s

\tdx{sum_case_Inl}   sum_case f g (Inl x) = f x
\tdx{sum_case_Inr}   sum_case f g (Inr x) = g x

\tdx{surjective_sum} sum_case (\%x. f(Inl x)) (\%y. f(Inr y)) s = f s
\tdx{expand_sum_case} R(sum_case f g s) = ((! x. s = Inl(x) --> R(f(x))) &
                                     (! y. s = Inr(y) --> R(g(y))))
\end{ttbox}
\caption{Type $\alpha+\beta$}\label{hol-sum}
\end{figure}

\begin{figure}
\index{*"< symbol}
\index{*"* symbol}
\index{*div symbol}
\index{*mod symbol}
\index{*"+ symbol}
\index{*"- symbol}
\begin{constants}
  \it symbol    & \it meta-type & \it priority & \it description \\ 
  \cdx{0}       & $nat$         & & zero \\
  \cdx{Suc}     & $nat \To nat$ & & successor function\\
% \cdx{nat_case} & $[\alpha, nat\To\alpha, nat] \To\alpha$ & & conditional\\
% \cdx{nat_rec} & $[nat, \alpha, [nat, \alpha]\To\alpha] \To \alpha$
%        & & primitive recursor\\
  \tt *         & $[nat,nat]\To nat$    &  Left 70      & multiplication \\
  \tt div       & $[nat,nat]\To nat$    &  Left 70      & division\\
  \tt mod       & $[nat,nat]\To nat$    &  Left 70      & modulus\\
  \tt +         & $[nat,nat]\To nat$    &  Left 65      & addition\\
  \tt -         & $[nat,nat]\To nat$    &  Left 65      & subtraction
\end{constants}
\subcaption{Constants and infixes}

\begin{ttbox}\makeatother
\tdx{nat_induct}     [| P 0; !!n. P n ==> P(Suc n) |]  ==> P n

\tdx{Suc_not_Zero}   Suc m ~= 0
\tdx{inj_Suc}        inj Suc
\tdx{n_not_Suc_n}    n~=Suc n
\subcaption{Basic properties}
\end{ttbox}
\caption{The type of natural numbers, {\tt nat}} \label{hol-nat1}
\end{figure}


\begin{figure}
\begin{ttbox}\makeatother
%\tdx{nat_case_0}     nat_case a f 0 = a
%\tdx{nat_case_Suc}   nat_case a f (Suc k) = f k
%
%\tdx{nat_rec_0}      nat_rec 0 c h = c
%\tdx{nat_rec_Suc}    nat_rec (Suc n) c h = h n (nat_rec n c h)
%
              0+n           = n
              (Suc m)+n     = Suc(m+n)
              m-0           = m
              0-n           = n
              Suc(m)-Suc(n) = m-n
              0*n           = 0
              Suc(m)*n      = n + m*n

\tdx{mod_less}      m<n ==> m mod n = m
\tdx{mod_geq}       [| 0<n;  ~m<n |] ==> m mod n = (m-n) mod n
\tdx{div_less}      m<n ==> m div n = 0
\tdx{div_geq}       [| 0<n;  ~m<n |] ==> m div n = Suc((m-n) div n)
%\subcaption{Recursion equations}
%
%\tdx{less_trans}     [| i<j;  j<k |] ==> i<k
%\tdx{lessI}          n < Suc n
%\tdx{zero_less_Suc}  0 < Suc n
%
%\tdx{less_not_sym}   n<m --> ~ m<n 
%\tdx{less_not_refl}  ~ n<n
%\tdx{not_less0}      ~ n<0
%
%\tdx{Suc_less_eq}    (Suc m < Suc n) = (m<n)
%\tdx{less_induct}    [| !!n. [| ! m. m<n --> P m |] ==> P n |]  ==>  P n
%
%\tdx{less_linear}    m<n | m=n | n<m
%\subcaption{The less-than relation}
\end{ttbox}
\caption{Recursion equations for {\tt nat}} \label{hol-nat2}
\end{figure}

\subsection{The type of natural numbers, {\tt nat}}

The theory \thydx{NatDef} defines the natural numbers in a roundabout but
traditional way.  The axiom of infinity postulates an type~\tydx{ind} of
individuals, which is non-empty and closed under an injective operation.
The natural numbers are inductively generated by choosing an arbitrary
individual for~0 and using the injective operation to take successors.  As
usual, the isomorphisms between~\tydx{nat} and its representation are made
explicitly. For details see the file {\tt NatDef.thy}.

%The definition makes use of a least fixed point operator \cdx{lfp},
%defined using the Knaster-Tarski theorem.  This is used to define the
%operator \cdx{trancl}, for taking the transitive closure of a relation.
%Primitive recursion makes use of \cdx{wfrec}, an operator for recursion
%along arbitrary well-founded relations.  The corresponding theories are
%called {\tt Lfp}, {\tt Trancl} and {\tt WF}\@.  Elsewhere I have described
%similar constructions in the context of set theory~\cite{paulson-set-II}.

Type~\tydx{nat} is an instance of class~\cldx{ord}, which makes the
overloaded functions of this class (esp.\ \cdx{<} and \cdx{<=}, but also
\cdx{min}, \cdx{max} and \cdx{LEAST}) available on {\tt nat}. Theory
\thydx{Nat} builds on {\tt NatDef} and shows that {\tt<=} is a partial order,
i.e.\ {\tt nat} is an instance of class {\tt order}.

Theory \thydx{Arith} develops arithmetic on the natural numbers.  It
defines addition, multiplication, subtraction, division, and remainder.
Many of their properties are proved: commutative, associative and
distributive laws, identity and cancellation laws, etc.
%  The most
%interesting result is perhaps the theorem $a \bmod b + (a/b)\times b = a$.
Division and remainder are defined by repeated subtraction, which requires
well-founded rather than primitive recursion.  See Figs.\ts\ref{hol-nat1}
and~\ref{hol-nat2}. The recursion equations for the operators {\tt +}, {\tt
-} and {\tt *} are part of the default simpset.

Functions on {\tt nat} can be defined by primitive recursion, for example
addition:
\begin{ttbox}
\sdx{primrec} "op +" nat 
  "0 + n = n"
  "Suc m + n = Suc(m + n)"
\end{ttbox}
(Remember that the name of an infix operator $\oplus$ is {\tt op}~$\oplus$.)
The general format for defining primitive recursive functions on {\tt nat}
follows the rules for primitive recursive functions on datatypes
(see~\S\ref{sec:HOL:primrec}).
There is also a \sdx{case}-construct of the form
\begin{ttbox}
case \(e\) of 0 => \(a\) | Suc \(m\) => \(b\)
\end{ttbox}
Note that Isabelle insists on precisely this format; you may not even change
the order of the two cases.
Both {\tt primrec} and {\tt case} are realized by a recursion operator
\cdx{nat_rec}, the details of which can be found in theory {\tt NatDef}.

%The predecessor relation, \cdx{pred_nat}, is shown to be well-founded.
%Recursion along this relation resembles primitive recursion, but is
%stronger because we are in higher-order logic; using primitive recursion to
%define a higher-order function, we can easily Ackermann's function, which
%is not primitive recursive \cite[page~104]{thompson91}.
%The transitive closure of \cdx{pred_nat} is~$<$.  Many functions on the
%natural numbers are most easily expressed using recursion along~$<$.

Tactic {\tt\ttindex{induct_tac} "$n$" $i$} performs induction on variable~$n$
in subgoal~$i$ using theorem {\tt nat_induct}. There is also the derived
theorem \tdx{less_induct}
\begin{ttbox}
[| !!n. [| ! m. m<n --> P m |] ==> P n |]  ==>  P n
\end{ttbox}


Reasoning about arithmetic inequalities can be tedious. A minimal amount of
automation is provided by the tactic \ttindex{trans_tac} of type {\tt int ->
tactic} that deals with simple inequalities. Note that it only knows about
{\tt 0}, {\tt Suc}, {\tt<} and {\tt<=}. The following goals are all solved by
{\tt trans_tac 1}:
\begin{ttbox}
{\out  1. [| \dots |] ==> m <= Suc(Suc m)}
{\out  1. [| \dots i <= j \dots Suc j <= k \dots |] ==> i < k}
{\out  1. [| \dots Suc m <= n \dots ~ m < n \dots |] ==> \dots}
\end{ttbox}
For a complete description of the limitations of the tactic and how to avoid
some of them, see the comments at the start of the file {\tt
Provers/nat_transitive.ML}.

If {\tt trans_tac} fails you, try to find relevant arithmetic results in the
library. The theory {\tt NatDef} contains theorems about {\tt<} and {\tt<=},
the theory {\tt Arith} contains theorems about {\tt +}, {\tt -}, {\tt *},
{\tt div} and {\tt mod}. Since specific results may be hard to find, we
recommend the {\tt find}-functions (see the {\em Reference Manual\/}).

\begin{figure}
\index{#@{\tt[]} symbol}
\index{#@{\tt\#} symbol}
\index{"@@{\tt\at} symbol}
\begin{constants}
  \it symbol & \it meta-type & \it priority & \it description \\
  \tt[]    & $\alpha\,list$ & & empty list\\
  \tt \#   & $[\alpha,\alpha\,list]\To \alpha\,list$ & Right 65 & 
        list constructor \\
  \cdx{null}    & $\alpha\,list \To bool$ & & emptiness test\\
  \cdx{hd}      & $\alpha\,list \To \alpha$ & & head \\
  \cdx{tl}      & $\alpha\,list \To \alpha\,list$ & & tail \\
  \cdx{ttl}     & $\alpha\,list \To \alpha\,list$ & & total tail \\
  \tt\at  & $[\alpha\,list,\alpha\,list]\To \alpha\,list$ & Left 65 & append \\
  \cdx{map}     & $(\alpha\To\beta) \To (\alpha\,list \To \beta\,list)$
        & & mapping functional\\
  \cdx{filter}  & $(\alpha \To bool) \To (\alpha\,list \To \alpha\,list)$
        & & filter functional\\
  \cdx{list_all}& $(\alpha \To bool) \To (\alpha\,list \To bool)$
        & & forall functional\\
  \cdx{set_of_list}& $\alpha\,list \To \alpha\,set$ & & elements\\
  \sdx{mem}  & $[\alpha,\alpha\,list]\To bool$    &  Left 55   & membership\\
  \cdx{foldl}   & $(\beta\To\alpha\To\beta) \To \beta \To \alpha\,list \To \beta$ &
  & iteration \\
  \cdx{concat}   & $(\alpha\,list)list\To \alpha\,list$ & & concatenation \\
  \cdx{rev}     & $\alpha\,list \To \alpha\,list$ & & reverse \\
  \cdx{length}  & $\alpha\,list \To nat$ & & length \\
  \cdx{nth}  & $nat \To \alpha\,list \To \alpha$ & & indexing \\
  \cdx{take}, \cdx{drop} & $nat \To \alpha\,list \To \alpha\,list$ &&
    take/drop prefix \\
  \cdx{takeWhile},\\
  \cdx{dropWhile} &
    $(\alpha \To bool) \To \alpha\,list \To \alpha\,list$ &&
    take/drop prefix
\end{constants}
\subcaption{Constants and infixes}

\begin{center} \tt\frenchspacing
\begin{tabular}{rrr} 
  \it external        & \it internal  & \it description \\{}
  [$x@1$, $\dots$, $x@n$]  &  $x@1$ \# $\cdots$ \# $x@n$ \# [] &
        \rm finite list \\{}
  [$x$:$l$. $P$]  & filter ($\lambda x{.}P$) $l$ & 
        \rm list comprehension
\end{tabular}
\end{center}
\subcaption{Translations}
\caption{The theory \thydx{List}} \label{hol-list}
\end{figure}


\begin{figure}
\begin{ttbox}\makeatother
null [] = True
null (x#xs) = False

hd (x#xs) = x
tl (x#xs) = xs

[] @ ys = ys
(x#xs) @ ys = x # xs @ ys

map f [] = []
map f (x#xs) = f x # map f xs

filter P [] = []
filter P (x#xs) = (if P x then x#filter P xs else filter P xs)

set_of_list [] = \{\}
set_of_list (x#xs) = insert x (set_of_list xs)

x mem [] = False
x mem (y#ys) = (if y=x then True else x mem ys)

foldl f a [] = a
foldl f a (x#xs) = foldl f (f a x) xs

concat([]) = []
concat(x#xs) = x @ concat(xs)

rev([]) = []
rev(x#xs) = rev(xs) @ [x]

length([]) = 0
length(x#xs) = Suc(length(xs))

nth 0 xs = hd xs
nth (Suc n) xs = nth n (tl xs)

take n [] = []
take n (x#xs) = (case n of 0 => [] | Suc(m) => x # take m xs)

drop n [] = []
drop n (x#xs) = (case n of 0 => x#xs | Suc(m) => drop m xs)

takeWhile P [] = []
takeWhile P (x#xs) = (if P x then x#takeWhile P xs else [])

dropWhile P [] = []
dropWhile P (x#xs) = (if P x then dropWhile P xs else xs)
\end{ttbox}
\caption{Recursions equations for list processing functions}
\label{fig:HOL:list-simps}
\end{figure}


\subsection{The type constructor for lists, {\tt list}}
\index{*list type}

Figure~\ref{hol-list} presents the theory \thydx{List}: the basic list
operations with their types and syntax. The type constructor {\tt list} is
defined as a {\tt datatype} with the constructors {\tt[]} and {\tt\#}.  As a
result the generic induction tactic \ttindex{induct_tac} also performs
structural induction over lists. A \sdx{case} construct of the form
\begin{center}\tt
case $e$ of [] => $a$  |  \(x\)\#\(xs\) => b
\end{center}
is defined by translation. For details see~\S\ref{sec:HOL:datatype}.

{\tt List} provides a basic library of list processing functions defined by
primitive recursion (see~\S\ref{sec:HOL:primrec}). The recursion equations
are shown in Fig.\ts\ref{fig:HOL:list-simps}.


\subsection{Introducing new types}

The \HOL-methodology dictates that all extension to a theory should be
conservative and thus preserve consistency. There are two basic type
extension mechanisms which meet this criterion: {\em type synonyms\/} and
{\em type definitions\/}. The former are inherited from {\tt Pure} and are
described elsewhere.
\begin{warn}
  Types in \HOL\ must be non-empty; otherwise the quantifier rules would be
  unsound, because $\exists x. x=x$ is a theorem \cite[\S7]{paulson-COLOG}.
\end{warn}
A \bfindex{type definition} identifies the new type with a subset of an
existing type. More precisely, the new type is defined by exhibiting an
existing type~$\tau$, a set~$A::(\tau)set$, and a theorem of the form $x:A$.
Thus~$A$ is a non-empty subset of~$\tau$, and the new type denotes this
subset.  New functions are defined that establish an isomorphism between the
new type and the subset.  If type~$\tau$ involves type variables $\alpha@1$,
\ldots, $\alpha@n$, then the type definition creates a type constructor
$(\alpha@1,\ldots,\alpha@n)ty$ rather than a particular type.

\begin{figure}[htbp]
\begin{rail}
typedef  : 'typedef' ( () | '(' tname ')') type '=' set witness;
type    : typevarlist name ( () | '(' infix ')' );
tname   : name;
set     : string;
witness : () | '(' id ')';
\end{rail}
\caption{Syntax of type definition}
\label{fig:HOL:typedef}
\end{figure}

The syntax for type definitions is shown in Fig.~\ref{fig:HOL:typedef}. For
the definition of `typevarlist' and `infix' see
\iflabelundefined{chap:classical}
{the appendix of the {\em Reference Manual\/}}%
{Appendix~\ref{app:TheorySyntax}}. The remaining nonterminals have the
following meaning:
\begin{description}
\item[\it type]: the new type constructor $(\alpha@1,\dots,\alpha@n)ty$ with
  optional infix annotation.
\item[\it tname]: an alphanumeric name $T$ for the type constructor $ty$, in
  case $ty$ is a symbolic name. Default: $ty$.
\item[\it set]: the representing subset $A$.
\item[\it witness]: name of a theorem of the form $a:A$ proving
  non-emptiness. Can be omitted in case Isabelle manages to prove
  non-emptiness automatically.
\end{description}
If all context conditions are met (no duplicate type variables in
`typevarlist', no extra type variables in `set', and no free term variables
in `set'), the following components are added to the theory:
\begin{itemize}
\item a type $ty :: (term,\dots)term$;
\item constants
\begin{eqnarray*}
T &::& (\tau)set \\
Rep_T &::& (\alpha@1,\dots,\alpha@n)ty \To \tau \\
Abs_T &::& \tau \To (\alpha@1,\dots,\alpha@n)ty
\end{eqnarray*}
\item a definition and three axioms
\[
\begin{array}{ll}
T{\tt_def} & T \equiv A \\
{\tt Rep_}T & Rep_T(x) : T \\
{\tt Rep_}T{\tt_inverse} & Abs_T(Rep_T(x)) = x \\
{\tt Abs_}T{\tt_inverse} & y:T \Imp Rep_T(Abs_T(y)) = y
\end{array}
\]
stating that $(\alpha@1,\dots,\alpha@n)ty$ is isomorphic to $A$ by $Rep_T$
and its inverse $Abs_T$.
\end{itemize}
Here are two simple examples where emptiness is proved automatically:
\begin{ttbox}
typedef unit = "\{True\}"

typedef (prod)
  ('a, 'b) "*"    (infixr 20)
      = "\{f . EX (a::'a) (b::'b). f = (\%x y. x = a & y = b)\}"
\end{ttbox}

Type definitions permit the introduction of abstract data types in a safe
way, namely by providing models based on already existing types. Given some
abstract axiomatic description $P$ of a type, this involves two steps:
\begin{enumerate}
\item Find an appropriate type $\tau$ and subset $A$ which has the desired
  properties $P$, and make a type definition based on this representation.
\item Prove that $P$ holds for $ty$ by lifting $P$ from the representation.
\end{enumerate}
You can now forget about the representation and work solely in terms of the
abstract properties $P$.

\begin{warn}
If you introduce a new type (constructor) $ty$ axiomatically, i.e.\ by
declaring the type and its operations and by stating the desired axioms, you
should make sure the type has a non-empty model. You must also have a clause
\par
\begin{ttbox}
arities \(ty\): (term,\(\dots\),term)term
\end{ttbox}
in your theory file to tell Isabelle that $ty$ is in class {\tt term}, the
class of all HOL types.
\end{warn}

\section{Datatype declarations}
\label{sec:HOL:datatype}
\index{*datatype|(}

It is often necessary to extend a theory with \ML-like datatypes.  This
extension consists of the new type, declarations of its constructors and
rules that describe the new type. The theory definition section {\tt
datatype} automates this.


\subsection{Foundations}

\underscoreon

A datatype declaration has the following general structure:
\[ \mbox{\tt datatype}~ (\alpha_1,\dots,\alpha_n)t ~=~
      C_1~\tau_{11}~\dots~\tau_{1k_1} ~\mid~ \dots ~\mid~
      C_m~\tau_{m1}~\dots~\tau_{mk_m} 
\]
where $\alpha_i$ are type variables, $C_i$ are distinct constructor names and
$\tau_{ij}$ are one of the following:
\begin{itemize}
\item type variables $\alpha_1,\dots,\alpha_n$,
\item types $(\beta_1,\dots,\beta_l)s$ where $s$ is a previously declared
  type or type synonym and $\{\beta_1,\dots,\beta_l\} \subseteq
  \{\alpha_1,\dots,\alpha_n\}$,
\item the newly defined type $(\alpha_1,\dots,\alpha_n)t$ \footnote{This
    makes it a recursive type. To ensure that the new type is not empty at
    least one constructor must consist of only non-recursive type
    components.}
\end{itemize}
If you would like one of the $\tau_{ij}$ to be a complex type expression
$\tau$ you need to declare a new type synonym $syn = \tau$ first and use
$syn$ in place of $\tau$. Of course this does not work if $\tau$ mentions the
recursive type itself, thus ruling out problematic cases like \[ \mbox{\tt
  datatype}~ t ~=~ C(t \To t) \] together with unproblematic ones like \[
\mbox{\tt datatype}~ t ~=~ C(t~list). \]

The constructors are automatically defined as functions of their respective
type:
\[ C_j : [\tau_{j1},\dots,\tau_{jk_j}] \To (\alpha_1,\dots,\alpha_n)t \]
These functions have certain {\em freeness} properties:
\begin{description}
\item[\tt distinct] They are distinct:
\[ C_i~x_1~\dots~x_{k_i} \neq C_j~y_1~\dots~y_{k_j} \qquad
   \mbox{for all}~ i \neq j.
\]
\item[\tt inject] They are injective:
\[ (C_j~x_1~\dots~x_{k_j} = C_j~y_1~\dots~y_{k_j}) =
   (x_1 = y_1 \land \dots \land x_{k_j} = y_{k_j})
\]
\end{description}
Because the number of inequalities is quadratic in the number of
constructors, a different method is used if their number exceeds
a certain value, currently 6. In that case every constructor is mapped to a
natural number
\[
\begin{array}{lcl}
\mbox{\it t\_ord}(C_1~x_1~\dots~x_{k_1}) & = & 0 \\
& \vdots & \\
\mbox{\it t\_ord}(C_m x_1~\dots~x_{k_m}) & = & m-1
\end{array}
\]
and distinctness of constructors is expressed by:
\[
\mbox{\it t\_ord}~x \neq \mbox{\it t\_ord}~y \Imp x \neq y.
\]
In addition a structural induction axiom {\tt induct} is provided: 
\[
\infer{P x}
{\begin{array}{lcl}
\Forall x_1\dots x_{k_1}.
  \List{P~x_{r_{11}}; \dots; P~x_{r_{1l_1}}} &
  \Imp  & P(C_1~x_1~\dots~x_{k_1}) \\
 & \vdots & \\
\Forall x_1\dots x_{k_m}.
  \List{P~x_{r_{m1}}; \dots; P~x_{r_{ml_m}}} &
  \Imp & P(C_m~x_1~\dots~x_{k_m})
\end{array}}
\]
where $\{r_{j1},\dots,r_{jl_j}\} = \{i \in \{1,\dots k_j\} ~\mid~ \tau_{ji}
= (\alpha_1,\dots,\alpha_n)t \}$, i.e.\ the property $P$ can be assumed for
all arguments of the recursive type.

The type also comes with an \ML-like \sdx{case}-construct:
\[
\begin{array}{rrcl}
\mbox{\tt case}~e~\mbox{\tt of} & C_1~x_{11}~\dots~x_{1k_1} & \To & e_1 \\
                           \vdots \\
                           \mid & C_m~x_{m1}~\dots~x_{mk_m} & \To & e_m
\end{array}
\]
where the $x_{ij}$ are either identifiers or nested tuple patterns as in
\S\ref{subsec:prod-sum}.
\begin{warn}
In contrast to \ML, {\em all} constructors must be present, their order is
fixed, and nested patterns are not supported (with the exception of tuples).
Violating this restriction results in strange error messages.
\end{warn}

\underscoreoff

\subsection{Defining datatypes}

A datatype is defined in a theory definition file using the keyword {\tt
  datatype}. The definition following {\tt datatype} must conform to the
syntax of {\em typedecl} specified in Fig.~\ref{datatype-grammar} and must
obey the rules in the previous section. As a result the theory is extended
with the new type, the constructors, and the theorems listed in the previous
section.

\begin{figure}
\begin{rail}
typedecl : typevarlist id '=' (cons + '|')
         ;
cons     : name (typ *) ( () | mixfix )
         ;
typ      : id | tid | ('(' typevarlist id ')')
         ;
\end{rail}
\caption{Syntax of datatype declarations}
\label{datatype-grammar}
\end{figure}

\begin{warn}
  If there are 7 or more constructors, the {\it t\_ord} scheme is used for
  distinctness theorems.  In this case the theory {\tt Arith} must be
  contained in the current theory, if necessary by including it explicitly.
\end{warn}

Most of the theorems about the datatype become part of the default simpset
and you never need to see them again because the simplifier applies them
automatically. Only induction is invoked by hand:
\begin{ttdescription}
\item[\ttindexbold{induct_tac} {\tt"}$x${\tt"} $i$]
 applies structural induction on variable $x$ to subgoal $i$, provided the
 type of $x$ is a datatype or type {\tt nat}.
\end{ttdescription}

For the technically minded, we give a more detailed description.
Reading the theory file produces a structure which, in addition to the usual
components, contains a structure named $t$ for each datatype $t$ defined in
the file.\footnote{Otherwise multiple datatypes in the same theory file would
  lead to name clashes.} Each structure $t$ contains the following elements:
\begin{ttbox}
val distinct : thm list
val inject : thm list
val induct : thm
val cases : thm list
val simps : thm list
val induct_tac : string -> int -> tactic
\end{ttbox}
{\tt distinct}, {\tt inject} and {\tt induct} contain the theorems described
above. For convenience {\tt distinct} contains inequalities in both
directions.  The reduction rules of the {\tt case}-construct are in {\tt
cases}.  All theorems from {\tt distinct}, {\tt inject} and {\tt cases} are
combined in {\tt simps}.

\subsection{Examples}

\subsubsection{The datatype $\alpha~list$}

We want to define the type $\alpha~list$.\footnote{Of course there is a list
  type in HOL already. This is only an example.} To do this we have to build
a new theory that contains the type definition. We start from {\tt HOL}.
\begin{ttbox}
MyList = HOL +
  datatype 'a list = Nil | Cons 'a ('a list)
end
\end{ttbox}
After loading the theory (\verb$use_thy "MyList"$), we can prove
$Cons~x~xs\neq xs$.  
\begin{ttbox}
goal MyList.thy "!x. Cons x xs ~= xs";
{\out Level 0}
{\out ! x. Cons x xs ~= xs}
{\out  1. ! x. Cons x xs ~= xs}
\end{ttbox}
This can be proved by the structural induction tactic:
\begin{ttbox}
by (induct_tac "xs" 1);
{\out Level 1}
{\out ! x. Cons x xs ~= xs}
{\out  1. ! x. Cons x Nil ~= Nil}
{\out  2. !!a list.}
{\out        ! x. Cons x list ~= list ==>}
{\out        ! x. Cons x (Cons a list) ~= Cons a list}
\end{ttbox}
The first subgoal can be proved using the simplifier.
Isabelle has already added the freeness properties of lists to the 
default simplification set.
\begin{ttbox}
by (Simp_tac 1);
{\out Level 2}
{\out ! x. Cons x xs ~= xs}
{\out  1. !!a list.}
{\out        ! x. Cons x list ~= list ==>}
{\out        ! x. Cons x (Cons a list) ~= Cons a list}
\end{ttbox}
Similarly, we prove the remaining goal.
\begin{ttbox}
by (Asm_simp_tac 1);
{\out Level 3}
{\out ! x. Cons x xs ~= xs}
{\out No subgoals!}
\end{ttbox}
Because both subgoals were proved by almost the same tactic we could have
done that in one step using
\begin{ttbox}
by (ALLGOALS Asm_simp_tac);
\end{ttbox}


\subsubsection{The datatype $\alpha~list$ with mixfix syntax}

In this example we define the type $\alpha~list$ again but this time we want
to write {\tt []} instead of {\tt Nil} and we want to use the infix operator
\verb|#| instead of {\tt Cons}. To do this we simply add mixfix annotations
after the constructor declarations as follows:
\begin{ttbox}
MyList = HOL +
  datatype 'a list = "[]" ("[]") 
                   | "#" 'a ('a list) (infixr 70)
end
\end{ttbox}
Now the theorem in the previous example can be written \verb|x#xs ~= xs|. The
proof is the same.


\subsubsection{A datatype for weekdays}

This example shows a datatype that consists of more than 6 constructors:
\begin{ttbox}
Days = Arith +
  datatype days = Mo | Tu | We | Th | Fr | Sa | So
end
\end{ttbox}
Because there are more than 6 constructors, the theory must be based on
{\tt Arith}.  Inequality is defined via a function \verb|days_ord|.  The
theorem \verb|Mo ~= Tu| is not directly contained among the distinctness
theorems, but the simplifier can prove it thanks to rewrite rules inherited
from theory {\tt Arith}.
\begin{ttbox}
goal Days.thy "Mo ~= Tu";
by (Simp_tac 1);
\end{ttbox}
You need not derive such inequalities explicitly: the simplifier will dispose
of them automatically.


\subsection{Primitive recursive functions}
\label{sec:HOL:primrec}
\index{primitive recursion|(}
\index{*primrec|(}

Datatypes come with a uniform way of defining functions, {\bf primitive
  recursion}. Although it is possible to define primitive recursive functions
by asserting their reduction rules as new axioms, e.g.\
\begin{ttbox}
Append = MyList +
consts app :: ['a list,'a list] => 'a list
rules 
   app_Nil   "app [] ys = ys"
   app_Cons  "app (x#xs) ys = x#app xs ys"
end
\end{ttbox}
this carries with it the danger of accidentally asserting an inconsistency,
as in \verb$app [] ys = us$. Therefore primitive recursive functions on
datatypes can be defined with a special syntax:
\begin{ttbox}
Append = MyList +
consts app :: ['a list,'a list] => 'a list
primrec app MyList.list
   "app [] ys = ys"
   "app (x#xs) ys = x#app xs ys"
end
\end{ttbox}
Isabelle will now check that the two rules do indeed form a primitive
recursive definition, thus ensuring that consistency is maintained. For
example
\begin{ttbox}
primrec app MyList.list
    "app [] ys = us"
\end{ttbox}
is rejected:
\begin{ttbox}
Extra variables on rhs
\end{ttbox}
\bigskip

The general form of a primitive recursive definition is
\begin{ttbox}
primrec {\it function} {\it type}
    {\it reduction rules}
\end{ttbox}
where
\begin{itemize}
\item {\it function} is the name of the function, either as an {\it id} or a
  {\it string}. The function must already have been declared.
\item {\it type} is the name of the datatype, either as an {\it id} or in the
  long form {\it Thy.t}, where {\it Thy} is the name of the parent theory the
  datatype was declared in, and $t$ the name of the datatype. The long form
  is required if the {\tt datatype} and the {\tt primrec} sections are in
  different theories.
\item {\it reduction rules} specify one or more equations of the form \[
  f~x@1~\dots~x@m~(C~y@1~\dots~y@k)~z@1~\dots~z@n = r \] such that $C$ is a
  constructor of the datatype, $r$ contains only the free variables on the
  left-hand side, and all recursive calls in $r$ are of the form
  $f~\dots~y@i~\dots$ for some $i$. There must be exactly one reduction rule
  for each constructor. The order is immaterial. {\em All reduction rules are
  added to the default {\tt simpset}.}

  If you would like to refer to some rule explicitly, you have to prefix each
  rule with an identifier (like in the {\tt rules} section of the first {\tt
  Append} theory above) that will serve as the name of the corresponding
  theorem at the \ML\ level.
\end{itemize}
A theory file may contain any number of {\tt primrec} sections which may be
intermixed with other declarations.

For the consistency-conscious user it may be reassuring to know that {\tt
  primrec} does not assert the reduction rules as new axioms but derives them
as theorems from an explicit definition of the recursive function in terms of
a recursion operator on the datatype.

The primitive recursive function can have infix or mixfix syntax:
\begin{ttbox}\underscoreon
Append = MyList +
consts "@"  :: ['a list,'a list] => 'a list  (infixr 60)
primrec "op @" MyList.list
   "[] @ ys = ys"
   "(x#xs) @ ys = x#(xs @ ys)"
end
\end{ttbox}

The reduction rules for {\tt\at} become part of the default simpset, which
leads to short proofs:
\begin{ttbox}\underscoreon
goal Append.thy "(xs @ ys) @ zs = xs @ (ys @ zs)";
by (induct\_tac "xs" 1);
by (ALLGOALS Asm\_simp\_tac);
\end{ttbox}

%Note that underdefined primitive recursive functions are allowed:
%\begin{ttbox}
%Tl = MyList +
%consts tl  :: 'a list => 'a list
%primrec tl MyList.list
%   tl_Cons "tl(x#xs) = xs"
%end
%\end{ttbox}
%Nevertheless {\tt tl} is total, although we do not know what the result of
%\verb$tl([])$ is.

\index{primitive recursion|)}
\index{*primrec|)}
\index{*datatype|)}


\section{Inductive and coinductive definitions}
\index{*inductive|(}
\index{*coinductive|(}

An {\bf inductive definition} specifies the least set~$R$ closed under given
rules.  (Applying a rule to elements of~$R$ yields a result within~$R$.)  For
example, a structural operational semantics is an inductive definition of an
evaluation relation.  Dually, a {\bf coinductive definition} specifies the
greatest set~$R$ consistent with given rules.  (Every element of~$R$ can be
seen as arising by applying a rule to elements of~$R$.)  An important example
is using bisimulation relations to formalize equivalence of processes and
infinite data structures.

A theory file may contain any number of inductive and coinductive
definitions.  They may be intermixed with other declarations; in
particular, the (co)inductive sets {\bf must} be declared separately as
constants, and may have mixfix syntax or be subject to syntax translations.

Each (co)inductive definition adds definitions to the theory and also
proves some theorems.  Each definition creates an ML structure, which is a
substructure of the main theory structure.

This package is derived from the ZF one, described in a
separate paper,\footnote{It appeared in CADE~\cite{paulson-CADE} and a
  longer version is distributed with Isabelle.} which you should refer to
in case of difficulties.  The package is simpler than ZF's thanks to HOL's
automatic type-checking.  The type of the (co)inductive determines the
domain of the fixedpoint definition, and the package does not use inference
rules for type-checking.


\subsection{The result structure}
Many of the result structure's components have been discussed in the paper;
others are self-explanatory.
\begin{description}
\item[\tt thy] is the new theory containing the recursive sets.

\item[\tt defs] is the list of definitions of the recursive sets.

\item[\tt mono] is a monotonicity theorem for the fixedpoint operator.

\item[\tt unfold] is a fixedpoint equation for the recursive set (the union of
the recursive sets, in the case of mutual recursion).

\item[\tt intrs] is the list of introduction rules, now proved as theorems, for
the recursive sets.  The rules are also available individually, using the
names given them in the theory file. 

\item[\tt elim] is the elimination rule.

\item[\tt mk_cases] is a function to create simplified instances of {\tt
elim}, using freeness reasoning on some underlying datatype.
\end{description}

For an inductive definition, the result structure contains two induction
rules, {\tt induct} and \verb|mutual_induct|.  (To save storage, the latter
rule is just {\tt True} unless more than one set is being defined.)  For a
coinductive definition, it contains the rule \verb|coinduct|.

Figure~\ref{def-result-fig} summarizes the two result signatures,
specifying the types of all these components.

\begin{figure}
\begin{ttbox}
sig
val thy          : theory
val defs         : thm list
val mono         : thm
val unfold       : thm
val intrs        : thm list
val elim         : thm
val mk_cases     : thm list -> string -> thm
{\it(Inductive definitions only)} 
val induct       : thm
val mutual_induct: thm
{\it(Coinductive definitions only)}
val coinduct    : thm
end
\end{ttbox}
\hrule
\caption{The result of a (co)inductive definition} \label{def-result-fig}
\end{figure}

\subsection{The syntax of a (co)inductive definition}
An inductive definition has the form
\begin{ttbox}
inductive    {\it inductive sets}
  intrs      {\it introduction rules}
  monos      {\it monotonicity theorems}
  con_defs   {\it constructor definitions}
\end{ttbox}
A coinductive definition is identical, except that it starts with the keyword
{\tt coinductive}.  

The {\tt monos} and {\tt con_defs} sections are optional.  If present,
each is specified as a string, which must be a valid ML expression of type
{\tt thm list}.  It is simply inserted into the {\tt .thy.ML} file; if it
is ill-formed, it will trigger ML error messages.  You can then inspect the
file on your directory.

\begin{itemize}
\item The {\it inductive sets} are specified by one or more strings.

\item The {\it introduction rules} specify one or more introduction rules in
  the form {\it ident\/}~{\it string}, where the identifier gives the name of
  the rule in the result structure.

\item The {\it monotonicity theorems} are required for each operator
  applied to a recursive set in the introduction rules.  There {\bf must}
  be a theorem of the form $A\subseteq B\Imp M(A)\subseteq M(B)$, for each
  premise $t\in M(R@i)$ in an introduction rule!

\item The {\it constructor definitions} contain definitions of constants
  appearing in the introduction rules.  In most cases it can be omitted.
\end{itemize}

The package has a few notable restrictions:
\begin{itemize}
\item The theory must separately declare the recursive sets as
  constants.

\item The names of the recursive sets must be identifiers, not infix
operators.  

\item Side-conditions must not be conjunctions.  However, an introduction rule
may contain any number of side-conditions.

\item Side-conditions of the form $x=t$, where the variable~$x$ does not
  occur in~$t$, will be substituted through the rule \verb|mutual_induct|.
\end{itemize}


\subsection{Example of an inductive definition}
Two declarations, included in a theory file, define the finite powerset
operator.  First we declare the constant~{\tt Fin}.  Then we declare it
inductively, with two introduction rules:
\begin{ttbox}
consts Fin :: 'a set => 'a set set
inductive "Fin A"
  intrs
    emptyI  "\{\} : Fin A"
    insertI "[| a: A;  b: Fin A |] ==> insert a b : Fin A"
\end{ttbox}
The resulting theory structure contains a substructure, called~{\tt Fin}.
It contains the {\tt Fin}$~A$ introduction rules as the list {\tt Fin.intrs},
and also individually as {\tt Fin.emptyI} and {\tt Fin.consI}.  The induction
rule is {\tt Fin.induct}.

For another example, here is a theory file defining the accessible part of a
relation.  The main thing to note is the use of~{\tt Pow} in the sole
introduction rule, and the corresponding mention of the rule
\verb|Pow_mono| in the {\tt monos} list.  The paper discusses a ZF version
of this example in more detail.
\begin{ttbox}
Acc = WF + 
consts pred :: "['b, ('a * 'b)set] => 'a set"   (*Set of predecessors*)
       acc  :: "('a * 'a)set => 'a set"         (*Accessible part*)
defs   pred_def  "pred x r == {y. (y,x):r}"
inductive "acc r"
  intrs
     pred "pred a r: Pow(acc r) ==> a: acc r"
  monos   "[Pow_mono]"
end
\end{ttbox}
The HOL distribution contains many other inductive definitions.  Simple
examples are collected on subdirectory \texttt{Induct}.  The theory {\tt
  HOL/Induct/LList.thy} contains coinductive definitions.  Larger examples may
be found on other subdirectories, such as {\tt IMP}, {\tt Lambda} and {\tt
  Auth}.

\index{*coinductive|)} \index{*inductive|)}


\section{The examples directories}

Directory {\tt HOL/Auth} contains theories for proving the correctness of 
cryptographic protocols.  The approach is based upon operational 
semantics~\cite{paulson-security} rather than the more usual belief logics.
On the same directory are proofs for some standard examples, such as the 
Needham-Schroeder public-key authentication protocol~\cite{paulson-ns} 
and the Otway-Rees protocol.

Directory {\tt HOL/IMP} contains a formalization of various denotational,
operational and axiomatic semantics of a simple while-language, the necessary
equivalence proofs, soundness and completeness of the Hoare rules with respect
to the 
denotational semantics, and soundness and completeness of a verification
condition generator. Much of development is taken from
Winskel~\cite{winskel93}. For details see~\cite{nipkow-IMP}.

Directory {\tt HOL/Hoare} contains a user friendly surface syntax for Hoare
logic, including a tactic for generating verification-conditions.

Directory {\tt HOL/MiniML} contains a formalization of the type system of the
core functional language Mini-ML and a correctness proof for its type
inference algorithm $\cal W$~\cite{milner78,nazareth-nipkow}.

Directory {\tt HOL/Lambda} contains a formalization of untyped
$\lambda$-calculus in de~Bruijn notation and Church-Rosser proofs for $\beta$
and $\eta$ reduction~\cite{Nipkow-CR}.

Directory {\tt HOL/Subst} contains Martin Coen's mechanisation of a theory of
substitutions and unifiers.  It is based on Paulson's previous
mechanisation in {\LCF}~\cite{paulson85} of Manna and Waldinger's
theory~\cite{mw81}. 

Directory {\tt HOL/Induct} presents simple examples of (co)inductive
definitions.  
\begin{itemize}
\item Theory {\tt PropLog} proves the soundness and completeness of
  classical propositional logic, given a truth table semantics.  The only
  connective is $\imp$.  A Hilbert-style axiom system is specified, and its
  set of theorems defined inductively.  A similar proof in \ZF{} is
  described elsewhere~\cite{paulson-set-II}.

\item Theory {\tt Term} develops an experimental recursive type definition;
  the recursion goes through the type constructor~\tydx{list}.

\item Theory {\tt Simult} constructs mutually recursive sets of trees and
  forests, including induction and recursion rules.

\item The definition of lazy lists demonstrates methods for handling
  infinite data structures and coinduction in higher-order
  logic~\cite{paulson-coind}.%
\footnote{To be precise, these lists are \emph{potentially infinite} rather
  than lazy.  Lazy implies a particular operational semantics.}
  Theory \thydx{LList} defines an operator for
  corecursion on lazy lists, which is used to define a few simple functions
  such as map and append.   A coinduction principle is defined
  for proving equations on lazy lists.
  
\item Theory \thydx{LFilter} defines the filter functional for lazy lists.
  This functional is notoriously difficult to define because finding the next
  element meeting the predicate requires possibly unlimited search.  It is not
  computable, but can be expressed using a combination of induction and
  corecursion.  

\item Theory \thydx{Exp} illustrates the use of iterated inductive definitions
  to express a programming language semantics that appears to require mutual
  induction.  Iterated induction allows greater modularity.
\end{itemize}

Directory {\tt HOL/ex} contains other examples and experimental proofs in
{\HOL}.  
\begin{itemize}
\item File {\tt cla.ML} demonstrates the classical reasoner on over sixty
  predicate calculus theorems, ranging from simple tautologies to
  moderately difficult problems involving equality and quantifiers.

\item File {\tt meson.ML} contains an experimental implementation of the {\sc
    meson} proof procedure, inspired by Plaisted~\cite{plaisted90}.  It is
  much more powerful than Isabelle's classical reasoner.  But it is less
  useful in practice because it works only for pure logic; it does not
  accept derived rules for the set theory primitives, for example.

\item File {\tt mesontest.ML} contains test data for the {\sc meson} proof
  procedure.  These are mostly taken from Pelletier \cite{pelletier86}.

\item File {\tt set.ML} proves Cantor's Theorem, which is presented in
  \S\ref{sec:hol-cantor} below, and the Schr\"oder-Bernstein Theorem.

\item Theory {\tt MT} contains Jacob Frost's formalization~\cite{frost93} of
  Milner and Tofte's coinduction example~\cite{milner-coind}.  This
  substantial proof concerns the soundness of a type system for a simple
  functional language.  The semantics of recursion is given by a cyclic
  environment, which makes a coinductive argument appropriate.
\end{itemize}


\goodbreak
\section{Example: Cantor's Theorem}\label{sec:hol-cantor}
Cantor's Theorem states that every set has more subsets than it has
elements.  It has become a favourite example in higher-order logic since
it is so easily expressed:
\[  \forall f::[\alpha,\alpha]\To bool. \exists S::\alpha\To bool.
    \forall x::\alpha. f~x \not= S 
\] 
%
Viewing types as sets, $\alpha\To bool$ represents the powerset
of~$\alpha$.  This version states that for every function from $\alpha$ to
its powerset, some subset is outside its range.  

The Isabelle proof uses \HOL's set theory, with the type $\alpha\,set$ and
the operator \cdx{range}.  The set~$S$ is given as an unknown instead of a
quantified variable so that we may inspect the subset found by the proof.
\begin{ttbox}
goal Set.thy "~ ?S : range(f :: 'a=>'a set)";
{\out Level 0}
{\out ~ ?S : range f}
{\out  1. ~ ?S : range f}
\end{ttbox}
The first two steps are routine.  The rule \tdx{rangeE} replaces
$\Var{S}\in {\tt range} f$ by $\Var{S}=f~x$ for some~$x$.
\begin{ttbox}
by (resolve_tac [notI] 1);
{\out Level 1}
{\out ~ ?S : range f}
{\out  1. ?S : range f ==> False}
\ttbreak
by (eresolve_tac [rangeE] 1);
{\out Level 2}
{\out ~ ?S : range f}
{\out  1. !!x. ?S = f x ==> False}
\end{ttbox}
Next, we apply \tdx{equalityCE}, reasoning that since $\Var{S}=f~x$,
we have $\Var{c}\in \Var{S}$ if and only if $\Var{c}\in f~x$ for
any~$\Var{c}$.
\begin{ttbox}
by (eresolve_tac [equalityCE] 1);
{\out Level 3}
{\out ~ ?S : range f}
{\out  1. !!x. [| ?c3 x : ?S; ?c3 x : f x |] ==> False}
{\out  2. !!x. [| ~ ?c3 x : ?S; ~ ?c3 x : f x |] ==> False}
\end{ttbox}
Now we use a bit of creativity.  Suppose that~$\Var{S}$ has the form of a
comprehension.  Then $\Var{c}\in\{x.\Var{P}~x\}$ implies
$\Var{P}~\Var{c}$.   Destruct-resolution using \tdx{CollectD}
instantiates~$\Var{S}$ and creates the new assumption.
\begin{ttbox}
by (dresolve_tac [CollectD] 1);
{\out Level 4}
{\out ~ \{x. ?P7 x\} : range f}
{\out  1. !!x. [| ?c3 x : f x; ?P7(?c3 x) |] ==> False}
{\out  2. !!x. [| ~ ?c3 x : \{x. ?P7 x\}; ~ ?c3 x : f x |] ==> False}
\end{ttbox}
Forcing a contradiction between the two assumptions of subgoal~1 completes
the instantiation of~$S$.  It is now the set $\{x. x\not\in f~x\}$, which
is the standard diagonal construction.
\begin{ttbox}
by (contr_tac 1);
{\out Level 5}
{\out ~ \{x. ~ x : f x\} : range f}
{\out  1. !!x. [| ~ x : \{x. ~ x : f x\}; ~ x : f x |] ==> False}
\end{ttbox}
The rest should be easy.  To apply \tdx{CollectI} to the negated
assumption, we employ \ttindex{swap_res_tac}:
\begin{ttbox}
by (swap_res_tac [CollectI] 1);
{\out Level 6}
{\out ~ \{x. ~ x : f x\} : range f}
{\out  1. !!x. [| ~ x : f x; ~ False |] ==> ~ x : f x}
\ttbreak
by (assume_tac 1);
{\out Level 7}
{\out ~ \{x. ~ x : f x\} : range f}
{\out No subgoals!}
\end{ttbox}
How much creativity is required?  As it happens, Isabelle can prove this
theorem automatically.  The default classical set {\tt!claset} contains rules
for most of the constructs of \HOL's set theory.  We must augment it with
\tdx{equalityCE} to break up set equalities, and then apply best-first
search.  Depth-first search would diverge, but best-first search
successfully navigates through the large search space.
\index{search!best-first}
\begin{ttbox}
choplev 0;
{\out Level 0}
{\out ~ ?S : range f}
{\out  1. ~ ?S : range f}
\ttbreak
by (best_tac (!claset addSEs [equalityCE]) 1);
{\out Level 1}
{\out ~ \{x. ~ x : f x\} : range f}
{\out No subgoals!}
\end{ttbox}
If you run this example interactively, make sure your current theory contains
theory {\tt Set}, for example by executing
\ttindex{set_current_thy}~{\tt"Set"}. Otherwise the default claset may not
contain the rules for set theory.
\index{higher-order logic|)}