The security semiring, and every Boolean algebra as an m-semiring #
The alternative security semiring Sā² of Amsterdamer, Deutch and
Tannen annotates a tuple with the set of clearance levels at which it may
be seen: ā is union, ā is intersection, š is the empty set, š is
the whole set L of levels, the monus is set difference and Ī“ is the
identity. It is š¹^L, and nothing about it is special to sets: the
construction below reads any Boolean algebra as an m-semiring, with
ā = ā, ā = ā, a ā b = a \ b and Ī“ = id, and Sā² is that
construction at Set L.
BooleanAlgebra.toSemiringWithMonus is a def and deliberately not
an instance: Bool, Prop, Set α and α ā Bool are all Boolean
algebras in Mathlib, so a global instance would collide with the
catalog's own š¹ and š¹[X] instances and would put a second Add,
Mul and Sub on anything else Mathlib happens to make a Boolean
algebra. Types that want it ask for it, as Security does below.
What the construction satisfies is every property the library states of
an m-semiring at once: both idempotences, absorptivity, exclusivity,
complementedness, left-distributivity of ā over ā, and Ī“ = id.
Among m-semirings that are lattices, exclusivity is being a Boolean algebra
(monus_one_isCompl, monus_one_unique_compl).
The commutative semiring of a Boolean algebra: join for ā, meet
for ā. Separated from the m-semiring below so that the numerals and
the natural-number cast are available while the monus part is built.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Every positive natural-number cast is š, join being idempotent.
Dependency graph
Every Boolean algebra is an m-semiring**: join for ā, meet for
ā, the difference for the monus, and the identity for Ī“. A def and
not an instance, for the reason in this file's header.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The security semiring #
Sā² L is the construction at Set L: a tuple is annotated with the set
of clearance levels at which it may be seen, ā collects levels, ā
requires them, and the monus removes them. Its own type keeps the
construction's Add, Mul and Sub off Set L itself, where Mathlib's
would clash.
The alternative security semiring Sā² = š¹^L: the subsets of a
set L of clearance levels.
Instances For
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
Dependency graph
Dependency graph
Dependency graph
Equations
- Security.instCommSemiringWithMonus = { toSemiringWithMonus := Security.instSemiringWithMonus, mul_comm := ⯠}