Documentation

Provenance.Semirings.Tropical

Tropical m-semiring #

This file shows that the tropicalization of any linearly ordered additive commutative monoid with an absorbing top element (e.g., ℕ ∪ {∞}, ℚ ∪ {∞}, ℝ ∪ {∞}) is a commutative m-semiring. Addition is min (inherited from the tropical structure in Mathlib), multiplication is the original addition of the monoid, zero is ⊤, and one is 0.

The tropical semiring is absorptive and idempotent, and satisfies left-distributivity of multiplication over monus.

Which order a line speaks in. Two orders live here and they are opposite: the semiring's natural order, in which the axioms and every statement of Provenance.SemiringWithMonus are written (𝟘 = ⊤ is the least element, and a ≤ b is untrop a ≥ untrop b), and the carrier's order, in which the monus is implemented (a ⊖ b = ⊤ where untrop a ≥ untrop b). A statement about this semiring therefore reads as its own opposite depending on which order the reader supplies, and the proofs below say untrop wherever they mean the carrier's. The same reversal is in Provenance.Semirings.MinMax, and it has misled a reader of each file at least once: when a line looks like the negation of what it should say, check which order it is written in before believing either.

The tropical semiring is used as a provenance semiring in Green, Karvounarakis & Tannen, Provenance Semirings.

Note: Geerts & Poggi, On database query languages for K-relations, Example 4 claims that the tropical semiring cannot be extended to an m-semiring. That claim is incorrect: Geerts & Poggi give a wrong definition of the monus operator.

References #

@[instance_reducible]
Equations
Dependency graph
@[instance_reducible]
Equations
Dependency graph

In the tropicalization of a linear order, a ≥ b if and only if a+b = b.

Dependency graph

ProvSQL's Tropical::delta: the indicator of being nonzero.

