This volume is dedicated to Leo Esakia's contributions to the theory of modal and intuitionistic systems. Consisting of 10 chapters, written by leading experts, this volume discusses Esakia’s original contributions and consequent developments that have helped to shape duality theory for modal and intuitionistic logics and to utilize it to obtain some major results in the area. Beginning with a chapter which explores Esakia duality for S4-algebras, the volume goes on to explore Esakia duality for Heyting algebras and its generalizations (...) to weak Heyting algebras and implicative semilattices. The book also dives into the Blok-Esakia theorem and provides an outline of the intuitionistic modal logic KM which is closely related to the Gödel-Löb provability logic GL. One chapter scrutinizes Esakia’s work interpreting modal diamond as the derivative of a topological space within the setting of point-free topology. The final chapter in the volume is dedicated to the derivational semantics of modal logic and other related issues. (shrink)

In researching presuppositions dealing with logic and dynamic of belief we distinguish two related parts. The first part refers to presuppositions and logic, which is not necessarily involved with intentional operators. We are primarily concerned with classical, free and presuppositonal logic. Here, we practice a well known Strawson’s approach to the problem of presupposition in relation to classical logic. Further on in this work, free logic is used, especially Van Fraassen’s research of the role of presupposition in supervaluations logical systems. (...) At the end of the first part, presuppositional logic, advocated by S.K. Thomason, is taken into consideration. The second part refers to the presuppositions in relation to the logic of the dynamics of belief. Here the logic of belief change is taken into consideration and other epistemic notions with immanent mechanism for the presentation of the dynamics. Three representative and dominant approaches are evaluated. First, we deal with new, less classical, situation semantics. Besides Strawson’s theory, the second theory is the theory of the belief change, developed by Alchourron, Gärdenfors, and Makinson (AGM theory). At the end, the oldest, universal, and dominant approach is used, recognized as Hintikka’s approach to the analysis of epistemic notions. (shrink)

The aim of this work is to develop a declarative semantics for N-Prolog with negation as failure. N-Prolog is an extension of Prolog proposed by Gabbay and Reyle, which allows for occurrences of nested implications in both goals and clauses. Our starting point is an operational semantics of the language defined by means of top-down derivation trees. Negation as finite failure can be naturally introduced in this context. A goal-G may be inferred from a database if every top-down derivation of (...) G from the database finitely fails, i.e., contains a failure node at finite height.Our purpose is to give a logical interpretation of the underlying operational semantics. In the present work we take into consideration only the basic problems of determining such an interpretation, so that our analysis will concentrate on the propositional case. Nevertheless we give an intuitive account of how to extend our results to a first order language. A full treatment of N-Prolog with quantifiers will be deferred to the second part of this work. (shrink)

The knower paradox states that the statement ‘We know that this statement is false’ leads to inconsistency. This article presents a fresh look at this paradox and some well-known solutions from the literature. Paul Égré discusses three possible solutions that modal provability logic provides for the paradox by surveying and comparing three different provability interpretations of modality, originally described by Skyrms, Anderson, and Solovay. In this article, some background is explained to clarify Égré’s solutions, all three of which hinge on (...) intricacies of provability logic and its arithmetical interpretations. To check whether Égré’s solutions are satisfactory, we use the criteria for solutions to paradoxes defined by Susan Haack and we propose some refinements of them. This article aims to describe to what extent the knower paradox can be solved using provability logic and to what extent the solutions proposed in the literature satisfy Haack’s criteria. Finally, the article offers some reflections on the relation between knowledge, proof, and provability, as inspired by the knower paradox and its solutions. (shrink)

After sketching the main lines of Hilbert's program, certain well-known andinfluential interpretations of the program are critically evaluated, and analternative interpretation is presented. Finally, some recent developments inlogic related to Hilbert's program are reviewed.

It is shown that for arithmetical interpretations that may include free variables it is not the Guaspari-Solovay system R that is arithmetically complete, but their system R⁻. This result is then applied to obtain the nonvalidity of some rules under arithmetical interpretations including free variables, and to show that some principles concerning Rosser orderings with free variables cannot be decided, even if one restricts onself to "usual" proof predicates.

We show that a consistent, finitely axiomatized, sequential theory cannot prove its own inconsistency on every definable cut. A corollary is that there are at least three degrees of global interpretability of theories equivalent modulo local interpretability to a consistent, finitely axiomatized, sequential theory U.

This paper contains a careful derivation of principles of Interpretability Logic valid in extensions of I0+1.

