src/ZF/ex/llist.ML
changeset 16 0b033d50ca1c
parent 7 268f93ab3bc4
child 34 747f1aad03cf
equal deleted inserted replaced
15:6c6d2f6e3185 16:0b033d50ca1c
    53 
    53 
    54 (*Keep unfolding the lazy list until the induction hypothesis applies*)
    54 (*Keep unfolding the lazy list until the induction hypothesis applies*)
    55 goal LList.thy
    55 goal LList.thy
    56    "!!i. i : nat ==> 	\
    56    "!!i. i : nat ==> 	\
    57 \        ALL l: llist(quniv(A)). l Int Vfrom(quniv(A), i) : quniv(A)";
    57 \        ALL l: llist(quniv(A)). l Int Vfrom(quniv(A), i) : quniv(A)";
    58 be complete_induct 1;
    58 by (etac complete_induct 1);
    59 br ballI 1;
    59 by (rtac ballI 1);
    60 be LList.elim 1;
    60 by (etac LList.elim 1);
    61 bws ([QInl_def,QInr_def]@LList.con_defs);
    61 by (rewrite_goals_tac ([QInl_def,QInr_def]@LList.con_defs));
    62 by (fast_tac quniv_cs 1);
    62 by (fast_tac quniv_cs 1);
    63 by (etac natE 1 THEN REPEAT_FIRST hyp_subst_tac);
    63 by (etac natE 1 THEN REPEAT_FIRST hyp_subst_tac);
    64 by (fast_tac quniv_cs 1);
    64 by (fast_tac quniv_cs 1);
    65 by (fast_tac quniv_cs 1);
    65 by (fast_tac quniv_cs 1);
    66 val llist_quniv_lemma = result();
    66 val llist_quniv_lemma = result();
    67 
    67 
    68 goal LList.thy "llist(quniv(A)) <= quniv(A)";
    68 goal LList.thy "llist(quniv(A)) <= quniv(A)";
    69 br subsetI 1;
    69 by (rtac subsetI 1);
    70 br quniv_Int_Vfrom 1;
    70 by (rtac quniv_Int_Vfrom 1);
    71 be (LList.dom_subset RS subsetD) 1;
    71 by (etac (LList.dom_subset RS subsetD) 1);
    72 by (REPEAT (ares_tac [llist_quniv_lemma RS bspec] 1));
    72 by (REPEAT (ares_tac [llist_quniv_lemma RS bspec] 1));
    73 val llist_quniv = result();
    73 val llist_quniv = result();
    74 
    74 
    75 val llist_subset_quniv = standard
    75 val llist_subset_quniv = standard
    76     (llist_mono RS (llist_quniv RSN (2,subset_trans)));
    76     (llist_mono RS (llist_quniv RSN (2,subset_trans)));
   100 		QPair_Int_Vset_subset_trans];
   100 		QPair_Int_Vset_subset_trans];
   101 
   101 
   102 (*Keep unfolding the lazy list until the induction hypothesis applies*)
   102 (*Keep unfolding the lazy list until the induction hypothesis applies*)
   103 goal LList_Eq.thy
   103 goal LList_Eq.thy
   104    "!!i. Ord(i) ==> ALL l l'. <l;l'> : lleq(A) --> l Int Vset(i) <= l'";
   104    "!!i. Ord(i) ==> ALL l l'. <l;l'> : lleq(A) --> l Int Vset(i) <= l'";
   105 be trans_induct 1;
   105 by (etac trans_induct 1);
   106 by (safe_tac subset_cs);
   106 by (safe_tac subset_cs);
   107 be LList_Eq.elim 1;
   107 by (etac LList_Eq.elim 1);
   108 by (safe_tac (subset_cs addSEs [QPair_inject]));
   108 by (safe_tac (subset_cs addSEs [QPair_inject]));
   109 bws LList.con_defs;
   109 by (rewrite_goals_tac LList.con_defs);
   110 by (etac Ord_cases 1 THEN REPEAT_FIRST hyp_subst_tac);
   110 by (etac Ord_cases 1 THEN REPEAT_FIRST hyp_subst_tac);
   111 (*0 case*)
   111 (*0 case*)
   112 by (fast_tac lleq_cs 1);
   112 by (fast_tac lleq_cs 1);
   113 (*succ(j) case*)
   113 (*succ(j) case*)
   114 bw QInr_def;
   114 by (rewtac QInr_def);
   115 by (fast_tac lleq_cs 1);
   115 by (fast_tac lleq_cs 1);
   116 (*Limit(i) case*)
   116 (*Limit(i) case*)
   117 be (Limit_Vfrom_eq RS ssubst) 1;
   117 by (etac (Limit_Vfrom_eq RS ssubst) 1);
   118 br (Int_UN_distrib RS ssubst) 1;
   118 by (rtac (Int_UN_distrib RS ssubst) 1);
   119 by (fast_tac lleq_cs 1);
   119 by (fast_tac lleq_cs 1);
   120 val lleq_Int_Vset_subset_lemma = result();
   120 val lleq_Int_Vset_subset_lemma = result();
   121 
   121 
   122 val lleq_Int_Vset_subset = standard
   122 val lleq_Int_Vset_subset = standard
   123 	(lleq_Int_Vset_subset_lemma RS spec RS spec RS mp);
   123 	(lleq_Int_Vset_subset_lemma RS spec RS spec RS mp);
   124 
   124 
   125 
   125 
   126 (*lleq(A) is a symmetric relation because qconverse(lleq(A)) is a fixedpoint*)
   126 (*lleq(A) is a symmetric relation because qconverse(lleq(A)) is a fixedpoint*)
   127 val [prem] = goal LList_Eq.thy "<l;l'> : lleq(A) ==> <l';l> : lleq(A)";
   127 val [prem] = goal LList_Eq.thy "<l;l'> : lleq(A) ==> <l';l> : lleq(A)";
   128 br (prem RS qconverseI RS LList_Eq.co_induct) 1;
   128 by (rtac (prem RS qconverseI RS LList_Eq.co_induct) 1);
   129 br (LList_Eq.dom_subset RS qconverse_type) 1;
   129 by (rtac (LList_Eq.dom_subset RS qconverse_type) 1);
   130 by (safe_tac qconverse_cs);
   130 by (safe_tac qconverse_cs);
   131 be LList_Eq.elim 1;
   131 by (etac LList_Eq.elim 1);
   132 by (ALLGOALS (fast_tac qconverse_cs));
   132 by (ALLGOALS (fast_tac qconverse_cs));
   133 val lleq_symmetric = result();
   133 val lleq_symmetric = result();
   134 
   134 
   135 goal LList_Eq.thy "!!l l'. <l;l'> : lleq(A) ==> l=l'";
   135 goal LList_Eq.thy "!!l l'. <l;l'> : lleq(A) ==> l=l'";
   136 br equalityI 1;
   136 by (rtac equalityI 1);
   137 by (REPEAT (ares_tac [lleq_Int_Vset_subset RS Int_Vset_subset] 1
   137 by (REPEAT (ares_tac [lleq_Int_Vset_subset RS Int_Vset_subset] 1
   138      ORELSE etac lleq_symmetric 1));
   138      ORELSE etac lleq_symmetric 1));
   139 val lleq_implies_equal = result();
   139 val lleq_implies_equal = result();
   140 
   140 
   141 val [eqprem,lprem] = goal LList_Eq.thy
   141 val [eqprem,lprem] = goal LList_Eq.thy
   142     "[| l=l';  l: llist(A) |] ==> <l;l'> : lleq(A)";
   142     "[| l=l';  l: llist(A) |] ==> <l;l'> : lleq(A)";
   143 by (res_inst_tac [("X", "{<l;l>. l: llist(A)}")] LList_Eq.co_induct 1);
   143 by (res_inst_tac [("X", "{<l;l>. l: llist(A)}")] LList_Eq.co_induct 1);
   144 br (lprem RS RepFunI RS (eqprem RS subst)) 1;
   144 by (rtac (lprem RS RepFunI RS (eqprem RS subst)) 1);
   145 by (safe_tac qpair_cs);
   145 by (safe_tac qpair_cs);
   146 be LList.elim 1;
   146 by (etac LList.elim 1);
   147 by (ALLGOALS (fast_tac qpair_cs));
   147 by (ALLGOALS (fast_tac qpair_cs));
   148 val equal_llist_implies_leq = result();
   148 val equal_llist_implies_leq = result();
   149 
   149 
   150 
   150