The starting point of the present study is the interpretation of intuitionistic linear logic in Petri nets proposed by U. Engberg and G. Winskel. We show that several categories of order algebras provide equivalent interpretations of this logic, and identify the category of the so called strongly coherent quantales arising in these interpretations. The equivalence of the interpretations is intimately related to the categorical facts that the aforementioned categories are connected with each other via adjunctions, and the compositions of (...) the connecting functors with co-domain the category of strongly coherent quantales are dense. In particular, each quantale canonically induces a Petri net, and this association gives rise to an adjunction between the category of quantales and a category whose objects are all Petri nets. (shrink)

It is well known that there is a correspondence between sets and complete, atomic Boolean algebras (\(\textit{CABA}\)s) taking a set to its power-set and, conversely, a complete, atomic Boolean algebra to its set of atomic elements. Of course, such a correspondence induces an equivalence between the opposite category of \(\textbf{Set}\) and the category of \(\textit{CABA}\)s. We modify this result by taking multialgebras over a signature \(\Sigma\), specifically those whose non-deterministic operations cannot return the empty-set, to \(\textit{CABA}\)s with their zero (...) element removed (which we call a \(\textit{bottomless Boolean algebra}\)) equipped with a structure of \(\Sigma\)-algebra compatible with its order (that we call \(\textit{ord-algebras}\)). Conversely, an ord-algebra over \(\Sigma\) is taken to its set of atomic elements equipped with a structure of multialgebra over \(\Sigma\). This leads to an equivalence between the category of \(\Sigma\)-multialgebras and the category of ord-algebras over \(\Sigma\). The intuition, here, is that if one wishes to do so, non-determinism may be replaced by a sufficiently rich ordering of the underlying structures. (shrink)

We present a systematic study of join-extensions and join-completions of partially ordered algebras, which naturally leads to a refined and simplified treatment of fundamental results and constructions in the theory of ordered structures ranging from properties of the Dedekind–MacNeille completion to the proof of the finite embeddability property for a number of varieties of lattice-ordered algebras.

Part I of this paper is developed in the tradition of Stone-type dualities, where we present a new topological representation for general lattices (influenced by and abstracting over both Goldblatt's [17] and Urquhart's [46]), identifying them as the lattices of stable compact-opens of their dual Stone spaces (stability refering to a closure operator on subsets). The representation is functorial and is extended to a full duality.In part II, we consider lattice-ordered algebras (lattices with additional operators), extending the Jónsson (...) and Tarski representation results [30] for Boolean algebras with Operators. Our work can be seen as developing, and indeed completing, Dunn's project of gaggle theory [13, 14]. We consider general lattices (rather than Boolean algebras), with a broad class of operators, which we dubb normal, and which includes the Jónsson-Tarski additive operators. Representation of l-algebras is extended to full duality. (shrink)

In this paper, constructions of free ordered algebras on one generator are given that correspond to some one-variable fragments of affine propositional classical logic and their extensions with n-contraction (n ≥ 2). Moreover, embeddings of the already known infinite free structures into the algebras introduced below are furnished with; thus, solving along the respective cardinality problems.

We review some of the essential novel ideas introduced by Bohm through the implicate order and indicate how they can be given mathematical expression in terms of an algebra. We also show how some of the features that are needed in the implicate order were anticipated in the work of Grassmann, Hamilton, and Clifford. By developing these ideas further we are able to show how the spinor itself, when viewed as a geometric object within a geometric algebra, can be given (...) a meaning which transcends the notion of the usual metric geometry in the sense that it must be regarded as an element of a broader and more general pregeometry. (shrink)

We propose various methods for combining or amalgamating propositional languages and deductive systems. We make heavy use of quantales and quantale modules in the wake of previous works by the present and other authors. We also describe quite extensively the relationships among the algebraic and order-theoretic constructions and the corresponding ones based on a purely logical approach.

Internal sets and the Boolean algebras of the collection of the internal sets are of central importance in non-standard analysis. Boolean algebras are the algebraization of propositional logic while the logic applied in non-standard analysis (in non-standard stochastics) is the first order or the higher order logic (type theory). We present here a first order logic algebraization for the collection of internal sets rather than the Boolean one. Further, we define an unusual probability on this algebraization.

First order formulas in a relational signature can be considered as operations on the relations of an underlying set, giving rise to multisorted algebras we call first order algebras. We present universal axioms so that an algebra satisfies the axioms iff it embeds into a first order algebra. Importantly, our argument is modular and also works for, e.g., the positive existential algebras and the quantifier-free algebras. We also explain the relationship to theories, and indicate how to (...) add in function symbols. (shrink)

