Online research in philosophy

We define a propositionally quantified intuitionistic logic Hπ + by a natural extension of Kripke's semantics for propositional intutionistic logic. We then show that Hπ+ is recursively isomorphic to full second order classical logic. Hπ+ is the intuitionistic analogue of the modal systems S5π +, S4π +, S4.2π +, K4π +, Tπ +, Kπ + and Bπ +, studied by Fine.

Classical first-order logic can be extended in two different ways to serve as a foundation for mathematics: introduce higher orders, type theory, or introduce sets. As it happens, both approaches have natural analogs for quantified modal logics, both approaches date from the 1960’s, one is not very well-known, and the other is well-known as something else. I will present the basic semantic ideas of both higher order intensional logic, and intensional set theory. Before doing so, I’ll quickly sketch some necessary background material from quantified modal logic. Except for standard material concerning propositional modal logics, the paper is essentially self-contained.

This is a free book, 165 pages. It is for anyone who has had a solid introductory logic course and wants more. Topics covered include soundness and completeness for first-order logic, Tarski's theorem on the undefinability of truth, Gödel's incompleteness theorems, the undecidability of first-order logic, a smattering of second-order logic, and modal logic (both propositional and quantificational). I wrote it for use in my own course, because I thought I could present the most important results and concepts more clearly than the available textbooks.

An interpolation theorem holds for many standard modal logics, but first order S5 is a prominent example of a logic for which it fails. In this paper it is shown that a first order S5 interpolation theorem can be proved provided the logic is extended to contain propositional quantifiers. A proper statement of the result involves some subtleties, but this is the essence of it.

Propositional modal logic is a standard tool in many disciplines, but first-order modal logic is not. There are several reasons for this, including multiplicity of versions and inadequate syntax. In this paper we sketch a syntax and semantics for a natural, well-behaved version of first-order modal logic, and show it copes easily with several familiar difficulties. And we provide tableau proof rules to go with the semantics, rules that are, at least in principle, automatable.

Modal logic is an enormous subject, and so any discussion of it must limit itself according to some set of principles. Modal logic is of interest to mathematicians, philosophers, linguists and computer scientists, for somewhat different reasons. Typically a philosopher may be interested in capturing some aspect of necessary truth, while a mathematician may be interested in characterizing a class of models having special structural features. For a computer scientist there is another criterion that is not as relevant for the other disciplines: a logic should be ‘well-behaved.’ This is, admittedly, a vague notion, but some things are clear enough. A logic that can be axiomatized is better than one that can’t be; a logic with a simple axiomatization is better yet; and a logic with a reasonably implementable proof procedure is best of all. My current interests are largely centered in computer science, and so I will only discuss well-behaved modal logics. My talk is organized into three sections, depending on the expressiveness of the modal logics considered: propositional; first-order with rigid designators; first-order with non-rigid designators. Even limited as I have said, the subject is a big one, and this talk can be no more than an outline. For a general discussion of propositional modal logic see [2]; for this and first-order modal logic see [9], [10] and [8]; for tableau systems in modal logic see [6].

As McKinsey and Tarksi showed, the Stone representation theorem for Boolean algebras extends to algebras with operators to give topological semantics for (classical) propositional modal logic, in which the "necessity" operation is modeled by taking the interior of an arbitrary subset of a topological space. in this paper the topological interpretation is extended in a natural way to arbitrary theories of full first-order logic. The resulting system of S4 first-order modal logic is complete with respect to such topological semantics.

One can add the machinery of relation symbols and terms to a propositional modal logic without adding quantifiers. Ordinarily this is no extension beyond the propositional. But if terms are allowed to be non-rigid, a scoping mechanism (usually written using lambda abstraction) must also be introduced to avoid ambiguity. Since quantifiers are not present, this is not really a first-order logic, but it is not exactly propositional either. For propositional logics such as K, T and D, adding such machinery produces a decidable logic, but adding it to S5 produces an undecidable one. Further, if an equality symbol is in the language, and interpreted by the equality relation, logics from K4 to S5 yield undecidable versions. (Thus transitivity is the villain here.) The proof of undecidability consists in showing that classical first-order logic can be embedded.

We consider second-order propositional modal logic (SOPML), an extension of the basic modal language with propositional quantifiers introduced by Kit Fine in 1970. We determine the precise expressive power of SOPML by giving analogues of the Van Benthem–Rosen theorem and the Goldblatt Thomason theorem. Furthermore, we show that the basic modal language is the bisimulation invariant fragment of SOPML, and we characterize the bounded fragment of first-order logic as being the intersection of first-order logic and SOPML.

We consider second-order propositional modal logic (SOPML), an extension of the basic modal language with propositional quantifiers introduced by Kit Fine in 1970. We determine the precise expressive power of SOPML by giving analogues of the Van Benthem–Rosen theorem and the Goldblatt Thomason theorem. Furthermore, we show that the basic modal language is the bisimulation invariant fragment of SOPML, and we characterize the bounded fragment of first-order logic as being the intersection of first-order logic and SOPML.