This is a reply to the considerations advanced by Schroeder-Heister and Tranchini as prima facie problematic for the proof-theoretic criterion of paradoxicality, as originally presented in Tennant and subsequently amended in Tennant. Countering these considerations lends new importance to the parallelized forms of elimination rules in natural deduction.

We explore the problems that confront any attempt to explain or explicate exactly what a primitive logical rule of inferenceis, orconsists in. We arrive at a proposed solution that places a surprisingly heavy load on the prospect of being able to understand and deal with specifications of rules that are essentiallyself-referring. That is, any rule$\rho $is to be understood via a specification that involves, embedded within it, reference to rule$\rho $itself. Just how we arrive at this position is explained (...) by reference to familiar rules as well as less familiar ones with unusual features. An inquiry of this kind is surprisingly absent from the foundations of inferentialism—the view that meanings of expressions (especially logical ones) are to be characterized by the rules of inference that govern them. (shrink)

The system of natural deduction that originated with Gentzen , and for which Prawitz proved a normalization theorem, is re-cast so that all elimination rules are in parallel form. This enables one to prove a very exigent normalization theorem. The normal forms that it provides have all disjunction-eliminations as low as possible, and have no major premisses for eliminations standing as conclusions of any rules. Normal natural deductions are isomorphic to cut-free, weakening-free sequent proofs. This form of (...) normalization theorem renders unnecessary Gentzen's resort to sequent calculi in order to establish the desired metalogical properties of his logical system.Ultimate normal forms are well-adapted to the needs of the computational logician, affording valuable constraints on proof-search. They also provide an analysis of deductive relevance. There is a deep isomorphism between natural deductions and sequent proofs in the relevantized system. (shrink)

While some branches of complexity theory are advancing rapidly, the same cannot be said for our understanding of emergence. Despite a complete knowledge of the rules underlying the interactions between the parts of many systems, we are often baffled by their sudden transitions from simple to complex. Here I propose a solution to this conceptual problem. Given that emergence is often the result of many interactions occurring simultaneously in time and space, an ability to intuitively grasp it would require (...) the ability to consciously think in parallel. A simple exercise is used to demonstrate that we do not possess this ability. Our surprise at the behaviour of cellular automata models, and the natural cases of pattern formation they mimic, is then explained from this perspective. This work suggests that the cognitive limitations of the mind can be as significant a barrier to scientific progress as the limitations of our senses. (shrink)

The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates.Through the condition that in a cut-free derivation of the (...) sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. (shrink)

This paper studies a formalisation of intuitionistic logic by Negri and von Plato which has general introduction and elimination rules. The philosophical importance of the system is expounded. Definitions of ‘maximal formula’, ‘segment’ and ‘maximal segment’ suitable to the system are formulated and corresponding reduction procedures for maximal formulas and permutative reduction procedures for maximal segments given. Alternatives to the main method used are also considered. It is shown that deductions in the system convert into normal form and (...) that deductions in normal form have the subformula property. (shrink)

This paper argues that Lemmon-style proof systems (those that consist of only introduction and elimination inference rules) have several pedagogical benefits over Copi-style systems (those that make use of inference rules and equivalence rules). It is argued that Lemmon-style systems are easier to learn as they do not require memorizing as many rules, they do not require learning the subtle distinction between a rule of inference and a rule of replacement, and deriving material conditionals is (...) more straightforward. Finally, it is argued that the need for learning provisional assumptions in Lemmon-style rules is not a significant enough reason for choosing the Copi-style system. (shrink)

This paper argues that Lemmon-style proof systems (those that consist of only introduction and elimination inference rules) have several pedagogical benefits over Copi-style systems (those that make use of inference rules and equivalence rules). It is argued that Lemmon-style systems are easier to learn as they do not require memorizing as many rules, they do not require learning the subtle distinction between a rule of inference and a rule of replacement, and deriving material conditionals is (...) more straightforward. Finally, it is argued that the need for learning provisional assumptions in Lemmon-style rules is not a significant enough reason for choosing the Copi-style system. (shrink)

