equal
deleted
inserted
replaced
11 (** Replacement, in its various formulations **) |
11 (** Replacement, in its various formulations **) |
12 |
12 |
13 (*Not easy to express monotonicity in P, since any "bigger" predicate |
13 (*Not easy to express monotonicity in P, since any "bigger" predicate |
14 would have to be single-valued*) |
14 would have to be single-valued*) |
15 goal thy "!!A B. A<=B ==> Replace(A,P) <= Replace(B,P)"; |
15 goal thy "!!A B. A<=B ==> Replace(A,P) <= Replace(B,P)"; |
16 by (blast_tac (!claset addSEs [ReplaceE]) 1); |
16 by (blast_tac (claset() addSEs [ReplaceE]) 1); |
17 qed "Replace_mono"; |
17 qed "Replace_mono"; |
18 |
18 |
19 goal thy "!!A B. A<=B ==> {f(x). x:A} <= {f(x). x:B}"; |
19 goal thy "!!A B. A<=B ==> {f(x). x:A} <= {f(x). x:B}"; |
20 by (Blast_tac 1); |
20 by (Blast_tac 1); |
21 qed "RepFun_mono"; |
21 qed "RepFun_mono"; |
29 qed "Union_mono"; |
29 qed "Union_mono"; |
30 |
30 |
31 val prems = goal thy |
31 val prems = goal thy |
32 "[| A<=C; !!x. x:A ==> B(x)<=D(x) \ |
32 "[| A<=C; !!x. x:A ==> B(x)<=D(x) \ |
33 \ |] ==> (UN x:A. B(x)) <= (UN x:C. D(x))"; |
33 \ |] ==> (UN x:A. B(x)) <= (UN x:C. D(x))"; |
34 by (blast_tac (!claset addIs (prems RL [subsetD])) 1); |
34 by (blast_tac (claset() addIs (prems RL [subsetD])) 1); |
35 qed "UN_mono"; |
35 qed "UN_mono"; |
36 |
36 |
37 (*Intersection is ANTI-monotonic. There are TWO premises! *) |
37 (*Intersection is ANTI-monotonic. There are TWO premises! *) |
38 goal thy "!!A B. [| A<=B; a:A |] ==> Inter(B) <= Inter(A)"; |
38 goal thy "!!A B. [| A<=B; a:A |] ==> Inter(B) <= Inter(A)"; |
39 by (Blast_tac 1); |
39 by (Blast_tac 1); |
67 by (REPEAT (ares_tac [subset_refl,Un_mono,Sigma_mono] 1)); |
67 by (REPEAT (ares_tac [subset_refl,Un_mono,Sigma_mono] 1)); |
68 qed "sum_mono"; |
68 qed "sum_mono"; |
69 |
69 |
70 (*Note that B->A and C->A are typically disjoint!*) |
70 (*Note that B->A and C->A are typically disjoint!*) |
71 goal thy "!!A B C. B<=C ==> A->B <= A->C"; |
71 goal thy "!!A B C. B<=C ==> A->B <= A->C"; |
72 by (blast_tac (!claset addIs [lam_type] addEs [Pi_lamE]) 1); |
72 by (blast_tac (claset() addIs [lam_type] addEs [Pi_lamE]) 1); |
73 qed "Pi_mono"; |
73 qed "Pi_mono"; |
74 |
74 |
75 goalw thy [lam_def] "!!A B. A<=B ==> Lambda(A,c) <= Lambda(B,c)"; |
75 goalw thy [lam_def] "!!A B. A<=B ==> Lambda(A,c) <= Lambda(B,c)"; |
76 by (etac RepFun_mono 1); |
76 by (etac RepFun_mono 1); |
77 qed "lam_mono"; |
77 qed "lam_mono"; |
131 |
131 |
132 (** Images **) |
132 (** Images **) |
133 |
133 |
134 val [prem1,prem2] = goal thy |
134 val [prem1,prem2] = goal thy |
135 "[| !! x y. <x,y>:r ==> <x,y>:s; A<=B |] ==> r``A <= s``B"; |
135 "[| !! x y. <x,y>:r ==> <x,y>:s; A<=B |] ==> r``A <= s``B"; |
136 by (blast_tac (!claset addIs [prem1, prem2 RS subsetD]) 1); |
136 by (blast_tac (claset() addIs [prem1, prem2 RS subsetD]) 1); |
137 qed "image_pair_mono"; |
137 qed "image_pair_mono"; |
138 |
138 |
139 val [prem1,prem2] = goal thy |
139 val [prem1,prem2] = goal thy |
140 "[| !! x y. <x,y>:r ==> <x,y>:s; A<=B |] ==> r-``A <= s-``B"; |
140 "[| !! x y. <x,y>:r ==> <x,y>:s; A<=B |] ==> r-``A <= s-``B"; |
141 by (blast_tac (!claset addIs [prem1, prem2 RS subsetD]) 1); |
141 by (blast_tac (claset() addIs [prem1, prem2 RS subsetD]) 1); |
142 qed "vimage_pair_mono"; |
142 qed "vimage_pair_mono"; |
143 |
143 |
144 goal thy "!!r s. [| r<=s; A<=B |] ==> r``A <= s``B"; |
144 goal thy "!!r s. [| r<=s; A<=B |] ==> r``A <= s``B"; |
145 by (Blast_tac 1); |
145 by (Blast_tac 1); |
146 qed "image_mono"; |
146 qed "image_mono"; |
149 by (Blast_tac 1); |
149 by (Blast_tac 1); |
150 qed "vimage_mono"; |
150 qed "vimage_mono"; |
151 |
151 |
152 val [sub,PQimp] = goal thy |
152 val [sub,PQimp] = goal thy |
153 "[| A<=B; !!x. x:A ==> P(x) --> Q(x) |] ==> Collect(A,P) <= Collect(B,Q)"; |
153 "[| A<=B; !!x. x:A ==> P(x) --> Q(x) |] ==> Collect(A,P) <= Collect(B,Q)"; |
154 by (blast_tac (!claset addIs [sub RS subsetD, PQimp RS mp]) 1); |
154 by (blast_tac (claset() addIs [sub RS subsetD, PQimp RS mp]) 1); |
155 qed "Collect_mono"; |
155 qed "Collect_mono"; |
156 |
156 |
157 (** Monotonicity of implications -- some could go to FOL **) |
157 (** Monotonicity of implications -- some could go to FOL **) |
158 |
158 |
159 goal thy "!!A B x. A<=B ==> x:A --> x:B"; |
159 goal thy "!!A B x. A<=B ==> x:A --> x:B"; |