This paper provides several examples of how modal logic can be used in studying the XML document navigation language XPath. More specifically, we derive complete axiomatizations, computational complexity and expressive power results for XPath fragments from known results for corresponding logics. A secondary aim of the paper is to introduce XPath in a way that makes it accessible to an audience of modal logicians.

Since Montague’s work it is well known that treating a single modality as a predicate may lead to paradox. In their paper “No Future”, Horsten and Leitgeb show that if the two temporal modalities are treated as predicates paradox might arise as well. In our paper we investigate whether paradoxes of multiple modalities, such as the No Future paradox, are genuinely new paradoxes or whether they “reduce” to the paradoxes of single modalities. In order to address this question we develop (...) a notion of reducibility based on a version of Smoryński Diagonalized Operator Logic. We show that there are reducible multimodal paradoxes as well as irreducible paradoxes of interaction. In particular, we show the No Future paradox to be an irreducible paradox according to our notion of reducibility. (shrink)

In Honour of John Crossley’s 85th Birthday.

We prove that the first order theory of the fixed point algebra corresponding to an r.e. consistent theory containing arithmetic is hereditarily undecidable.

S. SHAPIRO (ed.), Intensional Mathematics (Studies in Logic and the Foundations of Mathematics, vol. 11 3). Amsterdam: North-Holland, 1985. v + 230 pp. $38.50/100Df.

Paradox is a logical phenomenon. Usually, it is produced in type theory, on a type Ω of “truth values”. A formula Ψ (i.e., a term of type Ω) is presented, such that Ψ↔¬Ψ (with negation as a term¬∶Ω→Ω)-whereupon everything can be proved: In Sect. 1 we describe a general pattern which many constructions of the formula Ψ follow: for example, the well known arguments of Cantor, Russell, and Gödel. The structure uncovered behind these paradoxes is generalized in Sect. 2. This (...) allows us to show that Reynolds' [R] construction of a typeA ≃℘℘A in polymorphic λ-calculus cannot be extended, as conjectured, to give a fixed point ofevery variable type derived from the exponentiation: for some (contravariant) types, such a fixed point causes a paradox.Pursueing the idea that $$\frac{{{\text{type theory}}}}{{{\text{categorical interpretation}}}} = \frac{{{\text{(propositional) logic}}}}{{{\text{Lindebaum algebra}}}}$$ the language of categories appears here as a natural medium for logical structures. It allows us to abstract from the specific predicates that appear in particular paradoxes, and to display the underlying constructions in “pure state”. The essential role of cartesian closed categories in this context has been pointed out in [L]. The paradoxes studied here remain within the limits of the cartesian closed structure of types, as sketched in this Lawvere's seminal paper — and do not depend on any logical operations on the type Ω. Our results can be translated in simply typed λ-calculus in a straightforward way (although some of them do become a bit messy). (shrink)

It is well-known that natural axiomatic theories are well-ordered by consistency strength. However, it is possible to construct descending chains of artificial theories with respect to consistency strength. We provide an explanation of this well-orderedness phenomenon by studying a coarsening of the consistency strength order, namely, the$\Pi ^1_1$reflection strength order. We prove that there are no descending sequences of$\Pi ^1_1$sound extensions of$\mathsf {ACA}_0$in this ordering. Accordingly, we can attach a rank in this order, which we call reflection rank, to any$\Pi (...) ^1_1$sound extension of$\mathsf {ACA}_0$. We prove that for any$\Pi ^1_1$sound theoryTextending$\mathsf {ACA}_0^+$, the reflection rank ofTequals the$\Pi ^1_1$proof-theoretic ordinal ofT. We also prove that the$\Pi ^1_1$proof-theoretic ordinal of$\alpha $iterated$\Pi ^1_1$reflection is$\varepsilon _\alpha $. Finally, we use our results to provide straightforward well-foundedness proofs of ordinal notation systems based on reflection principles. (shrink)

-/- Provability logic is a modal logic that is used to investigate what arithmetical theories can express in a restricted language about their provability predicates. The logic has been inspired by developments in meta-mathematics such as Gödel’s incompleteness theorems of 1931 and Löb’s theorem of 1953. As a modal logic, provability logic has been studied since the early seventies, and has had important applications in the foundations of mathematics. -/- From a philosophical point of view, provability logic is interesting because (...) the concept of provability in a fixed theory of arithmetic has a unique and non-problematic meaning, other than concepts like necessity and knowledge studied in modal and epistemic logic. Furthermore, provability logic provides tools to study the notion of self-reference. (shrink)