The paper reports that the explanations of the v-elimination rule in three commonly used introductory logic textbooks are misleading to students and can result in invalid inferences.

A natural extension of Natural Deduction was defined by Schroder-Heister where not only formulas but also rules could be used as hypotheses and hence discharged. It was shown that this extension allows the definition of higher-level introduction and elimination schemes and that the set $\{ \vee, \wedge, \rightarrow, \bot \}$ of intuitionist sentential operators forms a {\it complete} set of operators modulo the higher level introduction and elimination schemes, i.e., that any operator whose introduction and elimination (...) rules are instances of the higher-level schemes can be defined in terms of $\{ \vee, \wedge, \rightarrow, \bot \}$.The aim of the present work is to extend the well-known connections between Proof Theory and Category Theory to higher-level Natural Deduction. To be precise, we will show how an adjointness between cartesian closed categories with finite coproducts can be associated, in a systematic way, with any operator $\phi$ defined by the higher-level schemes. The objects in the categories will be rules instead of formulas. (shrink)

Context-dependent rules are an obstacle to cut elimination. Turning to a generalised sequent style formulation using deep inferences is helpful, and for the calculus presented here it is essential. Cut elimination is shown for a substructural, multiplicative, pure propositional calculus. Moreover we consider the extra problems induced by non-logical axioms and extend the results to additive connectives and quantifiers.

Consider a general class of structural inference rules such as exchange, weakening, contraction and their generalizations. Among them, some are harmless but others do harm to cut elimination. Hence it is natural to ask under which condition cut elimination is preserved when a set of structural rules is added to a structure-free logic. The aim of this work is to give such a condition by using algebraic semantics. We consider full Lambek calculus (FL), i.e., intuitionistic logic (...) without any structural rules, as our basic framework. Residuated lattices are the algebraic structures corresponding to FL. In this setting, we introduce a criterion, called the propagation property, that can be stated both in syntactic and algebraic terminologies. We then show that, for any set R of structural rules, the cut elimination theorem holds for FL enriched with R if and only if R satisfies the propagation property. As an application, we show that any set R of structural rules can be "completed" into another set R*, so that the cut elimination theorem holds for FL enriched with R*, while the provability remains the same. (shrink)

