A five-element chain m-semiring where ⊗ does not distribute over ⊖ #
This file defines ChainFive, a commutative m-semiring on the five-element
chain 𝟘 < lo < mid < hi < 𝟙 with ⊕ = max, the chain monus
(a ⊖ b = 𝟘 if a ≤ b, else a), and the commutative multiplication
determined by
ChainFive is absorptive (hence idempotent) but does not satisfy
mul_sub_left_distributive: hi ⊗ (𝟙 ⊖ hi) = hi while
hi ⊗ 𝟙 ⊖ hi ⊗ hi = 𝟘.
Why this semiring exists #
Its purpose is to show that the mul_sub_left_distributive hypothesis of
Having.world_bound – and hence of Having.G_eq_S_monus_S and
Having.atMost_eq_S_monus_S, which rest on it – is genuinely needed and
cannot be weakened away as it can for Having.F_eq_S (which needs only
absorptivity, via Having.upward_closed_collapse).
The witness is the family α = (mid, hi, hi) on a three-element universe
U, with W = {0} and C = 1:
- the exactly-
Wannotation isT_U(W) = mid ⊖ (mid⊗hi ⊕ mid⊗hi) = mid ⊖ lo = mid, but S_1(U) ⊖ S_2(U) = (mid ⊕ hi ⊕ hi) ⊖ (lo ⊕ lo ⊕ hi) = hi ⊖ hi = 𝟘,
so the bound T_U(W) ≤ S_1(U) ⊖ S_2(U) of Having.world_bound fails
(ChainFive.not_world_bound), and with it the HAVING count = 1 identity
G_1(U) = S_1(U) ⊖ S_2(U) (ChainFive.G_ne_S_monus_S) and the
HAVING count ≤ 1 identity (ChainFive.atMost_ne_S_monus_S).
Intuitively, in the factored form T_U(W) = A_W ⊗ (𝟙 ⊖ E_W) the failure
disappears: 𝟙 ⊖ E_W = 𝟙 ⊖ hi = 𝟙 and mid ⊗ 𝟙 = mid, but the world of
size 2 extending W by one hi-occurrence has annotation lo, which the
chain monus of the unfactored form A_W ⊖ ⊕_x A_{W∪{x}} fails to cancel
against mid. The two forms of the world annotation coincide exactly when
⊗ distributes over ⊖; ChainFive is where they part company.
All proofs are by decide: the carrier is a five-element enumeration with
derived decidable equality and order.
The five-element chain 𝟘 < lo < mid < hi < 𝟙 (constructor order is the
chain order), carrying the m-semiring structure described in the module
docstring.
Instances For
Dependency graph
Dependency graph
Equations
- instReprChainFive = { reprPrec := instReprChainFive.repr }
Dependency graph
Equations
- instReprChainFive.repr ChainFive.zero prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "ChainFive.zero")).group prec✝
- instReprChainFive.repr ChainFive.lo prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "ChainFive.lo")).group prec✝
- instReprChainFive.repr ChainFive.mid prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "ChainFive.mid")).group prec✝
- instReprChainFive.repr ChainFive.hi prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "ChainFive.hi")).group prec✝
- instReprChainFive.repr ChainFive.one prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "ChainFive.one")).group prec✝
Instances For
Dependency graph
Equations
- instOrdChainFive.ord x✝ y✝ = compare x✝.ctorIdx y✝.ctorIdx
Instances For
Dependency graph
Equations
- instOrdChainFive = { compare := instOrdChainFive.ord }
Dependency graph
Equations
- instFintypeChainFive = { elems := { val := ↑ChainFive.enumList, nodup := ChainFive.enumList_nodup }, complete := instFintypeChainFive._proof_1 }
Dependency graph
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- ChainFive.instZero = { zero := ChainFive.zero }
Dependency graph
Equations
- ChainFive.instOne = { one := ChainFive.one }
Dependency graph
Addition is max (the chain join).
Dependency graph
The commutative multiplication: 𝟙 is neutral, 𝟘 absorbing,
hi ⊗ hi = hi, hi ⊗ mid = hi ⊗ lo = lo, and all other products of
non-unit elements are 𝟘.
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
The chain monus: a ⊖ b = 𝟘 if a ≤ b, and a otherwise.
Equations
- ChainFive.instSub = { sub := fun (a b : ChainFive) => if a ≤ b then ChainFive.zero else a }
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- ChainFive.instCommSemiringWithMonus = { toSemiringWithMonus := ChainFive.instSemiringWithMonus, mul_comm := ChainFive.instCommSemiringWithMonus._proof_1 }
Dependency graph
Equations
- ChainFive.instHasAltLinearOrder = { altOrder := inferInstance }
Dependency graph
Dependency graph
ChainFive does not satisfy left-distributivity of ⊗ over ⊖:
hi ⊗ (𝟙 ⊖ hi) = hi ⊗ 𝟙 = hi, while hi ⊗ 𝟙 ⊖ hi ⊗ hi = hi ⊖ hi = 𝟘.
Dependency graph
ChainFive is not exclusive: hi ⊗ (𝟙 ⊖ hi) = hi, the computation the
module docstring already performs for a different purpose. It is absorptive
and not distributive, where Viterbi is absorptive and distributive and
Bool is both and exclusive.
Dependency graph
The antijoin against the difference that expresses it #
WHERE NOT EXISTS (Q) is the antijoin, and a row annotated α whose
matches are annotated βᵢ gets α ⊗ (𝟙 ⊖ ⊕βᵢ) from it in every
m-semiring (evaluateAnnotated_antijoin, which asks nothing of K).
The difference R ∖ Π(σ(R × Q)) that expresses the same condition –
what an uncorrelated EXCEPT uses – gets α ⊖ ⊕(α ⊗ βᵢ) instead, and
the two are each other's only where ⊗ distributes over ⊖. ChainFive
is where they part company, and by the whole of the row: the antijoin
keeps it, the difference annihilates it.
The antijoin's annotation of a row annotated hi with one match
annotated hi: hi ⊗ (𝟙 ⊖ hi) = hi ⊗ 𝟙 = hi, the row's own annotation
undiminished, since the chain monus leaves 𝟙 alone above hi.
Dependency graph
The difference's annotation of the same row: hi ⊖ hi ⊗ hi = hi ⊖ hi = 𝟘. The product the difference subtracts is the row's own annotation
back again, which the chain monus cancels completely.
Dependency graph
The EXCEPT that expresses WHERE NOT EXISTS loses the row. In
the absorptive, non-distributive ChainFive, a row annotated hi with a
single match annotated hi is annotated hi by the antijoin and 𝟘 by
the difference: the condition the two spell is the same and the row is
kept by one and dropped by the other.
α = lo, β = hi is the only other pair that parts them (lo against
𝟘); every other pair of the twenty-five agrees. Together with
ChainFive.absorptive this isolates the distribution: the semijoin's
own collapse, which needs absorptivity, is available here, so what fails
is ChainFive.not_mul_sub_left_distributive and nothing else.
Dependency graph
The witness family α = (mid, hi, hi) on a three-element universe.
Equations
- ChainFive.alphaCE i = if ↑i = 0 then ChainFive.mid else ChainFive.hi
Instances For
Dependency graph
Having.world_bound fails without mul_sub_left_distributive.
In the absorptive m-semiring ChainFive, the per-world upper bound
T_U(W) ≤ S_j(U) ⊖ S_{C+1}(U) (for j ≤ |W| ≤ C) does not hold: with
α = (mid, hi, hi), W = {0} and j = C = 1, the left-hand side is mid
and the right-hand side is 𝟘. Together with
ChainFive.not_mul_sub_left_distributive and ChainFive.absorptive, this
shows the distributivity hypothesis of Having.world_bound is essential,
in contrast with Having.F_eq_S where it can be dropped.
Dependency graph
Having.G_eq_S_monus_S fails without mul_sub_left_distributive.
The HAVING count = 1 identity G_1(U) = S_1(U) ⊖ S_2(U) does not hold in
ChainFive for α = (mid, hi, hi): the left-hand side is mid, the
right-hand side 𝟘.
Dependency graph
Having.atMost_eq_S_monus_S fails without mul_sub_left_distributive.
The HAVING count ≤ 1 identity does not hold in ChainFive for
α = (mid, hi, hi): the left-hand side is mid, the right-hand side 𝟘.