author  wenzelm 
Wed, 19 Mar 2008 22:47:38 +0100  
changeset 26340  a85fe32e7b2f 
parent 26271  e324f8918c98 
child 26801  244184661a09 
permissions  rwrr 
10213  1 
(* Title: HOL/Transitive_Closure.thy 
2 
ID: $Id$ 

3 
Author: Lawrence C Paulson, Cambridge University Computer Laboratory 

4 
Copyright 1992 University of Cambridge 

5 
*) 

6 

12691  7 
header {* Reflexive and Transitive closure of a relation *} 
8 

15131  9 
theory Transitive_Closure 
22262  10 
imports Predicate 
21589  11 
uses "~~/src/Provers/trancl.ML" 
15131  12 
begin 
12691  13 

14 
text {* 

15 
@{text rtrancl} is reflexive/transitive closure, 

16 
@{text trancl} is transitive closure, 

17 
@{text reflcl} is reflexive closure. 

18 

19 
These postfix operators have \emph{maximum priority}, forcing their 

20 
operands to be atomic. 

21 
*} 

10213  22 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

23 
inductive_set 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

24 
rtrancl :: "('a \<times> 'a) set \<Rightarrow> ('a \<times> 'a) set" ("(_^*)" [1000] 999) 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

25 
for r :: "('a \<times> 'a) set" 
22262  26 
where 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

27 
rtrancl_refl [intro!, Pure.intro!, simp]: "(a, a) : r^*" 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

28 
 rtrancl_into_rtrancl [Pure.intro]: "(a, b) : r^* ==> (b, c) : r ==> (a, c) : r^*" 
11327
cd2c27a23df1
Transitive closure is now defined via "inductive".
berghofe
parents:
11115
diff
changeset

29 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

30 
inductive_set 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

31 
trancl :: "('a \<times> 'a) set \<Rightarrow> ('a \<times> 'a) set" ("(_^+)" [1000] 999) 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

32 
for r :: "('a \<times> 'a) set" 
22262  33 
where 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

34 
r_into_trancl [intro, Pure.intro]: "(a, b) : r ==> (a, b) : r^+" 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

35 
 trancl_into_trancl [Pure.intro]: "(a, b) : r^+ ==> (b, c) : r ==> (a, c) : r^+" 
13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

36 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

37 
notation 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

38 
rtranclp ("(_^**)" [1000] 1000) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

39 
tranclp ("(_^++)" [1000] 1000) 
10213  40 

19656
09be06943252
tuned concrete syntax  abbreviation/const_syntax;
wenzelm
parents:
19623
diff
changeset

41 
abbreviation 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

42 
reflclp :: "('a => 'a => bool) => 'a => 'a => bool" ("(_^==)" [1000] 1000) where 
22422
ee19cdb07528
stepping towards uniform lattice theory development in HOL
haftmann
parents:
22262
diff
changeset

43 
"r^== == sup r op =" 
22262  44 

45 
abbreviation 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

46 
reflcl :: "('a \<times> 'a) set => ('a \<times> 'a) set" ("(_^=)" [1000] 999) where 
19656
09be06943252
tuned concrete syntax  abbreviation/const_syntax;
wenzelm
parents:
19623
diff
changeset

47 
"r^= == r \<union> Id" 
10213  48 

21210  49 
notation (xsymbols) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

50 
rtranclp ("(_\<^sup>*\<^sup>*)" [1000] 1000) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

51 
tranclp ("(_\<^sup>+\<^sup>+)" [1000] 1000) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

52 
reflclp ("(_\<^sup>=\<^sup>=)" [1000] 1000) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

53 
rtrancl ("(_\<^sup>*)" [1000] 999) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

54 
trancl ("(_\<^sup>+)" [1000] 999) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

55 
reflcl ("(_\<^sup>=)" [1000] 999) 
12691  56 

21210  57 
notation (HTML output) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

58 
rtranclp ("(_\<^sup>*\<^sup>*)" [1000] 1000) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

59 
tranclp ("(_\<^sup>+\<^sup>+)" [1000] 1000) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

60 
reflclp ("(_\<^sup>=\<^sup>=)" [1000] 1000) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

61 
rtrancl ("(_\<^sup>*)" [1000] 999) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

62 
trancl ("(_\<^sup>+)" [1000] 999) and 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

63 
reflcl ("(_\<^sup>=)" [1000] 999) 
14565  64 

12691  65 

26271  66 
subsection {* Reflexive closure *} 
67 

68 
lemma reflexive_reflcl[simp]: "reflexive(r^=)" 

69 
by(simp add:refl_def) 

70 

71 
lemma antisym_reflcl[simp]: "antisym(r^=) = antisym r" 

72 
by(simp add:antisym_def) 

73 

74 
lemma trans_reflclI[simp]: "trans r \<Longrightarrow> trans(r^=)" 

75 
unfolding trans_def by blast 

76 

77 

12691  78 
subsection {* Reflexivetransitive closure *} 
79 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

80 
lemma reflcl_set_eq [pred_set_conv]: "(sup (\<lambda>x y. (x, y) \<in> r) op =) = (\<lambda>x y. (x, y) \<in> r Un Id)" 
22262  81 
by (simp add: expand_fun_eq) 
82 

12691  83 
lemma r_into_rtrancl [intro]: "!!p. p \<in> r ==> p \<in> r^*" 
84 
 {* @{text rtrancl} of @{text r} contains @{text r} *} 

