Structural Completeness in Relevance Logics

It is proved that the relevance logic \({\mathbf{R}}\) (without sentential constants) has no structurally complete consistent axiomatic extension, except for classical propositional logic. In fact, no other such extension is even passively structurally complete.     

The Normal-Form Decision Method in the Combined Calculus

The original decision criterion and method of the combined calculus, presented by D. Hilbert and W. Ackermann, and applied by later logicians, are illuminating, but also go seriously awry and lead the universality and preciseness of the combined calculus to be damaged. The main error is that they confuse the two levels of the combined calculus in the course of calculating. This paper aims to resolve the problem through dividing the levels of the combined calculus, introducing a mixed operation mode, and therefore finding a normal-form decision method approximated by that in sentential logic. Finally, this paper provides a more precise proof of Hauber’s theorem by using the normal-form decision method of the combined calculus.     

On the degree of complexity of sentential logics.II. An example of the logic with semi-negation

In this paper being a sequel to our [1] the logic with semi-negation is chosen as an example to elucidate some basic notions of the semantics for sentential calculi. E.g., there are shown some links between the Post number and the degree of complexity of a sentential logic, and it is proved that the degree of complexity of the sentential logic with semi-negation is 20. This is the first known example of a logic with such a degree of complexity. The results of the final part of the paper cast a new light on the scope of the Kripke-style semantics in comparison to the matrix semantics.In memory of Roman Suszko     

Sentential constants in R and R⌝

In this paper, we shall confine ourselves to the study of sentential constants in the system R of relevant implication.In dealing with the behaviour of the sentential constants in R, we shall think of R itself as presented in three stages, depending on the level of truth-functional involvement.     

Generic generalized Rosser fixed points

To the standard propositional modal system of provability logic constants are added to account for the arithmetical fixed points introduced by Bernardi-Montagna in [5]. With that interpretation in mind, a system LR of modal propositional logic is axiomatized, a modal completeness theorem is established for LR and, after that, a uniform arithmetical (Solovay-type) completeness theorem with respect to PA is obtained for LR. This paper supersedes: Franco Montagna, Extremely undecidable sentences and generic generalized Rosser's fixed points, Rapporto Matematico, No. 95, Siena, 1983.     

On S

The sentential logic S extends classical logic by an implication-like connective. The logic was first presented by Chellas as the smallest system modelled by contraining the Stalnaker-Lewis semantics for counterfactual conditionals such that the conditional is effectively evaluated as in the ternary relations semantics for relevant logics. The resulting logic occupies a key position among modal and substructural logics. We prove completeness results and study conditions for proceeding from one family of logics to another.We are grateful to Peter Apostoli, Kosta Doen, and anonymous referees for their comments on an earlier version of this paper. A.F.'s work has been supported by a grant from the Volkswagen-Stiftung.Presented byJan Zygmunt     

Classical harmony: Rules of inference and the meaning of the logical constants

The thesis that, in a system of natural deduction, the meaning of a logical constant is given by some or all of its introduction and elimination rules has been developed recently in the work of Dummett, Prawitz, Tennant, and others, by the addition of harmony constraints. Introduction and elimination rules for a logical constant must be in harmony. By deploying harmony constraints, these authors have arrived at logics no stronger than intuitionist propositional logic. Classical logic, they maintain, cannot be justified from this proof-theoretic perspective. This paper argues that, while classical logic can be formulated so as to satisfy a number of harmony constraints, the meanings of the standard logical constants cannot all be given by their introduction and/or elimination rules; negation, in particular, comes under close scrutiny.     

一个多值逻辑的一阶谓词系统

鞠实儿曾提出一个开放类三值命题逻辑系统,这一逻辑也可以推广到任意m值逻辑情形,成为一个联结词函数完全的逻辑。本文将对推广的命题逻辑系统L^＊建立一种一阶谓词系统,并证明其可靠性、完全性。     

Logic Semantics with the Potential Infinite

A form of quantification logic referred to by the author in earlier papers as being ‘ontologically neutral’ still made use of the actual infinite in its semantics. Here it is shown that one can have, if one desires, a formal logic that refers in its semantics only to the potential infinite. Included are two new quantifiers generalizing the sentential connectives, equivalence and non-equivalence. There are thus new avenues opening up for exploration in both quantification logic and semantics of the infinite.     

