In this paper I shall present some of the results I have obtained on modal theories which contain quantifiers for propositions. The paper is in two parts: in the first part I consider theories whose non-quantificational part is S5; in the second part I consider theories whose non-quantificational part is weaker than or not contained in S5. Unless otherwise stated, each theory has the same language L. This consists of a countable set V of propositional variables pl, pa, ... , (...) the operators v (or), ~ (not) and □ (necessarily), the universal quantifier (p), p a propositional variable, and brackets ( and ). The formulas of L are then defined in the usual way. (shrink)

Dependence is a common phenomenon, wherever one looks: ecological systems, astronomy, human history, stock markets - but what is the logic of dependence? This book is the first to carry out a systematic logical study of this important concept, giving on the way a precise mathematical treatment of Hintikka’s independence friendly logic. Dependence logic adds the concept of dependence to first order logic. Here the syntax and semantics of dependence logic are studied, dependence logic is given an alternative game theoretic (...) semantics, and results about its complexity are proven. This is a graduate textbook suitable for a special course in logic in mathematics, philosophy and computer science departments, and contains over 200 exercises, many of which have a full solution at the end of the book. It is also accessible to readers, with a basic knowledge of logic, interested in new phenomena in logic. (shrink)

This modern, advanced textbook reviews modal logic, a field which caught the attention of computer scientists in the late 1970's.

The book presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logics that are important in this context include fixed-point logics, transitive closure logics, and also certain infinitary languages; their model theory is studied in full detail. Other topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems. The book is written in such a way (...) that the respective parts on model theory and descriptive complexity theory may be read independently. This second edition is a thoroughly revised and enlarged version of the original text. (shrink)

This book, written by one of philosophy's pre-eminent logicians, argues that many of the basic assumptions common to logic, philosophy of mathematics and metaphysics are in need of change. It is therefore a book of critical importance to logical theory. Jaakko Hintikka proposes a new basic first-order logic and uses it to explore the foundations of mathematics. This new logic enables logicians to express on the first-order level such concepts as equicardinality, infinity, and truth in the same language. The famous (...) impossibility results by Gödel and Tarski that have dominated the field for the last sixty years turn out to be much less significant than has been thought. All of ordinary mathematics can in principle be done on this first-order level, thus dispensing with the existence of sets and other higher-order entities. (shrink)

We shall introduce in this paper a language whose formulas will be interpreted by games of imperfect information. Such games will be defined in the same way as the games for first-order formulas except that the players do not have complete information of the earlier course of the game. Some simple logical properties of these games will be stated together with the relation of such games of imperfect information to higher-order logic. Finally, a set of applications will be outlined.

We describe a logic which is the same as first-order logic except that it allows control over the information that passes down from formulas to subformulas. For example the logic is adequate to express branching quantifiers. We describe a compositional semantics for this logic; in particular this gives a compositional meaning to formulas of the 'information-friendly' language of Hintikka and Sandu. For first-order formulas the semantics reduces to Tarski's semantics for first-order logic. We prove that two formulas have the same (...) interpretation in all structures if and only if replacing an occurrence of one by an occurrence of the other in a sentence never alters the truth-value of the sentence in any structure. (shrink)

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.

This book offers a comprehensive treatment of the classical decision problem of mathematical logic and of the role of the classical decision problem in modern computer science. The text presents a revealing analysis of the natural order of decidable and undecidable cases and includes a number of simple proofs and exercises.

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 introduce several senses of the principle ofcompositionality. We illustrate the difference between them with thehelp of some recent results obtained by Cameron and Hodges oncompositional semantics for languages of imperfect information.