85 
apply (simp only: split_tupled_all) 

86 
apply (erule rtrancl_refl [THEN rtrancl_into_rtrancl]) 

87 
done 

88 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

89 
lemma r_into_rtranclp [intro]: "r x y ==> r^** x y" 
22262  90 
 {* @{text rtrancl} of @{text r} contains @{text r} *} 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

91 
by (erule rtranclp.rtrancl_refl [THEN rtranclp.rtrancl_into_rtrancl]) 
22262  92 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

93 
lemma rtranclp_mono: "r \<le> s ==> r^** \<le> s^**" 
12691  94 
 {* monotonicity of @{text rtrancl} *} 
22262  95 
apply (rule predicate2I) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

96 
apply (erule rtranclp.induct) 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

97 
apply (rule_tac [2] rtranclp.rtrancl_into_rtrancl, blast+) 
12691  98 
done 
99 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

100 
lemmas rtrancl_mono = rtranclp_mono [to_set] 
22262  101 

26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

102 
theorem rtranclp_induct [consumes 1, case_names base step, induct set: rtranclp]: 
22262  103 
assumes a: "r^** a b" 
104 
and cases: "P a" "!!y z. [ r^** a y; r y z; P y ] ==> P z" 

12937
0c4fd7529467
clarified syntax of ``long'' statements: fixes/assumes/shows;
wenzelm
parents:
12823
diff
changeset

105 
shows "P b" 
12691  106 
proof  
107 
from a have "a = a > P b" 

17589  108 
by (induct "%x y. x = a > P y" a b) (iprover intro: cases)+ 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

109 
then show ?thesis by iprover 
12691  110 
qed 
111 

25425
9191942c4ead
Removed some case_names and consumes attributes that are now no longer
berghofe
parents:
25295
diff
changeset

112 
lemmas rtrancl_induct [induct set: rtrancl] = rtranclp_induct [to_set] 
22262  113 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

114 
lemmas rtranclp_induct2 = 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

115 
rtranclp_induct[of _ "(ax,ay)" "(bx,by)", split_rule, 
22262  116 
consumes 1, case_names refl step] 
117 

14404
4952c5a92e04
Transitive_Closure: added consumes and case_names attributes
nipkow
parents:
14398
diff
changeset

118 
lemmas rtrancl_induct2 = 
4952c5a92e04
Transitive_Closure: added consumes and case_names attributes
nipkow
parents:
14398
diff
changeset

119 
rtrancl_induct[of "(ax,ay)" "(bx,by)", split_format (complete), 
4952c5a92e04
Transitive_Closure: added consumes and case_names attributes
nipkow
parents:
14398
diff
changeset

120 
consumes 1, case_names refl step] 
18372  121 

19228  122 
lemma reflexive_rtrancl: "reflexive (r^*)" 
123 
by (unfold refl_def) fast 

124 

26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

125 
text {* Transitivity of transitive closure. *} 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

126 
lemma trans_rtrancl: "trans (r^*)" 
12823  127 
proof (rule transI) 
128 
fix x y z 

129 
assume "(x, y) \<in> r\<^sup>*" 

130 
assume "(y, z) \<in> r\<^sup>*" 

26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

131 
then show "(x, z) \<in> r\<^sup>*" 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

132 
proof induct 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

133 
case base 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

134 
show "(x, y) \<in> r\<^sup>*" by fact 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

135 
next 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

136 
case (step u v) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

137 
from `(x, u) \<in> r\<^sup>*` and `(u, v) \<in> r` 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

138 
show "(x, v) \<in> r\<^sup>*" .. 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

139 
qed 
12823  140 
qed 
12691  141 

142 
lemmas rtrancl_trans = trans_rtrancl [THEN transD, standard] 

143 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

144 
lemma rtranclp_trans: 
22262  145 
assumes xy: "r^** x y" 
146 
and yz: "r^** y z" 

147 
shows "r^** x z" using yz xy 

148 
by induct iprover+ 

149 

26174
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

150 
lemma rtranclE [cases set: rtrancl]: 
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

151 
assumes major: "(a::'a, b) : r^*" 
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

152 
obtains 
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

153 
(base) "a = b" 
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

154 
 (step) y where "(a, y) : r^*" and "(y, b) : r" 
12691  155 
 {* elimination of @{text rtrancl}  by induction on a special formula *} 
18372  156 
apply (subgoal_tac "(a::'a) = b  (EX y. (a,y) : r^* & (y,b) : r)") 
157 
apply (rule_tac [2] major [THEN rtrancl_induct]) 

158 
prefer 2 apply blast 

159 
prefer 2 apply blast 

26174
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

160 
apply (erule asm_rl exE disjE conjE base step)+ 
18372  161 
done 
12691  162 

22080
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

163 
lemma rtrancl_Int_subset: "[ Id \<subseteq> s; r O (r^* \<inter> s) \<subseteq> s] ==> r^* \<subseteq> s" 
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

164 
apply (rule subsetI) 
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

165 
apply (rule_tac p="x" in PairE, clarify) 
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

166 
apply (erule rtrancl_induct, auto) 
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

167 
done 
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

168 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

169 
lemma converse_rtranclp_into_rtranclp: 
22262  170 
"r a b \<Longrightarrow> r\<^sup>*\<^sup>* b c \<Longrightarrow> r\<^sup>*\<^sup>* a c" 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

