From the point of view of non-classical logics, Heyting's implication is the smallest implication for which the deduction theorem holds. This book studies properties of logical systems having some of the classical connectives and implication in the neighbourhood of Heyt ing's implication. I have not included anything on entailment, al though it belongs to this neighbourhood, mainly because of the appearance of the Anderson-Belnap book on entailment. In the later chapters of this book, I have included material that might (...) be of interest to the intuitionist mathematician. Originally, I intended to include more material in that spirit but I decided against it. There is no coherent body of material to include that builds naturally on the present book. There are some serious results on topological models, second order Beth and Kripke models, theories of types, etc., but it would require further research to be able to present a general theory, possibly using sheaves. That would have postponed pUblication for too long. I would like to dedicate this book to my colleagues, Professors G. Kreisel, M.O. Rabin and D. Scott. I have benefited greatly from Professor Kreisel's criticism and suggestions. Professor Rabin's fun damental results on decidability and undecidability provided the powerful tools used in obtaining the majority of the results reported in this book. Professor Scott's approach to non-classical logics and especially his analysis of the Scott consequence relation makes it possible to present Heyting's logic as a beautiful, integral part of non-classical logics. (shrink)

In this paper it is shown that Heyting and Co-Heyting mereological systems provide a convenient conceptual framework for spatial reasoning, in which spatial concepts such as connectedness, interior parts, (exterior) contact, and boundary can be defined in a natural and intuitively appealing way. This fact refutes the wide-spread contention that mereology cannot deal with the more advanced aspects of spatial reasoning and therefore has to be enhanced by further non-mereological concepts to overcome its congenital limitations. The allegedly unmereological (...) concept of boundary is treated in detail and shown to be essentially affected by mereological considerations. More precisely, the concept of boundary turns out to be realizable in a variety of different mereologically grounded versions. In particular, every part K of a Heyting algebra H gives rise to a well-behaved K-relative boundary operator. (shrink)

We present an extension of Heyting arithmetic in finite types called Uniform Heyting Arithmetic that allows for the extraction of optimized programs from constructive and classical proofs. The system has two sorts of first-order quantifiers: ordinary quantifiers governed by the usual rules, and uniform quantifiers subject to stronger variable conditions expressing roughly that the quantified object is not computationally used in the proof. We combine a Kripke-style Friedman/Dragalin translation which is inspired by work of Coquand and Hofmann (...) and a variant of the refined A-translation due to Buchholz, Schwichtenberg and the author to extract programs from a rather large class of classical first-order proofs while keeping explicit control over the levels of recursion and the decision procedures for predicates used in the extracted program. (shrink)

The paper studies Heyting algebras within the framework of computable structure theory. We prove that the class _K_ containing all Heyting algebras with distinguished atoms and coatoms is complete in the sense of the work of Hirschfeldt et al. (Ann Pure Appl Logic 115(1-3):71-113, 2002). This shows that the class _K_ is rich from the computability-theoretic point of view: for example, every possible degree spectrum can be realized by a countable structure from _K_. In addition, there is no (...) simple syntactic characterization of computably categorical members of _K_ (i.e., structures from _K_ possessing a unique computable copy, up to computable isomorphisms). (shrink)

In this paper we define an augmentation mHC of the Heyting propositional calculus HC by a modal operator ?. This modalized Heyting calculus mHC is a weakening of the Proof-Intuitionistic Logic KM of Kuznetsov and Muravitsky. In Section 2 we present a short selection of attractive (algebraic, relational, topological and categorical) features of mHC. In Section 3 we establish some close connections between mHC and certain normal extension K4.Grz of the modal system K4. We define a translation (...) of mHC into K4.Grz and prove that this translation is exact, i. e. theorem-preserving and deducibility-invariant. We have established (however, in this note we do not present a proof of this) that the lattice of all extensions of mHC is isomorphic to the lattice of normal extensions of K4.Grz (a generalization of the Kuznetsov and Muravitsky theorem). (shrink)

At the end of the 19th century in the fundamentals of mathematics appeared a crisis. It was caused by the paradoxes found in Cantor’s set theory. One of the ideas a resolving the crisis was intuitionism – one of the constructivist trends in the philosophy of mathematics. Its creator was Brouwer, the main representative was Heyting. In this paper described will be attempt to construct a suitable logic for philosophical intuitionism theses. In second paragraph Heyting system will (...) be present – its axioms and matrices truth-. Later Gödel theorem about the inadequacy of finite dimensional matrices for this system will be explained. At the end this paper an infinite sequence of matrices adequate for Heyting axioms proposed by Jaśkowski will be described. (shrink)

It is known that propositional relevant logics can be conservatively extended by the addition of a Heyting (intuitionistic) implication connective. We show that this same conservativity holds for a range of first-order relevant logics with strong identity axioms, using an adaptation of Fine’s stratified model theory. For systems without identity, the question of conservatively adding Heyting implication is thereby reduced to the question of conservatively adding the axioms for identity. Some results in this direction are also obtained. The (...) conservative presence of Heyting implication allows the development of an alternative model theory for quantified relevant logics. (shrink)

