The class DA of diagonalizable algebras enjoys the interpolation property . Using LDA-Gentzen System corresponding to DA, we show that it has the strong amalgamation property as well.

We prove that the diagonalizable algebras of PA and ZF are not isomorphic.

This paper studies the topological duality between diagonalizable algebras and bi-topological spaces. In particular, the correspondence between algebraic properties of a diagonalizable algebra and topological properties of its dual space is investigated. Since the main example of a diagonalizable algebra is the Lindenbaum algebra of an r.e. theory extending Peano Arithmetic, endowed with an operator defined by means of the provability predicate of the theory, this duality gives the possibility to study arithmetical properties of (...) theories from a topological point of view. We find topological characterization of $\Sigma_1$-sound theories and of sentences that are $\Sigma_1$-conservative over such a theory. (shrink)

If a formal theory T is able to reason about its own syntax, then the diagonalizable algebra of T is defined as its Lindenbaum sentence algebra endowed with a unary operator □ which sends a sentence φ to the sentence □φ asserting the provability of φ in T. We prove that the first order theories of diagonalizable algebras of a wide class of theories are undecidable and establish some related results.

Within the technical frame supplied by the algebraic variety of diagonalizable algebras, defined by R. Magari in [2], we prove the following: Let T be any first-order theory with a predicate Pr satisfying the canonical derivability conditions, including Löb's property. Then any formula in T built up from the propositional variables $q,p_{1},...,p_{n}$ , using logical connectives and the predicate Pr, has the same "fixed-points" relative to q (that is, formulas $\psi (p_{1},...,p_{n})$ for which for all $p_{1},...,p_{n}\vdash _{T}\phi (\psi (p_{1},...,p_{n}),p_{1},...,p_{n})\leftrightarrow (...) \psi (p_{1},...,p_{n})$ ) of a formula $\phi ^{\ast}$ of the same kind, obtained from φ in an effective way. Moreover, such $\phi ^{\ast}$ is provably equivalent to the formula obtained from φ substituting with $\phi ^{\ast}$ itself all the occurrences of q which are under Pr. In the particular case where q is always under Pr in φ, $\phi ^{\ast}$ is the unique (up to provable equivalence) "fixed-point" of φ. Since this result is proved only assuming Pr to be canonical, it can be deduced that Löb's property is, in a sense, equivalent to Gödel's diagonalization lemma. All the results are proved more generally in the intuitionistic case. (shrink)

We prove a strengthened version of Shavrukov’s result on the non-isomorphism of diagonalizable algebras of two $\Sigma _1$ -sound theories, based on the improvements previously found by Adamsson. We then obtain several corollaries to the strengthened result by applying it to various pairs of theories and obtain new non-isomorphism examples. In particular, we show that there are no surjective homomorphisms from the algebra $(\mathfrak {L}_T, \Box _T\Box _T)$ onto the algebra $(\mathfrak {L}_T, \Box _T)$. The case of (...) bimodal diagonalizable algebras is also considered. We give several examples of pairs of theories with isomorphic diagonalizable algebras but non-isomorphic bimodal diagonalizable algebras. (shrink)

The duality theory established by Halmos in [2] for boolean hemimorphism applies of course to the diagonalizable algebra, because ντν is an hemimorphism. For commodity in working on diagonalizable algebras we recall the basic facts and give the characteristic conditions on the dual of ντν.

It is well known that, in Peano arithmetic, there exists a formula Theor (x) which numerates the set of theorems. By Gödel's and Löb's results, we have that Theor (˹p˺) ≡ p implies p is a theorem ∼Theor (˹p˺) ≡ p implies p is provably equivalent to Theor (˹0 = 1˺). Therefore, the considered "equations" admit, up to provable equivalence, only one solution. In this paper we prove (Corollary 1) that, in general, if P (x) is an arbitrary formula built (...) from Theor (x), then the fixed-point of P (x) (which exists by the diagonalization lemma) is unique up to provable equivalence. This result is settled referring to the concept of diagonalizable algebra (see Introduction). (shrink)

It is well-known that, in Peano arithmetic, there exists a formula Theor (x) which numerates the set of theorems and that this formula satisfies Hilbert-Bernays derivability conditions. Recently R. Magari has suggested an algebraization of the properties of Theor, introducing the concept of diagonalizable algebra (see [7]): of course this algebraization can be applied to all these theories in which there exists a predicate with analogous properties. In this paper, by means of methods of universal algebra, we (...) study the equational class of diagonalizable algebras, proving, among other things, that the set of identities satisfied by Theor which are consequences of the known ones is decidable. (shrink)

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.

