Documentation

Provenance.SemiringWithMonus

Semirings with monus #

This file defines semirings with monus and introduces their main properties.

Many semirings relevant for provenance can be equipped with a monus - operator, resulting in what is called a semiring with monus, or m-semiring. This is standard in semiring theory [Ame84] and was introduced in the setting of provenance semirings by Geerts and Poggi [GP10]. The class is the algebraic structure underlying the annotated query semantics of Section IV-A of Sen, Maniu & Senellart, ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data (Definition 5).

References #

Definition of a SemiringWithMonus #

A SemiringWithMonus is a naturally ordered semiring with a monus operation that is compatible with the natural order. We do not require the semiring to be necessarily commutative.

In addition to monus, the class carries a δ : α → α operator subject to three axioms (delta_zero, delta_natCast_pos, and delta_absorb). This is the duplicate-eliminating support operator used to interpret aggregation in the framework of Amsterdamer, Deutch & Tannen, Provenance for aggregate queries, mirroring ProvSQL's Semiring::delta.

Instances
    Dependency graph

    Main properties #

    theorem monus_unique {α : Type} [K : SemiringWithMonus α] (s : α → α → α) (hs : ∀ (a b c : α), s a b ≤ c ↔ a ≤ b + c) (a b : α) :
    s a b = a - b

    Uniqueness of monus. The monus operation is determined by its adjunction property: any binary operation s satisfying s a b ≤ c ↔ a ≤ b + c coincides with ⊖. Consequently, a naturally ordered semiring admits at most one monus operation.

    Dependency graph
    theorem monus_self {α : Type} [K : SemiringWithMonus α] (a : α) :
    a - a = 0

    In a SemiringWithMonus, a - a = 0.

    Dependency graph
    theorem zero_monus {α : Type} [K : SemiringWithMonus α] (a : α) :
    0 - a = 0

    In a SemiringWithMonus, 0 - a = 0.

    Dependency graph
    theorem monus_zero {α : Type} [K : SemiringWithMonus α] (a : α) :
    a - 0 = a

    In a SemiringWithMonus, a - 0 = a.

    Dependency graph
    theorem add_monus {α : Type} [K : SemiringWithMonus α] (a b : α) :
    a + (b - a) = b + (a - b)

    In a SemiringWithMonus, a + (b -a) = b + (a - b).

    Dependency graph
    theorem monus_add {α : Type} [K : SemiringWithMonus α] (a b c : α) :
    a - (b + c) = a - b - c

    In a SemiringWithMonus, monus is left-distributive over plus.

    Dependency graph

    Additional properties #

    The following properties do not always hold in an arbitrary m-semiring.

    @[reducible, inline]
    abbrev idempotent (α : Type u_1) [Semiring α] :

    A Semiring is idempotent if a + a = a.

    Equations
    Instances For
      Dependency graph
      @[reducible, inline]
      abbrev mulIdempotent (α : Type u_1) [Semiring α] :

      A Semiring is multiplicatively idempotent when a ⊗ a = a. It is the lattice-like condition: with ⊕-idempotence it makes the semiring a bounded distributive lattice, and it is what a world annotation needs in order to survive being multiplied by itself – which is what happens when two atoms of one predicate read the same occurrence family (AggValue.predProvOf_mul_predProvOf). 𝔹, 𝔹[X], lineage and interval union have it; ℕ and the absorptive numeric domains do not.

      Equations
      Instances For
        Dependency graph
        @[reducible, inline]
        abbrev absorptive (α : Type u_1) [Semiring α] :

        A Semiring is absorptive (also called 0-closed or 0-bounded) if 1 + a = 1.

        Equations
        Instances For
          Dependency graph
          @[reducible, inline]

          We define left-distributivity of times over monus in a SemiringWithMonus.

          Equations
          Instances For
            Dependency graph
            @[reducible, inline]
            abbrev exclusive (α : Type) [SemiringWithMonus α] :

            A SemiringWithMonus is exclusive when every element is orthogonal to what 𝟙 retains after removing it: a ⊗ (𝟙 ⊖ a) = 𝟘.

            This is weaker than asking 𝟙 ⊖ a to be a complement of a, which would also require a ⊕ (𝟙 ⊖ a) = 𝟙: ℕ is exclusive, and there 𝟙 ⊖ 2 = 𝟘 joins with 2 to 2, not to 𝟙.

            Exclusivity is what makes two distinct possible worlds of one occurrence family annihilate each other (worldAnn_mul_eq_zero_of_ne), hence what makes the alternatives of an occurrence exclude each other. It holds in Bool, BoolFunc, Nat, Which and IntervalUnion, and fails in How, Why, Viterbi, MinMax, Lukasiewicz, Tropical and ChainFive (the catalog theorems named exclusive and not_exclusive in Provenance.Semirings.*).

            Those five are not five independent facts. Exclusivity is a unary equation, so it passes both to subalgebras and to the elements reached by a homomorphism out of an exclusive semiring. Bool and IntervalUnion inherit it from BoolFunc on those two routes: Bool embeds in BoolFunc as the constant functions (Bool.exclusive_of_boolFunc, by exclusive_of_injective_homomorphism_exclusive), while every interval union is the image of a variable under a homomorphism from BoolFunc (IntervalUnion.exclusive_of_boolFunc, by mul_one_monus_self_eq_zero_of_range – that homomorphism has a finite domain and is never onto, so the element-by-element form is what applies, not the surjective one). Nat and Which are beyond that reach, neither being absorptive (BoolFunc.no_hom_of_not_absorptive), and are exclusive for the other of the two reasons: their monus against 𝟙 collapses to 𝟘 rather than complementing.

            Note that How – the universal semiring, in which provenance circuits are built – is not exclusive, so the terms exclusivity cancels are carried by a circuit and vanish only on evaluation into a semiring that has the property, homomorphisms commuting with ⊖.

            Independence #

            Exclusivity is independent of each of the three properties above, every combination being realized in the catalog:

            exclusivenot exclusive
            absorptiveBoolViterbi
            not absorptiveNatHow
            idempotentBoolWhy
            not idempotentNatHow
            mul_sub_left_distributiveBoolViterbi
            not mul_sub_left_distributiveWhichWhy

            Independence is not absence of interaction: absorptivity and exclusivity constrain each other jointly without either implying the other, by eq_zero_or_one_of_exclusive_of_absorptive.

            Equations
            Instances For
              Dependency graph
              @[reducible, inline]

              A SemiringWithMonus is complemented when 𝟙 ⊖ · turns ⊕ into ⊗: the De Morgan law of a complement.

              It is what makes the annotation of a world of a family split along a partition of that family into the annotations of the two halves (Having.worldAnn_split), and so what lets a predicate whose atoms read disjoint families be evaluated atom by atom rather than over the union. It is not an m-semiring identity – the non-negative reals with truncated subtraction fail it at a = b = ½, which nnreal_not_complemented records against the m-semiring instance there – but it is proved for every semiring of the catalog, for one of two reasons. Either 𝟙 ⊖ · is a genuine complement, which is De Morgan's law: 𝔹 (Bool.complemented), 𝔹[X] (BoolFunc.complemented) and the temporal semiring (IntervalUnion.complemented). Or 𝟙 ⊖ · takes only the two values 𝟘 and 𝟙, is 𝟘 exactly on a property that a sum has iff one of its summands has, and ⊗ is 𝟘-absorbing with 𝟙 ⊗ 𝟙 = 𝟙: ℕ (Nat.complemented), ℕ[X] (How.complemented, the constant coefficient), Lin[X] (Which.complemented), Why[X] (Why.complemented, the empty witness), the tropical semirings (MinTropical.complemented), Viterbi (Viterbi.complemented), the bounded linear order (MinMax.complemented) and Łukasiewicz (Lukasiewicz.complemented). The second reason is a fact about each semiring and not a consequence of the two-valuedness alone, which is why each is proved rather than argued once.

              Equations
              Instances For
                Dependency graph
                theorem idempotent_of_absorptive {α : Type u_1} [K : Semiring α] :

                Absorptivity implies idempotence

                Dependency graph
                theorem idempotent_of_add_monus {α : Type} [K : SemiringWithMonus α] (h : ∀ (a b c : α), a + b - c = a - c + (b - c)) :

                In a SemiringWithMonus, right-distributivity of monus over plus implies idempotence.

                Dependency graph
                theorem add_monus_of_idempotent {α : Type} [K : SemiringWithMonus α] (h : idempotent α) (a b c : α) :
                a + b - c = a - c + (b - c)

                In a SemiringWithMonus, idempotence implies right-distributivity of monus over plus.

                Dependency graph
                theorem idempotent_iff_add_monus {α : Type} [SemiringWithMonus α] :
                idempotent α ↔ ∀ (a b c : α), a + b - c = a - c + (b - c)

                A SemiringWithMonus is idempotent iff monus is right-distributive over plus.

                Dependency graph
                theorem add_monus_of_idempotent_multiset {α : Type} [SemiringWithMonus α] (h : idempotent α) (s : Multiset α) (c : α) :
                s.sum - c = (Multiset.map (fun (x : α) => x - c) s).sum

                Finite-family version of add_monus_of_idempotent: in an idempotent SemiringWithMonus, monus distributes over the sum of any multiset of annotations, (⨁ᵢ aᵢ) ⊖ c = ⨁ᵢ (aᵢ ⊖ c).

                Dependency graph
                theorem monus_le {α : Type} [SemiringWithMonus α] (a b : α) :
                a - b ≤ a
                Dependency graph
                theorem le_plus_monus {α : Type} [SemiringWithMonus α] (a b : α) :
                a ≤ b + (a - b)
                Dependency graph
                theorem monus_antitone {α : Type} [SemiringWithMonus α] {b b' : α} (h : b ≤ b') (a : α) :
                a - b' ≤ a - b

                Monus is antitone in its second argument: subtracting more leaves less. Together with monus_le this is what lets a subtrahend be replaced by a larger one inside an upper bound.

                Dependency graph

                Exclusivity #

                exclusive says a ⊗ (𝟙 ⊖ a) = 𝟘. The possible-world arguments consume a two-argument form, a ⊗ (𝟙 ⊖ (a ⊕ b)) = 𝟘: an occurrence present in one world and absent from another contributes a to the first world's annotation and 𝟙 ⊖ (a ⊕ b) to the second's. The two forms are equivalent, so the one-argument form is what a semiring is checked against and the two-argument form is what the proofs use.

                Exclusivity against absorptivity #

                An absorptive m-semiring has 𝟙 at the top of its natural order, so 𝟙 ⊖ a is the least element joining with a to 𝟙 – the least relative complement. Exclusivity then asks that least complement to be orthogonal to a, which a chain cannot deliver: there the join of two elements is one of them, so the only complement of a non-𝟙 element is 𝟙 itself.

                theorem le_one_of_absorptive {α : Type} [SemiringWithMonus α] (h : absorptive α) (a : α) :
                a ≤ 1

                In an absorptive semiring 𝟙 is the greatest element of the natural order.

                Dependency graph
                theorem add_one_monus_eq_one_of_absorptive {α : Type} [SemiringWithMonus α] (h : absorptive α) (a : α) :
                a + (1 - a) = 1

                In an absorptive m-semiring, 𝟙 ⊖ a joins with a to 𝟙; by monus_smallest it is the least element that does.

                Dependency graph
                theorem eq_zero_or_one_of_exclusive_of_absorptive {α : Type} [SemiringWithMonus α] (habs : absorptive α) (hirr : ∀ (a z : α), a + z = 1 → a = 1 ∨ z = 1) (hexcl : exclusive α) (a : α) :
                a = 0 ∨ a = 1

                Absorptivity and exclusivity together are restrictive. If 𝟙 is join-irreducible – as it is in every absorptive m-semiring whose natural order is total – then an exclusive one has no element besides 𝟘 and 𝟙.

                Dependency graph
                theorem not_exclusive_of_absorptive_of_total {α : Type} [SemiringWithMonus α] (habs : absorptive α) (htot : ∀ (a b : α), a ≤ b ∨ b ≤ a) {a : α} (h0 : a ≠ 0) (h1 : a ≠ 1) :

                The contrapositive, in the form the catalog uses: a totally ordered absorptive m-semiring with an element other than 𝟘 and 𝟙 is not exclusive. This one argument covers Viterbi, MinMax, Lukasiewicz, Tropical and ChainFive.

                Dependency graph

                Characteristic of idempotent semirings #

                In an idempotent semiring (a + a = a), every positive natural-number cast collapses to 1. With 1 ≠ 0 this yields CharP K 0. Note that this is strictly weaker than CharZero K, which fails for idempotent semirings since the cast ℕ → K is not injective.

                theorem natCast_pos_eq_one_of_idempotent {K : Type} [Semiring K] (h : idempotent K) {n : ℕ} :
                0 < n → ↑n = 1

                In a semiring with idempotent addition, the cast of any positive natural number equals 1.

                Dependency graph

                Generic constructions of δ #

                In the m-semirings used for provenance the δ operator is invariably realized in one of two ways: as the identity (when the semiring is idempotent, so every positive natural cast already equals 1) or as the indicator-of-nonzero (a ↦ if a = 0 then 0 else 1). The lemmas below package the proofs of the δ axioms for both candidates so each concrete instance can plug them in directly.

                theorem delta_natCast_pos_id {K : Type} [Semiring K] (h : idempotent K) {n : ℕ} (hn : 0 < n) :
                id ↑n = 1

                δ := id satisfies delta_natCast_pos in any idempotent semiring: every positive natural-number cast collapses to 1.

                Dependency graph
                structure IsLegalDelta {K : Type} [Semiring K] (δ : K → K) :

                What the δ axioms ask of a candidate, as a predicate, so that the choices open to a given semiring can be compared.

                • zero : δ 0 = 0

                  δ sends 𝟘 to 𝟘.

                • natCast_pos {n : ℕ} : 0 < n → δ ↑n = 1

                  δ sends every positive natural cast to 𝟙.

                • absorb (a b : K) : a * δ (a + b) = a

                  A δ-guard is absorbed by any multiple of one of its summands.

                Instances For
                  Dependency graph
                  theorem isLegalDelta_id_iff {K : Type} [Semiring K] :
                  IsLegalDelta id ↔ (∀ (a b : K), a * (a + b) = a) ∧ ∀ (n : ℕ), 0 < n → ↑n = 1

                  The identity is a legal δ exactly where the semiring absorbs and its 𝟙 is additively idempotent. The absorption clause is the one a reader expects – a ⊓ (a ⊔ b) = a in a lattice-like semiring – but it is not the whole condition: δ must send every positive cast of 𝟙 to 𝟙, which for the identity says n · 𝟙 = 𝟙, that is, that ⊕ does not accumulate copies of 𝟙. Min-max satisfies both; ℕ fails the second, which is why the identity is not available there even though the first is what one thinks to check.

                  Dependency graph
                  structure IsDeltaIndicator {K : Type} [Zero K] [One K] (δ : K → K) :

                  The “indicator-of-nonzero” recipe: δ a = 0 when a = 0 and δ a = 1 otherwise. Captured abstractly so a single set of axioms can serve all the concrete instances that use it (ℕ, ℕ[X], Tropical, Viterbi, Lukasiewicz).

                  • zero : δ 0 = 0
                  • nonzero (a : K) : a ≠ 0 → δ a = 1
                  Instances For
                    Dependency graph
                    theorem delta_natCast_pos_indicator {K : Type} [Semiring K] [Nontrivial K] [CharP K 0] {δ : K → K} (h : IsDeltaIndicator δ) {n : ℕ} (hn : 0 < n) :
                    δ ↑n = 1

                    Any δ matching the indicator recipe satisfies delta_natCast_pos in a nontrivial semiring of characteristic 0 (in the CharP sense): positive natural-number casts are nonzero, so δ sends them to 1.

                    Dependency graph
                    theorem delta_absorb_indicator {K : Type} [Semiring K] [PartialOrder K] [IsOrderedAddMonoid K] [CanonicallyOrderedAdd K] {δ : K → K} (h : IsDeltaIndicator δ) (a b : K) :
                    a * δ (a + b) = a

                    Any δ matching the indicator recipe satisfies delta_absorb in a canonically ordered semiring: if a ⊕ b = 𝟘 then a = 𝟘 by zero-sum freeness, and otherwise δ(a ⊕ b) = 𝟙.

                    Dependency graph

                    The support map is a legal δ wherever the casts are non-zero. It is the greatest legal choice, the identity the least where it is available.

                    Dependency graph

                    Admissibility of a candidate δ #

                    δ is not determined by the axioms, and the two operators used in practice are the identity and the support indicator. IsDelta states the axioms as a predicate on a candidate operator, so that a semiring can record which of the two it must use: the identity is preferred where it is admissible, and the indicator is forced exactly where ¬ IsDelta id holds. The three not_isDelta_id_of_* lemmas below cover the three ways the identity fails, in increasing order of subtlety.

                    structure IsDelta {K : Type} [Semiring K] (δ : K → K) :

                    A candidate operator δ : K → K satisfies the δ-axioms of SemiringWithMonus.

                    • zero : δ 0 = 0

                      δ sends 𝟘 to 𝟘.

                    • natCast_pos {n : ℕ} : 0 < n → δ ↑n = 1

                      δ sends every positive natural-number cast to 𝟙.

                    • absorb (a b : K) : a * δ (a + b) = a

                      A δ-guard is absorbed by any multiple of one of its summands.

                    Instances For
                      Dependency graph
                      theorem not_isDelta_id_of_absorb_ne {K : Type} [Semiring K] {a b : K} (h : a * (a + b) ≠ a) :

                      To refute δ := id, exhibit a pair violating the lattice absorption law a ⊗ (a ⊕ b) = a, which is what delta_absorb demands of the identity.

                      Dependency graph

                      δ := id requires the semiring to be idempotent: delta_natCast_pos at n = 2 reads 𝟙 ⊕ 𝟙 = 𝟙, whence a ⊕ a = a ⊗ (𝟙 ⊕ 𝟙) = a. This is the crudest of the three obstructions, and the one that rules the identity out of the counting semirings (ℕ, ℕ[X]).

                      Dependency graph
                      theorem not_isDelta_id_of_not_mul_idempotent {K : Type} [Semiring K] (hadd : idempotent K) (h : ¬∀ (a : K), a * a = a) :

                      δ := id requires multiplicative idempotence as soon as addition is idempotent: delta_absorb at b = a reads a ⊗ (a ⊕ a) = a ⊗ a = a. This is the obstruction in the absorptive semirings whose ⊗ is a genuine product (Viterbi, Łukasiewicz), where the two coarser tests below say nothing.

                      Dependency graph

                      δ := id requires absorptivity: delta_absorb at a = 𝟙 reads 𝟙 ⊗ (𝟙 ⊕ b) = 𝟙, i.e., 𝟙 ⊕ b = 𝟙.

                      Dependency graph

                      Existence of a δ-like operator #

                      This is the abstract counterpart of the SemiringWithMonus δ-axioms: we characterize, in an arbitrary nontrivial semiring (no order assumed), when a function δ : K → K satisfying δ 0 = 0 and δ ((n : K)) = 1 for 0 < n can exist. The class also demands delta_absorb, which the iff below ignores, so it should be read as a statement about how much of the ProvSQL δ interface is consistent with a given characteristic, not as a full existence proof for the class. (Constructing a witness for delta_absorb requires more structure: in a canonically ordered semiring the indicator works, see delta_absorb_indicator.)

                      theorem delta_exists_iff_charP_zero {K : Type} [Semiring K] [Nontrivial K] :
                      (∃ (δ : K → K), δ 0 = 0 ∧ ∀ {n : ℕ}, 0 < n → δ ↑n = 1) ↔ CharP K 0

                      In any nontrivial semiring, a function δ : K → K satisfying δ 0 = 0 and δ ((n : K)) = 1 for every positive natural cast n exists if and only if K has characteristic 0 in the CharP sense. The forward direction follows because δ 0 = 0 and δ ((n : K)) = 1 are inconsistent when (n : K) = 0 for some 0 < n (it would force 0 = 1). The backward direction defines δ as the indicator of being nonzero.

                      Note that the δ operator is not uniquely determined by these axioms: they only pin its values on the image of ℕ. Two typical choices are δ as the indicator of being nonzero (δ x = if x = 0 then 0 else 1, used in the backward direction below) and, in an idempotent semiring, δ as the identity (since every positive natural cast then equals 1, see natCast_pos_eq_one_of_idempotent). Both are idempotent (δ (δ a) = δ a); adding idempotence as a third requirement would leave the statement unchanged, since the forward direction never uses it and the indicator witness satisfies it.

                      Dependency graph

                      The companion of delta_exists_iff_charP_zero for the full axiom set: in a nontrivial canonically ordered semiring, an admissible δ exists if and only if the characteristic is 0.

                      Dependency graph

                      Commutative SemiringWithMonuss #

                      SemiringWithMonus is intentionally not assumed to be commutative; however, every provenance semiring used in this library is in fact commutative, and the algebraic identities that drive HAVING-style aggregate provenance (see Provenance.Having) require it. CommSemiringWithMonus packages a SemiringWithMonus together with the commutativity axiom, producing a CommMonoid instance whose Mul matches the one already supplied by SemiringWithMonus, so no Mul diamond appears when Finset.prod is used.

                      A SemiringWithMonus whose multiplication is commutative.

                      Instances
                        Dependency graph
                        @[instance_reducible, instance 100]

                        A CommSemiringWithMonus is automatically a CommMonoid, sharing its multiplicative structure with the underlying SemiringWithMonus. This makes Finset.prod usable without introducing a separate CommSemiring hypothesis that would cause a Mul diamond.

                        Equations
                        Dependency graph

                        An exclusive lattice m-semiring is a Boolean algebra #

                        In an absorptive m-semiring ⊕ is the join of a lattice whose top is 𝟙 (le_one_of_absorptive) and, where ⊗ is idempotent too, ⊗ is its meet: the two lattice absorption laws are derived from 𝟙 ⊕ a = 𝟙 and distributivity (add_mul_self, mul_add_self) rather than assumed. The lattice is distributive, ⊗ distributing over ⊕ by the semiring axioms, and one distributive law in a lattice gives the other.

                        In such a semiring 𝟙 ⊖ a always joins a to 𝟙 (add_one_monus_eq_one_of_absorptive, by residuation), and exclusivity is exactly what makes it a complement – exclusive says it meets a at 𝟘 – after which the complement is unique (monus_one_unique_compl). So an exclusive lattice m-semiring is a distributive lattice in which every element has a complement, i.e., a Boolean algebra; conversely, in a Boolean algebra residuation forces a ⊖ b = a ⊓ bᶜ, whose exclusivity is a ⊓ aᶜ = ⊥. What follows is the elementwise content of that characterization, stated without building the lattice structure.

                        theorem add_mul_self {α : Type} [CommSemiringWithMonus α] (hab : absorptive α) (a b : α) :
                        a + a * b = a

                        The first lattice absorption law, derived: a ⊕ a ⊗ b = a.

                        Dependency graph
                        theorem mul_add_self {α : Type} [CommSemiringWithMonus α] (hab : absorptive α) (hm : ∀ (x : α), x * x = x) (a b : α) :
                        a * (a + b) = a

                        The second, where ⊗ is idempotent: a ⊗ (a ⊕ b) = a.

                        Dependency graph
                        theorem monus_one_isCompl {α : Type} [CommSemiringWithMonus α] (hab : absorptive α) (hex : exclusive α) (a : α) :
                        a + (1 - a) = 1 ∧ a * (1 - a) = 0

                        Exclusivity makes 𝟙 ⊖ a a complement: it joins a to 𝟙 and meets it at 𝟘.

                        Dependency graph
                        theorem monus_one_unique_compl {α : Type} [CommSemiringWithMonus α] (hab : absorptive α) (hex : exclusive α) {a b : α} (hjoin : a + b = 1) (hmeet : a * b = 0) :
                        b = 1 - a

                        And the complement is unique, by the distributive-lattice argument: any b joining a to 𝟙 and meeting it at 𝟘 is 𝟙 ⊖ a. With monus_one_isCompl this is what identifies 𝟙 ⊖ · with Boolean complementation.

                        Dependency graph

                        Homomorphisms of SemiringWithMonuss #

                        class SemiringWithMonusHom (α β : Type) [SemiringWithMonus α] [SemiringWithMonus β] extends α →+* β :

                        Definition of a homomorphism of SemiringWithMonuss. Preserves the semiring structure (via RingHom), the monus (map_sub), and the δ operator (map_delta). The latter is required for hom commutation of the aggregation operator, where δ appears on the row-annotation column (Definition 7 / R5 of Sen, Maniu & Senellart).

                        Instances
                          Dependency graph
                          @[instance_reducible]
                          Equations
                          Dependency graph

                          If ν is an injective m-semiring homomorphism from α to β, and β is exclusive, so is α.

                          Dependency graph

                          If ν is an m-semiring homomorphism from α onto β, and α is exclusive, so is β. Exclusivity passes to quotients as idempotence and distributivity do, being likewise an equation.

                          Dependency graph

                          Miscellaneous #

                          theorem natural_preorder_not_antisymm :
                          ∃ (a : ℤ), ∃ (b : ℤ), (∃ (c : ℤ), b = a + c) ∧ (∃ (c : ℤ), a = b + c) ∧ a ≠ b

                          On an arbitrary semiring the natural relation a ≼ b ↔ ∃ c, b = a + c is always a preorder (reflexive by c = 0, transitive by adding witnesses) but not always antisymmetric: on ℤ, any two elements are related in both directions, e.g., 0 ≼ 1 ≼ 0 with 0 ≠ 1. This is why SemiringWithMonus assumes the canonically ordered structure instead of deriving an order from +.

                          Dependency graph
                          class HasAltLinearOrder (α : Type u) :
                          Instances
                            Dependency graph