We show that Intuitionistic Open Induction iop is not closed under the rule DNS(∃ - 1 ). This is established by constructing a Kripke model of iop + $\neg L_y(2y > x)$ , where $L_y(2y > x)$ is universally quantified on x. On the other hand, we prove that iop is equivalent with the intuitionistic theory axiomatized by PA - plus the scheme of weak ¬¬LNP for open formulas, where universal quantification on the parameters precedes double negation. We also show (...) that for any open formula φ(y) having only y free, $(PA^-)^i \vdash L_y\varphi(y)$ . We observe that the theories iop, i∀ 1 and iΠ 1 are closed under Friedman's translation by negated formulas and so under VR and IP. We include some remarks on the classical worlds in Kripke models of iop. (shrink)

That every first-order theory has a coherent conservative extension is regarded by some as obvious, even trivial, and by others as not at all obvious, but instead remarkable and valuable; the result is in any case neither sufficiently well-known nor easily found in the literature. Various approaches to the result are presented and discussed in detail, including one inspired by a problem in the proof theory of intermediate logics that led us to the proof of the present paper. It can (...) be seen as a modification of Skolem’s argument from 1920 for his “Normal Form” theorem. “Geometric” being the infinitary version of “coherent”, it is further shown that every infinitary first-order theory, suitably restricted, has a geometric conservative extension, hence the title. The results are applied to simplify methods used in reasoning in and about modal and intermediate logics. We include also a new algorithm to generate special coherent implications from an axiom, designed to preserve the structure of formulae with relatively little use of normal forms. (shrink)

In contemporary natural languages semantics one will often see the use of special brackets to enclose a linguistic expression, e.g. ⟦carrot⟧. These brackets---so-called denotation brackets or semantic evaluation brackets---stand for a function that maps a linguistic expression to its "denotation" or semantic value (perhaps relative to a model or other parameters). Even though this notation has been used in one form or another since the early development of natural language semantics in the 1960s and 1970s, Montague himself didn't make use (...) of this notation in his series of groundbreaking papers on semantics. That raises the question: When was the ⟦.⟧-notation introduced to semantics? This note answers that question. (shrink)

The rather unrestrained use of second-order logic in the neo-logicist program is critically examined. It is argued in some detail that it brings with it genuine set-theoretical existence assumptions and that the mathematical power that Hume’s Principle seems to provide, in the derivation of Frege’s Theorem, comes largely from the ‘logic’ assumed rather than from Hume’s Principle. It is shown that Hume’s Principle is in reality not stronger than the very weak Robinson Arithmetic Q. Consequently, only a few rudimentary facts (...) of arithmetic are logically derivable from Hume’s Principle. And that hardly counts as a vindication of logicism. (shrink)

I begin by drawing a parallel between the intuitionistic understanding of quantification over all natural numbers and the generality relativist understanding of quantification over absolutely everything. I then argue that adoption of an intuitionistic reading of relativism not only provides an immediate reply to the absolutist's charge of incoherence but it also throws a new light on the debates surrounding absolute generality.

