One way to obtain a comprehensive semantics for various systems of modal logic is to use a general notion of non-normal world. In the present article, a general notion of modal system is considered together with a semantic framework provided by such a general notion of non-normal world. Methodologically, the main purpose of this paper is to provide a logical framework for the study of various modalities, notably prepositional attitudes. Some specific systems are studied together with semantics using non-normal worlds (...) of different kinds. (shrink)

The main part of the proof of Kripke's completeness theorem for intuitionistic logic is Henkin's construction. We introduce a new Kripke-type semantics with semilattice structures for intuitionistic logic. The completeness theorem for this semantics can he proved without Henkin's construction.

Kripke-style models with two accessibility relations, one intuitionistic and the other modal, are given for analogues of the modal systemK based on Heyting's prepositional logic. It is shown that these two relations can combine with each other in various ways. Soundness and completeness are proved for systems with only the necessity operator, or only the possibility operator, or both. Embeddings in modal systems with several modal operators, based on classical propositional logic, are also considered. This paper lays the ground for (...) an investigation of intuitionistic analogues of systems stronger thanK. A brief survey is given of the existing literature on intuitionistic modal logic. (shrink)

Michael Dummett argues that acceptance of potentially infinite collections requires that we abandon classical logic and restrict ourselves to intuitionistic logic. In this paper we examine whether Dummett is correct. After developing two detailed accounts of what, exactly, it means for a concept to be potentially infinite (based on ideas due to Charles McCarty and Øystein Linnebo, respectively), we construct a Kripke structure that contains a natural number structure that satisfies both accounts. This model supports a logic much stronger than (...) intuitionistic logic, demonstrating that Dummett was wrong. We conclude by briefly examining ways to extend the account(s) in question to indefinitely extensible concepts such as Cardinal, Ordinal, and Set. (shrink)

In 2001, W. Carnielli and Marcos considered a 3-valued logic in order to prove that the schema ϕ ∨ (ϕ → ψ) is not a theorem of da Costa’s logic Cω. In 2006, this logic was studied (and baptized) as G'3 by Osorio et al. as a tool to define semantics of logic programming. It is known that the truth-tables of G'3 have the same expressive power than the one of Łukasiewicz 3-valued logic as well as the one of Gödel (...) 3-valued logic G3. From this, the three logics coincide up-to language, taking into acccount that 1 is the only designated truth-value in these logics. -/- From the algebraic point of view, Canals-Frau and Figallo have studied the 3-valued modal implicative semilattices, where the modal operator is the well-known Moisil-Monteiro-Baaz Δ operator, and the supremum is definable from this. We prove that the subvariety obtained from this by adding a bottom element 0 is term-equivalent to the variety generated by the 3-valued algebra of G'3. The algebras of that variety are called G'3-algebras. From this result, we obtain the equations which axiomatize the variety of G'3-algebras. Moreover, we prove that this variety is semisimple, and the 3-element and the 2-element chains are the unique simple algebras of the variety. Finally an extension of G'3 to first-order languages is presented, with an algebraic semantics based on complete G'3-algebras. The corresponding soundness and completeness theorems are obtained. (shrink)

