Kurt Godel was the most outstanding logician of the twentieth century, famous for his work on the completeness of logic, the incompleteness of number theory, and the consistency of the axiom of choice and the continuum hypothesis. He is also noted for his work on constructivity, the decision problem, and the foundations of computation theory, as well as for the strong individuality of his writings on the philosophy of mathematics. Less well-known is his discovery of unusual cosmological models for Einstein's (...) equations, permitting "time-travel" into the past. This second volume of a comprehensive edition of Godel's works collects together all his publications from 1938 to 1974. Together with Volume I (Publications 1929-1936), it makes available for the first time in a single source all of his previously published work. Continuing the format established in the earlier volume, the present text includes introductory notes that provide extensive explanatory and historical commentary on each of the papers, a facing English translation of the one German original, and a complete bibliography. Succeeding volumes are to contain unpublished manuscripts, lectures, correspondence, and extracts from the notebooks. Collected Works is designed to be accessible and useful to as wide an audience as possible without sacrificing scientific or historical accuracy. The only complete edition available in English, it will be an essential part of the working library of professionals and students in logic, mathematics, philosophy, history of science, and computer science. These volumes will also interest scientists and all others who wish to be acquainted with one of the great minds of the twentieth century. (shrink)

We address the old question whether a logical understanding of Quantum Mechanics requires abandoning some of the principles of classical logic. Against Putnam and others (Among whom we may count or not E. W. Beth, depending on how we interpret some of his statements), our answer is a clear "no". Philosophically, our argument is based on combining a formal semantic approach, in the spirit of E. W. Beth's proposal of applying Tarski's semantical methods to the analysis of physical theories, with (...) an empirical-experimental approach to Logic, as advocated by both Beth and Putnam, but understood by us in the view of the operationalrealistic tradition of Jauch and Piron, i. e. as an investigation of "the logic of yes-no experiments" (or "questions"). Technically, we use the recently-developed setting of Quantum Dynamic Logic (Baltag and Smets 2005, 2008) to make explicit the operational meaning of quantum-mechanical concepts in our formal semantics. Based on our recent results (Baltag and Smets 2005), we show that the correct interpretation of quantum-logical connectives is dynamical, rather than purely propositional. We conclude that there is no contradiction between classical logic and (our dynamic reinterpretation of) quantum logic. Moreover, we argue that the Dynamic-Logical perspective leads to a better and deeper understanding of the "non-classicality" of quantum behavior than any perspective based on static Propositional Logic. (shrink)

In spite of a powerful tradition, more than two thousand years old, that in a valid argument the premises must be relevant to the conclusion, twentieth-century logicians neglected the concept of relevance until the publication of Volume I of this monumental work. Since that time relevance logic has achieved an important place in the field of philosophy: Volume II of Entailment brings to a conclusion a powerful and authoritative presentation of the subject by most of the top people working in (...) the area. Originally the aim of Volume II was simply to cover certain topics not treated in the first volume--quantification, for example--or to extend the coverage of certain topics, such as semantics. However, because of the technical progress that has occurred since the publication of the first volume, Volume II now includes other material. The book contains the work of Alasdair Urquhart, who has shown that the principal sentential systems of relevance logic are undecidable, and of Kit Fine, who has demonstrated that, although the first-order systems are incomplete with respect to the conjectured constant domain semantics, they are still complete with respect to a semantics based on "arbitrary objects." Also presented is important work by the other contributing authors, who are Daniel Cohen, Steven Giambrone, Dorothy L. Grover, Anil Gupta, Glen Helman, Errol P. Martin, Michael A. McRobbie, and Stuart Shapiro. Robert G. Wolf's bibliography of 3000 items is a valuable addition to the volume. Originally published in 1992. The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These editions preserve the original texts of these important books while presenting them in durable paperback and hardcover editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905. (shrink)

We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a finite (...) model. Moreover, Mortimer showed that every satisfiable FO 2 -sentence has a model whose size is at most doubly exponential in the size of the sentence. In this paper, we improve Mortimer's bound by one exponential and show that every satisfiable FO 2 -sentence has a model whose size is at most exponential in the size of the sentence. As a consequence, we establish that the satisfiability problem for FO 2 is NEXPTIME-complete. (shrink)

