src/ZF/mono.ML
changeset 4091 771b1f6422a8
parent 3890 2a2a86b57fed
child 5067 62b6288e6005
equal deleted inserted replaced
4090:9f1eaab75e8c 4091:771b1f6422a8
    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";