The paper provides a uniform Gentzen-style proof-theoretic framework for various subsystems of classical predicate logic. In particular, predicate logics obtained by adopting van Behthem''s modal perspective on first-order logic are considered. The Gentzen systems for these logics augment Belnap''s display logic by introduction rules for the existential and the universal quantifier. These rules for x and x are analogous to the display introduction rules for the modal operators and and do not themselves allow the Barcan formula or its converse to (...) be derived. En route from the minimal modal predicate logic to full first-order logic, axiomatic extensions are captured by purely structural sequent rules. (shrink)

We discuss a `negative' way of defining frame classes in (multi)modal logic, and address the question of whether these classes can be axiomatized by derivation rules, the `non-ξ rules', styled after Gabbay's Irreflexivity Rule. The main result of this paper is a metatheorem on completeness, of the following kind: If Λ is a derivation system having a set of axioms that are special Sahlqvist formulas and Λ+ is the extension of Λ with a set of non-ξ rules, then Λ+ is (...) strongly sound and complete with respect to the class of frames determined by the axioms and the rules. (shrink)

Treating the existential quantification ∃ν i as a diamond $\diamond_i$ and the identity ν i = ν j as a constant δ ij , we study restricted versions of first order logic as if they were modal formalisms. This approach is closely related to algebraic logic, as the Kripke frames of our system have the type of the atom structures of cylindric algebras; the full cylindric set algebras are the complex algebras of the intended multidimensional frames called cubes. The main (...) contribution of the paper is a characterization of these cube frames for the finite-dimensional case and, as a consequence of the special form of this characterization, a completeness theorem for this class. These results lead to finite, though unorthodox, derivation systems for several related formalisms, e.g. for the valid n-variable first order formulas, for type-free valid formulas and for the equational theory of representable cylindric algebras. The result for type-free valid formulas indicates a positive solution to Problem 4.16 of Henkin, Monk and Tarski [16]. (shrink)

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). As a result, fork arrow logic attains the expressive power of its first-order (...) correspondence language, so both can express the same input–output behavior of processes. (shrink)

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). As a result, fork arrow logic attains the expressive power of its first-order (...) correspondence language, so both can express the same input-output behavior of processes. (shrink)

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.

What precisely are fragments of classical first-order logic showing “modal” behaviour? Perhaps the most influential answer is that of Gabbay 1981, which identifies them with so-called “finite-variable fragments”, using only some fixed finite number of variables (free or bound). This view-point has been endorsed by many authors (cf. van Benthem 1991). We will investigate these fragments, and find that, illuminating and interesting though they are, they lack the required nice behaviour in our sense. (Several new negative results support this claim.) (...) As a counterproposal, then, we define a large fragment of predicate logic characterized by its use of only bounded quantification. This so-called guarded fragment enjoys the above nice properties, including decidability, through an effectively bounded finite model property. (These are new results, obtained by generalizing notions and techniques from modal logic.) Moreover, its own internal finite variable hierarchy turns out to work well. Finally, we shall make another move. The above analogy works both ways. Modal operators are like quantifiers, but quantifiers are also like modal operators. This observation inspires a generalized semantics for first-order predicate logic with accessibility constraints on available assignments (cf. N´emeti 1986, 1992) which moves the earlier quantifier restrictions into the semantics. This provides a fresh look at the landscape of possible predicate logics, including candidates sharing various desirable features with basic modal logic – in particular, its decidability. (shrink)

With each projective geometry we can associate a Lyndon algebra. Such an algebra always satisfies Tarski's axioms for relation algebras and Lyndon algebras thus form an interesting connection between the fields of projective geometry and algebraic logic. In this paper we prove that if G is a class of projective geometries which contains an infinite projective geometry of dimension at least three, then the class L(G) of Lyndon algebras associated with projective geometries in G has an undecidable equational theory. In (...) our proof we develop and use a connection between projective geometries and diagonal-free cylindric algebras. (shrink)

We give a condensed survey of recent research on generalized quantifiers in logic, linguistics and computer science, under the following headings: Logical definability and expressive power, Polyadic quantifiers and linguistic definability, Weak semantics and axiomatizability, Computational semantics, Quantifiers in dynamic settings, Quantifiers and modal logic, Proof theory of generalized quantifiers.

Following research initiated by Tarski, Craig and Nemeti, and futher pursued by Sain and others, we show that for certain subsets G of $^\omega \omega $ , atomic countable G poiyadic algebras are completely representable. G polyadic algebras are obtained by restricting the similarity type and axiomatization of ω-dimensional polyadic algebras to finite quantifiers and substitutions in G. This contrasts the cases of cylindric and relation algebras.

