27 "f : UP ==> (%n. (a * f n::'a::ring)) : UP"; |
27 "f : UP ==> (%n. (a * f n::'a::ring)) : UP"; |
28 by (Force_tac 1); |
28 by (Force_tac 1); |
29 qed "UP_closed_smult"; |
29 qed "UP_closed_smult"; |
30 |
30 |
31 Goalw [UP_def] |
31 Goalw [UP_def] |
32 "(%n. if m = n then <1> else <0>) : UP"; |
32 "(%n. if m = n then <1> else 0) : UP"; |
33 by Auto_tac; |
33 by Auto_tac; |
34 qed "UP_closed_monom"; |
34 qed "UP_closed_monom"; |
35 |
35 |
36 Goalw [UP_def] "(%n. if n = 0 then a else <0>) : UP"; |
36 Goalw [UP_def] "(%n. if n = 0 then a else 0) : UP"; |
37 by Auto_tac; |
37 by Auto_tac; |
38 qed "UP_closed_const"; |
38 qed "UP_closed_const"; |
39 |
39 |
40 Goal |
40 Goal |
41 "!! f::nat=>'a::ring. \ |
41 "!! f::nat=>'a::ring. \ |
42 \ [| bound n f; bound m g; n + m < k |] ==> f i * g (k - i) = <0>"; |
42 \ [| bound n f; bound m g; n + m < k |] ==> f i * g (k - i) = 0"; |
43 (* Case split: either f i or g (k - i) is zero *) |
43 (* Case split: either f i or g (k - i) is zero *) |
44 by (case_tac "n<i" 1); |
44 by (case_tac "n<i" 1); |
45 (* First case, f i is zero *) |
45 (* First case, f i is zero *) |
46 by (Force_tac 1); |
46 by (Force_tac 1); |
47 (* Second case, we have to derive m < k-i *) |
47 (* Second case, we have to derive m < k-i *) |
50 by (Force_tac 1); |
50 by (Force_tac 1); |
51 qed "bound_mult_zero"; |
51 qed "bound_mult_zero"; |
52 |
52 |
53 Goalw [UP_def] |
53 Goalw [UP_def] |
54 "[| f : UP; g : UP |] ==> \ |
54 "[| f : UP; g : UP |] ==> \ |
55 \ (%n. (SUM n (%i. f i * g (n-i))::'a::ring)) : UP"; |
55 \ (%n. (setsum (%i. f i * g (n-i)) {..n}::'a::ring)) : UP"; |
56 by (Step_tac 1); |
56 by (Step_tac 1); |
57 (* Instantiate bound for the product, and remove bound in goal *) |
57 (* Instantiate bound for the product, and remove bound in goal *) |
58 by (res_inst_tac [("x", "n + na")] exI 1); |
58 by (res_inst_tac [("x", "n + na")] exI 1); |
59 by (Step_tac 1); |
59 by (Step_tac 1); |
60 (* Show that the sum is 0 *) |
60 (* Show that the sum is 0 *) |
61 by (asm_simp_tac (simpset() addsimps [bound_mult_zero]) 1); |
61 by (asm_simp_tac (simpset() addsimps [bound_mult_zero]) 1); |
62 qed "UP_closed_mult"; |
62 qed "UP_closed_mult"; |
63 |
63 |
64 (* %x. <0> represents a polynomial *) |
64 (* %x. 0 represents a polynomial *) |
65 |
65 |
66 Goalw [UP_def] "(%x. <0>) : UP"; |
66 Goalw [UP_def] "(%x. 0) : UP"; |
67 by (Fast_tac 1); |
67 by (Fast_tac 1); |
68 qed "UP_zero"; |
68 qed "UP_zero"; |
69 |
69 |
70 (* Effect of +, *s, monom, * and the other operations on the coefficients *) |
70 (* Effect of +, *s, monom, * and the other operations on the coefficients *) |
71 |
71 |
78 "!!a::'a::ring. coeff n (a *s p) = a * coeff n p"; |
78 "!!a::'a::ring. coeff n (a *s p) = a * coeff n p"; |
79 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_closed_smult, Rep_UP]) 1); |
79 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_closed_smult, Rep_UP]) 1); |
80 qed "coeff_smult"; |
80 qed "coeff_smult"; |
81 |
81 |
82 Goalw [coeff_def, monom_def] |
82 Goalw [coeff_def, monom_def] |
83 "coeff n (monom m) = (if m=n then <1> else <0>)"; |
83 "coeff n (monom m) = (if m=n then <1> else 0)"; |
84 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_closed_monom, Rep_UP]) 1); |
84 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_closed_monom, Rep_UP]) 1); |
85 qed "coeff_monom"; |
85 qed "coeff_monom"; |
86 |
86 |
87 Goalw [coeff_def, const_def] |
87 Goalw [coeff_def, const_def] |
88 "coeff n (const a) = (if n=0 then a else <0>)"; |
88 "coeff n (const a) = (if n=0 then a else 0)"; |
89 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_closed_const, Rep_UP]) 1); |
89 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_closed_const, Rep_UP]) 1); |
90 qed "coeff_const"; |
90 qed "coeff_const"; |
91 |
91 |
92 Goalw [coeff_def, up_mult_def] |
92 Goalw [coeff_def, up_mult_def] |
93 "coeff n (p * q) = (SUM n (%i. coeff i p * coeff (n-i) q)::'a::ring)"; |
93 "coeff n (p * q) = (setsum (%i. coeff i p * coeff (n-i) q) {..n}::'a::ring)"; |
94 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_closed_mult, Rep_UP]) 1); |
94 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_closed_mult, Rep_UP]) 1); |
95 qed "coeff_mult"; |
95 qed "coeff_mult"; |
96 |
96 |
97 Goalw [coeff_def, up_zero_def] "coeff n <0> = <0>"; |
97 Goalw [coeff_def, up_zero_def] "coeff n 0 = 0"; |
98 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_zero, Rep_UP]) 1); |
98 by (asm_simp_tac (simpset() addsimps [Abs_UP_inverse, UP_zero, Rep_UP]) 1); |
99 qed "coeff_zero"; |
99 qed "coeff_zero"; |
100 |
100 |
101 Addsimps [coeff_add, coeff_smult, coeff_monom, coeff_const, |
101 Addsimps [coeff_add, coeff_smult, coeff_monom, coeff_const, |
102 coeff_mult, coeff_zero]; |
102 coeff_mult, coeff_zero]; |
103 |
103 |
104 Goalw [up_one_def] |
104 Goalw [up_one_def] |
105 "coeff n <1> = (if n=0 then <1> else <0>)"; |
105 "coeff n <1> = (if n=0 then <1> else 0)"; |
106 by (Simp_tac 1); |
106 by (Simp_tac 1); |
107 qed "coeff_one"; |
107 qed "coeff_one"; |
108 |
108 |
109 Goalw [up_uminus_def] "coeff n (-p) = (-coeff n p::'a::ring)"; |
109 Goalw [up_uminus_def] "coeff n (-p) = (-coeff n p::'a::ring)"; |
110 by (simp_tac (simpset() addsimps m_minus) 1); |
110 by (simp_tac (simpset() addsimps m_minus) 1); |
174 by (cut_inst_tac [("a", "%i. coeff i a"), ("b", "%i. coeff i b")] |
174 by (cut_inst_tac [("a", "%i. coeff i a"), ("b", "%i. coeff i b")] |
175 poly_comm_lemma 1); |
175 poly_comm_lemma 1); |
176 by (asm_full_simp_tac (simpset() addsimps [m_comm]) 1); |
176 by (asm_full_simp_tac (simpset() addsimps [m_comm]) 1); |
177 qed "up_m_comm"; |
177 qed "up_m_comm"; |
178 |
178 |
179 Goal "<1> ~= (<0>::('a::ring) up)"; |
|
180 by (res_inst_tac [("n", "0")] up_neqI 1); |
|
181 by (Simp_tac 1); |
|
182 qed "up_one_not_zero"; |
|
183 |
|
184 (* Further algebraic rules *) |
179 (* Further algebraic rules *) |
185 |
180 |
186 Goal "!! a::'a::ring. const a * p = a *s p"; |
181 Goal "!! a::'a::ring. const a * p = a *s p"; |
187 by (rtac up_eqI 1); |
182 by (rtac up_eqI 1); |
188 by (case_tac "n" 1); |
183 by (case_tac "n" 1); |
224 qed "const_inj"; |
219 qed "const_inj"; |
225 |
220 |
226 (*Lemma used in PolyHomo*) |
221 (*Lemma used in PolyHomo*) |
227 Goal |
222 Goal |
228 "!! f::nat=>'a::ring. [| bound n f; bound m g|] ==> \ |
223 "!! f::nat=>'a::ring. [| bound n f; bound m g|] ==> \ |
229 \ SUM (n + m) (%k. SUM k (%i. f i * g (k-i))) = SUM n f * SUM m g"; |
224 \ setsum (%k. setsum (%i. f i * g (k-i)) {..k}) {..n + m} = \ |
|
225 \ setsum f {..n} * setsum g {..m}"; |
230 by (simp_tac (simpset() addsimps [SUM_ldistr, DiagSum]) 1); |
226 by (simp_tac (simpset() addsimps [SUM_ldistr, DiagSum]) 1); |
231 (* SUM_rdistr must be applied after SUM_ldistr ! *) |
227 (* SUM_rdistr must be applied after SUM_ldistr ! *) |
232 by (simp_tac (simpset() addsimps [SUM_rdistr]) 1); |
228 by (simp_tac (simpset() addsimps [SUM_rdistr]) 1); |
233 by (res_inst_tac [("m", "n"), ("n", "n+m")] SUM_extend 1); |
229 by (res_inst_tac [("m", "n"), ("n", "n+m")] SUM_extend 1); |
234 by (rtac le_add1 1); |
230 by (rtac le_add1 1); |