src/ZF/AC/AC7_AC9.ML
changeset 1196 d43c1f7a53fe
parent 1123 5dfdc1464966
child 1207 3f460842e919
equal deleted inserted replaced
1195:686e3eb613b9 1196:d43c1f7a53fe
    25 val Sigma_fun_space_not0 = result();
    25 val Sigma_fun_space_not0 = result();
    26 
    26 
    27 goal thy "!!A C. (ALL B:A. B eqpoll C) ==> (ALL B1:A. ALL B2:A. B1 eqpoll B2)";
    27 goal thy "!!A C. (ALL B:A. B eqpoll C) ==> (ALL B1:A. ALL B2:A. B1 eqpoll B2)";
    28 by (REPEAT (resolve_tac [ballI] 1));
    28 by (REPEAT (resolve_tac [ballI] 1));
    29 by (resolve_tac [bspec RS (bspec RSN (2, eqpoll_sym RSN (2, eqpoll_trans)))] 1
    29 by (resolve_tac [bspec RS (bspec RSN (2, eqpoll_sym RSN (2, eqpoll_trans)))] 1
    30 	THEN REPEAT (atac 1));
    30 	THEN REPEAT (assume_tac 1));
    31 val all_eqpoll_imp_pair_eqpoll = result();
    31 val all_eqpoll_imp_pair_eqpoll = result();
    32 
    32 
    33 goal thy "!!A. [| ALL a:A. if(a=b, P(a), Q(a)) = if(a=b, R(a), S(a)); b:A   \
    33 goal thy "!!A. [| ALL a:A. if(a=b, P(a), Q(a)) = if(a=b, R(a), S(a)); b:A   \
    34 \	|] ==> P(b)=R(b)";
    34 \	|] ==> P(b)=R(b)";
    35 by (dresolve_tac [bspec] 1 THEN (atac 1));
    35 by (dresolve_tac [bspec] 1 THEN (assume_tac 1));
    36 by (asm_full_simp_tac ZF_ss 1);
    36 by (asm_full_simp_tac ZF_ss 1);
    37 val if_eqE1 = result();
    37 val if_eqE1 = result();
    38 
    38 
    39 goal thy "!!A. ALL a:A. if(a=b, P(a), Q(a)) = if(a=b, R(a), S(a))  \
    39 goal thy "!!A. ALL a:A. if(a=b, P(a), Q(a)) = if(a=b, R(a), S(a))  \
    40 \	==> ALL a:A. a~=b --> Q(a)=S(a)";
    40 \	==> ALL a:A. a~=b --> Q(a)=S(a)";
    41 by (resolve_tac [ballI] 1);
    41 by (resolve_tac [ballI] 1);
    42 by (resolve_tac [impI] 1);
    42 by (resolve_tac [impI] 1);
    43 by (dresolve_tac [bspec] 1 THEN (atac 1));
    43 by (dresolve_tac [bspec] 1 THEN (assume_tac 1));
    44 by (asm_full_simp_tac ZF_ss 1);
    44 by (asm_full_simp_tac ZF_ss 1);
    45 val if_eqE2 = result();
    45 val if_eqE2 = result();
    46 
    46 
    47 goal thy "!!A. [| (lam x:A. f(x))=(lam x:A. g(x)); a:A |] ==> f(a)=g(a)";
    47 goal thy "!!A. [| (lam x:A. f(x))=(lam x:A. g(x)); a:A |] ==> f(a)=g(a)";
    48 by (fast_tac (ZF_cs addDs [subsetD]
    48 by (fast_tac (ZF_cs addDs [subsetD]
    63 by (REPEAT (hyp_subst_tac 1));
    63 by (REPEAT (hyp_subst_tac 1));
    64 by (asm_full_simp_tac ZF_ss 1);
    64 by (asm_full_simp_tac ZF_ss 1);
    65 by (resolve_tac [conjI] 1);
    65 by (resolve_tac [conjI] 1);
    66 by (dresolve_tac [nat_0I RSN (2, lam_eqE)] 2);
    66 by (dresolve_tac [nat_0I RSN (2, lam_eqE)] 2);
    67 by (asm_full_simp_tac AC_ss 2);
    67 by (asm_full_simp_tac AC_ss 2);
    68 by (resolve_tac [fun_extension] 1 THEN  REPEAT (atac 1));
    68 by (resolve_tac [fun_extension] 1 THEN  REPEAT (assume_tac 1));
    69 by (dresolve_tac [nat_succI RSN (2, lam_eqE)] 1 THEN (atac 1));
    69 by (dresolve_tac [nat_succI RSN (2, lam_eqE)] 1 THEN (assume_tac 1));
    70 by (asm_full_simp_tac (AC_ss addsimps [succ_not_0 RS if_not_P]) 1);
    70 by (asm_full_simp_tac (AC_ss addsimps [succ_not_0 RS if_not_P]) 1);
    71 by (fast_tac (AC_cs addSEs [diff_succ_succ RS (diff_0 RSN (2, trans)) RS subst]
    71 by (fast_tac (AC_cs addSEs [diff_succ_succ RS (diff_0 RSN (2, trans)) RS subst]
    72 		addSIs [nat_0I]) 1);
    72 		addSIs [nat_0I]) 1);
    73 val lemma = result();
    73 val lemma = result();
    74 
    74 
    85 (* AC6 ==> AC7								  *)
    85 (* AC6 ==> AC7								  *)
    86 (* ********************************************************************** *)
    86 (* ********************************************************************** *)
    87 
    87 
    88 goalw thy AC_defs "!!Z. AC6 ==> AC7";
    88 goalw thy AC_defs "!!Z. AC6 ==> AC7";
    89 by (fast_tac ZF_cs 1);
    89 by (fast_tac ZF_cs 1);
    90 result();
    90 qed "AC6_AC7";
    91 
    91 
    92 (* ********************************************************************** *)
    92 (* ********************************************************************** *)
    93 (* AC7 ==> AC6, Rubin & Rubin p. 12, Theorem 2.8			  *)
    93 (* AC7 ==> AC6, Rubin & Rubin p. 12, Theorem 2.8			  *)
    94 (* The case of the empty family of sets added in order to complete	  *)
    94 (* The case of the empty family of sets added in order to complete	  *)
    95 (* the proof.								  *)
    95 (* the proof.								  *)
   120 by (resolve_tac [impI] 1);
   120 by (resolve_tac [impI] 1);
   121 by (excluded_middle_tac "A=0" 1);
   121 by (excluded_middle_tac "A=0" 1);
   122 by (fast_tac (ZF_cs addSIs [not_emptyI, empty_fun]) 2);
   122 by (fast_tac (ZF_cs addSIs [not_emptyI, empty_fun]) 2);
   123 by (resolve_tac [lemma1] 1);
   123 by (resolve_tac [lemma1] 1);
   124 by (eresolve_tac [allE] 1);
   124 by (eresolve_tac [allE] 1);
   125 by (eresolve_tac [impE] 1 THEN (atac 2));
   125 by (eresolve_tac [impE] 1 THEN (assume_tac 2));
   126 by (fast_tac (AC_cs addSEs [RepFunE]
   126 by (fast_tac (AC_cs addSEs [RepFunE]
   127 	addSIs [lemma2, all_eqpoll_imp_pair_eqpoll,
   127 	addSIs [lemma2, all_eqpoll_imp_pair_eqpoll,
   128 		Sigma_fun_space_eqpoll]) 1);
   128 		Sigma_fun_space_eqpoll]) 1);
   129 result();
   129 qed "AC7_AC6";
   130 
   130 
   131 
   131 
   132 (* ********************************************************************** *)
   132 (* ********************************************************************** *)
   133 (* AC1 ==> AC8								  *)
   133 (* AC1 ==> AC8								  *)
   134 (* ********************************************************************** *)
   134 (* ********************************************************************** *)
   136 goalw thy [eqpoll_def]
   136 goalw thy [eqpoll_def]
   137 	"!!A. ALL B:A. EX B1 B2. B=<B1,B2> & B1 eqpoll B2  \
   137 	"!!A. ALL B:A. EX B1 B2. B=<B1,B2> & B1 eqpoll B2  \
   138 \	==> 0 ~: { bij(fst(B),snd(B)). B:A }";
   138 \	==> 0 ~: { bij(fst(B),snd(B)). B:A }";
   139 by (resolve_tac [notI] 1);
   139 by (resolve_tac [notI] 1);
   140 by (eresolve_tac [RepFunE] 1);
   140 by (eresolve_tac [RepFunE] 1);
   141 by (dresolve_tac [bspec] 1 THEN (atac 1));
   141 by (dresolve_tac [bspec] 1 THEN (assume_tac 1));
   142 by (REPEAT (eresolve_tac [exE,conjE] 1));
   142 by (REPEAT (eresolve_tac [exE,conjE] 1));
   143 by (hyp_subst_tac 1);
   143 by (hyp_subst_tac 1);
   144 by (asm_full_simp_tac AC_ss 1);
   144 by (asm_full_simp_tac AC_ss 1);
   145 by (fast_tac (AC_cs addSEs [sym RS equals0D]) 1);
   145 by (fast_tac (AC_cs addSEs [sym RS equals0D]) 1);
   146 val lemma1 = result();
   146 val lemma1 = result();
   147 
   147 
   148 goal thy "!!A. [| f: (PROD X:RepFun(A,p). X); D:A |]  \
   148 goal thy "!!A. [| f: (PROD X:RepFun(A,p). X); D:A |]  \
   149 \		==> (lam x:A. f`p(x))`D : p(D)";
   149 \		==> (lam x:A. f`p(x))`D : p(D)";
   150 by (resolve_tac [beta RS ssubst] 1 THEN (atac 1));
   150 by (resolve_tac [beta RS ssubst] 1 THEN (assume_tac 1));
   151 by (fast_tac (AC_cs addSEs [apply_type]) 1);
   151 by (fast_tac (AC_cs addSEs [apply_type]) 1);
   152 val lemma2 = result();
   152 val lemma2 = result();
   153 
   153 
   154 goalw thy AC_defs "!!Z. AC1 ==> AC8";
   154 goalw thy AC_defs "!!Z. AC1 ==> AC8";
   155 by (resolve_tac [allI] 1);
   155 by (resolve_tac [allI] 1);
   156 by (eresolve_tac [allE] 1);
   156 by (eresolve_tac [allE] 1);
   157 by (resolve_tac [impI] 1);
   157 by (resolve_tac [impI] 1);
   158 by (eresolve_tac [impE] 1);
   158 by (eresolve_tac [impE] 1);
   159 by (eresolve_tac [lemma1] 1);
   159 by (eresolve_tac [lemma1] 1);
   160 by (fast_tac (AC_cs addSEs [lemma2]) 1);
   160 by (fast_tac (AC_cs addSEs [lemma2]) 1);
   161 result();
   161 qed "AC1_AC8";
   162 
   162 
   163 
   163 
   164 (* ********************************************************************** *)
   164 (* ********************************************************************** *)
   165 (* AC8 ==> AC9								  *)
   165 (* AC8 ==> AC9								  *)
   166 (*  - this proof replaces the following two from Rubin & Rubin:		  *)
   166 (*  - this proof replaces the following two from Rubin & Rubin:		  *)
   181 by (resolve_tac [impI] 1);
   181 by (resolve_tac [impI] 1);
   182 by (eresolve_tac [allE] 1);
   182 by (eresolve_tac [allE] 1);
   183 by (eresolve_tac [impE] 1);
   183 by (eresolve_tac [impE] 1);
   184 by (eresolve_tac [lemma1] 1);
   184 by (eresolve_tac [lemma1] 1);
   185 by (fast_tac (AC_cs addSEs [lemma2]) 1);
   185 by (fast_tac (AC_cs addSEs [lemma2]) 1);
   186 result();
   186 qed "AC8_AC9";
   187 
   187 
   188 
   188 
   189 (* ********************************************************************** *)
   189 (* ********************************************************************** *)
   190 (* AC9 ==> AC1								  *)
   190 (* AC9 ==> AC1								  *)
   191 (* The idea of this proof comes from "Equivalents of the Axiom of Choice" *)
   191 (* The idea of this proof comes from "Equivalents of the Axiom of Choice" *)
   223 by (resolve_tac [fst_type] 1);
   223 by (resolve_tac [fst_type] 1);
   224 by (resolve_tac [consI1 RSN (2, apply_type)] 1);
   224 by (resolve_tac [consI1 RSN (2, apply_type)] 1);
   225 by (fast_tac (ZF_cs addSIs [fun_weaken_type, bij_is_fun]) 1);
   225 by (fast_tac (ZF_cs addSIs [fun_weaken_type, bij_is_fun]) 1);
   226 val lemma2 = result();
   226 val lemma2 = result();
   227 
   227 
   228 val prems = goalw thy AC_defs "!!Z. AC9 ==> AC1";
   228 goalw thy AC_defs "!!Z. AC9 ==> AC1";
   229 by (resolve_tac [allI] 1);
   229 by (resolve_tac [allI] 1);
   230 by (resolve_tac [impI] 1);
   230 by (resolve_tac [impI] 1);
   231 by (eresolve_tac [allE] 1);
   231 by (eresolve_tac [allE] 1);
   232 by (excluded_middle_tac "A=0" 1);
   232 by (excluded_middle_tac "A=0" 1);
   233 by (fast_tac (FOL_cs addSIs [empty_fun]) 2);
   233 by (fast_tac (FOL_cs addSIs [empty_fun]) 2);
   234 by (eresolve_tac [impE] 1);
   234 by (eresolve_tac [impE] 1);
   235 by (resolve_tac [lemma1] 1 THEN (REPEAT (atac 1)));
   235 by (resolve_tac [lemma1] 1 THEN (REPEAT (assume_tac 1)));
   236 by (fast_tac (AC_cs addSEs [lemma2]) 1);
   236 by (fast_tac (AC_cs addSEs [lemma2]) 1);
   237 result();
   237 qed "AC9_AC1";