While this submission is a draft, it cannot be used by other submissions.

Semirings with monus

Lax392996.SemiringsWithMonus · concepts/Lax392996/SemiringsWithMonus.lean · lax-392996

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    A semiring with monus, or m-semiring, is a semiring (K,⊕,⊗,0,1)(\mathbb{K}, \oplus, \otimes, \mathbb{0}, \mathbb{1}) with a further binary operation ⊖\ominus. Here it is axiomatized through the natural order of a canonically ordered semiring, a≤ba \le b when b=a⊕cb = a \oplus c for some cc, by the Galois connection a⊖b≤c  ⟺  a≤b⊕ca \ominus b \le c \iff a \le b \oplus c; the three equations of the paper's definition, a⊕(b⊖a)=b⊕(a⊖b)a \oplus (b \ominus a) = b \oplus (a \ominus b), (a⊖b)⊖c=a⊖(b⊕c)(a \ominus b) \ominus c = a \ominus (b \oplus c) and a⊖a=0⊖a=0a \ominus a = \mathbb{0} \ominus a = \mathbb{0}, follow and are the claims of this module. The class also carries the duplicate-eliminating operator δ\delta of Amsterdamer, Deutch and Tannen (2011), with δ(0)=0\delta(\mathbb{0}) = \mathbb{0}, δ(1⊕⋯⊕1)=1\delta(\mathbb{1} \oplus \dots \oplus \mathbb{1}) = \mathbb{1} and a⊗δ(a⊕b)=aa \otimes \delta(a \oplus b) = a, which the paper's rewriting of aggregation uses. An alternative linear order on an annotation type is bundled separately: it is what makes a type of annotations usable as a value type once data and annotations share a column.

    Concept map
    1 concept; 11 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 5 statements. Each proof establishes one of them relative to its assumptions.

    5 msemiring_axiom_iii proven

    In the paper

    • page 4 of this submission's paper

    Lean source view on GitHub

    1import Mathlib.Algebra.Order.Monoid.Canonical.Defs
    2import Mathlib.Algebra.Order.Ring.Defs
    3import Mathlib.Order.Defs.LinearOrder
    4
    5/-!
    6---
    7title: Semirings with monus
    8type: definition
    9---
    10A semiring with monus, or m-semiring, is a semiring (K,⊕,⊗,0,1)(\mathbb{K}, \oplus, \otimes, \mathbb{0}, \mathbb{1})
    11 with a further binary operation ⊖\ominus.
    12Here it is axiomatized through the natural order of a canonically ordered
    13semiring, a≤ba \le b when b=a⊕cb = a \oplus c for some cc, by the Galois
    14connection a⊖b≤c  ⟺  a≤b⊕ca \ominus b \le c \iff a \le b \oplus c; the three equations of
    15the paper's definition, a⊕(b⊖a)=b⊕(a⊖b)a \oplus (b \ominus a) = b \oplus (a \ominus b),
    16(a⊖b)⊖c=a⊖(b⊕c)(a \ominus b) \ominus c = a \ominus (b \oplus c) and a⊖a=0⊖a=0a \ominus a = \mathbb{0} \ominus a = \mathbb{0}
    17, follow and are the claims of this module. The class
    18also carries the duplicate-eliminating operator δ\delta of Amsterdamer,
    19Deutch and Tannen (2011), with δ(0)=0\delta(\mathbb{0}) = \mathbb{0},
    20δ(1⊕⋯⊕1)=1\delta(\mathbb{1} \oplus \dots \oplus \mathbb{1}) = \mathbb{1} and a⊗δ(a⊕b)=aa \otimes \delta(a \oplus b) = a
    21, which the paper's rewriting of aggregation
    22uses. An alternative linear order on an annotation type is bundled
    23separately: it is what makes a type of annotations usable as a value type
    24once data and annotations share a column.
    25-/
    26
    27universe u
    28
    29namespace Lax392996.SemiringsWithMonus
    30
    31/-- A `SemiringWithMonus` is a naturally ordered semiring
    32with a monus operation that is compatible with the natural order.
    33The semiring is not required to be commutative.
    34
    35In addition to monus, the class carries a `δ : α → α` operator subject
    36to three axioms (`delta_zero`, `delta_natCast_pos`, and
    37`delta_absorb`). This is the duplicate-eliminating support
    38operator used to interpret aggregation in the framework of
    39[Amsterdamer, Deutch & Tannen, *Provenance for aggregate queries*][amsterdamer2011aggregate]. -/
    40class SemiringWithMonus (α : Type)
    41 extends Semiring α, PartialOrder α, IsOrderedAddMonoid α, CanonicallyOrderedAdd α, Sub α where
    42 monus_spec : ∀ a b c : α, a - b ≤ c ↔ a ≤ b + c
    43 /-- Duplicate-eliminating support operator. Sends `0` to `0` and any
    44 positive integer iterate of `1` to `1`. -/
    45 delta : α → α
    46 /-- `δ` sends `0` to `0`. -/
    47 delta_zero : delta 0 = 0
    48 /-- `δ` sends every positive integer iterate of `1` (i.e., every
    49 positive natural-number cast) to `1`. -/
    50 delta_natCast_pos : ∀ {n : ℕ}, 0 < n → delta ((n : α)) = 1
    51 /-- A δ-guard is absorbed by any multiple of one of its summands:
    52 `a ⊗ δ(a ⊕ b) = a`. This is what makes a group-existence factor
    53 redundant next to any provenance that already contains an occurrence
    54 of the group: `δ` acts as “the group exists” and nothing more. -/
    55 delta_absorb : ∀ (a b : α), a * delta (a + b) = a
    56
    57/-- An alternative linear order on a type, used to order annotations when
    58they share a column with data values. -/
    59class HasAltLinearOrder (α : Type u) where
    60 altOrder : LinearOrder α
    61
    62/-- The paper's m-semiring axiom (i): `a ⊕ (b ⊖ a) = b ⊕ (a ⊖ b)`. -/
    63axiom msemiring_axiom_i : ∀ {K : Type} [SemiringWithMonus K] (a b : K),
    64 a + (b - a) = b + (a - b)
    65
    66/-- The paper's m-semiring axiom (ii): `(a ⊖ b) ⊖ c = a ⊖ (b ⊕ c)`. -/
    67axiom msemiring_axiom_ii : ∀ {K : Type} [SemiringWithMonus K] (a b c : K),
    68 ((a - b) - c) = (a - (b + c))
    69
    70/-- The paper's m-semiring axiom (iii): `a ⊖ a = 𝟘 ⊖ a = 𝟘`. -/
    71axiom msemiring_axiom_iii : ∀ {K : Type} [SemiringWithMonus K] (a : K),
    72 ((a - a) = 0) ∧ (((0 : K) - a) = 0)
    73
    74/-- The paper's δ-semiring axiom (i): `δ(𝟘) = 𝟘`. -/
    75axiom delta_axiom_i : ∀ {K : Type} [SemiringWithMonus K],
    76 SemiringWithMonus.delta (0 : K) = 0
    77
    78/-- The paper's δ-semiring axiom (ii): `δ(𝟙 ⊕ ⋯ ⊕ 𝟙) = 𝟙`, whatever the
    79positive number of `𝟙`s. -/
    80axiom delta_axiom_ii : ∀ {K : Type} [SemiringWithMonus K] {j : ℕ}, 0 < j →
    81 SemiringWithMonus.delta ((j : K)) = 1
    82
    83end Lax392996.SemiringsWithMonus
    84
    Show ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…