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.
- absorptive : _root_.absorptive K
๐ โ a = ๐. - mulIdempotent : _root_.mulIdempotent K
a โ a = a.
Instances For
Dependency graph
A Boolean m-semiring: a lattice m-semiring that is exclusive, so
that ๐ โ a is the complement of a.
- exclusive : _root_.exclusive K
a โ (๐ โ a) = ๐.
Instances For
Dependency graph
โ is idempotent.
Dependency graph
The order of K is a โค b โ a โ b = b.
Dependency graph
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 โ.
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
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
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
A point of a Boolean m-semiring preserves the monus, the monus of
๐น being a โง ยฌ b.
Dependency graph
A point is an m-semiring homomorphism when ฮด is the identity,
the ฮด of ๐น being the identity too.
Instances For
Dependency graph
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.
๐ โ a = ๐ from the absorption law a โ a โ b = a, at a = ๐.
Dependency graph
The absorption law from ๐ โ a = ๐.
Dependency graph
The other absorption law, a โ (a โ b) = a, from distributivity
and the first.
Dependency graph
๐ is the top of the natural order.