src/HOL/Algebra/poly/UnivPoly.ML
changeset 11093 62c2e0af1d30
parent 8707 5de763446504
child 13735 7de9342aca7a
equal deleted inserted replaced
11092:69c1abb9a129 11093:62c2e0af1d30
    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);
   130 by (rtac up_eqI 1);
   130 by (rtac up_eqI 1);
   131 by (Simp_tac 1);
   131 by (Simp_tac 1);
   132 by (rtac a_assoc 1);
   132 by (rtac a_assoc 1);
   133 qed "up_a_assoc";
   133 qed "up_a_assoc";
   134 
   134 
   135 Goal "!! a::('a::ring) up. <0> + a = a";
   135 Goal "!! a::('a::ring) up. 0 + a = a";
   136 by (rtac up_eqI 1);
   136 by (rtac up_eqI 1);
   137 by (Simp_tac 1);
   137 by (Simp_tac 1);
   138 qed "up_l_zero";
   138 qed "up_l_zero";
   139 
   139 
   140 Goal "!! a::('a::ring) up. (-a) + a = <0>";
   140 Goal "!! a::('a::ring) up. (-a) + a = 0";
   141 by (rtac up_eqI 1);
   141 by (rtac up_eqI 1);
   142 by (Simp_tac 1);
   142 by (Simp_tac 1);
   143 qed "up_l_neg";
   143 qed "up_l_neg";
   144 
   144 
   145 Goal "!! a::('a::ring) up. a + b = b + a";
   145 Goal "!! a::('a::ring) up. a + b = b + a";
   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); 
   204 Goal "const (<1>::'a::ring) = <1>";
   199 Goal "const (<1>::'a::ring) = <1>";
   205 by (rtac up_eqI 1);
   200 by (rtac up_eqI 1);
   206 by (Simp_tac 1);
   201 by (Simp_tac 1);
   207 qed "const_one";
   202 qed "const_one";
   208 
   203 
   209 Goal "const (<0>::'a::ring) = <0>";
   204 Goal "const (0::'a::ring) = 0";
   210 by (rtac up_eqI 1);
   205 by (rtac up_eqI 1);
   211 by (Simp_tac 1);
   206 by (Simp_tac 1);
   212 qed "const_zero";
   207 qed "const_zero";
   213 
   208 
   214 Addsimps [const_add, const_mult, const_one, const_zero];
   209 Addsimps [const_add, const_mult, const_one, const_zero];
   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);
   237 by (rtac refl 1);
   233 by (rtac refl 1);
   238 by (res_inst_tac [("m", "m"), ("n", "n+m-i")] SUM_shrink 1);
   234 by (res_inst_tac [("m", "m"), ("n", "n+m-i")] SUM_shrink 1);
   239 by (asm_simp_tac (simpset() addsimps [le_add_diff]) 1);
   235 by (asm_simp_tac (simpset() addsimps [le_add_diff]) 1);
   240 by Auto_tac;
   236 by Auto_tac;
   241 qed "CauchySum";
   237 qed "CauchySum";
       
   238 
       
   239 Goal "<1> ~= (0::('a::domain) up)";
       
   240 by (res_inst_tac [("n", "0")] up_neqI 1);
       
   241 by (Simp_tac 1);
       
   242 qed "up_one_not_zero";