In the first chapter, we discuss Dummett’s idea that the notion of truth arises from the one of the correctness of an assertion. We argue that, in a first-order language, the need of defining truth in terms of the notion of satisfaction, which is yielded by the presence of quantifiers, is structurally analogous to the need of a notion of truth as distinct from the one of correctness of an assertion. In the light of the analogy between predicates in Frege (...) and open formulas in Tarksi, we concentrate on the semantic status of predicates. We register a dual attitude of Dummett towards Frege’s ascription of reference to predicates. On the one it is needed to endow quantifiers with their appropriate meaning. On the other hand, the introduction of concepts, as semantic correlate of predicates, smuggles a realist flavor in the overall semantic picture. In concluding the excursus (and with it the chapter), we stress Dummett’s will of developing a semantic picture free from this realist trait. In the second chapter, we present the idea of a proof-theoretic semantics. As for Frege true sentences denotes the truth-value True, so here closed' (i.e. categorical) valid argumentations denotes proofs. If a language contains implication-like operators, in order to characterize the condition of validity of a closed argumentation one has to introduce a notion of validity applying to ‘open’ (i.e. hypothetical) argumentations. We argue that this problem is analogous to the one posed by quantifiers in Frege-Tarksi’s style semantics. That is, implication forces one to introduce notion of validity for argumentations, which is more substantial than the correctness of the assertion of their conclusions. As we saw, the corresponding claim in the truth-based approach—that quantifiers require one to introduce a notion of truth, which is more substantial than the one of an assertion being correct—was the source of realism. Hence, Dummett proposes to reduce the semantic contribution of open argumentations to the one of their ‘closed instances’. In the truth-based perspective, this would correspond to the denial of the need of introducing concepts as the semantic correlates of predicates. We argue that Dummett’s fear, that an irreducible notion of function (represented by the need of ascribing validity to open argumentations) would lead to realism, turns out to be ill-founded. In the third chapter, we discuss the role played by the notion of truth in the anti-realist account. The notion of truth is what the anti-realist needs to cope with the so-called paradox of deduction. The analysis of the paradox yields to distinguishing between the truth of a sentence and the truth of a sentence being recognized. In terms of these conceptual couple, we reconsider the relationship between truth and assertion in an anti-realist perspective. Grounds are provided for a thesis (which was already advanced in chapter two), according to which the notion of the assertion of a sentence being correct is primarily connected only with the canonical means of establishing a sentence. The possibility of establishing a sentence by indirect means is conceptually dependent on the practice of establishing logical relationship of dependence among sentences. That is, the notion of a closed valid non-canonical argumentation is of any theoretical relevance only in presence of a notion of validity applying to open argumentations. In the fourth chapter, we discuss the possibility of characterizing in the proof-theoretic-semantics a notion of refutation. We develop an original characterization of refutations starting from an informal inductive specification of the condition of refutations of logically complex sentences. A sub-structural logic, called dual-intuitionistic logic, stands to this notion in the same relationship in which intuitionistic logic stands to the notion of proof so far consdered. All notions developed in chapter 2 have their corresponding (dual) ones in the framework developed. In particular, the distinctions canonical/non-canonical and closed/open argumentations. In the refutation based perspective, elimination rules have priority over introductions and the (only) assumption over the (many) conclusions. In the conclusions, we indicate the ingredients that an anti-realist approach to meaning should incorporate, in order to avoid the difficulties we registered. The core of an alternative view is a different conception of the relationship between categorical and hypothetical notions, in which the validity of open argumentations is not reduced to that of their instances, but rather it is directly defined. As a limit case, one would get a notion of validity applying to closed argumentations. (shrink)

This article concerns the treatment of propositional quantification in a framework of labelled natural deduction for modal logic developed by Basin, Matthews and Viganò. We provide a detailed analysis of a basic calculus that can be used for a proof-theoretic rendering of minimal normal multimodal systems with quantification over stable domains of propositions. Furthermore, we consider variations of the basic calculus obtained via relational theories and domain theories allowing for quantification over possibly unstable domains of propositions. The main result of (...) the article is that fragments of the labelled calculi not exploiting reductio ad absurdum enjoy the Church–Rosser property and the strong normalization property; such result is obtained by combining Girard’s method of reducibility candidates and labelled languages of lambda calculus codifying the structure of modal proofs. (shrink)