In the present paper we study systematically several consequence relations on the usual language of propositional intuitionistic logic that can be defined semantically by using Kripke frames and the same defining truth conditions for the connectives as in intuitionistic logic but without imposing some of the conditions on the Kripke frames that are required in the intuitionistic case. The logics so obtained are called subintuitionistic logics in the literature. We depart from the perspective of considering a logic just as a (...) set of theorems and also depart from the perspective taken by Restall in that we consider standard Kripke models instead of models with a base point. We study the relations between subintuitionistic logics and modal logics given by the translation considered by Došen. Moreover, we classify the logics obtained according to the hierarchy considered inAlgebraic Logic. (shrink)

Algebraic work [9] shows that the deep theory of possible world semantics is available in the more general setting of substructural logics, at least in an algebraic guise. The question is whether it is also available in a relational form.This article seeks to set the stage for answering this question. Guided by the algebraic theory, but purely relationally we introduce a new type of frames. These structures generalize Kripke structures but are two-sorted, containing both worlds and co-worlds. These latter points (...) may be viewed as modelling irreducible increases in information where worlds model irreducible decreases in information. Based on these structures, a purely model theoretic and uniform account of completeness for the implication-fusion fragment of various substructural logics is given. Completeness is obtained via a generalization of the standard canonical model construction in combination with correspondence results. (shrink)

In the pioneering article and two papers, written jointly with McKinsey, Tarski developed the so-called algebraic and topological frameworks for the Intuitionistic Logic and the Lewis modal system. In this paper, we present an outline of modern systems with a topological tinge. We consider topological interpretation of basic systems GL and G of the provability logic in terms of the Cantor derivative and the Hausdorff residue.

This paper is a survey of results concerning embeddings of intuitionistic propositional logic and its extensions into various classical modal systems.

Once the Kripke semantics for normal modal logics were introduced, a whole family of modal logics other than the Lewis systems S1 to S5 were discovered. These logics were obtained by changing the semantics in natural ways. The same can be said of the Kripke-style semantics for relevant logics: a whole range of logics other than the standard systems R, E and T were unearthed once a semantics was given (cf. Priest and Sylvan [6], Restall [7], and Routley et al. (...) [8]). In a similar way, weakening the structural rules of the Gentzen formulation of classical logic gives rise to other ‘substructural’ logics such as linear logic (as in Girard [4]). This process of ‘strategic weakening’ is becoming popular today, with the discovery of applications of these logics to areas such as linguistics and the theory of computation (cf. van Benthem [1]). Until now no-one has (to my knowledge) examined what the process of weakening does to the Kripke-style semantics of intuitionistic logic. This paper remedies the deficiency, introducing the family of subintuitionistic logics. These systems have some appealing features. Unlike other substructural logics such as linear logic (which lack distribution of extensional disjunction over conjunction) they have a very natural Kripke-style worlds semantics. Also, the difficulties with regard to modelling quantification in these systems may be able to shed some light on the difficulties in naturally modelling quantification in relevant logics, as it must be admitted that the semantics currently available for quantified relevant logics are rather baroque (cf. Fine [3]). But most importantly, delving in the undergrowth of logics such as intuitionistic logic gives us a ‘feel’ for how such systems are put together, and what job is being done by each aspect of the modelling conditions in.. (shrink)

In this paper we introduce canonical extensions of partially ordered sets and monotone maps and a corresponding discrete duality. We then use these to give a uniform treatment of completeness of relational semantics for various substructural logics with implication as the residual(s) of fusion.

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

In this paper, we will develop an algebraic study of substructural propositional logics over FLew, i.e. the logic which is obtained from intuitionistic logics by eliminating the contraction rule. Our main technical tool is to use residuated lattices as the algebraic semantics for them. This enables us to study different kinds of nonclassical logics, including intermediate logics, BCK-logics, Lukasiewicz’s many-valued logics and fuzzy logics, within a uniform framework.

This article presents an approach to the semantics of non-distributive propositional logics that is based on a lattice representation theorem that delivers a canonical extension of the lattice. Our approach supports both a plain Kripke-style semantics and, by restriction, a general frame semantics. Unlike the framework of generalized Kripke frames, the semantic approach presented in this article is suitable for modeling applied logics, as it respects the intended interpretation of the logical operators. This is made possible by restricting admissible interpretations.

In this paper, we establish the first-order definability of sequents with consistent variable occurrence on bi-approximation semantics by means of the Sahlqvist–van Benthem algorithm. Then together with the canonicity results in Suzuki (2011), this allows us to establish a Sahlqvist theorem for substructural logic. Our result is not limited to substructural logic but is also easily applicable to other lattice-based logics.

