632 |
632 |
633 Goal "[| a <= D n; D n < b; partition(a,b) D |] ==> n < psize D"; |
633 Goal "[| a <= D n; D n < b; partition(a,b) D |] ==> n < psize D"; |
634 by (dtac (partition RS iffD1) 1 THEN Step_tac 1); |
634 by (dtac (partition RS iffD1) 1 THEN Step_tac 1); |
635 by (rtac ccontr 1 THEN dtac leI 1); |
635 by (rtac ccontr 1 THEN dtac leI 1); |
636 by Auto_tac; |
636 by Auto_tac; |
637 val lemma_additivity1 = result(); |
637 qed "lemma_additivity1"; |
638 |
638 |
639 Goal "[| a <= D n; partition(a,D n) D |] ==> psize D <= n"; |
639 Goal "[| a <= D n; partition(a,D n) D |] ==> psize D <= n"; |
640 by (rtac ccontr 1 THEN dtac not_leE 1); |
640 by (rtac ccontr 1 THEN dtac not_leE 1); |
641 by (ftac (partition RS iffD1) 1 THEN Step_tac 1); |
641 by (ftac (partition RS iffD1) 1 THEN Step_tac 1); |
642 by (forw_inst_tac [("r","Suc n")] partition_ub 1); |
642 by (forw_inst_tac [("r","Suc n")] partition_ub 1); |
643 by (auto_tac (claset() addSDs [spec],simpset())); |
643 by (auto_tac (claset() addSDs [spec],simpset())); |
644 val lemma_additivity2 = result(); |
644 qed "lemma_additivity2"; |
645 |
645 |
646 Goal "[| partition(a,b) D; psize D < m |] ==> D(m) = D(psize D)"; |
646 Goal "[| partition(a,b) D; psize D < m |] ==> D(m) = D(psize D)"; |
647 by (auto_tac (claset(),simpset() addsimps [partition])); |
647 by (auto_tac (claset(),simpset() addsimps [partition])); |
648 qed "partition_eq_bound"; |
648 qed "partition_eq_bound"; |
649 |
649 |
732 by (auto_tac (claset(),simpset() addsimps [partition_rhs2])); |
732 by (auto_tac (claset(),simpset() addsimps [partition_rhs2])); |
733 by (dtac (ARITH_PROVE "n < Suc na ==> n < na | n = na") 1); |
733 by (dtac (ARITH_PROVE "n < Suc na ==> n < na | n = na") 1); |
734 by Auto_tac; |
734 by Auto_tac; |
735 by (dres_inst_tac [("n","na")] partition_lt_gen 1); |
735 by (dres_inst_tac [("n","na")] partition_lt_gen 1); |
736 by Auto_tac; |
736 by Auto_tac; |
737 val lemma_additivity3 = result(); |
737 qed "lemma_additivity3"; |
738 |
738 |
739 Goalw [psize_def] "psize (%x. k) = 0"; |
739 Goalw [psize_def] "psize (%x. k) = 0"; |
740 by Auto_tac; |
740 by Auto_tac; |
741 qed "psize_const"; |
741 qed "psize_const"; |
742 Addsimps [psize_const]; |
742 Addsimps [psize_const]; |
744 Goal "[| partition(a,b) D; D na < D n; D n < D (Suc na); \ |
744 Goal "[| partition(a,b) D; D na < D n; D n < D (Suc na); \ |
745 \ na < psize D |] \ |
745 \ na < psize D |] \ |
746 \ ==> False"; |
746 \ ==> False"; |
747 by (forw_inst_tac [("m","n")] partition_lt_cancel 1); |
747 by (forw_inst_tac [("m","n")] partition_lt_cancel 1); |
748 by (auto_tac (claset() addIs [lemma_additivity3],simpset())); |
748 by (auto_tac (claset() addIs [lemma_additivity3],simpset())); |
749 val lemma_additivity3a = result(); |
749 qed "lemma_additivity3a"; |
750 |
750 |
751 Goal "[| partition(a,b) D; D n < b |] ==> psize (%x. D (x + n)) <= psize D - n"; |
751 Goal "[| partition(a,b) D; D n < b |] ==> psize (%x. D (x + n)) <= psize D - n"; |
752 by (res_inst_tac [("D2","(%x. D (x + n))")] (psize_def RS |
752 by (res_inst_tac [("D2","(%x. D (x + n))")] (psize_def RS |
753 meta_eq_to_obj_eq RS ssubst) 1); |
753 meta_eq_to_obj_eq RS ssubst) 1); |
754 by (res_inst_tac [("a","psize D - n")] someI2 1); |
754 by (res_inst_tac [("a","psize D - n")] someI2 1); |