src/HOL/Algebra/UnivPoly.thy
changeset 33657 a4179bf442d1
parent 32960 69916a850301
child 34915 7894c7dab132
equal deleted inserted replaced
33648:555e5358b8c9 33657:a4179bf442d1
   809 qed
   809 qed
   810 
   810 
   811 lemma deg_eqI:
   811 lemma deg_eqI:
   812   "[| !!m. n < m ==> coeff P p m = \<zero>;
   812   "[| !!m. n < m ==> coeff P p m = \<zero>;
   813       !!n. n ~= 0 ==> coeff P p n ~= \<zero>; p \<in> carrier P |] ==> deg R p = n"
   813       !!n. n ~= 0 ==> coeff P p n ~= \<zero>; p \<in> carrier P |] ==> deg R p = n"
   814 by (fast intro: le_anti_sym deg_aboveI deg_belowI)
   814 by (fast intro: le_antisym deg_aboveI deg_belowI)
   815 
   815 
   816 text {* Degree and polynomial operations *}
   816 text {* Degree and polynomial operations *}
   817 
   817 
   818 lemma deg_add [simp]:
   818 lemma deg_add [simp]:
   819   "p \<in> carrier P \<Longrightarrow> q \<in> carrier P \<Longrightarrow>
   819   "p \<in> carrier P \<Longrightarrow> q \<in> carrier P \<Longrightarrow>
   824   "a \<in> carrier R ==> deg R (monom P a n) <= n"
   824   "a \<in> carrier R ==> deg R (monom P a n) <= n"
   825   by (intro deg_aboveI) simp_all
   825   by (intro deg_aboveI) simp_all
   826 
   826 
   827 lemma deg_monom [simp]:
   827 lemma deg_monom [simp]:
   828   "[| a ~= \<zero>; a \<in> carrier R |] ==> deg R (monom P a n) = n"
   828   "[| a ~= \<zero>; a \<in> carrier R |] ==> deg R (monom P a n) = n"
   829   by (fastsimp intro: le_anti_sym deg_aboveI deg_belowI)
   829   by (fastsimp intro: le_antisym deg_aboveI deg_belowI)
   830 
   830 
   831 lemma deg_const [simp]:
   831 lemma deg_const [simp]:
   832   assumes R: "a \<in> carrier R" shows "deg R (monom P a 0) = 0"
   832   assumes R: "a \<in> carrier R" shows "deg R (monom P a 0) = 0"
   833 proof (rule le_anti_sym)
   833 proof (rule le_antisym)
   834   show "deg R (monom P a 0) <= 0" by (rule deg_aboveI) (simp_all add: R)
   834   show "deg R (monom P a 0) <= 0" by (rule deg_aboveI) (simp_all add: R)
   835 next
   835 next
   836   show "0 <= deg R (monom P a 0)" by (rule deg_belowI) (simp_all add: R)
   836   show "0 <= deg R (monom P a 0)" by (rule deg_belowI) (simp_all add: R)
   837 qed
   837 qed
   838 
   838 
   839 lemma deg_zero [simp]:
   839 lemma deg_zero [simp]:
   840   "deg R \<zero>\<^bsub>P\<^esub> = 0"
   840   "deg R \<zero>\<^bsub>P\<^esub> = 0"
   841 proof (rule le_anti_sym)
   841 proof (rule le_antisym)
   842   show "deg R \<zero>\<^bsub>P\<^esub> <= 0" by (rule deg_aboveI) simp_all
   842   show "deg R \<zero>\<^bsub>P\<^esub> <= 0" by (rule deg_aboveI) simp_all
   843 next
   843 next
   844   show "0 <= deg R \<zero>\<^bsub>P\<^esub>" by (rule deg_belowI) simp_all
   844   show "0 <= deg R \<zero>\<^bsub>P\<^esub>" by (rule deg_belowI) simp_all
   845 qed
   845 qed
   846 
   846 
   847 lemma deg_one [simp]:
   847 lemma deg_one [simp]:
   848   "deg R \<one>\<^bsub>P\<^esub> = 0"
   848   "deg R \<one>\<^bsub>P\<^esub> = 0"
   849 proof (rule le_anti_sym)
   849 proof (rule le_antisym)
   850   show "deg R \<one>\<^bsub>P\<^esub> <= 0" by (rule deg_aboveI) simp_all
   850   show "deg R \<one>\<^bsub>P\<^esub> <= 0" by (rule deg_aboveI) simp_all
   851 next
   851 next
   852   show "0 <= deg R \<one>\<^bsub>P\<^esub>" by (rule deg_belowI) simp_all
   852   show "0 <= deg R \<one>\<^bsub>P\<^esub>" by (rule deg_belowI) simp_all
   853 qed
   853 qed
   854 
   854 
   855 lemma deg_uminus [simp]:
   855 lemma deg_uminus [simp]:
   856   assumes R: "p \<in> carrier P" shows "deg R (\<ominus>\<^bsub>P\<^esub> p) = deg R p"
   856   assumes R: "p \<in> carrier P" shows "deg R (\<ominus>\<^bsub>P\<^esub> p) = deg R p"
   857 proof (rule le_anti_sym)
   857 proof (rule le_antisym)
   858   show "deg R (\<ominus>\<^bsub>P\<^esub> p) <= deg R p" by (simp add: deg_aboveI deg_aboveD R)
   858   show "deg R (\<ominus>\<^bsub>P\<^esub> p) <= deg R p" by (simp add: deg_aboveI deg_aboveD R)
   859 next
   859 next
   860   show "deg R p <= deg R (\<ominus>\<^bsub>P\<^esub> p)"
   860   show "deg R p <= deg R (\<ominus>\<^bsub>P\<^esub> p)"
   861     by (simp add: deg_belowI lcoeff_nonzero_deg
   861     by (simp add: deg_belowI lcoeff_nonzero_deg
   862       inj_on_iff [OF R.a_inv_inj, of _ "\<zero>", simplified] R)
   862       inj_on_iff [OF R.a_inv_inj, of _ "\<zero>", simplified] R)
   876 begin
   876 begin
   877 
   877 
   878 lemma deg_smult [simp]:
   878 lemma deg_smult [simp]:
   879   assumes R: "a \<in> carrier R" "p \<in> carrier P"
   879   assumes R: "a \<in> carrier R" "p \<in> carrier P"
   880   shows "deg R (a \<odot>\<^bsub>P\<^esub> p) = (if a = \<zero> then 0 else deg R p)"
   880   shows "deg R (a \<odot>\<^bsub>P\<^esub> p) = (if a = \<zero> then 0 else deg R p)"
   881 proof (rule le_anti_sym)
   881 proof (rule le_antisym)
   882   show "deg R (a \<odot>\<^bsub>P\<^esub> p) <= (if a = \<zero> then 0 else deg R p)"
   882   show "deg R (a \<odot>\<^bsub>P\<^esub> p) <= (if a = \<zero> then 0 else deg R p)"
   883     using R by (rule deg_smult_ring)
   883     using R by (rule deg_smult_ring)
   884 next
   884 next
   885   show "(if a = \<zero> then 0 else deg R p) <= deg R (a \<odot>\<^bsub>P\<^esub> p)"
   885   show "(if a = \<zero> then 0 else deg R p) <= deg R (a \<odot>\<^bsub>P\<^esub> p)"
   886   proof (cases "a = \<zero>")
   886   proof (cases "a = \<zero>")
   918 begin
   918 begin
   919 
   919 
   920 lemma deg_mult [simp]:
   920 lemma deg_mult [simp]:
   921   "[| p ~= \<zero>\<^bsub>P\<^esub>; q ~= \<zero>\<^bsub>P\<^esub>; p \<in> carrier P; q \<in> carrier P |] ==>
   921   "[| p ~= \<zero>\<^bsub>P\<^esub>; q ~= \<zero>\<^bsub>P\<^esub>; p \<in> carrier P; q \<in> carrier P |] ==>
   922   deg R (p \<otimes>\<^bsub>P\<^esub> q) = deg R p + deg R q"
   922   deg R (p \<otimes>\<^bsub>P\<^esub> q) = deg R p + deg R q"
   923 proof (rule le_anti_sym)
   923 proof (rule le_antisym)
   924   assume "p \<in> carrier P" " q \<in> carrier P"
   924   assume "p \<in> carrier P" " q \<in> carrier P"
   925   then show "deg R (p \<otimes>\<^bsub>P\<^esub> q) <= deg R p + deg R q" by (rule deg_mult_ring)
   925   then show "deg R (p \<otimes>\<^bsub>P\<^esub> q) <= deg R p + deg R q" by (rule deg_mult_ring)
   926 next
   926 next
   927   let ?s = "(%i. coeff P p i \<otimes> coeff P q (deg R p + deg R q - i))"
   927   let ?s = "(%i. coeff P p i \<otimes> coeff P q (deg R p + deg R q - i))"
   928   assume R: "p \<in> carrier P" "q \<in> carrier P" and nz: "p ~= \<zero>\<^bsub>P\<^esub>" "q ~= \<zero>\<^bsub>P\<^esub>"
   928   assume R: "p \<in> carrier P" "q \<in> carrier P" and nz: "p ~= \<zero>\<^bsub>P\<^esub>" "q ~= \<zero>\<^bsub>P\<^esub>"