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.
ProvSQL's Counting::delta: the support indicator.
Instances For
Dependency graph
Dependency graph
ℕ 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
Equations
- instCommSemiringWithMonusNat = { toSemiringWithMonus := instSemiringWithMonusNat, mul_comm := instCommSemiringWithMonusNat._proof_1 }
Dependency graph
Equations
- instHasAltLinearOrderNat = { altOrder := inferInstance }
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.