\(\nabla \) -algebra is a natural generalization of Heyting algebra, unifying many algebraic structures including bounded lattices, Heyting algebras, temporal Heyting algebras and the algebraic presentation of the dynamic topological systems. In a series of two papers, we will systematically study the algebro-topological properties of different varieties of \(\nabla \) -algebras. In the present paper, we start with investigating the structure of these varieties by characterizing their subdirectly irreducible and simple elements. Then, we prove the closure of (...) these varieties under the Dedekind-MacNeille completion and provide the canonical construction and the Kripke representation for \(\nabla \) -algebras by which we establish the amalgamation property for some varieties of \(\nabla \) -algebras. In the sequel of the present paper, we will complete the study by covering the logics of these varieties and their corresponding Priestley-Esakia and spectral duality theories. (shrink)

Restricted to first-order formulas, the rules of inference in the Curry-Howard type theory are equivalent to those of first-order predicate logic as formalized by Heyting, with one exception: ∃-elimination in the Curry-Howard theory, where ∃x : A.F (x) is understood as disjoint union, are the projections, and these do not preserve firstorderedness. This note shows, however, that the Curry-Howard theory is conservative over Heyting’s system.

In this paper, we study (open) filters and deductive systems of self-distributive weak Heyting algebras (SDWH-algebras) and obtain some results which determine the relationship between them. We show that the variety of SDWH-algebras is not weakly regular and every open filter is the kernel of at least one congruence relation. Then it presents necessary and sufficient conditions for the existence of a one to one correspondence between open filters and congruence relations.

The purpose of this paper is to connect the proof theory and the model theory of a family of propositional logics weaker than Heyting's. This family includes systems analogous to the Lambek calculus of syntactic categories, systems of relevant logic, systems related toBCK algebras, and, finally, Johansson's and Heyting's logic. First, sequent-systems are given for these logics, and cut-elimination results are proved. In these sequent-systems the rules for the logical operations are never changed: all changes are made in (...) the structural rules. Next, Hubert-style formulations are given for these logics, and algebraic completeness results are demonstrated with respect to residuated lattice-ordered groupoids. Finally, model structures related to relevant model structures (of Urquhart, Fine, Routley, Meyer, and Maksimova) are given for our logics. These model structures are based on groupoids parallel to the sequent-systems. This paper lays the ground for a kind of correspondence theory for axioms of logics with implication weaker than Heyting's, a correspondence theory analogous to the correspondence theory for modal axioms of normal modal logics.The first part of the paper, which follows, contains the first two sections, which deal with sequent-systems and Hubert-formulations. The second part, due to appear in the next issue of this journal, will contain the third section, which deals with groupoid models. (shrink)

Brouwer's criticism of mathematical proofs making essential use of the tertium non datur had a surprisingly late response in logical circles. Among the diverse reactions in the mid 1920s and early 1930s, it is possible to delimit a coherent body of opinions on these questions: (1) whether Brouwer's denial of the tertium non datur meant only the abandonment of this classical law or, beyond that, the affirmation of its negation; (2) whether one or both of these alternatives were logically inconsistent; (...) and (3) whether Brouwer's line of argument was forced to take resort to the very law it was designed to refute. The controversy centred around a series of articles by Marcel Barzin and Alfred Errera who fought against the intuitionistic critique, missed their victory because of conceptual confusions and fallacious reasoning, but emerged unconvinced from the debate in the late 1930s. The controversy is of interest to the historiography of formal logic since it stimulated the clarification not only of the concepts of formal validity, decidability, many-valued systems of logic and non-classical systems generally, but also of the distinction between object and meta-level, and between a formal system and its semantics. Most important, the debate, by putting pressure on the intuitionistic camp to make their ideas more precise, seems to have given the decisive motivation towards Heyting's answer to this demand by his axiomatization of intuitionistic logic in 1930. (shrink)

The purpose of this paper is to connect the proof theory and the model theory of a family of prepositional logics weaker than Heyting's. This family includes systems analogous to the Lambek calculus of syntactic categories, systems of relevant logic, systems related to BCK algebras, and, finally, Johansson's and Heyting's logic. First, sequent-systems are given for these logics, and cut-elimination results are proved. In these sequent-systems the rules for the logical operations are never changed: all changes are made (...) in the structural rules. Next, Hilbert-style formulations are given for these logics, and algebraic completeness results are demonstrated with respect to residuated lattice-ordered groupoids. Finally, model structures related to relevant model structures (of Urquhart, Fine, Routley, Meyer, and Maksimova) are given for our logics. These model structures are based on groupoids parallel to the sequent-systems. This paper lays the ground for a kind of correspondence theory for axioms of logics with implication weaker than Heyting's, a correspondence theory analogous to the correspondence theory for modal axioms of normal modal logics.Below is the sequel to the first part of the paper, which appeared in the previous issue of this journal (vol. 47 (1988), pp. 353–386). The first part contained sections on sequent-systems and Hilbert-formulations, and here is the third section on groupoid models. This second part is meant to be read in conjunction with the first part. (shrink)