Arguments by Sorkin (Impossible measurements on quantum fields. In: Directions in general relativity: proceedings of the 1993 International Symposium, Maryland, vol 2, pp 293–305, 1993) and Borsten et al. (Phys Rev D 104(2), 2021. https://doi.org/10.1103/PhysRevD.104.025012 ) establish that a natural extension of quantum measurement theory from non-relativistic quantum mechanics to relativistic quantum theory leads to the unacceptable consequence that expectation values in one region depend on which unitary operation is performed in a spacelike separated region. Sorkin [ 1 ] labels (...) such scenarios ‘impossible measurements’. We explicitly present these arguments as a no-go result with the logical form of a reductio argument and investigate the consequences for measurement in quantum field theory (QFT). Sorkin-type impossible measurement scenarios clearly illustrate the moral that Microcausality is not by itself sufficient to rule out superluminal signalling in relativistic quantum theories that use Lüders’ rule. We review three different approaches to formulating an account of measurement for QFT and analyze their responses to the ‘impossible measurements’ problem. Two of the approaches are: a measurement theory based on detector models proposed in Polo-Gómez et al. (Phys Rev D, 2022. https://doi.org/10.1103/physrevd.105.065003 ) and a measurement framework for algebraic QFT proposed in Fewster and Verch (Commun Math Phys 378(2):851–889, 2020). Of particular interest for foundations of QFT is that they share common features that may hold general morals about how to represent measurement in QFT. These morals are about the role that dynamics plays in eliminating ‘impossible measurements’, the abandonment of the operational interpretation of local algebras \({\mathcal {A}}(O)\) as representing possible operations carried out in region _O_, and the interpretation of state update rules. Finally, we examine the form that the ‘impossible measurements’ problem takes in histories-based approaches and we discuss the remaining challenges. (shrink)

Some philosophers argue that throughout its long history, Confucian ethics have stressed character formation or personal cultivation of virtues. Thus, it seems appropriate to characterise Confucian ethics as ethics of virtue. in this book, the author attempts to critique the apparent similarity and show, on the contrary, that Confucian ethics are better conceived of as a unique kind of ethics, in which rule-based morality and virtues are united. Through a unique analysis of Confucian ethics and comparison between Confucian ethics and (...) some Western ethical theories, the author also hopes to generate suggestions and ideas on how to integrate or unify rule and virtue in one moral theory. (shrink)

Inferentialism claims that expressions are meaningful by virtue of rules governing their use. In particular, logical expressions are autonomous if given meaning by their introduction-rules, rules specifying the grounds for assertion of propositions containing them. If the elimination-rules do no more, and no less, than is justified by the introduction-rules, the rules satisfy what Prawitz, following Lorenzen, called an inversion principle. This connection between rules leads to a general form of elimination-rule, (...) and when the rules have this form, they may be said to exhibit “general-elimination” harmony. Ge-harmony ensures that the meaning of a logical expression is clearly visible in its I-rule, and that the I- and E-rules are coherent, in encapsulating the same meaning. However, it does not ensure that the resulting logical system is normalizable, nor that it satisfies the conservative extension property, nor that it is consistent. Thus harmony should not be identified with any of these notions. (shrink)

Any set of truth-functional connectives has sequent calculus rules that can be generated systematically from the truth tables of the connectives. Such a sequent calculus gives rise to a multi-conclusion natural deduction system and to a version of Parigot’s free deduction. The elimination rules are “general,” but can be systematically simplified. Cut-elimination and normalization hold. Restriction to a single formula in the succedent yields intuitionistic versions of these systems. The rules also yield generalized lambda calculi (...) providing proof terms for natural deduction proofs as in the Curry-Howard isomorphism. Addition of an indirect proof rule yields classical single-conclusion versions of these systems. Gentzen’s standard systems arise as special cases. (shrink)

General-elimination harmony articulates Gentzen’s idea that the elimination-rules are justified if they infer from an assertion no more than can already be inferred from the grounds for making it. Dummett described the rules as not only harmonious but stable if the E-rules allow one to infer no more and no less than the I-rules justify. Pfenning and Davies call the rules locally complete if the E-rules are strong enough to allow one to (...) infer the original judgement. A method is given of generating harmonious general-elimination rules from a collection of I-rules. We show that the general-elimination rules satisfy Pfenning and Davies’ test for local completeness, but question whether that is enough to show that they are stable. Alternative conditions for stability are considered, including equivalence between the introduction- and elimination-meanings of a connective, and recovery of the grounds for assertion, finally generalizing the notion of local completeness to capture Dummett’s notion of stability satisfactorily. We show that the general-elimination rules meet the last of these conditions, and so are indeed not only harmonious but also stable. (shrink)

In this paper we first give a survey of reductive cut-elimination methods in classical logic. In particular we describe the methods of Gentzen and Schütte-Tait from the abstract point of view of proof reduction. We also present the method CERES which we classify as a semi-semantic method. In a further section we describe the so-called semantic methods. In the second part of the paper we carry the proof analysis further by generalizing the CERES method to CERESD . In the (...) generalized version CERESD we admit general elimination rules which are based on the mere semantical truth of sentences. We construct complete cut-free LK-derivations originating from derivations potentially containing unproven lemmas. Finally we give a comparison of reductive methods and CERESD by presenting a general simulation result. (shrink)

Supporters of eliminative connectionism have argued for a pattern association-based explanation of language learning and language processing. They deny that explicit rules and symbolic representations play any role in language processing and cognition in general. Their argument is based to a large extent on two artificial neural network (ANN) models that are claimed to be able to learn the past tenses of English verbs (Rumelhart & McClelland, 1986, Parallel distributed processing, Vol. 2, Cambridge, MA: MIT Press; MacWhinney & Leinbach, (...) 1991, Cognition, 40, 121-157). In this article we critically review Rumelhart and McClelland's as well as MacWhinney and Leinbach's ANN models and conclude that they do not succeed in the assigned task of learning the past tenses of English verbs. In order to answer their challenge to the symbolic processing approach, we present our symbolic pattern associator (SPA)-a general-purpose pattern associator that can learn to associate arbitrary discrete patterns. We carried out several experiments with the SPA using the same set of verbs that was used in MacWhinney and Leinbach's simulation with more realistic training and testing procedures. The SPA outperformed the connectionist models by a wide margin in the accuracy of learning, and successful inductive generalizations to unseen verbs. Our SPA has very natural and psychologically realistic explanations to many psychological effects such as U-shaped learning curve, and is much closer to human subjects in predicting past tense of the pseudo-verbs. In contrast to ANNs, whose internal representations are entirely opaque, the SPA can represent the acquired knowledge in the form of production rules that allow for further higher-level processing and integration, resulting in linguistically realistic associative templates for irregular verbs and production rules for regular verbs. In the light of these findings, we conclude that eliminative connectionists' vision of cognition as simple pattern association and pattern recognition without symbolic representation is inadequate. Pattern association as such does not imply rule-less or cue-based models of language acquisition or of human learning in general. (shrink)

The system GLS, which is a modal sequent calculus system for the provability logic GL, was introduced by G. Sambin and S. Valentini in Journal of Philosophical Logic, 11, 311–342,, and in 12, 471–476,, the second author presented a syntactic cut-elimination proof for GLS. In this paper, we will use regress trees in order to present a simpler and more intuitive syntactic cut derivability proof for GLS1, which is a variant of GLS without the cut rule.

Natural deduction with alternatives extends Gentzen–Prawitz-style natural deduction with a single structural addition: negatively signed assumptions, called alternatives. It is a mildly bilateralist, single-conclusion natural deduction proof system in which the connective rules are unmodi_ed from the usual Prawitz introduction and elimination rules — the extension is purely structural. This framework is general: it can be used for (1) classical logic, (2) relevant logic without distribution, (3) affine logic, and (4) linear logic, keeping the connective rules (...) fixed, and varying purely structural rules. The key result of this paper is that the two principles that introduce kinds of irrelevance to natural deduction proofs: (a) the rule of explosion (from a contradiction, anything follows); and (b) the structural rule of vacuous discharge; are shown to be two sides of a single coin, in the same way that they correspond to the structural rule of weakening in the sequent calculus. The paper also includes a discussion of assumption classes, and how they can play a role in treating additive connectives in substructural natural deduction. (shrink)

A way is found to add axioms to sequent calculi that maintains the eliminability of cut, through the representation of axioms as rules of inference of a suitable form. By this method, the structural analysis of proofs is extended from pure logic to free-variable theories, covering all classical theories, and a wide class of constructive theories. All results are proved for systems in which also the rules of weakening and contraction can be eliminated. Applications include a system of (...) predicate logic with equality in which also cuts on the equality axioms are eliminated. (shrink)

We present a syntactical cut-elimination proof for an extended sequent calculus covering the classical modal logics in the \(\mathsf{K}\), \(\mathsf{D}\), \(\mathsf{T}\), \(\mathsf{K4}\), \(\mathsf{D4}\) and \(\mathsf{S4}\) spectrum. We design the systems uniformly since they all share the same set of rules. Different logics are obtained by “tuning” a single parameter, namely a constraint on the applicability of the cut rule and on the (left and right, respectively) rules for \(\Box\) and \(\Diamond\). Starting points for this research are 2-sequents (...) and indexed-based calculi (sequents and tableaux). By extending and modifying existing proposals, we show how to achieve a syntactical proof of the cut-elimination theorem that is as close as possible to the one for first-order classical logic. In doing this, we implicitly show how small is the proof-theoretical distance between classical logic and the systems under consideration. (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 about intuitionistic propositional logic that bear on that perspective, and discuss their significance.

We develop a general algebraic and proof-theoretic study of substructural logics that may lack associativity, along with other structural rules. Our study extends existing work on substructural logics over the full Lambek Calculus [34], Galatos and Ono [18], Galatos et al. [17]). We present a Gentzen-style sequent system that lacks the structural rules of contraction, weakening, exchange and associativity, and can be considered a non-associative formulation of . Moreover, we introduce an equivalent Hilbert-style system and show that the (...) logic associated with and is algebraizable, with the variety of residuated lattice-ordered groupoids with unit serving as its equivalent algebraic semantics. Overcoming technical complications arising from the lack of associativity, we introduce a generalized version of a logical matrix and apply the method of quasicompletions to obtain an algebra and a quasiembedding from the matrix to the algebra. By applying the general result to specific cases, we obtain important logical and algebraic properties, including the cut elimination of and various extensions, the strong separation of , and the finite generation of the variety of residuated lattice-ordered groupoids with unit. (shrink)

Sport, Rules and Values presents a philosophical perspective on some issues concerning the character of sport. Central questions for the text are motivated from real life sporting examples as described in newspaper reports. For instance, the (supposed) subjectivity of umpiring decisions is explored via an examination of the judging ice-skating at the Salt Lake City Olympic Games of 2002. Throughout, the presentation is rich in concrete cases from sporting situations, including baseball, football, and soccer. While granting the constitutive nature (...) of the rules of sport, discussion focuses on three broad uses commonly urged for rules: in defining sport; in judging or assessing sport (as deployed by judges or umpires); and in characterizing the value of sport, especially if that value is regarded as moral value. In general, McFee rejects a conception of the determinacy of rules as possible within sport, and a parallel picture of the determinacy assumed to be required by philosophy. (shrink)

In proof-theoretic semantics the meaning of an atomic sentence is usually determined by a set of derivations in an atomic system which contain that sentence as a conclusion (see, in particular, Prawitz, 1971, 1973). The paper critically discusses this standard approach and suggests an alternative account which proceeds in terms of subatomic introduction and elimination rules for atomic sentences. A simple subatomic normal form theorem by which this account of the semantics of atomic sentences and the terms from (...) which they are composed is underpinned, shows moreover that the proof-theoretic analysis of first-order logic can be pursued also beneath the atomic level. (shrink)

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

We develop a Gentzen-style proof theory for super-Belnap logics, expanding on an approach initiated by Pynko. We show that just like substructural logics may be understood proof-theoretically as logics which relax the structural rules of classical logic but keep its logical rules as well as the rules of Identity and Cut, super-Belnap logics may be seen as logics which relax Identity and Cut but keep the logical rules as well as the structural rules of classical (...) logic. A generalization of the cut elimination theorem for classical propositional logic is then proved and used to establish interpolation for various super-Belnap logics. In particular, we obtain an alternative syntactic proof of a refinement of the Craig interpolation theorem for classical propositional logic discovered recently by Milne. (shrink)

Article history: This article sketches the Parallel Architecture, an approach to the structure of grammar that Accepted 29 August 2006 contrasts with mainstream generative grammar (MGG) in that (a) it treats phonology, Available online 13 October 2006 syntax, and semantics as independent generative components whose structures are linked by interface rules; (b) it uses a parallel constraint-based formalism that is nondirectional; (c) Keywords: it treats words and rules alike as pieces of linguistic structure stored in long-term memory.

We investigate introduction and elimination rules for truth-functional connectives, focusing on the general questions of the existence, for a given connective, of at least one such rule that it satisfies, and the uniqueness of a connective with respect to the set of all of them. The answers are straightforward in the context of rules using general set/set sequents of formulae, but rather complex and asymmetric in the restricted (but more often used) context of set/formula sequents, as also (...) in the intermediate set/formula-or-empty context. (shrink)

We explore the consequences, for logical system-building, of taking seriously the aim of having irredundant rules of inference, and a preference for proofs of stronger results over proofs of weaker ones. This leads one to reconsider the structural rules of REFLEXIVITY, THINNING, and CUT. REFLEXIVITY survives in the minimally necessary form $\varphi:\varphi$. Proofs have to get started. CUT is subject to a CUT-elimination theorem, to the effect that one can always make do without applications of CUT. So (...) CUT is redundant, and should not be a rule of the system. CUT-elimination, however, in the context of the usual forms of logical rules, requires the presence, in the system, of THINNING. But THINNING, it turns out, is not really necessary. Provided only that one liberalizes the statement of certain logical rules in an appropriate way, one can make do without CUT or THINNING. From the methodological point of view of this study, the logical rules ought to be framed in this newly liberalized form. These liberalized logical rules determine the system of core logic. Given any intuitionistic Gentzen proof of $\Delta:\varphi$, one can determine from it a Core proof of some subsequent of $\Delta:\varphi$. Given any classical Gentzen proof of $\Delta:\varphi$, one can determine from it a classical Core proof of some subsequent of $\Delta:\varphi$. In both cases the Core proof is of a result at least as strong as that of the Gentzen proof; and the only structural rule used is $\varphi:\varphi$. (shrink)

Canonical Propositional Gentzen-type systems are systems which in addition to the standard axioms and structural rules have only pure logical rules with the sub-formula property, in which exactly one occurrence of a connective is introduced in the conclusion, and no other occurrence of any connective is mentioned anywhere else. In this paper we considerably generalize the notion of a “canonical system” to first-order languages and beyond. We extend the Propositional coherence criterion for the non-triviality of such systems to (...) rules with unary quantifiers and show that it remains constructive. Then we provide semantics for such canonical systems using 2-valued non-deterministic matrices extended to languages with quantifiers, and prove that the following properties are equivalent for a canonical system G: (1) G admits Cut-Elimination, (2) G is coherent, and (3) G has a characteristic 2-valued non-deterministic matrix. (shrink)

We investigate introduction and elimination rules for truth-functional connectives, focusing on the general questions of the existence, for a given connective, of at least one such rule that it satisfies, and the uniqueness of a connective with respect to the set of all of them. The answers are straightforward in the context of rules using general set/set sequents of formulae, but rather complex and asymmetric in the restricted (but more often used) context of set/formula sequents, as also (...) in the intermediate set/formula-or-empty context. (shrink)

Nowadays, there is a quite considerable amount of literature on the use of analogy or more generally of inferences by parallel reasoning in contemporary legal reasoning and particularly so within Common Law. These studies are often motivated by research in artificial intelligence seeking to develop suitable software-support for legal reasoning. Recently, Rahman et al. developed a dialogical approach in the framework of Constructive Type Theory to what in Islamic Jurisprudence was called qiyās or correlational inferences. In their last chapter the (...) authors suggested that such an approach contributes to the study of patterns of reasoning by precedent cases within contemporary Common Law. In the present paper we will further motivate the deployment of the dialogical framework developed in Rahman et al. within Civil and Common Law. After a presentation of Scott Brewer’s take on analogy within Common Law, that has striking structural similarities to reasoning by precedent case rooted in ratio legis, we will illustrate the implementation of the framework with a brief discussion of some cases of legal reasoning based on Spanish Civil Law but where the accent is put in the emerging ruling rather than in the existing of a case in Common Law. Moreover, quite surprisingly, the case under study suggests that even cases of Law interpretation fit the argumentation pattern of qiyās al-‘illa. A caveat: in the present paper we will focus mainly in discussing the dynamics of the meaning constitution involved rather than in setting the rules of the underlying dialogical framework, the latter is the subject of a follow-up paper. (shrink)

We establish the “contraction-elimination theorem” which means that if a sequent Γ A is provable in the implicational fragment of the Gentzen's sequent calculus LK and if it satisfies a certain condition on the number of the occurrences of propositional variables, then it is provable without the right contraction rule. By this theorem, we get the following.1. If an implicational formula A is a theorem of classical logic and is not a theorem of intuitionistic logic, then there is a (...) propositional variable which occurs at least once positively and at least twice negatively in A → a) → a).2. If an implicational formula A is a theorem of intuitionistic logic and is not a theorem of BCK-logic, then there is a propositional variable which occurs at least twice positively and at least once negatively in A → a → b).We prove the contraction-elimination theorem by a fully syntactical method, which has some analogy with Gentzen's cut-elimination. (shrink)

The paper studies a cluster of systems for fully disquotational truth based on the restriction of initial sequents. Unlike well-known alternative approaches, such systems display both a simple and intuitive model theory and remarkable proof-theoretic properties. We start by showing that, due to a strong form of invertibility of the truth rules, cut is eliminable in the systems via a standard strategy supplemented by a suitable measure of the number of applications of truth rules to formulas in derivations. (...) Next, we notice that cut remains eliminable when suitable arithmetical axioms are added to the system. Finally, we establish a direct link between cut-free derivability in infinitary formulations of the systems considered and fixed-point semantics. Noticeably, unlike what happens with other background logics, such links are established without imposing any restriction to the premisses of the truth rules. (shrink)

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)

