Documentation

Provenance.BooleanSemiring

Lattice and Boolean m-semirings, and their points #

The m-semirings in which โŠ• and โŠ— are a bounded distributive lattice, those in which ๐Ÿ™ โŠ– ยท is moreover a complement, and the homomorphisms onto ๐”น that separate the elements of either.

IsLatticeSemiring K says that K is absorptive (๐Ÿ™ โŠ• a = ๐Ÿ™, which gives a โŠ• a = a and a โŠ• a โŠ— b = a) and that โŠ— is idempotent. That is what makes (K, โŠ•, โŠ—) a bounded distributive lattice for the natural order of K: IsLatticeSemiring.distribLattice and IsLatticeSemiring.boundedOrder build the structures on the order K already carries, with โŠ” = โŠ•, โŠ“ = โŠ—, โŠฅ = ๐Ÿ˜ and โŠค = ๐Ÿ™. IsBooleanSemiring K adds exclusivity, a โŠ— (๐Ÿ™ โŠ– a) = ๐Ÿ˜, under which ๐Ÿ™ โŠ– ยท is the complement (monus_one_isCompl) and the monus is a โŠ– b = a โŠ— (๐Ÿ™ โŠ– b) (IsBooleanSemiring.monus_eq_mul_one_monus).

A point of K is a semiring homomorphism K โ†’+* ๐”น. Over a lattice m-semiring the points separate the elements (IsLatticeSemiring.exists_point_ne, off Mathlib's prime separation theorem for distributive lattices): two elements agreeing at every point are equal (IsLatticeSemiring.eq_of_forall_point). Over a Boolean m-semiring a point preserves the monus as well (IsBooleanSemiring.map_monus), and when ฮด is the identity it is an m-semiring homomorphism (IsBooleanSemiring.pointHom). These are what the extensionality theorem of Provenance.Extensionality uses: the annotation of a tuple is determined by its images at the points, and each image is a plain evaluation.

Lattice m-semirings #

A lattice m-semiring: absorptive, with an idempotent โŠ—. These are the m-semirings in which (K, โŠ•, โŠ—) is a bounded distributive lattice, ๐Ÿ˜ its bottom and ๐Ÿ™ its top.

Instances For
    Dependency graph

    A Boolean m-semiring: a lattice m-semiring that is exclusive, so that ๐Ÿ™ โŠ– a is the complement of a.

    Instances For
      Dependency graph
      Dependency graph

      The order of K is a โ‰ค b โ†” a โŠ• b = b.

      Dependency graph
      theorem IsLatticeSemiring.mul_le_mul {K : Type} [CommSemiringWithMonus K] (_h : IsLatticeSemiring K) {a b c d : K} (hab : a โ‰ค b) (hcd : c โ‰ค d) :
      a * c โ‰ค b * d

      Multiplication is monotone in both arguments.

      Dependency graph

      Points #

      A point is a semiring homomorphism K โ†’+* ๐”น. Each proper prime ideal J of the lattice gives one, a โ†ฆ [a โˆ‰ J]: the complement of a prime ideal is closed under โŠ“, and the complement of an ideal is upward closed and closed under the two sides of a โŠ”.

      theorem IsLatticeSemiring.exists_point_ne {K : Type} [CommSemiringWithMonus K] (h : IsLatticeSemiring K) {a b : K} (hab : a โ‰  b) :
      โˆƒ (f : K โ†’+* Bool), f a โ‰  f b

      The points separate the elements: two distinct elements of a lattice m-semiring differ at some point. One of the two is not below the other, so the principal filter of the first and the principal ideal of the second are disjoint, and a prime ideal extending the ideal and avoiding the filter gives a point true on the first and false on the second.

      Dependency graph
      theorem IsLatticeSemiring.eq_of_forall_point {K : Type} [CommSemiringWithMonus K] (h : IsLatticeSemiring K) {a b : K} (hf : โˆ€ (f : K โ†’+* Bool), f a = f b) :
      a = b

      Two elements agreeing at every point are equal.

      Dependency graph

      Boolean m-semirings #

      The monus of a Boolean m-semiring is a โŠ— (๐Ÿ™ โŠ– b): the meet with the complement, which residuation determines.

      Dependency graph
      theorem IsBooleanSemiring.map_one_monus {K : Type} [CommSemiringWithMonus K] (h : IsBooleanSemiring K) (f : K โ†’+* Bool) (b : K) :
      f (1 - b) = !f b

      A point sends ๐Ÿ™ โŠ– b to the negation of its value at b: the two join to ๐Ÿ™ and meet at ๐Ÿ˜, and so do their images.

      Dependency graph
      theorem IsBooleanSemiring.map_monus {K : Type} [CommSemiringWithMonus K] (h : IsBooleanSemiring K) (f : K โ†’+* Bool) (a b : K) :
      f (a - b) = f a - f b

      A point of a Boolean m-semiring preserves the monus, the monus of ๐”น being a โˆง ยฌ b.

      Dependency graph
      @[instance_reducible]

      A point is an m-semiring homomorphism when ฮด is the identity, the ฮด of ๐”น being the identity too.

      Equations
      • h.pointHom hฮด f = { toRingHom := f, map_sub := โ‹ฏ, map_delta := โ‹ฏ }
      Instances For
        Dependency graph
        @[simp]
        theorem IsBooleanSemiring.pointHom_apply {K : Type} [CommSemiringWithMonus K] (h : IsBooleanSemiring K) (hฮด : โˆ€ (a : K), SemiringWithMonus.delta a = a) (f : K โ†’+* Bool) (a : K) :
        (fun (x : K) => (h.pointHom hฮด f).toRingHom x) a = f a

        The underlying function of pointHom is the point.

        Dependency graph

        From the two identities to the lattice, and back #

        The paper states the lattice condition as three identities, a โŠ• a = a, a โŠ— a = a and a โŠ• a โŠ— b = a; the library's absorptive is ๐Ÿ™ โŠ• a = ๐Ÿ™. The absorption law and absorptive are equivalent in every semiring, with no idempotence needed โ€“ one is the other at a = ๐Ÿ™, and ๐Ÿ™ โŠ• b = ๐Ÿ™ gives a โŠ• a โŠ— b = a โŠ— (๐Ÿ™ โŠ• b) = a โ€“ and a โŠ• a = a follows from either (idempotent_of_absorptive). So the paper's class and IsLatticeSemiring are the same class, which is recorded here so that either form can be read off the other.

        theorem absorptive_of_add_mul_self {K : Type} [CommSemiringWithMonus K] (h : โˆ€ (a b : K), a + a * b = a) :

        ๐Ÿ™ โŠ• a = ๐Ÿ™ from the absorption law a โŠ• a โŠ— b = a, at a = ๐Ÿ™.

        Dependency graph
        theorem add_mul_self_of_absorptive {K : Type} [CommSemiringWithMonus K] (h : absorptive K) (a b : K) :
        a + a * b = a

        The absorption law from ๐Ÿ™ โŠ• a = ๐Ÿ™.

        Dependency graph
        theorem IsLatticeSemiring.mul_add_self {K : Type} [CommSemiringWithMonus K] (h : IsLatticeSemiring K) (a b : K) :
        a * (a + b) = a

        The other absorption law, a โŠ— (a โŠ• b) = a, from distributivity and the first.

        Dependency graph

        ๐Ÿ™ is the top of the natural order.

        Dependency graph