171 
by (rule rtranclp_trans) iprover+ 
22262  172 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

173 
lemmas converse_rtrancl_into_rtrancl = converse_rtranclp_into_rtranclp [to_set] 
12691  174 

175 
text {* 

176 
\medskip More @{term "r^*"} equations and inclusions. 

177 
*} 

178 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

179 
lemma rtranclp_idemp [simp]: "(r^**)^** = r^**" 
22262  180 
apply (auto intro!: order_antisym) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

181 
apply (erule rtranclp_induct) 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

182 
apply (rule rtranclp.rtrancl_refl) 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

183 
apply (blast intro: rtranclp_trans) 
12691  184 
done 
185 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

186 
lemmas rtrancl_idemp [simp] = rtranclp_idemp [to_set] 
22262  187 

12691  188 
lemma rtrancl_idemp_self_comp [simp]: "R^* O R^* = R^*" 
189 
apply (rule set_ext) 

190 
apply (simp only: split_tupled_all) 

191 
apply (blast intro: rtrancl_trans) 

192 
done 

193 

194 
lemma rtrancl_subset_rtrancl: "r \<subseteq> s^* ==> r^* \<subseteq> s^*" 

26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

195 
apply (drule rtrancl_mono) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

196 
apply simp 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

197 
done 
12691  198 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

199 
lemma rtranclp_subset: "R \<le> S ==> S \<le> R^** ==> S^** = R^**" 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

200 
apply (drule rtranclp_mono) 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

201 
apply (drule rtranclp_mono) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

202 
apply simp 
12691  203 
done 
204 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

205 
lemmas rtrancl_subset = rtranclp_subset [to_set] 
22262  206 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

207 
lemma rtranclp_sup_rtranclp: "(sup (R^**) (S^**))^** = (sup R S)^**" 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

208 
by (blast intro!: rtranclp_subset intro: rtranclp_mono [THEN predicate2D]) 
12691  209 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

210 
lemmas rtrancl_Un_rtrancl = rtranclp_sup_rtranclp [to_set] 
22262  211 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

212 
lemma rtranclp_reflcl [simp]: "(R^==)^** = R^**" 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

213 
by (blast intro!: rtranclp_subset) 
22262  214 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

215 
lemmas rtrancl_reflcl [simp] = rtranclp_reflcl [to_set] 
12691  216 

217 
lemma rtrancl_r_diff_Id: "(r  Id)^* = r^*" 

218 
apply (rule sym) 

14208  219 
apply (rule rtrancl_subset, blast, clarify) 
12691  220 
apply (rename_tac a b) 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

221 
apply (case_tac "a = b") 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

222 
apply blast 
12691  223 
apply (blast intro!: r_into_rtrancl) 
224 
done 

225 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

226 
lemma rtranclp_r_diff_Id: "(inf r op ~=)^** = r^**" 
22262  227 
apply (rule sym) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

228 
apply (rule rtranclp_subset) 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

229 
apply blast+ 
22262  230 
done 
231 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

232 
theorem rtranclp_converseD: 
22262  233 
assumes r: "(r^1)^** x y" 
234 
shows "r^** y x" 

12823  235 
proof  
236 
from r show ?thesis 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

237 
by induct (iprover intro: rtranclp_trans dest!: conversepD)+ 
12823  238 
qed 
12691  239 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

240 
lemmas rtrancl_converseD = rtranclp_converseD [to_set] 
22262  241 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

242 
theorem rtranclp_converseI: 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

243 
assumes "r^** y x" 
22262  244 
shows "(r^1)^** x y" 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

245 
using assms 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

246 
by induct (iprover intro: rtranclp_trans conversepI)+ 
12691  247 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

248 
lemmas rtrancl_converseI = rtranclp_converseI [to_set] 
22262  249 

12691  250 
lemma rtrancl_converse: "(r^1)^* = (r^*)^1" 
251 
by (fast dest!: rtrancl_converseD intro!: rtrancl_converseI) 

252 

19228  253 
lemma sym_rtrancl: "sym r ==> sym (r^*)" 
254 
by (simp only: sym_conv_converse_eq rtrancl_converse [symmetric]) 

255 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

256 
theorem converse_rtranclp_induct[consumes 1]: 
22262  257 
assumes major: "r^** a b" 
258 
and cases: "P b" "!!y z. [ r y z; r^** z b; P z ] ==> P y" 

12937
0c4fd7529467
clarified syntax of ``long'' statements: fixes/assumes/shows;
wenzelm
parents:
12823
diff
changeset

259 
shows "P a" 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

260 
using rtranclp_converseI [OF major] 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

261 
by induct (iprover intro: cases dest!: conversepD rtranclp_converseD)+ 
12691  262 

25425
9191942c4ead
Removed some case_names and consumes attributes that are now no longer
berghofe
parents:
25295
diff
changeset

263 
lemmas converse_rtrancl_induct = converse_rtranclp_induct [to_set] 
22262  264 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

265 
lemmas converse_rtranclp_induct2 = 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

266 
converse_rtranclp_induct [of _ "(ax,ay)" "(bx,by)", split_rule, 
22262  267 
consumes 1, case_names refl step] 
268 

14404
4952c5a92e04
Transitive_Closure: added consumes and case_names attributes
nipkow
parents:
14398
diff
changeset

269 
lemmas converse_rtrancl_induct2 = 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

