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.     

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.     

Equivalential logics (II)

In the first section logics with an algebraic semantics are investigated. Section 2 is devoted to subdirect products of matrices. There, among others we give the matrix counterpart of a theorem of Jónsson from universal algebra. Some positive results concerning logics with, finite degrees of maximality are presented in Section 3.     

On Gentzen Relations Associated with Finite-valued Logics Preserving Degrees of Truth

When considering m-sequents, it is always possible to obtain an m-sequent calculus VL for every m-valued logic (defined from an arbitrary finite algebra L of cardinality m) following for instance the works of the Vienna Group for Multiple-valued Logics. The Gentzen relations associated with the calculi VL are always finitely equivalential but might not be algebraizable. In this paper we associate an algebraizable 2-Gentzen relation with every sequent calculus VL in a uniform way, provided the original algebra L has a reduct that is a distributive lattice or a pseudocomplemented distributive lattice. We also show that the sentential logic naturally associated with the provable sequents of this algebraizable Gentzen relation is the logic that preserves degrees of truth with respect to the original algebra (in contrast with the more common logic that merely preserves truth). Finally, for some particular logics we obtain 2-sequent calculi that axiomatize the algebraizable Gentzen relations obtained so far.     

Equivalential logics (I)

The class of equivalential logics comprises all implicative logics in the sense of Rasiowa [9], Suszko's logicSCI and many Others. Roughly speaking, a logic is equivalential iff the greatest strict congruences in its matrices (models) are determined by polynomials. The present paper is the first part of the survey in which systematic investigations into this class of logics are undertaken. Using results given in [3] and general theorems from the theory of quasi-varieties of models [5] we give a characterization of all simpleC-matrices for any equivalential logicC (Theorem I.14). In corollaries we give necessary and sufficient conditions for the class of all simple models for a given equivalential logic to be closed under free products (Theorem I.18). Theorem I.17 can be generalized as follows:For any equivalential logic C, clauses (i), (iii)and (v),formulated in Th.I.17,are equivalent.     

Sentential logics and Maehara Interpolation Property

With each sentential logic C, identified with a structural consequence operation in a sentential language, the class Matr ^* (C) of factorial matrices which validate C is associated. The paper, which is a continuation of [2], concerns the connection between the purely syntactic property imposed on C, referred to as Maehara Interpolation Property (MIP), and three diagrammatic properties of the class Matr* (C): the Amalgamation Property (AP), the (deductive) Filter Extension Property (FEP) and Injections Transferable (IT). The main theorem of the paper (Theorem 2.2) is analogous to the Wroński's result for equational classes of algebras [13]. It reads that for a large class of logics the conjunction of (AP) and (FEP) is equivalent to (IT) and that the latter property is equivalent to (MIP).     

Definability and Interpolation in Non-Classical Logics

Algebraic approach to study of classical and non-classical logical calculi was developed and systematically presented by Helena Rasiowa in [48], [47]. It is very fruitful in investigation of non-classical logics because it makes possible to study large families of logics in an uniform way. In such research one can replace logics with suitable classes of algebras and apply powerful machinery of universal algebra. In this paper we present an overview of results on interpolation and definability in modal and positive logics,and also in extensions of Johansson's minimal logic. All these logics are strongly complete under algebraic semantics. It allows to combine syntactic methods with studying varieties of algebras and to flnd algebraic equivalents for interpolation and related properties. Moreover, we give exhaustive solution to interpolation and some related problems for many families of propositional logics and calculi. This paper is a version of the invited talk given by the author at the conference Trends in Logic III, dedicated to the memory of A. MOSTOWSKI, H. RASIOWA and C. RAUSZER, and held in Warsaw and Ruciane-Nida from 23rd to 25th September 2005. Presented by Jacek Malinowski     

Paraconsistent algebras

The prepositional calculiC _n , 1 n introduced by N.C.A. da Costa constitute special kinds of paraconsistent logics. A question which remained open for some time concerned whether it was possible to obtain a Lindenbaum's algebra forC _n . C. Mortensen settled the problem, proving that no equivalence relation forC _n . determines a non-trivial quotient algebra.The concept of da Costa algebra, which reflects most of the logical properties ofC _n , as well as the concept of paraconsistent closure system, are introduced in this paper.We show that every da Costa algebra is isomorphic with a paraconsistent algebra of sets, and that the closure system of all filters of a da Costa algebra is paraconsistent.     

