author | paulson |
Thu, 21 Mar 1996 13:02:26 +0100 | |
changeset 1601 | 0ef6ea27ab15 |
parent 1461 | 6bcb44e4d6e5 |
child 1675 | 36ba4da350c3 |
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), |
|
34 |
(Asm_simp_tac 1) |
|
35 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
36 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
37 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
38 |
(* the sequence of function itertaions is a chain *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
39 |
(* 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
|
40 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
41 |
|
892 | 42 |
qed_goalw "is_chain_iterate2" Fix.thy [is_chain] |
1461 | 43 |
" 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
|
44 |
(fn prems => |
1461 | 45 |
[ |
46 |
(cut_facts_tac prems 1), |
|
47 |
(strip_tac 1), |
|
48 |
(Simp_tac 1), |
|
49 |
(nat_ind_tac "i" 1), |
|
50 |
(Asm_simp_tac 1), |
|
51 |
(Asm_simp_tac 1), |
|
52 |
(etac monofun_cfun_arg 1) |
|
53 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
54 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
55 |
|
892 | 56 |
qed_goal "is_chain_iterate" Fix.thy |
1461 | 57 |
"is_chain (%i.iterate i F UU)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
58 |
(fn prems => |
1461 | 59 |
[ |
60 |
(rtac is_chain_iterate2 1), |
|
61 |
(rtac minimal 1) |
|
62 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
63 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
64 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
65 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
66 |
(* 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
|
67 |
(* omega cpo's *) |
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 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
70 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
71 |
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
|
72 |
(fn prems => |
1461 | 73 |
[ |
74 |
(rtac (contlub_cfun_arg RS ssubst) 1), |
|
75 |
(rtac is_chain_iterate 1), |
|
76 |
(rtac antisym_less 1), |
|
77 |
(rtac lub_mono 1), |
|
78 |
(rtac is_chain_iterate 1), |
|
79 |
(rtac ch2ch_fappR 1), |
|
80 |
(rtac is_chain_iterate 1), |
|
81 |
(rtac allI 1), |
|
82 |
(rtac (iterate_Suc RS subst) 1), |
|
83 |
(rtac (is_chain_iterate RS is_chainE RS spec) 1), |
|
84 |
(rtac is_lub_thelub 1), |
|
85 |
(rtac ch2ch_fappR 1), |
|
86 |
(rtac is_chain_iterate 1), |
|
87 |
(rtac ub_rangeI 1), |
|
88 |
(rtac allI 1), |
|
89 |
(rtac (iterate_Suc RS subst) 1), |
|
90 |
(rtac is_ub_thelub 1), |
|
91 |
(rtac is_chain_iterate 1) |
|
92 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
93 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
94 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
95 |
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
|
96 |
(fn prems => |
1461 | 97 |
[ |
98 |
(cut_facts_tac prems 1), |
|
99 |
(rtac is_lub_thelub 1), |
|
100 |
(rtac is_chain_iterate 1), |
|
101 |
(rtac ub_rangeI 1), |
|
102 |
(strip_tac 1), |
|
103 |
(nat_ind_tac "i" 1), |
|
104 |
(Asm_simp_tac 1), |
|
105 |
(Asm_simp_tac 1), |
|
106 |
(res_inst_tac [("t","x")] subst 1), |
|
107 |
(atac 1), |
|
108 |
(etac monofun_cfun_arg 1) |
|
109 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
110 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
111 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
112 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
113 |
(* monotonicity and continuity of iterate *) |
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 |
|
892 | 116 |
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
|
117 |
(fn prems => |
1461 | 118 |
[ |
119 |
(strip_tac 1), |
|
120 |
(nat_ind_tac "i" 1), |
|
121 |
(Asm_simp_tac 1), |
|
122 |
(Asm_simp_tac 1), |
|
123 |
(rtac (less_fun RS iffD2) 1), |
|
124 |
(rtac allI 1), |
|
125 |
(rtac monofun_cfun 1), |
|
126 |
(atac 1), |
|
127 |
(rtac (less_fun RS iffD1 RS spec) 1), |
|
128 |
(atac 1) |
|
129 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
130 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
131 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
132 |
(* 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
|
133 |
(* diagonalisation lemma for continuous functions with two arguments. *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
134 |
(* 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
|
135 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
136 |
|
892 | 137 |
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
|
138 |
(fn prems => |
1461 | 139 |
[ |
140 |
(strip_tac 1), |
|
141 |
(nat_ind_tac "i" 1), |
|
142 |
(Asm_simp_tac 1), |
|
143 |
(rtac (lub_const RS thelubI RS sym) 1), |
|
144 |
(Asm_simp_tac 1), |
|
145 |
(rtac ext 1), |
|
146 |
(rtac (thelub_fun RS ssubst) 1), |
|
147 |
(rtac is_chainI 1), |
|
148 |
(rtac allI 1), |
|
149 |
(rtac (less_fun RS iffD2) 1), |
|
150 |
(rtac allI 1), |
|
151 |
(rtac (is_chainE RS spec) 1), |
|
152 |
(rtac (monofun_fapp1 RS ch2ch_MF2LR) 1), |
|
153 |
(rtac allI 1), |
|
154 |
(rtac monofun_fapp2 1), |
|
155 |
(atac 1), |
|
156 |
(rtac ch2ch_fun 1), |
|
157 |
(rtac (monofun_iterate RS ch2ch_monofun) 1), |
|
158 |
(atac 1), |
|
159 |
(rtac (thelub_fun RS ssubst) 1), |
|
160 |
(rtac (monofun_iterate RS ch2ch_monofun) 1), |
|
161 |
(atac 1), |
|
162 |
(rtac contlub_cfun 1), |
|
163 |
(atac 1), |
|
164 |
(etac (monofun_iterate RS ch2ch_monofun RS ch2ch_fun) 1) |
|
165 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
166 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
167 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
168 |
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
|
169 |
(fn prems => |
1461 | 170 |
[ |
171 |
(rtac monocontlub2cont 1), |
|
172 |
(rtac monofun_iterate 1), |
|
173 |
(rtac contlub_iterate 1) |
|
174 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
175 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
176 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
177 |
(* 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
|
178 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
179 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
180 |
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
|
181 |
(fn prems => |
1461 | 182 |
[ |
183 |
(rtac monofunI 1), |
|
184 |
(strip_tac 1), |
|
185 |
(nat_ind_tac "n" 1), |
|
186 |
(Asm_simp_tac 1), |
|
187 |
(Asm_simp_tac 1), |
|
188 |
(etac monofun_cfun_arg 1) |
|
189 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
190 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
191 |
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
|
192 |
(fn prems => |
1461 | 193 |
[ |
194 |
(rtac contlubI 1), |
|
195 |
(strip_tac 1), |
|
196 |
(nat_ind_tac "n" 1), |
|
197 |
(Simp_tac 1), |
|
198 |
(Simp_tac 1), |
|
199 |
(res_inst_tac [("t","iterate n1 F (lub(range(%u. Y u)))"), |
|
200 |
("s","lub(range(%i. iterate n1 F (Y i)))")] ssubst 1), |
|
201 |
(atac 1), |
|
202 |
(rtac contlub_cfun_arg 1), |
|
203 |
(etac (monofun_iterate2 RS ch2ch_monofun) 1) |
|
204 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
205 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
206 |
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
|
207 |
(fn prems => |
1461 | 208 |
[ |
209 |
(rtac monocontlub2cont 1), |
|
210 |
(rtac monofun_iterate2 1), |
|
211 |
(rtac contlub_iterate2 1) |
|
212 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
213 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
214 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
215 |
(* monotonicity and continuity of Ifix *) |
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 |
|
892 | 218 |
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
|
219 |
(fn prems => |
1461 | 220 |
[ |
221 |
(strip_tac 1), |
|
222 |
(rtac lub_mono 1), |
|
223 |
(rtac is_chain_iterate 1), |
|
224 |
(rtac is_chain_iterate 1), |
|
225 |
(rtac allI 1), |
|
226 |
(rtac (less_fun RS iffD1 RS spec) 1), |
|
227 |
(etac (monofun_iterate RS monofunE RS spec RS spec RS mp) 1) |
|
228 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
229 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
230 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
231 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
232 |
(* 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
|
233 |
(* be derived for lubs in this argument *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
234 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
235 |
|
892 | 236 |
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
|
237 |
"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
|
238 |
(fn prems => |
1461 | 239 |
[ |
240 |
(cut_facts_tac prems 1), |
|
241 |
(rtac is_chainI 1), |
|
242 |
(strip_tac 1), |
|
243 |
(rtac lub_mono 1), |
|
244 |
(rtac is_chain_iterate 1), |
|
245 |
(rtac is_chain_iterate 1), |
|
246 |
(strip_tac 1), |
|
247 |
(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
|
248 |
RS spec) 1) |
1461 | 249 |
]); |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
250 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
251 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
252 |
(* 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
|
253 |
(* 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
|
254 |
(* 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
|
255 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
256 |
|
892 | 257 |
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
|
258 |
"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
|
259 |
(fn prems => |
1461 | 260 |
[ |
261 |
(cut_facts_tac prems 1), |
|
262 |
(rtac (thelub_fun RS subst) 1), |
|
263 |
(rtac (monofun_iterate RS ch2ch_monofun) 1), |
|
264 |
(atac 1), |
|
265 |
(rtac fun_cong 1), |
|
266 |
(rtac (contlub_iterate RS contlubE RS spec RS mp RS ssubst) 1), |
|
267 |
(atac 1), |
|
268 |
(rtac refl 1) |
|
269 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
270 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
271 |
|
892 | 272 |
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
|
273 |
\ 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
|
274 |
\ 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
|
275 |
(fn prems => |
1461 | 276 |
[ |
277 |
(cut_facts_tac prems 1), |
|
278 |
(rtac antisym_less 1), |
|
279 |
(rtac is_lub_thelub 1), |
|
280 |
(rtac (contlub_Ifix_lemma1 RS ext RS subst) 1), |
|
281 |
(atac 1), |
|
282 |
(rtac is_chain_iterate 1), |
|
283 |
(rtac ub_rangeI 1), |
|
284 |
(strip_tac 1), |
|
285 |
(rtac lub_mono 1), |
|
286 |
(etac (monofun_iterate RS ch2ch_monofun RS ch2ch_fun) 1), |
|
287 |
(etac is_chain_iterate_lub 1), |
|
288 |
(strip_tac 1), |
|
289 |
(rtac is_ub_thelub 1), |
|
290 |
(rtac is_chain_iterate 1), |
|
291 |
(rtac is_lub_thelub 1), |
|
292 |
(etac is_chain_iterate_lub 1), |
|
293 |
(rtac ub_rangeI 1), |
|
294 |
(strip_tac 1), |
|
295 |
(rtac lub_mono 1), |
|
296 |
(rtac is_chain_iterate 1), |
|
297 |
(rtac (contlub_Ifix_lemma1 RS ext RS subst) 1), |
|
298 |
(atac 1), |
|
299 |
(rtac is_chain_iterate 1), |
|
300 |
(strip_tac 1), |
|
301 |
(rtac is_ub_thelub 1), |
|
302 |
(etac (monofun_iterate RS ch2ch_monofun RS ch2ch_fun) 1) |
|
303 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
304 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
305 |
|
892 | 306 |
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
|
307 |
(fn prems => |
1461 | 308 |
[ |
309 |
(strip_tac 1), |
|
310 |
(rtac (contlub_Ifix_lemma1 RS ext RS ssubst) 1), |
|
311 |
(atac 1), |
|
312 |
(etac ex_lub_iterate 1) |
|
313 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
314 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
315 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
316 |
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
|
317 |
(fn prems => |
1461 | 318 |
[ |
319 |
(rtac monocontlub2cont 1), |
|
320 |
(rtac monofun_Ifix 1), |
|
321 |
(rtac contlub_Ifix 1) |
|
322 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
323 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
324 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
325 |
(* propagate properties of Ifix to its continuous counterpart *) |
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 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
328 |
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
|
329 |
(fn prems => |
1461 | 330 |
[ |
331 |
(asm_simp_tac (!simpset addsimps [cont_Ifix]) 1), |
|
332 |
(rtac Ifix_eq 1) |
|
333 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
334 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
335 |
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
|
336 |
(fn prems => |
1461 | 337 |
[ |
338 |
(cut_facts_tac prems 1), |
|
339 |
(asm_simp_tac (!simpset addsimps [cont_Ifix]) 1), |
|
340 |
(etac Ifix_least 1) |
|
341 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
342 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
343 |
|
1274 | 344 |
qed_goal "fix_eqI" Fix.thy |
345 |
"[| F`x = x; !z. F`z = z --> x << z |] ==> x = fix`F" |
|
346 |
(fn prems => |
|
1461 | 347 |
[ |
348 |
(cut_facts_tac prems 1), |
|
349 |
(rtac antisym_less 1), |
|
350 |
(etac allE 1), |
|
351 |
(etac mp 1), |
|
352 |
(rtac (fix_eq RS sym) 1), |
|
353 |
(etac fix_least 1) |
|
354 |
]); |
|
1274 | 355 |
|
356 |
||
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
357 |
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
|
358 |
(fn prems => |
1461 | 359 |
[ |
360 |
(rewrite_goals_tac prems), |
|
361 |
(rtac fix_eq 1) |
|
362 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
363 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
364 |
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
|
365 |
(fn prems => |
1461 | 366 |
[ |
367 |
(rtac trans 1), |
|
368 |
(rtac ((hd prems) RS fix_eq2 RS cfun_fun_cong) 1), |
|
369 |
(rtac refl 1) |
|
370 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
371 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
372 |
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
|
373 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
374 |
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
|
375 |
(fn prems => |
1461 | 376 |
[ |
377 |
(cut_facts_tac prems 1), |
|
378 |
(hyp_subst_tac 1), |
|
379 |
(rtac fix_eq 1) |
|
380 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
381 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
382 |
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
|
383 |
(fn prems => |
1461 | 384 |
[ |
385 |
(rtac trans 1), |
|
386 |
(rtac ((hd prems) RS fix_eq4 RS cfun_fun_cong) 1), |
|
387 |
(rtac refl 1) |
|
388 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
389 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
390 |
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
|
391 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
392 |
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
|
393 |
(fn prems => |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
394 |
[ |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
395 |
(rtac trans 1), |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
396 |
(rtac (fixdef RS fix_eq4) 1), |
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 beta_cfun 1), |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
399 |
(cont_tacR 1), |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
400 |
(rtac refl 1) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
401 |
]); |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
402 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
403 |
(* use this one for definitions! *) |
297 | 404 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
405 |
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
|
406 |
(fn prems => |
1461 | 407 |
[ |
408 |
(rtac trans 1), |
|
409 |
(rtac (fix_eq2) 1), |
|
410 |
(rtac fixdef 1), |
|
411 |
(rtac beta_cfun 1), |
|
412 |
(cont_tacR 1) |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
413 |
]); |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
414 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
415 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
416 |
(* better access to definitions *) |
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 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
419 |
|
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
420 |
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
|
421 |
(fn prems => |
1461 | 422 |
[ |
423 |
(rtac ext 1), |
|
424 |
(rewtac Ifix_def), |
|
425 |
(rtac refl 1) |
|
426 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
427 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
428 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
429 |
(* direct connection between fix and iteration without Ifix *) |
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 |
|
892 | 432 |
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
|
433 |
"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
|
434 |
(fn prems => |
1461 | 435 |
[ |
436 |
(fold_goals_tac [Ifix_def]), |
|
437 |
(asm_simp_tac (!simpset addsimps [cont_Ifix]) 1) |
|
438 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
439 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
440 |
|
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 |
(* Lemmas about admissibility and fixed point induction *) |
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 |
|
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 |
(* access to definitions *) |
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 |
|
892 | 449 |
qed_goalw "adm_def2" Fix.thy [adm_def] |
1461 | 450 |
"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
|
451 |
(fn prems => |
1461 | 452 |
[ |
453 |
(rtac refl 1) |
|
454 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
455 |
|
892 | 456 |
qed_goalw "admw_def2" Fix.thy [admw_def] |
1461 | 457 |
"admw(P) = (!F.(!n.P(iterate n F UU)) -->\ |
458 |
\ 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
|
459 |
(fn prems => |
1461 | 460 |
[ |
461 |
(rtac refl 1) |
|
462 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
463 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
464 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
465 |
(* an admissible formula is also weak admissible *) |
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 |
|
892 | 468 |
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
|
469 |
(fn prems => |
1461 | 470 |
[ |
471 |
(cut_facts_tac prems 1), |
|
472 |
(strip_tac 1), |
|
473 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
474 |
(atac 1), |
|
475 |
(rtac is_chain_iterate 1), |
|
476 |
(atac 1) |
|
477 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
478 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
479 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
480 |
(* fixed point induction *) |
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 |
|
892 | 483 |
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
|
484 |
"[| 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
|
485 |
(fn prems => |
1461 | 486 |
[ |
487 |
(cut_facts_tac prems 1), |
|
488 |
(rtac (fix_def2 RS ssubst) 1), |
|
489 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
490 |
(atac 1), |
|
491 |
(rtac is_chain_iterate 1), |
|
492 |
(rtac allI 1), |
|
493 |
(nat_ind_tac "i" 1), |
|
494 |
(rtac (iterate_0 RS ssubst) 1), |
|
495 |
(atac 1), |
|
496 |
(rtac (iterate_Suc RS ssubst) 1), |
|
497 |
(resolve_tac prems 1), |
|
498 |
(atac 1) |
|
499 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
500 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
501 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
502 |
(* computational induction for weak admissible formulae *) |
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 |
|
892 | 505 |
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
|
506 |
"[| 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
|
507 |
(fn prems => |
1461 | 508 |
[ |
509 |
(cut_facts_tac prems 1), |
|
510 |
(rtac (fix_def2 RS ssubst) 1), |
|
511 |
(rtac (admw_def2 RS iffD1 RS spec RS mp) 1), |
|
512 |
(atac 1), |
|
513 |
(rtac allI 1), |
|
514 |
(etac spec 1) |
|
515 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
516 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
517 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
518 |
(* 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
|
519 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
520 |
|
892 | 521 |
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
|
522 |
"!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
|
523 |
(fn prems => |
1461 | 524 |
[ |
525 |
(cut_facts_tac prems 1), |
|
526 |
(strip_tac 1), |
|
527 |
(rtac exE 1), |
|
528 |
(rtac mp 1), |
|
529 |
(etac spec 1), |
|
530 |
(atac 1), |
|
531 |
(rtac (lub_finch1 RS thelubI RS ssubst) 1), |
|
532 |
(atac 1), |
|
533 |
(atac 1), |
|
534 |
(etac spec 1) |
|
535 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
536 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
537 |
|
892 | 538 |
qed_goalw "adm_chain_finite" Fix.thy [chain_finite_def] |
1461 | 539 |
"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
|
540 |
(fn prems => |
1461 | 541 |
[ |
542 |
(cut_facts_tac prems 1), |
|
543 |
(etac adm_max_in_chain 1) |
|
544 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
545 |
|
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 |
(* flat types are chain_finite *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
548 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
549 |
|
1410
324aa8134639
changed predicate flat to is_flat in theory Fix.thy
regensbu
parents:
1274
diff
changeset
|
550 |
qed_goalw "flat_imp_chain_finite" Fix.thy [is_flat_def,chain_finite_def] |
1461 | 551 |
"is_flat(x::'a)==>chain_finite(x::'a)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
552 |
(fn prems => |
1461 | 553 |
[ |
554 |
(rewtac max_in_chain_def), |
|
555 |
(cut_facts_tac prems 1), |
|
556 |
(strip_tac 1), |
|
557 |
(res_inst_tac [("Q","!i.Y(i)=UU")] classical2 1), |
|
558 |
(res_inst_tac [("x","0")] exI 1), |
|
559 |
(strip_tac 1), |
|
560 |
(rtac trans 1), |
|
561 |
(etac spec 1), |
|
562 |
(rtac sym 1), |
|
563 |
(etac spec 1), |
|
564 |
(rtac (chain_mono2 RS exE) 1), |
|
565 |
(fast_tac HOL_cs 1), |
|
566 |
(atac 1), |
|
567 |
(res_inst_tac [("x","Suc(x)")] exI 1), |
|
568 |
(strip_tac 1), |
|
569 |
(rtac disjE 1), |
|
570 |
(atac 3), |
|
571 |
(rtac mp 1), |
|
572 |
(dtac spec 1), |
|
573 |
(etac spec 1), |
|
574 |
(etac (le_imp_less_or_eq RS disjE) 1), |
|
575 |
(etac (chain_mono RS mp) 1), |
|
576 |
(atac 1), |
|
577 |
(hyp_subst_tac 1), |
|
578 |
(rtac refl_less 1), |
|
579 |
(res_inst_tac [("P","Y(Suc(x)) = UU")] notE 1), |
|
580 |
(atac 2), |
|
581 |
(rtac mp 1), |
|
582 |
(etac spec 1), |
|
583 |
(Asm_simp_tac 1) |
|
584 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
585 |
|
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 |
val adm_flat = flat_imp_chain_finite RS adm_chain_finite; |
1410
324aa8134639
changed predicate flat to is_flat in theory Fix.thy
regensbu
parents:
1274
diff
changeset
|
588 |
(* is_flat(?x::?'a) ==> adm(?P::?'a => bool) *) |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
589 |
|
1410
324aa8134639
changed predicate flat to is_flat in theory Fix.thy
regensbu
parents:
1274
diff
changeset
|
590 |
qed_goalw "flat_void" Fix.thy [is_flat_def] "is_flat(UU::void)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
591 |
(fn prems => |
1461 | 592 |
[ |
593 |
(strip_tac 1), |
|
594 |
(rtac disjI1 1), |
|
595 |
(rtac unique_void2 1) |
|
596 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
597 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
598 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
599 |
(* continuous isomorphisms are strict *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
600 |
(* a prove for embedding projection pairs is similar *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
601 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
602 |
|
892 | 603 |
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
|
604 |
"!!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
|
605 |
\ ==> f`UU=UU & g`UU=UU" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
606 |
(fn prems => |
1461 | 607 |
[ |
608 |
(rtac conjI 1), |
|
609 |
(rtac UU_I 1), |
|
610 |
(res_inst_tac [("s","f`(g`(UU::'b))"),("t","UU::'b")] subst 1), |
|
611 |
(etac spec 1), |
|
612 |
(rtac (minimal RS monofun_cfun_arg) 1), |
|
613 |
(rtac UU_I 1), |
|
614 |
(res_inst_tac [("s","g`(f`(UU::'a))"),("t","UU::'a")] subst 1), |
|
615 |
(etac spec 1), |
|
616 |
(rtac (minimal RS monofun_cfun_arg) 1) |
|
617 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
618 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
619 |
|
892 | 620 |
qed_goal "isorep_defined" Fix.thy |
1461 | 621 |
"[|!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
|
622 |
(fn prems => |
1461 | 623 |
[ |
624 |
(cut_facts_tac prems 1), |
|
625 |
(etac swap 1), |
|
626 |
(dtac notnotD 1), |
|
627 |
(dres_inst_tac [("f","abs")] cfun_arg_cong 1), |
|
628 |
(etac box_equals 1), |
|
629 |
(fast_tac HOL_cs 1), |
|
630 |
(etac (iso_strict RS conjunct1) 1), |
|
631 |
(atac 1) |
|
632 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
633 |
|
892 | 634 |
qed_goal "isoabs_defined" Fix.thy |
1461 | 635 |
"[|!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
|
636 |
(fn prems => |
1461 | 637 |
[ |
638 |
(cut_facts_tac prems 1), |
|
639 |
(etac swap 1), |
|
640 |
(dtac notnotD 1), |
|
641 |
(dres_inst_tac [("f","rep")] cfun_arg_cong 1), |
|
642 |
(etac box_equals 1), |
|
643 |
(fast_tac HOL_cs 1), |
|
644 |
(etac (iso_strict RS conjunct2) 1), |
|
645 |
(atac 1) |
|
646 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
647 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
648 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
649 |
(* propagation of flatness and chainfiniteness by continuous isomorphisms *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
650 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
651 |
|
892 | 652 |
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
|
653 |
"!!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
|
654 |
\ ==> chain_finite(y::'b)" |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
655 |
(fn prems => |
1461 | 656 |
[ |
657 |
(rewtac max_in_chain_def), |
|
658 |
(strip_tac 1), |
|
659 |
(rtac exE 1), |
|
660 |
(res_inst_tac [("P","is_chain(%i.g`(Y i))")] mp 1), |
|
661 |
(etac spec 1), |
|
662 |
(etac ch2ch_fappR 1), |
|
663 |
(rtac exI 1), |
|
664 |
(strip_tac 1), |
|
665 |
(res_inst_tac [("s","f`(g`(Y x))"),("t","Y(x)")] subst 1), |
|
666 |
(etac spec 1), |
|
667 |
(res_inst_tac [("s","f`(g`(Y j))"),("t","Y(j)")] subst 1), |
|
668 |
(etac spec 1), |
|
669 |
(rtac cfun_arg_cong 1), |
|
670 |
(rtac mp 1), |
|
671 |
(etac spec 1), |
|
672 |
(atac 1) |
|
673 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
674 |
|
1410
324aa8134639
changed predicate flat to is_flat in theory Fix.thy
regensbu
parents:
1274
diff
changeset
|
675 |
qed_goalw "flat2flat" Fix.thy [is_flat_def] |
324aa8134639
changed predicate flat to is_flat in theory Fix.thy
regensbu
parents:
1274
diff
changeset
|
676 |
"!!f g.[|is_flat(x::'a); !y.f`(g`y)=(y::'b) ; !x.g`(f`x)=(x::'a) |] \ |
324aa8134639
changed predicate flat to is_flat in theory Fix.thy
regensbu
parents:
1274
diff
changeset
|
677 |
\ ==> is_flat(y::'b)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
678 |
(fn prems => |
1461 | 679 |
[ |
680 |
(strip_tac 1), |
|
681 |
(rtac disjE 1), |
|
682 |
(res_inst_tac [("P","g`x<<g`y")] mp 1), |
|
683 |
(etac monofun_cfun_arg 2), |
|
684 |
(dtac spec 1), |
|
685 |
(etac spec 1), |
|
686 |
(rtac disjI1 1), |
|
687 |
(rtac trans 1), |
|
688 |
(res_inst_tac [("s","f`(g`x)"),("t","x")] subst 1), |
|
689 |
(etac spec 1), |
|
690 |
(etac cfun_arg_cong 1), |
|
691 |
(rtac (iso_strict RS conjunct1) 1), |
|
692 |
(atac 1), |
|
693 |
(atac 1), |
|
694 |
(rtac disjI2 1), |
|
695 |
(res_inst_tac [("s","f`(g`x)"),("t","x")] subst 1), |
|
696 |
(etac spec 1), |
|
697 |
(res_inst_tac [("s","f`(g`y)"),("t","y")] subst 1), |
|
698 |
(etac spec 1), |
|
699 |
(etac cfun_arg_cong 1) |
|
700 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
701 |
|
625 | 702 |
(* ------------------------------------------------------------------------- *) |
703 |
(* a result about functions with flat codomain *) |
|
704 |
(* ------------------------------------------------------------------------- *) |
|
705 |
||
1410
324aa8134639
changed predicate flat to is_flat in theory Fix.thy
regensbu
parents:
1274
diff
changeset
|
706 |
qed_goalw "flat_codom" Fix.thy [is_flat_def] |
324aa8134639
changed predicate flat to is_flat in theory Fix.thy
regensbu
parents:
1274
diff
changeset
|
707 |
"[|is_flat(y::'b);f`(x::'a)=(c::'b)|] ==> f`(UU::'a)=(UU::'b) | (!z.f`(z::'a)=c)" |
625 | 708 |
(fn prems => |
1461 | 709 |
[ |
710 |
(cut_facts_tac prems 1), |
|
711 |
(res_inst_tac [("Q","f`(x::'a)=(UU::'b)")] classical2 1), |
|
712 |
(rtac disjI1 1), |
|
713 |
(rtac UU_I 1), |
|
714 |
(res_inst_tac [("s","f`(x)"),("t","UU::'b")] subst 1), |
|
715 |
(atac 1), |
|
716 |
(rtac (minimal RS monofun_cfun_arg) 1), |
|
717 |
(res_inst_tac [("Q","f`(UU::'a)=(UU::'b)")] classical2 1), |
|
718 |
(etac disjI1 1), |
|
719 |
(rtac disjI2 1), |
|
720 |
(rtac allI 1), |
|
721 |
(res_inst_tac [("s","f`x"),("t","c")] subst 1), |
|
722 |
(atac 1), |
|
723 |
(res_inst_tac [("a","f`(UU::'a)")] (refl RS box_equals) 1), |
|
724 |
(etac allE 1),(etac allE 1), |
|
725 |
(dtac mp 1), |
|
726 |
(res_inst_tac [("fo5","f")] (minimal RS monofun_cfun_arg) 1), |
|
727 |
(etac disjE 1), |
|
728 |
(contr_tac 1), |
|
729 |
(atac 1), |
|
730 |
(etac allE 1), |
|
731 |
(etac allE 1), |
|
732 |
(dtac mp 1), |
|
733 |
(res_inst_tac [("fo5","f")] (minimal RS monofun_cfun_arg) 1), |
|
734 |
(etac disjE 1), |
|
735 |
(contr_tac 1), |
|
736 |
(atac 1) |
|
737 |
]); |
|
625 | 738 |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
739 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
740 |
(* admissibility of special formulae and propagation *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
741 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
742 |
|
892 | 743 |
qed_goalw "adm_less" Fix.thy [adm_def] |
1461 | 744 |
"[|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
|
745 |
(fn prems => |
1461 | 746 |
[ |
747 |
(cut_facts_tac prems 1), |
|
748 |
(strip_tac 1), |
|
749 |
(etac (cont2contlub RS contlubE RS spec RS mp RS ssubst) 1), |
|
750 |
(atac 1), |
|
751 |
(etac (cont2contlub RS contlubE RS spec RS mp RS ssubst) 1), |
|
752 |
(atac 1), |
|
753 |
(rtac lub_mono 1), |
|
754 |
(cut_facts_tac prems 1), |
|
755 |
(etac (cont2mono RS ch2ch_monofun) 1), |
|
756 |
(atac 1), |
|
757 |
(cut_facts_tac prems 1), |
|
758 |
(etac (cont2mono RS ch2ch_monofun) 1), |
|
759 |
(atac 1), |
|
760 |
(atac 1) |
|
761 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
762 |
|
892 | 763 |
qed_goal "adm_conj" Fix.thy |
1461 | 764 |
"[| 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
|
765 |
(fn prems => |
1461 | 766 |
[ |
767 |
(cut_facts_tac prems 1), |
|
768 |
(rtac (adm_def2 RS iffD2) 1), |
|
769 |
(strip_tac 1), |
|
770 |
(rtac conjI 1), |
|
771 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
772 |
(atac 1), |
|
773 |
(atac 1), |
|
774 |
(fast_tac HOL_cs 1), |
|
775 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
776 |
(atac 1), |
|
777 |
(atac 1), |
|
778 |
(fast_tac HOL_cs 1) |
|
779 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
780 |
|
892 | 781 |
qed_goal "adm_cong" Fix.thy |
1461 | 782 |
"(!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
|
783 |
(fn prems => |
1461 | 784 |
[ |
785 |
(cut_facts_tac prems 1), |
|
786 |
(res_inst_tac [("s","P"),("t","Q")] subst 1), |
|
787 |
(rtac refl 2), |
|
788 |
(rtac ext 1), |
|
789 |
(etac spec 1) |
|
790 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
791 |
|
892 | 792 |
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
|
793 |
(fn prems => |
1461 | 794 |
[ |
795 |
(fast_tac HOL_cs 1) |
|
796 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
797 |
|
892 | 798 |
qed_goalw "adm_not_less" Fix.thy [adm_def] |
1461 | 799 |
"cont t ==> adm(%x.~ (t x) << u)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
800 |
(fn prems => |
1461 | 801 |
[ |
802 |
(cut_facts_tac prems 1), |
|
803 |
(strip_tac 1), |
|
804 |
(rtac contrapos 1), |
|
805 |
(etac spec 1), |
|
806 |
(rtac trans_less 1), |
|
807 |
(atac 2), |
|
808 |
(etac (cont2mono RS monofun_fun_arg) 1), |
|
809 |
(rtac is_ub_thelub 1), |
|
810 |
(atac 1) |
|
811 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
812 |
|
892 | 813 |
qed_goal "adm_all" Fix.thy |
1461 | 814 |
" !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
|
815 |
(fn prems => |
1461 | 816 |
[ |
817 |
(cut_facts_tac prems 1), |
|
818 |
(rtac (adm_def2 RS iffD2) 1), |
|
819 |
(strip_tac 1), |
|
820 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
821 |
(etac spec 1), |
|
822 |
(atac 1), |
|
823 |
(rtac allI 1), |
|
824 |
(dtac spec 1), |
|
825 |
(etac spec 1) |
|
826 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
827 |
|
625 | 828 |
val adm_all2 = (allI RS adm_all); |
829 |
||
892 | 830 |
qed_goal "adm_subst" Fix.thy |
1461 | 831 |
"[|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
|
832 |
(fn prems => |
1461 | 833 |
[ |
834 |
(cut_facts_tac prems 1), |
|
835 |
(rtac (adm_def2 RS iffD2) 1), |
|
836 |
(strip_tac 1), |
|
837 |
(rtac (cont2contlub RS contlubE RS spec RS mp RS ssubst) 1), |
|
838 |
(atac 1), |
|
839 |
(atac 1), |
|
840 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
841 |
(atac 1), |
|
842 |
(rtac (cont2mono RS ch2ch_monofun) 1), |
|
843 |
(atac 1), |
|
844 |
(atac 1), |
|
845 |
(atac 1) |
|
846 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
847 |
|
892 | 848 |
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
|
849 |
(fn prems => |
1461 | 850 |
[ |
851 |
(res_inst_tac [("P2","%x.False")] (adm_cong RS iffD1) 1), |
|
852 |
(Asm_simp_tac 1), |
|
853 |
(rtac adm_not_free 1) |
|
854 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
855 |
|
892 | 856 |
qed_goalw "adm_not_UU" Fix.thy [adm_def] |
1461 | 857 |
"cont(t)==> adm(%x.~ (t x) = UU)" |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
858 |
(fn prems => |
1461 | 859 |
[ |
860 |
(cut_facts_tac prems 1), |
|
861 |
(strip_tac 1), |
|
862 |
(rtac contrapos 1), |
|
863 |
(etac spec 1), |
|
864 |
(rtac (chain_UU_I RS spec) 1), |
|
865 |
(rtac (cont2mono RS ch2ch_monofun) 1), |
|
866 |
(atac 1), |
|
867 |
(atac 1), |
|
868 |
(rtac (cont2contlub RS contlubE RS spec RS mp RS subst) 1), |
|
869 |
(atac 1), |
|
870 |
(atac 1), |
|
871 |
(atac 1) |
|
872 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
873 |
|
892 | 874 |
qed_goal "adm_eq" Fix.thy |
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 |
(rtac (adm_cong RS iffD1) 1), |
|
879 |
(rtac allI 1), |
|
880 |
(rtac iffI 1), |
|
881 |
(rtac antisym_less 1), |
|
882 |
(rtac antisym_less_inverse 3), |
|
883 |
(atac 3), |
|
884 |
(etac conjunct1 1), |
|
885 |
(etac conjunct2 1), |
|
886 |
(rtac adm_conj 1), |
|
887 |
(rtac adm_less 1), |
|
888 |
(resolve_tac prems 1), |
|
889 |
(resolve_tac prems 1), |
|
890 |
(rtac adm_less 1), |
|
891 |
(resolve_tac prems 1), |
|
892 |
(resolve_tac prems 1) |
|
893 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
894 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
895 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
896 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
897 |
(* 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
|
898 |
(* ------------------------------------------------------------------------ *) |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
899 |
|
892 | 900 |
qed_goal "adm_disj_lemma1" Pcpo.thy |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
901 |
"[| is_chain Y; !n.P (Y n) | Q(Y n)|]\ |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
902 |
\ ==> (? i.!j. i<j --> Q(Y(j))) | (!i.? j.i<j & P(Y(j)))" |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
903 |
(fn prems => |
1461 | 904 |
[ |
905 |
(cut_facts_tac prems 1), |
|
906 |
(fast_tac HOL_cs 1) |
|
907 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
908 |
|
892 | 909 |
qed_goal "adm_disj_lemma2" Fix.thy |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
910 |
"[| adm(Q); ? X.is_chain(X) & (!n.Q(X(n))) &\ |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
911 |
\ lub(range(Y))=lub(range(X))|] ==> Q(lub(range(Y)))" |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
912 |
(fn prems => |
1461 | 913 |
[ |
914 |
(cut_facts_tac prems 1), |
|
915 |
(etac exE 1), |
|
916 |
(etac conjE 1), |
|
917 |
(etac conjE 1), |
|
918 |
(res_inst_tac [("s","lub(range(X))"),("t","lub(range(Y))")] ssubst 1), |
|
919 |
(atac 1), |
|
920 |
(rtac (adm_def2 RS iffD1 RS spec RS mp RS mp) 1), |
|
921 |
(atac 1), |
|
922 |
(atac 1), |
|
923 |
(atac 1) |
|
924 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
925 |
|
892 | 926 |
qed_goal "adm_disj_lemma3" Fix.thy |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
927 |
"[| is_chain(Y); ! j. i < j --> Q(Y(j)) |] ==>\ |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
928 |
\ 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
|
929 |
(fn prems => |
1461 | 930 |
[ |
931 |
(cut_facts_tac prems 1), |
|
932 |
(rtac is_chainI 1), |
|
933 |
(rtac allI 1), |
|
934 |
(res_inst_tac [("m","i"),("n","ia")] nat_less_cases 1), |
|
935 |
(res_inst_tac [("s","False"),("t","ia < Suc(i)")] ssubst 1), |
|
936 |
(rtac iffI 1), |
|
937 |
(etac FalseE 2), |
|
938 |
(rtac notE 1), |
|
939 |
(rtac (not_less_eq RS iffD2) 1), |
|
940 |
(atac 1), |
|
941 |
(atac 1), |
|
942 |
(res_inst_tac [("s","False"),("t","Suc(ia) < Suc(i)")] ssubst 1), |
|
943 |
(Asm_simp_tac 1), |
|
944 |
(rtac iffI 1), |
|
945 |
(etac FalseE 2), |
|
946 |
(rtac notE 1), |
|
947 |
(etac less_not_sym 1), |
|
948 |
(atac 1), |
|
949 |
(Asm_simp_tac 1), |
|
950 |
(etac (is_chainE RS spec) 1), |
|
951 |
(hyp_subst_tac 1), |
|
952 |
(Asm_simp_tac 1), |
|
953 |
(Asm_simp_tac 1) |
|
954 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
955 |
|
892 | 956 |
qed_goal "adm_disj_lemma4" Fix.thy |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
957 |
"[| ! j. i < j --> Q(Y(j)) |] ==>\ |
1461 | 958 |
\ ! 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
|
959 |
(fn prems => |
1461 | 960 |
[ |
961 |
(cut_facts_tac prems 1), |
|
962 |
(rtac allI 1), |
|
963 |
(res_inst_tac [("m","n"),("n","Suc(i)")] nat_less_cases 1), |
|
964 |
(res_inst_tac[("s","Y(Suc(i))"),("t","if n<Suc(i) then Y(Suc(i)) else Y n")] ssubst 1), |
|
965 |
(Asm_simp_tac 1), |
|
966 |
(etac allE 1), |
|
967 |
(rtac mp 1), |
|
968 |
(atac 1), |
|
969 |
(Asm_simp_tac 1), |
|
970 |
(res_inst_tac[("s","Y(n)"),("t","if n<Suc(i) then Y(Suc(i)) else Y(n)")] ssubst 1), |
|
971 |
(Asm_simp_tac 1), |
|
972 |
(hyp_subst_tac 1), |
|
973 |
(dtac spec 1), |
|
974 |
(rtac mp 1), |
|
975 |
(atac 1), |
|
976 |
(Asm_simp_tac 1), |
|
977 |
(res_inst_tac [("s","Y(n)"),("t","if n < Suc(i) then Y(Suc(i)) else Y(n)")] ssubst 1), |
|
978 |
(res_inst_tac [("s","False"),("t","n < Suc(i)")] ssubst 1), |
|
979 |
(rtac iffI 1), |
|
980 |
(etac FalseE 2), |
|
981 |
(rtac notE 1), |
|
982 |
(etac less_not_sym 1), |
|
983 |
(atac 1), |
|
984 |
(Asm_simp_tac 1), |
|
985 |
(dtac spec 1), |
|
986 |
(rtac mp 1), |
|
987 |
(atac 1), |
|
988 |
(etac Suc_lessD 1) |
|
989 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
990 |
|
892 | 991 |
qed_goal "adm_disj_lemma5" Fix.thy |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
992 |
"[| is_chain(Y::nat=>'a); ! j. i < j --> Q(Y(j)) |] ==>\ |
1168
74be52691d62
The curried version of HOLCF is now just called HOLCF. The old
regensbu
parents:
892
diff
changeset
|
993 |
\ 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
|
994 |
(fn prems => |
1461 | 995 |
[ |
996 |
(cut_facts_tac prems 1), |
|
997 |
(rtac lub_equal2 1), |
|
998 |
(atac 2), |
|
999 |
(rtac adm_disj_lemma3 2), |
|
1000 |
(atac 2), |
|
1001 |
(atac 2), |
|
1002 |
(res_inst_tac [("x","i")] exI 1), |
|
1003 |
(strip_tac 1), |
|
1004 |
(res_inst_tac [("s","False"),("t","ia < Suc(i)")] ssubst 1), |
|
1005 |
(rtac iffI 1), |
|
1006 |
(etac FalseE 2), |
|
1007 |
(rtac notE 1), |
|
1008 |
(rtac (not_less_eq RS iffD2) 1), |
|
1009 |
(atac 1), |
|
1010 |
(atac 1), |
|
1011 |
(rtac (if_False RS ssubst) 1), |
|
1012 |
(rtac refl 1) |
|
1013 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1014 |
|
892 | 1015 |
qed_goal "adm_disj_lemma6" Fix.thy |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1016 |
"[| is_chain(Y::nat=>'a); ? i. ! j. i < j --> Q(Y(j)) |] ==>\ |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1017 |
\ ? X. is_chain(X) & (! n. Q(X(n))) & lub(range(Y)) = lub(range(X))" |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1018 |
(fn prems => |
1461 | 1019 |
[ |
1020 |
(cut_facts_tac prems 1), |
|
1021 |
(etac exE 1), |
|
1022 |
(res_inst_tac [("x","%m.if m<Suc(i) then Y(Suc(i)) else Y m")] exI 1), |
|
1023 |
(rtac conjI 1), |
|
1024 |
(rtac adm_disj_lemma3 1), |
|
1025 |
(atac 1), |
|
1026 |
(atac 1), |
|
1027 |
(rtac conjI 1), |
|
1028 |
(rtac adm_disj_lemma4 1), |
|
1029 |
(atac 1), |
|
1030 |
(rtac adm_disj_lemma5 1), |
|
1031 |
(atac 1), |
|
1032 |
(atac 1) |
|
1033 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1034 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1035 |
|
892 | 1036 |
qed_goal "adm_disj_lemma7" Fix.thy |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1037 |
"[| is_chain(Y::nat=>'a); ! i. ? j. i < j & P(Y(j)) |] ==>\ |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1038 |
\ is_chain(%m. Y(theleast(%j. m<j & P(Y(j)))))" |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1039 |
(fn prems => |
1461 | 1040 |
[ |
1041 |
(cut_facts_tac prems 1), |
|
1042 |
(rtac is_chainI 1), |
|
1043 |
(rtac allI 1), |
|
1044 |
(rtac chain_mono3 1), |
|
1045 |
(atac 1), |
|
1046 |
(rtac theleast2 1), |
|
1047 |
(rtac conjI 1), |
|
1048 |
(rtac Suc_lessD 1), |
|
1049 |
(etac allE 1), |
|
1050 |
(etac exE 1), |
|
1051 |
(rtac (theleast1 RS conjunct1) 1), |
|
1052 |
(atac 1), |
|
1053 |
(etac allE 1), |
|
1054 |
(etac exE 1), |
|
1055 |
(rtac (theleast1 RS conjunct2) 1), |
|
1056 |
(atac 1) |
|
1057 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1058 |
|
892 | 1059 |
qed_goal "adm_disj_lemma8" Fix.thy |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1060 |
"[| ! i. ? j. i < j & P(Y(j)) |] ==> ! m. P(Y(theleast(%j. m<j & P(Y(j)))))" |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1061 |
(fn prems => |
1461 | 1062 |
[ |
1063 |
(cut_facts_tac prems 1), |
|
1064 |
(strip_tac 1), |
|
1065 |
(etac allE 1), |
|
1066 |
(etac exE 1), |
|
1067 |
(etac (theleast1 RS conjunct2) 1) |
|
1068 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1069 |
|
892 | 1070 |
qed_goal "adm_disj_lemma9" Fix.thy |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1071 |
"[| is_chain(Y::nat=>'a); ! i. ? j. i < j & P(Y(j)) |] ==>\ |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1072 |
\ lub(range(Y)) = lub(range(%m. Y(theleast(%j. m<j & P(Y(j))))))" |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1073 |
(fn prems => |
1461 | 1074 |
[ |
1075 |
(cut_facts_tac prems 1), |
|
1076 |
(rtac antisym_less 1), |
|
1077 |
(rtac lub_mono 1), |
|
1078 |
(atac 1), |
|
1079 |
(rtac adm_disj_lemma7 1), |
|
1080 |
(atac 1), |
|
1081 |
(atac 1), |
|
1082 |
(strip_tac 1), |
|
1083 |
(rtac (chain_mono RS mp) 1), |
|
1084 |
(atac 1), |
|
1085 |
(etac allE 1), |
|
1086 |
(etac exE 1), |
|
1087 |
(rtac (theleast1 RS conjunct1) 1), |
|
1088 |
(atac 1), |
|
1089 |
(rtac lub_mono3 1), |
|
1090 |
(rtac adm_disj_lemma7 1), |
|
1091 |
(atac 1), |
|
1092 |
(atac 1), |
|
1093 |
(atac 1), |
|
1094 |
(strip_tac 1), |
|
1095 |
(rtac exI 1), |
|
1096 |
(rtac (chain_mono RS mp) 1), |
|
1097 |
(atac 1), |
|
1098 |
(rtac lessI 1) |
|
1099 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1100 |
|
892 | 1101 |
qed_goal "adm_disj_lemma10" Fix.thy |
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1102 |
"[| is_chain(Y::nat=>'a); ! i. ? j. i < j & P(Y(j)) |] ==>\ |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1103 |
\ ? X. is_chain(X) & (! n. P(X(n))) & lub(range(Y)) = lub(range(X))" |
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1104 |
(fn prems => |
1461 | 1105 |
[ |
1106 |
(cut_facts_tac prems 1), |
|
1107 |
(res_inst_tac [("x","%m. Y(theleast(%j. m<j & P(Y(j))))")] exI 1), |
|
1108 |
(rtac conjI 1), |
|
1109 |
(rtac adm_disj_lemma7 1), |
|
1110 |
(atac 1), |
|
1111 |
(atac 1), |
|
1112 |
(rtac conjI 1), |
|
1113 |
(rtac adm_disj_lemma8 1), |
|
1114 |
(atac 1), |
|
1115 |
(rtac adm_disj_lemma9 1), |
|
1116 |
(atac 1), |
|
1117 |
(atac 1) |
|
1118 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1119 |
|
430 | 1120 |
|
892 | 1121 |
qed_goal "adm_disj_lemma11" Fix.thy |
430 | 1122 |
"[| adm(P); is_chain(Y); ! i. ? j. i < j & P(Y(j)) |]==>P(lub(range(Y)))" |
1123 |
(fn prems => |
|
1461 | 1124 |
[ |
1125 |
(cut_facts_tac prems 1), |
|
1126 |
(etac adm_disj_lemma2 1), |
|
1127 |
(etac adm_disj_lemma10 1), |
|
1128 |
(atac 1) |
|
1129 |
]); |
|
430 | 1130 |
|
892 | 1131 |
qed_goal "adm_disj_lemma12" Fix.thy |
430 | 1132 |
"[| adm(P); is_chain(Y);? i. ! j. i < j --> P(Y(j))|]==>P(lub(range(Y)))" |
1133 |
(fn prems => |
|
1461 | 1134 |
[ |
1135 |
(cut_facts_tac prems 1), |
|
1136 |
(etac adm_disj_lemma2 1), |
|
1137 |
(etac adm_disj_lemma6 1), |
|
1138 |
(atac 1) |
|
1139 |
]); |
|
430 | 1140 |
|
892 | 1141 |
qed_goal "adm_disj" Fix.thy |
1461 | 1142 |
"[| 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
|
1143 |
(fn prems => |
1461 | 1144 |
[ |
1145 |
(cut_facts_tac prems 1), |
|
1146 |
(rtac (adm_def2 RS iffD2) 1), |
|
1147 |
(strip_tac 1), |
|
1148 |
(rtac (adm_disj_lemma1 RS disjE) 1), |
|
1149 |
(atac 1), |
|
1150 |
(atac 1), |
|
1151 |
(rtac disjI2 1), |
|
1152 |
(etac adm_disj_lemma12 1), |
|
1153 |
(atac 1), |
|
1154 |
(atac 1), |
|
1155 |
(rtac disjI1 1), |
|
1156 |
(etac adm_disj_lemma11 1), |
|
1157 |
(atac 1), |
|
1158 |
(atac 1) |
|
1159 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1160 |
|
430 | 1161 |
|
892 | 1162 |
qed_goal "adm_impl" Fix.thy |
1461 | 1163 |
"[| 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
|
1164 |
(fn prems => |
1461 | 1165 |
[ |
1166 |
(cut_facts_tac prems 1), |
|
1167 |
(res_inst_tac [("P2","%x.~(P x)|Q x")] (adm_cong RS iffD1) 1), |
|
1168 |
(fast_tac HOL_cs 1), |
|
1169 |
(rtac adm_disj 1), |
|
1170 |
(atac 1), |
|
1171 |
(atac 1) |
|
1172 |
]); |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1173 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1174 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1175 |
|
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1176 |
val adm_thms = [adm_impl,adm_disj,adm_eq,adm_not_UU,adm_UU_not_less, |
1461 | 1177 |
adm_all2,adm_not_less,adm_not_free,adm_conj,adm_less |
1178 |
]; |
|
243
c22b85994e17
Franz Regensburger's Higher-Order Logic of Computable Functions embedding LCF
nipkow
parents:
diff
changeset
|
1179 |