An Admissible Semantics for Propositionally Quantified Relevant Logics

The Routley-Meyer relational semantics for relevant logics is extended to give a sound and complete model theory for many propositionally quantified relevant logics (and some non-relevant ones). This involves a restriction on which sets of worlds are admissible as propositions, and an interpretation of propositional quantification that makes ∀ pA true when there is some true admissible proposition that entails all p-instantiations of A. It is also shown that without the admissibility qualification many of the systems considered are semantically incomplete, including all those that are sub-logics of the quantified version of Anderson and Belnap’s system E of entailment, extended by the mingle axiom and the Ackermann constant t. The incompleteness proof involves an algebraic semantics based on atomless complete Boolean algebras.     

Contextual Deduction Theorems

Logics that do not have a deduction-detachment theorem (briefly, a DDT) may still possess a contextual DDT??a syntactic notion introduced here for arbitrary deductive systems, along with a local variant. Substructural logics without sentential constants are natural witnesses to these phenomena. In the presence of a contextual DDT, we can still upgrade many weak completeness results to strong ones, e.g., the finite model property implies the strong finite model property. It turns out that a finitary system has a contextual DDT iff it is protoalgebraic and gives rise to a dually Brouwerian semilattice of compact deductive filters in every finitely generated algebra of the corresponding type. Any such system is filter distributive, although it may lack the filter extension property. More generally, filter distributivity and modularity are characterized for all finitary systems with a local contextual DDT, and several examples are discussed. For algebraizable logics, the well-known correspondence between the DDT and the equational definability of principal congruences is adapted to the contextual case.     

Subjunctivity and cross-world predication

The main goal of this paper is to present and compare two approaches to formalizing cross-world comparisons like ??John might have been taller than he is?? in quantified modal logics. One is the standard method employing degrees and graded positives, according to which the example just given is to be paraphrased as something like ??The height that John has is such that he might have had a height greater than it,?? which is amenable to familiar formalization strategies with respect to quantified modal logic. The other approach, based on subjunctive modal logic, mimics the mixed indicative-subjunctive patterns typical of cross-world comparisons in many natural languages by means of explicit mood markers. This latter approach is new and should, for various reasons, appeal to linguists and philosophers. Along the way, I argue that attempts to capture cross-world comparison by means of sentential operators are either inadequate or subject to substantive logical and philosophical objections.     

Labelled Resolution for Classical and Non-classical Logics

Resolution is an effective deduction procedure for classical logic. There is no similar "resolution" system for non-classical logics (though there are various automated deduction systems). The paper presents resolution systems for intuistionistic predicate logic as well as for modal and temporal logics within the framework of labelled deductive systems. Whereas in classical predicate logic resolution is applied to literals, in our system resolution is applied to L(abelled) R(epresentation) S(tructures). Proofs are discovered by a refutation procedure defined on LRSs, that imposes a hierarchy on clause sets of such structures together with an inheritance discipline. This is a form of Theory Resolution. For intuitionistic logic these structures are called I(ntuitionistic) R(epresentation) S(tructures). Their hierarchical structure allows the restriction of unification of individual variables and/or constants without using Skolem functions. This structures must therefore be preserved when we consider other (non-modal) logics. Variations between different logics are captured by fine tuning of the inheritance properties of the hierarchy. For modal and temporal logics IRS's are extended to structures that represent worlds and/or times. This enables us to consider all kinds of combined logics.     

A Routley-Meyer Type Semantics for Relevant Logics Including B<Subscript>r</Subscript> Plus the Disjunctive Syllogism

Routley-Meyer type ternary relational semantics are defined for relevant logics including Routley and Meyer’s basic logic B plus the reductio rule \( \vdash A\rightarrow \lnot A\Rightarrow \vdash \lnot A\) and the disjunctive syllogism. Standard relevant logics such as E and R (plus γ) and Ackermann’s logics of ‘strenge Implikation’ Π and Π^′ are among the logics considered.     

Syntactic features and synonymy relations: a unified treatment of some proofs of the compactness and interpolation theorems