In order to modelize the reasoning of an intelligent agent represented by a poset T, H. Rasiowa introduced logic systems called “Approximation Logics”. In these systems a set of constants constitutes a fundamental tool. In this papers, we consider logic systems called L′T without this kind of constants but limited to the case where T is a finite poset. We prove a weak deduction theorem. We introduce also an algebraic semantics using Hey ting algebra with operators. To prove the completeness (...) theorem of the L′T system with respect to the algebraic semantics, we use the method of H. Rasiowa and R. Sikorski for first order logic. In the propositional case, a corollary allows us to assert that it is decidable to know “if a propositional formula is valid”. We study also certain relations between the L′T logic and the intuitionistic and classical logics. (shrink)

This paper proves some independence results for weak fragments of Heyting arithmetic by using Kripke models. We present a necessary condition for linear Kripke models of arithmetical theories which are closed under the negative translation and use it to show that the union of the worlds in any linear Kripke model of HA satisfies PA. We construct a two-node PA-normal Kripke structure which does not force iΣ2. We prove i∀1 ⊬ i∃1, i∃1 ⊬ i∀1, iΠ2 ⊬ iΣ2 and iΣ2 (...) ⊬ iΠ2. We use Smorynski's operation Σ′ to show HA ⊬ lΠ1. (shrink)

We build a topological model, based on intuitionistic logic, for multi-agent biological systems (such as _Physarum polycephalum_, bacterial colonies or any other swarm), reacting to external nourishment stimuli. Our construction follows the topological description of brain activity, where particles (neurons) are activated by an external environment, represented by a topological space _X_ with an open cover \(\{U_i:i\in I\}\). The brain builds the model of this external space via the nerve (trace) of a topological space _X_. Here the body of _Physarum (...) polycephalum_ or a swarm made of networks of tubular structures represents a nerve (trace) of _X_ also which means that _Physarum polycephalum_ or a swarm gains orientation in the space of external stimuli even in the absence of any neural system. The logic of living organisms is based on open subsets of _X_ and thus can be represented by Heyting algebra (i.e. intuitionistically). We also consider the generalisation of the nerve construction to a categorical context, where the category is determined by the network structures of multi-agent biological system. This model can be generalised up to simulating the behaviour of any swarm by means of intuitionistic logic. (shrink)

This paper investigates various interpretations of HPC (Heyting's predicate calculus) and mainly of HPC0 (Heyting's propositional calculus) in Post systems.§1 recalls some background material concerning HPC including the Kripke and Beth interpretations, and later sections study the various interpretations available.

A decade ago, Isham and Butterfield proposed a topos-theoretic approach to quantum mechanics, which meanwhile has been extended by Döring and Isham so as to provide a new mathematical foundation for all of physics. Last year, three of the present authors redeveloped and refined these ideas by combining the C*-algebraic approach to quantum theory with the so-called internal language of topos theory (Heunen et al. in arXiv:0709.4364). The goal of the present paper is to illustrate our abstract setup through the (...) concrete example of the C*-algebra M n (ℂ) of complex n×n matrices. This leads to an explicit expression for the pointfree quantum phase space Σ n and the associated logical structure and Gelfand transform of an n-level system. We also determine the pertinent non-probabilisitic state-proposition pairing (or valuation) and give a very natural topos-theoretic reformulation of the Kochen–Specker Theorem.In our approach, the nondistributive lattice ℘(M n (ℂ)) of projections in M n (ℂ) (which forms the basis of the traditional quantum logic of Birkhoff and von Neumann) is replaced by a specific distributive lattice $\mathcal{O}(\Sigma_{n})$ of functions from the poset $\mathcal{C}(M_{n}(\mathbb{C}))$ of all unital commutative C*-subalgebras C of M n (ℂ) to ℘(M n (ℂ)). The lattice $\mathcal{O}(\Sigma_{n})$ is essentially the (pointfree) topology of the quantum phase space Σ n , and as such defines a Heyting algebra. Each element of $\mathcal{O}(\Sigma_{n})$ corresponds to a “Bohrified” proposition, in the sense that to each classical context $C\in\mathcal{C}(M_{n}(\mathbb{C}))$ it associates a yes-no question (i.e. an element of the Boolean lattice ℘(C) of projections in C), rather than being a single projection as in standard quantum logic. Distributivity is recovered at the expense of the law of the excluded middle (Tertium Non Datur), whose demise is in our opinion to be welcomed, not just in intuitionistic logic in the spirit of Brouwer, but also in quantum logic in the spirit of von Neumann. (shrink)

Sahlqvist theory is extended to the fragments of the intuitionistic propositional calculus that include the conjunction connective. This allows us to introduce a Sahlqvist theory of intuitionistic character amenable to arbitrary protoalgebraic deductive systems. As an application, we obtain a Sahlqvist theorem for the fragments of the intuitionistic propositional calculus that include the implication connective and for the extensions of the intuitionistic linear logic.

The logic of the weak law of excluded middleKC p is obtained by adding the formula A A as an axiom scheme to Heyting's intuitionistic logicH p . A cut-free sequent calculus for this logic is given. As the consequences of the cut-elimination theorem, we get the decidability of the propositional part of this calculus, its separability, equality of the negationless fragments ofKC p andH p , interpolation theorems and so on. From the proof-theoretical point of view, the formulation (...) presented in this paper makes clearer the relations betweenKC p ,H p , and the classical logic. In the end, an interpretation of classical propositional logic in the propositional part ofKC p is given. (shrink)

