src/ZF/subset.ML
changeset 2877 6476784dba1c
parent 2493 bdeb5024353a
child 3840 e0baea4d485a
equal deleted inserted replaced
2876:02c12d4c8b97 2877:6476784dba1c
     7 Union and Intersection as lattice operations
     7 Union and Intersection as lattice operations
     8 *)
     8 *)
     9 
     9 
    10 (*** cons ***)
    10 (*** cons ***)
    11 
    11 
    12 qed_goal "cons_subsetI" thy "!!a. [| a:C; B<=C |] ==> cons(a,B) <= C"
    12 qed_goal "cons_subsetI" ZF.thy "!!a. [| a:C; B<=C |] ==> cons(a,B) <= C"
    13  (fn _ => [ Fast_tac 1 ]);
    13  (fn _ => [ Blast_tac 1 ]);
    14 
    14 
    15 qed_goal "subset_consI" thy "B <= cons(a,B)"
    15 qed_goal "subset_consI" ZF.thy "B <= cons(a,B)"
    16  (fn _ => [ Fast_tac 1 ]);
    16  (fn _ => [ Blast_tac 1 ]);
    17 
    17 
    18 qed_goal "cons_subset_iff" thy "cons(a,B)<=C <-> a:C & B<=C"
    18 qed_goal "cons_subset_iff" ZF.thy "cons(a,B)<=C <-> a:C & B<=C"
    19  (fn _ => [ Fast_tac 1 ]);
    19  (fn _ => [ Blast_tac 1 ]);
    20 
    20 
    21 (*A safe special case of subset elimination, adding no new variables 
    21 (*A safe special case of subset elimination, adding no new variables 
    22   [| cons(a,B) <= C; [| a : C; B <= C |] ==> R |] ==> R *)
    22   [| cons(a,B) <= C; [| a : C; B <= C |] ==> R |] ==> R *)
    23 bind_thm ("cons_subsetE", cons_subset_iff RS iffD1 RS conjE);
    23 bind_thm ("cons_subsetE", cons_subset_iff RS iffD1 RS conjE);
    24 
    24 
    25 qed_goal "subset_empty_iff" thy "A<=0 <-> A=0"
    25 qed_goal "subset_empty_iff" ZF.thy "A<=0 <-> A=0"
    26  (fn _=> [ (Fast_tac 1) ]);
    26  (fn _=> [ (Blast_tac 1) ]);
    27 
    27 
    28 qed_goal "subset_cons_iff" thy
    28 qed_goal "subset_cons_iff" ZF.thy
    29     "C<=cons(a,B) <-> C<=B | (a:C & C-{a} <= B)"
    29     "C<=cons(a,B) <-> C<=B | (a:C & C-{a} <= B)"
    30  (fn _=> [ (Fast_tac 1) ]);
    30  (fn _=> [ (Blast_tac 1) ]);
    31 
    31 
    32 (*** succ ***)
    32 (*** succ ***)
    33 
    33 
    34 qed_goal "subset_succI" thy "i <= succ(i)"
    34 qed_goal "subset_succI" ZF.thy "i <= succ(i)"
    35  (fn _=> [ (Fast_tac 1) ]);
    35  (fn _=> [ (Blast_tac 1) ]);
    36 
    36 
    37 (*But if j is an ordinal or is transitive, then i:j implies i<=j! 
    37 (*But if j is an ordinal or is transitive, then i:j implies i<=j! 
    38   See ordinal/Ord_succ_subsetI*)
    38   See ordinal/Ord_succ_subsetI*)
    39 qed_goalw "succ_subsetI" thy [succ_def]
    39 qed_goalw "succ_subsetI" ZF.thy [succ_def]
    40     "!!i j. [| i:j;  i<=j |] ==> succ(i)<=j"
    40     "!!i j. [| i:j;  i<=j |] ==> succ(i)<=j"
    41  (fn _=> [ (Fast_tac 1) ]);
    41  (fn _=> [ (Blast_tac 1) ]);
    42 
    42 
    43 qed_goalw "succ_subsetE" thy [succ_def] 
    43 qed_goalw "succ_subsetE" ZF.thy [succ_def] 
    44     "[| succ(i) <= j;  [| i:j;  i<=j |] ==> P \
    44     "[| succ(i) <= j;  [| i:j;  i<=j |] ==> P \
    45 \    |] ==> P"
    45 \    |] ==> P"
    46  (fn major::prems=>
    46  (fn major::prems=>
    47   [ (rtac (major RS cons_subsetE) 1),
    47   [ (rtac (major RS cons_subsetE) 1),
    48     (REPEAT (ares_tac prems 1)) ]);
    48     (REPEAT (ares_tac prems 1)) ]);
    49 
    49 
    50 (*** singletons ***)
    50 (*** singletons ***)
    51 
    51 
    52 qed_goal "singleton_subsetI" thy "!!a c. a:C ==> {a} <= C"
    52 qed_goal "singleton_subsetI" ZF.thy "!!a c. a:C ==> {a} <= C"
    53  (fn _=> [ (Fast_tac 1) ]);
    53  (fn _=> [ (Blast_tac 1) ]);
    54 
    54 
    55 qed_goal "singleton_subsetD" thy "!!a C. {a} <= C  ==>  a:C"
    55 qed_goal "singleton_subsetD" ZF.thy "!!a C. {a} <= C  ==>  a:C"
    56  (fn _=> [ (Fast_tac 1) ]);
    56  (fn _=> [ (Blast_tac 1) ]);
    57 
    57 
    58 (*** Big Union -- least upper bound of a set  ***)
    58 (*** Big Union -- least upper bound of a set  ***)
    59 
    59 
    60 qed_goal "Union_subset_iff" thy "Union(A) <= C <-> (ALL x:A. x <= C)"
    60 qed_goal "Union_subset_iff" ZF.thy "Union(A) <= C <-> (ALL x:A. x <= C)"
    61  (fn _ => [ Fast_tac 1 ]);
    61  (fn _ => [ Blast_tac 1 ]);
    62 
    62 
    63 qed_goal "Union_upper" thy
    63 qed_goal "Union_upper" ZF.thy
    64     "!!B A. B:A ==> B <= Union(A)"
    64     "!!B A. B:A ==> B <= Union(A)"
    65  (fn _ => [ Fast_tac 1 ]);
    65  (fn _ => [ Blast_tac 1 ]);
    66 
    66 
    67 qed_goal "Union_least" thy
    67 qed_goal "Union_least" ZF.thy
    68     "[| !!x. x:A ==> x<=C |] ==> Union(A) <= C"
    68     "[| !!x. x:A ==> x<=C |] ==> Union(A) <= C"
    69  (fn [prem]=>
    69  (fn [prem]=>
    70   [ (rtac (ballI RS (Union_subset_iff RS iffD2)) 1),
    70   [ (rtac (ballI RS (Union_subset_iff RS iffD2)) 1),
    71     (etac prem 1) ]);
    71     (etac prem 1) ]);
    72 
    72 
    73 (*** Union of a family of sets  ***)
    73 (*** Union of a family of sets  ***)
    74 
    74 
    75 goal thy "A <= (UN i:I. B(i)) <-> A = (UN i:I. A Int B(i))";
    75 goal ZF.thy "A <= (UN i:I. B(i)) <-> A = (UN i:I. A Int B(i))";
    76 by (fast_tac (!claset addSEs [equalityE]) 1);
    76 by (blast_tac (!claset addSEs [equalityE]) 1);
    77 qed "subset_UN_iff_eq";
    77 qed "subset_UN_iff_eq";
    78 
    78 
    79 qed_goal "UN_subset_iff" thy
    79 qed_goal "UN_subset_iff" ZF.thy
    80      "(UN x:A.B(x)) <= C <-> (ALL x:A. B(x) <= C)"
    80      "(UN x:A.B(x)) <= C <-> (ALL x:A. B(x) <= C)"
    81  (fn _ => [ Fast_tac 1 ]);
    81  (fn _ => [ Blast_tac 1 ]);
    82 
    82 
    83 qed_goal "UN_upper" thy
    83 qed_goal "UN_upper" ZF.thy
    84     "!!x A. x:A ==> B(x) <= (UN x:A.B(x))"
    84     "!!x A. x:A ==> B(x) <= (UN x:A.B(x))"
    85  (fn _ => [ etac (RepFunI RS Union_upper) 1 ]);
    85  (fn _ => [ etac (RepFunI RS Union_upper) 1 ]);
    86 
    86 
    87 qed_goal "UN_least" thy
    87 qed_goal "UN_least" ZF.thy
    88     "[| !!x. x:A ==> B(x)<=C |] ==> (UN x:A.B(x)) <= C"
    88     "[| !!x. x:A ==> B(x)<=C |] ==> (UN x:A.B(x)) <= C"
    89  (fn [prem]=>
    89  (fn [prem]=>
    90   [ (rtac (ballI RS (UN_subset_iff RS iffD2)) 1),
    90   [ (rtac (ballI RS (UN_subset_iff RS iffD2)) 1),
    91     (etac prem 1) ]);
    91     (etac prem 1) ]);
    92 
    92 
    93 
    93 
    94 (*** Big Intersection -- greatest lower bound of a nonempty set ***)
    94 (*** Big Intersection -- greatest lower bound of a nonempty set ***)
    95 
    95 
    96 qed_goal "Inter_subset_iff" thy
    96 qed_goal "Inter_subset_iff" ZF.thy
    97      "!!a A. a: A  ==>  C <= Inter(A) <-> (ALL x:A. C <= x)"
    97      "!!a A. a: A  ==>  C <= Inter(A) <-> (ALL x:A. C <= x)"
    98  (fn _ => [ Fast_tac 1 ]);
    98  (fn _ => [ Blast_tac 1 ]);
    99 
    99 
   100 qed_goal "Inter_lower" thy "!!B A. B:A ==> Inter(A) <= B"
   100 qed_goal "Inter_lower" ZF.thy "!!B A. B:A ==> Inter(A) <= B"
   101  (fn _ => [ Fast_tac 1 ]);
   101  (fn _ => [ Blast_tac 1 ]);
   102 
   102 
   103 qed_goal "Inter_greatest" thy
   103 qed_goal "Inter_greatest" ZF.thy
   104     "[| a:A;  !!x. x:A ==> C<=x |] ==> C <= Inter(A)"
   104     "[| a:A;  !!x. x:A ==> C<=x |] ==> C <= Inter(A)"
   105  (fn [prem1,prem2]=>
   105  (fn [prem1,prem2]=>
   106   [ (rtac ([prem1, ballI] MRS (Inter_subset_iff RS iffD2)) 1),
   106   [ (rtac ([prem1, ballI] MRS (Inter_subset_iff RS iffD2)) 1),
   107     (etac prem2 1) ]);
   107     (etac prem2 1) ]);
   108 
   108 
   109 (*** Intersection of a family of sets  ***)
   109 (*** Intersection of a family of sets  ***)
   110 
   110 
   111 qed_goal "INT_lower" thy
   111 qed_goal "INT_lower" ZF.thy
   112     "!!x. x:A ==> (INT x:A.B(x)) <= B(x)"
   112     "!!x. x:A ==> (INT x:A.B(x)) <= B(x)"
   113  (fn _ => [ Fast_tac 1 ]);
   113  (fn _ => [ Blast_tac 1 ]);
   114 
   114 
   115 qed_goal "INT_greatest" thy
   115 qed_goal "INT_greatest" ZF.thy
   116     "[| a:A;  !!x. x:A ==> C<=B(x) |] ==> C <= (INT x:A.B(x))"
   116     "[| a:A;  !!x. x:A ==> C<=B(x) |] ==> C <= (INT x:A.B(x))"
   117  (fn [nonempty,prem] =>
   117  (fn [nonempty,prem] =>
   118   [ rtac (nonempty RS RepFunI RS Inter_greatest) 1,
   118   [ rtac (nonempty RS RepFunI RS Inter_greatest) 1,
   119     REPEAT (eresolve_tac [RepFunE, prem, ssubst] 1) ]);
   119     REPEAT (eresolve_tac [RepFunE, prem, ssubst] 1) ]);
   120 
   120 
   121 
   121 
   122 (*** Finite Union -- the least upper bound of 2 sets ***)
   122 (*** Finite Union -- the least upper bound of 2 sets ***)
   123 
   123 
   124 qed_goal "Un_subset_iff" thy "A Un B <= C <-> A <= C & B <= C"
   124 qed_goal "Un_subset_iff" ZF.thy "A Un B <= C <-> A <= C & B <= C"
   125  (fn _ => [ Fast_tac 1 ]);
   125  (fn _ => [ Blast_tac 1 ]);
   126 
   126 
   127 qed_goal "Un_upper1" thy "A <= A Un B"
   127 qed_goal "Un_upper1" ZF.thy "A <= A Un B"
   128  (fn _ => [ Fast_tac 1 ]);
   128  (fn _ => [ Blast_tac 1 ]);
   129 
   129 
   130 qed_goal "Un_upper2" thy "B <= A Un B"
   130 qed_goal "Un_upper2" ZF.thy "B <= A Un B"
   131  (fn _ => [ Fast_tac 1 ]);
   131  (fn _ => [ Blast_tac 1 ]);
   132 
   132 
   133 qed_goal "Un_least" thy "!!A B C. [| A<=C;  B<=C |] ==> A Un B <= C"
   133 qed_goal "Un_least" ZF.thy "!!A B C. [| A<=C;  B<=C |] ==> A Un B <= C"
   134  (fn _ => [ Fast_tac 1 ]);
   134  (fn _ => [ Blast_tac 1 ]);
   135 
   135 
   136 
   136 
   137 (*** Finite Intersection -- the greatest lower bound of 2 sets *)
   137 (*** Finite Intersection -- the greatest lower bound of 2 sets *)
   138 
   138 
   139 qed_goal "Int_subset_iff" thy "C <= A Int B <-> C <= A & C <= B"
   139 qed_goal "Int_subset_iff" ZF.thy "C <= A Int B <-> C <= A & C <= B"
   140  (fn _ => [ Fast_tac 1 ]);
   140  (fn _ => [ Blast_tac 1 ]);
   141 
   141 
   142 qed_goal "Int_lower1" thy "A Int B <= A"
   142 qed_goal "Int_lower1" ZF.thy "A Int B <= A"
   143  (fn _ => [ Fast_tac 1 ]);
   143  (fn _ => [ Blast_tac 1 ]);
   144 
   144 
   145 qed_goal "Int_lower2" thy "A Int B <= B"
   145 qed_goal "Int_lower2" ZF.thy "A Int B <= B"
   146  (fn _ => [ Fast_tac 1 ]);
   146  (fn _ => [ Blast_tac 1 ]);
   147 
   147 
   148 qed_goal "Int_greatest" thy "!!A B C. [| C<=A;  C<=B |] ==> C <= A Int B"
   148 qed_goal "Int_greatest" ZF.thy "!!A B C. [| C<=A;  C<=B |] ==> C <= A Int B"
   149  (fn _ => [ Fast_tac 1 ]);
   149  (fn _ => [ Blast_tac 1 ]);
   150 
   150 
   151 
   151 
   152 (*** Set difference *)
   152 (*** Set difference *)
   153 
   153 
   154 qed_goal "Diff_subset" thy "A-B <= A"
   154 qed_goal "Diff_subset" ZF.thy "A-B <= A"
   155  (fn _ => [ Fast_tac 1 ]);
   155  (fn _ => [ Blast_tac 1 ]);
   156 
   156 
   157 qed_goal "Diff_contains" thy
   157 qed_goal "Diff_contains" ZF.thy
   158     "!!C. [| C<=A;  C Int B = 0 |] ==> C <= A-B"
   158     "!!C. [| C<=A;  C Int B = 0 |] ==> C <= A-B"
   159  (fn _ => [ (fast_tac (!claset addSEs [equalityE]) 1) ]);
   159  (fn _ => [ (blast_tac (!claset addSEs [equalityE]) 1) ]);
   160 
   160 
   161 
   161 
   162 (** Collect **)
   162 (** Collect **)
   163 
   163 
   164 qed_goal "Collect_subset" thy "Collect(A,P) <= A"
   164 qed_goal "Collect_subset" ZF.thy "Collect(A,P) <= A"
   165  (fn _ => [ Fast_tac 1 ]);
   165  (fn _ => [ Blast_tac 1 ]);
   166 
   166 
   167 
   167 
   168 (** RepFun **)
   168 (** RepFun **)
   169 
   169 
   170 val prems = goal thy "[| !!x. x:A ==> f(x): B |] ==> {f(x). x:A} <= B";
   170 val prems = goal ZF.thy "[| !!x. x:A ==> f(x): B |] ==> {f(x). x:A} <= B";
   171 by (fast_tac (!claset addIs prems) 1);
   171 by (blast_tac (!claset addIs prems) 1);
   172 qed "RepFun_subset";
   172 qed "RepFun_subset";
   173 
   173 
   174 val subset_SIs =
   174 val subset_SIs =
   175     [subset_refl, cons_subsetI, subset_consI, 
   175     [subset_refl, cons_subsetI, subset_consI, 
   176      Union_least, UN_least, Un_least, 
   176      Union_least, UN_least, Un_least,