Nominal logic is a variant of first-order logic in which abstract syntax with names and binding is formalized in terms of two basic operations: name-swapping and freshness. It relies on two important principles: equivariance (validity is preserved by name-swapping), and fresh name generation ("new" or fresh names can always be chosen). It is inspired by a particular class of models for abstract syntax trees involving names and binding, drawing on ideas from Fraenkel-Mostowski set theory: finite-support models in which each value (...) can depend on only finitely many names. Although nominal logic is sound with respect to such models, it is not complete. In this paper we review nominal logic and show why finite-support models are insufficient both in theory and practice. We then identify (up to isomorphism) the class of models with respect to which nominal logic is complete: ideal-supported models in which the supports of values are elements of a proper ideal on the set of names. We also investigate an appropriate generalization of Herbrand models to nominal logic. After adjusting the syntax of nominal logic to include constants denoting names, we generalize universal theories to nominal-universal theories and prove that each such theory has an Herbrand model. (shrink)

We present an inferentialist account of the epistemic modal operator might. Our starting point is the bilateralist programme. A bilateralist explains the operator not in terms of the speech act of rejection ; we explain the operator might in terms of weak assertion, a speech act whose existence we argue for on the basis of linguistic evidence. We show that our account of might provides a solution to certain well-known puzzles about the semantics of modal vocabulary whilst retaining classical logic. (...) This demonstrates that an inferentialist approach to meaning can be successfully extended beyond the core logical constants. (shrink)

The paper is devoted to the concise description of some Natural Deduction System (ND for short) for Linear Temporal Logic. The system's distinctive feature is that it is labelled and analytical. Labels convey necessary semantic information connected with the rules for temporal functors while the analytical character of the rules lets the system work as a decision procedure. It makes it more similar to Labelled Tableau Systems than to standard Natural Deduction. In fact, our solution of linearity representation is rather (...) independent of the underlying proof method, provided that some form of (analytic) cut is admissible. We will also discuss some generalisations of the system and compare it with other formalizations of linearity. (shrink)

In this paper we give a brief treatment of a theory of proofs for a system of Full Intuitionistic Linear Logic. This system is distinct from Classical Linear Logic, but unlike the standard Intuitionistic Linear Logic of Girard and Lafont includes the multiplicative disjunction par. This connective does have an entirely natural interpretation in a variety of categorical models of Intuitionistic Linear Logic. The main proof-theoretic problem arises from the observation of Schellinx that cut elimination fails outright for an intuitive (...) formulation of Full Intuitionistic Linear Logic; the nub of the problem is the interaction between par and linear implication. We present here a term assignment system which gives an interpretation of proofs as some kind of non-deterministic function. In this way we find a system which does enjoy cut elimination. The system is a direct result of an analysis of the categorical semantics, though we make an effort to present the system as if it were purely a proof-theoretic construction. (shrink)

An exclusive disjunction is true when exactly one of the disjuncts is true. In the case of the familiar binary exclusive disjunction, we have a formula occurring as the first disjunct and a formula occurring as the second disjunct, so, if what we have is two formula-tokens of the same formula-type—one formula occurring twice over, that is—the question arises as to whether, when that formula is true, to count the case as one in which exactly one of the disjuncts is (...) true, counting by type, or as a case in which two disjuncts are true, counting by token. The latter is the standard answer: counting by tokens. James McCawley once suggested that, when the exclusively disjunctive construction in natural language is at issue, the construction should be treated as involving a multigrade connective whose semantic treatment is sensitive to the set of disjuncts rather than the corresponding multiset. Without any commitment as to whether there actually is such a construction, and conceding that for obvious pragmatic reasons such ‘repeated disjunct’ cases would be at best highly marginal, we note that for the binary case, this requires a nonstandard answer—count by type rather than by token—to the earlier question, and thus, an idempotent exclusive disjunction connective. Section 2 explores that idea and Section 3, a further idempotent variant for which it is the propositions expressed by the disjuncts, rather than the disjuncts themselves, that get counted once only in the case of repetitions. Sections 1 and 4 respectively set the stage for these investigations and conclude the discussion. More detailed considerations of points arising from the discussion but otherwise in danger of interrupting the flow are deferred to a ‘Longer Notes’ appendix at the end. (shrink)