Conditional logics were originally developed for the purpose of modeling intuitively correct modes of reasoning involving conditional—especially counterfactual—expressions in natural language. While the debate over the logic of conditionals is as old as propositional logic, it was the development of worlds semantics for modal logic in the past century that catalyzed the rapid maturation of the field. Moreover, like modal logic, conditional logic has subsequently found a wide array of uses, from the traditional (e.g. counterfactuals) to the exotic (e.g. conditional (...) obligation). Despite the close connections between conditional and modal logic, both the technical development and philosophical exploitation of the latter has outstripped that of the former, with the result that noticeable lacunae exist in the literature on conditional logic. My dissertation addresses a number of these underdeveloped frontiers, producing new technical insights and philosophical applications. -/- I contribute to the solution of a problem posed by Priest of finding sound and complete labeled tableaux for systems of conditional logic from Lewis' V-family. To develop these tableaux, I draw on previous work on labeled tableaux for modal and conditional logic; errors and shortcomings in recent work on this problem are identified and corrected. While modal logic has by now been thoroughly studied in non-classical contexts, e.g. intuitionistic and relevant logic, the literature on conditional logic is still overwhelmingly classical. Another contribution of my dissertation is a thorough analysis of intuitionistic conditional logic, in which I utilize both algebraic and worlds semantics, and investigate how several novel embedding results might shed light on the philosophical interpretation of both intuitionistic logic and conditional logic extensions thereof. -/- My dissertation examines deontic and connexive conditional logic as well as the underappreciated history of connexive notions in the analysis of conditional obligation. The possibility of interpreting deontic modal logics in such systems (via embedding results) serves as an important theoretical guide. A philosophically motivated proscription on impossible obligations is shown to correspond to, and justify, certain (weak) connexive theses. Finally, I contribute to the intensifying debate over counterpossibles, counterfactuals with impossible antecedents, and take—in contrast to Lewis and Williamson—a non-vacuous line. Thus, in my view, a counterpossible like "If there had been a counterexample to the law of the excluded middle, Brouwer would not have been vindicated" is false, not (vacuously) true, although it has an impossible antecedent. I exploit impossible (non-normal) worlds—originally developed to model non-normal modal logics—to provide non-vacuous semantics for counterpossibles. I buttress the case for non-vacuous semantics by making recourse to both novel technical results and theoretical considerations. (shrink)

Conditional logics have traditionally been intended to formalize various intuitively correct modes of reasoning involving conditional expressions in natural language. Although conditional logics have by now been thoroughly studied in a classical context, they have yet to be systematically examined in an intuitionistic context, despite compelling philosophical and technical reasons to do so. This paper addresses this gap by thoroughly examining the basic intuitionistic conditional logic ICK, the intuitionistic counterpart of Chellas’ important classical system CK. I give ICK both worlds (...) semantics and algebraic semantics, and prove that these are equivalent. I give a Gödel-type embedding of ICK into CK and a Glivenko-type embedding of CK into ICK. I axiomatize ICK and prove soundness, completeness, and decidability results. Finally, I discuss extending ICK. (shrink)

Modern categorical logic as well as the Kripke and topological models of intuitionistic logic suggest that the interpretation of ordinary “propositional” logic should in general be the logic of subsets of a given universe set. Partitions on a set are dual to subsets of a set in the sense of the category-theoretic duality of epimorphisms and monomorphisms—which is reflected in the duality between quotient objects and subobjects throughout algebra. If “propositional” logic is thus seen as the logic of subsets of (...) a universe set, then the question naturally arises of a dual logic of partitions on a universe set. This paper is an introduction to that logic of partitions dual to classical subset logic. The paper goes from basic concepts up through the correctness and completeness theorems for a tableau system of partition logic. (shrink)

Classical logic is usually interpreted as the logic of propositions. But from Boole's original development up to modern categorical logic, there has always been the alternative interpretation of classical logic as the logic of subsets of any given (nonempty) universe set. Partitions on a universe set are dual to subsets of a universe set in the sense of the reverse-the-arrows category-theoretic duality--which is reflected in the duality between quotient objects and subobjects throughout algebra. Hence the idea arises of a dual (...) logic of partitions. That dual logic is described here. Partition logic is at the same mathematical level as subset logic since models for both are constructed from (partitions on or subsets of) arbitrary unstructured sets with no ordering relations, compatibility or accessibility relations, or topologies on the sets. Just as Boole developed logical finite probability theory as a quantitative treatment of subset logic, applying the analogous mathematical steps to partition logic yields a logical notion of entropy so that information theory can be refounded on partition logic. But the biggest application is that when partition logic and the accompanying logical information theory are "lifted" to complex vector spaces, then the mathematical framework of quantum mechanics is obtained. Partition logic models indefiniteness (i.e., numerical attributes on a set become more definite as the inverse-image partition becomes more refined) while subset logic models the definiteness of classical physics (an entity either definitely has a property or definitely does not). Hence partition logic provides the backstory so the old idea of "objective indefiniteness" in QM can be fleshed out to a full interpretation of quantum mechanics. (shrink)

