Semirings with monus
Lax392996.SemiringsWithMonus · concepts/Lax392996/SemiringsWithMonus.lean · lax-392996
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A semiring with monus, or m-semiring, is a semiring with a further binary operation . Here it is axiomatized through the natural order of a canonically ordered semiring, when for some , by the Galois connection ; the three equations of the paper's definition, , and , follow and are the claims of this module. The class also carries the duplicate-eliminating operator of Amsterdamer, Deutch and Tannen (2011), with , and , 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
Evidence
This concept declares 5 statements. Each proof establishes one of them relative to its assumptions.
1 delta_axiom_i proven
2 delta_axiom_ii proven
3 msemiring_axiom_i proven
4 msemiring_axiom_ii proven
5 msemiring_axiom_iii proven
In the paper
- page 4 of this submission's paper
Lean source view on GitHub
| 1 | import Mathlib.Algebra.Order.Monoid.Canonical.Defs |
| 2 | import Mathlib.Algebra.Order.Ring.Defs |
| 3 | import Mathlib.Order.Defs.LinearOrder |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Semirings with monus |
| 8 | type: definition |
| 9 | --- |
| 10 | A semiring with monus, or m-semiring, is a semiring |
| 11 | with a further binary operation . |
| 12 | Here it is axiomatized through the natural order of a canonically ordered |
| 13 | semiring, when for some , by the Galois |
| 14 | connection ; the three equations of |
| 15 | the paper's definition, , |
| 16 | and |
| 17 | , follow and are the claims of this module. The class |
| 18 | also carries the duplicate-eliminating operator of Amsterdamer, |
| 19 | Deutch and Tannen (2011), with , |
| 20 | and |
| 21 | , which the paper's rewriting of aggregation |
| 22 | uses. An alternative linear order on an annotation type is bundled |
| 23 | separately: it is what makes a type of annotations usable as a value type |
| 24 | once data and annotations share a column. |
| 25 | -/ |
| 26 | |
| 27 | universe u |
| 28 | |
| 29 | namespace Lax392996.SemiringsWithMonus |
| 30 | |
| 31 | /-- A `SemiringWithMonus` is a naturally ordered semiring |
| 32 | with a monus operation that is compatible with the natural order. |
| 33 | The semiring is not required to be commutative. |
| 34 | |
| 35 | In addition to monus, the class carries a `δ : α → α` operator subject |
| 36 | to three axioms (`delta_zero`, `delta_natCast_pos`, and |
| 37 | `delta_absorb`). This is the duplicate-eliminating support |
| 38 | operator used to interpret aggregation in the framework of |
| 39 | [Amsterdamer, Deutch & Tannen, *Provenance for aggregate queries*][amsterdamer2011aggregate]. -/ |
| 40 | class 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 |
| 58 | they share a column with data values. -/ |
| 59 | class HasAltLinearOrder (α : Type u) where |
| 60 | altOrder : LinearOrder α |
| 61 | |
| 62 | /-- The paper's m-semiring axiom (i): `a ⊕ (b ⊖ a) = b ⊕ (a ⊖ b)`. -/ |
| 63 | axiom 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)`. -/ |
| 67 | axiom 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 = 𝟘`. -/ |
| 71 | axiom 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): `δ(𝟘) = 𝟘`. -/ |
| 75 | axiom delta_axiom_i : ∀ {K : Type} [SemiringWithMonus K], |
| 76 | SemiringWithMonus.delta (0 : K) = 0 |
| 77 | |
| 78 | /-- The paper's δ-semiring axiom (ii): `δ(𝟙 ⊕ ⋯ ⊕ 𝟙) = 𝟙`, whatever the |
| 79 | positive number of `𝟙`s. -/ |
| 80 | axiom delta_axiom_ii : ∀ {K : Type} [SemiringWithMonus K] {j : ℕ}, 0 < j → |
| 81 | SemiringWithMonus.delta ((j : K)) = 1 |
| 82 | |
| 83 | end Lax392996.SemiringsWithMonus |
| 84 |
Builds on
none
Used by
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments