Preprints

We study the congruence lattices of the multinomial lattices L(v) introduced by Bennett and Birkhoff. Our main motivation is to investigate Parikh equivalence relations that model concurrent computation. We accomplish this goal by providing an explicit description of the join dependency relation between two join irreducible elements and of its reflexive transitive closure. The explicit description emphasizes several properties and makes it possible to separate the equational theories of multinomial lattices by their dimensions. In their covering of non modular varieties Jipsen and Rose define a sequence of equations SD_n(/\), for n >= 0. Our main result sounds as follows: if v = (v₁,... ,v_n) in Nⁿ and v_i > 0 for i = 1,... ,n, then the multinomial lattice L(v) satisfies SD_n-1(/\) and fails SD_n-2(/\).

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 Σ₁-operations satisfy the constructive relation μ_x.f = _{n >= 0} fⁿ(). These properties imply the following statement: 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(Σ₁,Π₁) of the fixed point alternation hierarchy.

We prove that every finitary polynomial endofunctor of a category C has a final coalgebra if C is locally Cartesian closed, has finite disjoint coproducts and a natural number object. More generally, we prove that the category of coalgebras for such an endofunctor has all finite limits.

We have investigated axioms related to linear negation in the context of intuitionistic generalization of complete semantics for Distributive Linear Logic presented in [GM]. We show that internal monoids in the monoidal category of bimodules between partially ordered sets provide a complete semantics for Linear Logic based on intuitionism. The basic framework is a set with a partial order and a ternary relation which satisfies compatibility conditions with the order, as also shown in [AD]. We give concrete examples of such structures: one of them is suggested by an immediate generalization to intuitionism of the quantale of all relations over a set; another universe can be obtained by putting together all the individuals of a monoid in presheaves. The analysis in this context of axioms ruling linear negation has followed the suggestion in [Yet]: condition of being a dualizing element and condition of being a cyclic element have been analyzed separately. Since the starting point of our work has been the observation that groupoids are models not only for linear logic, but also for classical linear logic when a proper choice of linear false is done, we have investigated also syntactic conditions which are always valid in these particular universes. These are a non-contradiction principle which merges cartesian conjunction with linear negation and true, and De Morgan laws of complement with respect to linear conjunction and disjunction. In the classical case the non contradiction principle is equivalent to take as linear false the complement of unity. This choice leads in groupoids to satisfy De Morgan laws which are however not derivable; which is proved by construction of counterexamples. Quantifiers elimination by means of properties of the free algebra of lower sets has been the general method followed in the analysis from syntax to semantics. A second part of the work has confronted the opposite problem: given semantic conditions we show that, from their truth in the canonical model of prime filters, equivalent syntactic conditions are found. In this case an analogous way of eliminating quantifiers over prime filters needs the extensive use of Extension/Exclusion Lemma which requires the axiom of choice. Beside the problem of extending a theory in which a syntactic condition holds to a complete one, there is the research of syntactic equivalents to interesting semantic conditions. [AD] G. Allwein - J.M. Dunn, Kripke Models for Linear Logic, The Journal of Symbolic Logic, Volume 58, Number 2, (1993), pp. 514-545; [GM] S. Ghilardi - G. Meloni, Modal logics with n-ary connectives, Zeitschr.f.math.Logik und Grundlagen d.Math., Bd. 36, S.193-215 (1990); [Yet] D.N. Yetter, Quantales and (noncommutative) linear logic, The Journal of Symbolic Logic, Volume 55, Number 1, (1990), pp. 41-64;