2005/08/22 by Luigi Santocanale, Santocanale, Luigi
Mathematics · #03B45 #03B70 #03G10 #13B23 #FOS: Mathematics #Logic (math.LO) #Rings and Algebras (math.RA) #math.LO #math.RA #msc:03B45 #msc:03B70 #msc:03G10 #msc:13B23
paper · pdf · doi:10.48550/arxiv.math/0508412
36 pages, extended abstract appears in LICS 2005 proceedings
arxiv created 2005/08/22 · arxiv updated 2009/12/01
A μ-algebra is a model of a first order theory that is an extension of the theory of bounded lattices, that comes with pairs of terms (f,μx.f) where μx.f is axiomatized as the least prefixed point of f, whose axioms are equations or equational implications. Standard μ-algebras are complete meaning that their lattice reduct is a complete lattice. We prove that any non trivial quasivariety of μ-algebras contains a μ-algebra that has no embedding into a complete μ-algebra. We focus then on modal μ-algebras, i.e. algebraic models of the propositional modal μ-calculus. We prove that free modal μ-algebras satisfy a condition -- reminiscent of Whitman's condition for free lattices -- which allows us to prove that (i) modal operators are adjoints on free modal μ-algebras, (ii) least prefixed points of Σ1-operations satisfy the constructive relation μx.f = \bigveen ≥ 0 fn(\bot). These properties imply the following statement: \em the MacNeille-Dedekind completion of a free modal μ-algebra is a complete modal μ-algebra and moreover the canonical embedding preserves all the operations in the class Comp(Σ1,Π1) of the fixed point alternation hierarchy.