What an intuitionist may refer to with respect to a given epistemic state depends not only on that epistemic state itself but on whether it is viewed concurrently from within, in the hindsight of some later state, or ideally from a standpoint “beyond” all epistemic states (though the latter perspective is no longer strictly intuitionistic). Each of these three perspectives has a different—and, in the last two cases, a novel—logic and semantics. This paper explains these logics and their semantics and (...) provides soundness and completeness proofs. It provides, moreover, a critique of some common versions of Kripke semantics for intuitionistic logic and suggests ways of modifying them to take account of the perspective-relativity of reference. (shrink)

We define an order independent version of default unification on typed feature structures. The operation is one where default information in a feature structure typed with a more specific type, will override default information in a feature structure typed with a more general type, where specificity is defined by the subtyping relation in the type hierarchy. The operation is also able to handle feature structures where reentrancies are default. We provide a formal semantics, prove order independence and demonstrate the utility (...) of this version of default unification in several linguistic applications. First, we show how it can be used to define multiple orthogonal default inheritance in the lexicon in a fully declarative fashion. Secondly, we show how default lexical specifications (introduced via default lexical inheritance) can be made to usefully persist beyond the lexicon and interact with syntagmatic rules. Finally, we outline how persistent default unification might underpin default feature propagation principles and a more restrictive and constraint-based approach to lexical rules. (shrink)

Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps the (...) developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic. (shrink)

This volume is dedicated to Prof. Dag Prawitz and his outstanding contributions to philosophical and mathematical logic. Prawitz's eminent contributions to structural proof theory, or general proof theory, as he calls it, and inference-based meaning theories have been extremely influential in the development of modern proof theory and anti-realistic semantics. In particular, Prawitz is the main author on natural deduction in addition to Gerhard Gentzen, who defined natural deduction in his PhD thesis published in 1934. The book opens with an (...) introductory paper that surveys Prawitz's numerous contributions to proof theory and proof-theoretic semantics and puts his work into a somewhat broader perspective, both historically and systematically. Chapters include either in-depth studies of certain aspects of Dag Prawitz's work or address open research problems that are concerned with core issues in structural proof theory and range from philosophical essays to papers of a mathematical nature. Investigations into the necessity of thought and the theory of grounds and computational justifications as well as an examination of Prawitz's conception of the validity of inferences in the light of three “dogmas of proof-theoretic semantics” are included. More formal papers deal with the constructive behaviour of fragments of classical logic and fragments of the modal logic S4 among other topics. In addition, there are chapters about inversion principles, normalization of proofs, and the notion of proof-theoretic harmony and other areas of a more mathematical persuasion. Dag Prawitz also writes a chapter in which he explains his current views on the epistemic dimension of proofs and addresses the question why some inferences succeed in conferring evidence on their conclusions when applied to premises for which one already possesses evidence. (shrink)

The Boolean many-valued approach to vagueness is similar to the infinite-valued approach embraced by fuzzy logic in the respect in which both approaches seek to solve the problems of vagueness by assigning to the relevant sentences many values between falsity and truth, but while the fuzzy-logic approach postulates linearly-ordered values between 0 and 1, the Boolean approach assigns to sentences values in a many-element complete Boolean algebra. On the modal-precisificational approach represented by Kit Fine, if a sentence is indeterminate in (...) truth value in some world, it is taken to be true in one precisified world accessible from that world and false in another. This paper points to a way to unify these two approaches to vagueness by showing that Fine’s version of the modal-precisificational approach can be combined with the Boolean many-valued approach instead of supervaluationism, one of the most popular approaches to vagueness. (shrink)

The concept of “necessity of thought” plays a central role in Dag Prawitz’s essay “Logical Consequence from a Constructivist Point of View” (Prawitz 2005). The theme is later developed in various articles devoted to the notion of valid inference (Prawitz, 2009, forthcoming a, forthcoming b). In section 1 I explain how the notion of necessity of thought emerges from Prawitz’s analysis of logical consequence. I try to expound Prawitz’s views concerning the necessity of thought in sections 2, 3 and 4. (...) In sections 5 and 6 I discuss some problems arising with regard to Prawitz’s views. (shrink)

This volume presents mathematical game theory as an interface between logic and philosophy.