A class of many-sorted polyadic set algebras is introduced. These generalise structure and model in a way that is relevant in regards to the Entscheidungsproblem and to automated reasoning.A downward Löwenheim-Skolem property is shown in that each satisfiable finite conjunction of purely relational first-order prenex sentences has a finite generalised model. This property does, together with a construction related to doubling the size of a finite structure, provide several strict generalisations of the strategy of finite model search for disproving.

For an arbitrary similarity type of Boolean Algebras with Operators we define a class of Sahlqvist identities. Sahlqvist identities have two important properties. First, a Sahlqvist identity is valid in a complex algebra if and only if the underlying relational atom structure satisfies a first-order condition which can be effectively read off from the syntactic form of the identity. Second, and as a consequence of the first property, Sahlqvist identities are canonical, that is, their validity is preserved under taking canonical (...) embedding algebras. Taken together, these properties imply that results about a Sahlqvist variety V van be obtained by reasoning in the elementary class of canonical structures of algebras in V. We give an example of this strategy in the variety of Cylindric Algebras: we show that an important identity called Henkin's equation is equivalent to a simpler identity that uses only one variable. We give a conceptually simple proof by showing that the firstorder correspondents of these two equations are equivalent over the class of cylindric atom structures. (shrink)

Monadic MV-algebras are an algebraic model of the predicate calculus of the Łukasiewicz infinite valued logic in which only a single individual variable occurs. GMV-algebras are a non-commutative generalization of MV-algebras and are an algebraic counterpart of the non-commutative Łukasiewicz infinite valued logic. We introduce monadic GMV-algebras and describe their connections to certain couples of GMV-algebras and to left adjoint mappings of canonical embeddings of GMV-algebras. Furthermore, functional MGMV-algebras are studied and polyadic GMV-algebras are introduced and discussed.

We present a formalization of first-order predicate calculus with equality which, unlike traditional systems with axiom schemata or substitution rules, is finitely axiomatized in the sense that each step in a formal proof admits only finitely many choices. This formalization is primarily based on the inference rule of condensed detachment of Meredith. The usual primitive notions of free variable and proper substitution are absent, making it easy to verify proofs in a machine-oriented application. Completeness results are presented. The example of (...) Zermelo-Fraenkel set theory is shown to be finitely axiomatized under the formalization. The relationship with resolution-based theorem provers is briefly discussed. A closely related axiomatization of traditional predicate calculus is shown to be complete in a strong metamathematical sense. (shrink)

