If the Visser rules are admissible for an intermediate logic, they form a basis for the admissible rules of the logic. How to characterize the admissible rules of intermediate logics for which not all of the Visser rules are admissible is not known. In this paper we give a brief overview of results on admissible rules in the context of intermediate logics. We apply these results to some well-known intermediate logics. We provide natural examples of logics for which the Visser (...) rule are derivable, admissible but nonderivable, or not admissible. (shrink)

The axiomatic presentation of modal systems and the standard formulations of natural deduction and sequent calculus for modal logic are reviewed, together with the difficulties that emerge with these approaches. Generalizations of standard proof systems are then presented. These include, among others, display calculi, hypersequents, and labelled systems, with the latter surveyed from a closer perspective.

A family of prepositional logics is considered to be intermediate between the intuitionistic and classical ones. The generalized interpolation property is defined and proved is the following.Theorem on interpolation. For every intermediate logic L the following statements are equivalent:(i) Craig's interpolation theorem holds in L, (ii) L possesses the generalized interpolation property, (iii) Robinson's consistency statement is true in L.

Structural proof theory is a branch of logic that studies the general structure and properties of logical and mathematical proofs. This book is both a concise introduction to the central results and methods of structural proof theory, and a work of research that will be of interest to specialists. The book is designed to be used by students of philosophy, mathematics and computer science. The book contains a wealth of results on proof-theoretical systems, including extensions of such systems from logic (...) to mathematics, and on the connection between the two main forms of structural proof theory - natural deduction and sequent calculus. The authors emphasize the computational content of logical results. A special feature of the volume is a computerized system for developing proofs interactively, downloadable from the web and regularly updated. (shrink)

Intuitionistic logic is presented here as part of familiar classical logic which allows mechanical extraction of programs from proofs. to make the material more accessible, basic techniques are presented first for propositional logic; Part II contains extensions to predicate logic. This material provides an introduction and a safe background for reading research literature in logic and computer science as well as advanced monographs. Readers are assumed to be familiar with basic notions of first order logic. One device for making this (...) book short was inventing new proofs of several theorems. The presentation is based on natural deduction. The topics include programming interpretation of intuitionistic logic by simply typed lambda-calculus (Curry-Howard isomorphism), negative translation of classical into intuitionistic logic, normalization of natural deductions, applications to category theory, Kripke models, algebraic and topological semantics, proof-search methods, interpolation theorem. The text developed from materal for several courses taught at Stanford University in 1992-1999. (shrink)

For a novice this book is a mathematically-oriented introduction to modal logic, the discipline within mathematical logic studying mathematical models of reasoning which involve various kinds of modal operators. It starts with very fundamental concepts and gradually proceeds to the front line of current research, introducing in full details the modern semantic and algebraic apparatus and covering practically all classical results in the field. It contains both numerous exercises and open problems, and presupposes only minimal knowledge in mathematics. A specialist (...) can use the book as a source of references. Results and methods of many directions in propositional modal logic, from completeness and duality to algorithmic problems, are collected and systematically presented in one volume. (shrink)

Modern modal logic originated as a branch of philosophical logic in which the concepts of necessity and possibility were investigated by means of a pair of dual operators that are added to a propositional or first-order language. The field owes much of its flavor and success to the introduction in the 1950s of the “possible-worlds” semantics in which the modal operators are interpreted via some “accessibility relation” connecting possible worlds. In subsequent years, modal logic has received attention as an attractive (...) approach towards formalizing such diverse notions as time, knowledge, or action. Nowadays, modal logics are applied in various disciplines, ranging from economics to linguistics and computer science. Consequently, there is by now a large variety of modal languages, with an even greater wealth of interpretations. For instance, many applications require a poly-modal framework consisting of a language with a family of modal operators and a semantics in which the corresponding accessibility relations are connected somehow. (shrink)

The subject of Labelled Non-Classical Logics is the development and investigation of a framework for the modular and uniform presentation and implementation of non-classical logics, in particular modal and relevance logics. Logics are presented as labelled deduction systems, which are proved to be sound and complete with respect to the corresponding Kripke-style semantics. We investigate the proof theory of our systems, and show them to possess structural properties such as normalization and the subformula property, which we exploit not only to (...) establish advantages and limitations of our approach with respect to related ones, but also to give, by means of a substructural analysis, a new proof-theoretic method for investigating decidability and complexity of (some of) the logics we consider. All of our deduction systems have been implemented in the generic theorem prover Isabelle, thus providing a simple and natural environment for interactive proof development. Labelled Non-Classical Logics is essential reading for researchers and practitioners interested in the theory and applications of non-classical logics. (shrink)

A way is found to add axioms to sequent calculi that maintains the eliminability of cut, through the representation of axioms as rules of inference of a suitable form. By this method, the structural analysis of proofs is extended from pure logic to free-variable theories, covering all classical theories, and a wide class of constructive theories. All results are proved for systems in which also the rules of weakening and contraction can be eliminated. Applications include a system of predicate logic (...) with equality in which also cuts on the equality axioms are eliminated. (shrink)