This paper is an investigation into what could be a goodexplication of ``theory S is reducible to theory T''''. Ipresent an axiomatic approach to reducibility, which is developedmetamathematically and used to evaluate most of the definitionsof ``reducible'''' found in the relevant literature. Among these,relative interpretability turns out to be most convincing as ageneral reducibility concept, proof-theoreticalreducibility being its only serious competitor left. Thisrelation is analyzed in some detail, both from the point of viewof the reducibility axioms and of modal logic.

Given a 1-ary sentence operator , we describe L - another 1-ary operator - as as a left inverse of in a given logic if in that logic every formula is provably equivalent to L. Similarly R is a right inverse of if is always provably equivalent to R. We investigate the behaviour of left and right inverses for taken as the operator of various normal modal logics, paying particular attention to the conditions under which these logics are conservatively extended (...) by the addition of such inverses, as well as to the question of when, in such extensions, the inverses behave as normal modal operators in their own right. (shrink)

Guaspari (J Symb Logic 48:777–789, 1983) conjectured that a modal formula is it essentially Σ1 (i.e., it is Σ1 under any arithmetical interpretation), if and only if it is provably equivalent to a disjunction of formulas of the form ${\square{B}}$ . This conjecture was proved first by A. Visser. Then, in (de Jongh and Pianigiani, Logic at Work: In Memory of Helena Rasiowa, Springer-Physica Verlag, Heidelberg-New York, pp. 246–255, 1999), the authors characterized essentially Σ1 formulas of languages including witness comparisons (...) using the interpretability logic ILM. In this note we give a similar characterization for formulas with a binary operator interpreted as interpretability in a finitely axiomatizable extension of IΔ 0 + Supexp and we address a similar problem for IΔ 0 + Exp. (shrink)

In this note, a fully modal proof is given of some conservation results proved in a previous paper by arithmetic means. The proof is based on the extendability of Kripke models.

The modal logic of Gödel sentences, termed as GS, is introduced to analyze the logical properties of 'true but unprovable' sentences in formal arithmetic. The logic GS is, in a sense, dual to Grzegorczyk's Logic, where modality can be interpreted as 'true and provable'. As we show, GS and Grzegorczyk's Logic are, in fact, mutually embeddable. We prove Kripke completeness and arithmetical completeness for GS. GS is also an extended system of the logic of 'Essence and Accident' proposed by Marcos (...) (Bull Sect Log 34(1):43-56, 2005). We also clarify the relationships between GS and the provability logic GL and between GS and Intuitionistic Propositional Logic. (shrink)

In this paper, we investigate Rosser provability predicates whose provability logics are normal modal logics. First, we prove that there exists a Rosser provability predicate whose provability logic is exactly the normal modal logic \. Secondly, we introduce a new normal modal logic \ which is a proper extension of \, and prove that there exists a Rosser provability predicate whose provability logic includes \.

We investigate relationships between versions of derivability conditions for provability predicates. We show several implications and non-implications between the conditions, and we discuss unprovability of consistency statements induced by derivability conditions. First, we classify already known versions of the second incompleteness theorem, and exhibit some new sets of conditions which are sufficient for unprovability of Hilbert–Bernays’ consistency statement. Secondly, we improve Buchholz’s schematic proof of provable$\Sigma_1$-completeness. Then among other things, we show that Hilbert–Bernays’ conditions and Löb’s conditions are mutually incomparable. (...) We also show that neither Hilbert–Bernays’ conditions nor Löb’s conditions accomplish Gödel’s original statement of the second incompleteness theorem. (shrink)

Let ℸ be the set of Gödel numbers Gn of function symbols f such that PRA ⊢ and let γ be the function such that equation imageWe prove: The r. e. set ℸ is m-complete; the function γ is not primitive recursive in any class of functions {f1, f2, ⃛} so long as each fi has a recursive upper bound. This implies that γ is not primitive recursive in ℸ although it is recursive in ℸ.

We investigate, for several modal logics but concentrating on KT, KD45, S4 and S5, the set of formulas B for which ${\square B}$ is provably equivalent to ${\square A}$ for a selected formula A (such as p, a sentence letter). In the exceptional case in which a modal logic is closed under the (‘cancellation’) rule taking us from ${\square C \leftrightarrow \square D}$ to ${C \leftrightarrow D}$ , there is only one formula B, to within equivalence, in this inverse image, (...) as we shall call it, of ${\square A}$ (relative to the logic concerned); for logics for which the intended reading of “ ${\square}$ ” is epistemic or doxastic, failure to be closed under this rule indicates that from the proposition expressed by a knowledge- or belief-attribution, the propositional object of the attitude in question cannot be recovered: arguably, a somewhat disconcerting situation. More generally, the inverse image of ${\square A}$ may comprise a range of non-equivalent formulas, all those provably implied by one fixed formula and provably implying another—though we shall see that for several choices of logic and of the formula A, there is not even such an ‘interval characterization’ of the inverse image (of ${\square A}$ ) to be found. (shrink)

