Fibring is defined as a mechanism for combining logics with a first-order base, at both the semantic and deductive levels. A completeness theorem is established for a wide class of such logics, using a variation of the Henkin method that takes advantage of the presence of equality and inequality in the logic. As a corollary, completeness is shown to be preserved when fibring logics in that class. A modal first-order logic is obtained as (...) a fibring where neither the Barcan formula nor its converse hold. (shrink)

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and (...) finite satisfiability problems are algorithmically solvable for restricted subsets---or, as we say, fragments---of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees. (shrink)

We introduce a Gentzen-style modal predicate logic and prove the cut-elimination theorem for it. This sequent calculus of cut-free proofs is chosen as a proxy to develop the proof-theory of the logics introduced in [14, 15, 4]. We present syntactic proofs for all the metatheoretical results that were proved model-theoretically in loc. cit. and moreover prove that the form of weak reflection proved in these papers is as strong as possible.

This paper deals with the translation of first order formulas to predicate S5 formulas. This translation does not bring the first order formula itself to a modal system, but modal interpretation of the first order formula can be given by the translation. Every formula can be translated, and the additional condition such as formula's having only one variable, or having both world domain and individual domain is not required. I introduce an indexical (...) predicate 'E' for the translation. The meaning that 'E(a)' is true is 'this world is 'a' '. Because of this meaning, I call 'E' an indexical predicate. 'E' plays an important role for the translation. In addition that the modal formulas can be translated into first order formulas, we can conclude that the first order logic and modal predicate logic isintertranslatable. (shrink)

I consider the first-order modal logic which counts as valid those sentences which are true on every interpretation of the non-logical constants. Based on the assumptions that it is necessary what individuals there are and that it is necessary which propositions are necessary, Timothy Williamson has tentatively suggested an argument for the claim that this logic is determined by a possible world structure consisting of an infinite set of individuals and an infinite set of worlds. (...) He notes that only the cardinalities of these sets matters, and that not all pairs of infinite sets determine the same logic. I use so-called two-cardinal theorems from model theory to investigate the space of logics and consequence relations determined by pairs of infinite sets, and show how to eliminate the assumption that worlds are individuals from Williamson’s argument. (shrink)