270 
converse_rtrancl_induct [of "(ax,ay)" "(bx,by)", split_format (complete), 
14404
4952c5a92e04
Transitive_Closure: added consumes and case_names attributes
nipkow
parents:
14398
diff
changeset

271 
consumes 1, case_names refl step] 
12691  272 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

273 
lemma converse_rtranclpE: 
22262  274 
assumes major: "r^** x z" 
18372  275 
and cases: "x=z ==> P" 
22262  276 
"!!y. [ r x y; r^** y z ] ==> P" 
18372  277 
shows P 
22262  278 
apply (subgoal_tac "x = z  (EX y. r x y & r^** y z)") 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

279 
apply (rule_tac [2] major [THEN converse_rtranclp_induct]) 
18372  280 
prefer 2 apply iprover 
281 
prefer 2 apply iprover 

282 
apply (erule asm_rl exE disjE conjE cases)+ 

283 
done 

12691  284 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

285 
lemmas converse_rtranclE = converse_rtranclpE [to_set] 
22262  286 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

287 
lemmas converse_rtranclpE2 = converse_rtranclpE [of _ "(xa,xb)" "(za,zb)", split_rule] 
22262  288 

289 
lemmas converse_rtranclE2 = converse_rtranclE [of "(xa,xb)" "(za,zb)", split_rule] 

12691  290 

291 
lemma r_comp_rtrancl_eq: "r O r^* = r^* O r" 

292 
by (blast elim: rtranclE converse_rtranclE 

293 
intro: rtrancl_into_rtrancl converse_rtrancl_into_rtrancl) 

294 

20716
a6686a8e1b68
Changed precedence of "op O" (relation composition) from 60 to 75.
krauss
parents:
19656
diff
changeset

295 
lemma rtrancl_unfold: "r^* = Id Un r O r^*" 
15551  296 
by (auto intro: rtrancl_into_rtrancl elim: rtranclE) 
297 

12691  298 

299 
subsection {* Transitive closure *} 

10331  300 

13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

301 
lemma trancl_mono: "!!p. p \<in> r^+ ==> r \<subseteq> s ==> p \<in> s^+" 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

302 
apply (simp add: split_tupled_all) 
13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

303 
apply (erule trancl.induct) 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

304 
apply (iprover dest: subsetD)+ 
12691  305 
done 
306 

13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

307 
lemma r_into_trancl': "!!p. p : r ==> p : r^+" 
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

308 
by (simp only: split_tupled_all) (erule r_into_trancl) 
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

309 

12691  310 
text {* 
311 
\medskip Conversions between @{text trancl} and @{text rtrancl}. 

312 
*} 

313 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

314 
lemma tranclp_into_rtranclp: "r^++ a b ==> r^** a b" 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

315 
by (erule tranclp.induct) iprover+ 
12691  316 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

317 
lemmas trancl_into_rtrancl = tranclp_into_rtranclp [to_set] 
22262  318 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

319 
lemma rtranclp_into_tranclp1: assumes r: "r^** a b" 
22262  320 
shows "!!c. r b c ==> r^++ a c" using r 
17589  321 
by induct iprover+ 
12691  322 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

323 
lemmas rtrancl_into_trancl1 = rtranclp_into_tranclp1 [to_set] 
22262  324 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

325 
lemma rtranclp_into_tranclp2: "[ r a b; r^** b c ] ==> r^++ a c" 
12691  326 
 {* intro rule from @{text r} and @{text rtrancl} *} 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

327 
apply (erule rtranclp.cases) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

328 
apply iprover 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

329 
apply (rule rtranclp_trans [THEN rtranclp_into_tranclp1]) 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

330 
apply (simp  rule r_into_rtranclp)+ 
12691  331 
done 
332 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

333 
lemmas rtrancl_into_trancl2 = rtranclp_into_tranclp2 [to_set] 
22262  334 

26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

335 
text {* Nice induction rule for @{text trancl} *} 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

336 
lemma tranclp_induct [consumes 1, case_names base step, induct pred: tranclp]: 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

337 
assumes "r^++ a b" 
22262  338 
and cases: "!!y. r a y ==> P y" 
339 
"!!y z. r^++ a y ==> r y z ==> P y ==> P z" 

13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

340 
shows "P b" 
12691  341 
proof  
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

342 
from `r^++ a b` have "a = a > P b" 
17589  343 
by (induct "%x y. x = a > P y" a b) (iprover intro: cases)+ 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

344 
then show ?thesis by iprover 
12691  345 
qed 
346 

25425
9191942c4ead
Removed some case_names and consumes attributes that are now no longer
berghofe
parents:
25295
diff
changeset

347 
lemmas trancl_induct [induct set: trancl] = tranclp_induct [to_set] 
22262  348 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

349 
lemmas tranclp_induct2 = 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

350 
tranclp_induct [of _ "(ax,ay)" "(bx,by)", split_rule, 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

351 
consumes 1, case_names base step] 
22262  352 

22172  353 
lemmas trancl_induct2 = 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

354 
trancl_induct [of "(ax,ay)" "(bx,by)", split_format (complete), 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

355 
consumes 1, case_names base step] 
22172  356 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

357 
lemma tranclp_trans_induct: 
22262  358 
assumes major: "r^++ x y" 
359 
and cases: "!!x y. r x y ==> P x y" 

360 
"!!x y z. [ r^++ x y; P x y; r^++ y z; P y z ] ==> P x z" 