We make use of a Theorem of Burris-McKenzie to prove that the only decidable variety of diagonalizable algebras is that defined by 0=1. Any variety containing an algebra in which 01 is hereditarily undecidable. Moreover, any variety of intuitionistic diagonalizable algebras is undecidable.

The undecidability of the first-order theory of diagonalizable algebras is shown here.

The present work refers directly to the investigations of Buszkowski and Prucnal [1] and that of Esakia [2], generalizing their results. Our main representation theorem for co-diagonalizable algebras is obtained by application of certain methods taken from J´onsson-Tarski [3].

This paper is devoted to the algebraization of theories in which, as in Peano arithmetic, there is a formula, Theor(x), numerating the set of theorems, and satisfying Hilbert-Bernays derivability conditions. In particular, we study the diagonalizable algebras, which are been introduced by R. Magari in [6], [7]. We prove that for every natural number n, the n-freely generated algebra $\germ{J}_{n}$ is not functionally free in the equational class of diagonalizable algebras; we also prove that the diagonalizable (...) algebra of Peano arithmetic is not an element of the equational class generated by $\{\germ{J}_{n}\}$. (shrink)

Let $\scr{T}$ be the first order theory of diagonalizable algebras. We define a bijection φ from the atomic formulas of $\scr{T}$ (identities) to the open formulas of $\scr{T}$ . φ is an algebraic analogous of $\vDash $ . We prove that φ, $\phi ^{-1}$ preserve the validity.

We show the non-arithmeticity of 1st order theories of lattices of Σ n sentences modulo provable equivalence in a formal theory, of diagonalizable algebras of a wider class of arithmetic theories than has been previously known, and of the lattice of degrees of interpretability over PA. The first two results are applications of Nies’ theorem on the non-arithmeticity of the 1st order theory of the lattice of r.e. ideals on any effectively dense r.e. Boolean algebra. The theorem on (...) degrees of interpretability relies on an adaptation of techniques leading to Nies’ theorem. (shrink)

We investigate the modal logic of interpretability over Peano arithmetic. Our main result is a compactness theorem that extends the arithmetical completeness theorem for the interpretability logic ILM ω . This extension concerns recursively enumerable sets of formulas of interpretability logic (rather than single formulas). As corollaries we obtain a uniform arithmetical completeness theorem for the interpretability logic ILM and a partial answer to a question of Orey from 1961. After some simplifications, we also obtain Shavrukov's embedding theorem for Magari (...) algebras (a.k.a. diagonalizable algebras). (shrink)

In Zwicker (1987) the hypergame paradox is introduced and studied. In this paper we continue this investigation, comparing the hypergame argument with the diagonal one, in order to find a proof schema. In particular, in Theorems 9 and 10 we discuss the complexity of the set of founded elements in a recursively enumerable relation on the set N of natural numbers, in the framework of reduction between relations. We also find an application in the theory of diagonalizable algebras and (...) construct an undecidable formula. (shrink)

Orthologic is defined by weakening the axioms and rules of inference of the classical propositional calculus. The resulting Lindenbaum-Tarski quotient algebra is an orthoimplication algebra which generalizes the author's implication algebra. The associated order structure is a semi-orthomodular lattice. The theory of orthomodular lattices is obtained by adjoining a falsity symbol to the underlying orthologic or a least element to the orthoimplication algebra.

We introduce new algebraic and topological semantics for inquisitive logic. The algebraic semantics is based on special Heyting algebras, which we call inquisitive algebras, with propositional valuations ranging over only the ¬¬-fixpoints of the algebra. We show how inquisitive algebras arise from Boolean algebras: for a given Boolean algebra B, we define its inquisitive extension H(B) and prove that H(B) is the unique inquisitive algebra having B as its algebra of ¬¬-fixpoints. We also show that inquisitive (...) algebras determine Medvedev’s logic of finite problems. In addition to the algebraic characterization of H(B), we give a topological characterization of H(B) in terms of the recently introduced choice-free duality for Boolean algebras using so-called upper Vietoris spaces (UV-spaces). In particular, while a Boolean algebra B is realized as the Boolean algebra of compact regular open elements of a UV-space dual to B, we show that H(B) is realized as the algebra of compact open elements of this space. This connection yields a new topological semantics for inquisitive logic. (shrink)

This volume is not restricted to papers presented at the 1988 Colloquium, but instead aims to provide the reader with a (relatively) coherent reading on Algebraic Logic, with an emphasis on current research. To help the non-specialist reader, the book contains an introduction to cylindric and relation algebras by Roger D. Maddux and an introduction to Boolean Algebras by Bjarni Joacute;nsson.

