Documentation

Mathlib.Algebra.Order.Ring.Defs

Ordered rings and semirings #

This file develops the basics of ordered (semi)rings.

Each typeclass here comprises

For short,

Typeclasses #

Hierarchy #

The hardest part of proving order lemmas might be to figure out the correct generality and its corresponding typeclass. Here's an attempt at demystifying it. For each typeclass, we list its immediate predecessors and what conditions are added to each of them.

Note that OrderDual does not satisfy any of the ordered ring typeclasses due to the zero_le_one field.

An OrderedSemiring is a semiring with a partial order such that addition is monotone and multiplication by a nonnegative number is monotone.

    Instances
      theorem OrderedSemiring.zero_le_one {α : Type u} [self : OrderedSemiring α] :
      0 1

      0 ≤ 1 in any ordered semiring.

      theorem OrderedSemiring.mul_le_mul_of_nonneg_left {α : Type u} [self : OrderedSemiring α] (a : α) (b : α) (c : α) :
      a b0 cc * a c * b

      In an ordered semiring, we can multiply an inequality a ≤ b on the left by a non-negative element 0 ≤ c to obtain c * a ≤ c * b.

      theorem OrderedSemiring.mul_le_mul_of_nonneg_right {α : Type u} [self : OrderedSemiring α] (a : α) (b : α) (c : α) :
      a b0 ca * c b * c

      In an ordered semiring, we can multiply an inequality a ≤ b on the right by a non-negative element 0 ≤ c to obtain a * c ≤ b * c.

      theorem OrderedRing.zero_le_one {α : Type u} [self : OrderedRing α] :
      0 1

      0 ≤ 1 in any ordered ring.

      theorem OrderedRing.mul_nonneg {α : Type u} [self : OrderedRing α] (a : α) (b : α) :
      0 a0 b0 a * b

      The product of non-negative elements is non-negative.

      In a strict ordered semiring, 0 ≤ 1.

      theorem StrictOrderedSemiring.mul_lt_mul_of_pos_left {α : Type u} [self : StrictOrderedSemiring α] (a : α) (b : α) (c : α) :
      a < b0 < cc * a < c * b

      Left multiplication by a positive element is strictly monotone.

      theorem StrictOrderedSemiring.mul_lt_mul_of_pos_right {α : Type u} [self : StrictOrderedSemiring α] (a : α) (b : α) (c : α) :
      a < b0 < ca * c < b * c

      Right multiplication by a positive element is strictly monotone.

      theorem StrictOrderedRing.zero_le_one {α : Type u} [self : StrictOrderedRing α] :
      0 1

      In a strict ordered ring, 0 ≤ 1.

      theorem StrictOrderedRing.mul_pos {α : Type u} [self : StrictOrderedRing α] (a : α) (b : α) :
      0 < a0 < b0 < a * b

      The product of two positive elements is positive.

      @[instance 100]
      Equations
      • =
      @[instance 200]
      Equations
      • =
      @[instance 200]
      Equations
      • =
      @[instance 100]
      Equations
      theorem one_add_le_one_sub_mul_one_add {α : Type u} [OrderedRing α] {a : α} {b : α} {c : α} (h : a + b + b * c c) :
      1 + a (1 - b) * (1 + c)
      theorem one_add_le_one_add_mul_one_sub {α : Type u} [OrderedRing α] {a : α} {b : α} {c : α} (h : a + c + b * c b) :
      1 + a (1 + b) * (1 - c)
      theorem one_sub_le_one_sub_mul_one_add {α : Type u} [OrderedRing α] {a : α} {b : α} {c : α} (h : b + b * c a + c) :
      1 - a (1 - b) * (1 + c)
      theorem one_sub_le_one_add_mul_one_sub {α : Type u} [OrderedRing α] {a : α} {b : α} {c : α} (h : c + b * c a + b) :
      1 - a (1 + b) * (1 - c)
      @[instance 100]
      Equations
      @[instance 200]
      Equations
      • =
      @[instance 200]
      Equations
      • =
      @[reducible, inline]

      A choice-free version of StrictOrderedSemiring.toOrderedSemiring to avoid using choice in basic Nat lemmas.

      Equations
      Instances For
        @[instance 100]
        Equations
        @[instance 100]
        Equations
        • =
        @[instance 100]
        Equations
        • =
        @[reducible, inline]

        A choice-free version of StrictOrderedCommSemiring.toOrderedCommSemiring' to avoid using choice in basic Nat lemmas.

        Equations
        Instances For
          @[instance 100]
          Equations
          @[instance 100]
          Equations
          @[reducible, inline]
          abbrev StrictOrderedRing.toOrderedRing' {α : Type u} [StrictOrderedRing α] [DecidableRel fun (x1 x2 : α) => x1 x2] :

          A choice-free version of StrictOrderedRing.toOrderedRing to avoid using choice in basic Int lemmas.

          Equations
          Instances For
            @[instance 100]
            Equations
            @[reducible, inline]

            A choice-free version of StrictOrderedCommRing.toOrderedCommRing to avoid using choice in basic Int lemmas.

            Equations
            Instances For
              @[instance 100]
              Equations
              @[instance 100]
              Equations
              @[instance 200]
              Equations
              • =
              @[instance 200]
              Equations
              • =
              @[instance 100]
              Equations
              • =
              @[instance 100]
              Equations
              • =
              @[instance 100]
              Equations
              • One or more equations did not get rendered due to their size.
              @[instance 100]
              Equations
              • LinearOrderedRing.toLinearOrderedSemiring = LinearOrderedSemiring.mk LinearOrderedRing.decidableLE LinearOrderedRing.decidableEq LinearOrderedRing.decidableLT
              @[instance 100]
              Equations
              • LinearOrderedRing.toLinearOrderedAddCommGroup = LinearOrderedAddCommGroup.mk LinearOrderedRing.decidableLE LinearOrderedRing.decidableEq LinearOrderedRing.decidableLT
              @[instance 100]
              Equations
              @[instance 100]
              Equations
              • LinearOrderedCommRing.toLinearOrderedCommSemiring = LinearOrderedCommSemiring.mk LinearOrderedRing.decidableLE LinearOrderedRing.decidableEq LinearOrderedRing.decidableLT