18372  361 
shows "P x y" 
12691  362 
 {* Another induction rule for trancl, incorporating transitivity *} 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

363 
by (iprover intro: major [THEN tranclp_induct] cases) 
12691  364 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

365 
lemmas trancl_trans_induct = tranclp_trans_induct [to_set] 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

366 

26174
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

367 
lemma tranclE [cases set: trancl]: 
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

368 
assumes "(a, b) : r^+" 
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

369 
obtains 
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

370 
(base) "(a, b) : r" 
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

371 
 (step) c where "(a, c) : r^+" and "(c, b) : r" 
9efd4c04eaa4
rtranclE, tranclE: tuned statement, added case_names;
wenzelm
parents:
25425
diff
changeset

372 
using assms by cases simp_all 
10980  373 

22080
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

374 
lemma trancl_Int_subset: "[ r \<subseteq> s; r O (r^+ \<inter> s) \<subseteq> s] ==> r^+ \<subseteq> s" 
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

375 
apply (rule subsetI) 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

376 
apply (rule_tac p = x in PairE) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

377 
apply clarify 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

378 
apply (erule trancl_induct) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

379 
apply auto 
22080
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

380 
done 
7bf8868ab3e4
induction rules for trancl/rtrancl expressed using subsets
paulson
parents:
21589
diff
changeset

381 

20716
a6686a8e1b68
Changed precedence of "op O" (relation composition) from 60 to 75.
krauss
parents:
19656
diff
changeset

382 
lemma trancl_unfold: "r^+ = r Un r O r^+" 
15551  383 
by (auto intro: trancl_into_trancl elim: tranclE) 
384 

26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

385 
text {* Transitivity of @{term "r^+"} *} 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

386 
lemma trans_trancl [simp]: "trans (r^+)" 
13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

387 
proof (rule transI) 
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

388 
fix x y z 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

389 
assume "(x, y) \<in> r^+" 
13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

390 
assume "(y, z) \<in> r^+" 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

391 
then show "(x, z) \<in> r^+" 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

392 
proof induct 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

393 
case (base u) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

394 
from `(x, y) \<in> r^+` and `(y, u) \<in> r` 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

395 
show "(x, u) \<in> r^+" .. 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

396 
next 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

397 
case (step u v) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

398 
from `(x, u) \<in> r^+` and `(u, v) \<in> r` 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

399 
show "(x, v) \<in> r^+" .. 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

400 
qed 
13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

401 
qed 
12691  402 

403 
lemmas trancl_trans = trans_trancl [THEN transD, standard] 

404 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

405 
lemma tranclp_trans: 
22262  406 
assumes xy: "r^++ x y" 
407 
and yz: "r^++ y z" 

408 
shows "r^++ x z" using yz xy 

409 
by induct iprover+ 

410 

26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

411 
lemma trancl_id [simp]: "trans r \<Longrightarrow> r^+ = r" 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

412 
apply auto 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

413 
apply (erule trancl_induct) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

414 
apply assumption 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

415 
apply (unfold trans_def) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

416 
apply blast 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

417 
done 
19623  418 

26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

419 
lemma rtranclp_tranclp_tranclp: 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

420 
assumes "r^** x y" 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

421 
shows "!!z. r^++ y z ==> r^++ x z" using assms 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

422 
by induct (iprover intro: tranclp_trans)+ 
12691  423 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

424 
lemmas rtrancl_trancl_trancl = rtranclp_tranclp_tranclp [to_set] 
22262  425 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

426 
lemma tranclp_into_tranclp2: "r a b ==> r^++ b c ==> r^++ a c" 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

427 
by (erule tranclp_trans [OF tranclp.r_into_trancl]) 
22262  428 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

429 
lemmas trancl_into_trancl2 = tranclp_into_tranclp2 [to_set] 
12691  430 

431 
lemma trancl_insert: 

432 
"(insert (y, x) r)^+ = r^+ \<union> {(a, b). (a, y) \<in> r^* \<and> (x, b) \<in> r^*}" 

433 
 {* primitive recursion for @{text trancl} over finite relations *} 

434 
apply (rule equalityI) 

435 
apply (rule subsetI) 

436 
apply (simp only: split_tupled_all) 

14208  437 
apply (erule trancl_induct, blast) 
12691  438 
apply (blast intro: rtrancl_into_trancl1 trancl_into_rtrancl r_into_trancl trancl_trans) 
439 
apply (rule subsetI) 

440 
apply (blast intro: trancl_mono rtrancl_mono 

441 
[THEN [2] rev_subsetD] rtrancl_trancl_trancl rtrancl_into_trancl2) 

442 
done 

443 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

444 
lemma tranclp_converseI: "(r^++)^1 x y ==> (r^1)^++ x y" 
22262  445 
apply (drule conversepD) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

446 
apply (erule tranclp_induct) 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

447 
apply (iprover intro: conversepI tranclp_trans)+ 
12691  448 
done 
449 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

450 
lemmas trancl_converseI = tranclp_converseI [to_set] 
22262  451 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

452 
lemma tranclp_converseD: "(r^1)^++ x y ==> (r^++)^1 x y" 
22262  453 
apply (rule conversepI) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

454 
apply (erule tranclp_induct) 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

455 
apply (iprover dest: conversepD intro: tranclp_trans)+ 
13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

456 
done 
12691  457 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

458 
lemmas trancl_converseD = tranclp_converseD [to_set] 
22262  459 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

