Lattices do not distribute over powerset
- PDF / 334,300 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 2 Downloads / 200 Views
Algebra Universalis
Lattices do not distribute over powerset Juli´an Salamanca T´ellez Dedicated to Jairo Agudelo Gonz´ alez. Abstract. We show that there is no distributive law of the free lattice monad over the powerset monad. The proof presented here also works for other classes of lattices such as (bounded) distributive/modular lattices and also for some variants of the powerset monad such as the (nonempty) finite powerset monad. Mathematics Subject Classification. 18A23, 18C15, 06B25, 06A12. Keywords. Distributive laws, Monads, Lattice, Complete semilattice, Powerset.
1. Introduction Distributive laws were introduce by Jon Beck [1], they provide a canonical way to compose monads and also allow to lift functors/monads to the category of algebras for a functor/monad. The classical example is the distributive law of product over addition which defines a distributive law of the free monoid monad over the free abelian group monad. This distributive law allows to compose those two monads in order to obtain the free ring monad. Distributive laws of a functor/monad over the powerset (monad) are of particular interest in computer science and category theory. In computer science, they are studied in automata theory [9], the so-called powerset construction or determinization, and in (guarded) structural operational semantics [10], SOS and GSOS. In category theory, they are of particular interest in the subject of relation lifting [5,7]. There are well-known canonical laws over the powerset, such as the distributive law of the free monoid monad over the powerset monad given by the Presented by J. Ad´ amek. The research of the author was supported by the European Union’s Horizon 2020 research and innovation programme (grant agreement No 683080). 0123456789().: V,-vol
49
Page 2 of 11
J. Salamanca T´ ellez
Algebra Univers.
law A · B → { a · b | a ∈ A, b ∈ B }. Such a canonical law over the powerset can be defined for any functor [5, Section 4] but in general is not a natural transformation. If the functor preserves weak pullbacks this canonical law is a natural transformation and it is distributive law of the functor over the powerset monad [5]. Additionally, if the functor has a monad structure in which the unit and the multiplication are weakly cartesian, meaning that each naturality square is a weak pullback, then this law is a distributive law between monads. From the perspective of universal algebra, the previous canonical law, that lifts a basic operation to its subsets by choosing elements in each subset and then applies the basic operation, provides the construction of power algebras (also known as complex algebras or global algebras) [3,4]. It is well-know that such construction only preserves regular linear identities [3, Theorem 5]. In particular, the non-linear axiom x ∨ (x ∧ y) = x of absorption in the theory of lattices is not preserved. As a consequence, the previous canonical law is not a distributive law of the lattice monad over the powerset monad (in fact, it is not even a natural transformation!).
Data Loading...
