The problem is addressed of establishing the satisfiability of prenex formulas involving a single universal quantifier, in diversified axiomatic set theories. A rather general decision method for solving this problem is illustrated through the treatment of membership theories of increasing strength, ending with a subtheory of Zermelo-Fraenkel which is already complete with respect to the ∀*∀ class of sentences. NP-hardness and NP-completeness results concerning the problems under study are achieved and a technique for restricting the universal quantifier is presented.

We study the decidability problem for metric and layered temporal logics. The logics we consider are suitable to model time granularity in various contexts, and they allow one to build granular temporal models by referring to the "natural scale" in any component of the model and by properly constraining the interactions between differently-grained components. A monadic second-order language combining operators such as temporal contextualization and projection, together with the usual displacement operator of metric temporal logics, is considered, and the theory (...) of finitely-layered metric temporal structures is shown to be decidable. (shrink)

The axiom of infinity can be expressed by stating the existence of sets satisfying a formula which involves restricted universal quantifiers only, even if the axiom of foundation is not assumed.

The still unsettled decision problem for the restricted purely universal formulae 0-formulae) of the first order set-theoretic language based over =, ∈ is discussed in relation with the adoption or rejection of the axiom of foundation. Assuming the axiom of foundation, the related finite set-satisfiability problem for the very significant subclass of the 0-formulae consisting of the formulae involving only nested variables of level 1 is proved to be semidecidable on the ground of a reflection property over the hereditarily finite (...) sets, and various extensions of this result are obtained. When variables are restricted to range only over sets, in universes with infinitely many urelements the set-satisfiability problem is shown to be solvable provided the axiom of foundation is assumed; if it is not, then the decidability of a related derivability problem still holds. That, in turn, suggests the alternative adoption of an antifoundation axiom under which the set-satisfiability problem is also solvable . Turning to set theory without urelements, assuming a form of Boffa's antifoundation axiom, the complement of the set-satisfiability problem for the full class of Δ0-formulae is shown to be semidecidable; a result that is known not to hold, for the set-satisfiability problem itself, even for a very restricted subclass of the Δ0-formulae. (shrink)

Being able to state the principles which lie deepest in the foundations of mathematics by sentences in three variables is crucially important for a satisfactory equational rendering of set theories along the lines proposed by Alfred Tarski and Steven Givant in their monograph of 1987. The main achievement of this paper is the proof that the 'kernel' set theory whose postulates are extensionality. (E), and single-element adjunction and removal. (W) and (L), cannot be axiomatized by means of three-variable sentences. This (...) highlights a sharp edge to be crossed in order to attain an 'algebraization' of Set Theory. Indeed, one easily shows that the theory which results from the said kernel by addition of the null set axiom, (N), is in its entirety expressible in three variables. (shrink)

In this paper, we generalize the set-theoretic translation method for polymodal logic introduced in [11] to extended modal logics. Instead of devising an ad-hoc translation for each logic, we develop a general framework within which a number of extended modal logics can be dealt with. We first extend the basic set-theoretic translation method to weak monadic second-order logic through a suitable change in the underlying set theory that connects up in interesting ways with constructibility; then, we show how to tailor (...) such a translation to work with specific cases of extended modal logics. (shrink)

As is well-known, the Bernays-Schönfinkel-Ramsey class of all prenex ∃*∀* -sentences which are valid in classical first-order logic is decidable. This paper paves the way to an analogous result which the authors deem to hold when the only available predicate symbols are ∈ and =, no constants or function symbols are present, and one moves inside a (rather generic) Set Theory whose axioms yield the well-foundedness of membership and the existence of infinite sets. Here semi-decidability of the satisfiability problem for (...) the BSR class is proved by following a purely semantic approach, the remaining part of the decidability result being postponed to a forthcoming paper. (shrink)

This book presents a set of historical recollections on the work of Martin Davis and his role in advancing our understanding of the connections between logic, computing, and unsolvability. The individual contributions touch on most of the core aspects of Davis’ work and set it in a contemporary context. They analyse, discuss and develop many of the ideas and concepts that Davis put forward, including such issues as contemporary satisfiability solvers, essential unification, quantum computing and generalisations of Hilbert’s tenth problem. (...) The book starts out with a scientific autobiography by Davis, and ends with his responses to comments included in the contributions. In addition, it includes two previously unpublished original historical papers in which Davis and Putnam investigate the decidable and the undecidable side of Logic, as well as a full bibliography of Davis’ work. As a whole, this book shows how Davis’ scientific work lies at the intersection of computability, theoretical computer science, foundations of mathematics, and philosophy, and draws its unifying vision from his deep involvement in Logic. (shrink)

As proved recently, the satisfaction problem for all prenex formulae in the set-theoretic Bernays-Shönfinkel-Ramsey class is semi-decidable over von Neumann's cumulative hierarchy. Here that semi-decidability result is strengthened into a decidability result for the same collection of formulae.

In this paper, we generalize the set-theoretic translation method for poly-modal logic introduced in [11] to extended modal logics. Instead of devising an ad-hoc translation for each logic, we develop a general framework within which a number of extended modal logics can be dealt with. We first extend the basic set-theoretic translation method to weak monadic second-order logic through a suitable change in the underlying set theory that connects up in interesting ways with constructibility; then, we show how to tailor (...) such a translation to work with specific cases of extended modal logics. (shrink)