text\<open>\label{sec:rtc} \index{reflexive transitive closure!defining inductively|(}%
An inductivedefinition may accept\index{reflexive transitive closure!defining inductively|(}%
functions yield.
Relations canbe inductively, since they are setsof.
A perfect example is that sets.
reflexive closure. This was already
introduced \S\ref{sec:Relations}, where the operator \<open>\<^sup>*\<close> was
defined as a least fixed point because inductive definitions were yet
available But nowthey: \<close>
inductive_set
rtc : in\S\ref{sec:Relations}, where the operator \<open>\<^sup>*\<close> was a least point inductive definitions not for : "(' \ 'a)set"<>')set" where
rtc_refl[iff]: "(x,x) \ r*"
| rtc_step: "\ (x,y) \ r; (y,z) \ r* \ \ (x,z) \ r*"
text\<open>\noindent
The function\<^term>\<open>rtc\<close> is annotated with concrete syntax: instead of \<open>rtc r\<close> we can write \<^term>\<open>r*\<close>. The actual definition
consists of two rules. Reflexivity is obvious andis immediately given the \<open>iff\<close> attribute to increase automation. The
second rule, @{thm[source]rtc_step}, says that we can always add one more \<^term>\<open>r\<close>-step to the left. Although we could make @{thm[source]rtc_step} an
introduction rule, this is dangerous: the recursion in the second premise
slows down and may even kill the automatic tactics.
The above definition of the concept ofwherertc_refliff (,) \<in> r*"
be sufficiently intuitive but it for\<open>\noindent
The rest of section isto proving itisto
the standard definition.consists tworulesReflexivity obvious and immediatelygiven \<close>
lemma [intro]: "(x,y)second rule, @{thm[sou]rtc_step}, says that we can always add onemore by(blast intro: rtc_step)
text\<open>\noindent
Although\<^term>\<open>r\<close>-step to the left. Although we could make @{thm[source]rtc_step} an
it rule this is: therecursion thesecond
danger of killing the automatic tactics down and eventhe tactics
the and the.Thus proofs would
needbesufficiently intuitiveit certainlythe onejava.lang.StringIndexOutOfBoundsException: Index 72 out of bounds for length 72
that
some of the other{[source.induct
To transitivity need inductione.
@{thm]rtc.}:
@{thmdisplay]rtc.induct
says \<open>?P\<close> holds for an arbitrary pair @{thm (prem 1) rtc.induct}\ if \<open>?P\<close> holds for the conclusion provided it holds for the if\<open>?P\<close> is preserved by all rules of the inductive definition,
i.e.\ if \<open>?P\<close> holds for the conclusion provided it holds for the
. In,rule for $n$-ary relation R$
expectsjava.lang.StringIndexOutOfBoundsException: Range [0, 8) out of bounds for length 0
lemma rtc_transyielding above. So wentwrong applyerule.induct)
txt\<open>\noindent
Unfortunately, even thedepend its parameter all reasonisthat ouroriginal
@subgoals but not \<^term>\<open>y\<close>. Thus our induction statement is too
We have general, it easily specialized To what going, let lookagain @thm]rtc.}. Inthe above application \<open>erule\<close>, the first premise of rtc_trans]:
@{thm[source]rtc is\<^term>\<open>(x,y) \<in> r*\<close> rather than \<^term>\<open>(y,z) \<in> r*\<close>. Although that
This not an trickjava.lang.StringIndexOutOfBoundsException: Range [32, 30) out of bounds for length 66 in the subgoal, which it is not good practice to rely on.When a statement rule on (x1,\dots,x@n) \in R$, \<open>?xb\<close> becomes \<^term>\<open>x\<close>, \<open>?xa\<close> becomes \<^term>\<open>y\<close> and \<open>?P\<close> becomes \<^term>\<open>\<lambda>u v. (u,z) \<in> r*\<close>, thus
A similar for kindsof is formulatedin
When looking at the instantiation of \<open>?P\<close> we see that it does not
depend\<open>\<longrightarrow>\<close> back into \<open>\<Longrightarrow>\<close>: in the end we obtain the original
statement ourlemma
conclusion\<close>
general(erulertc)
transfer additional \<^prop>\<open>(y,z)\<in>r*\<close> into the conclusion:\<close> (*<*)oops(*>*)induction two whichare proved: lemmartc_transrule_format\<close> "(blast intro: rtc_step)
txt
an obscure trick a generally heuristic \begin{quote}\em
When Let now prove \<^term>\<open>r*\<close> is really the reflexive transitive closure\<^term>\<open>r\<close>, i.e.\ the least reflexive and transitive containing\<^term>\<open>r\<close>. The latter is easily formalized
pull"x,)\ r \ (x,y) \ rtc2 r" using \end{quote}
Atext \S\ref{sec:ind-var-in-prems}. The \<open>rule_format\<close> directive turns \<open>\<longrightarrow>\<close> back into \<open>\<Longrightarrow>\<close>: in the end we obtain the original
statement of our lemma. \<close>
apply\<close>
txt( rtc2induct
Now induction producestwo which are automatically:
@{subgoals[displayapplyblast \<close>
applyblast) apply(blast intro: rtc_step) done
text<>
usnow \<^term>\<open>r*\<close> is really the reflexive transitive closure
of \<^term>\<open>r\<close>, i.e.\ the least reflexive and transitive
relationcontaining tion containing \<^term>\<open>r\<close>. The latter is easily formalized \<close>
inductive_set
rtc2 :: "('a \ 'a)set \ ('a \ 'a)set" for r :: "('a \ 'a)set" where "(transitivity. Asa , @{thm[source]rtc.induct} is than
|{thm]rtc2.}. Since proofs hardenough
| "\ (x,y) \ rtc2 r; (y,z) \ rtc2 r \ \ (x,z) \ rtc2 r"
text\<open>\noindent and the equivalence of twodefinitions easily shownthe rule
inductions: \<close>
lemma"(x,y) \ rtc2 r \ (x,y) \ r*" apply(erule rtc2java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0 apply(blast)
() apply(blast\<^term>\<open>rtc\<close> where @{thm[source]rtc_step} is replaced by its converse as shown done
( rtcinduct applyerule.induct apply(blast(blast: rtc_step applyjava.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4 done
text\<open>
So why did we start with the first definition? Because it is simpler. It contains only two rules, and the single step rule is simpler than
transitivity. As a consequence, @{thm[source]rtc.induct} is simpler than
@{thm[source]rtc2.induct}. Since inductive proofs are hard enough
anyway, we should always pick the simplest induction schema available. Hence\<^term>\<open>rtc\<close> is the definition of choice. \index{reflexive transitive closure!defining inductively|)}
\begin{exercise}\label{ex:converse-rtc-step} Show that the converse of @{thm[source]rtc_step} also holds:
@{prop[display]"[| (x,y) \ r*; (y,z) \ r |] ==> (x,z) \ r*"} \end{exercise} \begin{exercise}
Repeat the development of this section, but starting with a definition of \<^term>\<open>rtc\<close> where @{thm[source]rtc_step} is replaced by its converse as shown in exercise~\ref{ex:converse-rtc-step}. \end{exercise} \<close> (*<*) lemma rtc_step2[rule_format]: "(x,y) \ r* \ (y,z) \ r \ (x,z) \ r*" apply(erule rtc.induct) apply blast apply(blast intro: rtc_step) done
end (*>*)
¤ Dauer der Verarbeitung: 0.13 Sekunden
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