We show that the conceptual distance between any two theories of first-order logic is the same as the generator distance between their Lindenbaum–Tarski algebras of concepts. As a consequence of this, we show that, for any two arbitrary mathematical structures, the generator distance between their meaning algebras (also known as cylindric set algebras) is the same as the conceptual distance between their first-order logic theories. As applications, we give a complete description for the distances between meaning algebras corresponding to structures (...) having at most three elements and show that this small network represents all the possible conceptual distances between complete theories. As a corollary of this, we will see that there are only two non-trivial structures definable on three-element sets up to conceptual equivalence (i.e., up to elementary plus definitional equivalence). (shrink)

This unique textbook states and proves all the major theorems of many-valued propositional logic and provides the reader with the most recent developments and trends, including applications to adaptive error-correcting binary search. The book is suitable for self-study, making the basic tools of many-valued logic accessible to students and scientists with a basic mathematical knowledge who are interested in the mathematical treatment of uncertain information. Stressing the interplay between algebra and logic, the book contains material never before published, such (...) as a simple proof of the completeness theorem and of the equivalence between Chang's MV algebras and Abelian lattice-ordered groups with unit - a necessary prerequisite for the incorporation of a genuine addition operation into fuzzy logic. Readers interested in fuzzy control are provided with a rich deductive system in which one can define fuzzy partitions, just as Boolean partitions can be defined and computed in classical logic. Detailed bibliographic remarks at the end of each chapter and an extensive bibliography lead the reader on to further specialised topics. (shrink)

We generalize the notion of a monadic algebra to that of a pseudomonadic algebra. In the same way as monadic algebras serve as algebraic models of epistemic modal system S5, pseudomonadic algebras serve as algebraic models of doxastic modal system KD45. The main results of the paper are: Characterization of subdirectly irreducible and simple pseudomonadic algebras, as well as Tokarz's proper filter algebras; Ordertopological representation of pseudomonadic algebras; Complete description of the lattice of subvarieties of the variety of (...) pseudomonadic algebras. (shrink)

In classical logic, the proposition expressed by a sentence is construed as a set of possible worlds, capturing the informative content of the sentence. However, sentences in natural language are not only used to provide information, but also to request information. Thus, natural language semantics requires a logical framework whose notion of meaning does not only embody informative content, but also inquisitive content. This paper develops the algebraic foundations for such a framework. We argue that propositions, in order to embody (...) both informative and inquisitive content in a satisfactory way, should be defined as non-empty, downward closed sets of possibilities, where each possibility in turn is a set of possible worlds. We define a natural entailment order over such propositions, capturing when one proposition is at least as informative and inquisitive as another, and we show that this entailment order gives rise to a complete Heyting algebra, with meet, join, and relative pseudo-complement operators. Just as in classical logic, these semantic operators are then associated with the logical constants in a first-order language. We explore the logical properties of the resulting system and discuss its significance for natural language semantics. We show that the system essentially coincides with the simplest and most well-understood existing implementation of inquisitive semantics, and that its treatment of disjunction and existentials also concurs with recent work in alternative semantics. Thus, our algebraic considerations do not lead to a wholly new treatment of the logical constants, but rather provide more solid foundations for some of the existing proposals. (shrink)

Algebraic proofs of the cut-elimination theorems for classical and intuitionistic logic are presented, and are used to show how one can sometimes extract a constructive proof and an algorithm from a proof that is nonconstructive. A variation of the double-negation translation is also discussed: if ϕ is provable classically, then ¬(¬ϕ)nf is provable in minimal logic, where θnf denotes the negation-normal form of θ. The translation is used to show that cut-elimination theorems for classical logic can be viewed as special (...) cases of the cut-elimination theorems for intuitionistic logic. (shrink)

The aim of this paper is to show that every topological space gives rise to a wealth of topological models of the modal logic S4.1. The construction of these models is based on the fact that every space defines a Boolean closure algebra (to be called a McKinsey algebra) that neatly reflects the structure of the modal system S4.1. It is shown that the class of topological models based on McKinsey algebras contains a canonical model that can be (...) used to prove a completeness theorem for S4.1. Further, it is shown that the McKinsey algebra MKX of a space X endoewed with an alpha-topologiy satisfies Esakia's GRZ axiom. (shrink)

Volume I provides a detailed analysis of cylindric algebras, starting with a formulation of their axioms and a development of their elementary properties, and proceeding to a deeper study of their interrelationships by means of general algebraic notions such as subalgebras, homomorphisms, direct products, free algebras, reducts and relativized algebras.