We give an equivalent formulation of topological algebras, interpreting S4, as boolean algebras equipped with intuitionistic negation. The intuitionistic substructure—Heyting algebra—of such an algebra can be then seen as an “epistemic subuniverse”, and modalities arise from the interaction between the intuitionistic and classical negations or, we might perhaps say, between the epistemic and the ontological aspects: they are not relations between arbitrary alternatives but between intuitionistic substructures and one common world governed by the classical (propositional) logic. As an example (...) of the generality of the obtained view, we apply it also to S5. We give a sound, complete and decidable sequent calculus, extending a classical system with the rules for handling the intuitionistic negation, in which one can prove all classical, intuitionistic and S4 valid sequents. (shrink)

This paper examines the relationships between the many-valued logics G~ and Gn~ of Esteva, Godo, Hajek, and Navara, i.e., Godel logic G enriched with Łukasiewicz negation, and neighbors of intuitionistic logic. The popular fragments of Rauszer's Heyting-Brouwer logic HB admit many-valued extensions similar to G which may likewise be enriched with Łukasiewicz negation; the fuzzy extensions of these logics, including HB, are equivalent to G ~, as are their n-valued extensions equivalent to Gn~ for any n ≥ 2. These (...) enriched systems extend Wansing's logic I4C4, showing that Łukasiewicz negation is a species of Nelson's negation of constructible falsity and yielding a Kripke-style semantics for G~ and Gn~ to complement the many-valued semantics. (shrink)

Heyting is considered to be the first individual to place the previously informal logic of the Intuitionist movement on a rigorous formal foundation; he is probably the most likely candidate one might select for a book about Intuitionism. The first edition appeared in 1956, and the revisions have been brief. Only the seventh of eight sections deals with the Intuitionistic formulation of sentential and predicate logics; the first chapter is in the form of a dialogue among an Intuitonist [[sic]], (...) Logicist, Formalist, and several supporting characters; this discussion is predominantly philosophical and deals with various views concerning the foundations of mathematics. The five succeeding chapters consider first arithmetic, spreads and species, algebra, plane pointspecies, measure and integration. The last chapter considers two controversial subjects—infinitely proceeding sequences and negationless mathematics. There is a bibliography containing references of recent as well as classical articles, an index and glossary of symbols. The reader with a classical mathematical intuition will have sticky going in certain sections and should take care not to conflate his own notions with those of the author; Intuitionism and its attendant mathematics are not merely formal systems or philosophies of mathematics, they are a way of thinking. (shrink)

We present axiom systems, and provide soundness and strong completeness theorems, for classes of Kripke models with restricted extension rules among the node structures of the model. As examples we present an axiom system for the class of cofinal extension Kripke models, and an axiom system for the class of end-extension Kripke models. We also show that Heyting arithmetic is strongly complete for its class of end-extension models. Cofinal extension models of HA are models of Peano arithmetic.

Elementary set theory accustoms the students to mathematical abstraction, includes the standard constructions of relations, functions, and orderings, and leads to a discussion of the various orders of infinity. The material on logic covers not only the standard statement logic and first-order predicate logic but includes an introduction to formal systems, axiomatization, and model theory. The section on algebra is presented with an emphasis on lattices as well as Boolean and Heyting algebras. Background for recent research in natural language (...) semantics includes sections on lambda-abstraction and generalized quantifiers. Chapters on automata theory and formal languages contain a discussion of languages between context-free and context-sensitive and form the background for much current work in syntactic theory and computational linguistics. The many exercises not only reinforce basic skills but offer an entry to linguistic applications of mathematical concepts. For upper-level undergraduate students and graduate students in theoretical linguistics, computer-science students with interests in computational linguistics, logic programming and artificial intelligence, mathematicians and logicians with interests in linguistics and the semantics of natural language. (shrink)

A deductive system is said to be structurally complete if its admissible rules are derivable. In addition, it is called hereditarily structurally complete if all its extensions are structurally complete. Citkin (1978) proved that an intermediate logic is hereditarily structurally complete if and only if the variety of Heyting algebras associated with it omits five finite algebras. Despite its importance in the theory of admissible rules, a direct proof of Citkin’s theorem is not widely accessible. In this paper (...) we offer a self-contained proof of Citkin’s theorem, based on Esakia duality and the method of subframe formulas. As a corollary, we obtain a short proof of Citkin’s 2019 characterization of hereditarily structurally complete positive logics. (shrink)

In earlier work we introduced two systems for nonstandard analysis, one based on classical and one based on intuitionistic logic; these systems were conservative extensions of first-order Peano and Heyting arithmetic, respectively. In this paper we study how adding the principle of countable saturation to these systems affects their proof-theoretic strength. We will show that adding countable saturation to our intuitionistic system does not increase its proof-theoretic strength, while adding it to the classical system increases the strength (...) from first- to full second-order arithmetic. (shrink)

We prove that every finitely axiomatizable extension of Heyting's intuitionistic logic has a corresponding cut-free Gentzen-type formulation. It is shown how one can use this result to find the corresponding normalizable natural deduction system and to give a criterion for separability of considered logic. Obviously, the question how to obtain an effective definition of a sequent calculus which corresponds to a concrete logic remains a separate problem for every logic.

