src/ZF/ex/LList.thy
changeset 13339 0f89104dd377
parent 12867 5c900a821a7c
child 16417 9bc16273c2d4
equal deleted inserted replaced
13338:20ca66539bef 13339:0f89104dd377
   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