The interplay of introduction and elimination rules for propositional connectives is often seen as suggesting a distinguished role for intuitionistic logic. We prove three formal results concerning intuitionistic propositional logic that bear on that perspective, and discuss their significance. First, for a range of connectives including both negation and the falsum, there are no classically or intuitionistically correct introduction rules. Second, irrespective of the choice of negation or the falsum as a primitive connective, classical and intuitionistic consequence satisfy exactly the (...) same structural, introduction, and elimination (briefly, elementary) rules. Third, for falsum as primitive only, intuitionistic consequence is the least consequence relation that satisfies all classically correct elementary rules. (shrink)

A reduction rule is introduced as a transformation of proof figures in implicational classical logic. Proof figures are represented as typed terms in a -calculus with a new constant P (()). It is shown that all terms with the same type are equivalent with respect to -reduction augmented by this P-reduction rule. Hence all the proofs of the same implicational formula are equivalent. It is also shown that strong normalization fails for P-reduction. Weak normalization is shown for P-reduction with another (...) reduction rule which simplifies of (( ) ) into an atomic type. (shrink)

We investigate the development of terms during cut-elimination in first-order logic and Peano arithmetic for proofs of existential formulas. The form of witness terms in cut-free proofs is characterized in terms of structured combinations of basic substitutions. Based on this result, a regular tree grammar computing witness terms is given and a class of proofs is shown to have only elementary cut-elimination.

Gentzen’s and Jaśkowski’s formulations of natural deduction are logically equivalent in the normal sense of those words. However, Gentzen’s formulation more straightforwardly lends itself both to a normalization theorem and to a theory of “meaning” for connectives . The present paper investigates cases where Jaskowski’s formulation seems better suited. These cases range from the phenomenology and epistemology of proof construction to the ways to incorporate novel logical connectives into the language. We close with a demonstration of this latter aspect by (...) considering a Sheffer function for intuitionistic logic. (shrink)

The initial premise of this paper is that the structure of a proof is inherent in the definition of the proof. Side conditions to deal with the discharging of assumptions means that this does not hold for systems of natural deduction, where proofs are given by monotone inductive definitions. We discuss the idea of using higher order definitions and the notion of a functional closure as a foundation to avoid these problems. In order to focus on structural issues we introduce (...) a more abstract perspective, where a structural proof theory becomes part of a more general theory of functional closures. A notion of proof equations is discussed as a structural classifier and we compare the Russell and Ekman paradoxes to illustrate this. (shrink)

We study how to postpone the application of the reductio ad absurdum rule (RAA) in classical natural deduction. This technique is connected with two normalization strategies for classical logic, due to Prawitz and Seldin, respectively. We introduce a variant of Seldin’s strategy for the postponement of RAA, which induces a negative translation from classical to intuitionistic and minimal logic. Through this translation, Glivenko’s theorem from classical to intuitionistic and minimal logic is proven.

1. It is a fact that developing a good proof theory for modal logics is a difficult task. The problem is not in having deductive systems. In fact, all the main modal logics enjoy an axiomatic prese...

Glue semantics is a theory of the syntax–semantics interface according to which the syntactic structure of a sentence produces premises in a fragment of linear logic, and the semantic interpretation of the sentence correspond to the proof derivable from those premises. This paper describes how Glue can be connected to a Minimalist syntactic theory and compares the result with the more mainstream approach to the syntax–semantics interface in Minimalism, according to which the input to semantic interpretation is a syntactic structure (...) derived by covert movement operations. I argue that the Glue approach has advantages that make it worth exploring. (shrink)

