Natural Deduction systems for some weak Subintuitionistic Logics

Fatemeh Shirmohammadzadeh Maleki · 2024

Read Natural Deduction systems for some weak Subintuitionistic Logics by Fatemeh Shirmohammadzadeh Maleki (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-00459.txt.

Introduction

Fatemeh Shirmohammadzadeh Maleki wrote a 2024 paper in mathematical logic on natural deduction systems for some weak subintuitionistic logics. These logics drop some rules of intuitionistic logic. Natural deduction is a proof style that mirrors everyday reasoning with assumptions. Maleki introduces deduction systems tailored to several of these weak logics and proves normalization theorems for them, showing that proofs can be put into a tidy standard form. The hosted text gives only this short summary of the work.

Catalog record

CREATORFatemeh Shirmohammadzadeh Maleki
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-00459

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Natural Deduction systems for some weak Subintuitionistic Logics Fatemeh Shirmohammadzadeh Maleki Abstract The paper is devoted to the introduction of natural deduction systems for some weak subintuitionistic logics, along with proofs of normalization theorems for these systems. Keywords: Subintuitionistic logics, Natural deduction, Hilbert-style, Normalization. 1 introduction The study of subintuitionistic logics began with the work of G. Corsi [ 6 ] , who introduced a basic system, F , using a Hilbert-style proof framework. The system F is characterized by Kripke frames that impose no conditions on the accessibility relation. Corsi also demonstrated that F can be translated into the modal logic K , similar to how IPC translates into S4 . G. Restall [ 15 ] defined a comparable system SJ , (see also [ 7 ] ). A widely studied extension of F was introduced by A. Visser, known as Basic Logic BPC , formulated in natural deduction style. Visser established the completeness of BPC for finite, irreflexive Kripke models. Substantial research on this logic has since been conducted by M. Ardeshir and W. Ruitenburg (see, for instance, [ 2 , 3 , 4 ] ). D. de Jongh and F. Shirmohammadzadeh Maleki have introduced weaker subintuitionistic logics based on neighborhood semantics [ 8 , 9 , 16 ] . Their work specifically emphasizes the system WF , which is considerably weaker than F , along with its extensions. These systems possess modal counterparts, establishing connections between subintuitionistic and modal logics [ 9 , 10 , 11 ] . Sequent calculi for F are explored in [ 14 , 13 , 21 , 1 , 19 ] . In [ 17 ] , F. Shirmohammadzadeh Maleki introduced and analyzed sequent calculi for specific weak subintuitionistic logics, including WF and F , as well as intermediate logics. To date, however, no natural deduction system has been provided for the logics positioned between WF and F . This paper aims to bridge this gap. In this paper, we introduce natural deduction systems for the subintuitionistic logics WF and F , as well as for certain logics that lie between these two systems. The structure of the paper is as follows: Section 2 provides an overview of Hilbert-style proof systems for selected subintuitionistic logics. In Section 3 , we introduce natural deduction systems for each of the subintuitionistic logics: WF , {\sf WF_{N}} , {\sf WF_{N_{2}}} , {\sf WF}{\sf\widehat{C}} , {\sf WF}{\sf\widehat{D}} , {\sf WFI} , {\sf WFC} , {\sf WFD} , and F . We also demonstrate the equivalence between these natural deduction systems and their corresponding Hilbert systems. In Section 4 , we discuss the normalization process for the natural deduction systems of WF and F , along with some intermediate logics. 2 Preliminaries In this subsection, we review the Hilbert-style system for the basic subintuitionistic logic WF and some of its extensions. The results presented here were previously established in [ 16 , 9 ] . The language of subintuitionistic logics is built from a countable set of atomic propositions, denoted by lowercase letters p,q,\dots from the set \mathsf{Prop} , using the connectives \vee,\wedge,\rightarrow and the propositional constant \bot . We use uppercase latin letters A,B,C,\ldots to represent formulas in this language. The symbol \leftrightarrow is defined as an abbreviation by A\leftrightarrow B\equiv(A\rightarrow B)\wedge(B\rightarrow A) 1. A\rightarrow(A\vee B) 8. A\rightarrow A 2. B\rightarrow(A\vee B) 9. A\rightarrow B B\rightarrow C A\rightarrow C 3. (A\and B)\rightarrow A 10. A\rightarrow B A\rightarrow C A\rightarrow(B\and C) 4. (A\and B)\rightarrow B 11. A\rightarrow C B\rightarrow C (A\vee B)\rightarrow C 5. A A\rightarrow B B 12. A B A\and B 6. A B\rightarrow A 13. A\leftrightarrow B C\leftrightarrow D (A\rightarrow C)\leftrightarrow(B\rightarrow D) 7. A\and(B\vee C)\rightarrow(A\and B)\vee(A\and C) 14. \bot\rightarrow A Figure 1: The Hilbert-style system for {\sf WF} Definition 2.1 . The Hilbert-style axiomatization of the basic subintuitionistic logic WF consists of the axioms and inference rules reported in Figure 1 . In Figure 1 , the rules should be applied in such a way that, if the formulas above the line are theorems of WF , then the formula below the line is a theorem as well and we will refer to rules 5, 6, and 12 as the modus ponens (MP), a fortiori (AF), and conjunction rules, respectively. The basic notion \vdash_{{\sf WF}}A means that A can be drived from the axioms of the WF by means of its rules. But, when one axiomatizes local validity, not all rules in a Hilbert type system have the same status when one considers deductions from assumptions. In the case of deductions from assumptions, we impose restrictions on all rules except the conjunction rule. The restriction on modus ponens is slightly weaker than on the other rules; when concluding B from A , A\rightarrow B only the implication A\rightarrow B need be a theorem. These considerations lead to the following definition. In this paper we will denote that a formula A is derivable from \Gamma in the Hilbert style system of logic L as \Gamma\,{\vdash_{H{\sf L}}}A . Definition 2.2 . We define \Gamma\,{\vdash_{H{\sf WF}}}A iff there is a derivation of A from \Gamma using the rules 6, 9, 10 , 11 and 13 of Figure 1 , only when there are no assumptions, and the rule 5, MP, only when the derivation of A\rightarrow B contains no assumptions. The logic WF can be extended by adding various rules and axiom schemes. In this paper, we will focus on the following axioms and rules: (A\rightarrow B)\wedge(B\rightarrow C)\rightarrow(A\rightarrow C)~~~~~~~~~~{\sf I} (A\rightarrow B)\wedge(A\rightarrow C)\rightarrow(A\rightarrow B\wedge C)~~~~{\sf C} (A\rightarrow C)\wedge(B\rightarrow C)\rightarrow(A\vee B\rightarrow C)~~~~{\sf D} (A\rightarrow B\wedge C)\rightarrow(A\rightarrow B)\wedge(A\rightarrow C)~~~~{\sf\widehat{C}} (A\vee B\rightarrow C)\rightarrow(A\rightarrow C)\wedge(B\rightarrow C)~~~~{\sf\widehat{D}} \frac{A\rightarrow B\vee C~~~~~C\rightarrow A\vee D~~~~~A\wedge D\rightarrow B~~~~~C\wedge B\rightarrow D}{(A\rightarrow B)\leftrightarrow(C\rightarrow D)}~~~~{\sf N} ~~~~~\frac{C\rightarrow A\vee D~~~~~~~C\wedge B\rightarrow D}{(A\rightarrow B)\rightarrow(C\rightarrow D)}~~~~~~~~~~{\sf N_{2}} If \Gamma\subseteq\{{\sf I},{\sf C},{\sf D},{\sf\widehat{C}},{\sf\widehat{D}},{\sf N},{\sf N_{2}}\} , we denote by {\sf WF\Gamma} the logic obtained from WF by adding the schemas and rules in \Gamma as new axioms and rules. Instead of writing {\sf WFN} and {\sf WFN_{2}} we will use {\sf WF_{N}} and {\sf WF_{N_{2}}} , respectively. The logic F is the smallest set of formulas closed under instances of WF , C , D and I [ 16 ] . A weak form of the deduction theorem with a single assumption is obtained: Theorem 2.3 . (Weak Deduction theorem, [ 16 , 9 ] ) \bullet A\vdash_{H{\sf WF\Gamma}}B~ iff ~\vdash_{H{\sf WF\Gamma}}A\rightarrow B . \bullet A_{1},\dots,A_{n}\vdash_{H{\sf WF\Gamma}}B~ iff ~\vdash_{H{\sf WF\Gamma}}A_{1}\wedge\dots\wedge A_{n}\rightarrow B . In the subsequent sections, we will present the first natural deduction system for the subintuitionistic logics WF , {\sf WF_{N}} , {\sf WF_{N_{2}}} , {\sf WF}{\sf\widehat{C}} , {\sf WF}{\sf\widehat{D}} , {\sf WFI} , {\sf WFC} , {\sf WFD} and F . 3 Natural Deduction system In this section, along with introducing the natural deduction system for the logics WF , {\sf WF_{N}} , {\sf WF_{N_{2}}} , {\sf WF}{\sf\widehat{C}} , {\sf WF}{\sf\widehat{D}} , {\sf WFI} , {\sf WFC} , {\sf WFD} and F , we will prove that these natural deduction systems are equivalent to their corresponding Hilbert systems. Assumptions in a natural deduction proof can be either canceled (or discharged) or uncanceled (or open). Initially, all assumptions are open, but specific inferences allow for some assumptions to be discharged. This

Read the complete text