equal
deleted
inserted
replaced
26 |
26 |
27 (* ------------------------------------------------------------------------ *) |
27 (* ------------------------------------------------------------------------ *) |
28 (* chains are monotone functions *) |
28 (* chains are monotone functions *) |
29 (* ------------------------------------------------------------------------ *) |
29 (* ------------------------------------------------------------------------ *) |
30 |
30 |
31 qed_goalw "chain_mono" thy [is_chain] "is_chain F ==> x<y --> F x<<F y" |
31 qed_goalw "chain_mono" thy [chain] "chain F ==> x<y --> F x<<F y" |
32 ( fn prems => |
32 ( fn prems => |
33 [ |
33 [ |
34 (cut_facts_tac prems 1), |
34 (cut_facts_tac prems 1), |
35 (nat_ind_tac "y" 1), |
35 (nat_ind_tac "y" 1), |
36 (rtac impI 1), |
36 (rtac impI 1), |
45 (hyp_subst_tac 1), |
45 (hyp_subst_tac 1), |
46 (etac allE 1), |
46 (etac allE 1), |
47 (atac 1) |
47 (atac 1) |
48 ]); |
48 ]); |
49 |
49 |
50 qed_goal "chain_mono3" thy "[| is_chain F; x <= y |] ==> F x << F y" |
50 qed_goal "chain_mono3" thy "[| chain F; x <= y |] ==> F x << F y" |
51 (fn prems => |
51 (fn prems => |
52 [ |
52 [ |
53 (cut_facts_tac prems 1), |
53 (cut_facts_tac prems 1), |
54 (rtac (le_imp_less_or_eq RS disjE) 1), |
54 (rtac (le_imp_less_or_eq RS disjE) 1), |
55 (atac 1), |
55 (atac 1), |
62 |
62 |
63 (* ------------------------------------------------------------------------ *) |
63 (* ------------------------------------------------------------------------ *) |
64 (* The range of a chain is a totaly ordered << *) |
64 (* The range of a chain is a totaly ordered << *) |
65 (* ------------------------------------------------------------------------ *) |
65 (* ------------------------------------------------------------------------ *) |
66 |
66 |
67 qed_goalw "chain_is_tord" thy [is_tord] |
67 qed_goalw "chain_tord" thy [tord] |
68 "!!F. is_chain(F) ==> is_tord(range(F))" |
68 "!!F. chain(F) ==> tord(range(F))" |
69 (fn _ => |
69 (fn _ => |
70 [ |
70 [ |
71 Safe_tac, |
71 Safe_tac, |
72 (rtac nat_less_cases 1), |
72 (rtac nat_less_cases 1), |
73 (ALLGOALS (fast_tac (claset() addIs [refl_less, chain_mono RS mp])))]); |
73 (ALLGOALS (fast_tac (claset() addIs [refl_less, chain_mono RS mp])))]); |
136 [ |
136 [ |
137 (cut_facts_tac prems 1), |
137 (cut_facts_tac prems 1), |
138 (atac 1) |
138 (atac 1) |
139 ]); |
139 ]); |
140 |
140 |
141 qed_goalw "is_chainE" thy [is_chain] "is_chain F ==> !i. F(i) << F(Suc(i))" |
141 qed_goalw "chainE" thy [chain] "chain F ==> !i. F(i) << F(Suc(i))" |
142 (fn prems => |
142 (fn prems => |
143 [ |
143 [ |
144 (cut_facts_tac prems 1), |
144 (cut_facts_tac prems 1), |
145 (atac 1)]); |
145 (atac 1)]); |
146 |
146 |
147 qed_goalw "is_chainI" thy [is_chain] "!i. F i << F(Suc i) ==> is_chain F" |
147 qed_goalw "chainI" thy [chain] "!i. F i << F(Suc i) ==> chain F" |
148 (fn prems => |
148 (fn prems => |
149 [ |
149 [ |
150 (cut_facts_tac prems 1), |
150 (cut_facts_tac prems 1), |
151 (atac 1)]); |
151 (atac 1)]); |
152 |
152 |
183 (* ------------------------------------------------------------------------ *) |
183 (* ------------------------------------------------------------------------ *) |
184 (* results about finite chains *) |
184 (* results about finite chains *) |
185 (* ------------------------------------------------------------------------ *) |
185 (* ------------------------------------------------------------------------ *) |
186 |
186 |
187 qed_goalw "lub_finch1" thy [max_in_chain_def] |
187 qed_goalw "lub_finch1" thy [max_in_chain_def] |
188 "[| is_chain C; max_in_chain i C|] ==> range C <<| C i" |
188 "[| chain C; max_in_chain i C|] ==> range C <<| C i" |
189 (fn prems => |
189 (fn prems => |
190 [ |
190 [ |
191 (cut_facts_tac prems 1), |
191 (cut_facts_tac prems 1), |
192 (rtac is_lubI 1), |
192 (rtac is_lubI 1), |
193 (rtac conjI 1), |
193 (rtac conjI 1), |
216 (rtac (select_eq_Ex RS iffD2) 1), |
216 (rtac (select_eq_Ex RS iffD2) 1), |
217 (etac conjunct2 1) |
217 (etac conjunct2 1) |
218 ]); |
218 ]); |
219 |
219 |
220 |
220 |
221 qed_goal "bin_chain" thy "x<<y ==> is_chain (%i. if i=0 then x else y)" |
221 qed_goal "bin_chain" thy "x<<y ==> chain (%i. if i=0 then x else y)" |
222 (fn prems => |
222 (fn prems => |
223 [ |
223 [ |
224 (cut_facts_tac prems 1), |
224 (cut_facts_tac prems 1), |
225 (rtac is_chainI 1), |
225 (rtac chainI 1), |
226 (rtac allI 1), |
226 (rtac allI 1), |
227 (nat_ind_tac "i" 1), |
227 (nat_ind_tac "i" 1), |
228 (Asm_simp_tac 1), |
228 (Asm_simp_tac 1), |
229 (Asm_simp_tac 1) |
229 (Asm_simp_tac 1) |
230 ]); |
230 ]); |