In Schwichtenberg, Schwichtenberg fine-tuned Tait’s technique so as to provide a simplified version of Gentzen’s original cut-elimination procedure for first-order classical logic. In this note we show that, limited to the case of classical propositional logic, the Tait–Schwichtenberg algorithm allows for a further simplification. The procedure offered here is implemented on Kleene’s sequent system G4. The specific formulation of the logical rules for G4 allows us to provide bounds on the height of cut-free proofs just in terms of (...) the logical complexity of their end-sequent. (shrink)

For the past three decades linguistic theory has been based on the assumption that sentences are interpreted and constructed by the brain by means of computational processes analogous to those of a serial-digital computer. The recent interest in devices based on the neural network or parallel distributed processor (PDP) principle raises the possibility ("eliminative connectionism") that such devices may ultimately replace the S-D computer as the model for the interpretation and generation of language by the brain. An analysis of the (...) differences between the two models suggests that the effect of such a development would be to steer linguistic theory towards a return to the empiricism and behaviorism which prevailed before it was driven by Chomsky towards nativism and mentalism. Linguists, however, will not be persuaded to return to such a theory unless and until it can deal with the phenomenon of novel sentence construction as effectively as its nativist/mentalist rival. (shrink)

We present a cut-free sequent calculus for a class of first-order theories in negation normal form which include coherent and co-coherent theories alike. All structural rules, including cut, are admissible.