This is a thorough treatment of first-order modal logic. The book covers such issues as quantification, equality (including a treatment of Frege's morning star/evening star puzzle), the notion of existence, non-rigid constants and function symbols, predicate abstraction, the distinction between nonexistence and nondesignation, and definite descriptions, borrowing from both Fregean and Russellian paradigms.

In this paper the language of first-order modal logic is enriched with an operator @ ('actually') such that, in any model, the evaluation of a formula @A at a possible world depends on the evaluation of A at the actual world. The models have world-variable domains. All the logics that are discussed extend the classical predicate calculus, with or without identity, and conform to the philosophical principle known as serious actualism. The basic logic relies on (...) the system K, whereas others correspond to various properties that the actual world may have. All the logics are axiomatized. (shrink)

The paper focuses on extending to the first order case the semantical program for modalities first introduced by Dana Scott and Richard Montague. We focus on the study of neighborhood frames with constant domains and we offer in the first part of the paper a series of new completeness results for salient classical systems of first order modal logic. Among other results we show that it is possible to prove strong completeness results (...) for normal systems without the Barcan Formula (like FOL + K)in terms of neighborhood frames with constant domains. The first order models we present permit the study of many epistemic modalities recently proposed in computer science as well as the development of adequate models for monadic operators of high probability. Models of this type are either difficult of impossible to build in terms of relational Kripkean semantics [40].We conclude by introducing general first order neighborhood frames with constant domains and we offer a general completeness result for the entire family of classical first order modal systems in terms of them, circumventing some well-known problems of propositional and first order neighborhood semantics (mainly the fact that many classical modal logics are incomplete with respect to an unmodified version of either neighborhood or relational frames). We argue that the semantical program that thus arises offers the first complete semantic unification of the family of classical first order modal logics. (shrink)

Classical logic has proved inadequate in various areas of computer science, artificial intelligence, mathematics, philosopy and linguistics. This is an introduction to extensions of first-order logic, based on the principle that many-sorted logic (MSL) provides a unifying framework in which to place, for example, second-order logic, type theory, modal and dynamic logics and MSL itself. The aim is two fold: only one theorem-prover is needed; proofs of the metaproperties of the different existing (...) calculi can be avoided by borrowing them from MSL. To make the book accessible to readers from different disciplines, whilst maintaining precision, the author has supplied detailed step-by-step proofs, avoiding difficult arguments, and continually motivating the material with examples. Consequently this can be used as a reference, for self-teaching or for first-year graduate courses. (shrink)

We present a natural standard translation of inquisitive modal logic $\mathrm{InqML}$ into first-order logic over the natural two-sorted relational representations of the intended models, which captures the built-in higher-order features of $\mathrm{InqML}$. This translation is based on a graded notion of flatness that ties the inherent second-order, team-semantic features of $\mathrm{InqML}$ over information states to subsets or tuples of bounded size. A natural notion of pseudo-models, which relaxes the non-elementary constraints on the intended (...) models, gives rise to an elementary, purely model-theoretic proof of the compactness property for $\mathrm{InqML}$. Moreover, we prove a Hennessy-Milner theorem for $\mathrm{InqML}$, which crucially uses $\omega $ -saturated pseudo-models and the new standard translation. As corollaries we also obtain van Benthem style characterisation theorems. (shrink)

We generalize two well-known model-theoretic characterization theorems from propositional modal logic to first-order modal logic. We first study FML-definable frames and give a version of the Goldblatt–Thomason theorem for this logic. The advantage of this result, compared with the original Goldblatt–Thomason theorem, is that it does not need the condition of ultrafilter reflection and uses only closure under bounded morphic images, generated subframes and disjoint unions. We then investigate Lindström type theorems for (...) first-order modal logic. We show that FML has the maximal expressive power among the logics extending FML which satisfy compactness, bisimulation invariance and the Tarski union property. (shrink)

We present the first-order logic of change, which is an extension of the propositional logic of change $\textsf {LC}\Box $ developed and axiomatized by Świętorzecka and Czermak. $\textsf {LC}\Box $ has two primitive operators: ${\mathcal {C}}$ to be read it changes whether and $\Box $ for constant unchangeability. It implements the philosophically grounded idea that with the help of the primary concept of change it is possible to define the concept of time. One of the characteristic (...) axioms for ${\mathcal {C}}$ is ${\mathcal {C}} A \to {\mathcal {C}}\neg A$ and one of the primitive rules is $\omega $-rule introducing $\Box $. It turns out that the next operator is definable in $\textsf {LC}\Box $. Logic $\textsf {LC}\Box $ with next is equivalent to certain fragment of $\textsf {LTL}$ extended by the appropriate definition of ${\mathcal {C}}$. Recently, $\textsf {LC}\Box $ has also been modified to the propositional logic of ‘branching’ changes $\textsf {BTC}$ by Łyczak and the logic of ‘parallel’ changes $\textsf {LC}\Box $ ↳ by Świętorzecka and Łyczak. Extended in an appropriate manner, $\textsf {BTC}$ is equivalent to a certain fragment of logic $\textsf {CTL}$ to which definitions of two kinds of changes have been added. Here we propose an extension of $\textsf {LC}\Box $ to first-order logic in which, again, the only primitive modal operators are ${\mathcal {C}}$ and $\Box $. We interpret our logic in the semantics of histories of changes. We give an axiomatic system $\textsf {LC}\Box Q$ for the considered logic, and we show selected theses about some relationships between ${\mathcal {C}}$, $\Box $ and $\forall $. Then we prove the completeness of $\textsf {LC}\Box Q$. Finally, we compare our logic with $\textsf {FOLT}$ and show the relation between $\textsf {LC}\Box Q$ and a certain fragment of the Kröger system $\varSigma $ to which the definition of ${\mathcal {C}}$ was added. (shrink)

It is shown that a formula of modal propositional logic has precisely the same models as a sentence of the first-order language of a single dyadic predicate iff its class of models is closed under ultraproducts. as a corollary, any modal formula definable by a set of first-order conditions is always definable by a single such condition. these results are then used to show that the formula (lmp 'validates' mlp) is not first- (...) class='Hi'>order definable. (shrink)

The paper studies first order extensions of classical systems of modal logic (see (Chellas, 1980, part III)). We focus on the role of the Barcan formulas. It is shown that these formulas correspond to fundamental properties of neighborhood frames. The results have interesting applications in epistemic logic. In particular we suggest that the proposed models can be used in order to study monadic operators of probability (Kyburg, 1990) and likelihood (Halpern-Rabin, 1987).

The paper focuses on extending to the first order case the semantical program for modalities first introduced by Dana Scott and Richard Montague. We focus on the study of neighborhood frames with constant domains and we offer in the first part of the paper a series of new completeness results for salient classical systems of first order modal logic. Among other results we show that it is possible to prove strong completeness results (...) for normal systems without the Barcan Formula (like FOL + K)in terms of neighborhood frames with constant domains. The first order models we present permit the study of many epistemic modalities recently proposed in computer science as well as the development of adequate models for monadic operators of high probability. Models of this type are either difficult of impossible to build in terms of relational Kripkean semantics [40].We conclude by introducing general first order neighborhood frames with constant domains and we offer a general completeness result for the entire family of classical first order modal systems in terms of them, circumventing some well-known problems of propositional and first order neighborhood semantics (mainly the fact that many classical modal logics are incomplete with respect to an unmodified version of either neighborhood or relational frames). We argue that the semantical program that thus arises offers the first complete semantic unification of the family of classical first order modal logics. (shrink)

Formalizing categorical propositions of traditional logic in the language of quantifiers and propositional functions is no straightforward matter, especially when modalities get involved. Starting...

The paper focuses on extending to the first order case the semantical program for modalities first introduced by Dana Scott and Richard Montague. We focus on the study of neighborhood frames with constant domains and we offer in the first part of the paper a series of new completeness results for salient classical systems of first order modal logic. Among other results we show that it is possible to prove strong completeness results (...) for normal systems without the Barcan Formula (like FOL + K)in terms of neighborhood frames with constant domains. The first order models we present permit the study of many epistemic modalities recently proposed in computer science as well as the development of adequate models for monadic operators of high probability. Models of this type are either difficult of impossible to build in terms of relational Kripkean semantics [40].We conclude by introducing general first order neighborhood frames with constant domains and we offer a general completeness result for the entire family of classical first order modal systems in terms of them, circumventing some well-known problems of propositional and first order neighborhood semantics (mainly the fact that many classical modal logics are incomplete with respect to an unmodified version of either neighborhood or relational frames). We argue that the semantical program that thus arises offers the first complete semantic unification of the family of classical first order modal logics. (shrink)

This paper follows Part I of our essay on case-intensional first-order logic (CIFOL; Belnap and Müller (2013)). We introduce a framework of branching histories to take account of indeterminism. Our system BH-CIFOL adds structure to the cases, which in Part I formed just a set: a case in BH-CIFOL is a moment/history pair, specifying both an element of a partial ordering of moments and one of the total courses of events (extending all the way into the future) (...) that that moment is part of. This framework allows us to define the familiar Ockhamist temporal/modal connectives, most notably for past, future, and settledness. The novelty of our framework becomes visible in our discussion of substances in branching histories, i.e., in its first-order part. That discussion shows how the basic idea of tracing an individual thing from case to case via an absolute property is applicable in a branching histories framework. We stress the importance of keeping apart extensionality and moment-definiteness, and give a formal account of how the specification of natural sortals and natural qualities turns out to be a coordination task in BH-CIFOL. We also provide a detailed answer to Lewis’s well-known argument against branching histories, exposing the fallacy in that argument. (shrink)

That every first-order theory has a coherent conservative extension is regarded by some as obvious, even trivial, and by others as not at all obvious, but instead remarkable and valuable; the result is in any case neither sufficiently well-known nor easily found in the literature. Various approaches to the result are presented and discussed in detail, including one inspired by a problem in the proof theory of intermediate logics that led us to the proof of the present paper. (...) It can be seen as a modification of Skolem’s argument from 1920 for his “Normal Form” theorem. “Geometric” being the infinitary version of “coherent”, it is further shown that every infinitary first-order theory, suitably restricted, has a geometric conservative extension, hence the title. The results are applied to simplify methods used in reasoning in and about modal and intermediate logics. We include also a new algorithm to generate special coherent implications from an axiom, designed to preserve the structure of formulae with relatively little use of normal forms. (shrink)

In an earlier defense of the view that the fundamental logical properties of logical truth and logical consequence obtain or fail to obtain only relative to contexts, I focused on a variation of Kaplan’s own modal logic of indexicals. In this paper, I state a semantics and sketch a system of proof for a first-order logic of demonstratives, and sketch proofs of soundness and completeness. (I omit details for readability.) That these results obtain for the (...) first-order logic of demonstratives shows that the significance of demonstratives for logic exceeds their behavior as rigid designators in counterfactual reasoning, or reasoning about alternative possibilities. Furthermore, the results in this paper help address one common objection to the view that logical truth and consequence obtain only relative to contexts. According to this objection, the view entails that logical consequence is not formal. (shrink)

In its first meaning, a logic is a collection of closely related artificial languages. There are certain languages called first‐order languages, and together they form first‐order logic. In the same spirit, there are several closely related languages called modal languages, and together they form modal logic. Likewise second‐order logic, deontic logic and so forth.

This is part I of a two-part essay introducing case-intensional first order logic, an easy-to-use, uniform, powerful, and useful combination of first-order logic with modal logic resulting from philosophical and technical modifications of Bressan’s General interpreted modal calculus. CIFOL starts with a set of cases; each expression has an extension in each case and an intension, which is the function from the cases to the respective case-relative extensions. Predication is intensional; identity (...) is extensional. Definite descriptions are context-independent terms, and lambda-predicates and -operators can be introduced without constraints. These logical resources allow one to define, within CIFOL, important properties of properties, viz., extensionality and absoluteness, Bressan’s chief innovation that allows tracing an individual across cases without recourse to any notion of “rigid designation” or “trans-world identity.” Thereby CIFOL abstains from incorporating any metaphysical principles into the quantificational machinery, unlike extant frameworks of quantified modal logic. We claim that this neutrality makes CIFOL a useful tool for discussing both metaphysical and scientific arguments involving modality and quantification, and we illustrate by discussing in diagrammatic detail a number of such arguments involving the extensional identification of individuals via absolute properties, essential properties, de re vs. de dicto, and the results of possible tests. (shrink)

This is part I of a two-part essay introducing case-intensional first order logic, an easy-to-use, uniform, powerful, and useful combination of first-order logic with modal logic resulting from philosophical and technical modifications of Bressan’s General interpreted modal calculus. CIFOL starts with a set of cases; each expression has an extension in each case and an intension, which is the function from the cases to the respective case-relative extensions. Predication is intensional; identity (...) is extensional. Definite descriptions are context-independent terms, and lambda-predicates and -operators can be introduced without constraints. These logical resources allow one to define, within CIFOL, important properties of properties, viz., extensionality and absoluteness, Bressan’s chief innovation that allows tracing an individual across cases without recourse to any notion of “rigid designation” or “trans-world identity.” Thereby CIFOL abstains from incorporating any metaphysical principles into the quantificational machinery, unlike extant frameworks of quantified modal logic. We claim that this neutrality makes CIFOL a useful tool for discussing both metaphysical and scientific arguments involving modality and quantification, and we illustrate by discussing in diagrammatic detail a number of such arguments involving the extensional identification of individuals via absolute properties, essential properties, de re vs. de dicto, and the results of possible tests. (shrink)

Closure spaces are generalizations of topological spaces, in which the Intersection of two open sets need not be open. The considered logic is related to closure spaces just as the standard logic S4 to topological ones. After describing basic properties of the logic we consider problems of representation of Lindenbaum algebras with some uncountable sets of infinite joins and meets, a notion of equality and a meaning of quantifiers. Results are extended onto the standard logic S4 (...) and they are valid also for some other standard modal logics. (shrink)

This chapter contains sections titled: Introduction Intensions Models About Quantification Truth in Models Equality Rigidity De Re/De Dicto Partial Designation Designation and Existence Definite Descriptions What Next?

This paper follows Part I of our essay on case-intensional first-order logic ). We introduce a framework of branching histories to take account of indeterminism. Our system BH-CIFOL adds structure to the cases, which in Part I formed just a set: a case in BH-CIFOL is a moment/history pair, specifying both an element of a partial ordering of moments and one of the total courses of events that that moment is part of. This framework allows us to (...) define the familiar Ockhamist temporal/modal connectives, most notably for past, future, and settledness. The novelty of our framework becomes visible in our discussion of substances in branching histories, i.e., in its first-order part. That discussion shows how the basic idea of tracing an individual thing from case to case via an absolute property is applicable in a branching histories framework. We stress the importance of keeping apart extensionality and moment-definiteness, and give a formal account of how the specification of natural sortals and natural qualities turns out to be a coordination task in BH-CIFOL. We also provide a detailed answer to Lewis’s well-known argument against branching histories, exposing the fallacy in that argument. (shrink)