Provability, Computability and Reflection.

The invention of symbolic algebra in the sixteenth and seventeenth centuries fundamentally changed the way we do mathematics. If we want to understand this change and appreciate its importance, we must analyze it on two levels. One concerns the compositional function of algebraic symbols as tools for representing complexity; the other concerns the referential function of algebraic symbols, which enables their use as tools for describing objects (such as polynomials), properties (such as irreducibility), relations (such as divisibility), and operations (...) (such as factorization). The reconstruction of both the compositional function and the referential function of algebraic symbols requires the use of different analytic tools and the taking of different temporal perspectives. In this chapter, we offer both: a reconstruction of the compositional function of algebraic symbols, and a reconstruction of their referential function. (shrink)

By a sentential logic we understand a pair, where S is a sentential language, i.e. an absolutely free algebra freely generated by an infinite set p, q, r,... of sentential variables and endowed with countably many finitary connectives §1, §2,... and C is a consequence operation on S, the underlying set of S, satisfying the condition of structurality: eC ⊆ C, for every endomorphism e of S and for every X ⊆ S. If no confusion is likely we shall (...) identify a logic with its consequence operation C. A logic C is standard if C = [ {C : Y ⊆ X & Y is finite}, for all X ⊆ S. (shrink)

This book is intended for mathematicians. Its origins lie in a course of lectures given by an algebraist to a class which had just completed a sub stantial course on abstract algebra. Consequently, our treatment ofthe sub ject is algebraic. Although we assurne a reasonable level of sophistication in algebra, the text requires little more than the basic notions of group, ring, module, etc. A more detailed knowledge of algebra is required for some of . the exercises. (...) We also assurne a familiarity with the main ideas of set theory, including cardinal numbers and Zorn's Lemma. In this book, we carry out a mathematical study of the logic used in mathematics. We do this by constructing a mathematical model oflogic and applying mathematics to analyse the properties of the model. We therefore regard all our existing knowledge of mathematics as being applicable to the analysis of the model, and in particular we accept set theory as part of the meta-Ianguage. We are not attempting to construct a foundation on which all mathematics is to be based-rather, any conclusions to be drawn about the foundations of mathematics co me only by analogy with the model, and are to be regarded in much the same way as the conclusions drawn from any scientific theory. (shrink)

It is shown that axiomatic extensions of intuitionistic propositional calculus defining univocally new connectives, including those proposed by Gabbay, are strongly complete with respect to valuations in Heyting algebras with additional operations. In all cases, the double negation of such a connective is equivalent to a formula of intuitionistic calculus. Thus, under the excluded third law it collapses to a classical formula, showing that this condition in Gabbay's definition is redundant. Moreover, such connectives can not be interpreted in all Heyting (...) algebras, unless they are already equivalent to a formula of intuitionistic calculus. These facts relativize to connectives over intermediate logics. In particular, the intermediate logic with values in the chain of length n may be "completed" conservatively by adding a single unary connective, so that the expanded system does not allow further axiomatic extensions by new connectives. (shrink)

This comprehensive text shows how various notions of logic can be viewed as notions of universal algebra providing more advanced concepts for those who have an introductory knowledge of algebraic logic, as well as those wishing to delve into more theoretical aspects.

Einstein algebras have been suggested (Earman 1989) and rejected (Rynasiewicz 1992) as a way to avoid the hole argument against spacetime substantivalism. In this article, I debate their merits and faults. In particular, I suggest that a gauge‐invariant interpretation of Einstein algebras that avoids the hole argument can be associated with one approach to quantizing gravity, and, for this reason, is at least as well motivated as sophisticated substantivalist and relationalist interpretations of the standard tensor formalism.

The first known statements of the deduction theorems for the first-order predicate calculus and the classical sentential logic are due to Herbrand [8] and Tarski [14], respectively. The present paper contains an analysis of closure spaces associated with those sentential logics which admit various deduction theorems. For purely algebraic reasons it is convenient to view deduction theorems in a more general form: given a sentential logic C (identified with a structural consequence operation) in a sentential language I, a quite arbitrary (...) set P of formulas of I built up with at most two distinct sentential variables p and q is called a uniform deduction theorem scheme for C if it satisfies the following condition: for every set X of formulas of I and for any formulas and , C(X{{a}}) iff P(, ) AC(X). [P(, ) denotes the set of formulas which result by the simultaneous substitution of for p and for q in all formulas in P]. The above definition encompasses many particular formulations of theorems considered in the literature to be deduction theorems. Theorem 1.3 gives necessary and sufficient conditions for a logic to have a uniform deduction theorem scheme. Then, given a sentential logic C with a uniform deduction theorem scheme, the lattices of deductive filters on the algebras A similar to the language of C are investigated. It is shown that the join-semilattice of finitely generated (= compact) deductive filters on each algebra A is dually Brouwerian. (shrink)

We generalize the double negation construction of Boolean algebras in Heyting algebras to a double negation construction of the same in Visser algebras. This result allows us to generalize Glivenko’s theorem from intuitionistic propositional logic and Heyting algebras to Visser’s basic propositional logic and Visser algebras.

Tarski defined a way of assigning to each Boolean algebra, B, an invariant inv(B) ∈ In, where In is a set of triples from ℕ, such that two Boolean algebras have the same invariant if and only if they are elementarily equivalent. Moreover, given the invariant of a Boolean algebra, there is a computable procedure that decides its elementary theory. If we restrict our attention to dense Boolean algebras, these invariants determine the algebra up to isomorphism. In (...) this paper we analyze the complexity of the question "Does B have invariant x?" For each x ∈ In we define a complexity class Γx that could be either Σⁿ, Πⁿ, Σⁿ ∧ Πⁿ, or Πω+1 depending on x, and we prove that the set of indices for computable Boolean algebras with invariant x is complete for the class Γx. Analogs of many of these results for computably enumerable Boolean algebras were proven in earlier works by Selivanov. In a more recent work, he showed that similar methods can be used to obtain the results for computable ones. Our methods are quite different and give new results as well. As the algebras we construct to witness hardness are all dense, we establish new similar results for the complexity of various isomorphism problems for dense Boolean algebras. (shrink)

The Algebra of Revolution is the first book to study Marxist method as it has been developed by the main representatives of the classical Marxist tradition, namely Marx and Engels, Luxembourg, Lenin, Lukacs, Gramsci, and Trotsky. This book provides the only single volume study of major Marxist thinkers' views on the crucial question of the dialectic, connecting them with pressing contemporary, political and theoretical questions. This title available in eBook format. Click here for more information . Visit our eBookstore (...) at: www.ebookstore.tandf.co.uk. (shrink)

A Hilbert algebra with supremum is a Hilbert algebra where the associated order is a join-semilattice. This class of algebras is a variety and was studied in Celani and Montangie . In this paper we shall introduce and study the variety of $${H_{\Diamond}^{\vee}}$$ H ◊ ∨ -algebras, which are Hilbert algebras with supremum endowed with a modal operator $${\Diamond}$$ ◊ . We give a topological representation for these algebras using the topological spectral-like representation for Hilbert algebras with supremum (...) given in Celani and Montangie . We will consider some particular varieties of $${H_{\Diamond}^{\vee}}$$ H ◊ ∨ -algebras. These varieties are the algebraic counterpart of extensions of the implicative fragment of the intuitionistic modal logic $${\mathbf{IntK}_{\Diamond}}$$ IntK ◊ . We also determine the congruences of $${H_{\Diamond}^{\vee}}$$ H ◊ ∨ -algebras in terms of certain closed subsets of the associated space, and in terms of a particular class of deductive systems. These results enable us to characterize the simple and subdirectly irreducible $${H_{\Diamond}^{\vee }}$$ H ◊ ∨ -algebras. (shrink)

The Belnap–Dunn logic is a well-known and well-studied four-valued logic, but until recently little has been known about its extensions, i.e. stronger logics in the same language, called super-Belnap logics here. We give an overview of several results on these logics which have been proved in recent works by Přenosil and Rivieccio. We present Hilbert-style axiomatizations, describe reduced matrix models, and give a description of the lattice of super-Belnap logics and its connections with graph theory. We adopt the point of (...) view ofAlgebraic Logic, exploring applications of the general theory of algebraization of logics to the super-Belnap family. In this respect we establish a number of new results, including a description of the algebraic counterparts, Leibniz filters, and strong versions of super-Belnap logics, as well as the classification of these logics within the Leibniz and Frege hierarchies. (shrink)

We suggest an algebraic approach to proof-theoretic analysis based on the notion of graded provability algebra, that is, Lindenbaum boolean algebra of a theory enriched by additional operators which allow for the structure to capture proof-theoretic information. We use this method to analyze Peano arithmetic and show how an ordinal notation system up to 0 can be recovered from the corresponding algebra in a canonical way. This method also establishes links between proof-theoretic ordinal analysis and the work (...) which has been done in the last two decades on provability logic and reflection principles. Because of its abstract algebraic nature, we hope that it will also be of interest for non-prooftheorists. (shrink)