3 Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
3 Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
4 Copyright 1994 University of Cambridge |
4 Copyright 1994 University of Cambridge |
5 |
5 |
6 For Order.thy. Orders in Zermelo-Fraenkel Set Theory |
6 For Order.thy. Orders in Zermelo-Fraenkel Set Theory |
7 *) |
7 *) |
8 |
|
9 (*TO PURE/TACTIC.ML*) |
|
10 fun subgoals_tac sprops = EVERY' (map subgoal_tac sprops); |
|
11 |
8 |
12 |
9 |
13 open Order; |
10 open Order; |
14 |
11 |
15 val bij_apply_cs = ZF_cs addSEs [bij_converse_bij] |
12 val bij_apply_cs = ZF_cs addSEs [bij_converse_bij] |
42 val ord_iso_apply = result(); |
39 val ord_iso_apply = result(); |
43 |
40 |
44 goalw Order.thy [ord_iso_def] |
41 goalw Order.thy [ord_iso_def] |
45 "!!f. [| f: ord_iso(A,r,B,s); <x,y>: s; x:B; y:B |] ==> \ |
42 "!!f. [| f: ord_iso(A,r,B,s); <x,y>: s; x:B; y:B |] ==> \ |
46 \ <converse(f) ` x, converse(f) ` y> : r"; |
43 \ <converse(f) ` x, converse(f) ` y> : r"; |
47 be CollectE 1; |
44 by (etac CollectE 1); |
48 be (bspec RS bspec RS iffD2) 1; |
45 by (etac (bspec RS bspec RS iffD2) 1); |
49 by (REPEAT (eresolve_tac [asm_rl, |
46 by (REPEAT (eresolve_tac [asm_rl, |
50 bij_converse_bij RS bij_is_fun RS apply_type] 1)); |
47 bij_converse_bij RS bij_is_fun RS apply_type] 1)); |
51 by (asm_simp_tac (ZF_ss addsimps [right_inverse_bij]) 1); |
48 by (asm_simp_tac (ZF_ss addsimps [right_inverse_bij]) 1); |
52 val ord_iso_converse = result(); |
49 val ord_iso_converse = result(); |
53 |
50 |
140 |
137 |
141 (*Kunen's Lemma 6.2: Order-isomorphisms between well-orderings are unique*) |
138 (*Kunen's Lemma 6.2: Order-isomorphisms between well-orderings are unique*) |
142 goal Order.thy |
139 goal Order.thy |
143 "!!r. [| well_ord(A,r); well_ord(B,s); \ |
140 "!!r. [| well_ord(A,r); well_ord(B,s); \ |
144 \ f: ord_iso(A,r, B,s); g: ord_iso(A,r, B,s) |] ==> f = g"; |
141 \ f: ord_iso(A,r, B,s); g: ord_iso(A,r, B,s) |] ==> f = g"; |
145 br fun_extension 1; |
142 by (rtac fun_extension 1); |
146 be (ord_iso_is_bij RS bij_is_fun) 1; |
143 by (etac (ord_iso_is_bij RS bij_is_fun) 1); |
147 be (ord_iso_is_bij RS bij_is_fun) 1; |
144 by (etac (ord_iso_is_bij RS bij_is_fun) 1); |
148 br well_ord_iso_unique_lemma 1; |
145 by (rtac well_ord_iso_unique_lemma 1); |
149 by (REPEAT_SOME assume_tac); |
146 by (REPEAT_SOME assume_tac); |
150 val well_ord_iso_unique = result(); |
147 val well_ord_iso_unique = result(); |
151 |
148 |
152 |
149 |
153 goalw Order.thy [irrefl_def, part_ord_def, tot_ord_def, |
150 goalw Order.thy [irrefl_def, part_ord_def, tot_ord_def, |
155 "!!r. [| wf[A](r); linear(A,r) |] ==> well_ord(A,r)"; |
152 "!!r. [| wf[A](r); linear(A,r) |] ==> well_ord(A,r)"; |
156 by (asm_simp_tac (ZF_ss addsimps [wf_on_not_refl]) 1); |
153 by (asm_simp_tac (ZF_ss addsimps [wf_on_not_refl]) 1); |
157 by (safe_tac ZF_cs); |
154 by (safe_tac ZF_cs); |
158 by (linear_case_tac 1); |
155 by (linear_case_tac 1); |
159 (*case x=xb*) |
156 (*case x=xb*) |
160 by (fast_tac (ZF_cs addSEs [wf_on_anti_sym]) 1); |
157 by (fast_tac (ZF_cs addSEs [wf_on_asym]) 1); |
161 (*case x<xb*) |
158 (*case x<xb*) |
162 by (fast_tac (ZF_cs addSEs [wf_on_chain3]) 1); |
159 by (fast_tac (ZF_cs addSEs [wf_on_chain3]) 1); |
163 val well_ordI = result(); |
160 val well_ordI = result(); |
164 |
161 |
165 goalw Order.thy [well_ord_def] |
162 goalw Order.thy [well_ord_def] |
170 |
167 |
171 (*** Derived rules for pred(A,x,r) ***) |
168 (*** Derived rules for pred(A,x,r) ***) |
172 |
169 |
173 val [major,minor] = goalw Order.thy [pred_def] |
170 val [major,minor] = goalw Order.thy [pred_def] |
174 "[| y: pred(A,x,r); [| y:A; <y,x>:r |] ==> P |] ==> P"; |
171 "[| y: pred(A,x,r); [| y:A; <y,x>:r |] ==> P |] ==> P"; |
175 br (major RS CollectE) 1; |
172 by (rtac (major RS CollectE) 1); |
176 by (REPEAT (ares_tac [minor] 1)); |
173 by (REPEAT (ares_tac [minor] 1)); |
177 val predE = result(); |
174 val predE = result(); |
178 |
175 |
179 goalw Order.thy [pred_def] "pred(A,x,r) <= r -`` {x}"; |
176 goalw Order.thy [pred_def] "pred(A,x,r) <= r -`` {x}"; |
180 by (fast_tac ZF_cs 1); |
177 by (fast_tac ZF_cs 1); |