A proof is given that the set of maximal intermediate propositional logics with the disjunction property and the set of maximal intermediate predicate logics with the disjunction property and the explicit definability property have the power of continuum. To prove our results, we introduce various notions which might be interesting by themselves. In particular, we illustrate a method to generate wide sets of pairwise "constructively incompatible constructive logics". We use a notion of "semiconstructive" logic and define wide sets of "constructive" (...) logics by representing the "constructive" logics as "limits" of decreasing sequences of "semiconstructive" logics. Also, we introduce some generalizations of the usual filtration techniques for propositional logics. For instance, "filtrations over rank formulas" are used to show that any two different logics belonging to a suitable uncountable set of "constructive" logics are "constructively incompatible". (shrink)

Geometric theories are presented as contraction- and cut-free systems of sequent calculi with mathematical rules following a prescribed rule-scheme that extends the scheme given in Negri and von Plato. Examples include cut-free calculi for Robinson arithmetic and real closed fields. As an immediate consequence of cut elimination, it is shown that if a geometric implication is classically derivable from a geometric theory then it is intuitionistically derivable.

This book continues from where the authors' previous book, Structural Proof Theory, ended. It presents an extension of the methods of analysis of proofs in pure logic to elementary axiomatic systems and to what is known as philosophical logic. A self-contained brief introduction to the proof theory of pure logic is included that serves both the mathematically and philosophically oriented reader. The method is built up gradually, with examples drawn from theories of order, lattice theory and elementary geometry. The aim (...) is, in each of the examples, to help the reader grasp the combinatorial behaviour of an axiom system, which typically leads to decidability results. The last part presents, as an application and extension of all that precedes it, a proof-theoretical approach to the Kripke semantics of modal and related logics, with a great number of new results, providing essential reading for mathematical and philosophical logicians. (shrink)

A general method for generating contraction- and cut-free sequent calculi for a large family of normal modal logics is presented. The method covers all modal logics characterized by Kripke frames determined by universal or geometric properties and it can be extended to treat also Gödel-Löb provability logic. The calculi provide direct decision methods through terminating proof search. Syntactic proofs of modal undefinability results are obtained in the form of conservativity theorems.

We get cut-free sequent calculi for the interpolable propositional intermediate logics by translating suitable duplication-free tableau calculi developed within a semantical framework. From this point of view, the paper also provides semantical proofs of the admissibility of the cut-rule for appropriate cut-free sequent calculi.

In this paper a method for the replacement, in formulas, of strong quantifiers by functions is introduced that can be considered as an alternative to Skolemization in the setting of constructive theories. A constructive extension of intuitionistic predicate logic that captures the notions of preorder and existence is introduced and the method, orderization, is shown to be sound and complete with respect to this logic. This implies an analogue of Herbrand's theorem for intuitionistic logic. The orderization method is applied to (...) the constructive theories of equality and groups. (shrink)

We give a short proof-theoretic treatment of a terminating contraction-free calculus G4-LC for the zero-order Gödel-Dummett logic LC. This calculus is a slight variant of a calculus given by Avellone et al, who show its completeness by model-theoretic techniques. In our calculus, all the rules of G4-LC are invertible, thus allowing a deterministic proof-search procedure.

The decision problem for positively quantified formulae in the theory of linearly ordered Heyting algebras is known, as a special case of work of Kreisel, to be solvable; a simple solution is here presented, inspired by related ideas in Gödel-Dummett logic.

Recent years have been blessed with an abundance of logical systems, arising from a multitude of applications. A logic can be characterised in many different ways. Traditionally, a logic is presented via the following three components: 1. an intuitive non-formal motivation, perhaps tie it in to some application area 2. a semantical interpretation 3. a proof theoretical formulation. There are several types of proof theoretical methodologies, Hilbert style, Gentzen style, goal directed style, labelled deductive system style, and so on. The (...) tableau methodology, invented in the 1950s by Beth and Hintikka and later per fected by Smullyan and Fitting, is today one of the most popular, since it appears to bring together the proof-theoretical and the semantical approaches to the pre of a logical system and is also very intuitive. In many universities it is sentation the style first taught to students. Recently interest in tableaux has become more widespread and a community crystallised around the subject. An annual tableaux conference is being held and proceedings are published. The present volume is a Handbook a/Tableaux pre senting to the community a wide coverage of tableaux systems for a variety of logics. It is written by active members of the community and brings the reader up to frontline research. It will be of interest to any formal logician from any area. (shrink)

A proof is given that the set of maximal intermediate propositional logics with the disjunction property and the set of maximal intermediate predicate logics with the disjunction property and the explicit definability property have the power of continuum. To prove our results, we introduce various notions which might be interesting by themselves. In particular, we illustrate a method to generate wide sets of pairwise "constructively incompatible constructive logics". We use a notion of "semiconstructive" logic and define wide sets of "constructive" (...) logics by representing the "constructive" logics as "limits" of decreasing sequences of "semiconstructive" logics. Also, we introduce some generalizations of the usual filtration techniques for propositional logics. For instance, "filtrations over rank formulas" are used to show that any two different logics belonging to a suitable uncountable set of "constructive" logics are "constructively incompatible". (shrink)