src/HOL/Integ/Integ.ML
changeset 1266 3ae9fe3c0f68
parent 972 e61b058d58d2
child 1465 5d7a7e439cec
equal deleted inserted replaced
1265:6ef9a9893fd6 1266:3ae9fe3c0f68
    81 goal Integ.thy "inj_onto Abs_Integ Integ";
    81 goal Integ.thy "inj_onto Abs_Integ Integ";
    82 by (rtac inj_onto_inverseI 1);
    82 by (rtac inj_onto_inverseI 1);
    83 by (etac Abs_Integ_inverse 1);
    83 by (etac Abs_Integ_inverse 1);
    84 qed "inj_onto_Abs_Integ";
    84 qed "inj_onto_Abs_Integ";
    85 
    85 
    86 val intrel_ss = 
    86 Addsimps [equiv_intrel_iff, inj_onto_Abs_Integ RS inj_onto_iff,
    87     arith_ss addsimps [equiv_intrel_iff, inj_onto_Abs_Integ RS inj_onto_iff,
    87 	  intrel_iff, intrel_in_integ, Abs_Integ_inverse];
    88 		       intrel_iff, intrel_in_integ, Abs_Integ_inverse];
       
    89 
    88 
    90 goal Integ.thy "inj(Rep_Integ)";
    89 goal Integ.thy "inj(Rep_Integ)";
    91 by (rtac inj_inverseI 1);
    90 by (rtac inj_inverseI 1);
    92 by (rtac Rep_Integ_inverse 1);
    91 by (rtac Rep_Integ_inverse 1);
    93 qed "inj_Rep_Integ";
    92 qed "inj_Rep_Integ";
   104 by (REPEAT (rtac intrel_in_integ 1));
   103 by (REPEAT (rtac intrel_in_integ 1));
   105 by (dtac eq_equiv_class 1);
   104 by (dtac eq_equiv_class 1);
   106 by (rtac equiv_intrel 1);
   105 by (rtac equiv_intrel 1);
   107 by (fast_tac set_cs 1);
   106 by (fast_tac set_cs 1);
   108 by (safe_tac intrel_cs);
   107 by (safe_tac intrel_cs);
   109 by (asm_full_simp_tac arith_ss 1);
   108 by (Asm_full_simp_tac 1);
   110 qed "inj_znat";
   109 qed "inj_znat";
   111 
   110 
   112 
   111 
   113 (**** zminus: unary negation on Integ ****)
   112 (**** zminus: unary negation on Integ ****)
   114 
   113 
   115 goalw Integ.thy [congruent_def]
   114 goalw Integ.thy [congruent_def]
   116   "congruent intrel (%p. split (%x y. intrel^^{(y,x)}) p)";
   115   "congruent intrel (%p. split (%x y. intrel^^{(y,x)}) p)";
   117 by (safe_tac intrel_cs);
   116 by (safe_tac intrel_cs);
   118 by (asm_simp_tac (intrel_ss addsimps add_ac) 1);
   117 by (asm_simp_tac (!simpset addsimps add_ac) 1);
   119 qed "zminus_congruent";
   118 qed "zminus_congruent";
   120 
   119 
   121 
   120 
   122 (*Resolve th against the corresponding facts for zminus*)
   121 (*Resolve th against the corresponding facts for zminus*)
   123 val zminus_ize = RSLIST [equiv_intrel, zminus_congruent];
   122 val zminus_ize = RSLIST [equiv_intrel, zminus_congruent];
   124 
   123 
   125 goalw Integ.thy [zminus_def]
   124 goalw Integ.thy [zminus_def]
   126       "$~ Abs_Integ(intrel^^{(x,y)}) = Abs_Integ(intrel ^^ {(y,x)})";
   125       "$~ Abs_Integ(intrel^^{(x,y)}) = Abs_Integ(intrel ^^ {(y,x)})";
   127 by (res_inst_tac [("f","Abs_Integ")] arg_cong 1);
   126 by (res_inst_tac [("f","Abs_Integ")] arg_cong 1);
   128 by (simp_tac (set_ss addsimps 
   127 by (simp_tac (!simpset addsimps 
   129    [intrel_in_integ RS Abs_Integ_inverse,zminus_ize UN_equiv_class]) 1);
   128    [intrel_in_integ RS Abs_Integ_inverse,zminus_ize UN_equiv_class]) 1);
   130 by (rewtac split_def);
       
   131 by (simp_tac prod_ss 1);
       
   132 qed "zminus";
   129 qed "zminus";
   133 
   130 
   134 (*by lcp*)
   131 (*by lcp*)
   135 val [prem] = goal Integ.thy
   132 val [prem] = goal Integ.thy
   136     "(!!x y. z = Abs_Integ(intrel^^{(x,y)}) ==> P) ==> P";
   133     "(!!x y. z = Abs_Integ(intrel^^{(x,y)}) ==> P) ==> P";
   137 by (res_inst_tac [("x1","z")] 
   134 by (res_inst_tac [("x1","z")] 
   138     (rewrite_rule [Integ_def] Rep_Integ RS quotientE) 1);
   135     (rewrite_rule [Integ_def] Rep_Integ RS quotientE) 1);
   139 by (dres_inst_tac [("f","Abs_Integ")] arg_cong 1);
   136 by (dres_inst_tac [("f","Abs_Integ")] arg_cong 1);
   140 by (res_inst_tac [("p","x")] PairE 1);
   137 by (res_inst_tac [("p","x")] PairE 1);
   141 by (rtac prem 1);
   138 by (rtac prem 1);
   142 by (asm_full_simp_tac (HOL_ss addsimps [Rep_Integ_inverse]) 1);
   139 by (asm_full_simp_tac (!simpset addsimps [Rep_Integ_inverse]) 1);
   143 qed "eq_Abs_Integ";
   140 qed "eq_Abs_Integ";
   144 
   141 
   145 goal Integ.thy "$~ ($~ z) = z";
   142 goal Integ.thy "$~ ($~ z) = z";
   146 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   143 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   147 by (asm_simp_tac (HOL_ss addsimps [zminus]) 1);
   144 by (asm_simp_tac (!simpset addsimps [zminus]) 1);
   148 qed "zminus_zminus";
   145 qed "zminus_zminus";
   149 
   146 
   150 goal Integ.thy "inj(zminus)";
   147 goal Integ.thy "inj(zminus)";
   151 by (rtac injI 1);
   148 by (rtac injI 1);
   152 by (dres_inst_tac [("f","zminus")] arg_cong 1);
   149 by (dres_inst_tac [("f","zminus")] arg_cong 1);
   153 by (asm_full_simp_tac (HOL_ss addsimps [zminus_zminus]) 1);
   150 by (asm_full_simp_tac (!simpset addsimps [zminus_zminus]) 1);
   154 qed "inj_zminus";
   151 qed "inj_zminus";
   155 
   152 
   156 goalw Integ.thy [znat_def] "$~ ($#0) = $#0";
   153 goalw Integ.thy [znat_def] "$~ ($#0) = $#0";
   157 by (simp_tac (arith_ss addsimps [zminus]) 1);
   154 by (simp_tac (!simpset addsimps [zminus]) 1);
   158 qed "zminus_0";
   155 qed "zminus_0";
   159 
   156 
   160 
   157 
   161 (**** znegative: the test for negative integers ****)
   158 (**** znegative: the test for negative integers ****)
   162 
   159 
   163 goal Arith.thy "!!m x n::nat. n+m=x ==> m<=x";
   160 goal Arith.thy "!!m x n::nat. n+m=x ==> m<=x";
   164 by (dtac (disjI2 RS less_or_eq_imp_le) 1);
   161 by (dtac (disjI2 RS less_or_eq_imp_le) 1);
   165 by (asm_full_simp_tac (arith_ss addsimps add_ac) 1);
   162 by (asm_full_simp_tac (!simpset addsimps add_ac) 1);
   166 by (dtac add_leD1 1);
   163 by (dtac add_leD1 1);
   167 by (assume_tac 1);
   164 by (assume_tac 1);
   168 qed "not_znegative_znat_lemma";
   165 qed "not_znegative_znat_lemma";
   169 
   166 
   170 
   167 
   171 goalw Integ.thy [znegative_def, znat_def]
   168 goalw Integ.thy [znegative_def, znat_def]
   172     "~ znegative($# n)";
   169     "~ znegative($# n)";
   173 by (simp_tac intrel_ss 1);
   170 by (Simp_tac 1);
   174 by (safe_tac intrel_cs);
   171 by (safe_tac intrel_cs);
   175 by (rtac ccontr 1);
   172 by (rtac ccontr 1);
   176 by (etac notE 1);
   173 by (etac notE 1);
   177 by (asm_full_simp_tac arith_ss 1);
   174 by (Asm_full_simp_tac 1);
   178 by (dtac not_znegative_znat_lemma 1);
   175 by (dtac not_znegative_znat_lemma 1);
   179 by (fast_tac (HOL_cs addDs [leD]) 1);
   176 by (fast_tac (HOL_cs addDs [leD]) 1);
   180 qed "not_znegative_znat";
   177 qed "not_znegative_znat";
   181 
   178 
   182 goalw Integ.thy [znegative_def, znat_def] "znegative($~ $# Suc(n))";
   179 goalw Integ.thy [znegative_def, znat_def] "znegative($~ $# Suc(n))";
   183 by (simp_tac (intrel_ss addsimps [zminus]) 1);
   180 by (simp_tac (!simpset addsimps [zminus]) 1);
   184 by (REPEAT (ares_tac [exI, conjI] 1));
   181 by (REPEAT (ares_tac [exI, conjI] 1));
   185 by (rtac (intrelI RS ImageI) 2);
   182 by (rtac (intrelI RS ImageI) 2);
   186 by (rtac singletonI 3);
   183 by (rtac singletonI 3);
   187 by (simp_tac arith_ss 2);
   184 by (Simp_tac 2);
   188 by (rtac less_add_Suc1 1);
   185 by (rtac less_add_Suc1 1);
   189 qed "znegative_zminus_znat";
   186 qed "znegative_zminus_znat";
   190 
   187 
   191 
   188 
   192 (**** zmagnitude: magnitide of an integer, as a natural number ****)
   189 (**** zmagnitude: magnitide of an integer, as a natural number ****)
   193 
   190 
   194 goal Arith.thy "!!n::nat. n - Suc(n+m)=0";
   191 goal Arith.thy "!!n::nat. n - Suc(n+m)=0";
   195 by (nat_ind_tac "n" 1);
   192 by (nat_ind_tac "n" 1);
   196 by (ALLGOALS(asm_simp_tac arith_ss));
   193 by (ALLGOALS Asm_simp_tac);
   197 qed "diff_Suc_add_0";
   194 qed "diff_Suc_add_0";
   198 
   195 
   199 goal Arith.thy "Suc((n::nat)+m)-n=Suc(m)";
   196 goal Arith.thy "Suc((n::nat)+m)-n=Suc(m)";
   200 by (nat_ind_tac "n" 1);
   197 by (nat_ind_tac "n" 1);
   201 by (ALLGOALS(asm_simp_tac arith_ss));
   198 by (ALLGOALS Asm_simp_tac);
   202 qed "diff_Suc_add_inverse";
   199 qed "diff_Suc_add_inverse";
   203 
   200 
   204 goalw Integ.thy [congruent_def]
   201 goalw Integ.thy [congruent_def]
   205     "congruent intrel (split (%x y. intrel^^{((y-x) + (x-(y::nat)),0)}))";
   202     "congruent intrel (split (%x y. intrel^^{((y-x) + (x-(y::nat)),0)}))";
   206 by (safe_tac intrel_cs);
   203 by (safe_tac intrel_cs);
   207 by (asm_simp_tac intrel_ss 1);
   204 by (Asm_simp_tac 1);
   208 by (etac rev_mp 1);
   205 by (etac rev_mp 1);
   209 by (res_inst_tac [("m","x1"),("n","y1")] diff_induct 1);
   206 by (res_inst_tac [("m","x1"),("n","y1")] diff_induct 1);
   210 by (asm_simp_tac (arith_ss addsimps [inj_Suc RS inj_eq]) 3);
   207 by (asm_simp_tac (!simpset addsimps [inj_Suc RS inj_eq]) 3);
   211 by (asm_simp_tac (arith_ss addsimps [diff_add_inverse,diff_add_0]) 2);
   208 by (asm_simp_tac (!simpset addsimps [diff_add_inverse,diff_add_0]) 2);
   212 by (asm_simp_tac arith_ss 1);
   209 by (Asm_simp_tac 1);
   213 by (rtac impI 1);
   210 by (rtac impI 1);
   214 by (etac subst 1);
   211 by (etac subst 1);
   215 by (res_inst_tac [("m1","x")] (add_commute RS ssubst) 1);
   212 by (res_inst_tac [("m1","x")] (add_commute RS ssubst) 1);
   216 by (asm_simp_tac (arith_ss addsimps [diff_add_inverse,diff_add_0]) 1);
   213 by (asm_simp_tac (!simpset addsimps [diff_add_inverse,diff_add_0]) 1);
   217 by (rtac impI 1);
   214 by (rtac impI 1);
   218 by (asm_simp_tac (arith_ss addsimps
   215 by (asm_simp_tac (!simpset addsimps
   219 		  [diff_add_inverse, diff_add_0, diff_Suc_add_0,
   216 		  [diff_add_inverse, diff_add_0, diff_Suc_add_0,
   220 		   diff_Suc_add_inverse]) 1);
   217 		   diff_Suc_add_inverse]) 1);
   221 qed "zmagnitude_congruent";
   218 qed "zmagnitude_congruent";
   222 
   219 
   223 (*Resolve th against the corresponding facts for zmagnitude*)
   220 (*Resolve th against the corresponding facts for zmagnitude*)
   226 
   223 
   227 goalw Integ.thy [zmagnitude_def]
   224 goalw Integ.thy [zmagnitude_def]
   228     "zmagnitude (Abs_Integ(intrel^^{(x,y)})) = \
   225     "zmagnitude (Abs_Integ(intrel^^{(x,y)})) = \
   229 \    Abs_Integ(intrel^^{((y - x) + (x - y),0)})";
   226 \    Abs_Integ(intrel^^{((y - x) + (x - y),0)})";
   230 by (res_inst_tac [("f","Abs_Integ")] arg_cong 1);
   227 by (res_inst_tac [("f","Abs_Integ")] arg_cong 1);
   231 by (asm_simp_tac (intrel_ss addsimps [zmagnitude_ize UN_equiv_class]) 1);
   228 by (asm_simp_tac (!simpset addsimps [zmagnitude_ize UN_equiv_class]) 1);
   232 qed "zmagnitude";
   229 qed "zmagnitude";
   233 
   230 
   234 goalw Integ.thy [znat_def] "zmagnitude($# n) = $#n";
   231 goalw Integ.thy [znat_def] "zmagnitude($# n) = $#n";
   235 by (asm_simp_tac (intrel_ss addsimps [zmagnitude]) 1);
   232 by (asm_simp_tac (!simpset addsimps [zmagnitude]) 1);
   236 qed "zmagnitude_znat";
   233 qed "zmagnitude_znat";
   237 
   234 
   238 goalw Integ.thy [znat_def] "zmagnitude($~ $# n) = $#n";
   235 goalw Integ.thy [znat_def] "zmagnitude($~ $# n) = $#n";
   239 by (asm_simp_tac (intrel_ss addsimps [zmagnitude, zminus]) 1);
   236 by (asm_simp_tac (!simpset addsimps [zmagnitude, zminus]) 1);
   240 qed "zmagnitude_zminus_znat";
   237 qed "zmagnitude_zminus_znat";
   241 
   238 
   242 
   239 
   243 (**** zadd: addition on Integ ****)
   240 (**** zadd: addition on Integ ****)
   244 
   241 
   247 goalw Integ.thy [congruent2_def]
   244 goalw Integ.thy [congruent2_def]
   248     "congruent2 intrel (%p1 p2.                  \
   245     "congruent2 intrel (%p1 p2.                  \
   249 \         split (%x1 y1. split (%x2 y2. intrel^^{(x1+x2, y1+y2)}) p2) p1)";
   246 \         split (%x1 y1. split (%x2 y2. intrel^^{(x1+x2, y1+y2)}) p2) p1)";
   250 (*Proof via congruent2_commuteI seems longer*)
   247 (*Proof via congruent2_commuteI seems longer*)
   251 by (safe_tac intrel_cs);
   248 by (safe_tac intrel_cs);
   252 by (asm_simp_tac (intrel_ss addsimps [add_assoc]) 1);
   249 by (asm_simp_tac (!simpset addsimps [add_assoc]) 1);
   253 (*The rest should be trivial, but rearranging terms is hard*)
   250 (*The rest should be trivial, but rearranging terms is hard*)
   254 by (res_inst_tac [("x1","x1a")] (add_left_commute RS ssubst) 1);
   251 by (res_inst_tac [("x1","x1a")] (add_left_commute RS ssubst) 1);
   255 by (asm_simp_tac (arith_ss addsimps [add_assoc RS sym]) 1);
   252 by (asm_simp_tac (!simpset addsimps [add_assoc RS sym]) 1);
   256 by (asm_simp_tac (arith_ss addsimps add_ac) 1);
   253 by (asm_simp_tac (!simpset addsimps add_ac) 1);
   257 qed "zadd_congruent2";
   254 qed "zadd_congruent2";
   258 
   255 
   259 (*Resolve th against the corresponding facts for zadd*)
   256 (*Resolve th against the corresponding facts for zadd*)
   260 val zadd_ize = RSLIST [equiv_intrel, zadd_congruent2];
   257 val zadd_ize = RSLIST [equiv_intrel, zadd_congruent2];
   261 
   258 
   262 goalw Integ.thy [zadd_def]
   259 goalw Integ.thy [zadd_def]
   263   "Abs_Integ(intrel^^{(x1,y1)}) + Abs_Integ(intrel^^{(x2,y2)}) = \
   260   "Abs_Integ(intrel^^{(x1,y1)}) + Abs_Integ(intrel^^{(x2,y2)}) = \
   264 \  Abs_Integ(intrel^^{(x1+x2, y1+y2)})";
   261 \  Abs_Integ(intrel^^{(x1+x2, y1+y2)})";
   265 by (asm_simp_tac
   262 by (asm_simp_tac
   266     (intrel_ss addsimps [zadd_ize UN_equiv_class2]) 1);
   263     (!simpset addsimps [zadd_ize UN_equiv_class2]) 1);
   267 qed "zadd";
   264 qed "zadd";
   268 
   265 
   269 goalw Integ.thy [znat_def] "$#0 + z = z";
   266 goalw Integ.thy [znat_def] "$#0 + z = z";
   270 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   267 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   271 by (asm_simp_tac (arith_ss addsimps [zadd]) 1);
   268 by (asm_simp_tac (!simpset addsimps [zadd]) 1);
   272 qed "zadd_0";
   269 qed "zadd_0";
   273 
   270 
   274 goal Integ.thy "$~ (z + w) = $~ z + $~ w";
   271 goal Integ.thy "$~ (z + w) = $~ z + $~ w";
   275 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   272 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   276 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   273 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   277 by (asm_simp_tac (arith_ss addsimps [zminus,zadd]) 1);
   274 by (asm_simp_tac (!simpset addsimps [zminus,zadd]) 1);
   278 qed "zminus_zadd_distrib";
   275 qed "zminus_zadd_distrib";
   279 
   276 
   280 goal Integ.thy "(z::int) + w = w + z";
   277 goal Integ.thy "(z::int) + w = w + z";
   281 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   278 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   282 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   279 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   283 by (asm_simp_tac (intrel_ss addsimps (add_ac @ [zadd])) 1);
   280 by (asm_simp_tac (!simpset addsimps (add_ac @ [zadd])) 1);
   284 qed "zadd_commute";
   281 qed "zadd_commute";
   285 
   282 
   286 goal Integ.thy "((z1::int) + z2) + z3 = z1 + (z2 + z3)";
   283 goal Integ.thy "((z1::int) + z2) + z3 = z1 + (z2 + z3)";
   287 by (res_inst_tac [("z","z1")] eq_Abs_Integ 1);
   284 by (res_inst_tac [("z","z1")] eq_Abs_Integ 1);
   288 by (res_inst_tac [("z","z2")] eq_Abs_Integ 1);
   285 by (res_inst_tac [("z","z2")] eq_Abs_Integ 1);
   289 by (res_inst_tac [("z","z3")] eq_Abs_Integ 1);
   286 by (res_inst_tac [("z","z3")] eq_Abs_Integ 1);
   290 by (asm_simp_tac (arith_ss addsimps [zadd, add_assoc]) 1);
   287 by (asm_simp_tac (!simpset addsimps [zadd, add_assoc]) 1);
   291 qed "zadd_assoc";
   288 qed "zadd_assoc";
   292 
   289 
   293 (*For AC rewriting*)
   290 (*For AC rewriting*)
   294 goal Integ.thy "(x::int)+(y+z)=y+(x+z)";
   291 goal Integ.thy "(x::int)+(y+z)=y+(x+z)";
   295 by (rtac (zadd_commute RS trans) 1);
   292 by (rtac (zadd_commute RS trans) 1);
   299 
   296 
   300 (*Integer addition is an AC operator*)
   297 (*Integer addition is an AC operator*)
   301 val zadd_ac = [zadd_assoc,zadd_commute,zadd_left_commute];
   298 val zadd_ac = [zadd_assoc,zadd_commute,zadd_left_commute];
   302 
   299 
   303 goalw Integ.thy [znat_def] "$# (m + n) = ($#m) + ($#n)";
   300 goalw Integ.thy [znat_def] "$# (m + n) = ($#m) + ($#n)";
   304 by (asm_simp_tac (arith_ss addsimps [zadd]) 1);
   301 by (asm_simp_tac (!simpset addsimps [zadd]) 1);
   305 qed "znat_add";
   302 qed "znat_add";
   306 
   303 
   307 goalw Integ.thy [znat_def] "z + ($~ z) = $#0";
   304 goalw Integ.thy [znat_def] "z + ($~ z) = $#0";
   308 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   305 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   309 by (asm_simp_tac (intrel_ss addsimps [zminus, zadd, add_commute]) 1);
   306 by (asm_simp_tac (!simpset addsimps [zminus, zadd, add_commute]) 1);
   310 qed "zadd_zminus_inverse";
   307 qed "zadd_zminus_inverse";
   311 
   308 
   312 goal Integ.thy "($~ z) + z = $#0";
   309 goal Integ.thy "($~ z) + z = $#0";
   313 by (rtac (zadd_commute RS trans) 1);
   310 by (rtac (zadd_commute RS trans) 1);
   314 by (rtac zadd_zminus_inverse 1);
   311 by (rtac zadd_zminus_inverse 1);
   325 (**** zmult: multiplication on Integ ****)
   322 (**** zmult: multiplication on Integ ****)
   326 
   323 
   327 (** Congruence property for multiplication **)
   324 (** Congruence property for multiplication **)
   328 
   325 
   329 goal Integ.thy "((k::nat) + l) + (m + n) = (k + m) + (n + l)";
   326 goal Integ.thy "((k::nat) + l) + (m + n) = (k + m) + (n + l)";
   330 by (simp_tac (arith_ss addsimps add_ac) 1);
   327 by (simp_tac (!simpset addsimps add_ac) 1);
   331 qed "zmult_congruent_lemma";
   328 qed "zmult_congruent_lemma";
   332 
   329 
   333 goal Integ.thy 
   330 goal Integ.thy 
   334     "congruent2 intrel (%p1 p2.  		\
   331     "congruent2 intrel (%p1 p2.  		\
   335 \               split (%x1 y1. split (%x2 y2. 	\
   332 \               split (%x1 y1. split (%x2 y2. 	\
   336 \                   intrel^^{(x1*x2 + y1*y2, x1*y2 + y1*x2)}) p2) p1)";
   333 \                   intrel^^{(x1*x2 + y1*y2, x1*y2 + y1*x2)}) p2) p1)";
   337 by (rtac (equiv_intrel RS congruent2_commuteI) 1);
   334 by (rtac (equiv_intrel RS congruent2_commuteI) 1);
   338 by (safe_tac intrel_cs);
   335 by (safe_tac intrel_cs);
   339 by (rewtac split_def);
   336 by (rewtac split_def);
   340 by (simp_tac (arith_ss addsimps add_ac@mult_ac) 1);
   337 by (simp_tac (!simpset addsimps add_ac@mult_ac) 1);
   341 by (asm_simp_tac (arith_ss addsimps add_ac@mult_ac) 1);
   338 by (asm_simp_tac (!simpset delsimps [equiv_intrel_iff]
       
   339                            addsimps add_ac@mult_ac) 1);
   342 by (rtac (intrelI RS(equiv_intrel RS equiv_class_eq)) 1);
   340 by (rtac (intrelI RS(equiv_intrel RS equiv_class_eq)) 1);
   343 by (rtac (zmult_congruent_lemma RS trans) 1);
   341 by (rtac (zmult_congruent_lemma RS trans) 1);
   344 by (rtac (zmult_congruent_lemma RS trans RS sym) 1);
   342 by (rtac (zmult_congruent_lemma RS trans RS sym) 1);
   345 by (rtac (zmult_congruent_lemma RS trans RS sym) 1);
   343 by (rtac (zmult_congruent_lemma RS trans RS sym) 1);
   346 by (rtac (zmult_congruent_lemma RS trans RS sym) 1);
   344 by (rtac (zmult_congruent_lemma RS trans RS sym) 1);
   347 by (asm_simp_tac (HOL_ss addsimps [add_mult_distrib RS sym]) 1);
   345 by (asm_simp_tac (!simpset delsimps [add_mult_distrib]
   348 by (asm_simp_tac (arith_ss addsimps add_ac@mult_ac) 1);
   346                            addsimps [add_mult_distrib RS sym]) 1);
       
   347 by (asm_simp_tac (!simpset addsimps add_ac@mult_ac) 1);
   349 qed "zmult_congruent2";
   348 qed "zmult_congruent2";
   350 
   349 
   351 (*Resolve th against the corresponding facts for zmult*)
   350 (*Resolve th against the corresponding facts for zmult*)
   352 val zmult_ize = RSLIST [equiv_intrel, zmult_congruent2];
   351 val zmult_ize = RSLIST [equiv_intrel, zmult_congruent2];
   353 
   352 
   354 goalw Integ.thy [zmult_def]
   353 goalw Integ.thy [zmult_def]
   355    "Abs_Integ((intrel^^{(x1,y1)})) * Abs_Integ((intrel^^{(x2,y2)})) = 	\
   354    "Abs_Integ((intrel^^{(x1,y1)})) * Abs_Integ((intrel^^{(x2,y2)})) = 	\
   356 \   Abs_Integ(intrel ^^ {(x1*x2 + y1*y2, x1*y2 + y1*x2)})";
   355 \   Abs_Integ(intrel ^^ {(x1*x2 + y1*y2, x1*y2 + y1*x2)})";
   357 by (simp_tac (intrel_ss addsimps [zmult_ize UN_equiv_class2]) 1);
   356 by (simp_tac (!simpset addsimps [zmult_ize UN_equiv_class2]) 1);
   358 qed "zmult";
   357 qed "zmult";
   359 
   358 
   360 goalw Integ.thy [znat_def] "$#0 * z = $#0";
   359 goalw Integ.thy [znat_def] "$#0 * z = $#0";
   361 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   360 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   362 by (asm_simp_tac (arith_ss addsimps [zmult]) 1);
   361 by (asm_simp_tac (!simpset addsimps [zmult]) 1);
   363 qed "zmult_0";
   362 qed "zmult_0";
   364 
   363 
   365 goalw Integ.thy [znat_def] "$#Suc(0) * z = z";
   364 goalw Integ.thy [znat_def] "$#Suc(0) * z = z";
   366 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   365 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   367 by (asm_simp_tac (arith_ss addsimps [zmult, add_0_right]) 1);
   366 by (asm_simp_tac (!simpset addsimps [zmult]) 1);
   368 qed "zmult_1";
   367 qed "zmult_1";
   369 
   368 
   370 goal Integ.thy "($~ z) * w = $~ (z * w)";
   369 goal Integ.thy "($~ z) * w = $~ (z * w)";
   371 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   370 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   372 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   371 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   373 by (asm_simp_tac (intrel_ss addsimps ([zminus, zmult] @ add_ac)) 1);
   372 by (asm_simp_tac (!simpset addsimps ([zminus, zmult] @ add_ac)) 1);
   374 qed "zmult_zminus";
   373 qed "zmult_zminus";
   375 
   374 
   376 
   375 
   377 goal Integ.thy "($~ z) * ($~ w) = (z * w)";
   376 goal Integ.thy "($~ z) * ($~ w) = (z * w)";
   378 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   377 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   379 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   378 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   380 by (asm_simp_tac (intrel_ss addsimps ([zminus, zmult] @ add_ac)) 1);
   379 by (asm_simp_tac (!simpset addsimps ([zminus, zmult] @ add_ac)) 1);
   381 qed "zmult_zminus_zminus";
   380 qed "zmult_zminus_zminus";
   382 
   381 
   383 goal Integ.thy "(z::int) * w = w * z";
   382 goal Integ.thy "(z::int) * w = w * z";
   384 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   383 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   385 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   384 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   386 by (asm_simp_tac (intrel_ss addsimps ([zmult] @ add_ac @ mult_ac)) 1);
   385 by (asm_simp_tac (!simpset addsimps ([zmult] @ add_ac @ mult_ac)) 1);
   387 qed "zmult_commute";
   386 qed "zmult_commute";
   388 
   387 
   389 goal Integ.thy "z * $# 0 = $#0";
   388 goal Integ.thy "z * $# 0 = $#0";
   390 by (rtac ([zmult_commute, zmult_0] MRS trans) 1);
   389 by (rtac ([zmult_commute, zmult_0] MRS trans) 1);
   391 qed "zmult_0_right";
   390 qed "zmult_0_right";
   396 
   395 
   397 goal Integ.thy "((z1::int) * z2) * z3 = z1 * (z2 * z3)";
   396 goal Integ.thy "((z1::int) * z2) * z3 = z1 * (z2 * z3)";
   398 by (res_inst_tac [("z","z1")] eq_Abs_Integ 1);
   397 by (res_inst_tac [("z","z1")] eq_Abs_Integ 1);
   399 by (res_inst_tac [("z","z2")] eq_Abs_Integ 1);
   398 by (res_inst_tac [("z","z2")] eq_Abs_Integ 1);
   400 by (res_inst_tac [("z","z3")] eq_Abs_Integ 1);
   399 by (res_inst_tac [("z","z3")] eq_Abs_Integ 1);
   401 by (asm_simp_tac (intrel_ss addsimps ([zmult] @ add_ac @ mult_ac)) 1);
   400 by (asm_simp_tac (!simpset addsimps ([zmult] @ add_ac @ mult_ac)) 1);
   402 qed "zmult_assoc";
   401 qed "zmult_assoc";
   403 
   402 
   404 (*For AC rewriting*)
   403 (*For AC rewriting*)
   405 qed_goal "zmult_left_commute" Integ.thy
   404 qed_goal "zmult_left_commute" Integ.thy
   406     "(z1::int)*(z2*z3) = z2*(z1*z3)"
   405     "(z1::int)*(z2*z3) = z2*(z1*z3)"
   413 goal Integ.thy "((z1::int) + z2) * w = (z1 * w) + (z2 * w)";
   412 goal Integ.thy "((z1::int) + z2) * w = (z1 * w) + (z2 * w)";
   414 by (res_inst_tac [("z","z1")] eq_Abs_Integ 1);
   413 by (res_inst_tac [("z","z1")] eq_Abs_Integ 1);
   415 by (res_inst_tac [("z","z2")] eq_Abs_Integ 1);
   414 by (res_inst_tac [("z","z2")] eq_Abs_Integ 1);
   416 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   415 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   417 by (asm_simp_tac 
   416 by (asm_simp_tac 
   418     (intrel_ss addsimps ([zadd, zmult, add_mult_distrib] @ 
   417     (!simpset addsimps ([zadd, zmult] @ add_ac @ mult_ac)) 1);
   419 			 add_ac @ mult_ac)) 1);
       
   420 qed "zadd_zmult_distrib";
   418 qed "zadd_zmult_distrib";
   421 
   419 
   422 val zmult_commute'= read_instantiate [("z","w")] zmult_commute;
   420 val zmult_commute'= read_instantiate [("z","w")] zmult_commute;
   423 
   421 
   424 goal Integ.thy "w * ($~ z) = $~ (w * z)";
   422 goal Integ.thy "w * ($~ z) = $~ (w * z)";
   425 by (simp_tac (HOL_ss addsimps [zmult_commute', zmult_zminus]) 1);
   423 by (simp_tac (!simpset addsimps [zmult_commute', zmult_zminus]) 1);
   426 qed "zmult_zminus_right";
   424 qed "zmult_zminus_right";
   427 
   425 
   428 goal Integ.thy "(w::int) * (z1 + z2) = (w * z1) + (w * z2)";
   426 goal Integ.thy "(w::int) * (z1 + z2) = (w * z1) + (w * z2)";
   429 by (simp_tac (HOL_ss addsimps [zmult_commute',zadd_zmult_distrib]) 1);
   427 by (simp_tac (!simpset addsimps [zmult_commute',zadd_zmult_distrib]) 1);
   430 qed "zadd_zmult_distrib2";
   428 qed "zadd_zmult_distrib2";
   431 
   429 
   432 val zadd_simps = 
   430 val zadd_simps = 
   433     [zadd_0, zadd_0_right, zadd_zminus_inverse, zadd_zminus_inverse2];
   431     [zadd_0, zadd_0_right, zadd_zminus_inverse, zadd_zminus_inverse2];
   434 
   432 
   435 val zminus_simps = [zminus_zminus, zminus_0, zminus_zadd_distrib];
   433 val zminus_simps = [zminus_zminus, zminus_0, zminus_zadd_distrib];
   436 
   434 
   437 val zmult_simps = [zmult_0, zmult_1, zmult_0_right, zmult_1_right, 
   435 val zmult_simps = [zmult_0, zmult_1, zmult_0_right, zmult_1_right, 
   438 		   zmult_zminus, zmult_zminus_right];
   436 		   zmult_zminus, zmult_zminus_right];
   439 
   437 
   440 val integ_ss =
   438 Addsimps (zadd_simps @ zminus_simps @ zmult_simps @ 
   441     arith_ss addsimps (zadd_simps @ zminus_simps @ zmult_simps @ 
   439           [zmagnitude_znat, zmagnitude_zminus_znat]);
   442 		       [zmagnitude_znat, zmagnitude_zminus_znat]);
       
   443 
   440 
   444 
   441 
   445 (**** Additional Theorems (by Mattolini; proofs mainly by lcp) ****)
   442 (**** Additional Theorems (by Mattolini; proofs mainly by lcp) ****)
   446 
   443 
   447 (* Some Theorems about zsuc and zpred *)
   444 (* Some Theorems about zsuc and zpred *)
   448 goalw Integ.thy [zsuc_def] "$#(Suc(n)) = zsuc($# n)";
   445 goalw Integ.thy [zsuc_def] "$#(Suc(n)) = zsuc($# n)";
   449 by (simp_tac (arith_ss addsimps [znat_add RS sym]) 1);
   446 by (simp_tac (!simpset addsimps [znat_add RS sym]) 1);
   450 qed "znat_Suc";
   447 qed "znat_Suc";
   451 
   448 
   452 goalw Integ.thy [zpred_def,zsuc_def,zdiff_def] "$~ zsuc(z) = zpred($~ z)";
   449 goalw Integ.thy [zpred_def,zsuc_def,zdiff_def] "$~ zsuc(z) = zpred($~ z)";
   453 by (simp_tac integ_ss 1);
   450 by (Simp_tac 1);
   454 qed "zminus_zsuc";
   451 qed "zminus_zsuc";
   455 
   452 
   456 goalw Integ.thy [zpred_def,zsuc_def,zdiff_def] "$~ zpred(z) = zsuc($~ z)";
   453 goalw Integ.thy [zpred_def,zsuc_def,zdiff_def] "$~ zpred(z) = zsuc($~ z)";
   457 by (simp_tac integ_ss 1);
   454 by (Simp_tac 1);
   458 qed "zminus_zpred";
   455 qed "zminus_zpred";
   459 
   456 
   460 goalw Integ.thy [zsuc_def,zpred_def,zdiff_def]
   457 goalw Integ.thy [zsuc_def,zpred_def,zdiff_def]
   461    "zpred(zsuc(z)) = z";
   458    "zpred(zsuc(z)) = z";
   462 by (simp_tac (integ_ss addsimps [zadd_assoc]) 1);
   459 by (simp_tac (!simpset addsimps [zadd_assoc]) 1);
   463 qed "zpred_zsuc";
   460 qed "zpred_zsuc";
   464 
   461 
   465 goalw Integ.thy [zsuc_def,zpred_def,zdiff_def]
   462 goalw Integ.thy [zsuc_def,zpred_def,zdiff_def]
   466    "zsuc(zpred(z)) = z";
   463    "zsuc(zpred(z)) = z";
   467 by (simp_tac (integ_ss addsimps [zadd_assoc]) 1);
   464 by (simp_tac (!simpset addsimps [zadd_assoc]) 1);
   468 qed "zsuc_zpred";
   465 qed "zsuc_zpred";
   469 
   466 
   470 goal Integ.thy "(zpred(z)=w) = (z=zsuc(w))";
   467 goal Integ.thy "(zpred(z)=w) = (z=zsuc(w))";
   471 by (safe_tac HOL_cs);
   468 by (safe_tac HOL_cs);
   472 by (rtac (zsuc_zpred RS sym) 1);
   469 by (rtac (zsuc_zpred RS sym) 1);
   486 qed "zminus_exchange";
   483 qed "zminus_exchange";
   487 
   484 
   488 goal Integ.thy"(zsuc(z)=zsuc(w)) = (z=w)";
   485 goal Integ.thy"(zsuc(z)=zsuc(w)) = (z=w)";
   489 by (safe_tac intrel_cs);
   486 by (safe_tac intrel_cs);
   490 by (dres_inst_tac [("f","zpred")] arg_cong 1);
   487 by (dres_inst_tac [("f","zpred")] arg_cong 1);
   491 by (asm_full_simp_tac (HOL_ss addsimps [zpred_zsuc]) 1);
   488 by (asm_full_simp_tac (!simpset addsimps [zpred_zsuc]) 1);
   492 qed "bijective_zsuc";
   489 qed "bijective_zsuc";
   493 
   490 
   494 goal Integ.thy"(zpred(z)=zpred(w)) = (z=w)";
   491 goal Integ.thy"(zpred(z)=zpred(w)) = (z=w)";
   495 by (safe_tac intrel_cs);
   492 by (safe_tac intrel_cs);
   496 by (dres_inst_tac [("f","zsuc")] arg_cong 1);
   493 by (dres_inst_tac [("f","zsuc")] arg_cong 1);
   497 by (asm_full_simp_tac (HOL_ss addsimps [zsuc_zpred]) 1);
   494 by (asm_full_simp_tac (!simpset addsimps [zsuc_zpred]) 1);
   498 qed "bijective_zpred";
   495 qed "bijective_zpred";
   499 
   496 
   500 (* Additional Theorems about zadd *)
   497 (* Additional Theorems about zadd *)
   501 
   498 
   502 goalw Integ.thy [zsuc_def] "zsuc(z) + w = zsuc(z+w)";
   499 goalw Integ.thy [zsuc_def] "zsuc(z) + w = zsuc(z+w)";
   503 by (simp_tac (arith_ss addsimps zadd_ac) 1);
   500 by (simp_tac (!simpset addsimps zadd_ac) 1);
   504 qed "zadd_zsuc";
   501 qed "zadd_zsuc";
   505 
   502 
   506 goalw Integ.thy [zsuc_def] "w + zsuc(z) = zsuc(w+z)";
   503 goalw Integ.thy [zsuc_def] "w + zsuc(z) = zsuc(w+z)";
   507 by (simp_tac (arith_ss addsimps zadd_ac) 1);
   504 by (simp_tac (!simpset addsimps zadd_ac) 1);
   508 qed "zadd_zsuc_right";
   505 qed "zadd_zsuc_right";
   509 
   506 
   510 goalw Integ.thy [zpred_def,zdiff_def] "zpred(z) + w = zpred(z+w)";
   507 goalw Integ.thy [zpred_def,zdiff_def] "zpred(z) + w = zpred(z+w)";
   511 by (simp_tac (arith_ss addsimps zadd_ac) 1);
   508 by (simp_tac (!simpset addsimps zadd_ac) 1);
   512 qed "zadd_zpred";
   509 qed "zadd_zpred";
   513 
   510 
   514 goalw Integ.thy [zpred_def,zdiff_def] "w + zpred(z) = zpred(w+z)";
   511 goalw Integ.thy [zpred_def,zdiff_def] "w + zpred(z) = zpred(w+z)";
   515 by (simp_tac (arith_ss addsimps zadd_ac) 1);
   512 by (simp_tac (!simpset addsimps zadd_ac) 1);
   516 qed "zadd_zpred_right";
   513 qed "zadd_zpred_right";
   517 
   514 
   518 
   515 
   519 (* Additional Theorems about zmult *)
   516 (* Additional Theorems about zmult *)
   520 
   517 
   521 goalw Integ.thy [zsuc_def] "zsuc(w) * z = z + w * z";
   518 goalw Integ.thy [zsuc_def] "zsuc(w) * z = z + w * z";
   522 by (simp_tac (integ_ss addsimps [zadd_zmult_distrib, zadd_commute]) 1);
   519 by (simp_tac (!simpset addsimps [zadd_zmult_distrib, zadd_commute]) 1);
   523 qed "zmult_zsuc";
   520 qed "zmult_zsuc";
   524 
   521 
   525 goalw Integ.thy [zsuc_def] "z * zsuc(w) = z + w * z";
   522 goalw Integ.thy [zsuc_def] "z * zsuc(w) = z + w * z";
   526 by (simp_tac 
   523 by (simp_tac 
   527     (integ_ss addsimps [zadd_zmult_distrib2, zadd_commute, zmult_commute]) 1);
   524     (!simpset addsimps [zadd_zmult_distrib2, zadd_commute, zmult_commute]) 1);
   528 qed "zmult_zsuc_right";
   525 qed "zmult_zsuc_right";
   529 
   526 
   530 goalw Integ.thy [zpred_def, zdiff_def] "zpred(w) * z = w * z - z";
   527 goalw Integ.thy [zpred_def, zdiff_def] "zpred(w) * z = w * z - z";
   531 by (simp_tac (integ_ss addsimps [zadd_zmult_distrib]) 1);
   528 by (simp_tac (!simpset addsimps [zadd_zmult_distrib]) 1);
   532 qed "zmult_zpred";
   529 qed "zmult_zpred";
   533 
   530 
   534 goalw Integ.thy [zpred_def, zdiff_def] "z * zpred(w) = w * z - z";
   531 goalw Integ.thy [zpred_def, zdiff_def] "z * zpred(w) = w * z - z";
   535 by (simp_tac (integ_ss addsimps [zadd_zmult_distrib2, zmult_commute]) 1);
   532 by (simp_tac (!simpset addsimps [zadd_zmult_distrib2, zmult_commute]) 1);
   536 qed "zmult_zpred_right";
   533 qed "zmult_zpred_right";
   537 
   534 
   538 (* Further Theorems about zsuc and zpred *)
   535 (* Further Theorems about zsuc and zpred *)
   539 goal Integ.thy "$#Suc(m) ~= $#0";
   536 goal Integ.thy "$#Suc(m) ~= $#0";
   540 by (simp_tac (integ_ss addsimps [inj_znat RS inj_eq]) 1);
   537 by (simp_tac (!simpset addsimps [inj_znat RS inj_eq]) 1);
   541 qed "znat_Suc_not_znat_Zero";
   538 qed "znat_Suc_not_znat_Zero";
   542 
   539 
   543 bind_thm ("znat_Zero_not_znat_Suc", (znat_Suc_not_znat_Zero RS not_sym));
   540 bind_thm ("znat_Zero_not_znat_Suc", (znat_Suc_not_znat_Zero RS not_sym));
   544 
   541 
   545 
   542 
   546 goalw Integ.thy [zsuc_def,znat_def] "w ~= zsuc(w)";
   543 goalw Integ.thy [zsuc_def,znat_def] "w ~= zsuc(w)";
   547 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   544 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   548 by (asm_full_simp_tac (intrel_ss addsimps [zadd]) 1);
   545 by (asm_full_simp_tac (!simpset addsimps [zadd]) 1);
   549 qed "n_not_zsuc_n";
   546 qed "n_not_zsuc_n";
   550 
   547 
   551 val zsuc_n_not_n = n_not_zsuc_n RS not_sym;
   548 val zsuc_n_not_n = n_not_zsuc_n RS not_sym;
   552 
   549 
   553 goal Integ.thy "w ~= zpred(w)";
   550 goal Integ.thy "w ~= zpred(w)";
   554 by (safe_tac HOL_cs);
   551 by (safe_tac HOL_cs);
   555 by (dres_inst_tac [("x","w"),("f","zsuc")] arg_cong 1);
   552 by (dres_inst_tac [("x","w"),("f","zsuc")] arg_cong 1);
   556 by (asm_full_simp_tac (HOL_ss addsimps [zsuc_zpred,zsuc_n_not_n]) 1);
   553 by (asm_full_simp_tac (!simpset addsimps [zsuc_zpred,zsuc_n_not_n]) 1);
   557 qed "n_not_zpred_n";
   554 qed "n_not_zpred_n";
   558 
   555 
   559 val zpred_n_not_n = n_not_zpred_n RS not_sym;
   556 val zpred_n_not_n = n_not_zpred_n RS not_sym;
   560 
   557 
   561 
   558 
   564 goalw Integ.thy [zless_def, znegative_def, zdiff_def, znat_def] 
   561 goalw Integ.thy [zless_def, znegative_def, zdiff_def, znat_def] 
   565     "!!w. w<z ==> ? n. z = w + $#(Suc(n))";
   562     "!!w. w<z ==> ? n. z = w + $#(Suc(n))";
   566 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   563 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   567 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   564 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   568 by (safe_tac intrel_cs);
   565 by (safe_tac intrel_cs);
   569 by (asm_full_simp_tac (intrel_ss addsimps [zadd, zminus]) 1);
   566 by (asm_full_simp_tac (!simpset addsimps [zadd, zminus]) 1);
   570 by (safe_tac (intrel_cs addSDs [less_eq_Suc_add]));
   567 by (safe_tac (intrel_cs addSDs [less_eq_Suc_add]));
   571 by (res_inst_tac [("x","k")] exI 1);
   568 by (res_inst_tac [("x","k")] exI 1);
   572 by (asm_full_simp_tac (HOL_ss addsimps ([add_Suc RS sym] @ add_ac)) 1);
   569 by (asm_full_simp_tac (!simpset delsimps [add_Suc, add_Suc_right]
       
   570                                 addsimps ([add_Suc RS sym] @ add_ac)) 1);
   573 (*To cancel x2, rename it to be first!*)
   571 (*To cancel x2, rename it to be first!*)
   574 by (rename_tac "a b c" 1);
   572 by (rename_tac "a b c" 1);
   575 by (asm_full_simp_tac (HOL_ss addsimps (add_left_cancel::add_ac)) 1);
   573 by (asm_full_simp_tac (!simpset delsimps [add_Suc_right]
       
   574                                 addsimps (add_left_cancel::add_ac)) 1);
   576 qed "zless_eq_zadd_Suc";
   575 qed "zless_eq_zadd_Suc";
   577 
   576 
   578 goalw Integ.thy [zless_def, znegative_def, zdiff_def, znat_def] 
   577 goalw Integ.thy [zless_def, znegative_def, zdiff_def, znat_def] 
   579     "z < z + $#(Suc(n))";
   578     "z < z + $#(Suc(n))";
   580 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   579 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   581 by (safe_tac intrel_cs);
   580 by (safe_tac intrel_cs);
   582 by (simp_tac (intrel_ss addsimps [zadd, zminus]) 1);
   581 by (simp_tac (!simpset addsimps [zadd, zminus]) 1);
   583 by (REPEAT_SOME (ares_tac [refl, exI, singletonI, ImageI, conjI, intrelI]));
   582 by (REPEAT_SOME (ares_tac [refl, exI, singletonI, ImageI, conjI, intrelI]));
   584 by (rtac le_less_trans 1);
   583 by (rtac le_less_trans 1);
   585 by (rtac lessI 2);
   584 by (rtac lessI 2);
   586 by (asm_simp_tac (arith_ss addsimps ([le_add1,add_left_cancel_le]@add_ac)) 1);
   585 by (asm_simp_tac (!simpset addsimps ([le_add1,add_left_cancel_le]@add_ac)) 1);
   587 qed "zless_zadd_Suc";
   586 qed "zless_zadd_Suc";
   588 
   587 
   589 goal Integ.thy "!!z1 z2 z3. [| z1<z2; z2<z3 |] ==> z1 < (z3::int)";
   588 goal Integ.thy "!!z1 z2 z3. [| z1<z2; z2<z3 |] ==> z1 < (z3::int)";
   590 by (safe_tac (HOL_cs addSDs [zless_eq_zadd_Suc]));
   589 by (safe_tac (HOL_cs addSDs [zless_eq_zadd_Suc]));
   591 by (simp_tac 
   590 by (simp_tac 
   592     (arith_ss addsimps [zadd_assoc, zless_zadd_Suc, znat_add RS sym]) 1);
   591     (!simpset addsimps [zadd_assoc, zless_zadd_Suc, znat_add RS sym]) 1);
   593 qed "zless_trans";
   592 qed "zless_trans";
   594 
   593 
   595 goalw Integ.thy [zsuc_def] "z<zsuc(z)";
   594 goalw Integ.thy [zsuc_def] "z<zsuc(z)";
   596 by (rtac zless_zadd_Suc 1);
   595 by (rtac zless_zadd_Suc 1);
   597 qed "zlessI";
   596 qed "zlessI";
   600 
   599 
   601 goal Integ.thy "!!z w::int. z<w ==> ~w<z";
   600 goal Integ.thy "!!z w::int. z<w ==> ~w<z";
   602 by (safe_tac (HOL_cs addSDs [zless_eq_zadd_Suc]));
   601 by (safe_tac (HOL_cs addSDs [zless_eq_zadd_Suc]));
   603 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   602 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   604 by (safe_tac intrel_cs);
   603 by (safe_tac intrel_cs);
   605 by (asm_full_simp_tac (intrel_ss addsimps ([znat_def, zadd])) 1);
   604 by (asm_full_simp_tac (!simpset addsimps ([znat_def, zadd])) 1);
   606 by (asm_full_simp_tac
   605 by (asm_full_simp_tac
   607  (HOL_ss addsimps [add_left_cancel, add_assoc, add_Suc_right RS sym]) 1);
   606  (!simpset delsimps [add_Suc_right] addsimps [add_left_cancel, add_assoc, add_Suc_right RS sym]) 1);
   608 by (resolve_tac [less_not_refl2 RS notE] 1);
   607 by (resolve_tac [less_not_refl2 RS notE] 1);
   609 by (etac sym 2);
   608 by (etac sym 2);
   610 by (REPEAT (resolve_tac [lessI, trans_less_add2, less_SucI] 1));
   609 by (REPEAT (resolve_tac [lessI, trans_less_add2, less_SucI] 1));
   611 qed "zless_not_sym";
   610 qed "zless_not_sym";
   612 
   611 
   631     "z<w | z=w | w<(z::int)";
   630     "z<w | z=w | w<(z::int)";
   632 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   631 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   633 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   632 by (res_inst_tac [("z","w")] eq_Abs_Integ 1);
   634 by (safe_tac intrel_cs);
   633 by (safe_tac intrel_cs);
   635 by (asm_full_simp_tac
   634 by (asm_full_simp_tac
   636     (intrel_ss addsimps [zadd, zminus, Image_iff, Bex_def]) 1);
   635     (!simpset addsimps [zadd, zminus, Image_iff, Bex_def]) 1);
   637 by (res_inst_tac [("m1", "x+ya"), ("n1", "xa+y")] (less_linear RS disjE) 1);
   636 by (res_inst_tac [("m1", "x+ya"), ("n1", "xa+y")] (less_linear RS disjE) 1);
   638 by (etac disjE 2);
   637 by (etac disjE 2);
   639 by (assume_tac 2);
   638 by (assume_tac 2);
   640 by (DEPTH_SOLVE
   639 by (DEPTH_SOLVE
   641     (swap_res_tac [exI] 1 THEN 
   640     (swap_res_tac [exI] 1 THEN 
   642      swap_res_tac [exI] 1 THEN 
   641      swap_res_tac [exI] 1 THEN 
   643      etac conjI 1 THEN 
   642      etac conjI 1 THEN 
   644      simp_tac (arith_ss addsimps add_ac)  1));
   643      simp_tac (!simpset addsimps add_ac)  1));
   645 qed "zless_linear";
   644 qed "zless_linear";
   646 
   645 
   647 
   646 
   648 (*** Properties of <= ***)
   647 (*** Properties of <= ***)
   649 
   648 
   650 goalw Integ.thy  [zless_def, znegative_def, zdiff_def, znat_def]
   649 goalw Integ.thy  [zless_def, znegative_def, zdiff_def, znat_def]
   651     "($#m < $#n) = (m<n)";
   650     "($#m < $#n) = (m<n)";
   652 by (simp_tac
   651 by (simp_tac
   653     (intrel_ss addsimps [zadd, zminus, Image_iff, Bex_def]) 1);
   652     (!simpset addsimps [zadd, zminus, Image_iff, Bex_def]) 1);
   654 by (fast_tac (HOL_cs addIs [add_commute] addSEs [less_add_eq_less]) 1);
   653 by (fast_tac (HOL_cs addIs [add_commute] addSEs [less_add_eq_less]) 1);
   655 qed "zless_eq_less";
   654 qed "zless_eq_less";
   656 
   655 
   657 goalw Integ.thy [zle_def, le_def] "($#m <= $#n) = (m<=n)";
   656 goalw Integ.thy [zle_def, le_def] "($#m <= $#n) = (m<=n)";
   658 by (simp_tac (HOL_ss addsimps [zless_eq_less]) 1);
   657 by (simp_tac (!simpset addsimps [zless_eq_less]) 1);
   659 qed "zle_eq_le";
   658 qed "zle_eq_le";
   660 
   659 
   661 goalw Integ.thy [zle_def] "!!w. ~(w<z) ==> z<=(w::int)";
   660 goalw Integ.thy [zle_def] "!!w. ~(w<z) ==> z<=(w::int)";
   662 by (assume_tac 1);
   661 by (assume_tac 1);
   663 qed "zleI";
   662 qed "zleI";
   689 goal Integ.thy "(x <= (y::int)) = (x < y | x=y)";
   688 goal Integ.thy "(x <= (y::int)) = (x < y | x=y)";
   690 by (REPEAT(ares_tac [iffI, zless_or_eq_imp_zle, zle_imp_zless_or_eq] 1));
   689 by (REPEAT(ares_tac [iffI, zless_or_eq_imp_zle, zle_imp_zless_or_eq] 1));
   691 qed "zle_eq_zless_or_eq";
   690 qed "zle_eq_zless_or_eq";
   692 
   691 
   693 goal Integ.thy "w <= (w::int)";
   692 goal Integ.thy "w <= (w::int)";
   694 by (simp_tac (HOL_ss addsimps [zle_eq_zless_or_eq]) 1);
   693 by (simp_tac (!simpset addsimps [zle_eq_zless_or_eq]) 1);
   695 qed "zle_refl";
   694 qed "zle_refl";
   696 
   695 
   697 val prems = goal Integ.thy "!!i. [| i <= j; j < k |] ==> i < (k::int)";
   696 val prems = goal Integ.thy "!!i. [| i <= j; j < k |] ==> i < (k::int)";
   698 by (dtac zle_imp_zless_or_eq 1);
   697 by (dtac zle_imp_zless_or_eq 1);
   699 by (fast_tac (HOL_cs addIs [zless_trans]) 1);
   698 by (fast_tac (HOL_cs addIs [zless_trans]) 1);
   710 qed "zle_anti_sym";
   709 qed "zle_anti_sym";
   711 
   710 
   712 
   711 
   713 goal Integ.thy "!!w w' z::int. z + w' = z + w ==> w' = w";
   712 goal Integ.thy "!!w w' z::int. z + w' = z + w ==> w' = w";
   714 by (dres_inst_tac [("f", "%x. x + $~z")] arg_cong 1);
   713 by (dres_inst_tac [("f", "%x. x + $~z")] arg_cong 1);
   715 by (asm_full_simp_tac (integ_ss addsimps zadd_ac) 1);
   714 by (asm_full_simp_tac (!simpset addsimps zadd_ac) 1);
   716 qed "zadd_left_cancel";
   715 qed "zadd_left_cancel";
   717 
   716 
   718 
   717 
   719 (*** Monotonicity results ***)
   718 (*** Monotonicity results ***)
   720 
   719 
   721 goal Integ.thy "!!v w z::int. v < w ==> v + z < w + z";
   720 goal Integ.thy "!!v w z::int. v < w ==> v + z < w + z";
   722 by (safe_tac (HOL_cs addSDs [zless_eq_zadd_Suc]));
   721 by (safe_tac (HOL_cs addSDs [zless_eq_zadd_Suc]));
   723 by (simp_tac (HOL_ss addsimps zadd_ac) 1);
   722 by (simp_tac (!simpset addsimps zadd_ac) 1);
   724 by (simp_tac (HOL_ss addsimps [zadd_assoc RS sym, zless_zadd_Suc]) 1);
   723 by (simp_tac (!simpset addsimps [zadd_assoc RS sym, zless_zadd_Suc]) 1);
   725 qed "zadd_zless_mono1";
   724 qed "zadd_zless_mono1";
   726 
   725 
   727 goal Integ.thy "!!v w z::int. (v+z < w+z) = (v < w)";
   726 goal Integ.thy "!!v w z::int. (v+z < w+z) = (v < w)";
   728 by (safe_tac (HOL_cs addSEs [zadd_zless_mono1]));
   727 by (safe_tac (HOL_cs addSEs [zadd_zless_mono1]));
   729 by (dres_inst_tac [("z", "$~z")] zadd_zless_mono1 1);
   728 by (dres_inst_tac [("z", "$~z")] zadd_zless_mono1 1);
   730 by (asm_full_simp_tac (integ_ss addsimps [zadd_assoc]) 1);
   729 by (asm_full_simp_tac (!simpset addsimps [zadd_assoc]) 1);
   731 qed "zadd_left_cancel_zless";
   730 qed "zadd_left_cancel_zless";
   732 
   731 
   733 goal Integ.thy "!!v w z::int. (v+z <= w+z) = (v <= w)";
   732 goal Integ.thy "!!v w z::int. (v+z <= w+z) = (v <= w)";
   734 by (asm_full_simp_tac
   733 by (asm_full_simp_tac
   735     (integ_ss addsimps [zle_def, zadd_left_cancel_zless]) 1);
   734     (!simpset addsimps [zle_def, zadd_left_cancel_zless]) 1);
   736 qed "zadd_left_cancel_zle";
   735 qed "zadd_left_cancel_zle";
   737 
   736 
   738 (*"v<=w ==> v+z <= w+z"*)
   737 (*"v<=w ==> v+z <= w+z"*)
   739 bind_thm ("zadd_zle_mono1", zadd_left_cancel_zle RS iffD2);
   738 bind_thm ("zadd_zle_mono1", zadd_left_cancel_zle RS iffD2);
   740 
   739 
   741 
   740 
   742 goal Integ.thy "!!z' z::int. [| w'<=w; z'<=z |] ==> w' + z' <= w + z";
   741 goal Integ.thy "!!z' z::int. [| w'<=w; z'<=z |] ==> w' + z' <= w + z";
   743 by (etac (zadd_zle_mono1 RS zle_trans) 1);
   742 by (etac (zadd_zle_mono1 RS zle_trans) 1);
   744 by (simp_tac (HOL_ss addsimps [zadd_commute]) 1);
   743 by (simp_tac (!simpset addsimps [zadd_commute]) 1);
   745 (*w moves to the end because it is free while z', z are bound*)
   744 (*w moves to the end because it is free while z', z are bound*)
   746 by (etac zadd_zle_mono1 1);
   745 by (etac zadd_zle_mono1 1);
   747 qed "zadd_zle_mono";
   746 qed "zadd_zle_mono";
   748 
   747 
   749 goal Integ.thy "!!w z::int. z<=$#0 ==> w+z <= w";
   748 goal Integ.thy "!!w z::int. z<=$#0 ==> w+z <= w";
   750 by (dres_inst_tac [("z", "w")] zadd_zle_mono1 1);
   749 by (dres_inst_tac [("z", "w")] zadd_zle_mono1 1);
   751 by (asm_full_simp_tac (integ_ss addsimps [zadd_commute]) 1);
   750 by (asm_full_simp_tac (!simpset addsimps [zadd_commute]) 1);
   752 qed "zadd_zle_self";
   751 qed "zadd_zle_self";