We show that arbitrary tautologies of Johansson’s minimal propositional logic are provable by “small” polynomial-size dag-like natural deductions in Prawitz’s system for minimal propositional logic. These “small” deductions arise from standard “large” tree-like inputs by horizontal dag-like compression that is obtained by merging distinct nodes labeled with identical formulas occurring in horizontal sections of deductions involved. The underlying geometric idea: if the height, h(∂), and the total number of distinct formulas, ϕ(∂), of a given tree-like deduction ∂ of a minimal (...) tautology ρ are both polynomial in the length of ρ, |ρ|, then the size of the horizontal dag-like compression ∂ᶜ is at most h(∂)×ϕ(∂), and hence polynomial in |ρ|. That minimal tautologies ρ are provable by tree-like natural deductions ∂ with |ρ|-polynomial h(∂) and ϕ(∂) follows via embedding from Hudelmaier’s result that there are analogous sequent calculus deductions of sequent ⇒ρ. The notion of dag-like provability involved is more sophisticated than Prawitz’s tree-like one and its complexity is not clear yet. Our approach nevertheless provides a convergent sequence of NP lower approximations of PSPACE-complete validity of minimal logic. (shrink)

We present a proof of the equivalence between two deductive systems for constructive necessity, namely an axiomatic characterisation inspired by Hakli and Negri's system of derivations from assumptions for modal logic , a Hilbert-style formalism designed to ensure the validity of the deduction theorem, and the judgmental reconstruction given by Pfenning and Davies by means of a natural deduction approach that makes a distinction between valid and true formulae, constructively. Both systems and the proof of their equivalence are formally verified (...) using the state-of-the-art proof assistant Coq. The proof approach taken throughout the paper unveils the use of some alternative proof methods that allow for a smooth transition from the high-level mathematical proofs to their mechanised counterparts. (shrink)

Various possibilities, that one is dreaming, that one is being deceived by a deceitful demon, that one is a brain in the vat being stimulated to think one has a body and is in a regular world, have been invoked to show that all one's experience-based beliefs might be false. Descartes in Meditation I advises that in order not to lapse into his careless everyday view of things he, or at least his meditator, should pretend that all his experience-based beliefs, (...) indeed all his …. (shrink)

The calculus of Natural Calculation is introduced as an extension of Natural Deduction by proper term rules. Such term rules provide the capacity of dealing directly with terms in the calculus instead of the usual reasoning based on equations, and therefore the capacity of a natural representation of informal mathematical calculations. Basic proof theoretic results are communicated, in particular completeness and soundness of the calculus; normalisation is briefly investigated. The philosophical impact on a proof theoretic account of the notion of (...) meaning is considered. (shrink)

In this paper we study natural deduction for the intuitionistic and classical (normal) modal logics obtained from the combinations of the axioms T, B, 4 and 5. In this context we introduce a new multi-contextual structure, called T-sequent, that allows to design simple labelfree natural deduction systems for these logics. After proving that they are sound and complete we show that they satisfy the normalization property and consequently the subformula property in the intuitionistic case.

The pluralist sheds the more traditional ideas of truth and ontology. This is dangerous, because it threatens instability of the theory. To lend stability to his philosophy, the pluralist trades truth and ontology for rigour and other ‘fixtures’. Fixtures are the steady goal posts. They are the parts of a theory that stay fixed across a pair of theories, and allow us to make translations and comparisons. They can ultimately be moved, but we tend to keep them fixed temporarily. Apart (...) from considering rigour of proof as a fixture, I discuss fixed models, invariant notions and fixed information about objects across theories. There are other fixtures, but it is enough to start with these. (shrink)

This paper argues that adopting a particular dialogical account of logical consequence quite directly gives rise to an interesting form of logical pluralism, the form of pluralism in question arising out of the requirement that deductive proofs be explanatory.

The paper presents a proof-theoretic semantics (PTS) for a fragment of natural language, providing an alternative to the traditional model-theoretic (Montagovian) semantics (MTS), whereby meanings are truth-condition (in arbitrary models). Instead, meanings are taken as derivability-conditions in a dedicated natural-deduction (ND) proof-system. This semantics is effective (algorithmically decidable), adhering to the meaning as use paradigm, not suffering from several of the criticisms formulated by philosophers of language against MTS as a theory of meaning. In particular, Dummett’s manifestation argument does not (...) obtain, and assertions are always warranted, having grounds of assertion. The proof system is shown to satisfy Dummett’s harmony property, justifying the ND rules as meaning conferring. The semantics is suitable for incorporation into computational linguistics grammars, formulated in type-logical grammar. (shrink)