460 
lemma tranclp_converse: "(r^1)^++ = (r^++)^1" 
22262  461 
by (fastsimp simp add: expand_fun_eq 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

462 
intro!: tranclp_converseI dest!: tranclp_converseD) 
22262  463 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

464 
lemmas trancl_converse = tranclp_converse [to_set] 
12691  465 

19228  466 
lemma sym_trancl: "sym r ==> sym (r^+)" 
467 
by (simp only: sym_conv_converse_eq trancl_converse [symmetric]) 

468 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

469 
lemma converse_tranclp_induct: 
22262  470 
assumes major: "r^++ a b" 
471 
and cases: "!!y. r y b ==> P(y)" 

472 
"!!y z.[ r y z; r^++ z b; P(z) ] ==> P(y)" 

18372  473 
shows "P a" 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

474 
apply (rule tranclp_induct [OF tranclp_converseI, OF conversepI, OF major]) 
18372  475 
apply (rule cases) 
22262  476 
apply (erule conversepD) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

477 
apply (blast intro: prems dest!: tranclp_converseD conversepD) 
18372  478 
done 
12691  479 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

480 
lemmas converse_trancl_induct = converse_tranclp_induct [to_set] 
22262  481 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

482 
lemma tranclpD: "R^++ x y ==> EX z. R x z \<and> R^** z y" 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

483 
apply (erule converse_tranclp_induct) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

484 
apply auto 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

485 
apply (blast intro: rtranclp_trans) 
12691  486 
done 
487 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

488 
lemmas tranclD = tranclpD [to_set] 
22262  489 

25295
12985023be5e
tranclD2 (tranclD at the other end) + trancl_power
kleing
parents:
23743
diff
changeset

490 
lemma tranclD2: 
12985023be5e
tranclD2 (tranclD at the other end) + trancl_power
kleing
parents:
23743
diff
changeset

491 
"(x, y) \<in> R\<^sup>+ \<Longrightarrow> \<exists>z. (x, z) \<in> R\<^sup>* \<and> (z, y) \<in> R" 
12985023be5e
tranclD2 (tranclD at the other end) + trancl_power
kleing
parents:
23743
diff
changeset

492 
by (blast elim: tranclE intro: trancl_into_rtrancl) 
12985023be5e
tranclD2 (tranclD at the other end) + trancl_power
kleing
parents:
23743
diff
changeset

493 

13867  494 
lemma irrefl_tranclI: "r^1 \<inter> r^* = {} ==> (x, x) \<notin> r^+" 
18372  495 
by (blast elim: tranclE dest: trancl_into_rtrancl) 
12691  496 

497 
lemma irrefl_trancl_rD: "!!X. ALL x. (x, x) \<notin> r^+ ==> (x, y) \<in> r ==> x \<noteq> y" 

498 
by (blast dest: r_into_trancl) 

499 

500 
lemma trancl_subset_Sigma_aux: 

501 
"(a, b) \<in> r^* ==> r \<subseteq> A \<times> A ==> a = b \<or> a \<in> A" 

18372  502 
by (induct rule: rtrancl_induct) auto 
12691  503 

504 
lemma trancl_subset_Sigma: "r \<subseteq> A \<times> A ==> r^+ \<subseteq> A \<times> A" 

13704
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

505 
apply (rule subsetI) 
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

506 
apply (simp only: split_tupled_all) 
854501b1e957
Transitive closure is now defined inductively as well.
berghofe
parents:
12937
diff
changeset

507 
apply (erule tranclE) 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

508 
apply (blast dest!: trancl_into_rtrancl trancl_subset_Sigma_aux)+ 
12691  509 
done 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

510 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

511 
lemma reflcl_tranclp [simp]: "(r^++)^== = r^**" 
22262  512 
apply (safe intro!: order_antisym) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

513 
apply (erule tranclp_into_rtranclp) 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

514 
apply (blast elim: rtranclp.cases dest: rtranclp_into_tranclp1) 
11084  515 
done 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

516 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

517 
lemmas reflcl_trancl [simp] = reflcl_tranclp [to_set] 
22262  518 

11090  519 
lemma trancl_reflcl [simp]: "(r^=)^+ = r^*" 
11084  520 
apply safe 
14208  521 
apply (drule trancl_into_rtrancl, simp) 
522 
apply (erule rtranclE, safe) 

523 
apply (rule r_into_trancl, simp) 

11084  524 
apply (rule rtrancl_into_trancl1) 
14208  525 
apply (erule rtrancl_reflcl [THEN equalityD2, THEN subsetD], fast) 
11084  526 
done 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

527 

11090  528 
lemma trancl_empty [simp]: "{}^+ = {}" 
11084  529 
by (auto elim: trancl_induct) 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

530 

11090  531 
lemma rtrancl_empty [simp]: "{}^* = Id" 
11084  532 
by (rule subst [OF reflcl_trancl]) simp 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

533 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

534 
lemma rtranclpD: "R^** a b ==> a = b \<or> a \<noteq> b \<and> R^++ a b" 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

535 
by (force simp add: reflcl_tranclp [symmetric] simp del: reflcl_tranclp) 
22262  536 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

537 
lemmas rtranclD = rtranclpD [to_set] 
11084  538 

16514  539 
lemma rtrancl_eq_or_trancl: 
540 
"(x,y) \<in> R\<^sup>* = (x=y \<or> x\<noteq>y \<and> (x,y) \<in> R\<^sup>+)" 

