src/HOL/Ring_and_Field.thy
changeset 25267 1f745c599b5c
parent 25238 ee73d4c33a88
child 25304 7491c00f0915
equal deleted inserted replaced
25266:37aa898e0523 25267:1f745c599b5c
   107 class no_zero_divisors = zero + times +
   107 class no_zero_divisors = zero + times +
   108   assumes no_zero_divisors: "a \<noteq> 0 \<Longrightarrow> b \<noteq> 0 \<Longrightarrow> a * b \<noteq> 0"
   108   assumes no_zero_divisors: "a \<noteq> 0 \<Longrightarrow> b \<noteq> 0 \<Longrightarrow> a * b \<noteq> 0"
   109 
   109 
   110 class semiring_1_cancel = semiring + comm_monoid_add + zero_neq_one
   110 class semiring_1_cancel = semiring + comm_monoid_add + zero_neq_one
   111   + cancel_ab_semigroup_add + monoid_mult
   111   + cancel_ab_semigroup_add + monoid_mult
   112 
   112 begin
   113 subclass (in semiring_1_cancel) semiring_0_cancel by unfold_locales
   113 
   114 
   114 subclass semiring_0_cancel by unfold_locales
   115 subclass (in semiring_1_cancel) semiring_1 by unfold_locales
   115 
       
   116 subclass semiring_1 by unfold_locales
       
   117 
       
   118 end
   116 
   119 
   117 class comm_semiring_1_cancel = comm_semiring + comm_monoid_add + comm_monoid_mult
   120 class comm_semiring_1_cancel = comm_semiring + comm_monoid_add + comm_monoid_mult
   118   + zero_neq_one + cancel_ab_semigroup_add
   121   + zero_neq_one + cancel_ab_semigroup_add
   119 
   122 begin
   120 subclass (in comm_semiring_1_cancel) semiring_1_cancel by unfold_locales
   123 
   121 subclass (in comm_semiring_1_cancel) comm_semiring_0_cancel by unfold_locales
   124 subclass semiring_1_cancel by unfold_locales
   122 subclass (in comm_semiring_1_cancel) comm_semiring_1 by unfold_locales
   125 subclass comm_semiring_0_cancel by unfold_locales
       
   126 subclass comm_semiring_1 by unfold_locales
       
   127 
       
   128 end
   123 
   129 
   124 class ring = semiring + ab_group_add
   130 class ring = semiring + ab_group_add
   125 
   131 begin
   126 subclass (in ring) semiring_0_cancel by unfold_locales
   132 
   127 
   133 subclass semiring_0_cancel by unfold_locales
   128 context ring
       
   129 begin
       
   130 
   134 
   131 text {* Distribution rules *}
   135 text {* Distribution rules *}
   132 
   136 
   133 lemma minus_mult_left: "- (a * b) = - a * b"
   137 lemma minus_mult_left: "- (a * b) = - a * b"
   134   by (rule equals_zero_I) (simp add: left_distrib [symmetric]) 
   138   by (rule equals_zero_I) (simp add: left_distrib [symmetric]) 
   171 
   175 
   172 lemmas ring_distribs =
   176 lemmas ring_distribs =
   173   right_distrib left_distrib left_diff_distrib right_diff_distrib
   177   right_distrib left_distrib left_diff_distrib right_diff_distrib
   174 
   178 
   175 class comm_ring = comm_semiring + ab_group_add
   179 class comm_ring = comm_semiring + ab_group_add
   176 
   180 begin
   177 subclass (in comm_ring) ring by unfold_locales
   181 
   178 subclass (in comm_ring) comm_semiring_0 by unfold_locales
   182 subclass ring by unfold_locales
       
   183 subclass comm_semiring_0 by unfold_locales
       
   184 
       
   185 end
   179 
   186 
   180 class ring_1 = ring + zero_neq_one + monoid_mult
   187 class ring_1 = ring + zero_neq_one + monoid_mult
   181 
   188 begin
   182 subclass (in ring_1) semiring_1_cancel by unfold_locales
   189 
       
   190 subclass semiring_1_cancel by unfold_locales
       
   191 
       
   192 end
   183 
   193 
   184 class comm_ring_1 = comm_ring + zero_neq_one + comm_monoid_mult
   194 class comm_ring_1 = comm_ring + zero_neq_one + comm_monoid_mult
   185   (*previously ring*)
   195   (*previously ring*)
   186 
   196 begin
   187 subclass (in comm_ring_1) ring_1 by unfold_locales
   197 
   188 subclass (in comm_ring_1) comm_semiring_1_cancel by unfold_locales
   198 subclass ring_1 by unfold_locales
       
   199 subclass comm_semiring_1_cancel by unfold_locales
       
   200 
       
   201 end
   189 
   202 
   190 class ring_no_zero_divisors = ring + no_zero_divisors
   203 class ring_no_zero_divisors = ring + no_zero_divisors
   191 begin
   204 begin
   192 
   205 
   193 lemma mult_eq_0_iff [simp]:
   206 lemma mult_eq_0_iff [simp]:
   236 end
   249 end
   237 
   250 
   238 class field = comm_ring_1 + inverse +
   251 class field = comm_ring_1 + inverse +
   239   assumes field_inverse:  "a \<noteq> 0 \<Longrightarrow> inverse a * a = 1"
   252   assumes field_inverse:  "a \<noteq> 0 \<Longrightarrow> inverse a * a = 1"
   240   assumes divide_inverse: "a / b = a * inverse b"
   253   assumes divide_inverse: "a / b = a * inverse b"
   241 
   254 begin
   242 subclass (in field) division_ring
   255 
       
   256 subclass division_ring
   243 proof unfold_locales
   257 proof unfold_locales
   244   fix a :: 'a
   258   fix a :: 'a
   245   assume "a \<noteq> 0"
   259   assume "a \<noteq> 0"
   246   thus "inverse a * a = 1" by (rule field_inverse)
   260   thus "inverse a * a = 1" by (rule field_inverse)
   247   thus "a * inverse a = 1" by (simp only: mult_commute)
   261   thus "a * inverse a = 1" by (simp only: mult_commute)
   248 qed
   262 qed
   249 
   263 
   250 subclass (in field) idom by unfold_locales
   264 subclass idom by unfold_locales
   251 
       
   252 context field
       
   253 begin
       
   254 
   265 
   255 lemma right_inverse_eq: "b \<noteq> 0 \<Longrightarrow> a / b = 1 \<longleftrightarrow> a = b"
   266 lemma right_inverse_eq: "b \<noteq> 0 \<Longrightarrow> a / b = 1 \<longleftrightarrow> a = b"
   256 proof
   267 proof
   257   assume neq: "b \<noteq> 0"
   268   assume neq: "b \<noteq> 0"
   258   {
   269   {
   316 
   327 
   317 end
   328 end
   318 
   329 
   319 class pordered_cancel_semiring = mult_mono + pordered_ab_semigroup_add
   330 class pordered_cancel_semiring = mult_mono + pordered_ab_semigroup_add
   320   + semiring + comm_monoid_add + cancel_ab_semigroup_add
   331   + semiring + comm_monoid_add + cancel_ab_semigroup_add
   321 
   332 begin
   322 subclass (in pordered_cancel_semiring) semiring_0_cancel by unfold_locales
   333 
   323 subclass (in pordered_cancel_semiring) pordered_semiring by unfold_locales
   334 subclass semiring_0_cancel by unfold_locales
   324 
   335 subclass pordered_semiring by unfold_locales
   325 context pordered_cancel_semiring
       
   326 begin
       
   327 
   336 
   328 lemma mult_nonneg_nonneg: "0 \<le> a \<Longrightarrow> 0 \<le> b \<Longrightarrow> 0 \<le> a * b"
   337 lemma mult_nonneg_nonneg: "0 \<le> a \<Longrightarrow> 0 \<le> b \<Longrightarrow> 0 \<le> a * b"
   329   by (drule mult_left_mono [of zero b], auto)
   338   by (drule mult_left_mono [of zero b], auto)
   330 
   339 
   331 lemma mult_nonneg_nonpos: "0 \<le> a \<Longrightarrow> b \<le> 0 \<Longrightarrow> a * b \<le> 0"
   340 lemma mult_nonneg_nonpos: "0 \<le> a \<Longrightarrow> b \<le> 0 \<Longrightarrow> a * b \<le> 0"
   338   by (auto simp add: mult_nonneg_nonpos mult_nonneg_nonpos2)
   347   by (auto simp add: mult_nonneg_nonpos mult_nonneg_nonpos2)
   339 
   348 
   340 end
   349 end
   341 
   350 
   342 class ordered_semiring = semiring + comm_monoid_add + ordered_cancel_ab_semigroup_add + mult_mono
   351 class ordered_semiring = semiring + comm_monoid_add + ordered_cancel_ab_semigroup_add + mult_mono
   343 
   352 begin
   344 subclass (in ordered_semiring) pordered_cancel_semiring by unfold_locales
   353 
   345 
   354 subclass pordered_cancel_semiring by unfold_locales
   346 context ordered_semiring
       
   347 begin
       
   348 
   355 
   349 lemma mult_left_less_imp_less:
   356 lemma mult_left_less_imp_less:
   350   "c * a < c * b \<Longrightarrow> 0 \<le> c \<Longrightarrow> a < b"
   357   "c * a < c * b \<Longrightarrow> 0 \<le> c \<Longrightarrow> a < b"
   351   by (force simp add: mult_left_mono not_le [symmetric])
   358   by (force simp add: mult_left_mono not_le [symmetric])
   352  
   359  
   357 end
   364 end
   358 
   365 
   359 class ordered_semiring_strict = semiring + comm_monoid_add + ordered_cancel_ab_semigroup_add +
   366 class ordered_semiring_strict = semiring + comm_monoid_add + ordered_cancel_ab_semigroup_add +
   360   assumes mult_strict_left_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> c * a < c * b"
   367   assumes mult_strict_left_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> c * a < c * b"
   361   assumes mult_strict_right_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> a * c < b * c"
   368   assumes mult_strict_right_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> a * c < b * c"
   362 
   369 begin
   363 subclass (in ordered_semiring_strict) semiring_0_cancel by unfold_locales
   370 
   364 
   371 subclass semiring_0_cancel by unfold_locales
   365 subclass (in ordered_semiring_strict) ordered_semiring
   372 
       
   373 subclass ordered_semiring
   366 proof unfold_locales
   374 proof unfold_locales
   367   fix a b c :: 'a
   375   fix a b c :: 'a
   368   assume A: "a \<le> b" "0 \<le> c"
   376   assume A: "a \<le> b" "0 \<le> c"
   369   from A show "c * a \<le> c * b"
   377   from A show "c * a \<le> c * b"
   370     unfolding le_less
   378     unfolding le_less
   372   from A show "a * c \<le> b * c"
   380   from A show "a * c \<le> b * c"
   373     unfolding le_less
   381     unfolding le_less
   374     using mult_strict_right_mono by (cases "c = 0") auto
   382     using mult_strict_right_mono by (cases "c = 0") auto
   375 qed
   383 qed
   376 
   384 
   377 context ordered_semiring_strict
       
   378 begin
       
   379 
       
   380 lemma mult_left_le_imp_le:
   385 lemma mult_left_le_imp_le:
   381   "c * a \<le> c * b \<Longrightarrow> 0 < c \<Longrightarrow> a \<le> b"
   386   "c * a \<le> c * b \<Longrightarrow> 0 < c \<Longrightarrow> a \<le> b"
   382   by (force simp add: mult_strict_left_mono _not_less [symmetric])
   387   by (force simp add: mult_strict_left_mono _not_less [symmetric])
   383  
   388  
   384 lemma mult_right_le_imp_le:
   389 lemma mult_right_le_imp_le:
   418 class mult_mono1 = times + zero + ord +
   423 class mult_mono1 = times + zero + ord +
   419   assumes mult_mono1: "a \<le> b \<Longrightarrow> 0 \<le> c \<Longrightarrow> c * a \<le> c * b"
   424   assumes mult_mono1: "a \<le> b \<Longrightarrow> 0 \<le> c \<Longrightarrow> c * a \<le> c * b"
   420 
   425 
   421 class pordered_comm_semiring = comm_semiring_0
   426 class pordered_comm_semiring = comm_semiring_0
   422   + pordered_ab_semigroup_add + mult_mono1
   427   + pordered_ab_semigroup_add + mult_mono1
   423 
   428 begin
   424 class pordered_cancel_comm_semiring = comm_semiring_0_cancel
   429 
   425   + pordered_ab_semigroup_add + mult_mono1
   430 subclass pordered_semiring
   426 begin
       
   427 
       
   428 subclass pordered_comm_semiring by unfold_locales
       
   429 
       
   430 end
       
   431 
       
   432 class ordered_comm_semiring_strict = comm_semiring_0 + ordered_cancel_ab_semigroup_add +
       
   433   assumes mult_strict_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> c * a < c * b"
       
   434 
       
   435 subclass (in pordered_comm_semiring) pordered_semiring
       
   436 proof unfold_locales
   431 proof unfold_locales
   437   fix a b c :: 'a
   432   fix a b c :: 'a
   438   assume "a \<le> b" "0 \<le> c"
   433   assume "a \<le> b" "0 \<le> c"
   439   thus "c * a \<le> c * b" by (rule mult_mono1)
   434   thus "c * a \<le> c * b" by (rule mult_mono1)
   440   thus "a * c \<le> b * c" by (simp only: mult_commute)
   435   thus "a * c \<le> b * c" by (simp only: mult_commute)
   441 qed
   436 qed
   442 
   437 
   443 subclass (in pordered_cancel_comm_semiring) pordered_cancel_semiring
   438 end
   444   by unfold_locales
   439 
   445 
   440 class pordered_cancel_comm_semiring = comm_semiring_0_cancel
   446 subclass (in ordered_comm_semiring_strict) ordered_semiring_strict
   441   + pordered_ab_semigroup_add + mult_mono1
       
   442 begin
       
   443 
       
   444 subclass pordered_comm_semiring by unfold_locales
       
   445 subclass pordered_cancel_semiring by unfold_locales
       
   446 
       
   447 end
       
   448 
       
   449 class ordered_comm_semiring_strict = comm_semiring_0 + ordered_cancel_ab_semigroup_add +
       
   450   assumes mult_strict_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> c * a < c * b"
       
   451 begin
       
   452 
       
   453 subclass ordered_semiring_strict
   447 proof unfold_locales
   454 proof unfold_locales
   448   fix a b c :: 'a
   455   fix a b c :: 'a
   449   assume "a < b" "0 < c"
   456   assume "a < b" "0 < c"
   450   thus "c * a < c * b" by (rule mult_strict_mono)
   457   thus "c * a < c * b" by (rule mult_strict_mono)
   451   thus "a * c < b * c" by (simp only: mult_commute)
   458   thus "a * c < b * c" by (simp only: mult_commute)
   452 qed
   459 qed
   453 
   460 
   454 subclass (in ordered_comm_semiring_strict) pordered_cancel_comm_semiring
   461 subclass pordered_cancel_comm_semiring
   455 proof unfold_locales
   462 proof unfold_locales
   456   fix a b c :: 'a
   463   fix a b c :: 'a
   457   assume "a \<le> b" "0 \<le> c"
   464   assume "a \<le> b" "0 \<le> c"
   458   thus "c * a \<le> c * b"
   465   thus "c * a \<le> c * b"
   459     unfolding le_less
   466     unfolding le_less
   460     using mult_strict_mono by (cases "c = 0") auto
   467     using mult_strict_mono by (cases "c = 0") auto
   461 qed
   468 qed
   462 
   469 
       
   470 end
       
   471 
   463 class pordered_ring = ring + pordered_cancel_semiring 
   472 class pordered_ring = ring + pordered_cancel_semiring 
   464 
   473 begin
   465 subclass (in pordered_ring) pordered_ab_group_add by unfold_locales
   474 
   466 
   475 subclass pordered_ab_group_add by unfold_locales
   467 context pordered_ring
       
   468 begin
       
   469 
   476 
   470 lemmas ring_simps = ring_simps group_simps
   477 lemmas ring_simps = ring_simps group_simps
   471 
   478 
   472 lemma less_add_iff1:
   479 lemma less_add_iff1:
   473   "a * e + c < b * e + d \<longleftrightarrow> (a - b) * e + c < d"
   480   "a * e + c < b * e + d \<longleftrightarrow> (a - b) * e + c < d"
   506   by (auto simp add: mult_nonneg_nonneg mult_nonpos_nonpos)
   513   by (auto simp add: mult_nonneg_nonneg mult_nonpos_nonpos)
   507 
   514 
   508 end
   515 end
   509 
   516 
   510 class lordered_ring = pordered_ring + lordered_ab_group_abs
   517 class lordered_ring = pordered_ring + lordered_ab_group_abs
   511 
   518 begin
   512 subclass (in lordered_ring) lordered_ab_group_meet by unfold_locales
   519 
   513 subclass (in lordered_ring) lordered_ab_group_join by unfold_locales
   520 subclass lordered_ab_group_meet by unfold_locales
       
   521 subclass lordered_ab_group_join by unfold_locales
       
   522 
       
   523 end
   514 
   524 
   515 class abs_if = minus + ord + zero + abs +
   525 class abs_if = minus + ord + zero + abs +
   516   assumes abs_if: "\<bar>a\<bar> = (if a < 0 then (- a) else a)"
   526   assumes abs_if: "\<bar>a\<bar> = (if a < 0 then (- a) else a)"
   517 
   527 
   518 class sgn_if = sgn + zero + one + minus + ord +
   528 class sgn_if = sgn + zero + one + minus + ord +
   604 also helps with inequalities. *}
   614 also helps with inequalities. *}
   605 lemmas ring_simps = group_simps ring_distribs
   615 lemmas ring_simps = group_simps ring_distribs
   606 
   616 
   607 
   617 
   608 class pordered_comm_ring = comm_ring + pordered_comm_semiring
   618 class pordered_comm_ring = comm_ring + pordered_comm_semiring
   609 
   619 begin
   610 subclass (in pordered_comm_ring) pordered_ring by unfold_locales
   620 
   611 
   621 subclass pordered_ring by unfold_locales
   612 subclass (in pordered_comm_ring) pordered_cancel_comm_semiring by unfold_locales
   622 subclass pordered_cancel_comm_semiring by unfold_locales
       
   623 
       
   624 end
   613 
   625 
   614 class ordered_semidom = comm_semiring_1_cancel + ordered_comm_semiring_strict +
   626 class ordered_semidom = comm_semiring_1_cancel + ordered_comm_semiring_strict +
   615   (*previously ordered_semiring*)
   627   (*previously ordered_semiring*)
   616   assumes zero_less_one [simp]: "0 < 1"
   628   assumes zero_less_one [simp]: "0 < 1"
   617 begin
   629 begin