src/ZF/Finite.ML
changeset 2469 b50b8c0eec01
parent 2033 639de962ded4
child 4091 771b1f6422a8
equal deleted inserted replaced
2468:428efffe8599 2469:b50b8c0eec01
    36 by (etac (cons_absorb RS ssubst) 3 THEN assume_tac 3);      (*backtracking!*)
    36 by (etac (cons_absorb RS ssubst) 3 THEN assume_tac 3);      (*backtracking!*)
    37 by (REPEAT (ares_tac prems 1));
    37 by (REPEAT (ares_tac prems 1));
    38 qed "Fin_induct";
    38 qed "Fin_induct";
    39 
    39 
    40 (** Simplification for Fin **)
    40 (** Simplification for Fin **)
    41 val Fin_ss = arith_ss addsimps Fin.intrs;
    41 Addsimps Fin.intrs;
    42 
    42 
    43 (*The union of two finite sets is finite.*)
    43 (*The union of two finite sets is finite.*)
    44 val major::prems = goal Finite.thy
    44 goal Finite.thy
    45     "[| b: Fin(A);  c: Fin(A) |] ==> b Un c : Fin(A)";
    45     "!!b c. [| b: Fin(A);  c: Fin(A) |] ==> b Un c : Fin(A)";
    46 by (rtac (major RS Fin_induct) 1);
    46 by (etac Fin_induct 1);
    47 by (ALLGOALS (asm_simp_tac (Fin_ss addsimps (prems@[Un_0, Un_cons]))));
    47 by (ALLGOALS (asm_simp_tac (!simpset addsimps [Un_cons])));
    48 qed "Fin_UnI";
    48 qed "Fin_UnI";
       
    49 
       
    50 Addsimps [Fin_UnI];
    49 
    51 
    50 (*The union of a set of finite sets is finite.*)
    52 (*The union of a set of finite sets is finite.*)
    51 val [major] = goal Finite.thy "C : Fin(Fin(A)) ==> Union(C) : Fin(A)";
    53 val [major] = goal Finite.thy "C : Fin(Fin(A)) ==> Union(C) : Fin(A)";
    52 by (rtac (major RS Fin_induct) 1);
    54 by (rtac (major RS Fin_induct) 1);
    53 by (ALLGOALS (asm_simp_tac (Fin_ss addsimps [Union_0, Union_cons, Fin_UnI])));
    55 by (ALLGOALS Asm_simp_tac);
    54 qed "Fin_UnionI";
    56 qed "Fin_UnionI";
    55 
    57 
    56 (*Every subset of a finite set is finite.*)
    58 (*Every subset of a finite set is finite.*)
    57 goal Finite.thy "!!b A. b: Fin(A) ==> ALL z. z<=b --> z: Fin(A)";
    59 goal Finite.thy "!!b A. b: Fin(A) ==> ALL z. z<=b --> z: Fin(A)";
    58 by (etac Fin_induct 1);
    60 by (etac Fin_induct 1);
    59 by (simp_tac (Fin_ss addsimps [subset_empty_iff]) 1);
    61 by (simp_tac (!simpset addsimps [subset_empty_iff]) 1);
    60 by (asm_simp_tac (ZF_ss addsimps subset_cons_iff::distrib_simps) 1);
    62 by (asm_simp_tac (!simpset addsimps subset_cons_iff::distrib_simps) 1);
    61 by (safe_tac ZF_cs);
    63 by (safe_tac (!claset));
    62 by (eres_inst_tac [("b","z")] (cons_Diff RS subst) 1);
    64 by (eres_inst_tac [("b","z")] (cons_Diff RS subst) 1);
    63 by (asm_simp_tac Fin_ss 1);
    65 by (Asm_simp_tac 1);
    64 qed "Fin_subset_lemma";
    66 qed "Fin_subset_lemma";
    65 
    67 
    66 goal Finite.thy "!!c b A. [| c<=b;  b: Fin(A) |] ==> c: Fin(A)";
    68 goal Finite.thy "!!c b A. [| c<=b;  b: Fin(A) |] ==> c: Fin(A)";
    67 by (REPEAT (ares_tac [Fin_subset_lemma RS spec RS mp] 1));
    69 by (REPEAT (ares_tac [Fin_subset_lemma RS spec RS mp] 1));
    68 qed "Fin_subset";
    70 qed "Fin_subset";
    72 \       P(b);                                                   \
    74 \       P(b);                                                   \
    73 \       !!x y. [| x: A;  y: Fin(A);  x:y;  P(y) |] ==> P(y-{x}) \
    75 \       !!x y. [| x: A;  y: Fin(A);  x:y;  P(y) |] ==> P(y-{x}) \
    74 \    |] ==> c<=b --> P(b-c)";
    76 \    |] ==> c<=b --> P(b-c)";
    75 by (rtac (major RS Fin_induct) 1);
    77 by (rtac (major RS Fin_induct) 1);
    76 by (stac Diff_cons 2);
    78 by (stac Diff_cons 2);
    77 by (ALLGOALS (asm_simp_tac (Fin_ss addsimps (prems@[Diff_0, cons_subset_iff, 
    79 by (ALLGOALS (asm_simp_tac (!simpset addsimps (prems@[cons_subset_iff, 
    78                                 Diff_subset RS Fin_subset]))));
    80                                 Diff_subset RS Fin_subset]))));
    79 qed "Fin_0_induct_lemma";
    81 qed "Fin_0_induct_lemma";
    80 
    82 
    81 val prems = goal Finite.thy 
    83 val prems = goal Finite.thy 
    82     "[| b: Fin(A);                                              \
    84     "[| b: Fin(A);                                              \
    89 qed "Fin_0_induct";
    91 qed "Fin_0_induct";
    90 
    92 
    91 (*Functions from a finite ordinal*)
    93 (*Functions from a finite ordinal*)
    92 val prems = goal Finite.thy "n: nat ==> n->A <= Fin(nat*A)";
    94 val prems = goal Finite.thy "n: nat ==> n->A <= Fin(nat*A)";
    93 by (nat_ind_tac "n" prems 1);
    95 by (nat_ind_tac "n" prems 1);
    94 by (simp_tac (ZF_ss addsimps [Pi_empty1, Fin.emptyI, subset_iff, cons_iff]) 1);
    96 by (simp_tac (!simpset addsimps [Pi_empty1, subset_iff, cons_iff]) 1);
    95 by (asm_simp_tac (ZF_ss addsimps [succ_def, mem_not_refl RS cons_fun_eq]) 1);
    97 by (asm_simp_tac (!simpset addsimps [succ_def, mem_not_refl RS cons_fun_eq]) 1);
    96 by (fast_tac (ZF_cs addSIs [Fin.consI]) 1);
    98 by (fast_tac (!claset addSIs [Fin.consI]) 1);
    97 qed "nat_fun_subset_Fin";
    99 qed "nat_fun_subset_Fin";
    98 
   100 
    99 
   101 
   100 (*** Finite function space ***)
   102 (*** Finite function space ***)
   101 
   103 
   110 by (REPEAT (ares_tac [FiniteFun_mono] 1));
   112 by (REPEAT (ares_tac [FiniteFun_mono] 1));
   111 qed "FiniteFun_mono1";
   113 qed "FiniteFun_mono1";
   112 
   114 
   113 goal Finite.thy "!!h. h: A -||>B ==> h: domain(h) -> B";
   115 goal Finite.thy "!!h. h: A -||>B ==> h: domain(h) -> B";
   114 by (etac FiniteFun.induct 1);
   116 by (etac FiniteFun.induct 1);
   115 by (simp_tac (ZF_ss addsimps [empty_fun, domain_0]) 1);
   117 by (simp_tac (!simpset addsimps [empty_fun, domain_0]) 1);
   116 by (asm_simp_tac (ZF_ss addsimps [fun_extend3, domain_cons]) 1);
   118 by (asm_simp_tac (!simpset addsimps [fun_extend3, domain_cons]) 1);
   117 qed "FiniteFun_is_fun";
   119 qed "FiniteFun_is_fun";
   118 
   120 
   119 goal Finite.thy "!!h. h: A -||>B ==> domain(h) : Fin(A)";
   121 goal Finite.thy "!!h. h: A -||>B ==> domain(h) : Fin(A)";
   120 by (etac FiniteFun.induct 1);
   122 by (etac FiniteFun.induct 1);
   121 by (simp_tac (Fin_ss addsimps [domain_0]) 1);
   123 by (simp_tac (!simpset addsimps [domain_0]) 1);
   122 by (asm_simp_tac (Fin_ss addsimps [domain_cons]) 1);
   124 by (asm_simp_tac (!simpset addsimps [domain_cons]) 1);
   123 qed "FiniteFun_domain_Fin";
   125 qed "FiniteFun_domain_Fin";
   124 
   126 
   125 bind_thm ("FiniteFun_apply_type", FiniteFun_is_fun RS apply_type);
   127 bind_thm ("FiniteFun_apply_type", FiniteFun_is_fun RS apply_type);
   126 
   128 
   127 (*Every subset of a finite function is a finite function.*)
   129 (*Every subset of a finite function is a finite function.*)
   128 goal Finite.thy "!!b A. b: A-||>B ==> ALL z. z<=b --> z: A-||>B";
   130 goal Finite.thy "!!b A. b: A-||>B ==> ALL z. z<=b --> z: A-||>B";
   129 by (etac FiniteFun.induct 1);
   131 by (etac FiniteFun.induct 1);
   130 by (simp_tac (ZF_ss addsimps subset_empty_iff::FiniteFun.intrs) 1);
   132 by (simp_tac (!simpset addsimps subset_empty_iff::FiniteFun.intrs) 1);
   131 by (asm_simp_tac (ZF_ss addsimps subset_cons_iff::distrib_simps) 1);
   133 by (asm_simp_tac (!simpset addsimps subset_cons_iff::distrib_simps) 1);
   132 by (safe_tac ZF_cs);
   134 by (safe_tac (!claset));
   133 by (eres_inst_tac [("b","z")] (cons_Diff RS subst) 1);
   135 by (eres_inst_tac [("b","z")] (cons_Diff RS subst) 1);
   134 by (dtac (spec RS mp) 1 THEN assume_tac 1);
   136 by (dtac (spec RS mp) 1 THEN assume_tac 1);
   135 by (fast_tac (ZF_cs addSIs FiniteFun.intrs) 1);
   137 by (fast_tac (!claset addSIs FiniteFun.intrs) 1);
   136 qed "FiniteFun_subset_lemma";
   138 qed "FiniteFun_subset_lemma";
   137 
   139 
   138 goal Finite.thy "!!c b A. [| c<=b;  b: A-||>B |] ==> c: A-||>B";
   140 goal Finite.thy "!!c b A. [| c<=b;  b: A-||>B |] ==> c: A-||>B";
   139 by (REPEAT (ares_tac [FiniteFun_subset_lemma RS spec RS mp] 1));
   141 by (REPEAT (ares_tac [FiniteFun_subset_lemma RS spec RS mp] 1));
   140 qed "FiniteFun_subset";
   142 qed "FiniteFun_subset";