Synonymy in sentential languages: a pragmatic view

In this note two notions of meaning are considered and accordingly two versions of synonymy are defined, weaker and stronger ones. A new semantic device is introduced: a matrix is said to be pragmatic iff its algebra is in fact an algebra of meanings in the stronger sense. The new semantics is proved to be universal enough (Theorem 1), and it turns out to be in some sense a generalization of Wójcicki's referential semantics (Theorem 3).     

On the Closure Properties of the Class of Full G-models of a Deductive System

In this paper we consider the structure of the class FGModS of full generalized models of a deductive system S from a universal-algebraic point of view, and the structure of the set of all the full generalized models of S on a fixed algebra A from the lattice-theoretical point of view; this set is represented by the lattice FACS_s A of all algebraic closed-set systems C on A such that (A, C) ε FGModS. We relate some properties of these structures with tipically logical properties of the sentential logic S. The main algebraic properties we consider are the closure of FGModS under substructures and under reduced products, and the property that for any A the lattice FACS_s A is a complete sublattice of the lattice of all algebraic closed-set systems over A. The logical properties are the existence of a fully adequate Gentzen system for S, the Local Deduction Theorem and the Deduction Theorem for S. Some of the results are established for arbitrary deductive systems, while some are found to hold only for deductive systems in more restricted classes like the protoalgebraic or the weakly algebraizable ones. The paper ends with a section on examples and counterexamples. Dedicated to the memory of Willem Johannes Blok     

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     

Completeness and conservative extension results for some boolean relevant logics

This paper presents completeness and conservative extension results for the boolean extensions of the relevant logic T of Ticket Entailment, and for the contractionless relevant logics TW and RW. Some surprising results are shown for adding the sentential constant t to these boolean relevant logics; specifically, the boolean extensions with t are conservative of the boolean extensions without t, but not of the original logics with t. The special treatment required for the semantic normality of T is also shown along the way.     

On the degree of complexity of sentential logics. A couple of examples

The first part of the paper is a reminder of fundamental results connected with the adequacy problem for sentential logics with respect to matrix semantics. One of the main notions associated with the problem, namely that of the degree of complexity of a sentential logic, is elucidated by a couple of examples in the second part of the paper. E.g., it is shown that the minimal logic of Johansson and some of its extensions have degree of complexity 2. This is the first example of an exact estimation of the degree of natural complex logics, i.e. logics whose deducibility relation cannot be represented by a single matrix. The remaining examples of complex logics are more artificial, having been constructed for the purpose of checking some theoretical possibilities.The paper was presented to the Polish Philosophical Society, Wrocaw Branch, at its meeting on March 27^th, 1980.The authors wish to thank both the referees of Studia Logica for their helpful and very insightful remarks. Following their criticism, we have been able to improve the style and structure of our presentation. In particular, we are indebted to the referees for pointing out a gap in the original proof of Theorem 2, and we have incorporated into the revised text a corrected proof of step (2.1) which one of them was kind enough to supply in detail.     

Matrices,primitive satisfaction and finitely based logics

We examine the notion of primitive satisfaction in logical matrices. Theorem II. 1, being the matrix counterpart of Baker's well-known result for congruently distributive varieties of algebras (cf [1], Thm. 1.5), links the notions of primitive and standard satisfaction. As a corollary we give the matrix version of Jónsson's Lemma, proved earlier in [4]. Then we investigate propositional logics with disjunction. The main result, Theorem III. 2, states a necessary and sufficient condition for such logics to be finitely based.     

Selfextensional Logics with a Conjunction

A logic is selfextensional if its interderivability (or mutual consequence) relation is a congruence relation on the algebra of formulas. In the paper we characterize the selfextensional logics with a conjunction as the logics that can be defined using the semilattice order induced by the interpretation of the conjunction in the algebras of their algebraic counterpart. Using the charactrization we provide simpler proofs of several results on selfextensional logics with a conjunction obtained in [13] using Gentzen systems. We also obtain some results on Fregean logics with conjunction.This paper is a version of the invited talk at the conference Trends in Logic III, dedicated to the memory of A. MOSTOWSKI, H. RASIOWA and C. RRAUSZER, and held in Warsaw and Ruciane-Nida from 23rd to 25th September 2005.     

