src/ZF/Arith.ML
changeset 1623 2b8573c1b1c1
parent 1609 5324067d993f
child 1708 8f782b919043
equal deleted inserted replaced
1622:4b0608ce6150 1623:2b8573c1b1c1
   345 goal Arith.thy
   345 goal Arith.thy
   346     "!!m n. [| 0<n;  m:nat;  n:nat |] ==> \
   346     "!!m n. [| 0<n;  m:nat;  n:nat |] ==> \
   347 \           succ(m) mod n = if(succ(m mod n) = n, 0, succ(m mod n))";
   347 \           succ(m) mod n = if(succ(m mod n) = n, 0, succ(m mod n))";
   348 by (etac complete_induct 1);
   348 by (etac complete_induct 1);
   349 by (excluded_middle_tac "succ(x)<n" 1);
   349 by (excluded_middle_tac "succ(x)<n" 1);
   350 (*case x<n*)
   350 (* case succ(x) < n *)
   351 by (asm_simp_tac (arith_ss addsimps [mod_less, nat_le_refl RS lt_trans,
   351 by (asm_simp_tac (arith_ss addsimps [mod_less, nat_le_refl RS lt_trans,
   352 				     succ_neq_self]) 2);
   352                                      succ_neq_self]) 2);
   353 by (asm_simp_tac (arith_ss addsimps [ltD RS mem_imp_not_eq]) 2);
   353 by (asm_simp_tac (arith_ss addsimps [ltD RS mem_imp_not_eq]) 2);
   354 (*case n le x*)
   354 (* case n le succ(x) *)
   355 by (asm_full_simp_tac
   355 by (asm_full_simp_tac
   356      (arith_ss addsimps [not_lt_iff_le, nat_into_Ord, mod_geq]) 1);
   356      (arith_ss addsimps [not_lt_iff_le, nat_into_Ord, mod_geq]) 1);
   357 be leE 1;
   357 by (etac leE 1);
   358 by (asm_simp_tac (arith_ss addsimps [div_termination RS ltD, diff_succ, 
   358 by (asm_simp_tac (arith_ss addsimps [div_termination RS ltD, diff_succ, 
   359 				     mod_geq]) 1);
   359                                      mod_geq]) 1);
   360 by (asm_simp_tac (arith_ss addsimps [mod_less, diff_self_eq_0]) 1);
   360 by (asm_simp_tac (arith_ss addsimps [mod_less, diff_self_eq_0]) 1);
   361 qed "mod_succ";
   361 qed "mod_succ";
   362 
   362 
   363 goal Arith.thy "!!m n. [| 0<n;  m:nat;  n:nat |] ==> m mod n < n";
   363 goal Arith.thy "!!m n. [| 0<n;  m:nat;  n:nat |] ==> m mod n < n";
   364 by (etac complete_induct 1);
   364 by (etac complete_induct 1);
   374 
   374 
   375 goal Arith.thy
   375 goal Arith.thy
   376     "!!k b. [| k: nat; b<2 |] ==> k mod 2 = b | k mod 2 = if(b=1,0,1)";
   376     "!!k b. [| k: nat; b<2 |] ==> k mod 2 = b | k mod 2 = if(b=1,0,1)";
   377 by (subgoal_tac "k mod 2: 2" 1);
   377 by (subgoal_tac "k mod 2: 2" 1);
   378 by (asm_simp_tac (arith_ss addsimps [mod_less_divisor RS ltD]) 2);
   378 by (asm_simp_tac (arith_ss addsimps [mod_less_divisor RS ltD]) 2);
   379 by (dresolve_tac [ltD] 1);
   379 by (dtac ltD 1);
   380 by (asm_simp_tac (ZF_ss setloop split_tac [expand_if]) 1);
   380 by (asm_simp_tac (ZF_ss setloop split_tac [expand_if]) 1);
   381 by (fast_tac ZF_cs 1);
   381 by (fast_tac ZF_cs 1);
   382 qed "mod2_cases";
   382 qed "mod2_cases";
   383 
   383 
   384 goal Arith.thy "!!m. m:nat ==> succ(succ(m)) mod 2 = m mod 2";
   384 goal Arith.thy "!!m. m:nat ==> succ(succ(m)) mod 2 = m mod 2";
   386 by (asm_simp_tac (arith_ss addsimps [mod_less_divisor RS ltD]) 2);
   386 by (asm_simp_tac (arith_ss addsimps [mod_less_divisor RS ltD]) 2);
   387 by (asm_simp_tac (arith_ss addsimps [mod_succ] setloop step_tac ZF_cs) 1);
   387 by (asm_simp_tac (arith_ss addsimps [mod_succ] setloop step_tac ZF_cs) 1);
   388 qed "mod2_succ_succ";
   388 qed "mod2_succ_succ";
   389 
   389 
   390 goal Arith.thy "!!m. m:nat ==> (m#+m) mod 2 = 0";
   390 goal Arith.thy "!!m. m:nat ==> (m#+m) mod 2 = 0";
   391 by (eresolve_tac [nat_induct] 1);
   391 by (etac nat_induct 1);
   392 by (simp_tac (arith_ss addsimps [mod_less]) 1);
   392 by (simp_tac (arith_ss addsimps [mod_less]) 1);
   393 by (asm_simp_tac (arith_ss addsimps [mod2_succ_succ, add_succ_right]) 1);
   393 by (asm_simp_tac (arith_ss addsimps [mod2_succ_succ, add_succ_right]) 1);
   394 qed "mod2_add_self";
   394 qed "mod2_add_self";
   395 
   395 
   396 
   396 
   454 by (REPEAT (eresolve_tac [asm_rl, lt_nat_in_nat, nat_succI] 1));
   454 by (REPEAT (eresolve_tac [asm_rl, lt_nat_in_nat, nat_succI] 1));
   455 qed "add_le_mono";
   455 qed "add_le_mono";
   456 
   456 
   457 val arith_ss0 = arith_ss
   457 val arith_ss0 = arith_ss
   458 and arith_ss = arith_ss addsimps [add_0_right, add_succ_right,
   458 and arith_ss = arith_ss addsimps [add_0_right, add_succ_right,
   459 				  mult_0_right, mult_succ_right,
   459                                   mult_0_right, mult_succ_right,
   460 				  mod_less, mod_geq, div_less, div_geq];
   460                                   mod_less, mod_geq, div_less, div_geq];