Substructural logics are logics obtained from a sequent formulation of intuitionistic or classical logic by rejecting some structural rules. The substructural logics considered here are linear logic, relevant logic and BCK logic. It is proved that first-order variants of these logics with an intuitionistic negation can be embedded by modal translations into S4-type extensions of these logics with a classical, involutive, negation. Related embeddings via translations like the double-negation translation are also considered. Embeddings into analogues of S4 are obtained with (...) the help of cut elimination for sequent formulations of our substructural logics and their modal extensions. These results are proved for systems with equality too. (shrink)

This first textbook on formal concept analysis gives a systematic presentation of the mathematical foundations and their relations to applications in computer science, especially in data analysis and knowledge processing. Above all, it presents graphical methods for representing conceptual systems that have proved themselves in communicating knowledge. The mathematical foundations are treated thoroughly and are illuminated by means of numerous examples, making the basic theory readily accessible in compact form.

ABSTRACT A spatial logic is a modal logic of which the models are the mathematical models of space. Successively considering the mathematical models of space that are the incidence geometry and the projective geometry, we will successively establish the language, the semantical basis, the axiomatical presentation, the proof of the decidability and the proof of the completeness of INC, the modal multilogic of incidence geometry, and PRO, the modal multilogic of projective geometry.

ABSTRACTCorrespondence and Shalqvist theories for Modal Logics rely on the simple observation that a relational structure is at the same time the basis for a model of modal logic and for a model of first-order logic with a binary predicate for the accessibility relation. If the underlying set of the frame is split into two components,, and, then frames are at the same time the basis for models of non-distributive lattice logic and of two-sorted, residuated modal logic. This suggests that (...) a reduction of the first to the latter may be possible, encoding Positive Lattice Logic as a fragment of Two-Sorted, Residuated Modal Logic. The reduction is analogous to the well-known Gödel-McKinsey-Tarski translation of Intuitionistic Logic into the S4 system of normal modal logic. In this article, we carry out this reduction in detail and we derive some properties of PLL from corresponding properties of First-Order Logic. The reduction we present is extendible to the case of lattices with operators, making use of recent results by this author on the relational representation of normal lattice expansions. (shrink)

We introduce the bimodal logic , which is the extension of Bennett’s bimodal logic by Grzegorczyk’s axiom □→p)→p and show that the lattice of normal extensions of the intuitionistic modal logic WS5 is isomorphic to the lattice of normal extensions of , thus generalizing the Blok–Esakia theorem. We also introduce the intuitionistic modal logic WS5.C, which is the extension of WS5 by the axiom →, and the bimodal logic , which is the extension of Shehtman’s bimodal logic by Grzegorczyk’s axiom, (...) and show that the lattice of normal extensions of WS5.C is isomorphic to the lattice of normal extensions of. (shrink)

We present dualities for implicative and residuated lattices. In combination with our recent article on a discrete duality for lattices with unary modal operators, the present article contributes in filling in a gap in the development of Orłowska and Rewitzky’s research program of discrete dualities, which seemed to have stumbled on the case of non-distributive lattices with operators. We discuss dualities via truth, which are essential in relating the non-distributive logic of two-sorted frames with their sorted, residuated modal logic, as (...) well as full Stone duality for residuated lattices. Our results have immediate applications to the semantics of related substructural logical calculi. (shrink)

We identify the computational complexity of the satisfiability problem for FO 2, the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a finite model. (...) Moreover, Mortimer showed that every satisfiable FO 2 -sentence has a model whose size is at most doubly exponential in the size of the sentence. In this paper, we improve Mortimer's bound by one exponential and show that every satisfiable FO 2 -sentence has a model whose size is at most exponential in the size of the sentence. As a consequence, we establish that the satisfiability problem for FO 2 is NEXPTIME-complete. (shrink)

The question of which is the logic that underlies quantum physics does not have an absolute answer, but only in relation to a conventional choice of interpretation . Most of the interpretations that have been offered work within the framework of classical logic. In contrast to these, we examine the corpuscular interpretation which is assumed in the application of non-distributive logic . The experiment in which single photons pass through a Mach-Zehnder interferometer is examined, indicating the difficulty of employing a (...) realist corpuscular interpretation in this context. One way to save this interpretation would be to use non-distributive logic to analyze the experiment, but this is not satisfactory . However, the use of an alethic modal logic solves the problem, blocking the argument that put the aforementioned corpuscular interpretation into difficulty. In the discussion of the conceptual problems involved, we suggest that a stochastic corpuscular interpretation is well adapted to this logical description. The project of extending this modal logical approach to other experiments in quantum physics, and of providing a rigorous logical treatment, is left open. (shrink)