10762
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
|
3 |
\def\isabellecontext{Mutual}%
|
11866
|
4 |
\isamarkupfalse%
|
10762
|
5 |
%
|
10878
|
6 |
\isamarkupsubsection{Mutually Inductive Definitions%
|
10762
|
7 |
}
|
11866
|
8 |
\isamarkuptrue%
|
10762
|
9 |
%
|
|
10 |
\begin{isamarkuptext}%
|
|
11 |
Just as there are datatypes defined by mutual recursion, there are sets defined
|
10790
|
12 |
by mutual induction. As a trivial example we consider the even and odd
|
|
13 |
natural numbers:%
|
10762
|
14 |
\end{isamarkuptext}%
|
11866
|
15 |
\isamarkuptrue%
|
10762
|
16 |
\isacommand{consts}\ even\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}nat\ set{\isachardoublequote}\isanewline
|
|
17 |
\ \ \ \ \ \ \ odd\ \ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}nat\ set{\isachardoublequote}\isanewline
|
|
18 |
\isanewline
|
11866
|
19 |
\isamarkupfalse%
|
10762
|
20 |
\isacommand{inductive}\ even\ odd\isanewline
|
|
21 |
\isakeyword{intros}\isanewline
|
|
22 |
zero{\isacharcolon}\ \ {\isachardoublequote}{\isadigit{0}}\ {\isasymin}\ even{\isachardoublequote}\isanewline
|
|
23 |
evenI{\isacharcolon}\ {\isachardoublequote}n\ {\isasymin}\ odd\ {\isasymLongrightarrow}\ Suc\ n\ {\isasymin}\ even{\isachardoublequote}\isanewline
|
11866
|
24 |
oddI{\isacharcolon}\ \ {\isachardoublequote}n\ {\isasymin}\ even\ {\isasymLongrightarrow}\ Suc\ n\ {\isasymin}\ odd{\isachardoublequote}\isamarkupfalse%
|
|
25 |
%
|
10762
|
26 |
\begin{isamarkuptext}%
|
|
27 |
\noindent
|
10790
|
28 |
The mutually inductive definition of multiple sets is no different from
|
|
29 |
that of a single set, except for induction: just as for mutually recursive
|
|
30 |
datatypes, induction needs to involve all the simultaneously defined sets. In
|
|
31 |
the above case, the induction rule is called \isa{even{\isacharunderscore}odd{\isachardot}induct}
|
|
32 |
(simply concatenate the names of the sets involved) and has the conclusion
|
10762
|
33 |
\begin{isabelle}%
|
|
34 |
\ \ \ \ \ {\isacharparenleft}{\isacharquery}x\ {\isasymin}\ even\ {\isasymlongrightarrow}\ {\isacharquery}P\ {\isacharquery}x{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}{\isacharquery}y\ {\isasymin}\ odd\ {\isasymlongrightarrow}\ {\isacharquery}Q\ {\isacharquery}y{\isacharparenright}%
|
|
35 |
\end{isabelle}
|
|
36 |
|
11494
|
37 |
If we want to prove that all even numbers are divisible by two, we have to
|
10790
|
38 |
generalize the statement as follows:%
|
10762
|
39 |
\end{isamarkuptext}%
|
11866
|
40 |
\isamarkuptrue%
|
|
41 |
\isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}m\ {\isasymin}\ even\ {\isasymlongrightarrow}\ {\isadigit{2}}\ dvd\ m{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}n\ {\isasymin}\ odd\ {\isasymlongrightarrow}\ {\isadigit{2}}\ dvd\ {\isacharparenleft}Suc\ n{\isacharparenright}{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
42 |
%
|
10762
|
43 |
\begin{isamarkuptxt}%
|
|
44 |
\noindent
|
10790
|
45 |
The proof is by rule induction. Because of the form of the induction theorem,
|
|
46 |
it is applied by \isa{rule} rather than \isa{erule} as for ordinary
|
|
47 |
inductive definitions:%
|
10762
|
48 |
\end{isamarkuptxt}%
|
11866
|
49 |
\isamarkuptrue%
|
|
50 |
\isacommand{apply}{\isacharparenleft}rule\ even{\isacharunderscore}odd{\isachardot}induct{\isacharparenright}\isamarkupfalse%
|
|
51 |
%
|
10762
|
52 |
\begin{isamarkuptxt}%
|
|
53 |
\begin{isabelle}%
|
|
54 |
\ {\isadigit{1}}{\isachardot}\ {\isadigit{2}}\ dvd\ {\isadigit{0}}\isanewline
|
|
55 |
\ {\isadigit{2}}{\isachardot}\ {\isasymAnd}n{\isachardot}\ {\isasymlbrakk}n\ {\isasymin}\ odd{\isacharsemicolon}\ {\isadigit{2}}\ dvd\ Suc\ n{\isasymrbrakk}\ {\isasymLongrightarrow}\ {\isadigit{2}}\ dvd\ Suc\ n\isanewline
|
14470
|
56 |
\ {\isadigit{3}}{\isachardot}\ {\isasymAnd}n{\isachardot}\ {\isasymlbrakk}n\ {\isasymin}\ Mutual{\isachardot}even{\isacharsemicolon}\ {\isadigit{2}}\ dvd\ n{\isasymrbrakk}\ {\isasymLongrightarrow}\ {\isadigit{2}}\ dvd\ Suc\ {\isacharparenleft}Suc\ n{\isacharparenright}%
|
10762
|
57 |
\end{isabelle}
|
|
58 |
The first two subgoals are proved by simplification and the final one can be
|
|
59 |
proved in the same manner as in \S\ref{sec:rule-induction}
|
|
60 |
where the same subgoal was encountered before.
|
|
61 |
We do not show the proof script.%
|
|
62 |
\end{isamarkuptxt}%
|
11866
|
63 |
\isamarkuptrue%
|
|
64 |
\isamarkupfalse%
|
|
65 |
\isamarkupfalse%
|
|
66 |
\isamarkupfalse%
|
|
67 |
\isamarkupfalse%
|
|
68 |
\isamarkupfalse%
|
|
69 |
\isamarkupfalse%
|
|
70 |
\isamarkupfalse%
|
|
71 |
\isamarkupfalse%
|
10762
|
72 |
\end{isabellebody}%
|
|
73 |
%%% Local Variables:
|
|
74 |
%%% mode: latex
|
|
75 |
%%% TeX-master: "root"
|
|
76 |
%%% End:
|