Edward Nieznanski developed in 2007 and 2008 two different systems in formal logic which deal with the problem of evil. Particularly, his aim is to refute a version of the logical problem of evil associated with a form of religious determinism. In this paper, we revisit his first system to give a more suitable form to it, reformulating it in first-order modal logic. The new resulting system, called N1, has much of the original basic (...) structure, and many axioms, definitions, and theorems still remain; however, some new results are obtained. If the conclusions attained are correct and true, then N1 solves the problem of evil through the refutation of a version of religious determinism, showing that the attributes of God in Classical Theism, namely, those of omniscience, omnipotence, infallibility, and omnibenevolence, when adequately formalized, are consistent with the existence of evil in the world. We consider that N1 is a good example of how formal systems can be applied in solving interesting philosophical issues, particularly in Philosophy of Religion and Analytic Theology, establishing bridges between such disciplines. (shrink)

We prove that the positive fragment of first-order intuitionistic logic in the language with two individual variables and a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable. This holds true regardless of whether we consider semantics with expanding or constant domains. We then generalise this result to intervals \ and \, where QKC is the logic of the weak law of the excluded middle and QBL and QFL are first-order counterparts (...) of Visser’s basic and formal logics, respectively. We also show that, for most “natural” first-order modal logics, the two-variable fragment with a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable, regardless of whether we consider semantics with expanding or constant domains. These include all sublogics of QKTB, QGL, and QGrz—among them, QK, QT, QKB, QD, QK4, and QS4. (shrink)

