src/ZF/Sum.ML
changeset 760 f0200e91b272
parent 744 2054fa3c8d76
child 773 9f8bcf1a4cff
equal deleted inserted replaced
759:e0b172d01c37 760:f0200e91b272
    11 (*** Rules for the Part primitive ***)
    11 (*** Rules for the Part primitive ***)
    12 
    12 
    13 goalw Sum.thy [Part_def]
    13 goalw Sum.thy [Part_def]
    14     "a : Part(A,h) <-> a:A & (EX y. a=h(y))";
    14     "a : Part(A,h) <-> a:A & (EX y. a=h(y))";
    15 by (rtac separation 1);
    15 by (rtac separation 1);
    16 val Part_iff = result();
    16 qed "Part_iff";
    17 
    17 
    18 goalw Sum.thy [Part_def]
    18 goalw Sum.thy [Part_def]
    19     "!!a b A h. [| a : A;  a=h(b) |] ==> a : Part(A,h)";
    19     "!!a b A h. [| a : A;  a=h(b) |] ==> a : Part(A,h)";
    20 by (REPEAT (ares_tac [exI,CollectI] 1));
    20 by (REPEAT (ares_tac [exI,CollectI] 1));
    21 val Part_eqI = result();
    21 qed "Part_eqI";
    22 
    22 
    23 val PartI = refl RSN (2,Part_eqI);
    23 val PartI = refl RSN (2,Part_eqI);
    24 
    24 
    25 val major::prems = goalw Sum.thy [Part_def]
    25 val major::prems = goalw Sum.thy [Part_def]
    26     "[| a : Part(A,h);  !!z. [| a : A;  a=h(z) |] ==> P  \
    26     "[| a : Part(A,h);  !!z. [| a : A;  a=h(z) |] ==> P  \
    27 \    |] ==> P";
    27 \    |] ==> P";
    28 by (rtac (major RS CollectE) 1);
    28 by (rtac (major RS CollectE) 1);
    29 by (etac exE 1);
    29 by (etac exE 1);
    30 by (REPEAT (ares_tac prems 1));
    30 by (REPEAT (ares_tac prems 1));
    31 val PartE = result();
    31 qed "PartE";
    32 
    32 
    33 goalw Sum.thy [Part_def] "Part(A,h) <= A";
    33 goalw Sum.thy [Part_def] "Part(A,h) <= A";
    34 by (rtac Collect_subset 1);
    34 by (rtac Collect_subset 1);
    35 val Part_subset = result();
    35 qed "Part_subset";
    36 
    36 
    37 
    37 
    38 (*** Rules for Disjoint Sums ***)
    38 (*** Rules for Disjoint Sums ***)
    39 
    39 
    40 val sum_defs = [sum_def,Inl_def,Inr_def,case_def];
    40 val sum_defs = [sum_def,Inl_def,Inr_def,case_def];
    41 
    41 
    42 goalw Sum.thy (bool_def::sum_defs) "Sigma(bool,C) = C(0) + C(1)";
    42 goalw Sum.thy (bool_def::sum_defs) "Sigma(bool,C) = C(0) + C(1)";
    43 by (fast_tac eq_cs 1);
    43 by (fast_tac eq_cs 1);
    44 val Sigma_bool = result();
    44 qed "Sigma_bool";
    45 
    45 
    46 (** Introduction rules for the injections **)
    46 (** Introduction rules for the injections **)
    47 
    47 
    48 goalw Sum.thy sum_defs "!!a A B. a : A ==> Inl(a) : A+B";
    48 goalw Sum.thy sum_defs "!!a A B. a : A ==> Inl(a) : A+B";
    49 by (REPEAT (ares_tac [UnI1,SigmaI,singletonI] 1));
    49 by (REPEAT (ares_tac [UnI1,SigmaI,singletonI] 1));
    50 val InlI = result();
    50 qed "InlI";
    51 
    51 
    52 goalw Sum.thy sum_defs "!!b A B. b : B ==> Inr(b) : A+B";
    52 goalw Sum.thy sum_defs "!!b A B. b : B ==> Inr(b) : A+B";
    53 by (REPEAT (ares_tac [UnI2,SigmaI,singletonI] 1));
    53 by (REPEAT (ares_tac [UnI2,SigmaI,singletonI] 1));
    54 val InrI = result();
    54 qed "InrI";
    55 
    55 
    56 (** Elimination rules **)
    56 (** Elimination rules **)
    57 
    57 
    58 val major::prems = goalw Sum.thy sum_defs
    58 val major::prems = goalw Sum.thy sum_defs
    59     "[| u: A+B;  \
    59     "[| u: A+B;  \
    61 \       !!y. [| y:B;  u=Inr(y) |] ==> P \
    61 \       !!y. [| y:B;  u=Inr(y) |] ==> P \
    62 \    |] ==> P";
    62 \    |] ==> P";
    63 by (rtac (major RS UnE) 1);
    63 by (rtac (major RS UnE) 1);
    64 by (REPEAT (rtac refl 1
    64 by (REPEAT (rtac refl 1
    65      ORELSE eresolve_tac (prems@[SigmaE,singletonE,ssubst]) 1));
    65      ORELSE eresolve_tac (prems@[SigmaE,singletonE,ssubst]) 1));
    66 val sumE = result();
    66 qed "sumE";
    67 
    67 
    68 (** Injection and freeness equivalences, for rewriting **)
    68 (** Injection and freeness equivalences, for rewriting **)
    69 
    69 
    70 goalw Sum.thy sum_defs "Inl(a)=Inl(b) <-> a=b";
    70 goalw Sum.thy sum_defs "Inl(a)=Inl(b) <-> a=b";
    71 by (simp_tac ZF_ss 1);
    71 by (simp_tac ZF_ss 1);
    72 val Inl_iff = result();
    72 qed "Inl_iff";
    73 
    73 
    74 goalw Sum.thy sum_defs "Inr(a)=Inr(b) <-> a=b";
    74 goalw Sum.thy sum_defs "Inr(a)=Inr(b) <-> a=b";
    75 by (simp_tac ZF_ss 1);
    75 by (simp_tac ZF_ss 1);
    76 val Inr_iff = result();
    76 qed "Inr_iff";
    77 
    77 
    78 goalw Sum.thy sum_defs "Inl(a)=Inr(b) <-> False";
    78 goalw Sum.thy sum_defs "Inl(a)=Inr(b) <-> False";
    79 by (simp_tac (ZF_ss addsimps [one_not_0 RS not_sym]) 1);
    79 by (simp_tac (ZF_ss addsimps [one_not_0 RS not_sym]) 1);
    80 val Inl_Inr_iff = result();
    80 qed "Inl_Inr_iff";
    81 
    81 
    82 goalw Sum.thy sum_defs "Inr(b)=Inl(a) <-> False";
    82 goalw Sum.thy sum_defs "Inr(b)=Inl(a) <-> False";
    83 by (simp_tac (ZF_ss addsimps [one_not_0]) 1);
    83 by (simp_tac (ZF_ss addsimps [one_not_0]) 1);
    84 val Inr_Inl_iff = result();
    84 qed "Inr_Inl_iff";
    85 
    85 
    86 (*Injection and freeness rules*)
    86 (*Injection and freeness rules*)
    87 
    87 
    88 val Inl_inject = standard (Inl_iff RS iffD1);
    88 val Inl_inject = standard (Inl_iff RS iffD1);
    89 val Inr_inject = standard (Inr_iff RS iffD1);
    89 val Inr_inject = standard (Inr_iff RS iffD1);
    97 val sum_ss = ZF_ss addsimps [InlI, InrI, Inl_iff, Inr_iff, 
    97 val sum_ss = ZF_ss addsimps [InlI, InrI, Inl_iff, Inr_iff, 
    98 			     Inl_Inr_iff, Inr_Inl_iff];
    98 			     Inl_Inr_iff, Inr_Inl_iff];
    99 
    99 
   100 goal Sum.thy "!!A B. Inl(a): A+B ==> a: A";
   100 goal Sum.thy "!!A B. Inl(a): A+B ==> a: A";
   101 by (fast_tac sum_cs 1);
   101 by (fast_tac sum_cs 1);
   102 val InlD = result();
   102 qed "InlD";
   103 
   103 
   104 goal Sum.thy "!!A B. Inr(b): A+B ==> b: B";
   104 goal Sum.thy "!!A B. Inr(b): A+B ==> b: B";
   105 by (fast_tac sum_cs 1);
   105 by (fast_tac sum_cs 1);
   106 val InrD = result();
   106 qed "InrD";
   107 
   107 
   108 goal Sum.thy "u: A+B <-> (EX x. x:A & u=Inl(x)) | (EX y. y:B & u=Inr(y))";
   108 goal Sum.thy "u: A+B <-> (EX x. x:A & u=Inl(x)) | (EX y. y:B & u=Inr(y))";
   109 by (fast_tac sum_cs 1);
   109 by (fast_tac sum_cs 1);
   110 val sum_iff = result();
   110 qed "sum_iff";
   111 
   111 
   112 goal Sum.thy "A+B <= C+D <-> A<=C & B<=D";
   112 goal Sum.thy "A+B <= C+D <-> A<=C & B<=D";
   113 by (fast_tac sum_cs 1);
   113 by (fast_tac sum_cs 1);
   114 val sum_subset_iff = result();
   114 qed "sum_subset_iff";
   115 
   115 
   116 goal Sum.thy "A+B = C+D <-> A=C & B=D";
   116 goal Sum.thy "A+B = C+D <-> A=C & B=D";
   117 by (simp_tac (ZF_ss addsimps [extension,sum_subset_iff]) 1);
   117 by (simp_tac (ZF_ss addsimps [extension,sum_subset_iff]) 1);
   118 by (fast_tac ZF_cs 1);
   118 by (fast_tac ZF_cs 1);
   119 val sum_equal_iff = result();
   119 qed "sum_equal_iff";
   120 
   120 
   121 
   121 
   122 (*** Eliminator -- case ***)
   122 (*** Eliminator -- case ***)
   123 
   123 
   124 goalw Sum.thy sum_defs "case(c, d, Inl(a)) = c(a)";
   124 goalw Sum.thy sum_defs "case(c, d, Inl(a)) = c(a)";
   125 by (rtac (split RS trans) 1);
   125 by (rtac (split RS trans) 1);
   126 by (rtac cond_0 1);
   126 by (rtac cond_0 1);
   127 val case_Inl = result();
   127 qed "case_Inl";
   128 
   128 
   129 goalw Sum.thy sum_defs "case(c, d, Inr(b)) = d(b)";
   129 goalw Sum.thy sum_defs "case(c, d, Inr(b)) = d(b)";
   130 by (rtac (split RS trans) 1);
   130 by (rtac (split RS trans) 1);
   131 by (rtac cond_1 1);
   131 by (rtac cond_1 1);
   132 val case_Inr = result();
   132 qed "case_Inr";
   133 
   133 
   134 val major::prems = goal Sum.thy
   134 val major::prems = goal Sum.thy
   135     "[| u: A+B; \
   135     "[| u: A+B; \
   136 \       !!x. x: A ==> c(x): C(Inl(x));   \
   136 \       !!x. x: A ==> c(x): C(Inl(x));   \
   137 \       !!y. y: B ==> d(y): C(Inr(y)) \
   137 \       !!y. y: B ==> d(y): C(Inr(y)) \
   138 \    |] ==> case(c,d,u) : C(u)";
   138 \    |] ==> case(c,d,u) : C(u)";
   139 by (rtac (major RS sumE) 1);
   139 by (rtac (major RS sumE) 1);
   140 by (ALLGOALS (etac ssubst));
   140 by (ALLGOALS (etac ssubst));
   141 by (ALLGOALS (asm_simp_tac (ZF_ss addsimps
   141 by (ALLGOALS (asm_simp_tac (ZF_ss addsimps
   142 			    (prems@[case_Inl,case_Inr]))));
   142 			    (prems@[case_Inl,case_Inr]))));
   143 val case_type = result();
   143 qed "case_type";
   144 
   144 
   145 goal Sum.thy
   145 goal Sum.thy
   146   "!!u. u: A+B ==>   \
   146   "!!u. u: A+B ==>   \
   147 \       R(case(c,d,u)) <-> \
   147 \       R(case(c,d,u)) <-> \
   148 \       ((ALL x:A. u = Inl(x) --> R(c(x))) & \
   148 \       ((ALL x:A. u = Inl(x) --> R(c(x))) & \
   150 by (etac sumE 1);
   150 by (etac sumE 1);
   151 by (asm_simp_tac (ZF_ss addsimps [case_Inl]) 1);
   151 by (asm_simp_tac (ZF_ss addsimps [case_Inl]) 1);
   152 by (fast_tac sum_cs 1);
   152 by (fast_tac sum_cs 1);
   153 by (asm_simp_tac (ZF_ss addsimps [case_Inr]) 1);
   153 by (asm_simp_tac (ZF_ss addsimps [case_Inr]) 1);
   154 by (fast_tac sum_cs 1);
   154 by (fast_tac sum_cs 1);
   155 val expand_case = result();
   155 qed "expand_case";
   156 
       
   157 
   156 
   158 goal Sum.thy "!!A B h. A<=B ==> Part(A,h)<=Part(B,h)";
   157 goal Sum.thy "!!A B h. A<=B ==> Part(A,h)<=Part(B,h)";
   159 by (fast_tac sum_cs 1);
   158 by (fast_tac sum_cs 1);
   160 val Part_mono = result();
   159 qed "Part_mono";
   161 
   160 
   162 goal Sum.thy "Part(Collect(A,P), h) = Collect(Part(A,h), P)";
   161 goal Sum.thy "Part(Collect(A,P), h) = Collect(Part(A,h), P)";
   163 by (fast_tac (sum_cs addSIs [equalityI]) 1);
   162 by (fast_tac (sum_cs addSIs [equalityI]) 1);
   164 val Part_Collect = result();
   163 qed "Part_Collect";
   165 
   164 
   166 val Part_CollectE =
   165 val Part_CollectE =
   167     Part_Collect RS equalityD1 RS subsetD RS CollectE |> standard;
   166     Part_Collect RS equalityD1 RS subsetD RS CollectE |> standard;
   168 
   167 
   169 goal Sum.thy "Part(A+B,Inl) = {Inl(x). x: A}";
   168 goal Sum.thy "Part(A+B,Inl) = {Inl(x). x: A}";
   170 by (fast_tac (sum_cs addIs [equalityI]) 1);
   169 by (fast_tac (sum_cs addIs [equalityI]) 1);
   171 val Part_Inl = result();
   170 qed "Part_Inl";
   172 
   171 
   173 goal Sum.thy "Part(A+B,Inr) = {Inr(y). y: B}";
   172 goal Sum.thy "Part(A+B,Inr) = {Inr(y). y: B}";
   174 by (fast_tac (sum_cs addIs [equalityI]) 1);
   173 by (fast_tac (sum_cs addIs [equalityI]) 1);
   175 val Part_Inr = result();
   174 qed "Part_Inr";
   176 
   175 
   177 goalw Sum.thy [Part_def] "!!a. a : Part(A,h) ==> a : A";
   176 goalw Sum.thy [Part_def] "!!a. a : Part(A,h) ==> a : A";
   178 by (etac CollectD1 1);
   177 by (etac CollectD1 1);
   179 val PartD1 = result();
   178 qed "PartD1";
   180 
   179 
   181 goal Sum.thy "Part(A,%x.x) = A";
   180 goal Sum.thy "Part(A,%x.x) = A";
   182 by (fast_tac (sum_cs addIs [equalityI]) 1);
   181 by (fast_tac (sum_cs addIs [equalityI]) 1);
   183 val Part_id = result();
   182 qed "Part_id";
   184 
   183 
   185 goal Sum.thy "Part(A+B, %x.Inr(h(x))) = {Inr(y). y: Part(B,h)}";
   184 goal Sum.thy "Part(A+B, %x.Inr(h(x))) = {Inr(y). y: Part(B,h)}";
   186 by (fast_tac (sum_cs addIs [equalityI]) 1);
   185 by (fast_tac (sum_cs addIs [equalityI]) 1);
   187 val Part_Inr2 = result();
   186 qed "Part_Inr2";
   188 
   187 
   189 goal Sum.thy "!!A B C. C <= A+B ==> Part(C,Inl) Un Part(C,Inr) = C";
   188 goal Sum.thy "!!A B C. C <= A+B ==> Part(C,Inl) Un Part(C,Inr) = C";
   190 by (fast_tac (sum_cs addIs [equalityI]) 1);
   189 by (fast_tac (sum_cs addIs [equalityI]) 1);
   191 val Part_sum_equality = result();
   190 qed "Part_sum_equality";