It is shown that the Boolean center of complemented elements in a bounded integral residuated lattice characterizes direct decompositions. Generalizing both Boolean products and poset sums of residuated lattices, the concepts of poset product, Priestley product and Esakia product of algebras are defined and used to prove decomposition theorems for various ordered algebras. In particular, we show that FLw-algebras decompose as a poset product over any finite set of join irreducible strongly central elements, and that bounded (...) n-potent GBL-algebras are represented as Esakia products of simple n-potent MV-algebras. (shrink)

An algebraization of multi-signature first-order logic without terms is presented. Rather than following the traditional method of choosing a type of algebras and constructing an appropriate variety, as is done in the case of cylindric and polyadic algebras, a new categorical algebraization method is used: The substitutions of formulas of one signature for relation symbols in another are treated in the object language. This enables the automatic generation via an adjunction of an algebraic theory. The algebras of (...) this theory are then used to algebraize first-order logic. (shrink)

Using a variation of the rainbow construction and various pebble and colouring games, we prove that RRA, the class of all representable relation algebras, cannot be axiomatised by any first-order relation algebra theory of bounded quantifier depth. We also prove that the class At(RRA) of atom structures of representable, atomic relation algebras cannot be defined by any set of sentences in the language of RA atom structures that uses only a finite number of variables.

We show that the variety of n -dimensional weakly higher order cylindric algebras, introduced in Németi [9], [8], is finitely axiomatizable when n > 2. Our result implies that in certain non-well-founded set theories the finitization problem of algebraic logic admits a positive solution; and it shows that this variety is a good candidate for being the cylindric algebra theoretic counterpart of Tarski’s quasi-projective relation algebras.

Demonic composition, demonic refinement and demonic union are alternatives to the usual ‘angelic’ composition, angelic refinement (inclusion) and angelic (usual) union defined on binary relations. We first motivate both the angelic and the demonic via an analysis of the behaviour of non-deterministic programs, with the angelic associated with partial correctness and demonic with total correctness, both cases emerging from a richer algebraic model of non-deterministic programs incorporating both aspects. Zareckiĭ has shown that the isomorphism class of algebras of binary (...) relations under angelic composition and inclusion is finitely axiomatized as the class of ordered semigroups. The proof can be used to establish that the same axiomatization applies to binary relations under demonic composition and refinement, and a further modification of the proof can be used to incorporate a zero element representing the empty relation in the angelic case and the full relation in the demonic case. For the signature of angelic composition and union, it is known that no finite axiomatization exists, and we show the analogous result for demonic composition and demonic union by showing that the same axiomatization holds for both. We show that the isomorphism class of algebras of binary relations with the ‘mixed’ signature of demonic composition and angelic inclusion has no finite axiomatization. As a contrast, we show that the isomorphism class of partial algebras of binary relations with the partial operation of constellation product and inclusion (also a ‘mixed’ signature) is finitely axiomatizable. (shrink)

Based on the paper [4] we show that true second‐order arithmetic is interpretable over the real‐algebraic structure of models of intuitionistic analysis built upon a certain class of complete Heyting algebras.

Lawvere hyperdoctrines give categorical algebraic semantics for intuitionistic predicate logic. Here we extend the hyperdoctrinal semantics to a broad variety of substructural predicate logics over the Typed Full Lambek Calculus, verifying their completeness with respect to the extended hyperdoctrinal semantics. This yields uniform hyperdoctrinal completeness results for numerous logics such as different types of relevant predicate logics and beyond, which are new results on their own; i.e., we give uniform categorical semantics for a broad variety of non-classical predicate logics. And (...) we introduce an analogue of Lawvere–Tierney topology and cotopology in the hyperdoctrinal setting, which gives a unifying perspective on different logical translations, in particular allowing for a uniform treatment of Girard’s exponential translation between linear and intuitionistic logics and of Kolmogorov’s double negation translation between intuitionistic and classical logics. In the hyerdoctrinal conception, type theories are categories, logics over type theories are functors, and logical translations between them, then, are natural transformations, in particular Lawvere–Tierney topologies and cotopologies on hyperdoctrines. The view of logical translations as hyperdoctrinal Lawvere–Tierney topologies and cotopologies has not been elucidated before, and may be seen as a novel contribution of the present work. From a broader perspective, this work may be regarded as taking first steps towards interplay between algebraic and categorical logics; it is, technically, a combination of substructural algebraic logic and hyperdoctrinal categorical logic, as the hyperdoctrinal completeness theorem is shown via the integration of the Lindenbaum–Tarski algebra construction with the syntactic category construction. As such this work lays a foundation for further interactions between algebraic and categorical logics. (shrink)

