Documentation

Provenance.Semirings.Nat

Counting m-semiring #

This file shows that ℕ (with standard addition and multiplication) is a commutative m-semiring. The monus is truncated subtraction (Nat.sub). Unlike most provenance semirings, ℕ is neither idempotent nor absorptive.

The natural order is the usual order on natural numbers, and monus coincides with Mathlib's Nat.sub.

def Nat.deltaInd (n : ℕ) :

ProvSQL's Counting::delta: the support indicator.

Equations
Instances For
    Dependency graph
    Dependency graph
    @[instance_reducible]

    ℕ is a commutative m-semiring. The natural order is the usual order on natural numbers, and the monus is truncated subtraction. The δ operator matches ProvSQL's Counting::delta: the support indicator (0 ↦ 0, positive ↦ 1).

    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    Dependency graph
    Dependency graph
    Dependency graph

    ℕ is exclusive: 𝟙 ⊖ a is 0 as soon as a is positive, and a itself is 0 otherwise.

    Unlike in Bool, 𝟙 ⊖ a is not a complement of a here: 2 + (1 - 2) = 2 and not 1. Exclusivity asks only for orthogonality, so it holds in a semiring where the monus against 𝟙 collapses as well as in one where it complements.

    Dependency graph
    Dependency graph
    Dependency graph

    ℕ has characteristic 0: it satisfies CharZero, hence CharP ℕ 0 via CharP.ofCharZero.

    Dependency graph

    There is no m-semiring homomorphism from ℕ to 𝔹. The unique ring homomorphism ℕ → 𝔹 is the support map n ↦ (n ≠ 0) (the natural-number cast), but it does not preserve monus: supp (2 ∸ 1) = ⊤ while supp 2 ∸ supp 1 = ⊥. This is the algebraic form of the fact that ℕ-adequacy of the annotated semantics stops at the monotone fragment: possible-worlds equalities transfer along monus-preserving homomorphisms into 𝔹 (as they exist for BoolFunc X, one per valuation), and ℕ has none.

    Dependency graph

    ℕ is not multiplicatively idempotent, which is what separates it from the lattice-like exclusive domains: it is exclusive, so the worlds of a family do annihilate each other pairwise, but a world annotated 2 is not worth the same squared. It is the one semiring of the catalog that is exclusive without being multiplicatively idempotent.

    Dependency graph