author | kleing |
Wed, 07 Jan 2004 07:52:12 +0100 | |
changeset 14343 | 6bc647f472b9 |
parent 13339 | 0f89104dd377 |
child 16417 | 9bc16273c2d4 |
permissions | -rw-r--r-- |
11042 | 1 |
(* Title: HOL/Lambda/Commutation.thy |
2 |
ID: $Id$ |
|
3 |
Author: Tobias Nipkow & Sidi Ould Ehmety |
|
4 |
Copyright 1995 TU Muenchen |
|
5 |
||
6 |
Commutation theory for proving the Church Rosser theorem |
|
7 |
ported from Isabelle/HOL by Sidi Ould Ehmety |
|
8 |
*) |
|
9 |
||
12867 | 10 |
theory Commutation = Main: |
11042 | 11 |
|
12 |
constdefs |
|
12867 | 13 |
square :: "[i, i, i, i] => o" |
11042 | 14 |
"square(r,s,t,u) == |
12867 | 15 |
(\<forall>a b. <a,b> \<in> r --> (\<forall>c. <a, c> \<in> s --> (\<exists>x. <b,x> \<in> t & <c,x> \<in> u)))" |
11042 | 16 |
|
12867 | 17 |
commute :: "[i, i] => o" |
11042 | 18 |
"commute(r,s) == square(r,s,s,r)" |
19 |
||
12867 | 20 |
diamond :: "i=>o" |
21 |
"diamond(r) == commute(r, r)" |
|
22 |
||
23 |
strip :: "i=>o" |
|
24 |
"strip(r) == commute(r^*, r)" |
|
25 |
||
26 |
Church_Rosser :: "i => o" |
|
27 |
"Church_Rosser(r) == (\<forall>x y. <x,y> \<in> (r Un converse(r))^* --> |
|
28 |
(\<exists>z. <x,z> \<in> r^* & <y,z> \<in> r^*))" |
|
29 |
confluent :: "i=>o" |
|
30 |
"confluent(r) == diamond(r^*)" |
|
31 |
||
32 |
||
33 |
lemma square_sym: "square(r,s,t,u) ==> square(s,r,u,t)" |
|
34 |
by (unfold square_def, blast) |
|
35 |
||
36 |
lemma square_subset: "[| square(r,s,t,u); t \<subseteq> t' |] ==> square(r,s,t',u)" |
|
37 |
by (unfold square_def, blast) |
|
38 |
||
39 |
||
40 |
lemma square_rtrancl [rule_format]: |
|
41 |
"square(r,s,s,t) --> field(s)<=field(t) --> square(r^*,s,s,t^*)" |
|
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
42 |
apply (unfold square_def, clarify) |
12867 | 43 |
apply (erule rtrancl_induct) |
44 |
apply (blast intro: rtrancl_refl) |
|
45 |
apply (blast intro: rtrancl_into_rtrancl) |
|
46 |
done |
|
11042 | 47 |
|
12867 | 48 |
(* A special case of square_rtrancl_on *) |
49 |
lemma diamond_strip: |
|
50 |
"diamond(r) ==> strip(r)" |
|
51 |
apply (unfold diamond_def commute_def strip_def) |
|
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
52 |
apply (rule square_rtrancl, simp_all) |
12867 | 53 |
done |
54 |
||
55 |
(*** commute ***) |
|
56 |
||
57 |
lemma commute_sym: |
|
58 |
"commute(r,s) ==> commute(s,r)" |
|
59 |
by (unfold commute_def, blast intro: square_sym) |
|
60 |
||
61 |
lemma commute_rtrancl [rule_format]: |
|
62 |
"commute(r,s) ==> field(r)=field(s) --> commute(r^*,s^*)" |
|
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
63 |
apply (unfold commute_def, clarify) |
12867 | 64 |
apply (rule square_rtrancl) |
65 |
apply (rule square_sym [THEN square_rtrancl, THEN square_sym]) |
|
66 |
apply (simp_all add: rtrancl_field) |
|
67 |
done |
|
68 |
||
69 |
||
70 |
lemma confluentD: "confluent(r) ==> diamond(r^*)" |
|
71 |
by (simp add: confluent_def) |
|
72 |
||
73 |
lemma strip_confluent: "strip(r) ==> confluent(r)" |
|
74 |
apply (unfold strip_def confluent_def diamond_def) |
|
75 |
apply (drule commute_rtrancl) |
|
76 |
apply (simp_all add: rtrancl_field) |
|
77 |
done |
|
78 |
||
79 |
lemma commute_Un: "[| commute(r,t); commute(s,t) |] ==> commute(r Un s, t)" |
|
80 |
by (unfold commute_def square_def, blast) |
|
11042 | 81 |
|
12867 | 82 |
lemma diamond_Un: |
83 |
"[| diamond(r); diamond(s); commute(r, s) |] ==> diamond(r Un s)" |
|
84 |
by (unfold diamond_def, blast intro: commute_Un commute_sym) |
|
85 |
||
86 |
lemma diamond_confluent: |
|
87 |
"diamond(r) ==> confluent(r)" |
|
88 |
apply (unfold diamond_def confluent_def) |
|
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
89 |
apply (erule commute_rtrancl, simp) |
12867 | 90 |
done |
91 |
||
92 |
lemma confluent_Un: |
|
13248 | 93 |
"[| confluent(r); confluent(s); commute(r^*, s^*); |
94 |
relation(r); relation(s) |] ==> confluent(r Un s)" |
|
12867 | 95 |
apply (unfold confluent_def) |
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
96 |
apply (rule rtrancl_Un_rtrancl [THEN subst], auto) |
12867 | 97 |
apply (blast dest: diamond_Un intro: diamond_confluent [THEN confluentD]) |
98 |
done |
|
99 |
||
100 |
||
101 |
lemma diamond_to_confluence: |
|
102 |
"[| diamond(r); s \<subseteq> r; r<= s^* |] ==> confluent(s)" |
|
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
103 |
apply (drule rtrancl_subset [symmetric], assumption) |
12867 | 104 |
apply (simp_all add: confluent_def) |
105 |
apply (blast intro: diamond_confluent [THEN confluentD]) |
|
106 |
done |
|
107 |
||
108 |
||
109 |
(*** Church_Rosser ***) |
|
110 |
||
111 |
lemma Church_Rosser1: |
|
112 |
"Church_Rosser(r) ==> confluent(r)" |
|
113 |
apply (unfold confluent_def Church_Rosser_def square_def |
|
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
114 |
commute_def diamond_def, auto) |
12867 | 115 |
apply (drule converseI) |
116 |
apply (simp (no_asm_use) add: rtrancl_converse [symmetric]) |
|
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
117 |
apply (drule_tac x = b in spec) |
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
118 |
apply (drule_tac x1 = c in spec [THEN mp]) |
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
119 |
apply (rule_tac b = a in rtrancl_trans) |
12867 | 120 |
apply (blast intro: rtrancl_mono [THEN subsetD])+ |
121 |
done |
|
122 |
||
123 |
||
124 |
lemma Church_Rosser2: |
|
125 |
"confluent(r) ==> Church_Rosser(r)" |
|
126 |
apply (unfold confluent_def Church_Rosser_def square_def |
|
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
127 |
commute_def diamond_def, auto) |
12867 | 128 |
apply (frule fieldI1) |
129 |
apply (simp add: rtrancl_field) |
|
13339
0f89104dd377
Fixed quantified variable name preservation for ball and bex (bounded quants)
paulson
parents:
13248
diff
changeset
|
130 |
apply (erule rtrancl_induct, auto) |
12867 | 131 |
apply (blast intro: rtrancl_refl) |
132 |
apply (blast del: rtrancl_refl intro: r_into_rtrancl rtrancl_trans)+ |
|
133 |
done |
|
134 |
||
135 |
||
136 |
lemma Church_Rosser: "Church_Rosser(r) <-> confluent(r)" |
|
137 |
by (blast intro: Church_Rosser1 Church_Rosser2) |
|
138 |
||
11042 | 139 |
end |