Equations
Instances For
    Dependency graph
    @[instance_reducible]

    The tropical semiring is an m-semiring. The natural order of the semiring is the reverse of the usual order. The monus a-b is defined as ⊤ if a≥b (for the usual order, not the natural semiring order), and as a otherwise.

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

    The tropical semiring over ℕ ∪ {∞} is a semiring with monus.

    Equations
    Dependency graph
    Dependency graph
    @[instance_reducible]

    The tropical semiring over ℚ ∪ {∞} is a semiring with monus.

    Equations
    Dependency graph
    Dependency graph
    @[instance_reducible]

    The tropical semiring over ℤ ∪ {∞} is a semiring with monus. Like the ℚ and ℝ variants it is idempotent and ⊗-over-⊖ distributive but not absorptive; unlike them its carrier is kernel-computable, which makes it the tropical semiring of choice for decide-checked counterexamples.

    Equations
    Dependency graph
    Dependency graph
    Dependency graph
    @[instance_reducible]

    The tropical semiring over ℝ ∪ {∞} is a semiring with monus. Note that this contradicts Geerts & Poggi, On database query languages for K-relations, Example 4 which claims this semiring cannot be extended to a semiring with monus: indeed, that paper gives a wrong definition of the monus operator in the tropical semiring.

    Equations
    Dependency graph
    Dependency graph

    The tropical semiring is absorptive, as long as the order in the addition monoid corresponds to a canonical order (e.g., as in ℕ) -

    Dependency graph
    Dependency graph

    The tropical semiring over WithTop ℕ is not exclusive: absorptive and totally ordered, with trop 1 neither 𝟘 = trop ⊤ nor 𝟙 = trop 0, so 𝟙 ⊖ trop 1 = 𝟙 and trop 1 ⊗ 𝟙 = trop 1.

    Dependency graph

    On the tropical semiring over ℕ ∪ {∞} the identity is not an admissible δ, even though this semiring is absorptive (MinTropicalN.absorptive): what delta_absorb asks of δ := id is the lattice law a ⊗ (a ⊕ b) = a, i.e., a + min(a, b) = a in ℕ, and at a = b = trop 1 it reads trop 2 ≠ trop 1. This is why the instance takes the support indicator (ProvSQL's Tropical::delta).

    Dependency graph

    Times distributes over monus on tropical semirings made of an order strictly compatible with addition, with an additional top element.

    Dependency graph
    Dependency graph
    Dependency graph
    Dependency graph

    The tropical semiring is idempotent -

    Dependency graph

    The tropical semiring over WithTop R (for any R with Zero R) has characteristic 0 in the CharP sense: it is idempotent, and (0 : MinTropical (WithTop R)) = trop ⊤ differs from (1 : MinTropical (WithTop R)) = trop 0 since ⊤ ≠ 0 in WithTop R.

    Dependency graph
    Dependency graph
    Dependency graph

    The tropical semiring over ℕ ∪ {∞} does not have idempotent multiplication: MinTropical.trop 1 * MinTropical.trop 1 = MinTropical.trop 2 ≠ MinTropical.trop 1. (MinTropical multiplication is the original additive monoid operation, which is not idempotent on ℕ.)

    Dependency graph
    theorem MinTropicalN.no_hom_from_BoolFunc {Y : Type} [Inhabited Y] :
    ∃ (ν : Y → MinTropical (WithTop ℕ)), ¬∃ (φ : BoolFunc Y →+* MinTropical (WithTop ℕ)), ∀ (i : Y), φ (BoolFunc.var i) = ν i

    There is no semiring homomorphism from BoolFunc Y to the tropical semiring over ℕ ∪ {∞} sending the variables to arbitrary values: tropical multiplication is not idempotent, contradicting var i * var i = var i in BoolFunc Y.

    Dependency graph

    Counterexample to Having.F_eq_S without absorptivity #

    Unlike MinTropical (WithTop ℕ) (canonically ordered, hence absorptive via MinTropical.absorptive), MinTropical (WithTop ℝ) is not absorptive: with a = trop (-1) we have 1 + a = trop (min 0 (-1)) = trop (-1) ≠ trop 0 = 1.

    The tropical m-semiring over ℝ is still idempotent and satisfies mul_sub_left_distributive, so it satisfies the “idempotent + ⊗-over-⊖ distributive” hypotheses one might hope to suffice for Having.F_eq_S. The witness below shows that the strengthened hypothesis (absorptivity) is genuinely required: on U = {true, false} ⊆ Bool and α ≡ trop (-1) we have S_1(U) = trop (-1) but F_1(U) = trop (-2).

    MinTropical (WithTop ℝ) is not absorptive: 1 + trop (-1) = trop (-1) ≠ 1. The proof goes through tropical_order_ge: a + 1 = 1 would force untrop a ≥ untrop 1 = 0, but with a = trop (-1) we have untrop a = -1.

    Dependency graph
    noncomputable def MinTropicalR.α_ce :

    Counterexample family: the constant α ≡ trop (-1) on Bool.

    Equations
    Instances For
      Dependency graph

      The HAVING-count identity F_C(U) = S_C(U) from Having.F_eq_S fails in MinTropical (WithTop ℝ): with U = Finset.univ : Finset Bool, α ≡ trop (-1), and C = 1, we have F_1(U) = trop (-2) while S_1(U) = trop (-1). This shows that Having.F_eq_S genuinely needs the absorptivity hypothesis (cf. MinTropicalR.not_absorptive): the weaker “idempotent + mul_sub_left_distributive” combination satisfied by MinTropical (WithTop ℝ) (and likewise by MinTropical (WithTop ℚ)) is insufficient.

      Dependency graph
      noncomputable def MinTropicalR.t_ce :
      Bool → ℝ

      Counterexample aggregate term: the constant t ≡ 0 on Bool.

      Equations
      Instances For
        Dependency graph

        The MIN-scan collapse (Having.minScan_correct) fails in MinTropical (WithTop ℝ): on U = {true, false} with α ≡ trop (-1), t ≡ 0 and the predicate MIN(t) ≥ 0, the possible-world provenance is trop (-2) while the scan returns trop (-1). This is the same instance as MinTropicalR.F_ne_S, and shows that the absorptivity hypothesis of Having.minScan_correct (and, by symmetry, of Having.maxScan_correct and Having.firstScan_correct) is genuinely required: the weaker “idempotent + mul_sub_left_distributive” combination satisfied by MinTropical (WithTop ℝ) is insufficient.

        Dependency graph