The paper considers the set ML 1 of first-order polymodal formulas the modal operators in which can be applied to subformulas of at most one free variable. Using a mosaic technique, we prove a general satisfiability criterion for formulas in ML 1 , which reduces the modal satisfiability to the classical one. The criterion is then used to single out a number of new, in a sense optimal, decidable fragments of various modal predicate logics.

The paper considers the set $\mathscr{M}\mathscr{L}_1$ of first-order polymodal formulas the modal operators in which can be applied to subformulas of at most one free variable. Using a mosaic technique, we prove a general satisfiability criterion for formulas in $\mathscr{M}\mathscr{L}_1$, which reduces the modal satisfiability to the classical one. The criterion is then used to single out a number of new, in a sense optimal, decidable fragments of various modal predicate logics.

We prove that the two-variable fragment of first-order intuitionistic logic is undecidable, even without constants and equality. We also show that the two-variable fragment of a quantified modal logic L with expanding first-order domains is undecidable whenever there is a Kripke frame for L with a point having infinitely many successors (such are, in particular, the first-order extensions of practically all standard modal logics like K, K4, GL, S4, S5, K4.1, (...) S4.2, GL.3, etc.). For many quantified modal logics, including those in the standard nomenclature above, even the monadic two-variable fragments turn out to be undecidable. (shrink)

