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