author | oheimb |
Mon, 16 Dec 1996 13:10:02 +0100 | |
changeset 2420 | cb21eef65704 |
parent 2354 | b4a1e3306aa0 |
child 2566 | cbf02fc74332 |
permissions | -rw-r--r-- |
1461 | 1 |
(* Title: HOLCF/fix.ML |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
2 |
ID: $Id$ |
1461 | 3 |
Author: Franz Regensburger |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
4 |
Copyright 1993 Technische Universitaet Muenchen |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
5 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
6 |
Lemmas for fix.thy |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
7 |
*) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
8 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
9 |
open Fix; |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
10 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
11 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
12 |
(* derive inductive properties of iterate from primitive recursion *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
13 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
14 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
15 |
qed_goal "iterate_0" Fix.thy "iterate 0 F x = x" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
16 |
(fn prems => |
1461 | 17 |
[ |
18 |
(resolve_tac (nat_recs iterate_def) 1) |
|
19 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
20 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
21 |
qed_goal "iterate_Suc" Fix.thy "iterate (Suc n) F x = F`(iterate n F x)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
22 |
(fn prems => |
1461 | 23 |
[ |
24 |
(resolve_tac (nat_recs iterate_def) 1) |
|
25 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
26 |
|
1267 | 27 |
Addsimps [iterate_0, iterate_Suc]; |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
28 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
29 |
qed_goal "iterate_Suc2" Fix.thy "iterate (Suc n) F x = iterate n F (F`x)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
30 |
(fn prems => |
1461 | 31 |
[ |
32 |
(nat_ind_tac "n" 1), |
|
33 |
(Simp_tac 1), |
|
2033 | 34 |
(stac iterate_Suc 1), |
35 |
(stac iterate_Suc 1), |
|
36 |
(etac ssubst 1), |
|
37 |
(rtac refl 1) |
|
1461 | 38 |
]); |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
39 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
40 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
41 |
(* the sequence of function itertaions is a chain *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
42 |
(* This property is essential since monotonicity of iterate makes no sense *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
43 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
44 |
|
892 | 45 |
qed_goalw "is_chain_iterate2" Fix.thy [is_chain] |
1461 | 46 |
" x << F`x ==> is_chain (%i.iterate i F x)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
47 |
(fn prems => |
1461 | 48 |
[ |
49 |
(cut_facts_tac prems 1), |
|
50 |
(strip_tac 1), |
|
51 |
(Simp_tac 1), |
|
52 |
(nat_ind_tac "i" 1), |
|
53 |
(Asm_simp_tac 1), |
|
54 |
(Asm_simp_tac 1), |
|
55 |
(etac monofun_cfun_arg 1) |
|
56 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
57 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
58 |
|
892 | 59 |
qed_goal "is_chain_iterate" Fix.thy |
1461 | 60 |
"is_chain (%i.iterate i F UU)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
61 |
(fn prems => |
1461 | 62 |
[ |
63 |
(rtac is_chain_iterate2 1), |
|
64 |
(rtac minimal 1) |
|
65 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
66 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
67 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
68 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
69 |
(* Kleene's fixed point theorems for continuous functions in pointed *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
70 |
(* omega cpo's *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
71 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
72 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
73 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
74 |
qed_goalw "Ifix_eq" Fix.thy [Ifix_def] "Ifix F =F`(Ifix F)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
75 |
(fn prems => |
1461 | 76 |
[ |
2033 | 77 |
(stac contlub_cfun_arg 1), |
1461 | 78 |
(rtac is_chain_iterate 1), |
79 |
(rtac antisym_less 1), |
|
80 |
(rtac lub_mono 1), |
|
81 |
(rtac is_chain_iterate 1), |
|
82 |
(rtac ch2ch_fappR 1), |
|
83 |
(rtac is_chain_iterate 1), |
|
84 |
(rtac allI 1), |
|
85 |
(rtac (iterate_Suc RS subst) 1), |
|
86 |
(rtac (is_chain_iterate RS is_chainE RS spec) 1), |
|
87 |
(rtac is_lub_thelub 1), |
|
88 |
(rtac ch2ch_fappR 1), |
|
89 |
(rtac is_chain_iterate 1), |
|
90 |
(rtac ub_rangeI 1), |
|
91 |
(rtac allI 1), |
|
92 |
(rtac (iterate_Suc RS subst) 1), |
|
93 |
(rtac is_ub_thelub 1), |
|
94 |
(rtac is_chain_iterate 1) |
|
95 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
96 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
97 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
98 |
qed_goalw "Ifix_least" Fix.thy [Ifix_def] "F`x=x ==> Ifix(F) << x" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
99 |
(fn prems => |
1461 | 100 |
[ |
101 |
(cut_facts_tac prems 1), |
|
102 |
(rtac is_lub_thelub 1), |
|
103 |
(rtac is_chain_iterate 1), |
|
104 |
(rtac ub_rangeI 1), |
|
105 |
(strip_tac 1), |
|
106 |
(nat_ind_tac "i" 1), |
|
107 |
(Asm_simp_tac 1), |
|
108 |
(Asm_simp_tac 1), |
|
109 |
(res_inst_tac [("t","x")] subst 1), |
|
110 |
(atac 1), |
|
111 |
(etac monofun_cfun_arg 1) |
|
112 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
113 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
114 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
115 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
116 |
(* monotonicity and continuity of iterate *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
117 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
118 |
|
892 | 119 |
qed_goalw "monofun_iterate" Fix.thy [monofun] "monofun(iterate(i))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
120 |
(fn prems => |
1461 | 121 |
[ |
122 |
(strip_tac 1), |
|
123 |
(nat_ind_tac "i" 1), |
|
124 |
(Asm_simp_tac 1), |
|
125 |
(Asm_simp_tac 1), |
|
126 |
(rtac (less_fun RS iffD2) 1), |
|
127 |
(rtac allI 1), |
|
128 |
(rtac monofun_cfun 1), |
|
129 |
(atac 1), |
|
130 |
(rtac (less_fun RS iffD1 RS spec) 1), |
|
131 |
(atac 1) |
|
132 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
133 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
134 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
135 |
(* the following lemma uses contlub_cfun which itself is based on a *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
136 |
(* diagonalisation lemma for continuous functions with two arguments. *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
137 |
(* In this special case it is the application function fapp *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
138 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
139 |
|
892 | 140 |
qed_goalw "contlub_iterate" Fix.thy [contlub] "contlub(iterate(i))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
141 |
(fn prems => |
1461 | 142 |
[ |
143 |
(strip_tac 1), |
|
144 |
(nat_ind_tac "i" 1), |
|
145 |
(Asm_simp_tac 1), |
|
146 |
(rtac (lub_const RS thelubI RS sym) 1), |
|
147 |
(Asm_simp_tac 1), |
|
148 |
(rtac ext 1), |
|
2033 | 149 |
(stac thelub_fun 1), |
1461 | 150 |
(rtac is_chainI 1), |
151 |
(rtac allI 1), |
|
152 |
(rtac (less_fun RS iffD2) 1), |
|
153 |
(rtac allI 1), |
|
154 |
(rtac (is_chainE RS spec) 1), |
|
155 |
(rtac (monofun_fapp1 RS ch2ch_MF2LR) 1), |
|
156 |
(rtac allI 1), |
|
157 |
(rtac monofun_fapp2 1), |
|
158 |
(atac 1), |
|
159 |
(rtac ch2ch_fun 1), |
|
160 |
(rtac (monofun_iterate RS ch2ch_monofun) 1), |
|
161 |
(atac 1), |
|
2033 | 162 |
(stac thelub_fun 1), |
1461 | 163 |
(rtac (monofun_iterate RS ch2ch_monofun) 1), |
164 |
(atac 1), |
|
165 |
(rtac contlub_cfun 1), |
|
166 |
(atac 1), |
|
167 |
(etac (monofun_iterate RS ch2ch_monofun RS ch2ch_fun) 1) |
|
168 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
169 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
170 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
171 |
qed_goal "cont_iterate" Fix.thy "cont(iterate(i))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
172 |
(fn prems => |
1461 | 173 |
[ |
174 |
(rtac monocontlub2cont 1), |
|
175 |
(rtac monofun_iterate 1), |
|
176 |
(rtac contlub_iterate 1) |
|
177 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
178 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
179 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
180 |
(* a lemma about continuity of iterate in its third argument *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
181 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
182 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
183 |
qed_goal "monofun_iterate2" Fix.thy "monofun(iterate n F)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
184 |
(fn prems => |
1461 | 185 |
[ |
186 |
(rtac monofunI 1), |
|
187 |
(strip_tac 1), |
|
188 |
(nat_ind_tac "n" 1), |
|
189 |
(Asm_simp_tac 1), |
|
190 |
(Asm_simp_tac 1), |
|
191 |
(etac monofun_cfun_arg 1) |
|
192 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
193 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
194 |
qed_goal "contlub_iterate2" Fix.thy "contlub(iterate n F)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
195 |
(fn prems => |
1461 | 196 |
[ |
197 |
(rtac contlubI 1), |
|
198 |
(strip_tac 1), |
|
199 |
(nat_ind_tac "n" 1), |
|
200 |
(Simp_tac 1), |
|
201 |
(Simp_tac 1), |
|
202 |
(res_inst_tac [("t","iterate n1 F (lub(range(%u. Y u)))"), |
|
203 |
("s","lub(range(%i. iterate n1 F (Y i)))")] ssubst 1), |
|
204 |
(atac 1), |
|
205 |
(rtac contlub_cfun_arg 1), |
|
206 |
(etac (monofun_iterate2 RS ch2ch_monofun) 1) |
|
207 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
208 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
209 |
qed_goal "cont_iterate2" Fix.thy "cont (iterate n F)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
210 |
(fn prems => |
1461 | 211 |
[ |
212 |
(rtac monocontlub2cont 1), |
|
213 |
(rtac monofun_iterate2 1), |
|
214 |
(rtac contlub_iterate2 1) |
|
215 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
216 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
217 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
218 |
(* monotonicity and continuity of Ifix *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
219 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
220 |
|
892 | 221 |
qed_goalw "monofun_Ifix" Fix.thy [monofun,Ifix_def] "monofun(Ifix)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
222 |
(fn prems => |
1461 | 223 |
[ |
224 |
(strip_tac 1), |
|
225 |
(rtac lub_mono 1), |
|
226 |
(rtac is_chain_iterate 1), |
|
227 |
(rtac is_chain_iterate 1), |
|
228 |
(rtac allI 1), |
|
229 |
(rtac (less_fun RS iffD1 RS spec) 1), |
|
230 |
(etac (monofun_iterate RS monofunE RS spec RS spec RS mp) 1) |
|
231 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
232 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
233 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
234 |
(* since iterate is not monotone in its first argument, special lemmas must *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
235 |
(* be derived for lubs in this argument *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
236 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
237 |
|
892 | 238 |
qed_goal "is_chain_iterate_lub" Fix.thy |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
239 |
"is_chain(Y) ==> is_chain(%i. lub(range(%ia. iterate ia (Y i) UU)))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
240 |
(fn prems => |
1461 | 241 |
[ |
242 |
(cut_facts_tac prems 1), |
|
243 |
(rtac is_chainI 1), |
|
244 |
(strip_tac 1), |
|
245 |
(rtac lub_mono 1), |
|
246 |
(rtac is_chain_iterate 1), |
|
247 |
(rtac is_chain_iterate 1), |
|
248 |
(strip_tac 1), |
|
249 |
(etac (monofun_iterate RS ch2ch_monofun RS ch2ch_fun RS is_chainE |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
250 |
RS spec) 1) |
1461 | 251 |
]); |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
252 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
253 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
254 |
(* this exchange lemma is analog to the one for monotone functions *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
255 |
(* observe that monotonicity is not really needed. The propagation of *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
256 |
(* chains is the essential argument which is usually derived from monot. *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
257 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
258 |
|
892 | 259 |
qed_goal "contlub_Ifix_lemma1" Fix.thy |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
260 |
"is_chain(Y) ==>iterate n (lub(range Y)) y = lub(range(%i. iterate n (Y i) y))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
261 |
(fn prems => |
1461 | 262 |
[ |
263 |
(cut_facts_tac prems 1), |
|
264 |
(rtac (thelub_fun RS subst) 1), |
|
265 |
(rtac (monofun_iterate RS ch2ch_monofun) 1), |
|
266 |
(atac 1), |
|
267 |
(rtac fun_cong 1), |
|
2033 | 268 |
(stac (contlub_iterate RS contlubE RS spec RS mp) 1), |
1461 | 269 |
(atac 1), |
270 |
(rtac refl 1) |
|
271 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
272 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
273 |
|
892 | 274 |
qed_goal "ex_lub_iterate" Fix.thy "is_chain(Y) ==>\ |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
275 |
\ lub(range(%i. lub(range(%ia. iterate i (Y ia) UU)))) =\ |
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
276 |
\ lub(range(%i. lub(range(%ia. iterate ia (Y i) UU))))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
277 |
(fn prems => |
1461 | 278 |
[ |
279 |
(cut_facts_tac prems 1), |
|
280 |
(rtac antisym_less 1), |
|
281 |
(rtac is_lub_thelub 1), |
|
282 |
(rtac (contlub_Ifix_lemma1 RS ext RS subst) 1), |
|
283 |
(atac 1), |
|
284 |
(rtac is_chain_iterate 1), |
|
285 |
(rtac ub_rangeI 1), |
|
286 |
(strip_tac 1), |
|
287 |
(rtac lub_mono 1), |
|
288 |
(etac (monofun_iterate RS ch2ch_monofun RS ch2ch_fun) 1), |
|
289 |
(etac is_chain_iterate_lub 1), |
|
290 |
(strip_tac 1), |
|
291 |
(rtac is_ub_thelub 1), |
|
292 |
(rtac is_chain_iterate 1), |
|
293 |
(rtac is_lub_thelub 1), |
|
294 |
(etac is_chain_iterate_lub 1), |
|
295 |
(rtac ub_rangeI 1), |
|
296 |
(strip_tac 1), |
|
297 |
(rtac lub_mono 1), |
|
298 |
(rtac is_chain_iterate 1), |
|
299 |
(rtac (contlub_Ifix_lemma1 RS ext RS subst) 1), |
|
300 |
(atac 1), |
|
301 |
(rtac is_chain_iterate 1), |
|
302 |
(strip_tac 1), |
|
303 |
(rtac is_ub_thelub 1), |
|
304 |
(etac (monofun_iterate RS ch2ch_monofun RS ch2ch_fun) 1) |
|
305 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
306 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
307 |
|
892 | 308 |
qed_goalw "contlub_Ifix" Fix.thy [contlub,Ifix_def] "contlub(Ifix)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
309 |
(fn prems => |
1461 | 310 |
[ |
311 |
(strip_tac 1), |
|
2033 | 312 |
(stac (contlub_Ifix_lemma1 RS ext) 1), |
1461 | 313 |
(atac 1), |
314 |
(etac ex_lub_iterate 1) |
|
315 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
316 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
317 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
318 |
qed_goal "cont_Ifix" Fix.thy "cont(Ifix)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
319 |
(fn prems => |
1461 | 320 |
[ |
321 |
(rtac monocontlub2cont 1), |
|
322 |
(rtac monofun_Ifix 1), |
|
323 |
(rtac contlub_Ifix 1) |
|
324 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
325 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
326 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
327 |
(* propagate properties of Ifix to its continuous counterpart *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
328 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
329 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
330 |
qed_goalw "fix_eq" Fix.thy [fix_def] "fix`F = F`(fix`F)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
331 |
(fn prems => |
1461 | 332 |
[ |
333 |
(asm_simp_tac (!simpset addsimps [cont_Ifix]) 1), |
|
334 |
(rtac Ifix_eq 1) |
|
335 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
336 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
337 |
qed_goalw "fix_least" Fix.thy [fix_def] "F`x = x ==> fix`F << x" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
338 |
(fn prems => |
1461 | 339 |
[ |
340 |
(cut_facts_tac prems 1), |
|
341 |
(asm_simp_tac (!simpset addsimps [cont_Ifix]) 1), |
|
342 |
(etac Ifix_least 1) |
|
343 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
344 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
345 |
|
1274 | 346 |
qed_goal "fix_eqI" Fix.thy |
347 |
"[| F`x = x; !z. F`z = z --> x << z |] ==> x = fix`F" |
|
348 |
(fn prems => |
|
1461 | 349 |
[ |
350 |
(cut_facts_tac prems 1), |
|
351 |
(rtac antisym_less 1), |
|
352 |
(etac allE 1), |
|
353 |
(etac mp 1), |
|
354 |
(rtac (fix_eq RS sym) 1), |
|
355 |
(etac fix_least 1) |
|
356 |
]); |
|
1274 | 357 |
|
358 |
||
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
359 |
qed_goal "fix_eq2" Fix.thy "f == fix`F ==> f = F`f" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
360 |
(fn prems => |
1461 | 361 |
[ |
362 |
(rewrite_goals_tac prems), |
|
363 |
(rtac fix_eq 1) |
|
364 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
365 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
366 |
qed_goal "fix_eq3" Fix.thy "f == fix`F ==> f`x = F`f`x" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
367 |
(fn prems => |
1461 | 368 |
[ |
369 |
(rtac trans 1), |
|
370 |
(rtac ((hd prems) RS fix_eq2 RS cfun_fun_cong) 1), |
|
371 |
(rtac refl 1) |
|
372 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
373 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
374 |
fun fix_tac3 thm i = ((rtac trans i) THEN (rtac (thm RS fix_eq3) i)); |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
375 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
376 |
qed_goal "fix_eq4" Fix.thy "f = fix`F ==> f = F`f" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
377 |
(fn prems => |
1461 | 378 |
[ |
379 |
(cut_facts_tac prems 1), |
|
380 |
(hyp_subst_tac 1), |
|
381 |
(rtac fix_eq 1) |
|
382 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
383 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
384 |
qed_goal "fix_eq5" Fix.thy "f = fix`F ==> f`x = F`f`x" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
385 |
(fn prems => |
1461 | 386 |
[ |
387 |
(rtac trans 1), |
|
388 |
(rtac ((hd prems) RS fix_eq4 RS cfun_fun_cong) 1), |
|
389 |
(rtac refl 1) |
|
390 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
391 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
392 |
fun fix_tac5 thm i = ((rtac trans i) THEN (rtac (thm RS fix_eq5) i)); |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
393 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
394 |
fun fix_prover thy fixdef thm = prove_goal thy thm |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
395 |
(fn prems => |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
396 |
[ |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
397 |
(rtac trans 1), |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
398 |
(rtac (fixdef RS fix_eq4) 1), |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
399 |
(rtac trans 1), |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
400 |
(rtac beta_cfun 1), |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
401 |
(cont_tacR 1), |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
402 |
(rtac refl 1) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
403 |
]); |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
404 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
405 |
(* use this one for definitions! *) |
297 | 406 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
407 |
fun fix_prover2 thy fixdef thm = prove_goal thy thm |
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
408 |
(fn prems => |
1461 | 409 |
[ |
410 |
(rtac trans 1), |
|
411 |
(rtac (fix_eq2) 1), |
|
412 |
(rtac fixdef 1), |
|
413 |
(rtac beta_cfun 1), |
|
414 |
(cont_tacR 1) |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
415 |
]); |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
416 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
417 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
418 |
(* better access to definitions *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
419 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
420 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
421 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
422 |
qed_goal "Ifix_def2" Fix.thy "Ifix=(%x. lub(range(%i. iterate i x UU)))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
423 |
(fn prems => |
1461 | 424 |
[ |
425 |
(rtac ext 1), |
|
426 |
(rewtac Ifix_def), |
|
427 |
(rtac refl 1) |
|
428 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
429 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
430 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
431 |
(* direct connection between fix and iteration without Ifix *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
432 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
433 |
|
892 | 434 |
qed_goalw "fix_def2" Fix.thy [fix_def] |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
435 |
"fix`F = lub(range(%i. iterate i F UU))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
436 |
(fn prems => |
1461 | 437 |
[ |
438 |
(fold_goals_tac [Ifix_def]), |
|
439 |
(asm_simp_tac (!simpset addsimps [cont_Ifix]) 1) |
|
440 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
441 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
442 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
443 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
444 |
(* Lemmas about admissibility and fixed point induction *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
445 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
446 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
447 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
448 |
(* access to definitions *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
449 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
450 |
|
892 | 451 |
qed_goalw "adm_def2" Fix.thy [adm_def] |
1461 | 452 |
"adm(P) = (!Y. is_chain(Y) --> (!i.P(Y(i))) --> P(lub(range(Y))))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
453 |
(fn prems => |
1461 | 454 |
[ |
455 |
(rtac refl 1) |
|
456 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
457 |
|
892 | 458 |
qed_goalw "admw_def2" Fix.thy [admw_def] |
1461 | 459 |
"admw(P) = (!F.(!n.P(iterate n F UU)) -->\ |
460 |
\ P (lub(range(%i.iterate i F UU))))" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
461 |
(fn prems => |
1461 | 462 |
[ |
463 |
(rtac refl 1) |
|
464 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
465 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
466 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
467 |
(* an admissible formula is also weak admissible *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
468 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
469 |
|
892 | 470 |
qed_goalw "adm_impl_admw" Fix.thy [admw_def] "adm(P)==>admw(P)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
471 |
(fn prems => |
1461 | 472 |
[ |
473 |
(cut_facts_tac prems 1), |
|
474 |
(strip_tac 1), |
|
475 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
476 |
(atac 1), |
|
477 |
(rtac is_chain_iterate 1), |
|
478 |
(atac 1) |
|
479 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
480 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
481 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
482 |
(* fixed point induction *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
483 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
484 |
|
892 | 485 |
qed_goal "fix_ind" Fix.thy |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
486 |
"[| adm(P);P(UU);!!x. P(x) ==> P(F`x)|] ==> P(fix`F)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
487 |
(fn prems => |
1461 | 488 |
[ |
489 |
(cut_facts_tac prems 1), |
|
2033 | 490 |
(stac fix_def2 1), |
1461 | 491 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
492 |
(atac 1), |
|
493 |
(rtac is_chain_iterate 1), |
|
494 |
(rtac allI 1), |
|
495 |
(nat_ind_tac "i" 1), |
|
2033 | 496 |
(stac iterate_0 1), |
1461 | 497 |
(atac 1), |
2033 | 498 |
(stac iterate_Suc 1), |
1461 | 499 |
(resolve_tac prems 1), |
500 |
(atac 1) |
|
501 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
502 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
503 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
504 |
(* computational induction for weak admissible formulae *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
505 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
506 |
|
892 | 507 |
qed_goal "wfix_ind" Fix.thy |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
508 |
"[| admw(P); !n. P(iterate n F UU)|] ==> P(fix`F)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
509 |
(fn prems => |
1461 | 510 |
[ |
511 |
(cut_facts_tac prems 1), |
|
2033 | 512 |
(stac fix_def2 1), |
1461 | 513 |
(rtac (admw_def2 RS iffD1 RS spec RS mp) 1), |
514 |
(atac 1), |
|
515 |
(rtac allI 1), |
|
516 |
(etac spec 1) |
|
517 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
518 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
519 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
520 |
(* for chain-finite (easy) types every formula is admissible *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
521 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
522 |
|
892 | 523 |
qed_goalw "adm_max_in_chain" Fix.thy [adm_def] |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
524 |
"!Y. is_chain(Y::nat=>'a) --> (? n.max_in_chain n Y) ==> adm(P::'a=>bool)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
525 |
(fn prems => |
1461 | 526 |
[ |
527 |
(cut_facts_tac prems 1), |
|
528 |
(strip_tac 1), |
|
529 |
(rtac exE 1), |
|
530 |
(rtac mp 1), |
|
531 |
(etac spec 1), |
|
532 |
(atac 1), |
|
2033 | 533 |
(stac (lub_finch1 RS thelubI) 1), |
1461 | 534 |
(atac 1), |
535 |
(atac 1), |
|
536 |
(etac spec 1) |
|
537 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
538 |
|
892 | 539 |
qed_goalw "adm_chain_finite" Fix.thy [chain_finite_def] |
1461 | 540 |
"chain_finite(x::'a) ==> adm(P::'a=>bool)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
541 |
(fn prems => |
1461 | 542 |
[ |
543 |
(cut_facts_tac prems 1), |
|
544 |
(etac adm_max_in_chain 1) |
|
545 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
546 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
547 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
548 |
(* flat types are chain_finite *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
549 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
550 |
|
2275 | 551 |
qed_goalw "flat_imp_chain_finite" Fix.thy [flat_def,chain_finite_def] |
552 |
"flat(x::'a)==>chain_finite(x::'a)" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
553 |
(fn prems => |
1461 | 554 |
[ |
555 |
(rewtac max_in_chain_def), |
|
556 |
(cut_facts_tac prems 1), |
|
557 |
(strip_tac 1), |
|
1675 | 558 |
(case_tac "!i.Y(i)=UU" 1), |
1461 | 559 |
(res_inst_tac [("x","0")] exI 1), |
560 |
(strip_tac 1), |
|
561 |
(rtac trans 1), |
|
562 |
(etac spec 1), |
|
563 |
(rtac sym 1), |
|
564 |
(etac spec 1), |
|
565 |
(rtac (chain_mono2 RS exE) 1), |
|
566 |
(fast_tac HOL_cs 1), |
|
567 |
(atac 1), |
|
568 |
(res_inst_tac [("x","Suc(x)")] exI 1), |
|
569 |
(strip_tac 1), |
|
570 |
(rtac disjE 1), |
|
571 |
(atac 3), |
|
572 |
(rtac mp 1), |
|
573 |
(dtac spec 1), |
|
574 |
(etac spec 1), |
|
575 |
(etac (le_imp_less_or_eq RS disjE) 1), |
|
576 |
(etac (chain_mono RS mp) 1), |
|
577 |
(atac 1), |
|
578 |
(hyp_subst_tac 1), |
|
579 |
(rtac refl_less 1), |
|
580 |
(res_inst_tac [("P","Y(Suc(x)) = UU")] notE 1), |
|
581 |
(atac 2), |
|
582 |
(rtac mp 1), |
|
583 |
(etac spec 1), |
|
584 |
(Asm_simp_tac 1) |
|
585 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
586 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
587 |
|
1779 | 588 |
bind_thm ("adm_flat", flat_imp_chain_finite RS adm_chain_finite); |
2275 | 589 |
(* flat(?x::?'a) ==> adm(?P::?'a => bool) *) |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
590 |
|
2354 | 591 |
(* ------------------------------------------------------------------------ *) |
592 |
(* some properties of flat *) |
|
593 |
(* ------------------------------------------------------------------------ *) |
|
594 |
||
595 |
qed_goalw "flatdom2monofun" Fix.thy [flat_def] |
|
596 |
"[| flat(x::'a::pcpo); f UU = UU |] ==> monofun (f::'a=>'b::pcpo)" |
|
597 |
(fn prems => |
|
598 |
[ |
|
599 |
cut_facts_tac prems 1, |
|
600 |
fast_tac ((HOL_cs addss !simpset) addSIs [monofunI]) 1 |
|
601 |
]); |
|
602 |
||
603 |
||
2275 | 604 |
qed_goalw "flat_void" Fix.thy [flat_def] "flat(UU::void)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
605 |
(fn prems => |
1461 | 606 |
[ |
607 |
(strip_tac 1), |
|
608 |
(rtac disjI1 1), |
|
609 |
(rtac unique_void2 1) |
|
610 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
611 |
|
2275 | 612 |
qed_goalw "flat_eq" Fix.thy [flat_def] |
613 |
"[| flat (x::'a); (a::'a) ~= UU |] ==> a << b = (a = b)" (fn prems=>[ |
|
2033 | 614 |
(cut_facts_tac prems 1), |
615 |
(fast_tac (HOL_cs addIs [refl_less]) 1)]); |
|
1992 | 616 |
|
2354 | 617 |
|
618 |
(* ------------------------------------------------------------------------ *) |
|
619 |
(* some lemmata for functions with flat/chain_finite domain/range types *) |
|
620 |
(* ------------------------------------------------------------------------ *) |
|
621 |
||
622 |
qed_goal "chfin2finch" Fix.thy |
|
623 |
"[| is_chain (Y::nat=>'a); chain_finite (x::'a) |] ==> finite_chain Y" |
|
624 |
(fn prems => |
|
625 |
[ |
|
626 |
cut_facts_tac prems 1, |
|
627 |
fast_tac (HOL_cs addss |
|
628 |
(!simpset addsimps [chain_finite_def,finite_chain_def])) 1 |
|
629 |
]); |
|
630 |
||
631 |
qed_goal "chfindom_monofun2cont" Fix.thy |
|
632 |
"[| chain_finite(x::'a::pcpo); monofun f |] ==> cont (f::'a=>'b::pcpo)" |
|
633 |
(fn prems => |
|
634 |
[ |
|
635 |
cut_facts_tac prems 1, |
|
636 |
rtac monocontlub2cont 1, |
|
637 |
atac 1, |
|
638 |
rtac contlubI 1, |
|
639 |
strip_tac 1, |
|
640 |
dtac (chfin2finch COMP swap_prems_rl) 1, |
|
641 |
atac 1, |
|
642 |
rtac antisym_less 1, |
|
643 |
fast_tac ((HOL_cs addIs [is_ub_thelub,ch2ch_monofun]) |
|
644 |
addss (HOL_ss addsimps [finite_chain_def,maxinch_is_thelub])) 1, |
|
645 |
dtac (monofun_finch2finch COMP swap_prems_rl) 1, |
|
646 |
atac 1, |
|
647 |
fast_tac ((HOL_cs |
|
648 |
addIs [is_ub_thelub,(monofunE RS spec RS spec RS mp)]) |
|
649 |
addss (HOL_ss addsimps [finite_chain_def,maxinch_is_thelub])) 1 |
|
650 |
]); |
|
651 |
||
652 |
bind_thm("flatdom_monofun2cont",flat_imp_chain_finite RS chfindom_monofun2cont); |
|
653 |
(* [| flat ?x; monofun ?f |] ==> cont ?f *) |
|
654 |
||
655 |
qed_goal "flatdom_strict2cont" Fix.thy |
|
656 |
"[| flat(x::'a::pcpo); f UU = UU |] ==> cont (f::'a=>'b::pcpo)" |
|
657 |
(fn prems => |
|
658 |
[ |
|
659 |
cut_facts_tac prems 1, |
|
660 |
fast_tac ((HOL_cs addSIs [flatdom2monofun, |
|
661 |
flat_imp_chain_finite RS chfindom_monofun2cont])) 1 |
|
662 |
]); |
|
663 |
||
664 |
qed_goal "chfin_fappR" Fix.thy |
|
665 |
"[| is_chain (Y::nat => 'a->'b); chain_finite(x::'b) |] ==> \ |
|
666 |
\ !s. ? n. lub(range(Y))`s = Y n`s" |
|
667 |
(fn prems => |
|
668 |
[ |
|
669 |
cut_facts_tac prems 1, |
|
670 |
rtac allI 1, |
|
671 |
rtac (contlub_cfun_fun RS ssubst) 1, |
|
672 |
atac 1, |
|
673 |
fast_tac (HOL_cs addSIs [thelubI,lub_finch2,chfin2finch,ch2ch_fappL])1 |
|
674 |
]); |
|
675 |
||
676 |
qed_goalw "adm_chfindom" Fix.thy [adm_def] |
|
677 |
"chain_finite (x::'b) ==> adm (%(u::'a->'b). P(u`s))" (fn prems => [ |
|
678 |
cut_facts_tac prems 1, |
|
679 |
strip_tac 1, |
|
680 |
dtac chfin_fappR 1, |
|
681 |
atac 1, |
|
682 |
eres_inst_tac [("x","s")] allE 1, |
|
683 |
fast_tac (HOL_cs addss !simpset) 1]); |
|
684 |
||
685 |
bind_thm("adm_flatdom",flat_imp_chain_finite RS adm_chfindom); |
|
686 |
(* flat ?x ==> adm (%u. ?P (u`?s)) *) |
|
687 |
||
688 |
||
1992 | 689 |
(* ------------------------------------------------------------------------ *) |
690 |
(* lemmata for improved admissibility introdution rule *) |
|
691 |
(* ------------------------------------------------------------------------ *) |
|
692 |
||
693 |
qed_goal "infinite_chain_adm_lemma" Porder.thy |
|
694 |
"[|is_chain Y; !i. P (Y i); \ |
|
695 |
\ (!!Y. [| is_chain Y; !i. P (Y i); ~ finite_chain Y |] ==> P (lub (range Y)))\ |
|
696 |
\ |] ==> P (lub (range Y))" |
|
697 |
(fn prems => [ |
|
2033 | 698 |
cut_facts_tac prems 1, |
699 |
case_tac "finite_chain Y" 1, |
|
700 |
eresolve_tac prems 2, atac 2, atac 2, |
|
701 |
rewtac finite_chain_def, |
|
702 |
safe_tac HOL_cs, |
|
703 |
etac (lub_finch1 RS thelubI RS ssubst) 1, atac 1, etac spec 1]); |
|
1992 | 704 |
|
705 |
qed_goal "increasing_chain_adm_lemma" Porder.thy |
|
706 |
"[|is_chain Y; !i. P (Y i); \ |
|
707 |
\ (!!Y. [| is_chain Y; !i. P (Y i); !i. ? j. i < j & Y i ~= Y j & Y i << Y j|]\ |
|
708 |
\ ==> P (lub (range Y))) |] ==> P (lub (range Y))" |
|
709 |
(fn prems => [ |
|
2033 | 710 |
cut_facts_tac prems 1, |
711 |
etac infinite_chain_adm_lemma 1, atac 1, etac thin_rl 1, |
|
712 |
rewtac finite_chain_def, |
|
713 |
safe_tac HOL_cs, |
|
714 |
etac swap 1, |
|
715 |
rewtac max_in_chain_def, |
|
716 |
resolve_tac prems 1, atac 1, atac 1, |
|
717 |
fast_tac (HOL_cs addDs [le_imp_less_or_eq] |
|
718 |
addEs [chain_mono RS mp]) 1]); |
|
1992 | 719 |
|
720 |
qed_goalw "admI" Fix.thy [adm_def] |
|
721 |
"(!!Y. [| is_chain Y; !i. P (Y i); !i. ? j. i < j & Y i ~= Y j & Y i << Y j |]\ |
|
722 |
\ ==> P(lub (range Y))) ==> adm P" |
|
723 |
(fn prems => [ |
|
2033 | 724 |
strip_tac 1, |
725 |
etac increasing_chain_adm_lemma 1, atac 1, |
|
726 |
eresolve_tac prems 1, atac 1, atac 1]); |
|
1992 | 727 |
|
728 |
||
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
729 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
730 |
(* continuous isomorphisms are strict *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
731 |
(* a prove for embedding projection pairs is similar *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
732 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
733 |
|
892 | 734 |
qed_goal "iso_strict" Fix.thy |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
735 |
"!!f g.[|!y.f`(g`y)=(y::'b) ; !x.g`(f`x)=(x::'a) |] \ |
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
736 |
\ ==> f`UU=UU & g`UU=UU" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
737 |
(fn prems => |
1461 | 738 |
[ |
739 |
(rtac conjI 1), |
|
740 |
(rtac UU_I 1), |
|
741 |
(res_inst_tac [("s","f`(g`(UU::'b))"),("t","UU::'b")] subst 1), |
|
742 |
(etac spec 1), |
|
743 |
(rtac (minimal RS monofun_cfun_arg) 1), |
|
744 |
(rtac UU_I 1), |
|
745 |
(res_inst_tac [("s","g`(f`(UU::'a))"),("t","UU::'a")] subst 1), |
|
746 |
(etac spec 1), |
|
747 |
(rtac (minimal RS monofun_cfun_arg) 1) |
|
748 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
749 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
750 |
|
892 | 751 |
qed_goal "isorep_defined" Fix.thy |
1461 | 752 |
"[|!x.rep`(abs`x)=x;!y.abs`(rep`y)=y; z~=UU|] ==> rep`z ~= UU" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
753 |
(fn prems => |
1461 | 754 |
[ |
755 |
(cut_facts_tac prems 1), |
|
756 |
(etac swap 1), |
|
757 |
(dtac notnotD 1), |
|
758 |
(dres_inst_tac [("f","abs")] cfun_arg_cong 1), |
|
759 |
(etac box_equals 1), |
|
760 |
(fast_tac HOL_cs 1), |
|
761 |
(etac (iso_strict RS conjunct1) 1), |
|
762 |
(atac 1) |
|
763 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
764 |
|
892 | 765 |
qed_goal "isoabs_defined" Fix.thy |
1461 | 766 |
"[|!x.rep`(abs`x) = x;!y.abs`(rep`y)=y ; z~=UU|] ==> abs`z ~= UU" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
767 |
(fn prems => |
1461 | 768 |
[ |
769 |
(cut_facts_tac prems 1), |
|
770 |
(etac swap 1), |
|
771 |
(dtac notnotD 1), |
|
772 |
(dres_inst_tac [("f","rep")] cfun_arg_cong 1), |
|
773 |
(etac box_equals 1), |
|
774 |
(fast_tac HOL_cs 1), |
|
775 |
(etac (iso_strict RS conjunct2) 1), |
|
776 |
(atac 1) |
|
777 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
778 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
779 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
780 |
(* propagation of flatness and chainfiniteness by continuous isomorphisms *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
781 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
782 |
|
892 | 783 |
qed_goalw "chfin2chfin" Fix.thy [chain_finite_def] |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
784 |
"!!f g.[|chain_finite(x::'a); !y.f`(g`y)=(y::'b) ; !x.g`(f`x)=(x::'a) |] \ |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
785 |
\ ==> chain_finite(y::'b)" |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
786 |
(fn prems => |
1461 | 787 |
[ |
788 |
(rewtac max_in_chain_def), |
|
789 |
(strip_tac 1), |
|
790 |
(rtac exE 1), |
|
791 |
(res_inst_tac [("P","is_chain(%i.g`(Y i))")] mp 1), |
|
792 |
(etac spec 1), |
|
793 |
(etac ch2ch_fappR 1), |
|
794 |
(rtac exI 1), |
|
795 |
(strip_tac 1), |
|
796 |
(res_inst_tac [("s","f`(g`(Y x))"),("t","Y(x)")] subst 1), |
|
797 |
(etac spec 1), |
|
798 |
(res_inst_tac [("s","f`(g`(Y j))"),("t","Y(j)")] subst 1), |
|
799 |
(etac spec 1), |
|
800 |
(rtac cfun_arg_cong 1), |
|
801 |
(rtac mp 1), |
|
802 |
(etac spec 1), |
|
803 |
(atac 1) |
|
804 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
805 |
|
2275 | 806 |
qed_goalw "flat2flat" Fix.thy [flat_def] |
807 |
"!!f g.[|flat(x::'a); !y.f`(g`y)=(y::'b) ; !x.g`(f`x)=(x::'a) |] \ |
|
808 |
\ ==> flat(y::'b)" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
809 |
(fn prems => |
1461 | 810 |
[ |
811 |
(strip_tac 1), |
|
812 |
(rtac disjE 1), |
|
813 |
(res_inst_tac [("P","g`x<<g`y")] mp 1), |
|
814 |
(etac monofun_cfun_arg 2), |
|
815 |
(dtac spec 1), |
|
816 |
(etac spec 1), |
|
817 |
(rtac disjI1 1), |
|
818 |
(rtac trans 1), |
|
819 |
(res_inst_tac [("s","f`(g`x)"),("t","x")] subst 1), |
|
820 |
(etac spec 1), |
|
821 |
(etac cfun_arg_cong 1), |
|
822 |
(rtac (iso_strict RS conjunct1) 1), |
|
823 |
(atac 1), |
|
824 |
(atac 1), |
|
825 |
(rtac disjI2 1), |
|
826 |
(res_inst_tac [("s","f`(g`x)"),("t","x")] subst 1), |
|
827 |
(etac spec 1), |
|
828 |
(res_inst_tac [("s","f`(g`y)"),("t","y")] subst 1), |
|
829 |
(etac spec 1), |
|
830 |
(etac cfun_arg_cong 1) |
|
831 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
832 |
|
625 | 833 |
(* ------------------------------------------------------------------------- *) |
834 |
(* a result about functions with flat codomain *) |
|
835 |
(* ------------------------------------------------------------------------- *) |
|
836 |
||
2275 | 837 |
qed_goalw "flat_codom" Fix.thy [flat_def] |
838 |
"[|flat(y::'b);f`(x::'a)=(c::'b)|] ==> f`(UU::'a)=(UU::'b) | (!z.f`(z::'a)=c)" |
|
625 | 839 |
(fn prems => |
1461 | 840 |
[ |
841 |
(cut_facts_tac prems 1), |
|
1675 | 842 |
(case_tac "f`(x::'a)=(UU::'b)" 1), |
1461 | 843 |
(rtac disjI1 1), |
844 |
(rtac UU_I 1), |
|
845 |
(res_inst_tac [("s","f`(x)"),("t","UU::'b")] subst 1), |
|
846 |
(atac 1), |
|
847 |
(rtac (minimal RS monofun_cfun_arg) 1), |
|
1675 | 848 |
(case_tac "f`(UU::'a)=(UU::'b)" 1), |
1461 | 849 |
(etac disjI1 1), |
850 |
(rtac disjI2 1), |
|
851 |
(rtac allI 1), |
|
852 |
(res_inst_tac [("s","f`x"),("t","c")] subst 1), |
|
853 |
(atac 1), |
|
854 |
(res_inst_tac [("a","f`(UU::'a)")] (refl RS box_equals) 1), |
|
855 |
(etac allE 1),(etac allE 1), |
|
856 |
(dtac mp 1), |
|
1780 | 857 |
(res_inst_tac [("fo","f")] (minimal RS monofun_cfun_arg) 1), |
1461 | 858 |
(etac disjE 1), |
859 |
(contr_tac 1), |
|
860 |
(atac 1), |
|
861 |
(etac allE 1), |
|
862 |
(etac allE 1), |
|
863 |
(dtac mp 1), |
|
1780 | 864 |
(res_inst_tac [("fo","f")] (minimal RS monofun_cfun_arg) 1), |
1461 | 865 |
(etac disjE 1), |
866 |
(contr_tac 1), |
|
867 |
(atac 1) |
|
868 |
]); |
|
625 | 869 |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
870 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
871 |
(* admissibility of special formulae and propagation *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
872 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
873 |
|
892 | 874 |
qed_goalw "adm_less" Fix.thy [adm_def] |
1461 | 875 |
"[|cont u;cont v|]==> adm(%x.u x << v x)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
876 |
(fn prems => |
1461 | 877 |
[ |
878 |
(cut_facts_tac prems 1), |
|
879 |
(strip_tac 1), |
|
880 |
(etac (cont2contlub RS contlubE RS spec RS mp RS ssubst) 1), |
|
881 |
(atac 1), |
|
882 |
(etac (cont2contlub RS contlubE RS spec RS mp RS ssubst) 1), |
|
883 |
(atac 1), |
|
884 |
(rtac lub_mono 1), |
|
885 |
(cut_facts_tac prems 1), |
|
886 |
(etac (cont2mono RS ch2ch_monofun) 1), |
|
887 |
(atac 1), |
|
888 |
(cut_facts_tac prems 1), |
|
889 |
(etac (cont2mono RS ch2ch_monofun) 1), |
|
890 |
(atac 1), |
|
891 |
(atac 1) |
|
892 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
893 |
|
892 | 894 |
qed_goal "adm_conj" Fix.thy |
1461 | 895 |
"[| adm P; adm Q |] ==> adm(%x. P x & Q x)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
896 |
(fn prems => |
1461 | 897 |
[ |
898 |
(cut_facts_tac prems 1), |
|
899 |
(rtac (adm_def2 RS iffD2) 1), |
|
900 |
(strip_tac 1), |
|
901 |
(rtac conjI 1), |
|
902 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
903 |
(atac 1), |
|
904 |
(atac 1), |
|
905 |
(fast_tac HOL_cs 1), |
|
906 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
907 |
(atac 1), |
|
908 |
(atac 1), |
|
909 |
(fast_tac HOL_cs 1) |
|
910 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
911 |
|
892 | 912 |
qed_goal "adm_cong" Fix.thy |
1461 | 913 |
"(!x. P x = Q x) ==> adm P = adm Q " |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
914 |
(fn prems => |
1461 | 915 |
[ |
916 |
(cut_facts_tac prems 1), |
|
917 |
(res_inst_tac [("s","P"),("t","Q")] subst 1), |
|
918 |
(rtac refl 2), |
|
919 |
(rtac ext 1), |
|
920 |
(etac spec 1) |
|
921 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
922 |
|
892 | 923 |
qed_goalw "adm_not_free" Fix.thy [adm_def] "adm(%x.t)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
924 |
(fn prems => |
1461 | 925 |
[ |
926 |
(fast_tac HOL_cs 1) |
|
927 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
928 |
|
892 | 929 |
qed_goalw "adm_not_less" Fix.thy [adm_def] |
1461 | 930 |
"cont t ==> adm(%x.~ (t x) << u)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
931 |
(fn prems => |
1461 | 932 |
[ |
933 |
(cut_facts_tac prems 1), |
|
934 |
(strip_tac 1), |
|
935 |
(rtac contrapos 1), |
|
936 |
(etac spec 1), |
|
937 |
(rtac trans_less 1), |
|
938 |
(atac 2), |
|
939 |
(etac (cont2mono RS monofun_fun_arg) 1), |
|
940 |
(rtac is_ub_thelub 1), |
|
941 |
(atac 1) |
|
942 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
943 |
|
892 | 944 |
qed_goal "adm_all" Fix.thy |
1461 | 945 |
" !y.adm(P y) ==> adm(%x.!y.P y x)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
946 |
(fn prems => |
1461 | 947 |
[ |
948 |
(cut_facts_tac prems 1), |
|
949 |
(rtac (adm_def2 RS iffD2) 1), |
|
950 |
(strip_tac 1), |
|
951 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
952 |
(etac spec 1), |
|
953 |
(atac 1), |
|
954 |
(rtac allI 1), |
|
955 |
(dtac spec 1), |
|
956 |
(etac spec 1) |
|
957 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
958 |
|
1779 | 959 |
bind_thm ("adm_all2", allI RS adm_all); |
625 | 960 |
|
892 | 961 |
qed_goal "adm_subst" Fix.thy |
1461 | 962 |
"[|cont t; adm P|] ==> adm(%x. P (t x))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
963 |
(fn prems => |
1461 | 964 |
[ |
965 |
(cut_facts_tac prems 1), |
|
966 |
(rtac (adm_def2 RS iffD2) 1), |
|
967 |
(strip_tac 1), |
|
2033 | 968 |
(stac (cont2contlub RS contlubE RS spec RS mp) 1), |
1461 | 969 |
(atac 1), |
970 |
(atac 1), |
|
971 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
972 |
(atac 1), |
|
973 |
(rtac (cont2mono RS ch2ch_monofun) 1), |
|
974 |
(atac 1), |
|
975 |
(atac 1), |
|
976 |
(atac 1) |
|
977 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
978 |
|
892 | 979 |
qed_goal "adm_UU_not_less" Fix.thy "adm(%x.~ UU << t(x))" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
980 |
(fn prems => |
1461 | 981 |
[ |
982 |
(res_inst_tac [("P2","%x.False")] (adm_cong RS iffD1) 1), |
|
983 |
(Asm_simp_tac 1), |
|
984 |
(rtac adm_not_free 1) |
|
985 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
986 |
|
892 | 987 |
qed_goalw "adm_not_UU" Fix.thy [adm_def] |
1461 | 988 |
"cont(t)==> adm(%x.~ (t x) = UU)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
989 |
(fn prems => |
1461 | 990 |
[ |
991 |
(cut_facts_tac prems 1), |
|
992 |
(strip_tac 1), |
|
993 |
(rtac contrapos 1), |
|
994 |
(etac spec 1), |
|
995 |
(rtac (chain_UU_I RS spec) 1), |
|
996 |
(rtac (cont2mono RS ch2ch_monofun) 1), |
|
997 |
(atac 1), |
|
998 |
(atac 1), |
|
999 |
(rtac (cont2contlub RS contlubE RS spec RS mp RS subst) 1), |
|
1000 |
(atac 1), |
|
1001 |
(atac 1), |
|
1002 |
(atac 1) |
|
1003 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1004 |
|
892 | 1005 |
qed_goal "adm_eq" Fix.thy |
1461 | 1006 |
"[|cont u ; cont v|]==> adm(%x. u x = v x)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1007 |
(fn prems => |
1461 | 1008 |
[ |
1009 |
(rtac (adm_cong RS iffD1) 1), |
|
1010 |
(rtac allI 1), |
|
1011 |
(rtac iffI 1), |
|
1012 |
(rtac antisym_less 1), |
|
1013 |
(rtac antisym_less_inverse 3), |
|
1014 |
(atac 3), |
|
1015 |
(etac conjunct1 1), |
|
1016 |
(etac conjunct2 1), |
|
1017 |
(rtac adm_conj 1), |
|
1018 |
(rtac adm_less 1), |
|
1019 |
(resolve_tac prems 1), |
|
1020 |
(resolve_tac prems 1), |
|
1021 |
(rtac adm_less 1), |
|
1022 |
(resolve_tac prems 1), |
|
1023 |
(resolve_tac prems 1) |
|
1024 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1025 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1026 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1027 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1028 |
(* admissibility for disjunction is hard to prove. It takes 10 Lemmas *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1029 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1030 |
|
1992 | 1031 |
local |
1032 |
||
1033 |
val adm_disj_lemma1 = prove_goal Pcpo.thy |
|
1034 |
"[| is_chain Y; !n.P (Y n) | Q(Y n)|]\ |
|
1035 |
\ ==> (? i.!j. i<j --> Q(Y(j))) | (!i.? j.i<j & P(Y(j)))" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1036 |
(fn prems => |
1461 | 1037 |
[ |
1038 |
(cut_facts_tac prems 1), |
|
1039 |
(fast_tac HOL_cs 1) |
|
1040 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1041 |
|
1992 | 1042 |
val adm_disj_lemma2 = prove_goal Fix.thy |
1043 |
"[| adm(Q); ? X.is_chain(X) & (!n.Q(X(n))) &\ |
|
1044 |
\ lub(range(Y))=lub(range(X))|] ==> Q(lub(range(Y)))" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1045 |
(fn prems => |
1461 | 1046 |
[ |
1047 |
(cut_facts_tac prems 1), |
|
1048 |
(etac exE 1), |
|
1049 |
(etac conjE 1), |
|
1050 |
(etac conjE 1), |
|
1051 |
(res_inst_tac [("s","lub(range(X))"),("t","lub(range(Y))")] ssubst 1), |
|
1052 |
(atac 1), |
|
1053 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
1054 |
(atac 1), |
|
1055 |
(atac 1), |
|
1056 |
(atac 1) |
|
1057 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1058 |
|
1992 | 1059 |
val adm_disj_lemma3 = prove_goal Fix.thy |
1060 |
"[| is_chain(Y); ! j. i < j --> Q(Y(j)) |] ==>\ |
|
1061 |
\ is_chain(%m. if m < Suc i then Y(Suc i) else Y m)" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1062 |
(fn prems => |
1461 | 1063 |
[ |
1064 |
(cut_facts_tac prems 1), |
|
1065 |
(rtac is_chainI 1), |
|
1066 |
(rtac allI 1), |
|
1067 |
(res_inst_tac [("m","i"),("n","ia")] nat_less_cases 1), |
|
1068 |
(res_inst_tac [("s","False"),("t","ia < Suc(i)")] ssubst 1), |
|
1069 |
(rtac iffI 1), |
|
1070 |
(etac FalseE 2), |
|
1071 |
(rtac notE 1), |
|
1072 |
(rtac (not_less_eq RS iffD2) 1), |
|
1073 |
(atac 1), |
|
1074 |
(atac 1), |
|
1075 |
(res_inst_tac [("s","False"),("t","Suc(ia) < Suc(i)")] ssubst 1), |
|
1076 |
(Asm_simp_tac 1), |
|
1077 |
(rtac iffI 1), |
|
1078 |
(etac FalseE 2), |
|
1079 |
(rtac notE 1), |
|
1080 |
(etac less_not_sym 1), |
|
1081 |
(atac 1), |
|
1082 |
(Asm_simp_tac 1), |
|
1083 |
(etac (is_chainE RS spec) 1), |
|
1084 |
(hyp_subst_tac 1), |
|
1085 |
(Asm_simp_tac 1), |
|
1675 | 1086 |
(Asm_simp_tac 1), |
2033 | 1087 |
(asm_simp_tac (!simpset addsimps [less_Suc_eq]) 1) |
1461 | 1088 |
]); |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1089 |
|
1992 | 1090 |
val adm_disj_lemma4 = prove_goal Fix.thy |
1091 |
"[| ! j. i < j --> Q(Y(j)) |] ==>\ |
|
1092 |
\ ! n. Q( if n < Suc i then Y(Suc i) else Y n)" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1093 |
(fn prems => |
1461 | 1094 |
[ |
1095 |
(cut_facts_tac prems 1), |
|
1096 |
(rtac allI 1), |
|
1097 |
(res_inst_tac [("m","n"),("n","Suc(i)")] nat_less_cases 1), |
|
1992 | 1098 |
(res_inst_tac[("s","Y(Suc(i))"), |
2033 | 1099 |
("t","if n<Suc(i) then Y(Suc(i)) else Y n")] ssubst 1), |
1461 | 1100 |
(Asm_simp_tac 1), |
1101 |
(etac allE 1), |
|
1102 |
(rtac mp 1), |
|
1103 |
(atac 1), |
|
1104 |
(Asm_simp_tac 1), |
|
1992 | 1105 |
(res_inst_tac[("s","Y(n)"), |
2033 | 1106 |
("t","if n<Suc(i) then Y(Suc(i)) else Y(n)")] ssubst 1), |
1461 | 1107 |
(Asm_simp_tac 1), |
1108 |
(hyp_subst_tac 1), |
|
1109 |
(dtac spec 1), |
|
1110 |
(rtac mp 1), |
|
1111 |
(atac 1), |
|
1112 |
(Asm_simp_tac 1), |
|
1992 | 1113 |
(res_inst_tac [("s","Y(n)"), |
2033 | 1114 |
("t","if n < Suc(i) then Y(Suc(i)) else Y(n)")]ssubst 1), |
1461 | 1115 |
(res_inst_tac [("s","False"),("t","n < Suc(i)")] ssubst 1), |
1116 |
(rtac iffI 1), |
|
1117 |
(etac FalseE 2), |
|
1118 |
(rtac notE 1), |
|
1119 |
(etac less_not_sym 1), |
|
1120 |
(atac 1), |
|
1121 |
(Asm_simp_tac 1), |
|
1122 |
(dtac spec 1), |
|
1123 |
(rtac mp 1), |
|
1124 |
(atac 1), |
|
1125 |
(etac Suc_lessD 1) |
|
1126 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1127 |
|
1992 | 1128 |
val adm_disj_lemma5 = prove_goal Fix.thy |
1129 |
"[| is_chain(Y::nat=>'a); ! j. i < j --> Q(Y(j)) |] ==>\ |
|
1130 |
\ lub(range(Y)) = lub(range(%m. if m< Suc(i) then Y(Suc(i)) else Y m))" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1131 |
(fn prems => |
1461 | 1132 |
[ |
1133 |
(cut_facts_tac prems 1), |
|
1134 |
(rtac lub_equal2 1), |
|
1135 |
(atac 2), |
|
1136 |
(rtac adm_disj_lemma3 2), |
|
1137 |
(atac 2), |
|
1138 |
(atac 2), |
|
1139 |
(res_inst_tac [("x","i")] exI 1), |
|
1140 |
(strip_tac 1), |
|
1141 |
(res_inst_tac [("s","False"),("t","ia < Suc(i)")] ssubst 1), |
|
1142 |
(rtac iffI 1), |
|
1143 |
(etac FalseE 2), |
|
1144 |
(rtac notE 1), |
|
1145 |
(rtac (not_less_eq RS iffD2) 1), |
|
1146 |
(atac 1), |
|
1147 |
(atac 1), |
|
2033 | 1148 |
(stac if_False 1), |
1461 | 1149 |
(rtac refl 1) |
1150 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1151 |
|
1992 | 1152 |
val adm_disj_lemma6 = prove_goal Fix.thy |
1153 |
"[| is_chain(Y::nat=>'a); ? i. ! j. i < j --> Q(Y(j)) |] ==>\ |
|
1154 |
\ ? X. is_chain(X) & (! n. Q(X(n))) & lub(range(Y)) = lub(range(X))" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1155 |
(fn prems => |
1461 | 1156 |
[ |
1157 |
(cut_facts_tac prems 1), |
|
1158 |
(etac exE 1), |
|
1159 |
(res_inst_tac [("x","%m.if m<Suc(i) then Y(Suc(i)) else Y m")] exI 1), |
|
1160 |
(rtac conjI 1), |
|
1161 |
(rtac adm_disj_lemma3 1), |
|
1162 |
(atac 1), |
|
1163 |
(atac 1), |
|
1164 |
(rtac conjI 1), |
|
1165 |
(rtac adm_disj_lemma4 1), |
|
1166 |
(atac 1), |
|
1167 |
(rtac adm_disj_lemma5 1), |
|
1168 |
(atac 1), |
|
1169 |
(atac 1) |
|
1170 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1171 |
|
1992 | 1172 |
val adm_disj_lemma7 = prove_goal Fix.thy |
1173 |
"[| is_chain(Y::nat=>'a); ! i. ? j. i < j & P(Y(j)) |] ==>\ |
|
1174 |
\ is_chain(%m. Y(Least(%j. m<j & P(Y(j)))))" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1175 |
(fn prems => |
1461 | 1176 |
[ |
1177 |
(cut_facts_tac prems 1), |
|
1178 |
(rtac is_chainI 1), |
|
1179 |
(rtac allI 1), |
|
1180 |
(rtac chain_mono3 1), |
|
1181 |
(atac 1), |
|
1675 | 1182 |
(rtac Least_le 1), |
1461 | 1183 |
(rtac conjI 1), |
1184 |
(rtac Suc_lessD 1), |
|
1185 |
(etac allE 1), |
|
1186 |
(etac exE 1), |
|
1675 | 1187 |
(rtac (LeastI RS conjunct1) 1), |
1461 | 1188 |
(atac 1), |
1189 |
(etac allE 1), |
|
1190 |
(etac exE 1), |
|
1675 | 1191 |
(rtac (LeastI RS conjunct2) 1), |
1461 | 1192 |
(atac 1) |
1193 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1194 |
|
1992 | 1195 |
val adm_disj_lemma8 = prove_goal Fix.thy |
1196 |
"[| ! i. ? j. i < j & P(Y(j)) |] ==> ! m. P(Y(Least(%j. m<j & P(Y(j)))))" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1197 |
(fn prems => |
1461 | 1198 |
[ |
1199 |
(cut_facts_tac prems 1), |
|
1200 |
(strip_tac 1), |
|
1201 |
(etac allE 1), |
|
1202 |
(etac exE 1), |
|
1675 | 1203 |
(etac (LeastI RS conjunct2) 1) |
1461 | 1204 |
]); |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1205 |
|
1992 | 1206 |
val adm_disj_lemma9 = prove_goal Fix.thy |
1207 |
"[| is_chain(Y::nat=>'a); ! i. ? j. i < j & P(Y(j)) |] ==>\ |
|
1208 |
\ lub(range(Y)) = lub(range(%m. Y(Least(%j. m<j & P(Y(j))))))" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1209 |
(fn prems => |
1461 | 1210 |
[ |
1211 |
(cut_facts_tac prems 1), |
|
1212 |
(rtac antisym_less 1), |
|
1213 |
(rtac lub_mono 1), |
|
1214 |
(atac 1), |
|
1215 |
(rtac adm_disj_lemma7 1), |
|
1216 |
(atac 1), |
|
1217 |
(atac 1), |
|
1218 |
(strip_tac 1), |
|
1219 |
(rtac (chain_mono RS mp) 1), |
|
1220 |
(atac 1), |
|
1221 |
(etac allE 1), |
|
1222 |
(etac exE 1), |
|
1675 | 1223 |
(rtac (LeastI RS conjunct1) 1), |
1461 | 1224 |
(atac 1), |
1225 |
(rtac lub_mono3 1), |
|
1226 |
(rtac adm_disj_lemma7 1), |
|
1227 |
(atac 1), |
|
1228 |
(atac 1), |
|
1229 |
(atac 1), |
|
1230 |
(strip_tac 1), |
|
1231 |
(rtac exI 1), |
|
1232 |
(rtac (chain_mono RS mp) 1), |
|
1233 |
(atac 1), |
|
1234 |
(rtac lessI 1) |
|
1235 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1236 |
|
1992 | 1237 |
val adm_disj_lemma10 = prove_goal Fix.thy |
1238 |
"[| is_chain(Y::nat=>'a); ! i. ? j. i < j & P(Y(j)) |] ==>\ |
|
1239 |
\ ? X. is_chain(X) & (! n. P(X(n))) & lub(range(Y)) = lub(range(X))" |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1240 |
(fn prems => |
1461 | 1241 |
[ |
1242 |
(cut_facts_tac prems 1), |
|
1675 | 1243 |
(res_inst_tac [("x","%m. Y(Least(%j. m<j & P(Y(j))))")] exI 1), |
1461 | 1244 |
(rtac conjI 1), |
1245 |
(rtac adm_disj_lemma7 1), |
|
1246 |
(atac 1), |
|
1247 |
(atac 1), |
|
1248 |
(rtac conjI 1), |
|
1249 |
(rtac adm_disj_lemma8 1), |
|
1250 |
(atac 1), |
|
1251 |
(rtac adm_disj_lemma9 1), |
|
1252 |
(atac 1), |
|
1253 |
(atac 1) |
|
1254 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1255 |
|
1992 | 1256 |
val adm_disj_lemma12 = prove_goal Fix.thy |
1257 |
"[| adm(P); is_chain(Y);? i. ! j. i < j --> P(Y(j))|]==>P(lub(range(Y)))" |
|
1258 |
(fn prems => |
|
1259 |
[ |
|
1260 |
(cut_facts_tac prems 1), |
|
1261 |
(etac adm_disj_lemma2 1), |
|
1262 |
(etac adm_disj_lemma6 1), |
|
1263 |
(atac 1) |
|
1264 |
]); |
|
430 | 1265 |
|
1992 | 1266 |
in |
1267 |
||
1268 |
val adm_lemma11 = prove_goal Fix.thy |
|
430 | 1269 |
"[| adm(P); is_chain(Y); ! i. ? j. i < j & P(Y(j)) |]==>P(lub(range(Y)))" |
1270 |
(fn prems => |
|
1461 | 1271 |
[ |
1272 |
(cut_facts_tac prems 1), |
|
1273 |
(etac adm_disj_lemma2 1), |
|
1274 |
(etac adm_disj_lemma10 1), |
|
1275 |
(atac 1) |
|
1276 |
]); |
|
430 | 1277 |
|
1992 | 1278 |
val adm_disj = prove_goal Fix.thy |
1461 | 1279 |
"[| adm P; adm Q |] ==> adm(%x.P x | Q x)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1280 |
(fn prems => |
1461 | 1281 |
[ |
1282 |
(cut_facts_tac prems 1), |
|
1283 |
(rtac (adm_def2 RS iffD2) 1), |
|
1284 |
(strip_tac 1), |
|
1285 |
(rtac (adm_disj_lemma1 RS disjE) 1), |
|
1286 |
(atac 1), |
|
1287 |
(atac 1), |
|
1288 |
(rtac disjI2 1), |
|
1289 |
(etac adm_disj_lemma12 1), |
|
1290 |
(atac 1), |
|
1291 |
(atac 1), |
|
1292 |
(rtac disjI1 1), |
|
1992 | 1293 |
(etac adm_lemma11 1), |
1461 | 1294 |
(atac 1), |
1295 |
(atac 1) |
|
1296 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1297 |
|
1992 | 1298 |
end; |
1299 |
||
1300 |
bind_thm("adm_lemma11",adm_lemma11); |
|
1301 |
bind_thm("adm_disj",adm_disj); |
|
430 | 1302 |
|
1872 | 1303 |
qed_goal "adm_imp" Fix.thy |
1461 | 1304 |
"[| adm(%x.~(P x)); adm Q |] ==> adm(%x.P x --> Q x)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1305 |
(fn prems => |
1461 | 1306 |
[ |
1307 |
(cut_facts_tac prems 1), |
|
1308 |
(res_inst_tac [("P2","%x.~(P x)|Q x")] (adm_cong RS iffD1) 1), |
|
1309 |
(fast_tac HOL_cs 1), |
|
1310 |
(rtac adm_disj 1), |
|
1311 |
(atac 1), |
|
1312 |
(atac 1) |
|
1313 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1314 |
|
1675 | 1315 |
qed_goal "adm_not_conj" Fix.thy |
1681 | 1316 |
"[| adm (%x. ~ P x); adm (%x. ~ Q x) |] ==> adm (%x. ~ (P x & Q x))"(fn prems=>[ |
2033 | 1317 |
cut_facts_tac prems 1, |
1318 |
subgoal_tac |
|
1319 |
"(%x. ~ (P x & Q x)) = (%x. ~ P x | ~ Q x)" 1, |
|
1320 |
rtac ext 2, |
|
1321 |
fast_tac HOL_cs 2, |
|
1322 |
etac ssubst 1, |
|
1323 |
etac adm_disj 1, |
|
1324 |
atac 1]); |
|
1675 | 1325 |
|
1992 | 1326 |
val adm_thms = [adm_imp,adm_disj,adm_eq,adm_not_UU,adm_UU_not_less, |
1327 |
adm_all2,adm_not_less,adm_not_free,adm_not_conj,adm_conj,adm_less]; |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1328 |