src/HOL/Divides.ML
changeset 5983 79e301a6a51b
parent 5537 c2bd39a2c0ee
child 6073 fba734ba6894
equal deleted inserted replaced
5982:aeb97860d352 5983:79e301a6a51b
   174 Goal "0<k ==> ALL m. m <= n --> (m div k) <= (n div k)";
   174 Goal "0<k ==> ALL m. m <= n --> (m div k) <= (n div k)";
   175 by (res_inst_tac [("n","n")] less_induct 1);
   175 by (res_inst_tac [("n","n")] less_induct 1);
   176 by (Clarify_tac 1);
   176 by (Clarify_tac 1);
   177 by (case_tac "n<k" 1);
   177 by (case_tac "n<k" 1);
   178 (* 1  case n<k *)
   178 (* 1  case n<k *)
   179 by (subgoal_tac "m<k" 1);
       
   180 by (asm_simp_tac (simpset() addsimps [div_less]) 1);
   179 by (asm_simp_tac (simpset() addsimps [div_less]) 1);
   181 by (trans_tac 1);
       
   182 (* 2  case n >= k *)
   180 (* 2  case n >= k *)
   183 by (case_tac "m<k" 1);
   181 by (case_tac "m<k" 1);
   184 (* 2.1  case m<k *)
   182 (* 2.1  case m<k *)
   185 by (asm_simp_tac (simpset() addsimps [div_less]) 1);
   183 by (asm_simp_tac (simpset() addsimps [div_less]) 1);
   186 (* 2.2  case m>=k *)
   184 (* 2.2  case m>=k *)
   189 
   187 
   190 
   188 
   191 (* Antimonotonicity of div in second argument *)
   189 (* Antimonotonicity of div in second argument *)
   192 Goal "[| 0<m; m<=n |] ==> (k div n) <= (k div m)";
   190 Goal "[| 0<m; m<=n |] ==> (k div n) <= (k div m)";
   193 by (subgoal_tac "0<n" 1);
   191 by (subgoal_tac "0<n" 1);
   194  by (trans_tac 2);
   192  by (Simp_tac 2);
   195 by (res_inst_tac [("n","k")] less_induct 1);
   193 by (res_inst_tac [("n","k")] less_induct 1);
   196 by (Simp_tac 1);
   194 by (Simp_tac 1);
   197 by (rename_tac "k" 1);
   195 by (rename_tac "k" 1);
   198 by (case_tac "k<n" 1);
   196 by (case_tac "k<n" 1);
   199  by (asm_simp_tac (simpset() addsimps [div_less]) 1);
   197  by (asm_simp_tac (simpset() addsimps [div_less]) 1);
   200 by (subgoal_tac "~(k<m)" 1);
   198 by (subgoal_tac "~(k<m)" 1);
   201  by (trans_tac 2);
   199  by (Simp_tac 2);
   202 by (asm_simp_tac (simpset() addsimps [div_geq]) 1);
   200 by (asm_simp_tac (simpset() addsimps [div_geq]) 1);
   203 by (subgoal_tac "(k-n) div n <= (k-m) div n" 1);
   201 by (subgoal_tac "(k-n) div n <= (k-m) div n" 1);
   204 by (REPEAT (eresolve_tac [div_le_mono,diff_le_mono2] 2));
   202 by (REPEAT (eresolve_tac [div_le_mono,diff_le_mono2] 2));
   205 by (rtac le_trans 1);
   203 by (rtac le_trans 1);
   206 by (Asm_simp_tac 1);
   204 by (Asm_simp_tac 1);
   209 
   207 
   210 Goal "0<n ==> m div n <= m";
   208 Goal "0<n ==> m div n <= m";
   211 by (subgoal_tac "m div n <= m div 1" 1);
   209 by (subgoal_tac "m div n <= m div 1" 1);
   212 by (Asm_full_simp_tac 1);
   210 by (Asm_full_simp_tac 1);
   213 by (rtac div_le_mono2 1);
   211 by (rtac div_le_mono2 1);
   214 by (ALLGOALS trans_tac);
   212 by (ALLGOALS Simp_tac);
   215 qed "div_le_dividend";
   213 qed "div_le_dividend";
   216 Addsimps [div_le_dividend];
   214 Addsimps [div_le_dividend];
   217 
   215 
   218 (* Similar for "less than" *)
   216 (* Similar for "less than" *)
   219 Goal "1<n ==> (0 < m) --> (m div n < m)";
   217 Goal "1<n ==> (0 < m) --> (m div n < m)";
   221 by (Simp_tac 1);
   219 by (Simp_tac 1);
   222 by (rename_tac "m" 1);
   220 by (rename_tac "m" 1);
   223 by (case_tac "m<n" 1);
   221 by (case_tac "m<n" 1);
   224  by (asm_full_simp_tac (simpset() addsimps [div_less]) 1);
   222  by (asm_full_simp_tac (simpset() addsimps [div_less]) 1);
   225 by (subgoal_tac "0<n" 1);
   223 by (subgoal_tac "0<n" 1);
   226  by (trans_tac 2);
   224  by (Simp_tac 2);
   227 by (asm_full_simp_tac (simpset() addsimps [div_geq]) 1);
   225 by (asm_full_simp_tac (simpset() addsimps [div_geq]) 1);
   228 by (case_tac "n<m" 1);
   226 by (case_tac "n<m" 1);
   229  by (subgoal_tac "(m-n) div n < (m-n)" 1);
   227  by (subgoal_tac "(m-n) div n < (m-n)" 1);
   230   by (REPEAT (ares_tac [impI,less_trans_Suc] 1));
   228   by (REPEAT (ares_tac [impI,less_trans_Suc] 1));
   231   by (asm_full_simp_tac (simpset() addsimps [diff_less]) 1);
   229   by (asm_full_simp_tac (simpset() addsimps [diff_less]) 1);
   232  by (asm_full_simp_tac (simpset() addsimps [diff_less]) 1);
   230  by (asm_full_simp_tac (simpset() addsimps [diff_less]) 1);
   233 (* case n=m *)
   231 (* case n=m *)
   234 by (subgoal_tac "m=n" 1);
   232 by (subgoal_tac "m=n" 1);
   235  by (trans_tac 2);
   233  by (Simp_tac 2);
   236 by (asm_simp_tac (simpset() addsimps [div_less]) 1);
   234 by (asm_simp_tac (simpset() addsimps [div_less]) 1);
   237 qed_spec_mp "div_less_dividend";
   235 qed_spec_mp "div_less_dividend";
   238 Addsimps [div_less_dividend];
   236 Addsimps [div_less_dividend];
   239 
   237 
   240 (*** Further facts about mod (mainly for the mutilated chess board ***)
   238 (*** Further facts about mod (mainly for the mutilated chess board ***)