It was shown in [3] (see also [5]) that there is a duality between the category of bounded distributive lattices endowed with a join-homomorphism and the category of Priestley spaces endowed with a Priestley relation. In this paper, bounded distributive lattices endowed with a join-homomorphism, are considered as algebras and we characterize the congruences of these algebras in terms of the mentioned duality and certain closed subsets of Priestley spaces. This enable us to characterize the simple and subdirectly (...) irreducible algebras. In particular, Priestley relations enable us to characterize the congruence lattice of the Q-distributive lattices considered in [4]. Moreover, these results give us an effective method to characterize the simple and subdirectly irreducible monadic De Morgan algebras [7].The duality considered in [4], was obtained in terms of the range of the quantifiers, and such a duality was enough to obtain the simple and subdirectly irreducible algebras, but not to characterize the congruences. (shrink)
My purpose in this paper is to analyze some aspects of the theory of Boolean algebras and distributive lattices within a constructive context, in particular, without employing the law of excluded middle. Throughout, we work within a constructive set theory which, provided with a suitable type-theoretic formulation, can be interpreted within an arbitrary topos (see,e.g. [3]).
An Ockham lattice is defined to be a distributive lattice with 0 and 1 which is equipped with a dual homomorphic operation. In this paper we prove: (1) The lattice of all equational classes of Ockham lattices is isomorphic to a lattice of easily described first-order theories and is uncountable, (2) every such equational class is generated by its finite members. In the proof of (2) a characterization of orderings of with respect to which the successor function is decreasing (...) is given. (shrink)
We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements (...) are disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)
The dual spaces of the free distributive lattices with a quantifier are constructed, generalizing Halmos' construction of the dual spaces of free monadic Boolean algebras.
It is well known that for all recursively enumerable sets X 1 , X 2 there are disjoint recursively enumerable sets Y 1 , Y 2 such that $Y_1 \subseteq X_1, Y_2 \subseteq X_2$ and Y 1 ∪ Y 2 = X 1 ∪ X 2 . Alistair Lachlan called distributive lattices satisfying this property separated. He proved that the first-order theory of finite separated distributive lattices is decidable. We prove here that the first-order theory of all separated (...)distributive lattices is undecidable. (shrink)
The main goal of this paper is to explain the link between the algebraic models and the Kripke-style models for certain classes of propositional non-classical logics. We consider logics that are sound and complete with respect to varieties of distributive lattices with certain classes of well-behaved operators for which a Priestley-style duality holds, and present a way of constructing topological and non-topological Kripke-style models for these types of logics. Moreover, we show that, under certain additional assumptions on the variety (...) of the algerabic models of the given logics, soundness and completeness with respect to these classes of Kripke-style models follows by using entirely algebraical arguments from the soundness and completeness of the logic with respect to its algebraic models. (shrink)
The main goal of this paper is to explain the link between the algebraic and the Kripke-style models for certain classes of propositional logics. We start by presenting a Priestley-type duality for distributive lattices endowed with a general class of well-behaved operators. We then show that finitely-generated varieties of distributive lattices with operators are closed under canonical embedding algebras. The results are used in the second part of the paper to construct topological and non-topological Kripke-style models for logics (...) that are sound and complete with respect to varieties of distributive lattices with operators in the above-mentioned classes. (shrink)
By a lattice we shall always mean a distributive lattice which is bounded, i.e. has both a bottom element 0 and a top element 1. Lattice homomorphisms will always be assumed to preserve 0 and 1.
The lattices of the title generalize the concept of a De Morgan lattice. A representation in terms of ordered topological spaces is described. This topological duality is applied to describe homomorphisms, congruences, and subdirectly irreducible and free lattices in the category. In addition, certain equational subclasses are described in detail.
We define a variant of the standard Kripke semantics for intuitionistic logic, motivated by the connection between constructive logic and the Medvedev lattice. We show that while the new semantics is still complete, it gives a simple and direct correspondence between Kripke models and algebraic structures such as factors of the Medvedev lattice.
In our previous paper Algebraic Logic for Classical Conjunction and Disjunction we studied some relations between the fragmentL of classical logic having just conjunction and disjunction and the varietyD of distributive lattices, within the context of Algebraic Logic. The central tool in that study was a class of closure operators which we calleddistributive, and one of its main results was that for any algebraA of type (2,2) there is an isomorphism between the lattices of allD-congruences ofA and of all (...)distributive closure operators overA. In the present paper we study the lattice structure of this last set, give a description of its finite and infinite operations, and obtain a topological representation. We also apply the mentioned isomorphism and other results to obtain proofs with a logical flavour for several new or well-known lattice-theoretical properties, like Hashimoto's characterization of distributive lattices, and Priestley's topological representation of the congruence lattice of a bounded distributive lattice. (shrink)
The contributions in the book examine the historical and contemporary manifestations of organized crime, the symbiotic relationship between legitimate and ...
Distributive bounded lattices with a dual homomorphism as unary operation, called Ockham algebras, were firstly studied by Berman (1977). The varieties of Boolean algebras, De Morgan algebras, Kleene algebras and Stone algebras are some of the well known subvarieties of Ockham algebra. In this paper, new results about the congruence lattice of Ockham algebras are given. From these results and Urquhart's representation theorem for Ockham algebras a complete characterization of the subdirectly irreducible Ockham algebras is obtained. These results are (...) particularized for a large number of subvarieties of Ockham algebras. For these subvarieties a full description of their subdirectly irreducible algebras is given as well. (shrink)
We generalize Priestley duality for distributive lattices to a duality for distributive meet-semilattices. On the one hand, our generalized Priestley spaces are easier to work with than Celani’s DS-spaces, and are similar to Hansoul’s Priestley structures. On the other hand, our generalized Priestley morphisms are similar to Celani’s meet-relations and are more general than Hansoul’s morphisms. As a result, our duality extends Hansoul’s duality and is an improvement of Celani’s duality.
We prove the Finite Model Property (FMP) for Distributive Full Lambek Calculus ( DFL ) whose algebraic semantics is the class of distributive residuated lattices ( DRL ). The problem was left open in [8, 5]. We use the method of nuclei and quasi–embedding in the style of [10, 1].
This work is part of a wider investigation into lattice-structured algebras and associated dual representations obtained via the methodology of canonical extensions. To this end, here we study lattices, not necessarily distributive, with negation operations. We consider equational classes of lattices equipped with a negation operation ¬ which is dually self-adjoint (the pair (¬,¬) is a Galois connection) and other axioms are added so as to give classes of lattices in which the negation is De Morgan, orthonegation, antilogism, pseudocomplementation (...) or weak pseudocomplementation. These classes are shown to be canonical and dual relational structures are given in a generalized Kripke-style. The fact that the negation is dually self-adjoint plays an important role here, as it implies that it sends arbitrary joins to meets and that will allow us to define the dual structures in a uniform way. (shrink)
A Priestley duality is developed for the variety j of all modal lattices. This is achieved by restricting to j a known Priestley duality for the variety of all bounded distributive lattices with a meet-homomorphism. The variety j was first studied by R. Beazer in 1986.The dual spaces of free modal lattices are constructed, paralleling P.R. Halmos'' construction of the dual spaces of free monadic Boolean algebras and its generalization, by R. Cignoli, to distributive lattices with a quantifier.
Motivated by an old construction due to J. Kalman that relates distributive lattices and centered Kleene algebras we define the functor K • relating integral residuated lattices with 0 (IRL0) with certain involutive residuated lattices. Our work is also based on the results obtained by Cignoli about an adjunction between Heyting and Nelson algebras, which is an enrichment of the basic adjunction between lattices and Kleene algebras. The lifting of the functor to (...) the category of residuated lattices leads us to study other adjunctions and equivalences. For example, we treat the functor C whose domain is cuRL, the category of involutive residuated lattices M whose unit is fixed by the involution and has a Boolean complement c (the underlying set of C M is the set of elements greater or equal than c). If we restrict to the full subcategory NRL of cuRL of those objects that have a nilpotent c, then C is an equivalence. In fact, C M is isomorphic to C e M, and C e is adjoint to , where assigns to an object A of IRL0 the product A × A 0 which is an object of NRL. (shrink)
We introduce a notion of complexity for interpretations, which is used to prove some new results about interpretations of sequential theories. In particular, we give a new, elementary proof of Pudlák's theorem that sequential theories are connected. We also demonstrate a counterexample to the infinitary distributive law $a \vee \bigwedge_{i \in I} b_i = \bigwedge_{i \in I} (a \vee b_i)$ in the lattice of chapters, in which the chapters a and b i are compact. (Counterexamples in which a is (...) not compact have been found previously.). (shrink)
Given a variety we study the existence of a class such that S1 every A can be represented as a global subdirect product with factors in and S2 every non-trivial A is globally indecomposable. We show that the following varieties (and its subvarieties) have a class satisfying properties S1 and S2: p-algebras, distributive double p-algebras of a finite range, semisimple varieties of lattice expansions such that the simple members form a universal class (bounded distributive lattices, De Morgan algebras, (...) etc) and arithmetical varieties in which the finitely subdirectly irreducible algebras form a universal class (f-rings, vector groups, Wajsberg algebras, discriminator varieties, Heyting algebras, etc). As an application we obtain results analogous to that of Nachbin saying that if every chain of prime filters of a bounded distributive lattice has at most length 1, then the lattice is Boolean. (shrink)
We give an idea of uniform approach to the problem of characterization of absolute extensors for categories of topological spaces [21], closure spaces [15], Boolean algebras [22], and distributive lattices [4]. In this characterization we use the notion of retract of the closure space of filters in the lattice of all subsets.
This paper investigates the algebraic structure of the Medvedev lattice M. We prove that M is not a Heyting algebra. We point out some relations between M and the Dyment lattice and the Mucnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.
The strongly innovative theory of whole-parts relations outlined by Husserl in his Third logical Investigation?to which he attributed a basic value for his entire phenomenology?has recently attracted a renewed interest. Although many important issues have been clarified (especially by Kit Fine) the subject seems still worth being revisited. To this aim Husserlian universes are introduced. These are lower bounded distributive lattices endowed with a unary operation of defect and a binary relation of isogeneity. Husserl's contents are identified with nonzero (...) elements of a Husserlian universe and the dependence relations among contents are defined and studied starting from the idea that the defect of xis what x needs in order to ?exist? i.e., in order to be ?closed? with respect to the closure operation defined as the sup of x and its defect. It turns out that there are (at least) eight dependence relations which are worth to be considered. Many other questions concerning the world of contents (among them the proofs of the famous Husserl's Sätze) may now be discussed and clarified. Then the theory of species and genera is developed. Ultimate species (for short: species) are identified with equivalence classes of contents modulo isogeneity, and species in general (for short: genera) are identified with arbitrary unions of species. On the basis of the relation obtaining among two contents when they are isogeneous to two contents the first of which is a part of the second it becomes possible to develop a rather satisfying interpretation of Husserl's theory of the dependencies among species and genera and of the material a priori laws. By strengthening the notion of Husserlian universe into the notion of rigid Husserlian universe, the theory of species and genera obtains a stronger version. Three models of the theory are exhibited. The first one, suggested by combinatorial-topological considerations, identifies contents with finite non-empty sets of natural numbers; the second one identifies contents with non-empty sets of formulas of a formal language; the third one (not totally ?rigid?) identifies contents with positive integers. (shrink)
We present a Kripke model for Girard's Linear Logic (without exponentials) in a conservative fashion where the logical functors beyond the basic lattice operations may be added one by one without recourse to such things as negation. You can either have some logical functors or not as you choose. Commutatively and associatively are isolated in such a way that the base Kripke model is a model for noncommutative, nonassociative Linear Logic. We also extend the logic by adding a coimplication operator, (...) similar to Curry's subtraction operator, which is resituated with Linear Logic's contensor product. And we can add contraction to get nondistributive Relevance Logic. The model rests heavily on Urquhart's representation of nondistributive lattices and also on Dunn's Gaggle Theory. Indeed, the paper may be viewed as an investigation into nondistributive Gaggle Theory restricted to binary operations. The valuations on the Kripke model are three valued: true, false, and indifferent. The lattice representation theorem of Urquhart has the nice feature of yielding Priestley's representation theorem for distributive lattices if the original lattice happens to be distributive. Hence the representation is consistent with Stone's representation of distributive and Boolean lattices, and our semantics is consistent with the Lemmon-Scott representation of modal algebras and the Routley-Meyer semantics for Relevance Logic. (shrink)
In this paper we introduce a new natural deduction system for the logic of lattices, and a number of extensions of lattice logic with different negation connectives. We provide the class of natural deduction proofs with both a standard inductive definition and a global graph-theoretical criterion for correctness, and we show how normalisation in this system corresponds to cut elimination in the sequent calculus for lattice logic. This natural deduction system is inspired both by Shoesmith and Smiley's multiple conclusion systems (...) for classical logic and Girard's proofnets for linear logic. (shrink)
The goal of the paper is to develop a universal semantic approach to derivable rules of propositional multiple-conclusion sequent calculi with structural rules, which explicitly involve not only atomic formulas, treated as metavariables for formulas, but also formula set variables (viz., metavariables for finite sets of formulas), upon the basis of the conception of model introduced in (Fuzzy Sets Syst 121(3):27–37, 2001). One of the main results of the paper is that any regular sequent calculus with structural rules has such (...) class of sequent models (called its semantics ) that a rule is derivable in the calculus iff it is sound with respect to each model of the semantics. We then show how semantics of admissible rules of such calculi can be found with using a method of free models. Next, our universal approach is applied to sequent calculi for many-valued logics with equality determinant . Finally, we exemplify this application by studying sequent calculi for some of such logics. (shrink)
This paper defines a category of bounded distributive lattice-ordered grupoids with a left-residual operation that corresponds to a weak system in the family of relevant logics. Algebras corresponding to stronger systems are obtained by adding further postulates. A duality theoey piggy-backed on the Priestley duality theory for distributive lattices is developed for these algebras. The duality theory is then applied in providing characterizations of the dual spaces corresponding to stronger relevant logics.
In this paper we study the relations between the fragment L of classical logic having just conjunction and disjunction and the variety D of distributive lattices, within the context of Algebraic Logic. We prove that these relations cannot be fully expressed either with the tools of Blok and Pigozzi's theory of algebraizable logics or with the use of reduced matrices for L. However, these relations can be naturally formulated when we introduce a new notion of model of a sequent (...) calculus. When applied to a certain natural calculus for L, the resulting models are equivalent to a class of abstract logics (in the sense of Brown and Suszko) which we call distributive. Among other results, we prove that D is exactly the class of the algebraic reducts of the reduced models of L, that there is an embedding of the theories of L into the theories of the equational consequence (in the sense of Blok and Pigozzi) relative to D, and that for any algebra A of type (2,2) there is an isomorphism between the D-congruences of A and the models of L over A. In the second part of this paper (which will be published separately) we will also apply some results to give proofs with a logical flavour for several new or well-known lattice-theoretical properties. (shrink)
In this paper we study the relations between the fragment L of classical logic having just conjunction and disjunction and the variety D of distributive lattices, within the context of Algebraic Logic. We prove that these relations cannot be fully expressed either with the tools of Blok and Pigozzi's theory of algebraizable logics or with the use of reduced matrices for L. However, these relations can be naturally formulated when we introduce a new notion of model of a sequent (...) calculus. When applied to a certain natural calculus for L, the resulting models are equivalent to a class of abstract logics (in the sense of Brown and Suszko) which we call distributive. Among other results, we prove that D is exactly the class of the algebraic reducts of the reduced models of L, that there is an embedding of the theories of L into the theories of the equational consequence (in the sense of Blok and Pigozzi) relative to D, and that for any algebra A of type (2,2) there is an isomorphism between the D-congruences of A and the models of L over A. In the second part of this paper (which will be published separately) we will also apply some results to give proofs with a logical flavour for several new or well-known lattice-theoretical properties. (shrink)
Semi-DeMorgan algebras are a common generalization of DeMorgan algebras and pseudocomplemented distributive lattices. A duality for them is developed that builds on the Priestley duality for distributive lattices. This duality is then used in several applications. The subdirectly irreducible semi-DeMorgan algebras are characterized. A theory of partial diagrams is developed, where properties of algebras are tied to the omission of certain partial diagrams from their duals. This theory is then used to find and give axioms for the largest (...) variety of semi-DeMorgan algebras with the congruence extension property. (shrink)
LetL(K) denote the lattice (ordered by inclusion) of quasivarieties contained in a quasivarietyK and letD 2 denote the variety of distributive (0, 1)-lattices with 2 additional nullary operations. In the present paperL(D 2) is described. As a consequence, ifM+N stands for the lattice join of the quasivarietiesM andN, then minimal quasivarietiesV 0,V 1, andV 2 are given each of which is generated by a 2-element algebra and such that the latticeL(V 0+V1), though infinite, still admits an easy and nice (...) description (see Figure 2) while the latticeL(V 0+V1+V2), because of its intricate inner structure, does not. In particular, it is shown thatL(V 0+V1+V2) contains as a sublattice the ideal lattice of a free lattice with free generators. Each of the quasivarietiesV 0,V 1, andV 2 is generated by a 2-element algebra inD 2. (shrink)
Let A be an algebra. We say that the functions f 1 , . . . , f m : A n → A are algebraic on A provided there is a finite system of term-equalities $${{\bigwedge t_{k}(\overline{x}, \overline{z}) = s_{k}(\overline{x}, \overline{z})}}$$ satisfying that for each $${{\overline{a} \in A^{n}}}$$, the m -tuple $${{(f_{1}(\overline{a}), \ldots , f_{m}(\overline{a}))}}$$ is the unique solution in A m to the system $${{\bigwedge t_{k}(\overline{a}, \overline{z}) = s_{k}(\overline{a}, \overline{z})}}$$. In this work we present a collection of general (...) tools for the study of algebraic functions, and apply them to obtain characterizations for algebraic functions on distributive lattices, Stone algebras, finite abelian groups and vector spaces, among other well known algebraic structures. (shrink)
The aim of this paper is to apply properties of the double dual endofunctor on the category of bounded distributive lattices and some extensions thereof to obtain completeness of certain non-classical propositional logics in a unified way. In particular, we obtain completeness theorems for Moisil calculus, n-valued Łukasiewicz calculus and Nelson calculus. Furthermore we show some conservativeness results by these methods.
We give topological proofs of Görnemann’s adaptation to Heyting algebras of the Rasiowa-Sikorski Lemma for Boolean algebras; and of the Rauszer-Sabalski generalisation of it to distributive lattices. The arguments use the Priestley topology on the set of prime filters, and the Baire category theorem. This is preceded by a discussion of criteria for compactness of various spaces of subsets of a lattice, including spaces of filters, prime filters etc.
The main aim of the present paper is to explain a nature of relationships exist between Nelson and Heyting algebras. In the realization, a topological duality theory of Heyting and Nelson algebras based on the topological duality theory of Priestley ([15], [16]) for bounded distributive lattices are applied. The general method of construction of spaces dual to Nelson algebras from a given dual space to Heyting algebra is described (Thm 2.3). The algebraic counterpart of this construction (...) being a generalization of the Fidel-Vakarelov construction ([6], [25]) is also given (Thm 3.6). These results are applied to compare the equational category N of Nelson algebras and some its subcategories (and their duals) with the equational category H of Heyting algebras (and its dual). It is proved (Thm 4.1) that the category N is topological over the category H. (shrink)
The main result of this paper is the following theorem: a closure space X has an , , Q-regular base of the power iff X is Q-embeddable in It is a generalization of the following theorems:(i) Stone representation theorem for distributive lattices ( = 0, = , Q = ), (ii) universality of the Alexandroff's cube for T 0-topological spaces ( = , = , Q = 0), (iii) universality of the closure space of filters in the lattice of (...) all subsets for , -closure spaces (Q = 0). By this theorem we obtain some characterizations of the closure space given by the consequence operator for the classical propositional calculus over a formalized language of the zero order with the set of propositional variables of the power . In particular we prove that a countable closure space X is embeddable with finite disjunctions preserved into F iff X is a consistent closure space satisfying the compactness theorem and X contains a 0, -base consisting of -prime sets. (shrink)
Two constructions for adding an involution operator to residuated ordered monoids are investigated. One preserves integrality and the mingle axiom x 2x but fails to preserve the contraction property xx 2. The other has the opposite preservation properties. Both constructions preserve commutativity as well as existent nonempty meets and joins and self-dual order properties. Used in conjunction with either construction, a result of R.T. Brady can be seen to show that the equational theory of commutative distributive residuated lattices (without (...) involution) is decidable, settling a question implicitly posed by P. Jipsen and C. Tsinakis. The corresponding logical result is the (theorem-) decidability of the negation-free axioms and rules of the logic RW, formulated with fusion and the Ackermann constant t. This completes a result of S. Giambrone whose proof relied on the absence of t. (shrink)
We prove that there are two involutions defined by monadic terms that characterize Monadic Algebras. We further prove that the variety of Monadic Algebras is the smallest variety of Interior Algebras where these involutions give rise to an interpretation from the variety of Bounded Distributive Lattices into it.
The paper describes the isomorphic lattices of quasivarieties of commutative quasigroup modes and of cancellative commutative binary modes. Each quasivariety is characterised by providing a quasi-equational basis. A structural description is also given. Both lattices are uncountable and distributive.
We characterize the model companions of universal Horn classes generated by a two-element algebra (or ordered two-element algebra). We begin by proving that given two mutually model consistent classes M and N of L (respectively L') structures, with $\mathscr{L} \subseteq \mathscr{L}'$ , M ec = N ec ∣ L , provided that an L-definability condition for the function and relation symbols of L' holds. We use this, together with Post's characterization of ISP(A), where A is a two-element algebra, to show (...) that the model companions of these classes essentially lie in the classes of posets and semilattices, or characteristic two groups and relatively complemented distributive lattices. (shrink)
This paper illustrates how Priestley duality can be used in the transfer of an optimal natural duality from a minimal generating algebra for a quasi-variety to other generating algebras. Detailed calculations are given for the quasi-variety of Kleene algebras and the quasi-varieties n of pseudocomplemented distributive lattices (n 1).
Let be a finite collection of finite algebras of finite signature such that SP( ) has meet semi-distributive congruence lattices. We prove that there exists a finite collection 1 of finite algebras of the same signature, , such that SP( 1) is finitely axiomatizable.We show also that if , then SP( 1) is finitely axiomatizable. We offer new proofs of two important finite basis theorems of D. Pigozzi and R. Willard. Our actual results are somewhat more general than this (...) abstract indicates. (shrink)
A biresiduation algebra is a 〈/,\,1〉-subreduct of an integral residuated lattice. These algebras arise as algebraic models of the implicational fragment of the Full Lambek Calculus with weakening. We axiomatize the quasi-variety B of biresiduation algebras using a construction for integral residuated lattices. We define a filter of a biresiduation algebra and show that the lattice of filters is isomorphic to the lattice of B-congruences and that these lattices are distributive. We give a finite basis of terms for generating (...) filters and use this to characterize the subvarieties of B with EDPC and also the discriminator varieties. A variety generated by a finite biresiduation algebra is shown to be a subvariety of B. The lattice of subvarieties of B is investigated; we show that there are precisely three finitely generated covers of the atom. (shrink)
We provide tools for a concise axiomatization of a broad class of quantifiers in many-valued logic, so-called distribution quantifiers. Although sound and complete axiomatizations for such quantifiers exist, their size renders them virtually useless for practical purposes. We show that for quantifiers based on finite distributive lattices compact axiomatizations can be obtained schematically. This is achieved by providing a link between skolemized signed formulas and filters/ideals in Boolean set lattices. Then lattice theoretic tools such as Birkhoff's representation theorem for (...) finite distributive lattices are used to derive tableau-style axiomatizations of distribution quantifiers. (shrink)
In the paper we present completeness theorems for hybrid logics, discuss the problem of finite axiomatization and study term rewriting and unification for the variety of distributive lattices and the variety of groups of exponent 2.
A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We (...) focus on the countable distributive lattices P w and P s of weak and strong degrees of mass problems given by nonempty Π 1 0 subsets of 2 ω . Using an abstract Gödel/Rosser incompleteness property, we characterize the Π 1 0 subsets of 2 ω whose associated mass problems are of top degree in P w and P s , respectively. Let R be the set of Turing oracles which are random in the sense of Martin-Löf, and let r be the weak degree of R. We show that r is a natural intermediate degree within P w . Namely, we characterize r as the unique largest weak degree of a Π 1 0 subset of 2 ω of positive measure. Within P w we show that r is meet irreducible, does not join to 1, and is incomparable with all weak degrees of nonempty thin perfect Π 1 0 subsets of 2 ω . In addition, we present other natural examples of intermediate degrees in P w . We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory. (shrink)
Two-dimensional coupled map lattices display, in a specific parameter range, a stable phase (quasi-) periodic in both space and time. With small changes to the model parameters, this stable phase develops spontaneous eruptions of nonperiodic behavior. Although this behavior itself appears irregular, it can be characterized in a systematic fashion. In particular, parameter-independent features of the spontaneous eruptions may allow useful empirical characterizations of other phenomena that are intrinsically hard to predict and reproduce. Specific features of the distributions of lifetimes (...) and emergence rates of irregular states display such parameter-independent properties. Ó 2004 Elsevier Ltd. All rights reserved. (shrink)
In this paper we examine interactions of the reciprocal with distributive and collective operators, which are encoded by prefixes on verbs expressing the reciprocal relation: namely, the Czech distributive po and the collectivizing na-. The theoretical import of this study is two-fold. First, it contributes to our knowledge of how word-internal operators interact with phrasal syntax/semantics. Second, the prefixes po and na generate (a range of) readings of reciprocal sentences for which the Strongest Meaning Hypothesis (SMH) proposed by (...) Dalrymple et al. (1998) does not make the right predictions. The distributive prefix po prefers the Strong Reciprocity reading, although the SMH predicts that a weakening should take place, while with the prefix na we find cases where weaker reciprocal readings are preferable to the stronger ones predicted by the SMH. This behavior of po and na is, we propose, due to the way in which they modulate two factors that are crucial in the interpretation of reciprocal sentences: (i) the relevant subpluralities in the group denoted by the reciprocal's antecedent, and (ii) the strength of reciprocal relations. We provide a detailed analysis of the semantics of the prefixes po and na and their contribution to the meaning of reciprocal sentences within the general framework of event semantics with lattice structures. (shrink)
It has been recently shown [4] that the lattice effect algebras can be treated as a subvariety of the variety of so-called basic algebras. The open problem whether all subdirectly irreducible distributive lattice effect algebras are just subdirectly irreducible MV-chains and the horizontal sum of two 3-element chains is in the paper transferred into a more tractable one. We prove that modulo distributive lattice effect algebras, the variety generated by MV-algebras and is definable by three simple identities and (...) the problem now is to check if these identities are satisfied by all distributive lattice effect algebras or not. (shrink)
The present paper is thought as a formal study of distributive closure systems which arise in the domain of sentential logics. Special stress is laid on the notion of a C-filter, playing the role analogous to that of a congruence in universal algebra. A sentential logic C is called filter distributive if the lattice of C-filters in every algebra similar to the language of C is distributive. Theorem IV.2 in Section IV gives a method of axiomatization of (...) those filter distributive logics for which the class Matr (C) prime of C-prime matrices (models) is axiomatizable. In Section V, the attention is focused on axiomatic strengthenings of filter distributive logics. The theorems placed there may be regarded, to some extent, as the matrix counterparts of Baker's well-known theorem from universal algebra [9, § 62, Theorem 2]. (shrink)
We study ranges of algebraic functions in lattices and in algebras, such as Łukasiewicz-Moisil algebras which are obtained by extending standard lattice signatures with unary operations.We characterize algebraic functions in such lattices having intervals as their ranges and we show that in Artinian or Noetherian lattices the requirement that every algebraic function has an interval as its range implies the distributivity of the lattice.
This paper discusses Crawley completions of residuated lattices. While MacNeille completions have been studied recently in relation to logic, Crawley completions (i.e. complete ideal completions), which are another kind of regular completions, have not been discussed much in this relation while many important algebraic works on Crawley completions had been done until the end of the 70’s. In this paper, basic algebraic properties of ideal completions and Crawley completions of residuated lattices are studied first in their conncetion with the join (...) infinite distributivity and Heyting implication. Then some results on algebraic completeness and conservativity of Heyting implication in substructural predicate logics are obtained as their consequences. (shrink)
We consider various classes of algebras obtained by expanding idempotent semirings with meet, residuals and Kleene-*. An investigation of congruence properties (e-permutability, e-regularity, congruence distributivity) is followed by a section on algebraic Gentzen systems for proving inequalities in idempotent semirings, in residuated lattices, and in (residuated) Kleene lattices (with cut). Finally we define (one-sorted) residuated Kleene lattices with tests to complement two-sorted Kleene algebras with tests.
We show that in the lattice E Π of Π 0 1 classes there are initial segments [ $\emptyset$ , P] = L(P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a Π 0 1 class P such that L is isomorphic to the lattice L(P)*, which is L(P), modulo finite differences. For the 2-element lattice, we (...) obtain a minimal class, first constructed by Cenzer, Downey, Jockusch and Shore in 1993. For the simplest new Π 0 1 class P constructed, P has a single, non-computable limit point and L(P)* has three elements, corresponding to $\emptyset$ , P and a minimal class P $_0 \subset$ P. The element corresponding to P 0 has no complement in the lattice. On the other hand, the theory of L(P) is shown to be decidable. A Π 0 1 class P is said to be decidable if it is the set of paths through a computable tree with no dead ends. We show that if P is decidable and has only finitely many limit points, then L(P)* is always a Boolean algebra. We show that if P is a decidable Π 0 1 class and L(P) is not a Boolean algebra, then the theory of L(P)interprets the theory of arithmetic and is therefore undecidable. (shrink)
We study the variety Var() of lattice-ordered monoids generated by the natural numbers. In particular, we show that it contains all 2-generated positively ordered lattice-ordered monoids satisfying appropriate distributive laws. Moreover, we establish that the cancellative totally ordered members of Var() are submonoids of ultrapowers of and can be embedded into ordered fields. In addition, the structure of ultrapowers relevant to the finitely generated case is analyzed. Finally, we provide a complete isomorphy invariant in the two-generated case.
In this paper we develop a reconstruction of the Tractatus ontology. The basic idea is that objects are unsaturated and that Sachlagen are like molecules. Bisimulation is used for the proper individuation of the Sachlagen. We show that the ordering of the Sachlagen is a complete distributive, lattice. It is atomistic , i.e., each Sachlage is the supremum of the Sachverhalte below it. We exhibit three normal forms for Sachlagen: the bisimulation collapse, the canonical unraveling and the canonical bisimulation (...) collapse. The first of these forms is unique modulo isomorphism, the second and third are simply unique. The subset ordering on normal forms of the second and third kind reflects the ordering of the Sachlagen. (shrink)
This paper aims at formulating a condition neccssary and sufficient for the existing of a prime filter preserving enumerable infinite joins and meets in a distributive lattice.
In [3] John S. Bell proposed how to associate particle trajectories with a lattice quantum field theory, yielding what can be regarded as a |Ψ|2-distributed Markov process on the appropriate configuration space. A similar process can be defined in the continuum, for more or less any regularized quantum field theory; such processes we call Bell-type quantum field theories. We describe methods for explicitly constructing these processes. These concern, in addition to the definition of the Markov processes, the efficient calculation of (...) jump rates, how to obtain the process from the processes corresponding to the free and interaction Hamiltonian alone, and how to obtain the free process from the free Hamiltonian or, alternatively, from the one-particle process by a construction analogous to “second quantization.” As an example, we consider the process for a second quantized Dirac field in an external electromagnetic field. (shrink)
The notation and terminology of this paper follow [2], and are dual to those of [6] and [7]. If L is a language in the narrow sense, Cn may be any consequence operation on sets of sentences of L that includes classical sentential logic. Henceforth when we talk of the language L we intend to include reference to some fixed, though unspecified, operation Cn. X is a deductive system if X = Cn(X). Sentences x, z that are logically equivalent with (...) respect to Cn – that is x ∈ Cn({z}) and z ∈ Cn({x}) – are identified. If X and Z are systems we often write X x instead of x ∈ X and Z X instead of X ⊆ Z. If X = Cn({x}) for some sentence x, X is (finitely) axiomatizable. The set theoretical intersection of X and Z has the logical force of disjunction, and is written X ∨ Z; Cn(X ∪ Z), the smallest system to include both X and Z, is written XZ. If K is a family of systems, [K] and [K] may be defined in an analogous way. The logically strongest system S is the set of all sentences of L; the weakest system T is defined as Cn(∅). The autocomplement Z of Z is defined to be the strongest system to complement T, namely the system [{Y : Y ∨ Z = T}]. More generally we may define X − Z as [{Y : X Y ∨ Z}]. In terms of this operation to remainder, Z is identical with T − Z. The class of all deductive systems forms a distributive lattice under the operations of concatenation and ∨; and indeed a Brouverian algebra (a relatively authocomplemented lattice with unit) under concatenation, ∨ – and T. (shrink)
The notation and terminology of this paper follow [2], and are dual to those of [6] and [7]. If L is a language in the narrow sense, Cn may be any consequence operation on sets of sentences of L that includes classical sentential logic. Henceforth when we talk of the language L we intend to include reference to some fixed, though unspecified, operation Cn. X is a deductive system if X = Cn(X). Sentences x, z that are logically equivalent with (...) respect to Cn – that is x ∈ Cn({z}) and z ∈ Cn({x}) – are identified. If X and Z are systems we often write X x instead of x ∈ X and Z X instead of X ⊆ Z. If X = Cn({x}) for some sentence x, X is (finitely) axiomatizable. The set theoretical intersection of X and Z has the logical force of disjunction, and is written X ∨ Z; Cn(X ∪ Z), the smallest system to include both X and Z, is written XZ. If K is a family of systems, [K] and [K] may be defined in an analogous way. The logically strongest system S is the set of all sentences of L; the weakest system T is defined as Cn(∅). The autocomplement Z of Z is defined to be the strongest system to complement T, namely the system [{Y : Y ∨ Z = T}]. More generally we may define X − Z as [{Y : X Y ∨ Z}]. In terms of this operation to remainder, Z is identical with T − Z. The class of all deductive systems forms a distributive lattice under the operations of concatenation and ∨; and indeed a Brouverian algebra (a relatively authocomplemented lattice with unit) under concatenation, ∨ – and T. (shrink)
This paper is a study of duality in the absence of canonicity. Specifically it concerns double quasioperator algebras, a class of distributive lattice expansions in which, coordinatewise, each operation either preserves both join and meet or reverses them. A variety of DQAs need not be canonical, but as has been shown in a companion paper, it is canonical in a generalized sense and an algebraic correspondence theorem is available. For very many varieties, canonicity (as traditionally defined) and correspondence lead (...) on to topological dualities in which the topological and correspondence components are quite separate. It is shown that, for DQAs, generalized canonicity is sufficient to yield, in a uniform way, topological dualities in the same style as those for canonical varieties. However topology and correspondence are no longer separable in the same way. (shrink)
A decade ago, Isham and Butterfield proposed a topos theoretic approach to quantum mechanics, which meanwhile has been extended by Doering and Isham so as to provide a new mathematical foundation for all of physics. Last year, three of the present authors redeveloped and refined these ideas by combining the C*-algebraic approach to quantum theory with the so-called internal language of topos theory (see arXiv:0709.4364). The goal of the present paper is to illustrate our abstract setup through the concrete example (...) of the C*-algebra M_n(C) of complex n x n matrices. This leads to an explicit expression for the pointfree quantum phase space and the associated logical structure and Gelfand transform of an n-level system. We also determine the pertinent non-probabilisitic state-proposition pairing (or valuation) and give a very natural topos-theoretic reformulation of the Kochen-Specker Theorem. In our approach, the nondistributive lattice P(M_n(C)) of projections in M_n(C)(which forms the basis of the traditional quantum logic of Birkhoff and von Neumann)is replaced by a specific distributive lattice of functions from the poset of all unital commutative C*-subalgebras of M_n(C) to P(M_n(C)). The latter lattice is essentially the (pointfree) topology of the quantum phase space mentioned above, and as such defines a Heyting algebra. Each element of the lattice corresponds to a ``Bohrified'' proposition, in the sense that to each classical context it associates a yes-no question pertinent to this context, rather than being a single projection as in standard quantum logic. Distributivity is recovered at the expense of the law of the excluded middle (Tertium Non Datur), whose demise is in our opinion to be welcomed, not just in intuitionistic logic in the spirit of Brouwer, but also in quantum logic in the spirit of von Neumann. (shrink)
relative to the actual world) of a propositional theory are defined. A theory is ‘closer to the truth’ the logically stronger its positive content and the logically weaker its negative content. This proposal delivers the same verisimilar preordering of theories that has been defined by Brink and Heidema as a ‘power ordering’. The preordering may be collapsed to a partial ordering and then embedded into a complete distributive lattice. The preordering may also be refined to a partial ordering by (...) employing the ‘convex content’ and the ‘non-convex content’ of each theory. Philosophical implications and historical relations are discussed. (shrink)
Let $\langle\mathscr{T},\leq\rangle$ be the usual structure of the degrees of unsolvability and $\langle\mathscr{D},\leq\rangle$ the structure of the T-degrees of partial functions defined in [7]. We prove that every countable distributive lattice with a least element can be isomorphically embedded as an initial segment of $\langle\mathscr{D},\leq\rangle$ : as a corollary, the first order theory of $\langle\mathscr{D},\leq\rangle$ is recursively isomorphic to that of $\langle\mathscr{T},\leq\rangle$ . We also show that $\langle\mathscr{D},\leq\rangle$ and $\langle\mathscr{T},\leq\rangle$ are not elementarily equivalent.
This paper is closely related to investigations of abstract properties of basic logical notions expressible in terms of closure spaces as they were begun by A. Tarski (see [6]). We shall prove many properties of -conjunctive closure spaces (X is -conjunctive provided that for every two elements of X their conjunction in X exists). For example we prove the following theorems:1. For every closed and proper subset of an -conjunctive closure space its interior is empty (i.e. it is a boundary (...) set). 2. If X is an -conjunctive closure space which satisfies the -compactness theorem and [X] is a meet-distributive semilattice (see [3]), then the lattice of all closed subsets in X is a Heyting lattice. 3. A closure space is linear iff it is an -conjunctive and topological space. 4. Every continuous function preserves all conjunctions. (shrink)
The totality of extensional 1-ary connectives distinguishable in a logical framework allowing sequents with multiple or empty (alongside singleton) succedents form a lattice under a natural partial ordering relating one connective to another if all the inferential properties of the former are possessed by the latter. Here we give a complete description of that lattice; its Hasse diagram appears as Figure 1 in §2. Simple syntactic descriptions of the lattice elements are provided in §3; §§4 and 5 give some additional (...) remarks on matrix methods and on alternative terminology. Background: The size of this lattice was underestimated in [3]; some missing cases were noted in [4] in the course of correcting an example from [3] purporting to show the non-distributivity of the lattice. All the missing cases (as well as those originally noted) are covered here. (The present discussion is self-contained.). (shrink)
Within the context of an involutive monoidal category the notion of a comparison relation ${\textsf{cp} : \overline{X} \otimes X \rightarrow \Omega}$ is identified. Instances are equality = on sets, inequality ${\leq}$ on posets, orthogonality ${\perp}$ on orthomodular lattices, non-empty intersection on powersets, and inner product ${\langle {-}|{-} \rangle}$ on vector or Hilbert spaces. Associated with a collection of such (symmetric) comparison relations a dagger category is defined with “tame” relations as morphisms. Examples include familiar categories in the foundations of quantum (...) mechanics, such as sets with partial injections, or with locally bifinite relations, or with formal distributions between them, or Hilbert spaces with bounded (continuous) linear maps. Of one particular example of such a dagger category of tame relations, involving sets and bifinite multirelations between them, the categorical structure is investigated in some detail. It turns out to involve symmetric monoidal dagger structure, with biproducts, and dagger kernels. This category may form an appropriate universe for discrete quantum computations, just like Hilbert spaces form a universe for continuous computation. (shrink)
The notion of a pseudo-interior algebra was introduced by Blok and Pigozzi in [BPIV]. We continue here our studies begun in [BK]. As a consequence of the representation theorem for pseudo-interior algebras given in [BK] we prove that the variety of all pseudo-interior algebras is generated by its finite members. This result together with Jónsson's Theorem for congruence distributive varieties provides a useful technique in the study of the lattice of varieties of pseudo-interior algebras.
No theory of a partially ordered set of finite width has the independence property, generalizing Poizat's corresponding result for linearly ordered sets. In fact, a question of Poizat concerning linearly ordered sets is answered by showing, moreover, that no theory of a partially ordered set of finite width has the multi-order property. It then follows that a distributive lattice is not finite-dimensional $\operatorname{iff}$ its theory has the independence property $\operatorname{iff}$ its theory has the multi-order property.
Craig's interpolation theorem fails for the prepositional logicsE of entailment,R of relevant implication andT of ticket entailment, as well as in a large class of related logics. This result is proved by a geometrical construction, using the fact that a non-Arguesian projective plane cannot be imbedded in a three-dimensional projective space. The same construction shows failure of the amalgamation property in many varieties of distributive lattice-ordered monoids.
The least element 0 of a finite meet semi-distributive lattice is a meet of meet-prime elements. We investigate conditions under which the least element of an algebraic, meet semi-distributive lattice is a (complete) meet of meet-prime elements. For example, this is true if the lattice has only countably many compact elements, or if |L| < 2ℵ0, or if L is in the variety generated by a finite meet semi-distributive lattice. We give an example of an algebraic, meet (...) semi-distributive lattice that has no meet-prime element or join-prime element. This lattice L has |L| = |LC| = 2ℵ0 where Lc is the set of compact elements of L. (shrink)
In this paper we define and study conditional problems and their degrees. The main result is that the class of conditional degrees is a lattice extending the ordinary Turing degrees and it is dense. These properties are not shared by ordinary Turing degrees. We show that the class of conditional many-one degrees is a distributive lattice. We also consider properties of semidecidable problems and their degrees, which are analogous to r.e. sets and degrees.
Let FΛ be a finite dimensional path algebra of a quiver Λ over a field F. Let L and R denote the varieties of all left and right FΛ-modules respectively. We prove the equivalence of the following statements. • The subvariety lattice of L is a sublattice of the subquasivariety lattice of L. • The subquasivariety lattice of R is distributive. • Λ is an ordered forest.
We introduce a new operator – belief fusion– which aggregates the beliefs of two agents, each informed by a subset of sources ranked by reliability. In the process we definepedigreed belief states, which enrich standard belief states with the source of each piece of information. We note that the fusion operator satisfies the invariants of idempotence, associativity, and commutativity. As a result, it can be iterated without difficulty. We also define belief diffusion; whereas fusion generally produces a belief state with (...) more information than is possessed by either of its two arguments, diffusion produces a state with less information. Fusion and diffusion are symmetric operators, and together define a distributive lattice. Finally, we show that AGM revision can be viewed as fusion between a novice and an expert. (shrink)
We introduce a new operator â belief fusionâ which aggregates the beliefs of two agents, each informed by a subset of sources ranked by reliability. In the process we definepedigreed belief states, which enrich standard belief states with the source of each piece of information. We note that the fusion operator satisfies the invariants of idempotence, associativity, and commutativity. As a result, it can be iterated without difficulty. We also define belief diffusion; whereas fusion generally produces a belief state with (...) more information than is possessed by either of its two arguments, diffusion produces a state with less information. Fusion and diffusion are symmetric operators, and together define a distributive lattice. Finally, we show that AGM revision can be viewed as fusion between a novice and an expert. (shrink)