Gödel interpreted Heyting arithmetic HA in a “logic-free” fragment T 0 of his theory T of primitive recursive functionals of finite types by his famous Dialectica-translation D . This works because the logic of HA is extremely simple. If the logic of the interpreted system is different—in particular more complicated—, it forces us to look for different and more complicated functional translations. We discuss the arising logical problems for arithmetical and set theoretical systems from HA to CZF . (...) We want to test the thesis: While the functionals take care of the proof theoretic strength of the interpreted system, it is the functional translation that has to cope with the logical complexities of the system. (shrink)

In this paper we define a family of many-valued semantics for hybrid logic, where each semantics is based on a finite Heyting algebra of truth-values. We provide sound and complete tableau systems for these semantics. Moreover, we show how the tableau systems can be made terminating and thereby give rise to decision procedures for the logics in question. Our many-valued hybrid logics turn out to be "intermediate" logics between intuitionistic hybrid logic and classical hybrid logic in a specific sense (...) explained in the paper. Our results show that many-valued hybrid logic is indeed a natural enterprise. (shrink)

One of the main problems in computer science is to ensure that programs are implemented in such a way that they satisfy a given specification. There are many studies about methods to prove correctness of programs. This work presents a method, belonging to the constructive synthesis or proofs-as-programs paradigm, that comes from the Curry-Howard isomorphism and extracts the computational contents of intuitionist proofs. The synthesis process proposed produces a program in an imperative language from a proof in many-sorted intuitionist logic, (...) where the axioms define the abstract data types, using Natural Deduction as deductive system. It is proved the correctness, as well as the completeness of the method regarding the Heyting arithmetic with ω-rule . A discussion about the use of the finitary induction instead of computational ω-rule concludes the work. (shrink)

This book gives a detailed treatment of functional interpretations of arithmetic, analysis, and set theory. The subject goes back to Gödel's Dialectica interpretation of Heyting arithmetic which replaces nested quantification by higher type operations and thus reduces the consistency problem for arithmetic to the problem of computability of primitive recursive functionals of finite types. Regular functional interpretations, i.e. Dialectica and Diller-Nahm interpretation as well as Kreisel's modified realization, together with their Troelstra-style hybrids, are applied to constructive as well as (...) classical systems of arithmetic, analysis, and set theory. They yield relative consistency and conservativity results and closure under relevant rules of the theories in question as well as axiomatic characterizations of the functional translations. Prerequisites are: familiarity with classical and intuitionistic predicate logic, basics of computability theory, Gödel's incompleteness theorems. (shrink)

It is shown that axiomatic extensions of intuitionistic propositional calculus defining univocally new connectives, including those proposed by Gabbay, are strongly complete with respect to valuations in Heyting algebras with additional operations. In all cases, the double negation of such a connective is equivalent to a formula of intuitionistic calculus. Thus, under the excluded third law it collapses to a classical formula, showing that this condition in Gabbay's definition is redundant. Moreover, such connectives can not be interpreted in all (...) Heyting algebras, unless they are already equivalent to a formula of intuitionistic calculus. These facts relativize to connectives over intermediate logics. In particular, the intermediate logic with values in the chain of length n may be "completed" conservatively by adding a single unary connective, so that the expanded system does not allow further axiomatic extensions by new connectives. (shrink)

In the 1920s Heyting attempted at axiomatizing constructive geometry. Recently, von Plato used different concepts to axiomatize it. He used 14 axioms to formulate constructive apartness geometry, seven of which have occurrences of negation. In this paper we show with the help of ANDP, a theorem prover based on natural deduction, that four new axioms without negation, shorter and more intuitive, can replace seven of von Plato's 14 ones. Thus we obtained a near negation-free new system consisting of (...) 11 axioms. (shrink)

We use formal semantic analysis based on new constructions to study abstract realizability, introduced by Läuchli in 1970, and expose its algebraic content. We claim realizability so conceived generates semantics-based intuitive confidence that the Heyting Calculus is an appropriate system of deduction for constructive reasoning.Well-known semantic formalisms have been defined by Kripke and Beth, but these have no formal concepts corresponding to constructions, and shed little intuitive light on the meanings of formulae. In particular, the completeness proofs for (...) these semantics do not generate confidence in the sufficiency of the Heyting Calculus, since we have no reason to believe that every intuitively constructive truth is valid in the formal semantics.Läuchli has proved completeness for a realizability semantics with formal concepts analogous to constructions. We argue in some detail that, in spite of a certain inherent inexactness of the analogy, every intuitively constructive truth is valid in Läuchli semantics, and therefore the Heyting Calculus is powerful enough to prove all constructive truths. Our argument is based on the postulate that a uniformly constructible object must be communicable in spite of imprecision in our language, and that the permutations in Läuchli's semantics represent conceivable imprecision in a language, while allowing a certain amount of freedom in choosing the particular structure of the language.We give a detailed generalization of Läuchli's proof of completeness for the propositional part of the Heyting Calculus, in order to make explicit constructive and algebraic content.In our treatment, we establish several new results about Läuchli models. We show how to extend the sconing and gluing constructions familiar from Kripke and Frame semantics and Topos theory, to Läuchli models, and use them to give an algebraic approach to countermodel construction. In particular, the Läuchli arguments are given without the restriction to the integers, Z, as a group of permutations, which makes much of the coding scheme used in Läuchli's original paper transparent.We also make use of a new propositions-as-types syntax for the Heyting calculus, with limited nondeterminism, in which validity of formulae can be decided without loop-detection. (shrink)

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)

