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>" |