The paper suggests a revision of the notion of harmony, a major necessary condition in proof-theoretic semantics for a natural-deduction proof-system to qualify as meaning conferring, when moving to a bilateral proof-system. The latter considers both forces of assertion and denial as primitive, and is applied here to positive logics, lacking negation altogether. It is suggested that in addition to the balance between (positive) introduction and elimination rules traditionally imposed by harmony, a balance should be imposed also on: (i) negative (...) introduction and elimination rules, and (ii) positive and negative introduction rules. The paper suggests a proof-theoretical definition of duality (not referring to truthtables), using which double harmony is defined. The paper proves that in a doubly-harmonious system, the coordination rule, typical to bilateral systems, is admissible. (shrink)

The paper suggests a revision of the notion of harmony, a major necessary condition in proof-theoretic semantics for a natural-deduction proof-system to qualify as meaning conferring, when moving to a bilateral proof-system. The latter considers both forces of assertion and denial as primitive, and is applied here to positive logics, lacking negation altogether. It is suggested that in addition to the balance between introduction and elimination rules traditionally imposed by harmony, a balance should be imposed also on: negative introduction and (...) elimination rules, and positive and negative introduction rules. The paper suggests a proof-theoretical definition of duality, using which double harmony is defined. The paper proves that in a doubly-harmonious system, the coordination rule, typical to bilateral systems, is admissible. (shrink)

Inspired by the grammar of natural language, the paper presents a variant of first-order logic, in which quantifiers are not sentential operators, but are used as subnectors . A quantified term formed by a subnector is an argument of a predicate. The logic is defined by means of a meaning-conferring natural-deduction proof-system, according to the proof-theoretic semantics program. The harmony of the I/E-rules is shown. The paper then presents a translation, called the Frege translation, from the defined logic to standard (...) first-order logic, and shows that the proof-theoretic meanings of both logics coincide. The paper criticizes Frege’s original regimentation of quantified sentences of natural language, and argues for advantages of the proposed variant. (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)

We show how to interpret intuitionistic propositional logic into a predicative second-order intuitionistic propositional system having only the conditional and the universal second-order quantifier. We comment on this fact. We argue that it supports the legitimacy of using classical logic in a predicative setting, even though the philosophical cast of predicativism is nonrealistic. We also note that the absence of disjunction and existential quantifications allows one to have a process of normalization of proofs that avoids the use of "commuting conversions.".

We study an alternative embedding of IPC into atomic system F whose translation of proofs is based, not on instantiation overflow, but instead on the admissibility of the elimination rules for disjunction and absurdity. As compared to the embedding based on instantiation overflow, the alternative embedding works equally well at the levels of provability and preservation of proof identity, but it produces shorter derivations and shorter simulations of reduction sequences. Lambda-terms are employed in the technical development so that the algorithmic (...) content is made explicit, both for the alternative and the original embeddings. The investigation of preservation of proof-reduction steps by the alternative embedding enables the analysis of generation of “administrative” redexes. These are the key, on the one hand, to understand the difference between the two embeddings; on the other hand, to understand whether the final word on the embedding of IPC into atomic system F has been said. (shrink)

