Documentation

Provenance.Semirings.MinMax

Min-max semiring #

This file defines the min-max semiring MinMax α over a bounded linear order α, where addition is min and multiplication is max. The natural order is the reverse of the order on α (so ⊤ is the additive identity and ⊥ the multiplicative identity). This semiring models security levels or (dually) the fuzzy semiring.

Which order a line speaks in. The two orders are opposite, and a statement reads as its own negation if the reader supplies the wrong one: the semiring's natural order is what the axioms and every statement of Provenance.SemiringWithMonus use (𝟘 = ⊤ is least), while the carrier's order on α is what the monus is implemented in (a ⊖ b = ⊤ where a.val ≥ b.val). The proofs below say .val wherever they mean the carrier's. Provenance.Semirings.Tropical has the same reversal, and each file has misled a reader at least once: when a line looks backwards, check which order it is written in first.

Also defined:

MinMax α is absorptive and idempotent. The dual MaxMin TVL does not satisfy left-distributivity of multiplication over monus.

The security/access control semiring is discussed in Green & Tannen, The Semiring Framework for Database Provenance.

References #

structure MinMax (α : Type) :

The min-max semiring over a bounded linear order: addition is min, multiplication is max, zero is ⊤ and one is ⊥. The natural order is the reverse of α's order.

  • val : α
Instances For
    Dependency graph
    theorem MinMax.ext {α : Type} {x y : MinMax α} (val : x.val = y.val) :
    x = y
    Dependency graph
    theorem MinMax.ext_iff {α : Type} {x y : MinMax α} :
    x = y ↔ x.val = y.val
    Dependency graph
    @[instance_reducible]
    instance instCoeMinMax {α : Type} :
    Coe (MinMax α) α
    Equations
    Dependency graph
    @[instance_reducible]
    instance instTopMinMax {α : Type} [LinearOrder α] [OrderTop α] :
    Top (MinMax α)
    Equations
    Dependency graph
    @[instance_reducible]
    instance instBotMinMax {α : Type} [LinearOrder α] [OrderBot α] :
    Bot (MinMax α)
    Equations
    Dependency graph
    @[instance_reducible]
    instance instLEMinMax {α : Type} [LinearOrder α] :
    LE (MinMax α)
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    instance instZeroMinMax {α : Type} [LinearOrder α] [OrderTop α] :
    Equations
    Dependency graph
    @[instance_reducible]
    instance instAddMinMax {α : Type} [LinearOrder α] :
    Add (MinMax α)
    Equations
    Dependency graph
    @[instance_reducible]
    instance instOneMinMax {α : Type} [LinearOrder α] [OrderBot α] :
    One (MinMax α)
    Equations
    Dependency graph
    @[instance_reducible]
    instance instMulMinMax {α : Type} [LinearOrder α] :
    Mul (MinMax α)
    Equations
    Dependency graph
    @[instance_reducible]
    instance instSubMinMax {α : Type} [LinearOrder α] [OrderTop α] :
    Sub (MinMax α)
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]

    MinMax α is a commutative m-semiring for any bounded linear order α.

    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    Dependency graph
    theorem MinMax.not_exclusive {α : Type} [LinearOrder α] [OrderBot α] [OrderTop α] {a : α} (h0 : a ≠ ⊤) (h1 : a ≠ ⊥) :

    MinMax α is not exclusive as soon as the chain has an element other than its two bounds: it is absorptive and totally ordered, so not_exclusive_of_absorptive_of_total applies. Here 𝟘 = ⊤ and 𝟙 = ⊥.

    Dependency graph
    Dependency graph
    Dependency graph
    instance MinMax.instCharPZero {α : Type} [LinearOrder α] [OrderBot α] [OrderTop α] [Nontrivial α] :
    CharP (MinMax α) 0

    MinMax α has characteristic 0 in the CharP sense whenever α is nontrivial: it is idempotent, and (0 : MinMax α) = ⟨⊤⟩ differs from (1 : MinMax α) = ⟨⊥⟩ since ⊥ ≠ ⊤ in a nontrivial bounded order.

    Dependency graph
    @[reducible, inline]
    abbrev MaxMin (α : Type) :
    Equations
    Instances For
      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
      Dependency graph
      inductive TVL :

      Three-valued logic {⊥, unknown, ⊤}, used as an instance of MaxMin.

      Instances For
        Dependency graph
        @[instance_reducible]
        Equations
        Dependency graph
        @[instance_reducible]
        instance instReprTVL :
        Equations
        Dependency graph
        Equations
        Instances For
          Dependency graph
          @[instance_reducible]
          instance instOrdTVL :
          Equations
          Dependency graph
          Equations
          Instances For
            Dependency graph
            @[instance_reducible]
            instance instLETVL :
            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
            Dependency graph
            Dependency graph
            Dependency graph
            Dependency graph
            instance MaxMin.instCharPZero {α : Type} [LinearOrder α] [OrderBot α] [OrderTop α] [Nontrivial α] :
            CharP (MaxMin α) 0

            MaxMin α has characteristic 0 in the CharP sense whenever α is nontrivial: this lifts the general MinMax instance to the dual order through MaxMin α = MinMax (OrderDual α). In particular it applies to MaxMin TVL since TVL is nontrivial.

            Dependency graph
            Dependency graph

            Orientation #

            The carrier is α with its order reversed: 𝟘 is α's top and 𝟙 its bottom, ⊕ is α's min and ⊗ its max, and ≤ on MinMax α is ≥ on α. The point of the reversal is that the semiring order comes out the right way up – 𝟘 least and 𝟙 greatest, as a canonically ordered semiring needs – so read in the semiring, ⊕ is the join, ⊗ the meet, 𝟙 the top and 𝟘 the bottom. A statement about min-max is therefore true in either telling; only the α-values change places, which is worth saying because 𝟙 = ⟨⊥⟩ reads as “𝟙 is the bottom” and means the opposite.