We construct an extension P of the standard language of classical propositional logic by adjoining to the alphabet of a new category of logical-pragmatic signs. The well formed formulas of are calledradical formulas (rfs) of P;rfs preceded by theassertion sign constituteelementary assertive formulas of P, which can be connected together by means of thepragmatic connectives N, K, A, C, E, so as to obtain the set of all theassertive formulas (afs). Everyrf of P is endowed with atruth value defined classically, (...) and everyaf is endowed with ajustification value, defined in terms of the intuitive notion of proof and depending on the truth values of its radical subformulas. In this framework, we define the notion ofpragmatic validity in P and yield a list of criteria of pragmatic validity which hold under the assumption that only classical metalinguistic procedures of proof be accepted. We translate the classical propositional calculus (CPC) and the intuitionistic propositional calculus (IPC) into the assertive part of P and show that this translation allows us to interpret Intuitionistic Logic as an axiomatic theory of the constructive proof concept rather than an alternative to Classical Logic. Finally, we show that our framework provides a suitable background for discussing classical problems in the philosophy of logic. (shrink)

This paper is a reaction to the following remark by grzegorczyk: "the compound sentences are not a product of experiment. they arise from reasoning. this concerns also negations; we see that the lemon is yellow, we do not see that it is not blue." generally, in science the truth is ascertained as indirectly as falsehood. an example: a litmus-paper is used to verify the sentence "the solution is acid." this approach gives rise to a (very intuitionistic indeed) conservative extension of (...) the heyting logic satisfying natural duality laws. (shrink)

We study finitely generated free Heyting algebras from a topological and from a model theoretic point of view. We review Bellissima’s representation of the finitely generated free Heyting algebra; we prove that it yields an embedding in the profinite completion, which is also the completion with respect to a naturally defined metric. We give an algebraic interpretation of the Kripke model used by Bellissima as the principal ideal spectrum and show it to be first order interpretable in the Heyting algebra, (...) from which several model theoretic and algebraic properties are derived. In particular, we prove that a free finitely generated Heyting algebra has only one set of free generators, which is definable in it. As a consequence its automorphism group is the permutation group over its generators. (shrink)

The paper presents predicate logical extensions of some subintuitionistic logics. Subintuitionistic logics result if conditions of the accessibility relation in Kripke models for intuitionistic logic are dropped. The accessibility relation which interprets implication in models for the propositional base subintuitionistic logic considered here is neither persistent on atoms, nor reflexive, nor transitive. Strongly complete predicate logical extensions are modeled with a second accessibility relation, which is a partial order, for the interpretation of the universal quantifier.

David Nelson’s constructive logics with strong negation may beviewed as alternative paraconsistent logic. These logics have been developedbefore da Costa’s works. We address some philosophical aspects of Nelson’slogics and give technical results concerning Kripke models and tableau calculi. We also suggest possible applications of paraconsistent constructivelogics.

Since 1993, when Hudelmaier developed an O(n log n)-space decision procedure for propositional Intuitionistic Logic, a lot of work has been done to improve the efficiency of the related proof-search algorithms. In this paper a tableau calculus using the signs T, F and Fc with a new set of rules to treat signed formulas of the kind T((A → B) → C) is provided. The main feature of the calculus is the reduction of both the non-determinism in proof-search and the (...) width of proofs with respect to Hudelmaier's one. These improvements have a significant influence on the performances of the implementation. (shrink)

This paper, a sequel to Models for normal intuitionistic modal logics by M. Boi and the author, which dealt with intuitionistic analogues of the modal system K, deals similarly with intuitionistic analogues of systems stronger than K, and, in particular, analogues of S4 and S5. For these prepositional logics Kripke-style models with two accessibility relations, one intuitionistic and the other modal, are given, and soundness and completeness are proved with respect to these models. It is shown how the holding of (...) formulae characteristic for particular logics is equivalent to conditions for the relations of the models. Modalities in these logics are also investigated. (shrink)