Deep inference is a natural generalisation of the one-sided sequent calculus where rules are allowed to apply deeply inside formulas, much like rewrite rules in term rewriting. This freedom in applying inference rules allows to express logical systems that are difficult or impossible to express in the cut-free sequent calculus and it also allows for a more fine-grained analysis of derivations than the sequent calculus. However, the same freedom also makes it harder to carry out this analysis, (...) in particular it is harder to design cut elimination procedures. In this paper we see a cut elimination procedure for a deep inference system for classical predicate logic. As a consequence we derive Herbrand's Theorem, which we express as a factorisation of derivations. (shrink)

S4C is a logic of continuous transformations of a topological space. Cut elimination for it requires new kind of rules and new kinds of reductions.

Bilateral proof systems, which provide rules for both affirming and denying sentences, have been prominent in the development of proof-theoretic semantics for classical logic in recent years. However, such systems provide a substantial amount of freedom in the formulation of the rules, and, as a result, a number of different sets of rules have been put forward as definitive of the meanings of the classical connectives. In this paper, I argue that a single general schema for bilateral (...) proof rules has a reasonable claim to inferentially articulating the core meaning of all of the classical connectives. I propose this schema in the context of a bilateral sequent calculus in which each connective is given exactly two rules: a rule for affirmation and a rule for denial. Positive and negative rules for all of the classical connectives are given by a single rule schema, harmony between these positive and negative rules is established at the schematic level by a pair of elimination theorems, and the truth-conditions for all of the classical connectives are read off at once from the schema itself. (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)