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 |