src/ZF/AC/AC2_AC6.ML
changeset 2469 b50b8c0eec01
parent 1932 cc9f1ba8f29a
child 2496 40efb87985b5
equal deleted inserted replaced
2468:428efffe8599 2469:b50b8c0eec01
    14 (* AC1 ==> AC2                                                            *)
    14 (* AC1 ==> AC2                                                            *)
    15 (* ********************************************************************** *)
    15 (* ********************************************************************** *)
    16 
    16 
    17 goal thy "!!B. [| B:A; f:(PROD X:A. X); 0~:A |]  \
    17 goal thy "!!B. [| B:A; f:(PROD X:A. X); 0~:A |]  \
    18 \               ==> {f`B} <= B Int {f`C. C:A}";
    18 \               ==> {f`B} <= B Int {f`C. C:A}";
    19 by (fast_tac (ZF_cs addSEs [apply_type]) 1);
    19 by (fast_tac (!claset addSEs [apply_type]) 1);
    20 val lemma1 = result();
    20 val lemma1 = result();
    21 
    21 
    22 goalw thy [pairwise_disjoint_def]
    22 goalw thy [pairwise_disjoint_def]
    23         "!!A. [| pairwise_disjoint(A); B:A; C:A; D:B; D:C |] ==> f`B = f`C";
    23         "!!A. [| pairwise_disjoint(A); B:A; C:A; D:B; D:C |] ==> f`B = f`C";
    24 by (fast_tac (ZF_cs addSEs [equals0D]) 1);
    24 by (fast_tac (!claset addSEs [equals0D]) 1);
    25 val lemma2 = result();
    25 val lemma2 = result();
    26 
    26 
    27 goalw thy AC_defs "!!Z. AC1 ==> AC2"; 
    27 goalw thy AC_defs "!!Z. AC1 ==> AC2"; 
    28 by (rtac allI 1);
    28 by (rtac allI 1);
    29 by (rtac impI 1);
    29 by (rtac impI 1);
    30 by (REPEAT (eresolve_tac [asm_rl,conjE,allE,exE,impE] 1));
    30 by (REPEAT (eresolve_tac [asm_rl,conjE,allE,exE,impE] 1));
    31 by (REPEAT (resolve_tac [exI,ballI,equalityI] 1));
    31 by (REPEAT (resolve_tac [exI,ballI,equalityI] 1));
    32 by (rtac lemma1 2 THEN (REPEAT (assume_tac 2)));
    32 by (rtac lemma1 2 THEN (REPEAT (assume_tac 2)));
    33 by (fast_tac (AC_cs addSEs [RepFunE, lemma2] addEs [apply_type]) 1);
    33 by (fast_tac (!claset addSEs [RepFunE, lemma2] addEs [apply_type]) 1);
    34 qed "AC1_AC2";
    34 qed "AC1_AC2";
    35 
    35 
    36 
    36 
    37 (* ********************************************************************** *)
    37 (* ********************************************************************** *)
    38 (* AC2 ==> AC1                                                            *)
    38 (* AC2 ==> AC1                                                            *)
    39 (* ********************************************************************** *)
    39 (* ********************************************************************** *)
    40 
    40 
    41 goal thy "!!A. 0~:A ==> 0 ~: {B*{B}. B:A}";
    41 goal thy "!!A. 0~:A ==> 0 ~: {B*{B}. B:A}";
    42 by (fast_tac (AC_cs addSDs [sym RS (Sigma_empty_iff RS iffD1)]
    42 by (fast_tac (!claset addSDs [sym RS (Sigma_empty_iff RS iffD1)]
    43         addSEs [RepFunE, equals0D]) 1);
    43         addSEs [RepFunE, equals0D]) 1);
    44 val lemma1 = result();
    44 val lemma1 = result();
    45 
    45 
    46 goal thy "!!A. [| X*{X} Int C = {y}; X:A |]  \
    46 goal thy "!!A. [| X*{X} Int C = {y}; X:A |]  \
    47 \               ==> (THE y. X*{X} Int C = {y}): X*A";
    47 \               ==> (THE y. X*{X} Int C = {y}): X*A";
    48 by (rtac subst_elem 1);
    48 by (rtac subst_elem 1);
    49 by (fast_tac (ZF_cs addSIs [the_equality]
    49 by (fast_tac (!claset addSIs [the_equality]
    50                 addSEs [sym RS trans RS (singleton_eq_iff RS iffD1)]) 2);
    50                 addSEs [sym RS trans RS (singleton_eq_iff RS iffD1)]) 2);
    51 by (fast_tac (AC_cs addSEs [equalityE, make_elim singleton_subsetD]) 1);
    51 by (fast_tac (!claset addSEs [equalityE, make_elim singleton_subsetD]) 1);
    52 val lemma2 = result();
    52 val lemma2 = result();
    53 
    53 
    54 goal thy "!!A. ALL D:{E*{E}. E:A}. EX y. D Int C = {y}  \
    54 goal thy "!!A. ALL D:{E*{E}. E:A}. EX y. D Int C = {y}  \
    55 \       ==> (lam x:A. fst(THE z. (x*{x} Int C = {z}))) :  \
    55 \       ==> (lam x:A. fst(THE z. (x*{x} Int C = {z}))) :  \
    56 \               (PROD X:A. X) ";
    56 \               (PROD X:A. X) ";
    57 by (fast_tac (FOL_cs addSEs [lemma2]
    57 by (fast_tac (!claset addSEs [lemma2]
    58                 addSIs [lam_type, RepFunI, fst_type]
    58                 addSIs [lam_type, RepFunI, fst_type]
    59                 addSDs [bspec]) 1);
    59                 addSDs [bspec]) 1);
    60 val lemma3 = result();
    60 val lemma3 = result();
    61 
    61 
    62 goalw thy (AC_defs@AC_aux_defs) "!!Z. AC2 ==> AC1";
    62 goalw thy (AC_defs@AC_aux_defs) "!!Z. AC2 ==> AC1";
    63 by (REPEAT (resolve_tac [allI, impI] 1));
    63 by (REPEAT (resolve_tac [allI, impI] 1));
    64 by (REPEAT (eresolve_tac [allE, impE] 1));
    64 by (REPEAT (eresolve_tac [allE, impE] 1));
    65 by (fast_tac (AC_cs addSEs [lemma3]) 2);
    65 by (fast_tac (!claset addSEs [lemma3]) 2);
    66 by (fast_tac (AC_cs addSIs [lemma1, equals0I]) 1);
    66 by (fast_tac (!claset addSIs [lemma1, equals0I]) 1);
    67 qed "AC2_AC1";
    67 qed "AC2_AC1";
    68 
    68 
    69 
    69 
    70 (* ********************************************************************** *)
    70 (* ********************************************************************** *)
    71 (* AC1 ==> AC4                                                            *)
    71 (* AC1 ==> AC4                                                            *)
    72 (* ********************************************************************** *)
    72 (* ********************************************************************** *)
    73 
    73 
    74 goal thy "!!R. 0 ~: {R``{x}. x:domain(R)}";
    74 goal thy "!!R. 0 ~: {R``{x}. x:domain(R)}";
    75 by (fast_tac (AC_cs addEs [sym RS equals0D]) 1);
    75 by (fast_tac (!claset addEs [sym RS equals0D]) 1);
    76 val lemma = result();
    76 val lemma = result();
    77 
    77 
    78 goalw thy AC_defs "!!Z. AC1 ==> AC4";
    78 goalw thy AC_defs "!!Z. AC1 ==> AC4";
    79 by (REPEAT (resolve_tac [allI, impI] 1));
    79 by (REPEAT (resolve_tac [allI, impI] 1));
    80 by (REPEAT (eresolve_tac [allE, lemma RSN (2, impE), exE] 1));
    80 by (REPEAT (eresolve_tac [allE, lemma RSN (2, impE), exE] 1));
    81 by (fast_tac (AC_cs addSIs [lam_type] addSEs [apply_type]) 1);
    81 by (fast_tac (!claset addSIs [lam_type] addSEs [apply_type]) 1);
    82 qed "AC1_AC4";
    82 qed "AC1_AC4";
    83 
    83 
    84 
    84 
    85 (* ********************************************************************** *)
    85 (* ********************************************************************** *)
    86 (* AC4 ==> AC3                                                            *)
    86 (* AC4 ==> AC3                                                            *)
    87 (* ********************************************************************** *)
    87 (* ********************************************************************** *)
    88 
    88 
    89 goal thy "!!f. f:A->B ==> (UN z:A. {z}*f`z) <= A*Union(B)";
    89 goal thy "!!f. f:A->B ==> (UN z:A. {z}*f`z) <= A*Union(B)";
    90 by (fast_tac (ZF_cs addSDs [apply_type]) 1);
    90 by (fast_tac (!claset addSDs [apply_type]) 1);
    91 val lemma1 = result();
    91 val lemma1 = result();
    92 
    92 
    93 goal thy "!!f. domain(UN z:A. {z}*f(z)) = {a:A. f(a)~=0}";
    93 goal thy "!!f. domain(UN z:A. {z}*f(z)) = {a:A. f(a)~=0}";
    94 by (fast_tac (ZF_cs addIs [equalityI]
    94 by (fast_tac (!claset addIs [equalityI]
    95                 addSEs [not_emptyE]
    95                 addSEs [not_emptyE]
    96                 addSIs [not_emptyI]
    96                 addSIs [not_emptyI]
    97                 addDs [range_type]) 1);
    97                 addDs [range_type]) 1);
    98 val lemma2 = result();
    98 val lemma2 = result();
    99 
    99 
   100 goal thy "!!f. x:A ==> (UN z:A. {z}*f(z))``{x} = f(x)";
   100 goal thy "!!f. x:A ==> (UN z:A. {z}*f(z))``{x} = f(x)";
   101 by (fast_tac (ZF_cs addIs [equalityI]) 1);
   101 by (fast_tac (!claset addIs [equalityI]) 1);
   102 val lemma3 = result();
   102 val lemma3 = result();
   103 
   103 
   104 goalw thy AC_defs "!!Z. AC4 ==> AC3";
   104 goalw thy AC_defs "!!Z. AC4 ==> AC3";
   105 by (REPEAT (resolve_tac [allI,ballI] 1));
   105 by (REPEAT (resolve_tac [allI,ballI] 1));
   106 by (REPEAT (eresolve_tac [allE,impE] 1));
   106 by (REPEAT (eresolve_tac [allE,impE] 1));
   107 by (etac lemma1 1);
   107 by (etac lemma1 1);
   108 by (asm_full_simp_tac (AC_ss addsimps [lemma2, lemma3]
   108 by (asm_full_simp_tac (!simpset addsimps [lemma2, lemma3]
   109                         addcongs [Pi_cong]) 1);
   109                         addcongs [Pi_cong]) 1);
   110 qed "AC4_AC3";
   110 qed "AC4_AC3";
   111 
   111 
   112 (* ********************************************************************** *)
   112 (* ********************************************************************** *)
   113 (* AC3 ==> AC1                                                            *)
   113 (* AC3 ==> AC1                                                            *)
   114 (* ********************************************************************** *)
   114 (* ********************************************************************** *)
   115 
   115 
   116 goal thy "!!A. b~:A ==> (PROD x:{a:A. id(A)`a~=b}. id(A)`x) = (PROD x:A. x)";
   116 goal thy "!!A. b~:A ==> (PROD x:{a:A. id(A)`a~=b}. id(A)`x) = (PROD x:A. x)";
   117 by (asm_full_simp_tac (AC_ss addsimps [id_def] addcongs [Pi_cong]) 1);
   117 by (asm_full_simp_tac (!simpset addsimps [id_def] addcongs [Pi_cong]) 1);
   118 by (res_inst_tac [("b","A")] subst_context 1);
   118 by (res_inst_tac [("b","A")] subst_context 1);
   119 by (fast_tac (AC_cs addSIs [equalityI]) 1);
   119 by (fast_tac (!claset addSIs [equalityI]) 1);
   120 val lemma = result();
   120 val lemma = result();
   121 
   121 
   122 goalw thy AC_defs "!!Z. AC3 ==> AC1";
   122 goalw thy AC_defs "!!Z. AC3 ==> AC1";
   123 by (REPEAT (resolve_tac [allI, impI] 1));
   123 by (REPEAT (resolve_tac [allI, impI] 1));
   124 by (REPEAT (eresolve_tac [allE, ballE] 1));
   124 by (REPEAT (eresolve_tac [allE, ballE] 1));
   125 by (fast_tac (AC_cs addSIs [id_type]) 2);
   125 by (fast_tac (!claset addSIs [id_type]) 2);
   126 by (fast_tac (AC_cs addEs [lemma RS subst]) 1);
   126 by (fast_tac (!claset addEs [lemma RS subst]) 1);
   127 qed "AC3_AC1";
   127 qed "AC3_AC1";
   128 
   128 
   129 (* ********************************************************************** *)
   129 (* ********************************************************************** *)
   130 (* AC4 ==> AC5                                                            *)
   130 (* AC4 ==> AC5                                                            *)
   131 (* ********************************************************************** *)
   131 (* ********************************************************************** *)
   135 by (REPEAT (eresolve_tac [allE,impE] 1));
   135 by (REPEAT (eresolve_tac [allE,impE] 1));
   136 by (eresolve_tac [fun_is_rel RS converse_type] 1);
   136 by (eresolve_tac [fun_is_rel RS converse_type] 1);
   137 by (etac exE 1);
   137 by (etac exE 1);
   138 by (rtac bexI 1);
   138 by (rtac bexI 1);
   139 by (rtac Pi_type 2 THEN (assume_tac 2));
   139 by (rtac Pi_type 2 THEN (assume_tac 2));
   140 by (fast_tac (ZF_cs addSDs [apply_type]
   140 by (fast_tac (!claset addSDs [apply_type]
   141         addSEs [fun_is_rel RS converse_type RS subsetD RS SigmaD2]) 2);
   141         addSEs [fun_is_rel RS converse_type RS subsetD RS SigmaD2]) 2);
   142 by (rtac ballI 1);
   142 by (rtac ballI 1);
   143 by (rtac apply_equality 1 THEN (assume_tac 2));
   143 by (rtac apply_equality 1 THEN (assume_tac 2));
   144 by (etac domainE 1);
   144 by (etac domainE 1);
   145 by (forward_tac [range_type] 1 THEN (assume_tac 1));
   145 by (forward_tac [range_type] 1 THEN (assume_tac 1));
   146 by (fast_tac (ZF_cs addDs [apply_equality]) 1);
   146 by (fast_tac (!claset addDs [apply_equality]) 1);
   147 qed "AC4_AC5";
   147 qed "AC4_AC5";
   148 
   148 
   149 
   149 
   150 (* ********************************************************************** *)
   150 (* ********************************************************************** *)
   151 (* AC5 ==> AC4, Rubin & Rubin, p. 11                                      *)
   151 (* AC5 ==> AC4, Rubin & Rubin, p. 11                                      *)
   152 (* ********************************************************************** *)
   152 (* ********************************************************************** *)
   153 
   153 
   154 goal thy "!!A. R <= A*B ==> (lam x:R. fst(x)) : R -> A";
   154 goal thy "!!A. R <= A*B ==> (lam x:R. fst(x)) : R -> A";
   155 by (fast_tac (ZF_cs addSIs [lam_type, fst_type]) 1);
   155 by (fast_tac (!claset addSIs [lam_type, fst_type]) 1);
   156 val lemma1 = result();
   156 val lemma1 = result();
   157 
   157 
   158 goalw thy [range_def] "!!A. R <= A*B ==> range(lam x:R. fst(x)) = domain(R)";
   158 goalw thy [range_def] "!!A. R <= A*B ==> range(lam x:R. fst(x)) = domain(R)";
   159 by (rtac equalityI 1);
   159 by (rtac equalityI 1);
   160 by (fast_tac (AC_cs addSEs [lamE]
   160 by (fast_tac (!claset addSEs [lamE]
   161                 addEs [subst_elem]
   161                 addEs [subst_elem]
   162                 addSDs [Pair_fst_snd_eq]) 1);
   162                 addSDs [Pair_fst_snd_eq]) 1);
   163 by (rtac subsetI 1);
   163 by (rtac subsetI 1);
   164 by (etac domainE 1);
   164 by (etac domainE 1);
   165 by (rtac domainI 1);
   165 by (rtac domainI 1);
   166 by (fast_tac (AC_cs addSEs [lamI RS subst_elem] addIs [fst_conv RS ssubst]) 1);
   166 by (fast_tac (!claset addSEs [lamI RS subst_elem] addIs [fst_conv RS ssubst]) 1);
   167 val lemma2 = result();
   167 val lemma2 = result();
   168 
   168 
   169 goal thy "!!A. [| EX f: A->C. P(f,domain(f)); A=B |] ==>  EX f: B->C. P(f,B)";
   169 goal thy "!!A. [| EX f: A->C. P(f,domain(f)); A=B |] ==>  EX f: B->C. P(f,B)";
   170 by (etac bexE 1);
   170 by (etac bexE 1);
   171 by (forward_tac [domain_of_fun] 1);
   171 by (forward_tac [domain_of_fun] 1);
   172 by (fast_tac ZF_cs 1);
   172 by (Fast_tac 1);
   173 val lemma3 = result();
   173 val lemma3 = result();
   174 
   174 
   175 goal thy "!!g. [| R <= A*B; g: C->R; ALL x:C. (lam z:R. fst(z))` (g`x) = x |] \
   175 goal thy "!!g. [| R <= A*B; g: C->R; ALL x:C. (lam z:R. fst(z))` (g`x) = x |] \
   176 \               ==> (lam x:C. snd(g`x)): (PROD x:C. R``{x})";
   176 \               ==> (lam x:C. snd(g`x)): (PROD x:C. R``{x})";
   177 by (rtac lam_type 1);
   177 by (rtac lam_type 1);
   178 by (dtac apply_type 1 THEN (assume_tac 1));
   178 by (dtac apply_type 1 THEN (assume_tac 1));
   179 by (dtac bspec 1 THEN (assume_tac 1));
   179 by (dtac bspec 1 THEN (assume_tac 1));
   180 by (rtac imageI 1);
   180 by (rtac imageI 1);
   181 by (resolve_tac [subsetD RS Pair_fst_snd_eq RSN (2, subst_elem)] 1
   181 by (resolve_tac [subsetD RS Pair_fst_snd_eq RSN (2, subst_elem)] 1
   182         THEN (REPEAT (assume_tac 1)));
   182         THEN (REPEAT (assume_tac 1)));
   183 by (asm_full_simp_tac AC_ss 1);
   183 by (Asm_full_simp_tac 1);
   184 val lemma4 = result();
   184 val lemma4 = result();
   185 
   185 
   186 goalw thy AC_defs "!!Z. AC5 ==> AC4";
   186 goalw thy AC_defs "!!Z. AC5 ==> AC4";
   187 by (REPEAT (resolve_tac [allI,impI] 1));
   187 by (REPEAT (resolve_tac [allI,impI] 1));
   188 by (REPEAT (eresolve_tac [allE,ballE] 1));
   188 by (REPEAT (eresolve_tac [allE,ballE] 1));
   189 by (eresolve_tac [lemma1 RSN (2, notE)] 2 THEN (assume_tac 2));
   189 by (eresolve_tac [lemma1 RSN (2, notE)] 2 THEN (assume_tac 2));
   190 by (dresolve_tac [lemma2 RSN (2, lemma3)] 1 THEN (assume_tac 1));
   190 by (dresolve_tac [lemma2 RSN (2, lemma3)] 1 THEN (assume_tac 1));
   191 by (fast_tac (AC_cs addSEs [lemma4]) 1);
   191 by (fast_tac (!claset addSEs [lemma4]) 1);
   192 qed "AC5_AC4";
   192 qed "AC5_AC4";
   193 
   193 
   194 
   194 
   195 (* ********************************************************************** *)
   195 (* ********************************************************************** *)
   196 (* AC1 <-> AC6                                                            *)
   196 (* AC1 <-> AC6                                                            *)
   197 (* ********************************************************************** *)
   197 (* ********************************************************************** *)
   198 
   198 
   199 goalw thy AC_defs "AC1 <-> AC6";
   199 goalw thy AC_defs "AC1 <-> AC6";
   200 by (fast_tac (ZF_cs addDs [equals0D] addSEs [not_emptyE]) 1);
   200 by (fast_tac (!claset addDs [equals0D] addSEs [not_emptyE]) 1);
   201 qed "AC1_iff_AC6";
   201 qed "AC1_iff_AC6";
   202 
   202