theory Basics
imports Main
begin
text‹
This chapter introduces HOL as a functional programming language and shows
how to prove properties of functional programs by induction.
\section{Basics}
\subsection{Types, Terms and Formulas}
\label{sec:TypesTermsForms}
HOL is a typed logic whose type system resembles that of functional
programming languages. Thus there are
\begin{description}
\item[base types,]
in particular @{typ bool}, the type of truth values,
@{typ nat}, the type of natural numbers ($\mathbb{N}$), and \indexed{@{typ int}}{int},
the type of mathematical integers ($\mathbb{Z}$).
\item[type constructors,]
in particular @{text list}, the type of
lists, and @{text set}, the type of sets. Type constructors are written
postfix, i.e., after their arguments. For example,
@{typ "nat list"} is the type of lists whose elements are natural numbers.
\item[function types,]
denoted by @{text"⇒"}.
\item[type variables,]
denoted by @{typ 'a}, @{typ 'b}, etc., like in ML\@.
\end{description}
Note that @{typ"'a ⇒ 'b list"} means \noquotes{@{typ[source]"'a ⇒ ('b list)"}},
not @{typ"('a ⇒ 'b) list"}: postfix type constructors have precedence
over @{text"⇒"}.
\conceptidx{Terms}{term} are formed as in functional programming by
applying functions to arguments. If @{text f} is a function of type
@{text"τ⇩1 ⇒ τ⇩2"} and @{text t} is a term of type
@{text"τ⇩1"} then @{term"f t"} is a term of type @{text"τ⇩2"}. We write @{text "t :: τ"} to mean that term @{text t} has type @{text τ}.
\begin{warn}
There are many predefined infix symbols like @{text "+"} and @{text"≤"}.
The name of the corresponding binary function is @{term"(+)"},
not just @{text"+"}. That is, @{term"x + y"} is nice surface syntax
(``syntactic sugar'') for \noquotes{@{term[source]"(+) x y"}}.
\end{warn}
HOL also supports some basic constructs from functional programming:
\begin{quote}
@{text "(if b then t⇩1 else t⇩2)"}\\
@{text "(let x = t in u)"}\\
@{text "(case t of pat⇩1 ⇒ t⇩1 | … | pat⇩n ⇒ t⇩n)"}
\end{quote}
\begin{warn}
The above three constructs must always be enclosed in parentheses
if they occur inside other constructs.
\end{warn}
Terms may also contain @{text "λ"}-abstractions. For example,
@{term "λx. x"} is the identity function.
\conceptidx{Formulas}{formula} are terms of type @{text bool}.
There are the basic constants @{term True} and @{term False} and
the usual logical connectives (in decreasing order of precedence):
@{text"¬"}, @{text"∧"}, @{text"∨"}, @{text"⟶"}.
\conceptidx{Equality}{equality} is available in the form of the infix function @{text "="}
of type @{typ "'a ⇒ 'a ⇒ bool"}. It also works for formulas, where
it means ``if and only if''.
\conceptidx{Quantifiers}{quantifier} are written @{prop"∀x. P"} and @{prop"∃x. P"}.
Isabelle automatically computes the type of each variable in a term. This is
called \concept{type inference}. Despite type inference, it is sometimes
necessary to attach an explicit \concept{type constraint} (or \concept{type
annotation}) to a variable or term. The syntax is @{text "t :: τ"} as in
\mbox{\noquotes{@{term[source] "m + (n::nat)"}}}. Type constraints may be
needed to
disambiguate terms involving overloaded functions such as @{text "+"}.
Finally there are the universal quantifier @{text"⋀"}\index{$4@\isasymAnd} and the implication
@{text"⟹"}\index{$3@\isasymLongrightarrow}. They are part of the Isabelle framework, not the logic
HOL. Logically, they agree with their HOL counterparts @{text"∀"} and
@{text"⟶"}, but operationally they behave differently. This will become
clearer as we go along.
\begin{warn}
Right-arrows of all kinds always associate to the right. In particular,
the formula
@{text"A⇩1 ⟹ A⇩2 ⟹ A⇩3"} means @{text "A⇩1 ⟹ (A⇩2 ⟹ A⇩3)"}.
The (Isabelle-specific\footnote{To display implications in this style in
Isabelle/jEdit you need to set Plugins $>$ Plugin Options $>$ Isabelle/General $>$ Print Mode to ``\texttt{brackets}'' and restart.}) notation \mbox{@{text"⟦ A⇩1; …; A⇩n ⟧ ⟹ A"}}
is short for the iterated implication \mbox{@{text"A⇩1 ⟹ … ⟹ A⇩n ⟹ A"}}.
Sometimes we also employ inference rule notation:
\inferrule{\mbox{@{text "A⇩1"}}\\ \mbox{@{text "…"}}\\ \mbox{@{text "A⇩n"}}}
{\mbox{@{text A}}}
\end{warn}
\subsection{Theories}
\label{sec:Basic:Theories}
Roughly speaking, a \concept{theory} is a named collection of types,
functions, and theorems, much like a module in a programming language.
All Isabelle text needs to go into a theory.
The general format of a theory @{text T} is
\begin{quote}
\indexed{\isacom{theory}}{theory} @{text T}\\
\indexed{\isacom{imports}}{imports} @{text "T⇩1 … T⇩n"}\\
\isacom{begin}\\
\emph{definitions, theorems and proofs}\\
\isacom{end}
\end{quote}
where @{text "T⇩1 … T⇩n"} are the names of existing
theories that @{text T} is based on. The @{text "T⇩i"} are the
direct \conceptidx{parent theories}{parent theory} of @{text T}.
Everything defined in the parent theories (and their parents, recursively) is
automatically visible. Each theory @{text T} must
reside in a \concept{theory file} named @{text "T.thy"}.
\begin{warn}
HOL contains a theory @{theory Main}\index{Main@@{theory Main}}, the union of all the basic
predefined theories like arithmetic, lists, sets, etc.
Unless you know what you are doing, always include @{text Main}
as a direct or indirect parent of all your theories.
\end{warn}
In addition to the theories that come with the Isabelle/HOL distribution
(see 🌐‹https://isabelle.in.tum.de/library/HOL›)
there is also the \emph{Archive of Formal Proofs}
at 🌐‹https://isa-afp.org›, a growing collection of Isabelle theories
that everybody can contribute to.
\subsection{Quotation Marks}
The textual definition of a theory follows a fixed syntax with keywords like
\isacommand{begin} and \isacommand{datatype}. Embedded in this syntax are
the types and formulas of HOL. To distinguish the two levels, everything
HOL-specific (terms and types) must be enclosed in quotation marks:
\texttt{"}\dots\texttt{"}. Quotation marks around a
single identifier can be dropped. When Isabelle prints a syntax error
message, it refers to the HOL syntax as the \concept{inner syntax} and the
enclosing theory language as the \concept{outer syntax}.
\ifsem\else
\subsection{Proof State}
\begin{warn}
By default Isabelle/jEdit does not show the proof state but this tutorial
refers to it frequently. You should tick the ``Proof state'' box
to see the proof state in the output window.
\end{warn}
\fi
›
end