We consider the problem of constructing first-order definitions in the language of rings of holomorphy rings of one-variable function fields of characteristic 0 in their integral closures in finite extensions of their fraction fields and in bigger holomorphy subrings of their fraction fields. This line of questions is motivated by similar existential definability results over global fields and related questions of Diophantine decidability.

Hindman’s theorem says that every finite coloring of the natural numbers has a monochromatic set of finite sums. A Ramsey algebra is a structure that satisfies an analogue of Hindman’s theorem. In this paper, we present the basic notions of Ramsey algebras by using terminology from mathematical logic. We also present some results regarding classification of Ramsey algebras.

For every sequence |p n } n of formulas of Peano ArithmeticPA with, every formulaA of the first-order theory diagonalizable algebras, we associate a formula 0 A, called the value ofA inPA with respect to the interpretation. We show that, ifA is true in every diagonalizable algebra, then, for every, 0 A is a theorem ofPA.

It has been proposed that the implicate order can be given mathematical expression in terms of an algebra and that this algebra is similar to that used in quantum theory. In this paper we bring out in a simple way those aspects of the algebraic formulation of quantum theory that are most relevant to the implicate order. By using the properties of the standard ket introduced by Dirac we describe in detail how the Heisenberg algebra can be generalized to produce (...) an algebraic structure in which it is possible to describe space translations in a way that is analogous to the description of rotations in a Clifford algebra. This approach opens up the possibility of going beyond the limits of the present quantum formalism and we discuss briefly some of the new implications. (shrink)

We give a construction assigning classes of Boolean algebras to first-order theories; several classes of Boolean algebras considered previously in the literature can be thus obtained. In particular it turns out that the class of semigroup algebras can be defined in this way, in fact by a Horn theory, and it is the largest class of Boolean algebras defined by a Horn theory.

In this paper we study the variety of order Hilbert algebras, which is the equivalent algebraic semantics of the order implicational calculus of Bull.

We establish, generalizing Di Nola and Lettieri’s categorical equivalence, a Morita-equivalence between the theory of lattice-ordered abelian groups and that of perfect MV-algebras. Further, after observing that the two theories are not bi-interpretable in the classical sense, we identify, by considering appropriate topos-theoretic invariants on their common classifying topos, three levels of bi-interpretability holding for particular classes of formulas: irreducible formulas, geometric sentences, and imaginaries. Lastly, by investigating the classifying topos of the theory of perfect MV-algebras, we (...) obtain various results on its syntax and semantics also in relation to the cartesian theory of the variety generated by Chang’s MV-algebra, including a concrete representation for the finitely presentable models of the latter theory as finite products of finitely presentable perfect MV-algebras. Among the results established on the way, we mention a Morita-equivalence between the theory of lattice-ordered abelian groups and that of cancellative lattice-ordered abelian monoids with bottom element. (shrink)

The aim of this paper is to give a new proof for the decidability and finite model property of first-order logic with two variables (without function symbols), using a combinatorial theorem due to Herwig. The results are proved in the framework of polyadic equality set algebras of dimension two (Pse 2 ). The new proof also shows the known results that the universal theory of Pse 2 is decidable and that every finite Pse 2 can be represented on a (...) finite base. Since the class Cs 2 of cylindric set algebras of dimension 2 forms a reduct of Pse 2 , these results extend to Cs 2 as well. (shrink)

Post algebras of order + as a semantic foundation for +-valued predicate calculi were examined in [5]. In this paper Post spaces of order + being a modification of Post spaces of order n2 (cf. Traczyk [8], Dwinger [1], Rasiowa [6]) are introduced and Post fields of order + are defined. A representation theorem for Post algebras of order + as Post fields of sets is proved. Moreover necessary and sufficient conditions for the existence of representations preserving a (...) given set of infinite joins and infinite meets are established and applied to Lindenbaum-Tarski algebras of elementary theories based on +-valued predicate calculi in order to obtain a topological characterization of open theories. (shrink)

A Dedekind Algebra is an ordered pair (B,h) where B is a non-empty set and h is an injective unary function on B. Each Dedekind algebra can be decomposed into a family of disjoint, countable subalgebras called configurations of the Dedekind algebra. There are N0 isomorphism types of configurations. Each Dedekind algebra is associated with a cardinal-valued function on omega called its configuration signature. The configuration signature of a Dedekind algebra counts the number of configurations in the decomposition of (...) the algebra in each isomorphism type.The configuration signature of a Dedekind algebra encodes the structure of that algebra in the sense that two Dedekind algebras are isomorphic iff their configuration signatures are identical. Configuration signatures are used to establish various results in the first-order model theory of Dedekind algebras. These include categoricity results for the first-order theories of Dedekind algebras and existence and uniqueness results for homogeneous, universal and saturated Dedekind algebras. Fundamental to these results is a condition on configuration signatures that is necessary and sufficient for elementary equivalence. (shrink)