The idea of an ?inversion principle?, and the name itself, originated in the work of Paul Lorenzen in the 1950s, as a method to generate new admissible rules within a certain syntactic context. Some fifteen years later, the idea was taken up by Dag Prawitz to devise a strategy of normalization for natural deduction calculi (this being an analogue of Gentzen's cut-elimination theorem for sequent calculi). Later, Prawitz used the inversion principle again, attributing it with a semantic role. Still working (...) in natural deduction calculi, he formulated a general type of schematic introduction rules to be matched ? thanks to the idea supporting the inversion principle ? by a corresponding general schematic Elimination rule. This was an attempt to provide a solution to the problem suggested by the often quoted note of Gentzen. According to Gentzen ?it should be possible to display the elimination rules as unique functions of the corresponding introduction rules on the basis of certain requirements?. Many people have since worked on this topic, which can be appropriately seen as the birthplace of what are now referred to as ?general elimination rules?, recently studied thoroughly by Sara Negri and Jan von Plato. In this study, we retrace the main threads of this chapter of proof-theoretical investigation, using Lorenzen's original framework as a general guide. (shrink)

In this paper it is shown that addition of certain reductions to the standard cut removing reductions of deductions in prepositional logic makes prepositional logic non-normalizable. From this follows that some provable propositions in prepositional logic has no direct proof.

We describe a sequent calculus, based on work of Herbelin, of which the cut-free derivations are in 1-1 correspondence with the normal natural deduction proofs of intuitionistic logic. We present a simple proof of Herbelin's strong cut-elimination theorem for the calculus, using the recursive path ordering theorem of Dershowitz.

The paper is a defense of a strict form of anti-realism, competing the "in principle" form defended by Michael Dummett. It proposes to ground anti-realism on the basis of two principles ("immanence" and "implicitness") and to develop the consequences of these principles in the light of sub-structural logics.

This paper gives a simple method for providing categorial brands of feature-based unification grammars with a model-theoretic semantics. The key idea is to apply the paradigm of fibred semantics (or layered logics, see Gabbay (1990)) in order to combine the two components of a feature-based grammar logic. We demonstrate the method for the augmentation of Lambek categorial grammar with Kasper/Rounds-style feature logic. These are combined by replacing (or annotating) atomic formulas of the first logic, i.e. the basic syntactic types, by (...) formulas of the second. Modelling such a combined logic is less trivial than one might expect. The direct application of the fibred semantics method where a combined atomic formula like np (num: sg & pers: 3rd) denotes those strings which have the indicated property and the categorial operators denote the usual left- and right-residuals of these string sets, does not match the intuitive, unification-based proof theory. Unification implements a global bookkeeping with respect to a proof whereas the direct fibring method restricts its view to the atoms of the grammar logic. The solution is to interpret the (embedded) feature terms as global feature constraints while maintaining the same kind of fibred structures. For this adjusted semantics, the anticipated proof system is sound and complete. (shrink)

In standard model theory, deductions are not the things one models. But in general proof theory, in particular in categorial proof theory, one finds models of deductions, and the purpose here is to motivate a simple example of such models. This will be a model of deductions performed within an abstract context, where we do not have any particular logical constant, but something underlying all logical constants. In this context, deductions are represented by arrows in categories involved in a general (...) adjoint situation. To motivate the notion of adjointness, one of the central notions of category theory, and of mathematics in general, it is first considered how some features of it occur in set-theoretical axioms and in the axioms of the lambda calculus. Next, it is explained how this notion arises in the context of deduction, where it characterizes logical constants. It is shown also how the categorial point of view suggests an analysis of propositional identity. The problem of propositional identity, i.e., the problem of identity of meaning for propositions, is no doubt a philosophical problem, but the spirit of the analysis proposed here will be rather mathematical. Finally, it is considered whether models of deductions can pretend to be a semantics. This question, which as so many questions having to do with meaning brings us to that wall that blocked linguists and philosophers during the whole of the twentieth century, is merely posed. At the very end, there is the example of a geometrical model of adjunction. Without pretending that it is a semantics, it is hoped that this model may prove illuminating and useful. (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)

Intra-theoretical logical pluralism is a form of meaning-invariant pluralism about logic, articulated recently by Hjortland :355–373, 2013). This version of pluralism relies on it being possible to define several distinct notions of provability relative to the same logical calculus. The present paper picks up and explores this theme: How can a single logical calculus express several different consequence relations? The main hypothesis articulated here is that the divide between the internal and external consequence relations in Gentzen systems generates a form (...) of intra-theoretical logical pluralism. (shrink)