As far as logic is concerned, the conclusion of Michael Dummett's manifestability argument is that intuitionistic logic, as first developed by Heyting, satisfies the semantic requirements of antirealism. The argument may be roughly sketched as follows: since we cannot manifest a grasp of possibly justification-transcendent truth conditions, we must countenance conditions which are such that, at least in principle and by the very nature of the case, we are able to recognize that they are satisfied whenever they are. Intuitionistic (...) logic satisfies the semantic requirement that we should either eschew the notion of truth altogether and replace it by provability in principle, or constrain it by provability in principle (Dummett [1973] 1978). (Handout: 1-5). Some philosophers have argued that the traditional antirealist desideratum of decidability in principle is too weak, so that semantic antirealism properly construed must be committed to effective decidability. As such, it either leads to strict finitism (Wright [1982] 1993) [Handout: 6] or to a much stronger kind of logical revisionism than the one considered by intuitionists (whether or not they accept the manifestability argument): substructural logics, and in particular linear logics, rather than intuitionistic logic, satisfy the semantic requirements of strict antirealism (Dubucs and Marion 2004) [Handout: 8-9]. I shall develop two different kinds of replies. The first is concerned with the notion of meaning per se and looks to strict finitism directly, although not on the ground that it would provide a correct way of dealing with Soritic-type paradoxes (the original and primary focus of discussion in Wright [1982] 1993). The second is concerned with the justification of structural and logical rules in a natural deduction system à la Gentzen. It will deal in particular with the criticism of the structural rules of Weakening and Contraction [Handout: 10 and 11]. The first kind of reply, which Dummett has partially taken into consideration, is that if we jettison the effectively vs. in principle distinction, as applied to manifestability-type arguments, we end up with an unsatisfactory explanation of how the meaning of statements covering the practically unsurveyable or pro tempora undecided cases is fixed. The idea is that if we have a method which may be used over some small range, we have determined a way of applying the method everywhere in principle and that this is enough as far as fixing meaning is concerned. Decidability in principle is just what we need with respect to manifestation of grasp of meaning. In this perspective, antirealism shouldn't be strict and manifestability-type arguments need not be applied as far as the strict finitist would want to [Handout: 7]. It follows that there is no reason to think that practical feasibility should be built in assertibility conditions and proofs be construed dynamically as acts in the strict antirealist's acception of that term [Handout: 8]. I shall then look at one radical antirealist principle disqualifying structural rules, namely Token Preservation, arguing against Bonnay and Cozic's criticisms of Dubucs and Marion (Bonnay and Cozic 3 2007) that some conceptual support may be provided for Token Preservation, which doesn't rely on a causal misreading of the turnstile [Handout: 13, 14]. I shall then assess the merits and limits of radical antirealism and the logic of feasible proofs with respect to the original Dummettian argument in favour of semantic antirealism (provided it has indeed revisionist implications for logic), whether the radical antirealist merely stipulates what human feasibility amounts to, or dispenses with structural rules in order to argue in favour of a curb on the epistemic idealizations they unwarrantedly embed. It will be noted here that there is a great difference, conceptually speaking, between the rejection of classical logic via the curbing of the epistemic idealizations embedded in structural rules, and the rejection of classical logic via the criticism of the introduction and elimination rules which fix the meaning of the classical constants. The kind of logical revisionism envisaged by intuitionists from Heyting on is in many respects stronger than the one envisaged by advocates of linear logic, should they ground their arguments on an endorsement of strict antirealism. The crucial case of excluded middle is telling. Because of the splitting of the constants in linear logic (Handout: 12], two distinct laws of excluded middle may be formulated (Handout: 15), but the traditional arguments of Brouwer and Heyting against the classical law yield a stronger revision than the substructural revision with its admission of these two (very) weak versions of the law. (Project: a clearer conception is needed of how the introduction and elimination rules for the logical connectives in the intuitionistic calculus depend on the structural rules which the radical antirealist wishes to reject.). (shrink)

In Coecke (2002) we proposed the intuitionistic or disjunctive representation of quantum logic, i.e., a representation of the property lattice of physical systems as a complete Heyting algebra of logical propositions on these properties, where this complete Heyting algebra goes equipped with an additional operation, the operational resolution, which identifies the properties within the logic of propositions. This representation has an important application towards dynamic quantum logic, namely in describing the temporal indeterministic propagation of actual properties of physical (...) systems. This paper can as such by conceived as an addendum to Quantum Logic in Intuitionistic Perspective that discusses spin-off and thus provides an additional motivation. We derive a quantaloidal semantics for dynamic disjunctive quantum logic and illustrate it for the particular case of a perfect (quantum) measurement. (shrink)