RésuméAristote n'a pas développé une théorie de la quantification du prédicat, mais une étude récente de Hasnawi a montré qu'Ibn Sīnā a consacré à celle-ci une étude rigoureuse. Assumant la structure aristotélicienne sujet-prédicat, Ibn Sīnā qualifie les propositions qui comportent un prédicat quantifié, de propositions déviantes. Une conséquence de cette approche avicennienne est que la seconde quantification est absorbée par le prédicat. La distinction claire ainsi opérée entre un sujet quantifié, qui pose le domaine de la quantification, et une partie (...) prédicative, qui construit une proposition sur ce domaine, correspond structurellement à la distinction, faite dans la théorie constructive des types, entre le type des ensembles et le type des propositions.Aristote n'a pas non plus combiné son analyse logique de la quantification avec sa théorie ontologique des relations ou de l’égalité. Ibn Sīnā, en revanche, a utilisé les syllogismes qui nécessitent une logique de l’égalité et il a examiné des cas où la quantification se combine, via l’égalité, avec des termes singuliers. En outre, ces réflexions sont essentielles pour sa théorie des nombres qui est fondée sur l'interaction entre l’un et le multiple. Lorsqu'on combine la théorie métaphysique de l’égalité telle qu'on la trouve chez Ibn Sīnā avec son travail sur la quantification du prédicat, il en résulte tout naturellement une logique de l’égalité. En effet, l'interaction entre la quantification du prédicat et l’égalité peut être appliquée aux exemples de syllogismes mentionnés par Ibn Sīnā dans lesquels ces notions interviennent. En utilisant les instruments formels fournis par la théorie constructive des types de Martin-Löf, cet article établit des liens entre la métaphysique d'Ibn Sīnā et son travail logique, liens qui ont été discutés en relation avec d'autres sujets par Thom et Street. Ibn Sīnā n'a pas développé une logique de l'identité, mais il a développé les moyens conceptuels de le faire. (shrink)

The notion of strict identity is sometimes given an explicit second-order definition: objects with all the same properties are identical. Here, a somewhat different problem is raised: Under what conditions is the identity relation on the domain of a structure first-order definable? A structure may have objects that are distinct, but indiscernible by the strongest means of discerning them given the language (the indiscernibility formula). Here a number of results concerning the indiscernibility formula, and the definability of identity, are collected (...) and a number of applications discussed. (shrink)

A number of classical theories are interpreted in analogous theories that are based on intuitionistic logic. The classical theories considered include subsystems of first- and second-order arithmetic, bounded arithmetic, and admissible set theory.

A minimal theorem in a logic L is an L-theorem which is not a non-trivial substitution instance of another L-theorem. Komori (1987) raised the question whether every minimal implicational theorem in intuitionistic logic has a unique normal proof in the natural deduction system NJ. The answer has been known to be partially positive and generally negative. It is shown here that a minimal implicational theorem A in intuitionistic logic has a unique -normal proof in NJ whenever A is provable without (...) non-prime contraction. The non-prime contraction rule in NJ is the implication introduction rule whose cancelled assumption differs from a propositional variable and appears more than once in the proof. Our result improves the known partial positive solutions to Komori's problem. Also, we present another simple example of a minimal implicational theorem in intuitionistic logic which does not have a unique -normal proof in NJ. (shrink)

We investigate in intuitionistic first-order logic various principles of preference relations alternative to the standard ones based on the transitivity and completeness of weak preference. In particular, we suggest two ways in which completeness can be formulated while remaining faithful to the spirit of constructive reasoning, and we prove that the cotransitivity of the strict preference relation is a valid intuitionistic alternative to the transitivity of weak preference. Along the way, we also show that the acyclicity axiom is not finitely (...) axiomatizable in first-order logic. (shrink)

The paper provides a preliminary study of algebraic semantics for modal and superintuitionistic non-monotonic logics. The main question answered is: how can non-monotonic inference be understood algebraically?

