deep_causality_algebra/algebra/semiring.rs
1/*
2 * SPDX-License-Identifier: MIT
3 * Copyright (c) 2023 - 2026. The DeepCausality Authors and Contributors. All Rights Reserved.
4 */
5
6use crate::algebra::operator::Additive;
7use crate::{AddMonoid, Commutative};
8use crate::{Annihilating, Distributive, MulMonoid};
9
10/// Represents a **Semiring** in abstract algebra.
11///
12/// A semiring is a `Ring` without additive inverses. It is the structure the natural numbers ℕ
13/// have and cannot exceed: `3 - 5` has no value in ℕ, so there is no `-a`, and the additive
14/// monoid never becomes a group.
15///
16/// # Mathematical Definition
17///
18/// A set `R` with two operations is a semiring if it satisfies:
19///
20/// 1. **Under Addition:** `R` forms a commutative `AddMonoid`.
21/// - Addition is associative: `(a + b) + c = a + (b + c)`
22/// - Addition is commutative: `a + b = b + a`
23/// - There is an additive identity `0`: `a + 0 = a`
24/// - There is **no** requirement of additive inverses. This is the whole difference.
25///
26/// 2. **Under Multiplication:** `R` forms a `MulMonoid`.
27/// - Multiplication is associative: `(a * b) * c = a * (b * c)`
28/// - There is a multiplicative identity `1`: `a * 1 = a`
29///
30/// 3. **Distributivity:** `a * (b + c) = a * b + a * c` and `(a + b) * c = a * c + b * c`
31///
32/// 4. **Annihilation:** `0 * a = a * 0 = 0`, recorded by [`Annihilating`](crate::Annihilating)
33///
34/// # Annihilation is an axiom here, not a theorem
35///
36/// This is the subtle part, and the reason a semiring is not merely "a ring with a bound
37/// removed". In a `Ring` the annihilation law is *derived*:
38///
39/// ```text
40/// 0·a = (0 + 0)·a = 0·a + 0·a by the additive identity and distributivity
41/// 0 = 0·a by adding −(0·a) to both sides
42/// ```
43///
44/// That last step consumes an additive inverse. A semiring has none, so the derivation is
45/// unavailable and the law must be assumed. Implementing this trait therefore promises
46/// annihilation independently. That is why [`Annihilating`](crate::Annihilating) is a supertrait
47/// here and not merely a line of prose: a `Semiring` bound would otherwise assert a law that no
48/// implementor had promised.
49///
50/// # Relationship to `Ring`
51///
52/// Every ring is a semiring, and the bounds here are deliberately a strict subset of the ones
53/// `Ring` requires, so every `Ring` really is a `Semiring`.
54///
55/// Getting that subset right needed care. [`AddMonoid`](crate::AddMonoid) once required
56/// `AddAssign`, which `Ring`'s additive side never has, and while it did this trait was
57/// accidentally *stronger* than `Ring`: `CausalTensor` implements `AddAssign<T>` for a scalar
58/// right-hand side and never `AddAssign<Self>`, so it satisfied `Ring` while failing `Semiring` —
59/// the exact inversion of what a weakening should do. `AddMonoid` is now
60/// `Add + Clone + Associative<Additive> + Zero`, which together with `Commutative<Additive>` is
61/// [`AbelianGroup`](crate::AbelianGroup) with `Sub` and `Neg` dropped. That is the additive side
62/// of a semiring, and it is what the bound below states.
63///
64/// `Ring` is nevertheless not declared as `Ring: Semiring`. Re-rooting the supertrait changes
65/// nothing about membership, since the blanket impls already give every `Ring` the weaker bound,
66/// and the tower is left flat rather than churned for a relationship the type system already
67/// enforces.
68///
69/// ## Examples
70/// - Natural numbers ℕ (`u8`–`u128`, `usize`) — the motivating case
71/// - Every `Ring`, and therefore every `Field`
72///
73/// ## Counter-examples
74/// - Any structure without a multiplicative identity, which is a *rig* rather than a semiring
75pub trait Semiring:
76 AddMonoid + Commutative<Additive> + MulMonoid + Distributive + Annihilating
77{
78}
79impl<T> Semiring for T where
80 T: AddMonoid + Commutative<Additive> + MulMonoid + Distributive + Annihilating
81{
82}