A method of developing a relational semantics and relational proof systems for many-valued logics based on finite algebras of truth values is presented. The method is applied to Rosser-Turquette logic, logics based on symmetric Heyting algebras with operators and a Post-style logic.

Brouwer's views on the foundations of mathematics have inspired the study of intuitionistic logic, including the study of the intuitionistic propositional calculus and its extensions. The theory of these systems has become an independent branch of logic with connections to lattice theory, topology, modal logic and other areas. This paper aims to present a modern account of semantics for intuitionistic propositional systems. The guiding idea is that of a hierarchy of semantics, organized by increasing generality: from the least general Kripke (...) semantics on through Beth semantics, topological semantics, Dragalin semantics, and finally to the most general algebraic semantics. While the Kripke, topological, and algebraic semantics have been extensively studied, the Beth and Dragalin semantics have received less attention. We bring Beth and Dragalin semantics to the fore, relating them to the concept of a nucleus from pointfree topology, which provides a unifying perspective on the semantic hierarchy. (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)

In the present paper I wish to regard constructivelogic as a self-contained system for the treatment ofepistemological issues; the explanations of theconstructivist logical notions are cast in anepistemological mold already from the outset. Thediscussion offered here intends to make explicit thisimplicit epistemic character of constructivism.Particular attention will be given to the intendedinterpretation laid down by Heyting. This interpretation, especially as refined in the type-theoretical work of Per Martin-Löf, puts thesystem on par with the early efforts of Frege andWhitehead-Russell. (...) This quite recent work, however,has proved valuable not only in the philosophy andfoundations of mathematics, but has also foundpractical application in computer science, where thelanguage of constructivism serves as an implementableprogramming language, and within the philosophy oflanguage.\footnote{Nordstr\"{o}m et al. give an overview of the work in computerscience, whereas Ranta provides an impressiveconstructivist alternative to Montague Grammar usingthe richer type structure of Martin-L\"{o}f in placeof the simple classical type theory of Church.} Mypresentation will be carried out through a contrastwith standard metamathematical work.\footnote{Troelstra and van Dalen give an encyclopedictreatment of the metamathematics of constructivism.}In the course of the development I have occasion tooffer some novel considerations on thenature of proof and inference. (shrink)

On the base of the classical logic the connectives of necessity and possibility have the equivalent positions in this sense that each of them is definable by the other one. The consequence of this fact is the possibility to define of the both modalities using the connective of identity. Thus, the connective of propositional identity defining the congruence of the propositional language has become the base of the reconstruction of necessity operator in some modal systems. Already in 1957 Greniewski [9] (...) obtained system S5 on the base of the propositional calculus with identity. Next, Cresswell [3], [4] reconstructed S4 and S5 in a similar way. Systematic investigations of this problem were undertaken by Suszko within the broader frame of SCI programme [16], [17], [18]. The connections between modal connectives and the connective of identity settle some philosophical sense of both modalities. Something is necessary, if it is identical with a logical truth. If something is different from the negation of some logical truth, it is possible. It is however, the “ontological” characteristics typical for modalities defined on the base of the classical logic. The settling of similar connections between intuitionistic identity and intuitionistic modalities uncover the philosophical sense of the “epistemic” necessity and possibility. Unfortunately, the symmetry between the classical and intuitionistic case is not entire. The acceptance of both equalities: = ¬ ¬ and = ¬ ¬, in the intuitionistic logic yields the classical versions of both modalities . Thus, there is a problem with defining the connective of intuitionistic possibility by the connective of identity. In Sections 2 and 3 two “partial” solutions of the mentioned problem are presented. They are “partial” because the connective of possibility has undesirable properties. The second solution yields the strengthening of the necessity connective, too. The main aim of this paper is obtained in Section 5, where a definition of the intuitionistic possibility is given. This definition uses the new connective of nonidentity, presented in Section 4. The new approach bases on the idea that some connectives like implication, negation, identity, necessity are “Heyting's” ones. The case of possibility is different. Together with coimplication, weak negation, and nonidentity, possibility belongs to the so-called “Brouwerian” connectives. The connectives of the first kind have such property that in Kripke's style semantics their interpretations in each point of this semantics are related to the interpretations in next points. In the case of the “Brouwerian” connectives the interpretations in each point depend on the interpretations in previous points. In this sense, “Heyting's” connectives are interpreted from the point of view of the future, while the interpretations of the “Brouwerian” connectives are from the point of view of the past. The relations between nonidentity and possibility connectives allow to say that in temporal semantics something is possible in the moment a, if before a there was such moment b in which it was different from the contradiction. Thus, “something is possible” does not mean that it held once in the past. A broader philosophical remarks about the nature of intuitionistic possibility are contained in two Comments in the last Section. (shrink)

In classical logic, the proposition expressed by a sentence is construed as a set of possible worlds, capturing the informative content of the sentence. However, sentences in natural language are not only used to provide information, but also to request information. Thus, natural language semantics requires a logical framework whose notion of meaning does not only embody informative content, but also inquisitive content. This paper develops the algebraic foundations for such a framework. We argue that propositions, in order to embody (...) both informative and inquisitive content in a satisfactory way, should be defined as non-empty, downward closed sets of possibilities, where each possibility in turn is a set of possible worlds. We define a natural entailment order over such propositions, capturing when one proposition is at least as informative and inquisitive as another, and we show that this entailment order gives rise to a complete Heyting algebra, with meet, join, and relative pseudo-complement operators. Just as in classical logic, these semantic operators are then associated with the logical constants in a first-order language. We explore the logical properties of the resulting system and discuss its significance for natural language semantics. We show that the system essentially coincides with the simplest and most well-understood existing implementation of inquisitive semantics, and that its treatment of disjunction and existentials also concurs with recent work in alternative semantics. Thus, our algebraic considerations do not lead to a wholly new treatment of the logical constants, but rather provide more solid foundations for some of the existing proposals. (shrink)

We give a constructive analysis of learning as it arises in various computational interpretations of classical Peano Arithmetic, such as Aschieri and Berardi learning based realizability, Avigad’s update procedures and epsilon substitution method. In particular, we show how to compute in Gödel’s system T upper bounds on the length of learning processes, which are themselves represented in T through learning based realizability. The result is achieved by the introduction of a new non standard model of Gödel’s T, whose new (...) basic objects are pairs of non standard natural numbers and moduli of convergence, where the latter are objects giving constructive information about the former. As a foundational corollary, we obtain that that learning based realizability is a constructive interpretation of Heyting Arithmetic plus excluded middle over Σ10 formulas and of all Peano Arithmetic when combined with Gödel’s double negation translation. As a byproduct of our approach, we also obtain a new proof of Avigad’s theorem for update procedures and thus of the termination of the epsilon substitution method for PA. (shrink)

We investigate intuitionistic propositional modal logics in which a modal operator is equivalent to intuitionistic double negation. Whereas ¬¬ is divisible into two negations, is a single indivisible operator. We shall first consider an axiomatization of the Heyting propositional calculus H, with the connectives →,∧,∨ and ¬, extended with . This system will be called Hdn . Next, we shall consider an axiomatization of the fragment of H without ¬ extended with . This system will be called (...) Hdn + . We shall show that these systems are sound and complete with respect to specific classes of Kripke-style models with two accessibility relations, one intuitionistic and the other modal. This type of models is investigated in [2] and [3], and here we try to apply the techniques of these papers to an intuitionistic modal operator with a natural interpretation. The full results of our investigation will be published in [4] and [1]. (shrink)

The Curry-Howard isomorphism states an amazing correspondence between systems of formal logic as encountered in proof theory and computational calculi as found in type theory. For instance, minimal propositional logic corresponds to simply typed lambda-calculus, first-order logic corresponds to dependent types, second-order logic corresponds to polymorphic types, sequent calculus is related to explicit substitution, etc. The isomorphism has many aspects, even at the syntactic level: formulas correspond to types, proofs correspond to terms, provability corresponds to inhabitation, proof normalization corresponds to (...) term reduction, etc. But there is more to the isomorphism than this. For instance, it is an old idea---due to Brouwer, Kolmogorov, and Heyting---that a constructive proof of an implication is a procedure that transforms proofs of the antecedent into proofs of the succedent; the Curry-Howard isomorphism gives syntactic representations of such procedures. The Curry-Howard isomorphism also provides theoretical foundations for many modern proof-assistant systems (e.g. Coq). This book give an introduction to parts of proof theory and related aspects of type theory relevant for the Curry-Howard isomorphism. It can serve as an introduction to any or both of typed lambda-calculus and intuitionistic logic. Key features - The Curry-Howard Isomorphism treated as common theme - Reader-friendly introduction to two complementary subjects: Lambda-calculus and constructive logics - Thorough study of the connection between calculi and logics - Elaborate study of classical logics and control operators - Account of dialogue games for classical and intuitionistic logic - Theoretical foundations of computer-assisted reasoning · The Curry-Howard Isomorphism treated as the common theme. · Reader-friendly introduction to two complementary subjects: lambda-calculus and constructive logics · Thorough study of the connection between calculi and logics. · Elaborate study of classical logics and control operators. · Account of dialogue games for classical and intuitionistic logic. · Theoretical foundations of computer-assisted reasoning. (shrink)

Abstract. The aim of this paper is to show that the topological interpretation of knowledge as an interior kernel operator K of a topological space (X, OX) comes along with a partially ordered family of belief modalities B that fit K in the sense that the pairs (K, B) satisfy all axioms of Stalnaker’s KB logic of knowledge and belief with the exception of the contentious axiom of negative introspection (NI). The new belief modalities B introduced in this paper are (...) defined with the help of the (dense) nuclei of the Heyting algebra OX of open subsets on the topological space (X, OX). In this way, the natural context for the belief operators B related to topological knowledge operator K is shown to be the Heyting algebra NUC(OX) of the nuclei of the Heyting algebra OX.1 More precisely, the dense nuclei of NUC(OX) can be used to define a variety of bimodal logics of knowledge operators K and belief operators B. The operators K and B are compatible with each other in the sense that the pairs (K, B) satisfy all axioms of Stalnaker’s KB system with the exception of the axiom (NI). Therefore, for (X, OX), one obtains a bounded, partially ordered family of belief operators B defined by the elements of NUC(OX). (shrink)