141 lemma lleq_Int_Vset_subset [rule_format]: |
141 lemma lleq_Int_Vset_subset [rule_format]: |
142 "Ord(i) ==> \<forall>l l'. <l,l'> \<in> lleq(A) --> l Int Vset(i) \<subseteq> l'" |
142 "Ord(i) ==> \<forall>l l'. <l,l'> \<in> lleq(A) --> l Int Vset(i) \<subseteq> l'" |
143 apply (erule trans_induct) |
143 apply (erule trans_induct) |
144 apply (intro allI impI) |
144 apply (intro allI impI) |
145 apply (erule lleq.cases) |
145 apply (erule lleq.cases) |
146 apply (unfold QInr_def llist.con_defs) |
146 apply (unfold QInr_def llist.con_defs, safe) |
147 apply safe |
|
148 apply (fast elim!: Ord_trans bspec [elim_format]) |
147 apply (fast elim!: Ord_trans bspec [elim_format]) |
149 done |
148 done |
150 |
149 |
151 (*lleq(A) is a symmetric relation because qconverse(lleq(A)) is a fixedpoint*) |
150 (*lleq(A) is a symmetric relation because qconverse(lleq(A)) is a fixedpoint*) |
152 lemma lleq_symmetric: "<l,l'> \<in> lleq(A) ==> <l',l> \<in> lleq(A)" |
151 lemma lleq_symmetric: "<l,l'> \<in> lleq(A) ==> <l',l> \<in> lleq(A)" |
153 apply (erule lleq.coinduct [OF converseI]) |
152 apply (erule lleq.coinduct [OF converseI]) |
154 apply (rule lleq.dom_subset [THEN converse_type]) |
153 apply (rule lleq.dom_subset [THEN converse_type], safe) |
155 apply safe |
154 apply (erule lleq.cases, blast+) |
156 apply (erule lleq.cases) |
|
157 apply blast+ |
|
158 done |
155 done |
159 |
156 |
160 lemma lleq_implies_equal: "<l,l'> \<in> lleq(A) ==> l=l'" |
157 lemma lleq_implies_equal: "<l,l'> \<in> lleq(A) ==> l=l'" |
161 apply (rule equalityI) |
158 apply (rule equalityI) |
162 apply (assumption | rule lleq_Int_Vset_subset [THEN Int_Vset_subset] | |
159 apply (assumption | rule lleq_Int_Vset_subset [THEN Int_Vset_subset] | |
166 lemma equal_llist_implies_leq: |
163 lemma equal_llist_implies_leq: |
167 "[| l=l'; l \<in> llist(A) |] ==> <l,l'> \<in> lleq(A)" |
164 "[| l=l'; l \<in> llist(A) |] ==> <l,l'> \<in> lleq(A)" |
168 apply (rule_tac X = "{<l,l>. l \<in> llist (A) }" in lleq.coinduct) |
165 apply (rule_tac X = "{<l,l>. l \<in> llist (A) }" in lleq.coinduct) |
169 apply blast |
166 apply blast |
170 apply safe |
167 apply safe |
171 apply (erule_tac a="l" in llist.cases) |
168 apply (erule_tac a=l in llist.cases, fast+) |
172 apply fast+ |
|
173 done |
169 done |
174 |
170 |
175 |
171 |
176 (*** Lazy List Functions ***) |
172 (*** Lazy List Functions ***) |
177 |
173 |
218 "productive" functions -- cf Coquand's "Infinite Objects in Type Theory".*) |
214 "productive" functions -- cf Coquand's "Infinite Objects in Type Theory".*) |
219 lemma flip_llist_quniv_lemma [rule_format]: |
215 lemma flip_llist_quniv_lemma [rule_format]: |
220 "Ord(i) ==> \<forall>l \<in> llist(bool). flip(l) Int Vset(i) \<subseteq> univ(eclose(bool))" |
216 "Ord(i) ==> \<forall>l \<in> llist(bool). flip(l) Int Vset(i) \<subseteq> univ(eclose(bool))" |
221 apply (erule trans_induct) |
217 apply (erule trans_induct) |
222 apply (rule ballI) |
218 apply (rule ballI) |
223 apply (erule llist.cases) |
219 apply (erule llist.cases, simp_all) |
224 apply (simp_all) |
|
225 apply (simp_all add: QInl_def QInr_def llist.con_defs) |
220 apply (simp_all add: QInl_def QInr_def llist.con_defs) |
226 (*LCons case: I simply can't get rid of the deepen_tac*) |
221 (*LCons case: I simply can't get rid of the deepen_tac*) |
227 apply (tactic "deepen_tac (claset() addIs [Ord_trans] addIs [Int_lower1 RS subset_trans]) 2 1") |
222 apply (tactic "deepen_tac (claset() addIs [Ord_trans] addIs [Int_lower1 RS subset_trans]) 2 1") |
228 done |
223 done |
229 |
224 |
230 lemma flip_in_quniv: "l \<in> llist(bool) ==> flip(l) \<in> quniv(bool)" |
225 lemma flip_in_quniv: "l \<in> llist(bool) ==> flip(l) \<in> quniv(bool)" |
231 apply (rule flip_llist_quniv_lemma [THEN Int_Vset_subset, THEN qunivI]) |
226 by (rule flip_llist_quniv_lemma [THEN Int_Vset_subset, THEN qunivI], assumption+) |
232 apply assumption+ |
|
233 done |
|
234 |
227 |
235 lemma flip_type: "l \<in> llist(bool) ==> flip(l): llist(bool)" |
228 lemma flip_type: "l \<in> llist(bool) ==> flip(l): llist(bool)" |
236 apply (rule_tac X = "{flip (l) . l \<in> llist (bool) }" in llist.coinduct) |
229 apply (rule_tac X = "{flip (l) . l \<in> llist (bool) }" in llist.coinduct) |
237 apply blast |
230 apply blast |
238 apply (fast intro!: flip_in_quniv) |
231 apply (fast intro!: flip_in_quniv) |
239 apply (erule RepFunE) |
232 apply (erule RepFunE) |
240 apply (erule_tac a="la" in llist.cases) |
233 apply (erule_tac a=la in llist.cases, auto) |
241 apply auto |
|
242 done |
234 done |
243 |
235 |
244 lemma flip_flip: "l \<in> llist(bool) ==> flip(flip(l)) = l" |
236 lemma flip_flip: "l \<in> llist(bool) ==> flip(flip(l)) = l" |
245 apply (rule_tac X1 = "{<flip (flip (l)),l> . l \<in> llist (bool) }" in |
237 apply (rule_tac X1 = "{<flip (flip (l)),l> . l \<in> llist (bool) }" in |
246 lleq.coinduct [THEN lleq_implies_equal]) |
238 lleq.coinduct [THEN lleq_implies_equal]) |
247 apply blast |
239 apply blast |
248 apply (fast intro!: flip_type) |
240 apply (fast intro!: flip_type) |
249 apply (erule RepFunE) |
241 apply (erule RepFunE) |
250 apply (erule_tac a="la" in llist.cases) |
242 apply (erule_tac a=la in llist.cases) |
251 apply (simp_all add: flip_type not_not) |
243 apply (simp_all add: flip_type not_not) |
252 done |
244 done |
253 |
245 |
254 end |
246 end |
255 |
247 |