541 
by (fast elim: trancl_into_rtrancl dest: rtranclD) 

10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

542 

12691  543 
text {* @{text Domain} and @{text Range} *} 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

544 

11090  545 
lemma Domain_rtrancl [simp]: "Domain (R^*) = UNIV" 
11084  546 
by blast 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

547 

11090  548 
lemma Range_rtrancl [simp]: "Range (R^*) = UNIV" 
11084  549 
by blast 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

550 

11090  551 
lemma rtrancl_Un_subset: "(R^* \<union> S^*) \<subseteq> (R Un S)^*" 
11084  552 
by (rule rtrancl_Un_rtrancl [THEN subst]) fast 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

553 

11090  554 
lemma in_rtrancl_UnI: "x \<in> R^* \<or> x \<in> S^* ==> x \<in> (R \<union> S)^*" 
11084  555 
by (blast intro: subsetD [OF rtrancl_Un_subset]) 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

556 

11090  557 
lemma trancl_domain [simp]: "Domain (r^+) = Domain r" 
11084  558 
by (unfold Domain_def) (blast dest: tranclD) 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

559 

11090  560 
lemma trancl_range [simp]: "Range (r^+) = Range r" 
26271  561 
unfolding Range_def by(simp add: trancl_converse [symmetric]) 
10996
74e970389def
Moved some thms from Transitive_ClosureTr.ML to Transitive_Closure.thy
nipkow
parents:
10980
diff
changeset

562 

11115  563 
lemma Not_Domain_rtrancl: 
12691  564 
"x ~: Domain R ==> ((x, y) : R^*) = (x = y)" 
565 
apply auto 

26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

566 
apply (erule rev_mp) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

567 
apply (erule rtrancl_induct) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

568 
apply auto 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

569 
done 
11327
cd2c27a23df1
Transitive closure is now defined via "inductive".
berghofe
parents:
11115
diff
changeset

570 

12691  571 
text {* More about converse @{text rtrancl} and @{text trancl}, should 
572 
be merged with main body. *} 

12428
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

573 

14337
e13731554e50
undid split_comp_eq[simp] because it leads to nontermination together with split_def!
nipkow
parents:
14208
diff
changeset

574 
lemma single_valued_confluent: 
e13731554e50
undid split_comp_eq[simp] because it leads to nontermination together with split_def!
nipkow
parents:
14208
diff
changeset

575 
"\<lbrakk> single_valued r; (x,y) \<in> r^*; (x,z) \<in> r^* \<rbrakk> 
e13731554e50
undid split_comp_eq[simp] because it leads to nontermination together with split_def!
nipkow
parents:
14208
diff
changeset

576 
\<Longrightarrow> (y,z) \<in> r^* \<or> (z,y) \<in> r^*" 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

577 
apply (erule rtrancl_induct) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

578 
apply simp 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

579 
apply (erule disjE) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

580 
apply (blast elim:converse_rtranclE dest:single_valuedD) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

581 
apply(blast intro:rtrancl_trans) 
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

582 
done 
14337
e13731554e50
undid split_comp_eq[simp] because it leads to nontermination together with split_def!
nipkow
parents:
14208
diff
changeset

583 

12691  584 
lemma r_r_into_trancl: "(a, b) \<in> R ==> (b, c) \<in> R ==> (a, c) \<in> R^+" 
12428
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

585 
by (fast intro: trancl_trans) 
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

586 

f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

587 
lemma trancl_into_trancl [rule_format]: 
12691  588 
"(a, b) \<in> r\<^sup>+ ==> (b, c) \<in> r > (a,c) \<in> r\<^sup>+" 
589 
apply (erule trancl_induct) 

12428
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

590 
apply (fast intro: r_r_into_trancl) 
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

591 
apply (fast intro: r_r_into_trancl trancl_trans) 
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

592 
done 
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

593 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

594 
lemma tranclp_rtranclp_tranclp: 
22262  595 
"r\<^sup>+\<^sup>+ a b ==> r\<^sup>*\<^sup>* b c ==> r\<^sup>+\<^sup>+ a c" 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

596 
apply (drule tranclpD) 
26179
bc5d582d6cfe
rtranclp_induct, tranclp_induct: added case_names;
wenzelm
parents:
26174
diff
changeset

597 
apply (elim exE conjE) 
23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

598 
apply (drule rtranclp_trans, assumption) 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

599 
apply (drule rtranclp_into_tranclp2, assumption, assumption) 
12428
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

600 
done 
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

601 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

602 
lemmas trancl_rtrancl_trancl = tranclp_rtranclp_tranclp [to_set] 
22262  603 

12691  604 
lemmas transitive_closure_trans [trans] = 
605 
r_r_into_trancl trancl_trans rtrancl_trans 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

606 
trancl.trancl_into_trancl trancl_into_trancl2 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

607 
rtrancl.rtrancl_into_rtrancl converse_rtrancl_into_rtrancl 
12691  608 
rtrancl_trancl_trancl trancl_rtrancl_trancl 
12428
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

609 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

610 
lemmas transitive_closurep_trans' [trans] = 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

611 
tranclp_trans rtranclp_trans 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

612 
tranclp.trancl_into_trancl tranclp_into_tranclp2 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

613 
rtranclp.rtrancl_into_rtrancl converse_rtranclp_into_rtranclp 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