The first amounts, roughly, to "It is necessarily the case that any President of the U.S. is a citizen of the U.S." But the second says, "the person who in fact is the President of the U.S, has the property of necessarily being a citizen of the U.S," Thus, while (2) is clearly true, it would be reasonable to consider (3) false.

Many authors have noted that there are types of English modal sentences cannot be formalized in the language of basic first-order modal logic. Some widely discussed examples include “There could have been things other than there actually are” and “Everyone who is actually rich could have been poor.” In response to this lack of expressive power, many authors have discussed extensions of first-order modal logic with two-dimensional operators. But claims about the (...) relative expressive power of these extensions are often justified only by example rather than by rigorous proof. In this paper, we provide proofs of many of these claims and present a more complete picture of the expressive landscape for such languages. (shrink)

We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF2, which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. The translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. It is practically relevant because it makes it possible to use a decision procedure for the guarded fragment in (...) order to decide regular grammar logics with converse. The class of regular grammar logics includes numerous logics from various application domains. A consequence of the translation is that the general satisfiability problem for every regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Other logics that can be translated into GF2 include nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF2 without extra machinery such as fixed-point operators. (shrink)

In the article we study the existence predicate \(\varepsilon\) in the context of semantics for first-order modal logic. For a formula \(\varphi\) we define \(\varphi^{\varepsilon}\) - the so called existence relativization. We point to a gap in the work of Fitting and Mendelsohn concerning the relationship between the truth of \(\varphi\) and \(\varphi^{\varepsilon}\) in classes of varying- and constant-domain models. We introduce operations on models which allow us to fill the gap and provide a more general (...) perspective on the issue. As a result we obtain a series of theorems describing the logical connection between the notion of truth of a formula with the existence predicate in constant-domain models and the notion of truth of a formula without the existence predicate in varying-domain models. (shrink)