A new system of algebraic logic is described. it is closely related to cylindric and polyadic algebras, and is axiomatized by a small number of very simple equations.

Grishin algebras are a generalisation of Boolean algebras that provide algebraic models for classical bilinear logic with two mutually cancelling negation connectives. We show how to build complete Grishin algebras as algebras of certain subsets (“propositions”) of cover systems that use an orthogonality relation to interpret the negations. The variety of Grishin algebras is shown to be closed under MacNeille completion, and this is applied to embed an arbitrary Grishin algebra into the algebra of all (...) propositions of some cover system, by a map that preserves all existing joins and meets. This representation is then used to give a cover system semantics for a version of classical bilinear logic that has first-order quantifiers and infinitary conjunctions and disjunctions. (shrink)

This paper is about partially ordered multisets (pomsets for short). We investigate a particular class of pomsets that we call order-deterministic, properly including all partially ordered sets, which satisfies a number of interesting properties: among other things, it forms a distributive lattice under pomset prefix (hence prefix closed sets of order-deterministic pomsets are prime algebraic), and it constitutes a reflective subcategory of the category of all pomsets. For the order-deterministic pomsets we develop an algebra with a sound and (...) (-) complete equational theory. The operators in the algebra are concatenation and join, the latter being a variation on the more usual disjoint union of pomsets. This theory is then extended in order to capture refinement of pomsets by incorporating homomorphisms between models as objects in the algebra and homomorphism application as a new operator. (shrink)

We prove that the equational theory of a semigroups becomes undecidable if we add a semilattice structure with a ‘touch of symmetric difference’. As a corollary we obtain that the variety of all Boolean algebras with an associative binary operator has a ‘hereditarily’ undecidable equational theory. Our results have implications in logic, e.g. they imply undecidability of modal logics extending the Lambek Calculus and undecidability of Arrow Logics with an associative arrow modality.

There is an extensive literature related to the algebraization of first‐order logic. But the algebraization of full second‐order logic, or Henkin‐type second‐order logic, has hardly been researched. The question arises: what kind of set algebra is the algebraic version of a Henkin‐type model of second‐order logic? The question is investigated within the framework of the theory of cylindric algebras. The answer is: a kind of cylindric‐relativized diagonal restricted set algebra. And the class of the subdirect products of these set (...) algebras is the algebraization of Henkin‐type second‐order logic. It is proved that the algebraization of a complete calculus of the Henkin‐type second‐order logic is a class of a kind of diagonal restricted cylindric algebras. Furthermore, the connection with the non‐standard enlargements of standard complete second‐order structures is investigated. (shrink)

The decision problem for positively quantified formulae in the theory of linearly ordered Heyting algebras is known, as a special case of work of Kreisel, to be solvable; a simple solution is here presented, inspired by related ideas in Gödel-Dummett logic.

This paper is a contribution to Mathematical fuzzy logic, in particular to the algebraic study of t-norm based fuzzy logics. In the general framework of propositional core and Δ-core fuzzy logics we consider three properties of completeness with respect to any semantics of linearly ordered algebras. Useful algebraic characterizations of these completeness properties are obtained and their relations are studied. Moreover, we concentrate on five kinds of distinguished semantics for these logics–namely the class of algebras defined over (...) the real unit interval, the rational unit interval, the hyperreals , the strict hyperreals and finite chains, respectively–and we survey the known completeness methods and results for prominent logics. We also obtain new interesting relations between the real, rational and hyperreal semantics, and good characterizations for the completeness with respect to the semantics of finite chains. Finally, all completeness properties and distinguished semantics are also considered for the first-order versions of the logics where a number of new results are proved. (shrink)

In this paper we pursue the study of the variety of m -generalized Łukasiewicz algebras of order n which was initiated in [1]. This variety contains the variety of Łukasiewicz algebras of order n . Given , we establish an isomorphism from its congruence lattice to the lattice of Stone filters of a certain Łukasiewicz algebra of order n and for each congruence on A we find a description via the corresponding Stone filter. We characterize the principal congruences (...) on A via Stone filters. In doing so, we obtain a polynomial equation which defines the principal congruences on the algebras of . After showing that for m > 1 and n > 2, the variety of Łukasiewicz algebras of order n is a proper subvariety of , we prove that is a finitely generated discriminator variety and point out some consequences of this strong property, one of which is congruence permutability. (shrink)

We characterize Δ20-categoricity in Boolean algebras and linear orderings under some extra effectiveness conditions. We begin with a study of the relativized notion in these structures.