RésuméGian-Carlo Rota est l’un des rares grands mathématiciens de la deuxième moitié du XX e siècle dont l’intérêt pour la logique formelle soit aussi ouvertement déclaré et ne se soit jamais démenti, depuis sa formation d’étudiant à Princeton jusqu’à ses derniers écrits. Plus exceptionnel encore, il fait partie des rares lecteurs assidus de Husserl à s’être aperçu que la phé-noménologie poursuivait un projet de réforme de la logique formelle. L’article propose d’attester l’existence d’un tel projet chez Husserl ; d’en examiner (...) la réappropriation et les prolongements chez Rota.Gian-Carlo Rota is among the few great mathematicians of the second-half of the XXth century whose interest in formal logic is openly declared and has never flagged, since his training as a student in Princeton up to his last writings. Even more exceptional, he belongs to the rare diligent readers of Husserl, who noticed that phenomenology was pursuing a project of reform of formal logic. This paper propose to testify to the existence of such a project in Husserl; to examine how it is taken over and continued by Rota. Gian-Carlo Rota è uno dei pochi grandi matematici della seconda metà del ventesimo secolo, il cui interesse per la logica formale è, dalla sua formazione come studente a Princeton al suo ultimi scritti, apertamente dichiarato e mai negato. Cosa ancora più eccezionale, Rota è uno dei rari lettori assidui di Husserl ad aver percepito che la fenomenologia stava perseguendo un progetto di riforma della logica formale. L’articolo propone di attestare l’esistenza di un tale progetto in Husserl e di esaminare la sua riappropriazione e le sue estensioni proposte da Gian-Carlo Rota.This article is in French. (shrink)

Various natural deduction formulations of classical, minimal, intuitionist, and intermediate propositional and first-order logics are presented and investigated with respect to satisfaction of the separation and subformula properties. The technique employed is, for the most part, semantic, based on general versions of the Lindenbaum and Lindenbaum–Henkin constructions. Careful attention is paid to which properties of theories result in the presence of which rules of inference, and to restrictions on the sets of formulas to which the rules may be employed, restrictions (...) determined by the formulas occurring as premises and conclusion of the invalid inference for which a counterexample is to be constructed. We obtain an elegant formulation of classical propositional logic with the subformula property and a singularly inelegant formulation of classical first-order logic with the subformula property, the latter, unfortunately, not a product of the strategy otherwise used throughout the article. Along the way, we arrive at an optimal strengthening of the subformula results for classical first-order logic obtained as consequences of normalization theorems by Dag Prawitz and Gunnar Stålmarck. (shrink)

This paper presents logics for reasoning about extension and reduction of partial information states. This enterprise amounts to nonpersistent variations of certain constructive logics, in particular the so-called logic of constructible falsity of Nelson. We provide simple semantics, sequential calculi, completeness and decidability proofs.

Motivated by the definition of semi-Nelson algebras, a propositional calculus called semi-intuitionistic logic with strong negation is introduced and proved to be complete with respect to that class of algebras. An axiomatic extension is proved to have as algebraic semantics the class of Nelson algebras.

An intermediate predicate logicS + n (n>0) is introduced and investigated. First, a sequent calculusGS n is introduced, which is shown to be equivalent toS + n and for which the cut elimination theorem holds. In § 2, it will be shown thatS + n is characterized by the class of all linear Kripke frames of the heightn.

The logic CD is an intermediate logic which exactly corresponds to the Kripke models with constant domains. It is known that the logic CD has a Gentzen-type formulation called LD and rules are replaced by the corresponding intuitionistic rules) and that the cut-elimination theorem does not hold for LD. In this paper we present a modification of LD and prove the cut-elimination theorem for it. Moreover we prove a “weak” version of cut-elimination theorem for LD, saying that all “cuts” except (...) some special forms can be eliminated from a proof in LD. From these cut-elimination theorems we obtain some corollaries on syntactical properties of CD: fragments collapsing into intuitionistic logic. Harrop disjunction and existence properties, and a fact on the number of logical symbols in the axiom of CD. (shrink)

A dialogical version of (modal) epistemic logic is outlined, with an intuitionistic variant. Another version of dialogical epistemic logic is then provided by means of the S4 mapping of intuitionistic logic. Both systems cast new light on the relationship between intuitionism, modal logic and dialogical games.

Medvedev's intermediate logic (MV) can be defined by means of Kripke semantics as the family of Kripke frames given by finite Boolean algebras without units as partially ordered sets. The aim of this paper is to present a proof of the theorem: For every set of connectives such that the-fragment ofMV equals the fragment of intuitionistic logic. The final part of the paper brings the negative solution to the problem set forth by T. Hosoi and H. Ono, namely: is an (...) intermediate logic based on the axiom (abc) (ab)(a c) separable? (shrink)