Proof-theoretic semantics is an alternative to model-theoretic semantics. It aims at explaining the meaning of the logical constants in terms of the inference rules that govern their behaviour in proofs. We argue that this must be construed as the task of explaining these meanings relative to a logic, i.e., to a consequence relation. Alas, there is no agreed set of properties that a relation must have in order to qualify as a consequence relation. Moreover, the association of a consequence relation (...) to a logical calculus is not as straightforward as it may seem. We show that these facts are problematic for the proof-theoretic project but the problems can be solved. Our thesis is that the consequence relation relevant for proof-theoretic semantics is the one given by the sequent-to-sequent derivability relation in Gentzen systems. (shrink)

Arguments, the story goes, have one or more premises and only one conclusion. A contentious generalisation allows arguments with several disjunctively connected conclusions. Contentious as this generalisation may be, I will argue nevertheless that it is justified. My main claim is that multiple conclusions are epiphenomena of the logical connectives: some connectives determine, in a certain sense, multiple-conclusion derivations. Therefore, such derivations are completely natural and can safely be used in proof-theoretic semantics.

In the original publication of the article, in Definition 4, the sixth line which reads as.

We present a categorical/denotational semantics for the Lambek Syntactic Calculus , indeed for a λlD-typed version Curry-Howard isomorphic to it. The main novelty of our approach is an abstract noncommutative construction with right and left adjoints, called sequential product. It is defined through a hierarchical structure of categories reflecting the implicit permission to sequence expressions and the inductive construction of compound expressions. We claim that Lambek's noncommutative product corresponds to a noncommutative bi-endofunctor into a category, which encloses all categories of (...) such hierarchical structure. A soundness theorem for LSC is shown with respect to this semantical framework. (shrink)

In Prawitz’s semantics, the validity of an argument may be defined, either relatively to an atomic base which determines the meaning of the non-logical terminology, or relatively to the whole class of atomic bases, namely as logical validity. In the first case, which may be qualified as local, one has to choose whether validity of arguments is or not monotonic over expansions of bases, while in the second case, which may be qualified as global, one has to choose whether the (...) reduction functions which justify non-primitive inferences are or not base-depending. I claim that these oppositions enjoy some conceptual symmetries, and that these symmetries may be understood as putting restrictions on one’s choice both at the local and at the global level. This produces two different proof-theoretic semantics in line with Prawitz’s tenets. However, I also argue that the symmetries stem from a deeper interaction within Prawitz’s semantics, i.e. non-logical meanings vs interpretation of rules. This interaction is in turn based on some primitive ingredients which, when suitably combined, produce other two Prawitz-compatible readings. The four readings form a diagram where some order relations hold. I finally claim that this diagram is complete, namely that, if we combine the ingredients in ways other than those giving rise to the four readings above, we obtain nothing new, or nothing compatible with general semantic requirements. Thus, symmetries between the local and the global level, and interaction between non-logical meaning and interpretation of rules, produce a complete classification of potential Prawitzian semantics. (shrink)

Prawitz has recently developed a theory of epistemic grounding that differs in many respects from his earlier semantics of arguments and proofs. An innovative approach to inferences yields a new conception of the intertwinement of the notions of valid inference and proof. We aim at singling out three reasons that may have led Prawitz to the ground-theoretic turn, i.e.: a better order in the explanation of the relation between valid inferences and proofs; a notion of valid inference based on which (...) valid inferences and proofs are recognisable as such; a reconstruction of the deductive activity that makes inferences capable of yielding justification per se. These topics are discussed by Prawitz with reference to a very general and ancient question: why and how correct deduction has the epistemic power to compel us to accept its conclusions, provided its premises are justified? We conclude by remarking that, in spite of some improvements, the ground-theoretic approach shares with the previous one a problem of vacuous validity which, as Prawitz himself points out, blocks in both cases a satisfactory explanation of epistemic compulsion. (shrink)

We outline a class of term-languages for epistemic grounding inspired by Prawitz’s theory of grounds. We show how denotation functions can be defined over these languages, relating terms to proof-objects built up of constructive functions. We discuss certain properties that the languages may enjoy both individually and with respect to their expansions. Finally, we provide a ground-theoretic version of Prawitz’s completeness conjecture, and adapt to our framework a refutation of this conjecture due to Piecha and Schroeder-Heister.