Among others we will prove that the equational theory of ω dimensional representable polyadic equality algebras (RPEA ω 's) is not schema axiomatizable. This result is in interesting contrast with the Daigneault-Monk representation theorem, which states that the class of representable polyadic algebras is finite schema-axiomatizable (and hence the equational theory of this class is finite schema-axiomatizable, as well). We will also show that the complexity of the equational theory of RPEA ω is also extremely high in the recursion theoretic (...) sense. Finally, comparing the present negative results with the positive results of Ildiko Sain and Viktor Gyuris [12], the following methodological conclusions will be drawn: The negative properties of polyadic (equality) algebras can be removed by switching from what we call the "polyadic algebraic paradigm" to the "cylindric algebraic paradigm". (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)

In this paper we show that relativized versions of relation set algebras and cylindric set algebras have undecidable equational theories if we include coordinatewise versions of the counting operations into the similarity type. We apply these results to the guarded fragment of first-order logic.

The class \ of t rue p airing a lgebras is defined to be the class of relation algebras expanded with concrete set theoretical projection functions. The main results of the present paper is that neither the equational theory of \ nor the first order theory of \ are decidable. Moreover, we show that the set of all equations valid in \ is exactly on the \ level. We consider the class \ of the relation algebra reducts of \ ’s, (...) as well. We prove that the equational theory of \ is much simpler, namely, it is recursively enumerable. We also give motivation for our results and some connections to related work. (shrink)

SC , CA , QA and QEA stand for the classes of Pinter's substitution algebras, Tarski's cylindric algebras, Halmos' quasipolyadic algebras, and quasipolyadic equality algebras of dimension , respectively. Generalizing a result of Németi on cylindric algebras, we show that for K {SC, CA, QA, QEA} and ordinals , the class Nr K of -dimensional neat reducts of -dimensional K algebras, though closed under taking homomorphic images and products, is not closed under forming subalgebras (i.e. is not a variety) if (...) and only if > 1.From this it easily follows that for 1 , the operation of forming -neat reducts of algebras in K does not commute with forming subalgebras, a notion to be made precise. (shrink)

In this paper, we introduce a general technology, calledtaming, for finding well-behaved versions of well-investigated logics. Further, we state completeness, decidability, definability and interpolation results for a multimodal logic, calledarrow logic, with additional operators such as thedifference operator, andgraded modalities. Finally, we give a completeness proof for a strong version of arrow logic.

ABSTRACT The two main directions pursued in the present paper are the following. The first direction was started by Pigozzi in 1969. In [Mak 91] and [Mak 79] Maksimova proved that a normal modal logic has the Craig interpolation property iff the corresponding class of algebras has the superamalgamation property. In this paper we extend Maksimova's theorem to normal multi-modal logics with arbitrarily many, not necessarily unary modalities, and to not necessarily normal multi-modal logics with modalities of ranks smaller than (...) 2. To extend the characterization beyond multi-modal logics, we look at arbitrary algebraizable logics. We will introduce an algebraic property equivalent with the Craig interpolation property in algebraizable logics, and prove that the superamalgamation property implies the Craig interpolation property. The problem of extending the characterization result to non-normal non-unary modal logics also will be discussed. In the second direction pursued herein: for non-normal modal logic with one unary modality Lemmon [Lem 66] gave a possible worlds semantics. Here we give a more general possible worlds semantics for not necessarily normal multi-modal logics with arbitrarily many not necessarily unary modalities. Strongly related to the above is the theorem, proved, e.g., in Jóns son-Tarski [JT 52] and Henkin-Monk-Tarski [HMT 71], that every normal Boolean algebra with operators can be represented as a subalgebra of the complex algebra of some relational structure. We extend this result to not necessarily normal BAO's as follows. We define partial relational structures and show that every not necessarily normal BAO is embeddable into the complex algebra of a partial relational structure. This gives a possible worlds semantics for not necessarily normal multi-modal logics. (shrink)

We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finite relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an (...) algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable. An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras. Other instances of this approach are looked at, and include the step by step method. (shrink)

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)

We show that the usual axiom system of quasi polyadic equality algebras is strongly redundant. Then, so called non‐commutative quasi‐polyadic equality algebras are introduced (), in which, among others, the commutativity of cylindrifications is dropped. As is known, quasi‐polyadic equality algebras are not representable in the classical sense, but we prove that algebras in are representable by quasi‐polyadic relativized set algebras, or more exactly by algebras in.

This essay is about how the notion of “structure” in ontic structuralism might be made precise. More specifically, my aim is to make precise the idea that the structure of the world is given by the relations inhering in the world, in such a way that the relations are ontologically prior to their relata. The central claim is the following: one can do so by giving due attention to the relationships that hold between those relations, by making use of certain (...) notions from algebraic logic. (shrink)

For an arbitrary similarity type of Boolean Algebras with Operators we define a class ofSahlqvist identities. Sahlqvist identities have two important properties. First, a Sahlqvist identity is valid in a complex algebra if and only if the underlying relational atom structure satisfies a first-order condition which can be effectively read off from the syntactic form of the identity. Second, and as a consequence of the first property, Sahlqvist identities arecanonical, that is, their validity is preserved under taking canonical embedding algebras. (...) Taken together, these properties imply that results about a Sahlqvist variety V van be obtained by reasoning in the elementary class of canonical structures of algebras in V.We give an example of this strategy in the variety of Cylindric Algebras: we show that an important identity calledHenkin's equation is equivalent to a simpler identity that uses only one variable. We give a conceptually simple proof by showing that the first-order correspondents of these two equations are equivalent over the class of cylindric atom structures. (shrink)

