Documentation

Provenance.Semirings.ChainFive

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:

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.

inductive ChainFive :

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
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    Dependency graph
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]

    Addition is max (the chain join).

    Equations
    Dependency graph
    @[instance_reducible]

    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
    @[instance_reducible]

    The chain monus: a ⊖ b = 𝟘 if a ≤ b, and a otherwise.

    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    Dependency graph
    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
    Instances For
      Dependency graph
      theorem ChainFive.not_world_bound :
      ¬∀ (α : Fin 3 → ChainFive) (U W : Finset (Fin 3)), W ⊆ U → ∀ (j C : ℕ), j ≤ W.card → W.card ≤ C → Having.T α U W ≤ Having.S α U j - Having.S α U (C + 1)

      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 𝟘.

      Dependency graph