Using the Hilbert-Bernays account as a spring-board, we first define four ways in which two objects can be discerned from one another, using the non-logical vocabulary of the language concerned. Because of our use of the Hilbert-Bernays account, these definitions are in terms of the syntax of the language. But we also relate our definitions to the idea of permutations on the domain of quantification, and their being symmetries. These relations turn out to be subtle---some natural conjectures about them are (...) false. We will see in particular that the idea of symmetry meshes with a species of indiscernibility that we will call `absolute indiscernibility'. We then report all the logical implications between our four kinds of discernibility. We use these four kinds as a resource for stating four metaphysical theses about identity. Three of these theses articulate two traditional philosophical themes: viz. the principle of the identity of indiscernibles, and haecceitism. The fourth is recent. Its most notable feature is that it makes diversity weaker than what we will call individuality : two objects can be distinct but not individuals. For this reason, it has been advocated both for quantum particles and for spacetime points. Finally, we locate this fourth metaphysical thesis in a broader position, which we call structuralism. We conclude with a discussion of the semantics suitable for a structuralist, with particular reference to physical theories as well as elementary model theory. (shrink)

Some authors have claimed that ante rem structuralism has problems with structures that have indiscernible places. In response, I argue that there is no requirement that mathematical objects be individuated in a non-trivial way. Metaphysical principles and intuitions to the contrary do not stand up to ordinary mathematical practice, which presupposes an identity relation that, in a sense, cannot be defined. In complex analysis, the two square roots of –1 are indiscernible: anything true of one of them is true of (...) the other. I suggest that ‘i’ functions like a parameter in natural deduction systems. I gave an early version of this paper at a workshop on structuralism in mathematics and science, held in the Autumn of 2006, at Bristol University. Thanks to the organizers, particularly Hannes Leitgeb, James Ladyman, and Øystein Linnebo, to my commentator Richard Pettigrew, and to the audience there. The paper also benefited considerably from a preliminary session at the Arché Research Centre at the University of St Andrews. I am indebted to my colleagues Craige Roberts, for help with the linguistics literature, and Ben Caplan and Gabriel Uzquiano, for help with the metaphysics. Thanks also to Hannes Leitgeb and Jeffrey Ketland for reading an earlier version of the manuscript and making helpful suggestions. I also benefited from conversations with Richard Heck, John Mayberry, Kevin Scharp, and Jason Stanley. CiteULike Connotea Del.icio.us What's this? (shrink)

Natural deduction is the type of logic most familiar to current philosophers, and indeed is all that many modern philosophers know about logic. Yet natural deduction is a fairly recent innovation in logic, dating from Gentzen and Jaśkowski in 1934. This article traces the development of natural deduction from the view that these founders embraced to the widespread acceptance of the method in the 1960s. I focus especially on the different choices made by writers of elementary textbooks—the standard conduits of (...) the method to a generation of philosophers—with an eye to determining what the ‘essential characteristics’ of natural deduction are. (shrink)

To save antirealism from Fitch's Paradox, Tennant has proposed to restrict the scope of the antirealist principle that all truths are knowable to truths that can be consistently assumed to be known. Although the proposal solves the paradox, it has been accused of doing so in an ad hoc manner. This paper argues that, first, for all Tennant has shown, the accusation is just; second, a restriction of the antirealist principle apparently weaker than Tennat's yields a non-ad hoc solution to (...) Fitch's Paradox; and third, the alternative is only apparently weaker than, and even provably equivalent to, Tennant's. It is thereby shown that the latter is not ad hoc after all. (shrink)

Kripke’s theory of truth, 690–716; 1975) has been very successful but shows well-known expressive difficulties; recently, Field has proposed to overcome them by adding a new conditional connective to it. In Field’s theories, desirable conditional and truth-theoretic principles are validated that Kripke’s theory does not yield. Some authors, however, are dissatisfied with certain aspects of Field’s theories, in particular the high complexity. I analyze Field’s models and pin down some reasons for discontent with them, focusing on the meaning of the (...) new conditional and on the status of the principles so successfully recovered. Subsequently, I develop a semantics that improves on Kripke’s theory following Field’s program of adding a conditional to it, using some inductive constructions that include Kripke’s one and feature a strong evaluation for conditionals. The new theory overcomes several problems of Kripke’s one and, although weaker than Field’s proposals, it avoids the difficulties that affect them; at the same time, the new theory turns out to be quite simple. Moreover, the new construction can be used to model various conceptions of what a conditional connective is, in ways that are precluded to both Kripke’s and Field’s theories. (shrink)

Ce bel ouvrage, clair, aéré et spacieux, se caractérise à la fois par sa volonté de simplicité d’accès, et son ambition, puisqu’on y trouve notamment une démonstration de la complétude d’un certain système déductif S1 pour la logique classique des prédicats, ainsi qu’une version synoptique du théorème de Gödel, selon lequel toute théorie du premier ordre complète axiomatisable est décidable, d’où il s’ensuit que l’arithmétique, c’est-à-dire l’ensemble des énoncés du premier ordre vrais dans, n’est pas axiomatisable; ce qu’on exprime souvent (...) en disant que tout système formel pour l’arithmétique est incomplet, au sens où il y a des énoncés vrais qui ne sont pas des théorèmes du système. (shrink)

Ce bel ouvrage, clair, aéré et spacieux, se caractérise à la fois par sa volonté de simplicité d’accès, et son ambition, puisqu’on y trouve notamment une démonstration de la complétude d’un certain système déductif S1 pour la logique classique des prédicats, ainsi qu’une version synoptique du théorème de Gödel, selon lequel toute théorie du premier ordre complète axiomatisable est décidable, d’où il s’ensuit que l’arithmétique, c’est-à-dire l’ensemble des énoncés du premier ordre vrais dans, n’est pas axiomatisable; ce qu’on exprime souvent (...) en disant que tout système formel pour l’arithmétique est incomplet, au sens où il y a des énoncés vrais qui ne sont pas des théorèmes du système. (shrink)

Fitch’s paradox shows, from fairly innocent-looking assumptions, that if there are any unknown truths, then there are unknowable truths. This is generally thought to deliver a blow to antirealist positions that imply that all truths are knowable. The present paper argues that a probabilistic version of antirealism escapes Fitch’s result while still offering all that antirealists should care for.

Primal infon logic was introduced in 2009 in connection with access control. In addition to traditional logic constructs, it contains unary connectives p said indispensable in the intended access control applications. Propositional primal infon logic is decidable in linear time, yet suffices for many common access control scenarios. The most obvious limitation on its expressivity is the failure of the transitivity law for implication: \$$ \to \$$ and \$$ \to \$$ do not necessarily yield \$$ \to \$$. Here we introduce (...) and investigate equiexpressive extensions TPIL and TPIL* of propositional primal infon logic as well as their quote-free fragments TPIL0 and TPIL0* respectively. We prove the subformula property for TPIL0* and a similar property for TPIL*; we define Kripke models for the four logics and prove the corresponding soundness-and-completeness theorems; we show that, in all these logics, satisfiable formulas have small models; but our main result is a quadratic-time derivation algorithm for TPIL*. (shrink)

Until is a notoriously difficult temporal operator as it is both existential and universal at the same time: A∪B holds at the current time instant w iff either B holds at w or there exists a time instant w' in the future at which B holds and such that A holds in all the time instants between the current one and ẃ. This “ambivalent” nature poses a significant challenge when attempting to give deduction rules for until. In this paper, in (...) contrast, we make explicit this duality of until by introducing a new temporal operator ∇ that allows us to formalize the “history” of until, i.e., the “internal” universal quantification over the time instants between the current one and ẃ. This approach provides the basis for formalizing deduction systems for temporal logics endowed with the until operator. For concreteness, we give here a labeled natural deduction system N(LTL∇) for a linear-time logic LTL∇ endowed with the new history operator. We show that LTL∇ is equivalent to the linear temporal logic LTL with until, which follows by formalizing back and forth translations between the two logics. We also define an indirect translation from LTL∇ into LTL via temporal logics with past operators; such a result provides an upper bound to the problem of satisfiability for LTL∇ formulas. (shrink)