Definability and Quantifier Elimination for J 3-theories

The Joint Non-Trivialization Theorem, two Definability Theorems and the generalized Quantifier Elimination Theorem are proved for J ₃-theories. These theories are three-valued with more than one distinguished truth-value, reflect certain aspects of model type logics and can. be paraconsistent. J ₃-theories were introduced in the author's doctoral dissertation.     

Rules in relevant logic — II: Formula representation

This paper surveys the various forms of Deduction Theorem for a broad range of relevant logics. The logics range from the basic system B of Routley-Meyer through to the system R of relevant implication, and the forms of Deduction Theorem are characterized by the various formula representations of rules that are either unrestricted or restricted in certain ways. The formula representations cover the iterated form,A ₁ .A ₂ . ... .A _n B, the conjunctive form,A ₁&A ₂ & ...A _n B, the combined conjunctive and iterated form, enthymematic version of these three forms, and the classical implicational form,A ₁&A ₂& ...A _n B. The concept of general enthymeme is introduced and the Deduction Theorem is shown to apply for rules essentially derived using Modus Ponens and Adjunction only, with logics containing either (A B)&(B C) .A C orA B .B C .A C.I acknowledge help from anonymous referees for guidance in preparing Part II, and especially for the suggestion that Theorem 9 could be expanded to fully contraction-less logics.     

The shortest possible length of the longest implicational axiom

A four-valued matrix is presented which validates all theorems of the implicational fragment, IF, of the classical sentential calculus in which at most two distinct sentence letters occur. The Wajsberg/Diamond-McKinsley Theorem for IF follows as a corollary: every complete set of axioms (with substitution and detachment as rules) must include at least one containing occurrences of three or more distinct sentence letters.Additionally, the matrix validates all IF theses built from nine or fewer occurrences of connectives and letters. So the classic result of Jaskovski for the full sentential calculus —that every complete axiom set must contain either two axioms of length at least nine or else one of length at least eleven—can be improved in the implicational case: every complete axiom set for IF must contain at least one axiom eleven or more characters long.Both results are best possible, and both apply as well to most subsystems of IF, e.g., the implicational fragments of the standard relevance logics, modal logics, the relatives of implicational intutionism, and logics in the ukasiewicz family.Earlier proofs of these results, utilizing a five-valued matrix built from the product matrix of C2 with itself via the method of [8], were obtained in 1988 while the author was a Visiting Research Fellow at the Automated Reasoning Project, Research School of Social Sciences, Australian National University, and were presented in [9]. The author owes thanks to the RSSS for creating the Project, and to the members of the Project generally for the stimulating atmosphere they created in turn, but especially to Robert K. Meyer for making the visit possible, and for many discussions over the years.     

Applications of weak Kripke semantics to intermediate consequences

Section 1 contains a Kripke-style completeness theorem for arbitrary intermediate consequences. In Section 2 we apply weak Kripke semantics to splittings in order to obtain generalized axiomatization criteria of the Jankov-type. Section 3 presents new and short proofs of recent results on implicationless intermediate consequences. In Section 4 we prove that these consequences admit no deduction theorem. In Section 5 all maximal logics in the 3 ^rd counterslice are determined. On these results we reported at the 1980 meeting on Mathematical Logic at Oberwolfach. This paper concerns propositional logic only.     

Abstract modal logics

In this paper we develop a general framework to deal with abstract logics associated with a given modal logic. In particular we study the abstract logics associated with the weak and strong deductive systems of the normal modal logicK and its intuitionistic version. We also study the abstract logics that satisfy the conditionC ⁺(X)=C( _in I ⁿ X) and find the modal deductive systems whose abstract logics, in addition to being classical or intuitionistic, satisfy that condition. Finally we study the deductive systems whose abstract logics satisfy, in addition to the already mentioned properties, the property that the operatorC ⁺ is classical relative to some new defined operations.Work partially supported by Spanish DGICYT grant PB90-0465-C02-01.Presented byJan Zygmunt