src/HOL/Integ/Integ.ML
changeset 5143 b94cd208f073
parent 5069 3ea049f7979d
child 5148 74919e8f221c
equal deleted inserted replaced
5142:c56aa8b59dc0 5143:b94cd208f073
   566 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   566 by (res_inst_tac [("z","z")] eq_Abs_Integ 1);
   567 by (Clarify_tac 1);
   567 by (Clarify_tac 1);
   568 by (simp_tac (simpset() addsimps [zadd, zminus]) 1);
   568 by (simp_tac (simpset() addsimps [zadd, zminus]) 1);
   569 qed "zless_zadd_Suc";
   569 qed "zless_zadd_Suc";
   570 
   570 
   571 Goal "!!z1 z2 z3. [| z1<z2; z2<z3 |] ==> z1 < (z3::int)";
   571 Goal "[| z1<z2; z2<z3 |] ==> z1 < (z3::int)";
   572 by (safe_tac (claset() addSDs [zless_eq_zadd_Suc]));
   572 by (safe_tac (claset() addSDs [zless_eq_zadd_Suc]));
   573 by (simp_tac 
   573 by (simp_tac 
   574     (simpset() addsimps [zadd_assoc, zless_zadd_Suc, znat_add RS sym]) 1);
   574     (simpset() addsimps [zadd_assoc, zless_zadd_Suc, znat_add RS sym]) 1);
   575 qed "zless_trans";
   575 qed "zless_trans";
   576 
   576 
   596 qed "zless_not_refl";
   596 qed "zless_not_refl";
   597 
   597 
   598 (* z<z ==> R *)
   598 (* z<z ==> R *)
   599 bind_thm ("zless_irrefl", (zless_not_refl RS notE));
   599 bind_thm ("zless_irrefl", (zless_not_refl RS notE));
   600 
   600 
   601 Goal "!!w. z<w ==> w ~= (z::int)";
   601 Goal "z<w ==> w ~= (z::int)";
   602 by (fast_tac (claset() addEs [zless_irrefl]) 1);
   602 by (fast_tac (claset() addEs [zless_irrefl]) 1);
   603 qed "zless_not_refl2";
   603 qed "zless_not_refl2";
   604 
   604 
   605 
   605 
   606 (*"Less than" is a linear ordering*)
   606 (*"Less than" is a linear ordering*)
   627 
   627 
   628 Goalw [zle_def, le_def] "($#m <= $#n) = (m<=n)";
   628 Goalw [zle_def, le_def] "($#m <= $#n) = (m<=n)";
   629 by (simp_tac (simpset() addsimps [zless_eq_less]) 1);
   629 by (simp_tac (simpset() addsimps [zless_eq_less]) 1);
   630 qed "zle_eq_le";
   630 qed "zle_eq_le";
   631 
   631 
   632 Goalw [zle_def] "!!w. ~(w<z) ==> z<=(w::int)";
   632 Goalw [zle_def] "~(w<z) ==> z<=(w::int)";
   633 by (assume_tac 1);
   633 by (assume_tac 1);
   634 qed "zleI";
   634 qed "zleI";
   635 
   635 
   636 Goalw [zle_def] "!!w. z<=w ==> ~(w<(z::int))";
   636 Goalw [zle_def] "z<=w ==> ~(w<(z::int))";
   637 by (assume_tac 1);
   637 by (assume_tac 1);
   638 qed "zleD";
   638 qed "zleD";
   639 
   639 
   640 val zleE = make_elim zleD;
   640 val zleE = make_elim zleD;
   641 
   641 
   642 Goalw [zle_def] "!!z. ~ z <= w ==> w<(z::int)";
   642 Goalw [zle_def] "~ z <= w ==> w<(z::int)";
   643 by (Fast_tac 1);
   643 by (Fast_tac 1);
   644 qed "not_zleE";
   644 qed "not_zleE";
   645 
   645 
   646 Goalw [zle_def] "!!z. z < w ==> z <= (w::int)";
   646 Goalw [zle_def] "z < w ==> z <= (w::int)";
   647 by (fast_tac (claset() addEs [zless_asym]) 1);
   647 by (fast_tac (claset() addEs [zless_asym]) 1);
   648 qed "zless_imp_zle";
   648 qed "zless_imp_zle";
   649 
   649 
   650 Goalw [zle_def] "!!z. z <= w ==> z < w | z=(w::int)";
   650 Goalw [zle_def] "z <= w ==> z < w | z=(w::int)";
   651 by (cut_facts_tac [zless_linear] 1);
   651 by (cut_facts_tac [zless_linear] 1);
   652 by (fast_tac (claset() addEs [zless_irrefl,zless_asym]) 1);
   652 by (fast_tac (claset() addEs [zless_irrefl,zless_asym]) 1);
   653 qed "zle_imp_zless_or_eq";
   653 qed "zle_imp_zless_or_eq";
   654 
   654 
   655 Goalw [zle_def] "!!z. z<w | z=w ==> z <=(w::int)";
   655 Goalw [zle_def] "z<w | z=w ==> z <=(w::int)";
   656 by (cut_facts_tac [zless_linear] 1);
   656 by (cut_facts_tac [zless_linear] 1);
   657 by (fast_tac (claset() addEs [zless_irrefl,zless_asym]) 1);
   657 by (fast_tac (claset() addEs [zless_irrefl,zless_asym]) 1);
   658 qed "zless_or_eq_imp_zle";
   658 qed "zless_or_eq_imp_zle";
   659 
   659 
   660 Goal "(x <= (y::int)) = (x < y | x=y)";
   660 Goal "(x <= (y::int)) = (x < y | x=y)";
   668 val prems = goal Integ.thy "!!i. [| i <= j; j < k |] ==> i < (k::int)";
   668 val prems = goal Integ.thy "!!i. [| i <= j; j < k |] ==> i < (k::int)";
   669 by (dtac zle_imp_zless_or_eq 1);
   669 by (dtac zle_imp_zless_or_eq 1);
   670 by (fast_tac (claset() addIs [zless_trans]) 1);
   670 by (fast_tac (claset() addIs [zless_trans]) 1);
   671 qed "zle_zless_trans";
   671 qed "zle_zless_trans";
   672 
   672 
   673 Goal "!!i. [| i <= j; j <= k |] ==> i <= (k::int)";
   673 Goal "[| i <= j; j <= k |] ==> i <= (k::int)";
   674 by (EVERY1 [dtac zle_imp_zless_or_eq, dtac zle_imp_zless_or_eq,
   674 by (EVERY1 [dtac zle_imp_zless_or_eq, dtac zle_imp_zless_or_eq,
   675             rtac zless_or_eq_imp_zle, fast_tac (claset() addIs [zless_trans])]);
   675             rtac zless_or_eq_imp_zle, fast_tac (claset() addIs [zless_trans])]);
   676 qed "zle_trans";
   676 qed "zle_trans";
   677 
   677 
   678 Goal "!!z. [| z <= w; w <= z |] ==> z = (w::int)";
   678 Goal "[| z <= w; w <= z |] ==> z = (w::int)";
   679 by (EVERY1 [dtac zle_imp_zless_or_eq, dtac zle_imp_zless_or_eq,
   679 by (EVERY1 [dtac zle_imp_zless_or_eq, dtac zle_imp_zless_or_eq,
   680             fast_tac (claset() addEs [zless_irrefl,zless_asym])]);
   680             fast_tac (claset() addEs [zless_irrefl,zless_asym])]);
   681 qed "zle_anti_sym";
   681 qed "zle_anti_sym";
   682 
   682 
   683 
   683 
   734 (** Additional theorems for Integ.thy **) 
   734 (** Additional theorems for Integ.thy **) 
   735 
   735 
   736 Addsimps [zless_eq_less, zle_eq_le,
   736 Addsimps [zless_eq_less, zle_eq_le,
   737 	  znegative_zminus_znat, not_znegative_znat]; 
   737 	  znegative_zminus_znat, not_znegative_znat]; 
   738 
   738 
   739 Goal "!! x. (x::int) = y ==> x <= y"; 
   739 Goal "(x::int) = y ==> x <= y"; 
   740   by (etac subst 1); by (rtac zle_refl 1); 
   740   by (etac subst 1); by (rtac zle_refl 1); 
   741 qed "zequalD1"; 
   741 qed "zequalD1"; 
   742 
   742 
   743 Goal "($~ x < $~ y) = (y < x)";
   743 Goal "($~ x < $~ y) = (y < x)";
   744   by (rewrite_goals_tac [zless_def,zdiff_def]); 
   744   by (rewrite_goals_tac [zless_def,zdiff_def]); 
   820 qed "negative_eq_positive"; 
   820 qed "negative_eq_positive"; 
   821 
   821 
   822 Addsimps [zminus_zless_zminus, zminus_zle_zminus, 
   822 Addsimps [zminus_zless_zminus, zminus_zle_zminus, 
   823 	  negative_eq_positive, not_znat_zless_negative]; 
   823 	  negative_eq_positive, not_znat_zless_negative]; 
   824 
   824 
   825 Goalw [zdiff_def,zless_def] "!! x. znegative x = (x < $# 0)";
   825 Goalw [zdiff_def,zless_def] "znegative x = (x < $# 0)";
   826   by Auto_tac; 
   826   by Auto_tac; 
   827 qed "znegative_less_0"; 
   827 qed "znegative_less_0"; 
   828 
   828 
   829 Goalw [zdiff_def,zless_def] "!! x. (~znegative x) = ($# 0 <= x)";
   829 Goalw [zdiff_def,zless_def] "(~znegative x) = ($# 0 <= x)";
   830   by (stac znegative_less_0 1); 
   830   by (stac znegative_less_0 1); 
   831   by (safe_tac (HOL_cs addSDs[zleD,not_zleE,zleI]) ); 
   831   by (safe_tac (HOL_cs addSDs[zleD,not_zleE,zleI]) ); 
   832 qed "not_znegative_ge_0"; 
   832 qed "not_znegative_ge_0"; 
   833 
   833 
   834 Goal "!! x. znegative x ==> ? n. x = $~ $# Suc n"; 
   834 Goal "znegative x ==> ? n. x = $~ $# Suc n"; 
   835   by (dtac (znegative_less_0 RS iffD1 RS zless_eq_zadd_Suc) 1); 
   835   by (dtac (znegative_less_0 RS iffD1 RS zless_eq_zadd_Suc) 1); 
   836   by (etac exE 1); 
   836   by (etac exE 1); 
   837   by (rtac exI 1);
   837   by (rtac exI 1);
   838   by (dres_inst_tac [("f","(% z. z + $~ $# Suc n )")] arg_cong 1); 
   838   by (dres_inst_tac [("f","(% z. z + $~ $# Suc n )")] arg_cong 1); 
   839   by (auto_tac(claset(), simpset() addsimps [zadd_assoc])); 
   839   by (auto_tac(claset(), simpset() addsimps [zadd_assoc])); 
   840 qed "znegativeD"; 
   840 qed "znegativeD"; 
   841 
   841 
   842 Goal "!! x. ~znegative x ==> ? n. x = $# n"; 
   842 Goal "~znegative x ==> ? n. x = $# n"; 
   843   by (dtac (not_znegative_ge_0 RS iffD1) 1); 
   843   by (dtac (not_znegative_ge_0 RS iffD1) 1); 
   844   by (dtac zle_imp_zless_or_eq 1); 
   844   by (dtac zle_imp_zless_or_eq 1); 
   845   by (etac disjE 1); 
   845   by (etac disjE 1); 
   846   by (dtac zless_eq_zadd_Suc 1); 
   846   by (dtac zless_eq_zadd_Suc 1); 
   847   by Auto_tac; 
   847   by Auto_tac;