This paper introduces the notion of syntactic feature to provide a unified treatment of earlier model theoretic proofs of both the compactness and interpolation theorems for a variety of two valued logics including sentential logic, first order logic, and a family of modal sentential logic includingM,B,S ₄ andS ₅. The compactness papers focused on providing a proof of the consequence formulation which exhibited the appropriate finite subset. A unified presentation of these proofs is given by isolating their essential feature and presenting it as an abstract principle about syntactic features. The interpolation papers focused on exhibiting the interpolant. A unified presentation of these proofs is given by isolating their essential feature and presenting it as a second abstract principle about syntactic features. This second principle reduces the problem of exhibiting the interpolant to that of establishing the existence of a family of syntactic features satisfying certain conditions. The existence of such features is established for a variety of logics (including those mentioned above) by purely combinatorial arguments.Presented byMelvin Fitting     

Algebraic aspects of deduction theorems

The first known statements of the deduction theorems for the first-order predicate calculus and the classical sentential logic are due to Herbrand [8] and Tarski [14], respectively. The present paper contains an analysis of closure spaces associated with those sentential logics which admit various deduction theorems. For purely algebraic reasons it is convenient to view deduction theorems in a more general form: given a sentential logic C (identified with a structural consequence operation) in a sentential language I, a quite arbitrary set P of formulas of I built up with at most two distinct sentential variables p and q is called a uniform deduction theorem scheme for C if it satisfies the following condition: for every set X of formulas of I and for any formulas and , C(X{{a}}) iff P(, ) AC(X). [P(, ) denotes the set of formulas which result by the simultaneous substitution of for p and for q in all formulas in P]. The above definition encompasses many particular formulations of theorems considered in the literature to be deduction theorems. Theorem 1.3 gives necessary and sufficient conditions for a logic to have a uniform deduction theorem scheme. Then, given a sentential logic C with a uniform deduction theorem scheme, the lattices of deductive filters on the algebras A similar to the language of C are investigated. It is shown that the join-semilattice of finitely generated (= compact) deductive filters on each algebra A is dually Brouwerian.A part of this paper was presented in abstracted form in Bulletin of the Section of Logic, Vol. 12, No. 3 (1983), pp. 111–116, and in The Journal of Symbolic Logic.     

Existential Import Today: New Metatheorems; Historical,Philosophical, and Pedagogical Misconceptions

We assemble material from the literature on matrix methodology for sentential logic—without claiming to present any new logical results—in order to show that Gödel once made (or at least, is quoted as having made) an uncharacteristically ill-considered remark in this area.     

Non‐Classical Knowledge

The Knower paradox purports to place surprising a priori limitations on what we can know. According to orthodoxy, it shows that we need to abandon one of three plausible and widely‐held ideas: that knowledge is factive, that we can know that knowledge is factive, and that we can use logical/mathematical reasoning to extend our knowledge via very weak single‐premise closure principles. I argue that classical logic, not any of these epistemic principles, is the culprit. I develop a consistent theory validating all these principles by combining Hartry Field's theory of truth with a modal enrichment developed for a different purpose by Michael Caie. The only casualty is classical logic: the theory avoids paradox by using a weaker‐than‐classical K₃ logic. I then assess the philosophical merits of this approach. I argue that, unlike the traditional semantic paradoxes involving extensional notions like truth, its plausibility depends on the way in which sentences are referred to—whether in natural languages via direct sentential reference, or in mathematical theories via indirect sentential reference by Gödel coding. In particular, I argue that from the perspective of natural language, my non‐classical treatment of knowledge as a predicate is plausible, while from the perspective of mathematical theories, its plausibility depends on unresolved questions about the limits of our idealized deductive capacities.     

Adding Involution to Residuated Structures

Two constructions for adding an involution operator to residuated ordered monoids are investigated. One preserves integrality and the mingle axiom x ²x but fails to preserve the contraction property xx ². The other has the opposite preservation properties. Both constructions preserve commutativity as well as existent nonempty meets and joins and self-dual order properties. Used in conjunction with either construction, a result of R.T. Brady can be seen to show that the equational theory of commutative distributive residuated lattices (without involution) is decidable, settling a question implicitly posed by P. Jipsen and C. Tsinakis. The corresponding logical result is the (theorem-) decidability of the negation-free axioms and rules of the logic RW, formulated with fusion and the Ackermann constant t. This completes a result of S. Giambrone whose proof relied on the absence of t.