src/ZF/ZF.ML
changeset 9180 3bda56c0d70d
parent 7531 99c7e60d6b3f
child 9211 6236c5285bd8
equal deleted inserted replaced
9179:44eabc57ed46 9180:3bda56c0d70d
    30  (fn major::prems=>
    30  (fn major::prems=>
    31   [ (rtac (major RS allE) 1),
    31   [ (rtac (major RS allE) 1),
    32     (REPEAT (eresolve_tac (prems@[asm_rl,impCE]) 1)) ]);
    32     (REPEAT (eresolve_tac (prems@[asm_rl,impCE]) 1)) ]);
    33 
    33 
    34 (*Used in the datatype package*)
    34 (*Used in the datatype package*)
    35 qed_goal "rev_bspec" ZF.thy
    35 Goal "[| x: A;  ALL x:A. P(x) |] ==> P(x)";
    36     "!!x A P. [| x: A;  ALL x:A. P(x) |] ==> P(x)"
    36 by (REPEAT (ares_tac [bspec] 1)) ;
    37  (fn _ =>
    37 qed "rev_bspec";
    38   [ REPEAT (ares_tac [bspec] 1) ]);
       
    39 
    38 
    40 (*Instantiates x first: better for automatic theorem proving?*)
    39 (*Instantiates x first: better for automatic theorem proving?*)
    41 qed_goal "rev_ballE" ZF.thy
    40 val major::prems= Goal
    42     "[| ALL x:A. P(x);  x~:A ==> Q;  P(x) ==> Q |] ==> Q"
    41     "[| ALL x:A. P(x);  x~:A ==> Q;  P(x) ==> Q |] ==> Q";
    43  (fn major::prems=>
    42 by (rtac (major RS ballE) 1);
    44   [ (rtac (major RS ballE) 1),
    43 by (REPEAT (eresolve_tac prems 1)) ;
    45     (REPEAT (eresolve_tac prems 1)) ]);
    44 qed "rev_ballE";
    46 
    45 
    47 AddSIs [ballI];
    46 AddSIs [ballI];
    48 AddEs  [rev_ballE];
    47 AddEs  [rev_ballE];
    49 AddXDs [bspec];
    48 AddXDs [bspec];
    50 
    49 
    51 (*Takes assumptions ALL x:A.P(x) and a:A; creates assumption P(a)*)
    50 (*Takes assumptions ALL x:A.P(x) and a:A; creates assumption P(a)*)
    52 val ball_tac = dtac bspec THEN' assume_tac;
    51 val ball_tac = dtac bspec THEN' assume_tac;
    53 
    52 
    54 (*Trival rewrite rule;   (ALL x:A.P)<->P holds only if A is nonempty!*)
    53 (*Trival rewrite rule;   (ALL x:A.P)<->P holds only if A is nonempty!*)
    55 qed_goal "ball_triv" ZF.thy "(ALL x:A. P) <-> ((EX x. x:A) --> P)"
    54 Goal "(ALL x:A. P) <-> ((EX x. x:A) --> P)";
    56  (fn _=> [ simp_tac (simpset() addsimps [Ball_def]) 1 ]);
    55 by (simp_tac (simpset() addsimps [Ball_def]) 1) ;
       
    56 qed "ball_triv";
    57 Addsimps [ball_triv];
    57 Addsimps [ball_triv];
    58 
    58 
    59 (*Congruence rule for rewriting*)
    59 (*Congruence rule for rewriting*)
    60 qed_goalw "ball_cong" ZF.thy [Ball_def]
    60 qed_goalw "ball_cong" ZF.thy [Ball_def]
    61     "[| A=A';  !!x. x:A' ==> P(x) <-> P'(x) |] ==> Ball(A,P) <-> Ball(A',P')"
    61     "[| A=A';  !!x. x:A' ==> P(x) <-> P'(x) |] ==> Ball(A,P) <-> Ball(A',P')"
    71 Goalw [Bex_def] "[| x:A;  P(x) |] ==> EX x:A. P(x)";
    71 Goalw [Bex_def] "[| x:A;  P(x) |] ==> EX x:A. P(x)";
    72 by (Blast_tac 1);
    72 by (Blast_tac 1);
    73 qed "rev_bexI";
    73 qed "rev_bexI";
    74 
    74 
    75 (*Not of the general form for such rules; ~EX has become ALL~ *)
    75 (*Not of the general form for such rules; ~EX has become ALL~ *)
    76 qed_goal "bexCI" ZF.thy 
    76 val prems= Goal "[| ALL x:A. ~P(x) ==> P(a);  a: A |] ==> EX x:A. P(x)";
    77    "[| ALL x:A. ~P(x) ==> P(a);  a: A |] ==> EX x:A. P(x)"
    77 by (rtac classical 1);
    78  (fn prems=>
    78 by (REPEAT (ares_tac (prems@[bexI,ballI,notI,notE]) 1)) ;
    79   [ (rtac classical 1),
    79 qed "bexCI";
    80     (REPEAT (ares_tac (prems@[bexI,ballI,notI,notE]) 1)) ]);
       
    81 
    80 
    82 qed_goalw "bexE" ZF.thy [Bex_def]
    81 qed_goalw "bexE" ZF.thy [Bex_def]
    83     "[| EX x:A. P(x);  !!x. [| x:A; P(x) |] ==> Q \
    82     "[| EX x:A. P(x);  !!x. [| x:A; P(x) |] ==> Q \
    84 \    |] ==> Q"
    83 \    |] ==> Q"
    85  (fn major::prems=>
    84  (fn major::prems=>
    88 
    87 
    89 AddIs  [bexI];  
    88 AddIs  [bexI];  
    90 AddSEs [bexE];
    89 AddSEs [bexE];
    91 
    90 
    92 (*We do not even have (EX x:A. True) <-> True unless A is nonempty!!*)
    91 (*We do not even have (EX x:A. True) <-> True unless A is nonempty!!*)
    93 qed_goal  "bex_triv" ZF.thy "(EX x:A. P) <-> ((EX x. x:A) & P)"
    92 Goal "(EX x:A. P) <-> ((EX x. x:A) & P)";
    94  (fn _=> [ simp_tac (simpset() addsimps [Bex_def]) 1 ]);
    93 by (simp_tac (simpset() addsimps [Bex_def]) 1) ;
       
    94 qed "bex_triv";
    95 Addsimps [bex_triv];
    95 Addsimps [bex_triv];
    96 
    96 
    97 qed_goalw "bex_cong" ZF.thy [Bex_def]
    97 qed_goalw "bex_cong" ZF.thy [Bex_def]
    98     "[| A=A';  !!x. x:A' ==> P(x) <-> P'(x) \
    98     "[| A=A';  !!x. x:A' ==> P(x) <-> P'(x) \
    99 \    |] ==> Bex(A,P) <-> Bex(A',P')"
    99 \    |] ==> Bex(A,P) <-> Bex(A',P')"
   127 
   127 
   128 (*Takes assumptions A<=B; c:A and creates the assumption c:B *)
   128 (*Takes assumptions A<=B; c:A and creates the assumption c:B *)
   129 val set_mp_tac = dtac subsetD THEN' assume_tac;
   129 val set_mp_tac = dtac subsetD THEN' assume_tac;
   130 
   130 
   131 (*Sometimes useful with premises in this order*)
   131 (*Sometimes useful with premises in this order*)
   132 qed_goal "rev_subsetD" ZF.thy "!!A B c. [| c:A; A<=B |] ==> c:B"
   132 Goal "[| c:A; A<=B |] ==> c:B";
   133  (fn _=> [ Blast_tac 1 ]);
   133 by (Blast_tac 1);
       
   134 qed "rev_subsetD";
   134 
   135 
   135 (*Converts A<=B to x:A ==> x:B*)
   136 (*Converts A<=B to x:A ==> x:B*)
   136 fun impOfSubs th = th RSN (2, rev_subsetD);
   137 fun impOfSubs th = th RSN (2, rev_subsetD);
   137 
   138 
   138 qed_goal "contra_subsetD" ZF.thy "!!c. [| A <= B; c ~: B |] ==> c ~: A"
   139 Goal "[| A <= B; c ~: B |] ==> c ~: A";
   139  (fn _=> [ Blast_tac 1 ]);
   140 by (Blast_tac 1);
   140 
   141 qed "contra_subsetD";
   141 qed_goal "rev_contra_subsetD" ZF.thy "!!c. [| c ~: B;  A <= B |] ==> c ~: A"
   142 
   142  (fn _=> [ Blast_tac 1 ]);
   143 Goal "[| c ~: B;  A <= B |] ==> c ~: A";
   143 
   144 by (Blast_tac 1);
   144 qed_goal "subset_refl" ZF.thy "A <= A"
   145 qed "rev_contra_subsetD";
   145  (fn _=> [ Blast_tac 1 ]);
   146 
       
   147 Goal "A <= A";
       
   148 by (Blast_tac 1);
       
   149 qed "subset_refl";
   146 
   150 
   147 Addsimps [subset_refl];
   151 Addsimps [subset_refl];
   148 
   152 
   149 qed_goal "subset_trans" ZF.thy "!!A B C. [| A<=B;  B<=C |] ==> A<=C"
   153 Goal "[| A<=B;  B<=C |] ==> A<=C";
   150  (fn _=> [ Blast_tac 1 ]);
   154 by (Blast_tac 1);
       
   155 qed "subset_trans";
   151 
   156 
   152 (*Useful for proving A<=B by rewriting in some cases*)
   157 (*Useful for proving A<=B by rewriting in some cases*)
   153 qed_goalw "subset_iff" ZF.thy [subset_def,Ball_def]
   158 qed_goalw "subset_iff" ZF.thy [subset_def,Ball_def]
   154      "A<=B <-> (ALL x. x:A --> x:B)"
   159      "A<=B <-> (ALL x. x:A --> x:B)"
   155  (fn _=> [ (rtac iff_refl 1) ]);
   160  (fn _=> [ (rtac iff_refl 1) ]);
   156 
   161 
   157 
   162 
   158 (*** Rules for equality ***)
   163 (*** Rules for equality ***)
   159 
   164 
   160 (*Anti-symmetry of the subset relation*)
   165 (*Anti-symmetry of the subset relation*)
   161 qed_goal "equalityI" ZF.thy "[| A <= B;  B <= A |] ==> A = B"
   166 Goal "[| A <= B;  B <= A |] ==> A = B";
   162  (fn prems=> [ (REPEAT (resolve_tac (prems@[conjI, extension RS iffD2]) 1)) ]);
   167 by (REPEAT (ares_tac [conjI, extension RS iffD2] 1)) ;
       
   168 qed "equalityI";
   163 
   169 
   164 AddIs [equalityI];
   170 AddIs [equalityI];
   165 
   171 
   166 qed_goal "equality_iffI" ZF.thy "(!!x. x:A <-> x:B) ==> A = B"
   172 val [prem] = Goal "(!!x. x:A <-> x:B) ==> A = B";
   167  (fn [prem] =>
   173 by (rtac equalityI 1);
   168   [ (rtac equalityI 1),
   174 by (REPEAT (ares_tac [subsetI, prem RS iffD1, prem RS iffD2] 1)) ;
   169     (REPEAT (ares_tac [subsetI, prem RS iffD1, prem RS iffD2] 1)) ]);
   175 qed "equality_iffI";
   170 
   176 
   171 bind_thm ("equalityD1", extension RS iffD1 RS conjunct1);
   177 bind_thm ("equalityD1", extension RS iffD1 RS conjunct1);
   172 bind_thm ("equalityD2", extension RS iffD1 RS conjunct2);
   178 bind_thm ("equalityD2", extension RS iffD1 RS conjunct2);
   173 
   179 
   174 qed_goal "equalityE" ZF.thy
   180 val prems = Goal "[| A = B;  [| A<=B; B<=A |] ==> P |]  ==>  P";
   175     "[| A = B;  [| A<=B; B<=A |] ==> P |]  ==>  P"
   181 by (DEPTH_SOLVE (resolve_tac (prems@[equalityD1,equalityD2]) 1)) ;
   176  (fn prems=>
   182 qed "equalityE";
   177   [ (DEPTH_SOLVE (resolve_tac (prems@[equalityD1,equalityD2]) 1)) ]);
   183 
   178 
   184 val major::prems= Goal
   179 qed_goal "equalityCE" ZF.thy
   185     "[| A = B;  [| c:A; c:B |] ==> P;  [| c~:A; c~:B |] ==> P |]  ==>  P";
   180     "[| A = B;  [| c:A; c:B |] ==> P;  [| c~:A; c~:B |] ==> P |]  ==>  P"
   186 by (rtac (major RS equalityE) 1);
   181  (fn major::prems=>
   187 by (REPEAT (contr_tac 1 ORELSE eresolve_tac ([asm_rl,subsetCE]@prems) 1)) ;
   182   [ (rtac (major RS equalityE) 1),
   188 qed "equalityCE";
   183     (REPEAT (contr_tac 1 ORELSE eresolve_tac ([asm_rl,subsetCE]@prems) 1)) ]);
       
   184 
   189 
   185 (*Lemma for creating induction formulae -- for "pattern matching" on p
   190 (*Lemma for creating induction formulae -- for "pattern matching" on p
   186   To make the induction hypotheses usable, apply "spec" or "bspec" to
   191   To make the induction hypotheses usable, apply "spec" or "bspec" to
   187   put universal quantifiers over the free variables in p. 
   192   put universal quantifiers over the free variables in p. 
   188   Would it be better to do subgoal_tac "ALL z. p = f(z) --> R(z)" ??*)
   193   Would it be better to do subgoal_tac "ALL z. p = f(z) --> R(z)" ??*)
   189 qed_goal "setup_induction" ZF.thy
   194 val prems = Goal "[| p: A;  !!z. z: A ==> p=z --> R |] ==> R";
   190     "[| p: A;  !!z. z: A ==> p=z --> R |] ==> R"
   195 by (rtac mp 1);
   191  (fn prems=>
   196 by (REPEAT (resolve_tac (refl::prems) 1)) ;
   192   [ (rtac mp 1),
   197 qed "setup_induction";
   193     (REPEAT (resolve_tac (refl::prems) 1)) ]);
       
   194 
   198 
   195 
   199 
   196 (*** Rules for Replace -- the derived form of replacement ***)
   200 (*** Rules for Replace -- the derived form of replacement ***)
   197 
   201 
   198 qed_goalw "Replace_iff" ZF.thy [Replace_def]
   202 qed_goalw "Replace_iff" ZF.thy [Replace_def]
   201   [ (rtac (replacement RS iff_trans) 1),
   205   [ (rtac (replacement RS iff_trans) 1),
   202     (REPEAT (ares_tac [refl,bex_cong,iffI,ballI,allI,conjI,impI,ex1I] 1
   206     (REPEAT (ares_tac [refl,bex_cong,iffI,ballI,allI,conjI,impI,ex1I] 1
   203         ORELSE eresolve_tac [conjE, spec RS mp, ex1_functional] 1)) ]);
   207         ORELSE eresolve_tac [conjE, spec RS mp, ex1_functional] 1)) ]);
   204 
   208 
   205 (*Introduction; there must be a unique y such that P(x,y), namely y=b. *)
   209 (*Introduction; there must be a unique y such that P(x,y), namely y=b. *)
   206 qed_goal "ReplaceI" ZF.thy
   210 val prems = Goal
   207     "[| P(x,b);  x: A;  !!y. P(x,y) ==> y=b |] ==> \
   211     "[| P(x,b);  x: A;  !!y. P(x,y) ==> y=b |] ==> \
   208 \    b : {y. x:A, P(x,y)}"
   212 \    b : {y. x:A, P(x,y)}";
   209  (fn prems=>
   213 by (rtac (Replace_iff RS iffD2) 1);
   210   [ (rtac (Replace_iff RS iffD2) 1),
   214 by (REPEAT (ares_tac (prems@[bexI,conjI,allI,impI]) 1)) ;
   211     (REPEAT (ares_tac (prems@[bexI,conjI,allI,impI]) 1)) ]);
   215 qed "ReplaceI";
   212 
   216 
   213 (*Elimination; may asssume there is a unique y such that P(x,y), namely y=b. *)
   217 (*Elimination; may asssume there is a unique y such that P(x,y), namely y=b. *)
   214 qed_goal "ReplaceE" ZF.thy 
   218 val prems = Goal
   215     "[| b : {y. x:A, P(x,y)};  \
   219     "[| b : {y. x:A, P(x,y)};  \
   216 \       !!x. [| x: A;  P(x,b);  ALL y. P(x,y)-->y=b |] ==> R \
   220 \       !!x. [| x: A;  P(x,b);  ALL y. P(x,y)-->y=b |] ==> R \
   217 \    |] ==> R"
   221 \    |] ==> R";
   218  (fn prems=>
   222 by (rtac (Replace_iff RS iffD1 RS bexE) 1);
   219   [ (rtac (Replace_iff RS iffD1 RS bexE) 1),
   223 by (etac conjE 2);
   220     (etac conjE 2),
   224 by (REPEAT (ares_tac prems 1)) ;
   221     (REPEAT (ares_tac prems 1)) ]);
   225 qed "ReplaceE";
   222 
   226 
   223 (*As above but without the (generally useless) 3rd assumption*)
   227 (*As above but without the (generally useless) 3rd assumption*)
   224 qed_goal "ReplaceE2" ZF.thy 
   228 val major::prems = Goal
   225     "[| b : {y. x:A, P(x,y)};  \
   229     "[| b : {y. x:A, P(x,y)};  \
   226 \       !!x. [| x: A;  P(x,b) |] ==> R \
   230 \       !!x. [| x: A;  P(x,b) |] ==> R \
   227 \    |] ==> R"
   231 \    |] ==> R";
   228  (fn major::prems=>
   232 by (rtac (major RS ReplaceE) 1);
   229   [ (rtac (major RS ReplaceE) 1),
   233 by (REPEAT (ares_tac prems 1)) ;
   230     (REPEAT (ares_tac prems 1)) ]);
   234 qed "ReplaceE2";
   231 
   235 
   232 AddIs  [ReplaceI];  
   236 AddIs  [ReplaceI];  
   233 AddSEs [ReplaceE2];
   237 AddSEs [ReplaceE2];
   234 
   238 
   235 qed_goal "Replace_cong" ZF.thy
   239 val prems = Goal
   236     "[| A=B;  !!x y. x:B ==> P(x,y) <-> Q(x,y) |] ==> \
   240     "[| A=B;  !!x y. x:B ==> P(x,y) <-> Q(x,y) |] ==> \
   237 \    Replace(A,P) = Replace(B,Q)"
   241 \    Replace(A,P) = Replace(B,Q)";
   238  (fn prems=>
   242 by (rtac equalityI 1);
   239    let val substprems = prems RL [subst, ssubst]
   243 by (REPEAT
   240        and iffprems = prems RL [iffD1,iffD2]
   244     (eresolve_tac ((prems RL [subst, ssubst])@[asm_rl, ReplaceE, spec RS mp]) 1     ORELSE resolve_tac [subsetI, ReplaceI] 1 
   241    in [ (rtac equalityI 1),
   245      ORELSE (resolve_tac (prems RL [iffD1,iffD2]) 1 THEN assume_tac 2)));
   242         (REPEAT (eresolve_tac (substprems@[asm_rl, ReplaceE, spec RS mp]) 1
   246 qed "Replace_cong";
   243          ORELSE resolve_tac [subsetI, ReplaceI] 1
       
   244          ORELSE (resolve_tac iffprems 1 THEN assume_tac 2))) ]
       
   245    end);
       
   246 
   247 
   247 Addcongs [Replace_cong];
   248 Addcongs [Replace_cong];
   248 
   249 
   249 (*** Rules for RepFun ***)
   250 (*** Rules for RepFun ***)
   250 
   251 
   251 qed_goalw "RepFunI" ZF.thy [RepFun_def]
   252 qed_goalw "RepFunI" ZF.thy [RepFun_def]
   252     "!!a A. a : A ==> f(a) : {f(x). x:A}"
   253     "!!a A. a : A ==> f(a) : {f(x). x:A}"
   253  (fn _ => [ (REPEAT (ares_tac [ReplaceI,refl] 1)) ]);
   254  (fn _ => [ (REPEAT (ares_tac [ReplaceI,refl] 1)) ]);
   254 
   255 
   255 (*Useful for coinduction proofs*)
   256 (*Useful for coinduction proofs*)
   256 qed_goal "RepFun_eqI" ZF.thy
   257 Goal "[| b=f(a);  a : A |] ==> b : {f(x). x:A}";
   257     "!!b a f. [| b=f(a);  a : A |] ==> b : {f(x). x:A}"
   258 by (etac ssubst 1);
   258  (fn _ => [ etac ssubst 1, etac RepFunI 1 ]);
   259 by (etac RepFunI 1) ;
       
   260 qed "RepFun_eqI";
   259 
   261 
   260 qed_goalw "RepFunE" ZF.thy [RepFun_def]
   262 qed_goalw "RepFunE" ZF.thy [RepFun_def]
   261     "[| b : {f(x). x:A};  \
   263     "[| b : {f(x). x:A};  \
   262 \       !!x.[| x:A;  b=f(x) |] ==> P |] ==> \
   264 \       !!x.[| x:A;  b=f(x) |] ==> P |] ==> \
   263 \    P"
   265 \    P"
   274 
   276 
   275 Addcongs [RepFun_cong];
   277 Addcongs [RepFun_cong];
   276 
   278 
   277 qed_goalw "RepFun_iff" ZF.thy [Bex_def]
   279 qed_goalw "RepFun_iff" ZF.thy [Bex_def]
   278     "b : {f(x). x:A} <-> (EX x:A. b=f(x))"
   280     "b : {f(x). x:A} <-> (EX x:A. b=f(x))"
   279  (fn _ => [Blast_tac 1]);
   281  (fn _ => [(Blast_tac 1)]);
   280 
   282 
   281 Goal "{x. x:A} = A";
   283 Goal "{x. x:A} = A";
   282 by (Blast_tac 1);
   284 by (Blast_tac 1);
   283 qed "triv_RepFun";
   285 qed "triv_RepFun";
   284 
   286 
   287 (*** Rules for Collect -- forming a subset by separation ***)
   289 (*** Rules for Collect -- forming a subset by separation ***)
   288 
   290 
   289 (*Separation is derivable from Replacement*)
   291 (*Separation is derivable from Replacement*)
   290 qed_goalw "separation" ZF.thy [Collect_def]
   292 qed_goalw "separation" ZF.thy [Collect_def]
   291     "a : {x:A. P(x)} <-> a:A & P(a)"
   293     "a : {x:A. P(x)} <-> a:A & P(a)"
   292  (fn _=> [Blast_tac 1]);
   294  (fn _=> [(Blast_tac 1)]);
   293 
   295 
   294 Addsimps [separation];
   296 Addsimps [separation];
   295 
   297 
   296 qed_goal "CollectI" ZF.thy
   298 Goal "[| a:A;  P(a) |] ==> a : {x:A. P(x)}";
   297     "!!P. [| a:A;  P(a) |] ==> a : {x:A. P(x)}"
   299 by (Asm_simp_tac 1);
   298  (fn _=> [ Asm_simp_tac 1 ]);
   300 qed "CollectI";
   299 
   301 
   300 qed_goal "CollectE" ZF.thy
   302 val prems = Goal
   301     "[| a : {x:A. P(x)};  [| a:A; P(a) |] ==> R |] ==> R"
   303     "[| a : {x:A. P(x)};  [| a:A; P(a) |] ==> R |] ==> R";
   302  (fn prems=>
   304 by (rtac (separation RS iffD1 RS conjE) 1);
   303   [ (rtac (separation RS iffD1 RS conjE) 1),
   305 by (REPEAT (ares_tac prems 1)) ;
   304     (REPEAT (ares_tac prems 1)) ]);
   306 qed "CollectE";
   305 
   307 
   306 qed_goal "CollectD1" ZF.thy "!!P. a : {x:A. P(x)} ==> a:A"
   308 Goal "a : {x:A. P(x)} ==> a:A";
   307  (fn _=> [ (etac CollectE 1), (assume_tac 1) ]);
   309 by (etac CollectE 1);
   308 
   310 by (assume_tac 1) ;
   309 qed_goal "CollectD2" ZF.thy "!!P. a : {x:A. P(x)} ==> P(a)"
   311 qed "CollectD1";
   310  (fn _=> [ (etac CollectE 1), (assume_tac 1) ]);
   312 
       
   313 Goal "a : {x:A. P(x)} ==> P(a)";
       
   314 by (etac CollectE 1);
       
   315 by (assume_tac 1) ;
       
   316 qed "CollectD2";
   311 
   317 
   312 qed_goalw "Collect_cong" ZF.thy [Collect_def] 
   318 qed_goalw "Collect_cong" ZF.thy [Collect_def] 
   313     "[| A=B;  !!x. x:B ==> P(x) <-> Q(x) |] ==> Collect(A,P) = Collect(B,Q)"
   319     "[| A=B;  !!x. x:B ==> P(x) <-> Q(x) |] ==> Collect(A,P) = Collect(B,Q)"
   314  (fn prems=> [ (simp_tac (simpset() addsimps prems) 1) ]);
   320  (fn prems=> [ (simp_tac (simpset() addsimps prems) 1) ]);
   315 
   321 
   320 (*** Rules for Unions ***)
   326 (*** Rules for Unions ***)
   321 
   327 
   322 Addsimps [Union_iff];
   328 Addsimps [Union_iff];
   323 
   329 
   324 (*The order of the premises presupposes that C is rigid; A may be flexible*)
   330 (*The order of the premises presupposes that C is rigid; A may be flexible*)
   325 qed_goal "UnionI" ZF.thy "!!C. [| B: C;  A: B |] ==> A: Union(C)"
   331 Goal "[| B: C;  A: B |] ==> A: Union(C)";
   326  (fn _=> [ Simp_tac 1, Blast_tac 1 ]);
   332 by (Simp_tac 1);
   327 
   333 by (Blast_tac 1) ;
   328 qed_goal "UnionE" ZF.thy
   334 qed "UnionI";
   329     "[| A : Union(C);  !!B.[| A: B;  B: C |] ==> R |] ==> R"
   335 
   330  (fn prems=>
   336 val prems = Goal "[| A : Union(C);  !!B.[| A: B;  B: C |] ==> R |] ==> R";
   331   [ (resolve_tac [Union_iff RS iffD1 RS bexE] 1),
   337 by (resolve_tac [Union_iff RS iffD1 RS bexE] 1);
   332     (REPEAT (ares_tac prems 1)) ]);
   338 by (REPEAT (ares_tac prems 1)) ;
       
   339 qed "UnionE";
   333 
   340 
   334 (*** Rules for Unions of families ***)
   341 (*** Rules for Unions of families ***)
   335 (* UN x:A. B(x) abbreviates Union({B(x). x:A}) *)
   342 (* UN x:A. B(x) abbreviates Union({B(x). x:A}) *)
   336 
   343 
   337 qed_goalw "UN_iff" ZF.thy [Bex_def]
   344 qed_goalw "UN_iff" ZF.thy [Bex_def]
   339  (fn _=> [ Simp_tac 1, Blast_tac 1 ]);
   346  (fn _=> [ Simp_tac 1, Blast_tac 1 ]);
   340 
   347 
   341 Addsimps [UN_iff];
   348 Addsimps [UN_iff];
   342 
   349 
   343 (*The order of the premises presupposes that A is rigid; b may be flexible*)
   350 (*The order of the premises presupposes that A is rigid; b may be flexible*)
   344 qed_goal "UN_I" ZF.thy "!!A B. [| a: A;  b: B(a) |] ==> b: (UN x:A. B(x))"
   351 Goal "[| a: A;  b: B(a) |] ==> b: (UN x:A. B(x))";
   345  (fn _=> [ Simp_tac 1, Blast_tac 1 ]);
   352 by (Simp_tac 1);
   346 
   353 by (Blast_tac 1) ;
   347 qed_goal "UN_E" ZF.thy
   354 qed "UN_I";
   348     "[| b : (UN x:A. B(x));  !!x.[| x: A;  b: B(x) |] ==> R |] ==> R"
   355 
   349  (fn major::prems=>
   356 val major::prems= Goal
   350   [ (rtac (major RS UnionE) 1),
   357     "[| b : (UN x:A. B(x));  !!x.[| x: A;  b: B(x) |] ==> R |] ==> R";
   351     (REPEAT (eresolve_tac (prems@[asm_rl, RepFunE, subst]) 1)) ]);
   358 by (rtac (major RS UnionE) 1);
   352 
   359 by (REPEAT (eresolve_tac (prems@[asm_rl, RepFunE, subst]) 1)) ;
   353 qed_goal "UN_cong" ZF.thy
   360 qed "UN_E";
   354     "[| A=B;  !!x. x:B ==> C(x)=D(x) |] ==> (UN x:A. C(x)) = (UN x:B. D(x))"
   361 
   355  (fn prems=> [ (simp_tac (simpset() addsimps prems) 1) ]);
   362 val prems = Goal
       
   363     "[| A=B;  !!x. x:B ==> C(x)=D(x) |] ==> (UN x:A. C(x)) = (UN x:B. D(x))";
       
   364 by (simp_tac (simpset() addsimps prems) 1) ;
       
   365 qed "UN_cong";
   356 
   366 
   357 (*No "Addcongs [UN_cong]" because UN is a combination of constants*)
   367 (*No "Addcongs [UN_cong]" because UN is a combination of constants*)
   358 
   368 
   359 (* UN_E appears before UnionE so that it is tried first, to avoid expensive
   369 (* UN_E appears before UnionE so that it is tried first, to avoid expensive
   360   calls to hyp_subst_tac.  Cannot include UN_I as it is unsafe: would enlarge
   370   calls to hyp_subst_tac.  Cannot include UN_I as it is unsafe: would enlarge
   370 qed_goalw "Inter_iff" ZF.thy [Inter_def,Ball_def]
   380 qed_goalw "Inter_iff" ZF.thy [Inter_def,Ball_def]
   371     "A : Inter(C) <-> (ALL x:C. A: x) & (EX x. x:C)"
   381     "A : Inter(C) <-> (ALL x:C. A: x) & (EX x. x:C)"
   372  (fn _=> [ Simp_tac 1, Blast_tac 1 ]);
   382  (fn _=> [ Simp_tac 1, Blast_tac 1 ]);
   373 
   383 
   374 (* Intersection is well-behaved only if the family is non-empty! *)
   384 (* Intersection is well-behaved only if the family is non-empty! *)
   375 qed_goal "InterI" ZF.thy
   385 val prems = Goal
   376     "[| !!x. x: C ==> A: x;  EX c. c:C |] ==> A : Inter(C)"
   386     "[| !!x. x: C ==> A: x;  EX c. c:C |] ==> A : Inter(C)";
   377  (fn prems=> [ (simp_tac (simpset() addsimps [Inter_iff]) 1), 
   387 by (simp_tac (simpset() addsimps [Inter_iff]) 1);
   378 	       blast_tac (claset() addIs prems) 1 ]);
   388 by (blast_tac (claset() addIs prems) 1) ;
       
   389 qed "InterI";
   379 
   390 
   380 (*A "destruct" rule -- every B in C contains A as an element, but
   391 (*A "destruct" rule -- every B in C contains A as an element, but
   381   A:B can hold when B:C does not!  This rule is analogous to "spec". *)
   392   A:B can hold when B:C does not!  This rule is analogous to "spec". *)
   382 qed_goalw "InterD" ZF.thy [Inter_def]
   393 qed_goalw "InterD" ZF.thy [Inter_def]
   383     "!!C. [| A : Inter(C);  B : C |] ==> A : B"
   394     "!!C. [| A : Inter(C);  B : C |] ==> A : B"
   384  (fn _=> [ Blast_tac 1 ]);
   395  (fn _=> [(Blast_tac 1)]);
   385 
   396 
   386 (*"Classical" elimination rule -- does not require exhibiting B:C *)
   397 (*"Classical" elimination rule -- does not require exhibiting B:C *)
   387 qed_goalw "InterE" ZF.thy [Inter_def]
   398 qed_goalw "InterE" ZF.thy [Inter_def]
   388     "[| A : Inter(C);  B~:C ==> R;  A:B ==> R |] ==> R"
   399     "[| A : Inter(C);  B~:C ==> R;  A:B ==> R |] ==> R"
   389  (fn major::prems=>
   400  (fn major::prems=>
   398 
   409 
   399 qed_goalw "INT_iff" ZF.thy [Inter_def]
   410 qed_goalw "INT_iff" ZF.thy [Inter_def]
   400     "b : (INT x:A. B(x)) <-> (ALL x:A. b : B(x)) & (EX x. x:A)"
   411     "b : (INT x:A. B(x)) <-> (ALL x:A. b : B(x)) & (EX x. x:A)"
   401  (fn _=> [ Simp_tac 1, Best_tac 1 ]);
   412  (fn _=> [ Simp_tac 1, Best_tac 1 ]);
   402 
   413 
   403 qed_goal "INT_I" ZF.thy
   414 val prems = Goal
   404     "[| !!x. x: A ==> b: B(x);  a: A |] ==> b: (INT x:A. B(x))"
   415     "[| !!x. x: A ==> b: B(x);  a: A |] ==> b: (INT x:A. B(x))";
   405  (fn prems=> [ blast_tac (claset() addIs prems) 1 ]);
   416 by (blast_tac (claset() addIs prems) 1);
   406 
   417 qed "INT_I";
   407 qed_goal "INT_E" ZF.thy
   418 
   408     "[| b : (INT x:A. B(x));  a: A |] ==> b : B(a)"
   419 Goal "[| b : (INT x:A. B(x));  a: A |] ==> b : B(a)";
   409  (fn [major,minor]=>
   420 by (Blast_tac 1);
   410   [ (rtac (major RS InterD) 1),
   421 qed "INT_E";
   411     (rtac (minor RS RepFunI) 1) ]);
   422 
   412 
   423 val prems = Goal
   413 qed_goal "INT_cong" ZF.thy
   424     "[| A=B;  !!x. x:B ==> C(x)=D(x) |] ==> (INT x:A. C(x)) = (INT x:B. D(x))";
   414     "[| A=B;  !!x. x:B ==> C(x)=D(x) |] ==> (INT x:A. C(x)) = (INT x:B. D(x))"
   425 by (simp_tac (simpset() addsimps prems) 1) ;
   415  (fn prems=> [ (simp_tac (simpset() addsimps prems) 1) ]);
   426 qed "INT_cong";
   416 
   427 
   417 (*No "Addcongs [INT_cong]" because INT is a combination of constants*)
   428 (*No "Addcongs [INT_cong]" because INT is a combination of constants*)
   418 
   429 
   419 
   430 
   420 (*** Rules for Powersets ***)
   431 (*** Rules for Powersets ***)
   421 
   432 
   422 qed_goal "PowI" ZF.thy "A <= B ==> A : Pow(B)"
   433 Goal "A <= B ==> A : Pow(B)";
   423  (fn [prem]=> [ (rtac (prem RS (Pow_iff RS iffD2)) 1) ]);
   434 by (etac (Pow_iff RS iffD2) 1) ;
   424 
   435 qed "PowI";
   425 qed_goal "PowD" ZF.thy "A : Pow(B)  ==>  A<=B"
   436 
   426  (fn [major]=> [ (rtac (major RS (Pow_iff RS iffD1)) 1) ]);
   437 Goal "A : Pow(B)  ==>  A<=B";
       
   438 by (etac (Pow_iff RS iffD1) 1) ;
       
   439 qed "PowD";
   427 
   440 
   428 AddSIs [PowI];
   441 AddSIs [PowI];
   429 AddSDs [PowD];
   442 AddSDs [PowD];
   430 
   443 
   431 
   444 
   432 (*** Rules for the empty set ***)
   445 (*** Rules for the empty set ***)
   433 
   446 
   434 (*The set {x:0.False} is empty; by foundation it equals 0 
   447 (*The set {x:0.False} is empty; by foundation it equals 0 
   435   See Suppes, page 21.*)
   448   See Suppes, page 21.*)
   436 qed_goal "not_mem_empty" ZF.thy "a ~: 0"
   449 Goal "a ~: 0";
   437  (fn _=>
   450 by (cut_facts_tac [foundation] 1);
   438   [ (cut_facts_tac [foundation] 1), 
   451 by (best_tac (claset() addDs [equalityD2]) 1) ;
   439     (best_tac (claset() addDs [equalityD2]) 1) ]);
   452 qed "not_mem_empty";
   440 
   453 
   441 bind_thm ("emptyE", not_mem_empty RS notE);
   454 bind_thm ("emptyE", not_mem_empty RS notE);
   442 
   455 
   443 Addsimps [not_mem_empty];
   456 Addsimps [not_mem_empty];
   444 AddSEs [emptyE];
   457 AddSEs [emptyE];
   445 
   458 
   446 qed_goal "empty_subsetI" ZF.thy "0 <= A"
   459 Goal "0 <= A";
   447  (fn _=> [ Blast_tac 1 ]);
   460 by (Blast_tac 1);
       
   461 qed "empty_subsetI";
   448 
   462 
   449 Addsimps [empty_subsetI];
   463 Addsimps [empty_subsetI];
   450 
   464 
   451 qed_goal "equals0I" ZF.thy "[| !!y. y:A ==> False |] ==> A=0"
   465 val prems = Goal "[| !!y. y:A ==> False |] ==> A=0";
   452  (fn prems=> [ blast_tac (claset() addDs prems) 1 ]);
   466 by (blast_tac (claset() addDs prems) 1) ;
   453 
   467 qed "equals0I";
   454 qed_goal "equals0D" ZF.thy "!!P. A=0 ==> a ~: A"
   468 
   455  (fn _=> [ Blast_tac 1 ]);
   469 Goal "A=0 ==> a ~: A";
       
   470 by (Blast_tac 1);
       
   471 qed "equals0D";
   456 
   472 
   457 AddDs [equals0D, sym RS equals0D];
   473 AddDs [equals0D, sym RS equals0D];
   458 
   474 
   459 qed_goal "not_emptyI" ZF.thy "!!A a. a:A ==> A ~= 0"
   475 Goal "a:A ==> A ~= 0";
   460  (fn _=> [ Blast_tac 1 ]);
   476 by (Blast_tac 1);
   461 
   477 qed "not_emptyI";
   462 qed_goal "not_emptyE" ZF.thy "[| A ~= 0;  !!x. x:A ==> R |] ==> R"
   478 
   463  (fn [major,minor]=>
   479 val [major,minor]= Goal "[| A ~= 0;  !!x. x:A ==> R |] ==> R";
   464   [ rtac ([major, equals0I] MRS swap) 1,
   480 by (rtac ([major, equals0I] MRS swap) 1);
   465     swap_res_tac [minor] 1,
   481 by (swap_res_tac [minor] 1);
   466     assume_tac 1 ]);
   482 by (assume_tac 1) ;
       
   483 qed "not_emptyE";
   467 
   484 
   468 
   485 
   469 (*** Cantor's Theorem: There is no surjection from a set to its powerset. ***)
   486 (*** Cantor's Theorem: There is no surjection from a set to its powerset. ***)
   470 
   487 
   471 val cantor_cs = FOL_cs   (*precisely the rules needed for the proof*)
   488 val cantor_cs = FOL_cs   (*precisely the rules needed for the proof*)
   472   addSIs [ballI, CollectI, PowI, subsetI] addIs [bexI]
   489   addSIs [ballI, CollectI, PowI, subsetI] addIs [bexI]
   473   addSEs [CollectE, equalityCE];
   490   addSEs [CollectE, equalityCE];
   474 
   491 
   475 (*The search is undirected; similar proof attempts may fail.
   492 (*The search is undirected; similar proof attempts may fail.
   476   b represents ANY map, such as (lam x:A.b(x)): A->Pow(A). *)
   493   b represents ANY map, such as (lam x:A.b(x)): A->Pow(A). *)
   477 qed_goal "cantor" ZF.thy "EX S: Pow(A). ALL x:A. b(x) ~= S"
   494 Goal "EX S: Pow(A). ALL x:A. b(x) ~= S";
   478  (fn _ => [best_tac cantor_cs 1]);
   495 by (best_tac cantor_cs 1);
       
   496 qed "cantor";
   479 
   497 
   480 (*Lemma for the inductive definition in Zorn.thy*)
   498 (*Lemma for the inductive definition in Zorn.thy*)
   481 qed_goal "Union_in_Pow" ZF.thy
   499 Goal "Y : Pow(Pow(A)) ==> Union(Y) : Pow(A)";
   482     "!!Y. Y : Pow(Pow(A)) ==> Union(Y) : Pow(A)"
   500 by (Blast_tac 1);
   483  (fn _ => [Blast_tac 1]);
   501 qed "Union_in_Pow";
   484 
   502 
   485 
   503 
   486 local
   504 local
   487 val (bspecT, bspec') = make_new_spec bspec
   505 val (bspecT, bspec') = make_new_spec bspec
   488 in
   506 in