equal
deleted
inserted
replaced
693 lemma assumes A: "(x,y) \<in> r*" and B: "(y,z) \<in> r*" |
693 lemma assumes A: "(x,y) \<in> r*" and B: "(y,z) \<in> r*" |
694 shows "(x,z) \<in> r*" |
694 shows "(x,z) \<in> r*" |
695 proof - |
695 proof - |
696 from A B show ?thesis |
696 from A B show ?thesis |
697 proof induct |
697 proof induct |
698 fix x assume "(x,z) \<in> r*" -- "B[x := z]" |
698 fix x assume "(x,z) \<in> r*" -- "B[y := x]" |
699 thus "(x,z) \<in> r*" . |
699 thus "(x,z) \<in> r*" . |
700 next |
700 next |
701 fix x' x y |
701 fix x' x y |
702 assume step: "(x',x) \<in> r" and |
702 assume step: "(x',x) \<in> r" and |
703 IH: "(y,z) \<in> r* \<Longrightarrow> (x,z) \<in> r*" and |
703 IH: "(y,z) \<in> r* \<Longrightarrow> (x,z) \<in> r*" and |
707 qed |
707 qed |
708 |
708 |
709 text{*\noindent We start the proof with \isakeyword{from}~@{text"A |
709 text{*\noindent We start the proof with \isakeyword{from}~@{text"A |
710 B"}. Only @{text A} is ``consumed'' by the first proof step, here |
710 B"}. Only @{text A} is ``consumed'' by the first proof step, here |
711 induction. Since @{text B} is left over we don't just prove @{text |
711 induction. Since @{text B} is left over we don't just prove @{text |
712 ?thesis} but in fact @{text"B \<Longrightarrow> ?thesis"}, just as in the previous |
712 ?thesis} but @{text"B \<Longrightarrow> ?thesis"}, just as in the previous |
713 proof, only more elegantly. The base case is trivial. In the |
713 proof, only more elegantly. The base case is trivial. In the |
714 assumptions for the induction step we can see very clearly how things |
714 assumptions for the induction step we can see very clearly how things |
715 fit together and permit ourselves the obvious forward step |
715 fit together and permit ourselves the obvious forward step |
716 @{text"IH[OF B]"}. *} |
716 @{text"IH[OF B]"}. *} |
717 |
717 |