src/HOL/mono.ML
author oheimb
Wed Jan 31 10:15:55 2001 +0100 (2001-01-31)
changeset 11008 f7333f055ef6
parent 10832 e33b47e4246d
child 11138 bdfb9ec76a0a
permissions -rw-r--r--
improved theory reference in comment
     1 (*  Title:      HOL/mono.ML
     2     ID:         $Id$
     3     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     4     Copyright   1991  University of Cambridge
     5 
     6 Monotonicity of various operations
     7 *)
     8 
     9 Goal "A<=B ==> f`A <= f`B";
    10 by (Blast_tac 1);
    11 qed "image_mono";
    12 
    13 Goal "A<=B ==> Pow(A) <= Pow(B)";
    14 by (Blast_tac 1);
    15 qed "Pow_mono";
    16 
    17 Goal "A<=B ==> Union(A) <= Union(B)";
    18 by (Blast_tac 1);
    19 qed "Union_mono";
    20 
    21 Goal "B<=A ==> Inter(A) <= Inter(B)";
    22 by (Blast_tac 1);
    23 qed "Inter_anti_mono";
    24 
    25 val prems = Goal
    26     "[| A<=B;  !!x. x:A ==> f(x)<=g(x) |] ==> \
    27 \    (UN x:A. f(x)) <= (UN x:B. g(x))";
    28 by (blast_tac (claset() addIs (prems RL [subsetD])) 1);
    29 qed "UN_mono";
    30 
    31 (*The last inclusion is POSITIVE! *)
    32 val prems = Goal
    33     "[| B<=A;  !!x. x:A ==> f(x)<=g(x) |] ==> \
    34 \    (INT x:A. f(x)) <= (INT x:A. g(x))";
    35 by (blast_tac (claset() addIs (prems RL [subsetD])) 1);
    36 qed "INT_anti_mono";
    37 
    38 Goal "C<=D ==> insert a C <= insert a D";
    39 by (Blast_tac 1);
    40 qed "insert_mono";
    41 
    42 Goal "[| A<=C;  B<=D |] ==> A Un B <= C Un D";
    43 by (Blast_tac 1);
    44 qed "Un_mono";
    45 
    46 Goal "[| A<=C;  B<=D |] ==> A Int B <= C Int D";
    47 by (Blast_tac 1);
    48 qed "Int_mono";
    49 
    50 Goal "!!A::'a set. [| A<=C;  D<=B |] ==> A-B <= C-D";
    51 by (Blast_tac 1);
    52 qed "Diff_mono";
    53 
    54 Goal "!!A::'a set. A <= B ==> -B <= -A";
    55 by (Blast_tac 1);
    56 qed "Compl_anti_mono";
    57 
    58 (** Monotonicity of implications.  For inductive definitions **)
    59 
    60 Goal "A<=B ==> x:A --> x:B";
    61 by (rtac impI 1);
    62 by (etac subsetD 1);
    63 by (assume_tac 1);
    64 qed "in_mono";
    65 
    66 Goal "[| P1-->Q1; P2-->Q2 |] ==> (P1&P2) --> (Q1&Q2)";
    67 by (Blast_tac 1);
    68 qed "conj_mono";
    69 
    70 Goal "[| P1-->Q1; P2-->Q2 |] ==> (P1|P2) --> (Q1|Q2)";
    71 by (Blast_tac 1);
    72 qed "disj_mono";
    73 
    74 Goal "[| Q1-->P1; P2-->Q2 |] ==> (P1-->P2)-->(Q1-->Q2)";
    75 by (Blast_tac 1);
    76 qed "imp_mono";
    77 
    78 Goal "P-->P";
    79 by (rtac impI 1);
    80 by (assume_tac 1);
    81 qed "imp_refl";
    82 
    83 val [PQimp] = Goal
    84     "[| !!x. P(x) --> Q(x) |] ==> (EX x. P(x)) --> (EX x. Q(x))";
    85 by (blast_tac (claset() addIs [PQimp RS mp]) 1);
    86 qed "ex_mono";
    87 
    88 val [PQimp] = Goal
    89     "[| !!x. P(x) --> Q(x) |] ==> (ALL x. P(x)) --> (ALL x. Q(x))";
    90 by (blast_tac (claset() addIs [PQimp RS mp]) 1);
    91 qed "all_mono";
    92 
    93 val [PQimp] = Goal
    94     "[| !!x. P(x) --> Q(x) |] ==> Collect(P) <= Collect(Q)";
    95 by (blast_tac (claset() addIs [PQimp RS mp]) 1);
    96 qed "Collect_mono";
    97 
    98 val [subs,PQimp] = Goal
    99     "[| A<=B;  !!x. x:A ==> P(x) --> Q(x) \
   100 \    |] ==> A Int Collect(P) <= B Int Collect(Q)";
   101 by (blast_tac (claset() addIs [subs RS subsetD, PQimp RS mp]) 1);
   102 qed "Int_Collect_mono";
   103 
   104 val basic_monos = [subset_refl, imp_refl, disj_mono, conj_mono, 
   105                    ex_mono, Collect_mono, in_mono];
   106 
   107 (* Courtesy of Stephan Merz *)
   108 Goalw [Least_def,mono_def]
   109   "[| mono (f::'a::order => 'b::order); ? x:S. ! y:S. x <= y |] \
   110 \  ==> (LEAST y. y : f`S) = f(LEAST x. x : S)";
   111 by (etac bexE 1);
   112 by (rtac someI2 1);
   113 by (Force_tac 1);
   114 by (rtac some_equality 1);
   115 by (Force_tac 1);
   116 by (force_tac (claset() addSIs [order_antisym], simpset()) 1);
   117 qed "Least_mono";
   118 
   119 Goal "[| a = b; c = d; b --> d |] ==> a --> c";
   120 by (Fast_tac 1);
   121 qed "eq_to_mono";
   122 
   123 Goal "[| a = b; c = d; ~ b --> ~ d |] ==> ~ a --> ~ c";
   124 by (Fast_tac 1);
   125 qed "eq_to_mono2";