src/HOL/Ring_and_Field.thy
changeset 25512 4134f7c782e2
parent 25450 c3b26e533b21
child 25564 4ca31a3706a4
equal deleted inserted replaced
25511:54db9b5080b8 25512:4134f7c782e2
    78 end
    78 end
    79 
    79 
    80 class comm_semiring_0 = comm_semiring + comm_monoid_add + mult_zero
    80 class comm_semiring_0 = comm_semiring + comm_monoid_add + mult_zero
    81 begin
    81 begin
    82 
    82 
    83 subclass semiring_0 by unfold_locales
    83 subclass semiring_0 by intro_locales
    84 
    84 
    85 end
    85 end
    86 
    86 
    87 class comm_semiring_0_cancel = comm_semiring + comm_monoid_add + cancel_ab_semigroup_add
    87 class comm_semiring_0_cancel = comm_semiring + comm_monoid_add + cancel_ab_semigroup_add
    88 begin
    88 begin
    89 
    89 
    90 subclass semiring_0_cancel by unfold_locales
    90 subclass semiring_0_cancel by intro_locales
    91 
    91 
    92 end
    92 end
    93 
    93 
    94 class zero_neq_one = zero + one +
    94 class zero_neq_one = zero + one +
    95   assumes zero_neq_one [simp]: "0 \<noteq> 1"
    95   assumes zero_neq_one [simp]: "0 \<noteq> 1"
    98 
    98 
    99 class comm_semiring_1 = zero_neq_one + comm_semiring_0 + comm_monoid_mult
    99 class comm_semiring_1 = zero_neq_one + comm_semiring_0 + comm_monoid_mult
   100   (*previously almost_semiring*)
   100   (*previously almost_semiring*)
   101 begin
   101 begin
   102 
   102 
   103 subclass semiring_1 by unfold_locales
   103 subclass semiring_1 by intro_locales
   104 
   104 
   105 end
   105 end
   106 
   106 
   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 begin
   112 begin
   113 
   113 
   114 subclass semiring_0_cancel by unfold_locales
   114 subclass semiring_0_cancel by intro_locales
   115 
   115 
   116 subclass semiring_1 by unfold_locales
   116 subclass semiring_1 by intro_locales
   117 
   117 
   118 end
   118 end
   119 
   119 
   120 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
   121   + zero_neq_one + cancel_ab_semigroup_add
   121   + zero_neq_one + cancel_ab_semigroup_add
   122 begin
   122 begin
   123 
   123 
   124 subclass semiring_1_cancel by unfold_locales
   124 subclass semiring_1_cancel by intro_locales
   125 subclass comm_semiring_0_cancel by unfold_locales
   125 subclass comm_semiring_0_cancel by intro_locales
   126 subclass comm_semiring_1 by unfold_locales
   126 subclass comm_semiring_1 by intro_locales
   127 
   127 
   128 end
   128 end
   129 
   129 
   130 class ring = semiring + ab_group_add
   130 class ring = semiring + ab_group_add
   131 begin
   131 begin
   132 
   132 
   133 subclass semiring_0_cancel by unfold_locales
   133 subclass semiring_0_cancel by intro_locales
   134 
   134 
   135 text {* Distribution rules *}
   135 text {* Distribution rules *}
   136 
   136 
   137 lemma minus_mult_left: "- (a * b) = - a * b"
   137 lemma minus_mult_left: "- (a * b) = - a * b"
   138   by (rule equals_zero_I) (simp add: left_distrib [symmetric]) 
   138   by (rule equals_zero_I) (simp add: left_distrib [symmetric]) 
   177   right_distrib left_distrib left_diff_distrib right_diff_distrib
   177   right_distrib left_distrib left_diff_distrib right_diff_distrib
   178 
   178 
   179 class comm_ring = comm_semiring + ab_group_add
   179 class comm_ring = comm_semiring + ab_group_add
   180 begin
   180 begin
   181 
   181 
   182 subclass ring by unfold_locales
   182 subclass ring by intro_locales
   183 subclass comm_semiring_0 by unfold_locales
   183 subclass comm_semiring_0 by intro_locales
   184 
   184 
   185 end
   185 end
   186 
   186 
   187 class ring_1 = ring + zero_neq_one + monoid_mult
   187 class ring_1 = ring + zero_neq_one + monoid_mult
   188 begin
   188 begin
   189 
   189 
   190 subclass semiring_1_cancel by unfold_locales
   190 subclass semiring_1_cancel by intro_locales
   191 
   191 
   192 end
   192 end
   193 
   193 
   194 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
   195   (*previously ring*)
   195   (*previously ring*)
   196 begin
   196 begin
   197 
   197 
   198 subclass ring_1 by unfold_locales
   198 subclass ring_1 by intro_locales
   199 subclass comm_semiring_1_cancel by unfold_locales
   199 subclass comm_semiring_1_cancel by intro_locales
   200 
   200 
   201 end
   201 end
   202 
   202 
   203 class ring_no_zero_divisors = ring + no_zero_divisors
   203 class ring_no_zero_divisors = ring + no_zero_divisors
   204 begin
   204 begin
   217 class ring_1_no_zero_divisors = ring_1 + ring_no_zero_divisors
   217 class ring_1_no_zero_divisors = ring_1 + ring_no_zero_divisors
   218 
   218 
   219 class idom = comm_ring_1 + no_zero_divisors
   219 class idom = comm_ring_1 + no_zero_divisors
   220 begin
   220 begin
   221 
   221 
   222 subclass ring_1_no_zero_divisors by unfold_locales
   222 subclass ring_1_no_zero_divisors by intro_locales
   223 
   223 
   224 end
   224 end
   225 
   225 
   226 class division_ring = ring_1 + inverse +
   226 class division_ring = ring_1 + inverse +
   227   assumes left_inverse [simp]:  "a \<noteq> 0 \<Longrightarrow> inverse a * a = 1"
   227   assumes left_inverse [simp]:  "a \<noteq> 0 \<Longrightarrow> inverse a * a = 1"
   259   assume "a \<noteq> 0"
   259   assume "a \<noteq> 0"
   260   thus "inverse a * a = 1" by (rule field_inverse)
   260   thus "inverse a * a = 1" by (rule field_inverse)
   261   thus "a * inverse a = 1" by (simp only: mult_commute)
   261   thus "a * inverse a = 1" by (simp only: mult_commute)
   262 qed
   262 qed
   263 
   263 
   264 subclass idom by unfold_locales
   264 subclass idom by intro_locales
   265 
   265 
   266 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"
   267 proof
   267 proof
   268   assume neq: "b \<noteq> 0"
   268   assume neq: "b \<noteq> 0"
   269   {
   269   {
   329 
   329 
   330 class pordered_cancel_semiring = mult_mono + pordered_ab_semigroup_add
   330 class pordered_cancel_semiring = mult_mono + pordered_ab_semigroup_add
   331   + semiring + comm_monoid_add + cancel_ab_semigroup_add
   331   + semiring + comm_monoid_add + cancel_ab_semigroup_add
   332 begin
   332 begin
   333 
   333 
   334 subclass semiring_0_cancel by unfold_locales
   334 subclass semiring_0_cancel by intro_locales
   335 subclass pordered_semiring by unfold_locales
   335 subclass pordered_semiring by intro_locales
   336 
   336 
   337 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"
   338   by (drule mult_left_mono [of zero b], auto)
   338   by (drule mult_left_mono [of zero b], auto)
   339 
   339 
   340 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"
   349 end
   349 end
   350 
   350 
   351 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
   352 begin
   352 begin
   353 
   353 
   354 subclass pordered_cancel_semiring by unfold_locales
   354 subclass pordered_cancel_semiring by intro_locales
   355 
   355 
   356 subclass pordered_comm_monoid_add by unfold_locales
   356 subclass pordered_comm_monoid_add by intro_locales
   357 
   357 
   358 lemma mult_left_less_imp_less:
   358 lemma mult_left_less_imp_less:
   359   "c * a < c * b \<Longrightarrow> 0 \<le> c \<Longrightarrow> a < b"
   359   "c * a < c * b \<Longrightarrow> 0 \<le> c \<Longrightarrow> a < b"
   360   by (force simp add: mult_left_mono not_le [symmetric])
   360   by (force simp add: mult_left_mono not_le [symmetric])
   361  
   361  
   368 class ordered_semiring_strict = semiring + comm_monoid_add + ordered_cancel_ab_semigroup_add +
   368 class ordered_semiring_strict = semiring + comm_monoid_add + ordered_cancel_ab_semigroup_add +
   369   assumes mult_strict_left_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> c * a < c * b"
   369   assumes mult_strict_left_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> c * a < c * b"
   370   assumes mult_strict_right_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> a * c < b * c"
   370   assumes mult_strict_right_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> a * c < b * c"
   371 begin
   371 begin
   372 
   372 
   373 subclass semiring_0_cancel by unfold_locales
   373 subclass semiring_0_cancel by intro_locales
   374 
   374 
   375 subclass ordered_semiring
   375 subclass ordered_semiring
   376 proof unfold_locales
   376 proof unfold_locales
   377   fix a b c :: 'a
   377   fix a b c :: 'a
   378   assume A: "a \<le> b" "0 \<le> c"
   378   assume A: "a \<le> b" "0 \<le> c"
   441 
   441 
   442 class pordered_cancel_comm_semiring = comm_semiring_0_cancel
   442 class pordered_cancel_comm_semiring = comm_semiring_0_cancel
   443   + pordered_ab_semigroup_add + mult_mono1
   443   + pordered_ab_semigroup_add + mult_mono1
   444 begin
   444 begin
   445 
   445 
   446 subclass pordered_comm_semiring by unfold_locales
   446 subclass pordered_comm_semiring by intro_locales
   447 subclass pordered_cancel_semiring by unfold_locales
   447 subclass pordered_cancel_semiring by intro_locales
   448 
   448 
   449 end
   449 end
   450 
   450 
   451 class ordered_comm_semiring_strict = comm_semiring_0 + ordered_cancel_ab_semigroup_add +
   451 class ordered_comm_semiring_strict = comm_semiring_0 + ordered_cancel_ab_semigroup_add +
   452   assumes mult_strict_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> c * a < c * b"
   452   assumes mult_strict_mono: "a < b \<Longrightarrow> 0 < c \<Longrightarrow> c * a < c * b"
   472 end
   472 end
   473 
   473 
   474 class pordered_ring = ring + pordered_cancel_semiring 
   474 class pordered_ring = ring + pordered_cancel_semiring 
   475 begin
   475 begin
   476 
   476 
   477 subclass pordered_ab_group_add by unfold_locales
   477 subclass pordered_ab_group_add by intro_locales
   478 
   478 
   479 lemmas ring_simps = ring_simps group_simps
   479 lemmas ring_simps = ring_simps group_simps
   480 
   480 
   481 lemma less_add_iff1:
   481 lemma less_add_iff1:
   482   "a * e + c < b * e + d \<longleftrightarrow> (a - b) * e + c < d"
   482   "a * e + c < b * e + d \<longleftrightarrow> (a - b) * e + c < d"
   524 
   524 
   525 class ordered_ring = ring + ordered_semiring
   525 class ordered_ring = ring + ordered_semiring
   526   + ordered_ab_group_add + abs_if
   526   + ordered_ab_group_add + abs_if
   527 begin
   527 begin
   528 
   528 
   529 subclass pordered_ring by unfold_locales
   529 subclass pordered_ring by intro_locales
   530 
   530 
   531 subclass pordered_ab_group_add_abs
   531 subclass pordered_ab_group_add_abs
   532 proof unfold_locales
   532 proof unfold_locales
   533   fix a b
   533   fix a b
   534   show "\<bar>a + b\<bar> \<le> \<bar>a\<bar> + \<bar>b\<bar>"
   534   show "\<bar>a + b\<bar> \<le> \<bar>a\<bar> + \<bar>b\<bar>"
   545  *)
   545  *)
   546 class ordered_ring_strict = ring + ordered_semiring_strict
   546 class ordered_ring_strict = ring + ordered_semiring_strict
   547   + ordered_ab_group_add + abs_if
   547   + ordered_ab_group_add + abs_if
   548 begin
   548 begin
   549 
   549 
   550 subclass ordered_ring by unfold_locales
   550 subclass ordered_ring by intro_locales
   551 
   551 
   552 lemma mult_strict_left_mono_neg:
   552 lemma mult_strict_left_mono_neg:
   553   "b < a \<Longrightarrow> c < 0 \<Longrightarrow> c * a < c * b"
   553   "b < a \<Longrightarrow> c < 0 \<Longrightarrow> c * a < c * b"
   554   apply (drule mult_strict_left_mono [of _ _ "uminus c"])
   554   apply (drule mult_strict_left_mono [of _ _ "uminus c"])
   555   apply (simp_all add: minus_mult_left [symmetric]) 
   555   apply (simp_all add: minus_mult_left [symmetric]) 
   612 
   612 
   613 
   613 
   614 class pordered_comm_ring = comm_ring + pordered_comm_semiring
   614 class pordered_comm_ring = comm_ring + pordered_comm_semiring
   615 begin
   615 begin
   616 
   616 
   617 subclass pordered_ring by unfold_locales
   617 subclass pordered_ring by intro_locales
   618 subclass pordered_cancel_comm_semiring by unfold_locales
   618 subclass pordered_cancel_comm_semiring by intro_locales
   619 
   619 
   620 end
   620 end
   621 
   621 
   622 class ordered_semidom = comm_semiring_1_cancel + ordered_comm_semiring_strict +
   622 class ordered_semidom = comm_semiring_1_cancel + ordered_comm_semiring_strict +
   623   (*previously ordered_semiring*)
   623   (*previously ordered_semiring*)
  2015 
  2015 
  2016 
  2016 
  2017 class lordered_ring = pordered_ring + lordered_ab_group_add_abs
  2017 class lordered_ring = pordered_ring + lordered_ab_group_add_abs
  2018 begin
  2018 begin
  2019 
  2019 
  2020 subclass lordered_ab_group_add_meet by unfold_locales
  2020 subclass lordered_ab_group_add_meet by intro_locales
  2021 subclass lordered_ab_group_add_join by unfold_locales
  2021 subclass lordered_ab_group_add_join by intro_locales
  2022 
  2022 
  2023 end
  2023 end
  2024 
  2024 
  2025 lemma abs_le_mult: "abs (a * b) \<le> (abs a) * (abs (b::'a::lordered_ring))" 
  2025 lemma abs_le_mult: "abs (a * b) \<le> (abs a) * (abs (b::'a::lordered_ring))" 
  2026 proof -
  2026 proof -