614 
rtranclp_tranclp_tranclp tranclp_rtranclp_tranclp 
22262  615 

12428
f3033eed309a
setup [trans] rules for calculational Isar reasoning
kleing
parents:
11327
diff
changeset

616 
declare trancl_into_rtrancl [elim] 
11327
cd2c27a23df1
Transitive closure is now defined via "inductive".
berghofe
parents:
11115
diff
changeset

617 

15551  618 

15076
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

619 
subsection {* Setup of transitivity reasoner *} 
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

620 

26340  621 
ML {* 
15076
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

622 

4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

623 
structure Trancl_Tac = Trancl_Tac_Fun ( 
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

624 
struct 
26340  625 
val r_into_trancl = @{thm trancl.r_into_trancl}; 
626 
val trancl_trans = @{thm trancl_trans}; 

627 
val rtrancl_refl = @{thm rtrancl.rtrancl_refl}; 

628 
val r_into_rtrancl = @{thm r_into_rtrancl}; 

629 
val trancl_into_rtrancl = @{thm trancl_into_rtrancl}; 

630 
val rtrancl_trancl_trancl = @{thm rtrancl_trancl_trancl}; 

631 
val trancl_rtrancl_trancl = @{thm trancl_rtrancl_trancl}; 

632 
val rtrancl_trans = @{thm rtrancl_trans}; 

15096  633 

18372  634 
fun decomp (Trueprop $ t) = 
635 
let fun dec (Const ("op :", _) $ (Const ("Pair", _) $ a $ b) $ rel ) = 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

636 
let fun decr (Const ("Transitive_Closure.rtrancl", _ ) $ r) = (r,"r*") 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

637 
 decr (Const ("Transitive_Closure.trancl", _ ) $ r) = (r,"r+") 
18372  638 
 decr r = (r,"r"); 
639 
val (rel,r) = decr rel; 

640 
in SOME (a,b,rel,r) end 

641 
 dec _ = NONE 

15076
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

642 
in dec t end; 
18372  643 

21589  644 
end); 
15076
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

645 

22262  646 
structure Tranclp_Tac = Trancl_Tac_Fun ( 
647 
struct 

26340  648 
val r_into_trancl = @{thm tranclp.r_into_trancl}; 
649 
val trancl_trans = @{thm tranclp_trans}; 

650 
val rtrancl_refl = @{thm rtranclp.rtrancl_refl}; 

651 
val r_into_rtrancl = @{thm r_into_rtranclp}; 

652 
val trancl_into_rtrancl = @{thm tranclp_into_rtranclp}; 

653 
val rtrancl_trancl_trancl = @{thm rtranclp_tranclp_tranclp}; 

654 
val trancl_rtrancl_trancl = @{thm tranclp_rtranclp_tranclp}; 

655 
val rtrancl_trans = @{thm rtranclp_trans}; 

22262  656 

657 
fun decomp (Trueprop $ t) = 

658 
let fun dec (rel $ a $ b) = 

23743
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

659 
let fun decr (Const ("Transitive_Closure.rtranclp", _ ) $ r) = (r,"r*") 
52fbc991039f
rtrancl and trancl are now defined using inductive_set.
berghofe
parents:
22422
diff
changeset

660 
 decr (Const ("Transitive_Closure.tranclp", _ ) $ r) = (r,"r+") 
22262  661 
 decr r = (r,"r"); 
662 
val (rel,r) = decr rel; 

663 
in SOME (a, b, Envir.beta_eta_contract rel, r) end 

664 
 dec _ = NONE 

665 
in dec t end; 

666 

667 
end); 

26340  668 
*} 
22262  669 

26340  670 
declaration {* fn _ => 
671 
Simplifier.map_ss (fn ss => ss 

672 
addSolver (mk_solver "Trancl" (fn _ => Trancl_Tac.trancl_tac)) 

673 
addSolver (mk_solver "Rtrancl" (fn _ => Trancl_Tac.rtrancl_tac)) 

674 
addSolver (mk_solver "Tranclp" (fn _ => Tranclp_Tac.trancl_tac)) 

675 
addSolver (mk_solver "Rtranclp" (fn _ => Tranclp_Tac.rtrancl_tac))) 

15076
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

676 
*} 
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

677 

21589  678 
(* Optional methods *) 
15076
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

679 

4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

680 
method_setup trancl = 
21589  681 
{* Method.no_args (Method.SIMPLE_METHOD' Trancl_Tac.trancl_tac) *} 
18372  682 
{* simple transitivity reasoner *} 
15076
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

683 
method_setup rtrancl = 
21589  684 
{* Method.no_args (Method.SIMPLE_METHOD' Trancl_Tac.rtrancl_tac) *} 
15076
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

685 
{* simple transitivity reasoner *} 
22262  686 
method_setup tranclp = 
687 
{* Method.no_args (Method.SIMPLE_METHOD' Tranclp_Tac.trancl_tac) *} 

688 
{* simple transitivity reasoner (predicate version) *} 

689 
method_setup rtranclp = 

690 
{* Method.no_args (Method.SIMPLE_METHOD' Tranclp_Tac.rtrancl_tac) *} 

691 
{* simple transitivity reasoner (predicate version) *} 

15076
4b3d280ef06a
New prover for transitive and reflexivetransitive closure of relations.
ballarin
parents:
14565
diff
changeset

692 

10213  693 
end 