We show that the modal prepositional logicILM (interpretability logic with Montagna's principle), which has been shown sound and complete as the interpretability logic of Peano arithmetic PA (by Berarducci and Savrukov), is sound and complete as the logic ofπ 1-conservativity over eachbE 1-sound axiomatized theory containingI⌆ 1 (PA with induction restricted tobE 1-formulas). Furthermore, we extend this result to a systemILMR obtained fromILM by adding witness comparisons in the style of Guaspari's and Solovay's logicR (this will be done in a (...) separate continuation of the present paper). (shrink)

The proof-theoretic results on axiomatic theories oftruth obtained by different authors in recent years are surveyed.In particular, the theories of truth are related to subsystems ofsecond-order analysis. On the basis of these results, thesuitability of axiomatic theories of truth for ontologicalreduction is evaluated.

This paper propounds a systematic examination of the link between the Knower Paradox and provability interpretations of modal logic. The aim of the paper is threefold: to give a streamlined presentation of the Knower Paradox and related results; to clarify the notion of a syntactical treatment of modalities; finally, to discuss the kind of solution that modal provability logic provides to the Paradox. I discuss the respective strength of different versions of the Knower Paradox, both in the framework of first-order (...) arithmetic and in that of modal logic with fixed point operators. It is shown that the notion of a syntactical treatment of modalities is ambiguous between a self-referential treatment and a metalinguistic treatment of modalities, and that these two notions are independent. I survey and compare the provability interpretations of modality respectively given by Skyrms, B. (1978, The Journal of Philosophy 75: 368–387) Anderson, C.A. (1983, The Journal of Philosophy 80: 338–355) and Solovay, R. (1976, Israel Journal of Mathematics 25: 287–304). I examine how these interpretations enable us to bypass the limitations imposed by the Knower Paradox while preserving the laws of classical logic, each time by appeal to a distinct form of hierarchy. (shrink)

This paper investigates the conditions under which diagonal sentences can be taken to constitute paradigmatic cases of self-reference. We put forward well-motivated constraints on the diagonal operator and the coding apparatus which separate paradigmatic self-referential sentences, for instance obtained via Gödel’s diagonalization method, from accidental diagonal sentences. In particular, we show that these constraints successfully exclude refutable Henkin sentences, as constructed by Kreisel.

In this paper the PA-completeness of modal logic is studied by syntactical and constructive methods. The main results are theorems on the structure of the PA-proofs of suitable arithmetical interpretationsS of a modal sequentS, which allow the transformation of PA-proofs ofS into proof-trees similar to modal proof-trees. As an application of such theorems, a proof of Solovay's theorem on arithmetical completeness of the modal system G is presented for the class of modal sequents of Boolean combinations of formulas of the (...) form p i,m i=0, 1, 2, ... The paper is the preliminary step for a forthcoming global syntactical resolution of the PA-completeness problem for modal logic. (shrink)

In [6] Albert Visser shows that ILP completely axiomatizes all schemata about provability and relative interpretability that are provable in finitely axiomatized theories. In this paper we introduce a system called $\text{ILP}^{\omega}$ that completely axiomatizes the arithmetically valid principles of provability in and interpretability over such theories. To prove the arithmetical completeness of $\text{ILP}^{\omega}$ we use a suitable kind of tail models; as a byproduct we obtain a somewhat modified proof of Visser's completeness result.

Solovay's 1976 completeness result for modal provability logic employs the recursion theorem in its proof. It is shown that the uses of the recursion theorem can in this proof replaced by the diagonalization lemma for arithmetic and that, in effect, the proof neatly fits the framework of another, enriched, system of modal logic so that any arithmetical system for which this logic is sound is strong enough to carry out the proof, in particular $\text{I}\Delta _{0}+\text{EXP}$ . The method is adapted (...) to obtain a similar completeness result for the Rosser logic. (shrink)

The problem of Uniqueness and Explicit Definability of Fixed Points for Interpretability Logic is considered. It turns out that Uniqueness is an immediate corollary of a theorem of Smoryński.

To the standard propositional modal system of provability logic constants are added to account for the arithmetical fixed points introduced by Bernardi-Montagna in [5]. With that interpretation in mind, a system LR of modal propositional logic is axiomatized, a modal completeness theorem is established for LR and, after that, a uniform arithmetical completeness theorem with respect to PA is obtained for LR.

The modal completeness proofs of Guaspari and Solovay for their systems R and R⁻ are improved and the relationship between R and R⁻ is clarified.