First - order modal logic is very much under current development, with many different semantics proposed. The use of rigid objects goes back to Saul Kripke. More recently, several semantics based on counterparts have been examined, in a development that goes back to David Lewis. There is yet another line of research, using intensional objects, that traces back to Richard Montague. I have been involved with this line of development for some time. In the present paper, (...) I briefly sketch several of the approaches to first - order modal logic. Then I present one that I call FOIL in the Montague tradition that, I believe, is both expressive and natural. I briefly discuss in what sense it can be made to encompass the other approaches. Finally, I provide tableau rules to go with the FOIL semantics. (shrink)

In this paper we investigate first order common knowledge logics; i.e., modal epistemic logics based on first order logic with common knowledge operators. It is shown that even rather weak fragments of first order common knowledge logics are not recursively axiomatizable. This applies, for example, to fragments which allow to reason about names only; that is to say, fragments the first order part of which is based on constant symbols and (...) the equality symbol only. Then formal properties of "quantifying into" epistemic contexts are investigated. The results are illustrated by means of epistemic representations of Nash Equilibria for finite games with mixed strategies. (shrink)

We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF2, which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. The translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. It is practically relevant because it makes it possible to use a decision procedure for the guarded fragment in (...) order to decide regular grammar logics with converse. The class of regular grammar logics includes numerous logics from various application domains. A consequence of the translation is that the general satisfiability problem for every regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Other logics that can be translated into GF2 include nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF2 without extra machinery such as fixed-point operators. (shrink)

A well established technique toward developing the proof theory of a Hilbert-style modal logic is to introduce a Gentzen-style equivalent (a Gentzenisation), then develop the proof theory of the latter, and finally transfer the metatheoretical results to the original logic (e.g., [1, 6, 8, 18, 10, 12]). In the first-order modal case, on one hand we know that the Gentzenisation of the straightforward first-order extension of GL, the logic QGL, admits no (...) cut elimination (if the rule is included as primitive; or, if not included, then the rule is not admissible [1]). On the other hand the (cut-free) Gentzenisations of the first-order modal logics M3 and ML3 of [10, 12] do have cut as an admissible rule. The syntactic cut admissibility proof given in [18] for the Gentzenisation of the propositional provability logic GL is extremely complex, and it was the basis of the proofs of cut admissibility of the Gentzenisations of M3 and ML3, where the presence of quantifiers and quantifier rules added to the complexity and length of the proof. A recent proof of cut admissibility in a cut-free Gentzenisation of GL is given in [5] and is quite short and easy to read. We adapt it here to revisit the proofs for the cases of M3 and ML3, resulting to similarly short and easy to read proofs, only slightly complicated by the presence of quantification and its relevant rules. (shrink)