In this paper we show that the class of fork squares has a complete orthodox axiomatization in fork arrow logic (FAL). This result may be seen as an orthodox counterpart of Venema's non-orthodox axiomatization for the class of squares in arrow logic. FAL is the modal logic of fork algebras (FAs) just as arrow logic is the modal logic of relation algebras (RAs). FAs extend RAs by a binary fork operator and are axiomatized by adding three equations to RAs equational (...) axiomatization. A proper FA is an algebra of relations where the fork is induced by an injective operation coding pair formation. In contrast to RAs, FAs are representable by proper ones and their equational theory has the expressive power of full first-order logic. A square semantics (the set of arrows is U×U for some set U) for arrow logic was defined by Y. Venema. Due to the negative results about the finite axiomatizability of representable RAs, Venema provided a non-orthodox finite axiomatization for arrow logic by adding a new rule governing the applications of a difference operator. We address here the question of extending the type of relational structures to define orthodox axiomatizations for the class of squares. Given the connections between this problem and the finitization problem addressed by I. Németi, we suspect that this cannot be done by using only logical operations. The modal version of the FA equations provides an orthodox axiomatization for FAL which is complete in view of the representability of FAs. Here we review this result and carry it further to prove that this orthodox axiomatization for FAL also axiomatizes the class of fork squares. (shrink)

We shall show that certain natural and interesting intervals in the lattice of varieties of representable relation algebras embed the lattice of all subsets of the natural numbers, and therefore must have a very complicated lattice-theoretic structure.

We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension n (for finite n > 2) with the additional property that they are one-generated and the set of all n by n atomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments of first order (...) logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic. (shrink)

Henkin and Tarski proved that an atomic cylindric algebra in which every atom is a rectangle must be representable . This theorem and its analogues for quasi-polyadic algebras with and without equality are formulated in Henkin, Monk and Tarski [13]. We introduce a natural and more general notion of rectangular density that can be applied to arbitrary cylindric and quasi-polyadic algebras, not just atomic ones. We then show that every rectangularly dense cylindric algebra is representable, and we extend this result (...) to other classes of algebras of logic, for example quasi-polyadic algebras and substitution-cylindrification algebras with and without equality, relation algebras, and special Boolean monoids. The results of op. cit. mentioned above are special cases of our general theorems. We point out an error in the proof of the Henkin-Monk-Tarski representation theorem for atomic, equality-free, quasi-polyadic algebras with rectangular atoms. The error consists in the implicit assumption of a property that does not, in general, hold. We then give a correct proof of their theorem. Henkin and Tarski also introduced the notion of a rich cylindric algebra and proved in op. cit. that every rich cylindric algebra of finite dimension satisfying certain special identities is representable. We introduce a modification of the notion of a rich algebra that, in our opinion, renders it more natural. In particular, under this modification richness becomes a density notion. Moreover, our notion of richness applies not only to algebras with equality, such as cylindric algebras, but also to algebras without equality. We show that a finite dimensional algebra is rich iff it is rectangularly dense and quasi-atomic; moreover, each of these conditions is also equivalent to a very natural condition of point density . As a consequence, every finite dimensional rich algebra of logic is representable. We do not have to assume the validity of any special identities to establish this representability. Not only does this give an improvement of the Henkin-Tarski representation theorem for rich cylindric algebras, it solves positively an open problem in op. cit. concerning the representability of finite dimensional rich quasi-polyadic algebras without equality. (shrink)

The problem of whether Lambek Calculus is complete with respect to (w.r.t.) relational semantics, has been raised several times, cf. van Benthem (1989a) and van Benthem (1991). In this paper, we show that the answer is in the affirmative. More precisely, we will prove that that version of the Lambek Calculus which does not use the empty sequence is strongly complete w.r.t. those relational Kripke-models where the set of possible worlds,W, is a transitive binary relation, while that version of the (...) Lambek Calculus where we admit the empty sequence as the antecedent of a sequent is strongly complete w.r.t. those relational models whereW=U×U for some setU. We will also look into extendability of this completeness result to various fragments of Girard's Linear Logic as suggested in van Benthem (1991), p. 235, and investigate the connection between the Lambek Calculus and language models. (shrink)

We show that not all epimorphisms are surjective in certain classes of infinite dimensional cylindric algebras, Pinter's substitution algebras and Halmos' quasipolyadic algebras with and without equality. It follows that these classes fail to have the strong amalgamation property. This answers a question in [3] and a question of Pigozzi in his landmark paper on amalgamation [9]. The cylindric case was first proved by Judit Madarasz [7]. The proof presented herein is substantially different. By a result of Németi, our result (...) implies that the Beth-definability Theorem fails for certain expansions of first order logic. (shrink)

SC, CA, QA and QEA denote the class of Pinter’s substitution algebras, Tarski’s cylindric algebras, Halmos’ quasi-polyadic and quasi-polyadic equality algebras, respectively. Let . and . We show that the class of n dimensional neat reducts of algebras in K m is not elementary. This solves a problem in [2]. Also our result generalizes results proved in [1] and [2].