src/ZF/AC/Cardinal_aux.ML
changeset 3731 71366483323b
parent 2873 5f0599e15448
child 3840 e0baea4d485a
equal deleted inserted replaced
3730:6933d20f335f 3731:71366483323b
    31 by (rtac Card_cardinal 1);
    31 by (rtac Card_cardinal 1);
    32 by (resolve_tac [Card_nat RS (Card_def RS def_imp_iff RS iffD1 RS ssubst)] 1);
    32 by (resolve_tac [Card_nat RS (Card_def RS def_imp_iff RS iffD1 RS ssubst)] 1);
    33 by (resolve_tac [nat_le_infinite_Ord RS le_imp_lepoll
    33 by (resolve_tac [nat_le_infinite_Ord RS le_imp_lepoll
    34         RSN (2, well_ord_Memrel RS well_ord_lepoll_imp_Card_le)] 1 
    34         RSN (2, well_ord_Memrel RS well_ord_lepoll_imp_Card_le)] 1 
    35     THEN REPEAT (assume_tac 1));
    35     THEN REPEAT (assume_tac 1));
    36 val Inf_Ord_imp_InfCard_cardinal = result();
    36 qed "Inf_Ord_imp_InfCard_cardinal";
    37 
    37 
    38 val sum_lepoll_prod = [sum_eq_2_times RS equalityD1 RS subset_imp_lepoll,
    38 val sum_lepoll_prod = [sum_eq_2_times RS equalityD1 RS subset_imp_lepoll,
    39         asm_rl, lepoll_refl] MRS (prod_lepoll_mono RSN (2, lepoll_trans))
    39         asm_rl, lepoll_refl] MRS (prod_lepoll_mono RSN (2, lepoll_trans))
    40         |> standard;
    40         |> standard;
    41 
    41 
    42 goal thy "!!A. [| A lepoll B; 2 lepoll A |] ==> A+B lepoll A*B";
    42 goal thy "!!A. [| A lepoll B; 2 lepoll A |] ==> A+B lepoll A*B";
    43 by (REPEAT (ares_tac [[sum_lepoll_mono, sum_lepoll_prod]
    43 by (REPEAT (ares_tac [[sum_lepoll_mono, sum_lepoll_prod]
    44                 MRS lepoll_trans, lepoll_refl] 1));
    44                 MRS lepoll_trans, lepoll_refl] 1));
    45 val lepoll_imp_sum_lepoll_prod = result();
    45 qed "lepoll_imp_sum_lepoll_prod";
    46 
    46 
    47 goal thy "!!A. [| A eqpoll i; B eqpoll i; ~Finite(i); Ord(i) |]  \
    47 goal thy "!!A. [| A eqpoll i; B eqpoll i; ~Finite(i); Ord(i) |]  \
    48 \               ==> A Un B eqpoll i";
    48 \               ==> A Un B eqpoll i";
    49 by (rtac eqpollI 1);
    49 by (rtac eqpollI 1);
    50 by (eresolve_tac [subset_imp_lepoll RSN (2, eqpoll_sym RS eqpoll_imp_lepoll
    50 by (eresolve_tac [subset_imp_lepoll RSN (2, eqpoll_sym RS eqpoll_imp_lepoll
    61 by (eresolve_tac [prod_eqpoll_cong RS eqpoll_imp_lepoll RS lepoll_trans] 1 
    61 by (eresolve_tac [prod_eqpoll_cong RS eqpoll_imp_lepoll RS lepoll_trans] 1 
    62     THEN (assume_tac 1));
    62     THEN (assume_tac 1));
    63 by (resolve_tac [Inf_Ord_imp_InfCard_cardinal RSN (2, well_ord_Memrel RS 
    63 by (resolve_tac [Inf_Ord_imp_InfCard_cardinal RSN (2, well_ord_Memrel RS 
    64         well_ord_InfCard_square_eq) RS eqpoll_imp_lepoll] 1 
    64         well_ord_InfCard_square_eq) RS eqpoll_imp_lepoll] 1 
    65     THEN REPEAT (assume_tac 1));
    65     THEN REPEAT (assume_tac 1));
    66 val Un_eqpoll_Inf_Ord = result();
    66 qed "Un_eqpoll_Inf_Ord";
    67 
    67 
    68 val ss = (!simpset) addsimps [inj_is_fun RS apply_type, left_inverse] 
    68 val ss = (!simpset) addsimps [inj_is_fun RS apply_type, left_inverse] 
    69                setloop (split_tac [expand_if] ORELSE' etac UnE);
    69                setloop (split_tac [expand_if] ORELSE' etac UnE);
    70 
    70 
    71 goal ZF.thy "{x, y} - {y} = {x} - {y}";
    71 goal ZF.thy "{x, y} - {y} = {x} - {y}";
    72 by (Fast_tac 1);
    72 by (Fast_tac 1);
    73 val double_Diff_sing = result();
    73 qed "double_Diff_sing";
    74 
    74 
    75 goal ZF.thy "if({y,z}-{z}=0, z, THE w. {y,z}-{z}={w}) = y";
    75 goal ZF.thy "if({y,z}-{z}=0, z, THE w. {y,z}-{z}={w}) = y";
    76 by (split_tac [expand_if] 1);
    76 by (split_tac [expand_if] 1);
    77 by (asm_full_simp_tac (!simpset addsimps [double_Diff_sing, Diff_eq_0_iff]) 1);
    77 by (asm_full_simp_tac (!simpset addsimps [double_Diff_sing, Diff_eq_0_iff]) 1);
    78 by (fast_tac (!claset addSIs [the_equality] addEs [equalityE]) 1);
    78 by (fast_tac (!claset addSIs [the_equality] addEs [equalityE]) 1);
    79 val paired_bij_lemma = result();
    79 qed "paired_bij_lemma";
    80 
    80 
    81 goal thy "(lam y:{{y,z}. y:x}. if(y-{z}=0, z, THE w. y-{z}={w}))  \
    81 goal thy "(lam y:{{y,z}. y:x}. if(y-{z}=0, z, THE w. y-{z}={w}))  \
    82 \               : bij({{y,z}. y:x}, x)";
    82 \               : bij({{y,z}. y:x}, x)";
    83 by (res_inst_tac [("d","%a. {a,z}")] lam_bijective 1);
    83 by (res_inst_tac [("d","%a. {a,z}")] lam_bijective 1);
    84 by (TRYALL (fast_tac (!claset addSEs [RepFunE] addSIs [RepFunI] 
    84 by (TRYALL (fast_tac (!claset addSEs [RepFunE] addSIs [RepFunI] 
    85                 addss (!simpset addsimps [paired_bij_lemma]))));
    85                 addss (!simpset addsimps [paired_bij_lemma]))));
    86 val paired_bij = result();
    86 qed "paired_bij";
    87 
    87 
    88 goalw thy [eqpoll_def] "{{y,z}. y:x} eqpoll x";
    88 goalw thy [eqpoll_def] "{{y,z}. y:x} eqpoll x";
    89 by (fast_tac (!claset addSIs [paired_bij]) 1);
    89 by (fast_tac (!claset addSIs [paired_bij]) 1);
    90 val paired_eqpoll = result();
    90 qed "paired_eqpoll";
    91 
    91 
    92 goal thy "!!A. EX B. B eqpoll A & B Int C = 0";
    92 goal thy "!!A. EX B. B eqpoll A & B Int C = 0";
    93 by (fast_tac (!claset addSIs [paired_eqpoll, equals0I] addEs [mem_asym]) 1);
    93 by (fast_tac (!claset addSIs [paired_eqpoll, equals0I] addEs [mem_asym]) 1);
    94 val ex_eqpoll_disjoint = result();
    94 qed "ex_eqpoll_disjoint";
    95 
    95 
    96 goal thy "!!A. [| A lepoll i; B lepoll i; ~Finite(i); Ord(i) |]  \
    96 goal thy "!!A. [| A lepoll i; B lepoll i; ~Finite(i); Ord(i) |]  \
    97 \               ==> A Un B lepoll i";
    97 \               ==> A Un B lepoll i";
    98 by (res_inst_tac [("A1","i"), ("C1","i")] (ex_eqpoll_disjoint RS exE) 1);
    98 by (res_inst_tac [("A1","i"), ("C1","i")] (ex_eqpoll_disjoint RS exE) 1);
    99 by (etac conjE 1);
    99 by (etac conjE 1);
   101 by (assume_tac 1);
   101 by (assume_tac 1);
   102 by (resolve_tac [Un_lepoll_Un RS lepoll_trans] 1 THEN (REPEAT (assume_tac 1)));
   102 by (resolve_tac [Un_lepoll_Un RS lepoll_trans] 1 THEN (REPEAT (assume_tac 1)));
   103 by (eresolve_tac [eqpoll_refl RSN (2, Un_eqpoll_Inf_Ord) RS
   103 by (eresolve_tac [eqpoll_refl RSN (2, Un_eqpoll_Inf_Ord) RS
   104         eqpoll_imp_lepoll] 1
   104         eqpoll_imp_lepoll] 1
   105         THEN (REPEAT (assume_tac 1)));
   105         THEN (REPEAT (assume_tac 1)));
   106 val Un_lepoll_Inf_Ord = result();
   106 qed "Un_lepoll_Inf_Ord";
   107 
   107 
   108 goal thy "!!P. [| P(i); i:j; Ord(j) |] ==> (LEAST i. P(i)) : j";
   108 goal thy "!!P. [| P(i); i:j; Ord(j) |] ==> (LEAST i. P(i)) : j";
   109 by (eresolve_tac [Least_le RS leE] 1);
   109 by (eresolve_tac [Least_le RS leE] 1);
   110 by (etac Ord_in_Ord 1 THEN (assume_tac 1));
   110 by (etac Ord_in_Ord 1 THEN (assume_tac 1));
   111 by (etac ltE 1);
   111 by (etac ltE 1);
   112 by (fast_tac (!claset addDs [OrdmemD]) 1);
   112 by (fast_tac (!claset addDs [OrdmemD]) 1);
   113 by (etac subst_elem 1 THEN (assume_tac 1));
   113 by (etac subst_elem 1 THEN (assume_tac 1));
   114 val Least_in_Ord = result();
   114 qed "Least_in_Ord";
   115 
   115 
   116 goal thy "!!x. [| well_ord(x,r); y<=x; y lepoll succ(n); n:nat |]  \
   116 goal thy "!!x. [| well_ord(x,r); y<=x; y lepoll succ(n); n:nat |]  \
   117 \       ==> y-{THE b. first(b,y,r)} lepoll n";
   117 \       ==> y-{THE b. first(b,y,r)} lepoll n";
   118 by (res_inst_tac [("Q","y=0")] (excluded_middle RS disjE) 1);
   118 by (res_inst_tac [("Q","y=0")] (excluded_middle RS disjE) 1);
   119 by (fast_tac (!claset addSIs [Diff_sing_lepoll, the_first_in]) 1);
   119 by (fast_tac (!claset addSIs [Diff_sing_lepoll, the_first_in]) 1);
   120 by (res_inst_tac [("b","y-{THE b. first(b, y, r)}")] subst 1);
   120 by (res_inst_tac [("b","y-{THE b. first(b, y, r)}")] subst 1);
   121 by (rtac empty_lepollI 2);
   121 by (rtac empty_lepollI 2);
   122 by (Fast_tac 1);
   122 by (Fast_tac 1);
   123 val Diff_first_lepoll = result();
   123 qed "Diff_first_lepoll";
   124 
   124 
   125 goal thy "(UN x:X. P(x)) <= (UN x:X. P(x)-Q(x)) Un (UN x:X. Q(x))";
   125 goal thy "(UN x:X. P(x)) <= (UN x:X. P(x)-Q(x)) Un (UN x:X. Q(x))";
   126 by (Fast_tac 1);
   126 by (Fast_tac 1);
   127 val UN_subset_split = result();
   127 qed "UN_subset_split";
   128 
   128 
   129 goalw thy [lepoll_def] "!!a. Ord(a) ==> (UN x:a. {P(x)}) lepoll a";
   129 goalw thy [lepoll_def] "!!a. Ord(a) ==> (UN x:a. {P(x)}) lepoll a";
   130 by (res_inst_tac [("x","lam z:(UN x:a. {P(x)}). (LEAST i. P(i)=z)")] exI 1);
   130 by (res_inst_tac [("x","lam z:(UN x:a. {P(x)}). (LEAST i. P(i)=z)")] exI 1);
   131 by (res_inst_tac [("d","%z. P(z)")] lam_injective 1);
   131 by (res_inst_tac [("d","%z. P(z)")] lam_injective 1);
   132 by (fast_tac (!claset addSIs [Least_in_Ord]) 1);
   132 by (fast_tac (!claset addSIs [Least_in_Ord]) 1);
   133 by (fast_tac (!claset addIs [LeastI] addSEs [Ord_in_Ord]) 1);
   133 by (fast_tac (!claset addIs [LeastI] addSEs [Ord_in_Ord]) 1);
   134 val UN_sing_lepoll = result();
   134 qed "UN_sing_lepoll";
   135 
   135 
   136 goal thy "!!a T. [| well_ord(T, R); ~Finite(a); Ord(a); n:nat |] ==>  \
   136 goal thy "!!a T. [| well_ord(T, R); ~Finite(a); Ord(a); n:nat |] ==>  \
   137 \       ALL f. (ALL b:a. f`b lepoll n & f`b <= T) --> (UN b:a. f`b) lepoll a";
   137 \       ALL f. (ALL b:a. f`b lepoll n & f`b <= T) --> (UN b:a. f`b) lepoll a";
   138 by (etac nat_induct 1);
   138 by (etac nat_induct 1);
   139 by (rtac allI 1);
   139 by (rtac allI 1);
   151 by (fast_tac (!claset addSIs [Diff_first_lepoll]) 1);
   151 by (fast_tac (!claset addSIs [Diff_first_lepoll]) 1);
   152 by (Asm_full_simp_tac 1);
   152 by (Asm_full_simp_tac 1);
   153 by (resolve_tac [UN_subset_split RS subset_imp_lepoll RS lepoll_trans] 1);
   153 by (resolve_tac [UN_subset_split RS subset_imp_lepoll RS lepoll_trans] 1);
   154 by (rtac Un_lepoll_Inf_Ord 1 THEN (REPEAT_FIRST assume_tac));
   154 by (rtac Un_lepoll_Inf_Ord 1 THEN (REPEAT_FIRST assume_tac));
   155 by (etac UN_sing_lepoll 1);
   155 by (etac UN_sing_lepoll 1);
   156 val UN_fun_lepoll_lemma = result();
   156 qed "UN_fun_lepoll_lemma";
   157 
   157 
   158 goal thy "!!a f. [| ALL b:a. f`b lepoll n & f`b <= T; well_ord(T, R);  \
   158 goal thy "!!a f. [| ALL b:a. f`b lepoll n & f`b <= T; well_ord(T, R);  \
   159 \       ~Finite(a); Ord(a); n:nat |] ==> (UN b:a. f`b) lepoll a";
   159 \       ~Finite(a); Ord(a); n:nat |] ==> (UN b:a. f`b) lepoll a";
   160 by (eresolve_tac [UN_fun_lepoll_lemma RS allE] 1 THEN (REPEAT (assume_tac 1)));
   160 by (eresolve_tac [UN_fun_lepoll_lemma RS allE] 1 THEN (REPEAT (assume_tac 1)));
   161 by (Fast_tac 1);
   161 by (Fast_tac 1);
   162 val UN_fun_lepoll = result();
   162 qed "UN_fun_lepoll";
   163 
   163 
   164 goal thy "!!a f. [| ALL b:a. F(b) lepoll n & F(b) <= T; well_ord(T, R);  \
   164 goal thy "!!a f. [| ALL b:a. F(b) lepoll n & F(b) <= T; well_ord(T, R);  \
   165 \       ~Finite(a); Ord(a); n:nat |] ==> (UN b:a. F(b)) lepoll a";
   165 \       ~Finite(a); Ord(a); n:nat |] ==> (UN b:a. F(b)) lepoll a";
   166 by (rtac impE 1 THEN (assume_tac 3));
   166 by (rtac impE 1 THEN (assume_tac 3));
   167 by (res_inst_tac [("f","lam b:a. F(b)")] (UN_fun_lepoll) 2 
   167 by (res_inst_tac [("f","lam b:a. F(b)")] (UN_fun_lepoll) 2 
   168         THEN (TRYALL assume_tac));
   168         THEN (TRYALL assume_tac));
   169 by (Simp_tac 2);
   169 by (Simp_tac 2);
   170 by (Asm_full_simp_tac 1);
   170 by (Asm_full_simp_tac 1);
   171 val UN_lepoll = result();
   171 qed "UN_lepoll";
   172 
   172 
   173 goal thy "!!a. Ord(a) ==> (UN b:a. F(b)) = (UN b:a. F(b) - (UN c:b. F(c)))";
   173 goal thy "!!a. Ord(a) ==> (UN b:a. F(b)) = (UN b:a. F(b) - (UN c:b. F(c)))";
   174 by (rtac equalityI 1);
   174 by (rtac equalityI 1);
   175 by (Fast_tac 2);
   175 by (Fast_tac 2);
   176 by (rtac subsetI 1);
   176 by (rtac subsetI 1);
   181 by (resolve_tac [Ord_in_Ord RSN (2, LeastI)] 1 THEN (REPEAT (assume_tac 1)));
   181 by (resolve_tac [Ord_in_Ord RSN (2, LeastI)] 1 THEN (REPEAT (assume_tac 1)));
   182 by (rtac notI 1);
   182 by (rtac notI 1);
   183 by (etac UN_E 1);
   183 by (etac UN_E 1);
   184 by (eres_inst_tac [("P","%z. x:F(z)"),("i","c")] less_LeastE 1);
   184 by (eres_inst_tac [("P","%z. x:F(z)"),("i","c")] less_LeastE 1);
   185 by (eresolve_tac [Ord_Least RSN (2, ltI)] 1);
   185 by (eresolve_tac [Ord_Least RSN (2, ltI)] 1);
   186 val UN_eq_UN_Diffs = result();
   186 qed "UN_eq_UN_Diffs";
   187 
   187 
   188 goalw thy [eqpoll_def] "!!A B. A Int B = 0 ==> A Un B eqpoll A + B";
   188 goalw thy [eqpoll_def] "!!A B. A Int B = 0 ==> A Un B eqpoll A + B";
   189 by (res_inst_tac [("x","lam a:A Un B. if(a:A,Inl(a),Inr(a))")] exI 1);
   189 by (res_inst_tac [("x","lam a:A Un B. if(a:A,Inl(a),Inr(a))")] exI 1);
   190 by (res_inst_tac [("d","%z. case(%x.x, %x.x, z)")] lam_bijective 1);
   190 by (res_inst_tac [("d","%z. case(%x.x, %x.x, z)")] lam_bijective 1);
   191 by (fast_tac (!claset addSIs [if_type, InlI, InrI]) 1);
   191 by (fast_tac (!claset addSIs [if_type, InlI, InrI]) 1);
   192 by (TRYALL (etac sumE ));
   192 by (TRYALL (etac sumE ));
   193 by (TRYALL (split_tac [expand_if]));
   193 by (TRYALL (split_tac [expand_if]));
   194 by (TRYALL Asm_simp_tac);
   194 by (TRYALL Asm_simp_tac);
   195 by (fast_tac (!claset addDs [equals0D]) 1);
   195 by (fast_tac (!claset addDs [equals0D]) 1);
   196 val disj_Un_eqpoll_sum = result();
   196 qed "disj_Un_eqpoll_sum";
   197 
   197 
   198 goalw thy [lepoll_def, eqpoll_def]
   198 goalw thy [lepoll_def, eqpoll_def]
   199         "!!X a. a lepoll X ==> EX Y. Y<=X & a eqpoll Y";
   199         "!!X a. a lepoll X ==> EX Y. Y<=X & a eqpoll Y";
   200 by (etac exE 1);
   200 by (etac exE 1);
   201 by (forward_tac [subset_refl RSN (2, restrict_bij)] 1);
   201 by (forward_tac [subset_refl RSN (2, restrict_bij)] 1);
   202 by (res_inst_tac [("x","f``a")] exI 1);
   202 by (res_inst_tac [("x","f``a")] exI 1);
   203 by (fast_tac (!claset addSEs [inj_is_fun RS fun_is_rel RS image_subset]) 1);
   203 by (fast_tac (!claset addSEs [inj_is_fun RS fun_is_rel RS image_subset]) 1);
   204 val lepoll_imp_eqpoll_subset = result();
   204 qed "lepoll_imp_eqpoll_subset";
   205 
   205 
   206 (* ********************************************************************** *)
   206 (* ********************************************************************** *)
   207 (* Diff_lesspoll_eqpoll_Card                                              *)
   207 (* Diff_lesspoll_eqpoll_Card                                              *)
   208 (* ********************************************************************** *)
   208 (* ********************************************************************** *)
   209 
   209 
   233 by (fast_tac (!claset addSEs [ltE, Ord_in_Ord]) 1);
   233 by (fast_tac (!claset addSEs [ltE, Ord_in_Ord]) 1);
   234 by (dresolve_tac [subset_Un_Diff RS subset_imp_lepoll RS lepoll_trans RSN
   234 by (dresolve_tac [subset_Un_Diff RS subset_imp_lepoll RS lepoll_trans RSN
   235         (3, lt_Card_imp_lesspoll RS lepoll_lesspoll_lesspoll)] 1
   235         (3, lt_Card_imp_lesspoll RS lepoll_lesspoll_lesspoll)] 1
   236         THEN (TRYALL assume_tac));
   236         THEN (TRYALL assume_tac));
   237 by (fast_tac (!claset addSDs [lesspoll_def RS def_imp_iff RS iffD1]) 1);
   237 by (fast_tac (!claset addSDs [lesspoll_def RS def_imp_iff RS iffD1]) 1);
   238 val Diff_lesspoll_eqpoll_Card_lemma = result();
   238 qed "Diff_lesspoll_eqpoll_Card_lemma";
   239 
   239 
   240 goal thy "!!A. [| A eqpoll a; ~Finite(a); Card(a); B lesspoll a |]  \
   240 goal thy "!!A. [| A eqpoll a; ~Finite(a); Card(a); B lesspoll a |]  \
   241 \       ==> A - B eqpoll a";
   241 \       ==> A - B eqpoll a";
   242 by (rtac swap 1 THEN (Fast_tac 1));
   242 by (rtac swap 1 THEN (Fast_tac 1));
   243 by (rtac Diff_lesspoll_eqpoll_Card_lemma 1 THEN (REPEAT (assume_tac 1)));
   243 by (rtac Diff_lesspoll_eqpoll_Card_lemma 1 THEN (REPEAT (assume_tac 1)));
   244 by (fast_tac (!claset addSIs [lesspoll_def RS def_imp_iff RS iffD2,
   244 by (fast_tac (!claset addSIs [lesspoll_def RS def_imp_iff RS iffD2,
   245         subset_imp_lepoll RS (eqpoll_imp_lepoll RSN (2, lepoll_trans))]) 1);
   245         subset_imp_lepoll RS (eqpoll_imp_lepoll RSN (2, lepoll_trans))]) 1);
   246 val Diff_lesspoll_eqpoll_Card = result();
   246 qed "Diff_lesspoll_eqpoll_Card";
   247 
   247