betaFeedback

WorksMathematics

A Kleene-inspired sequent system for a minimal logic of evidence and truth

Abstract

This paper investigates the proof theory of the logic of evidence and truth LETFm, with the aim of obtaining a sequent calculus consisting only of logical rules, suitable for a simple bottom-up decision procedure. We begin with G1f, a sequent system containing structural rules, which makes explicit the main difficulties in obtaining a fully logical and decidable calculus for LETFm. We then introduce G3f, a G3-style system obtained from by applying Kleene's trick, which absorbs contraction into the logical rules by adding the principal formula of the rule to its premises.

This paper is a small tribute to Professor Luiz Carlos Pereira, a great logician and Flamengo supporter – a sure sign of wisdom and good taste – in recognition of his intellectual influence and a long-standing friendship with one of the authors, dating back to 2002.

Introduction

Logics of evidence and truth (LETLETs) form a family of paraconsistent and paracomplete logics. They extend the logic of first-degree entailment (FDEFDE), also known as Belnap–Dunn four-valued logic (e.g. [4, 16]), with a unary operator ∘\circ designed to recover classical negation to formulas within its scope. The sentential logic LETF−LET_{F}^{-} is a minimal LETLET, obtained by adding ∘\circ and its inference rules to FDEFDE.

This paper investigates the proof theory of LETF−LET_{F}^{-}. More precisely, our aim is to present a sequent calculus for LETF−LET_{F}^{-} with purely logical rules, and to use it to obtain a simple bottom-up decision procedure. We do so by first introducing the system G1f−G1f^{-}, a sequent system which contains the structural rules and highlights the problems that must be addressed in order to get to our aimed fully logical and decidable sequent system for LETF−LET_{F}^{-}. The system G1f−G1f^{-} is then modified into a system that we call G3f−G3f^{-}, a G3G3-style system inspired by Kleene [19 §80, pp. 479ff.]. G3f−G3f^{-} is obtained from G1f−G1f^{-} by applying the so-called Kleene’s trick, which consists in duplicating the principal formula in the premises so that contraction is absorbed into the logical rules.

The remainder of this text is structured as follows. § 2 provides a brief presentation of LETLETs, their motivations, and their historical background. Readers interested primarily in proof theory may skip this section and proceed directly to § 3, which begins by presenting a natural deduction system for LETF−LET_{F}^{-}, called Nf−Nf^{-}, together with a sound and complete bivalued semantics. Nf−Nf^{-} is the sentential fragment of a first-order version of LETF−LET_{F}^{-}, investigated in [25]. In § 3 we also introduce the sequent system G1f−G1f^{-}, and show, based on results from [11], that the cut rule can be eliminated from deductions in G1f−G1f^{-}. In § 4 we introduce the cut-free system G3f−G3f^{-}, and show that all structural rules are admissible in it. In this Section we also establish the main result of this paper, namely, the decidability of LETF−LET_{F}^{-} by means of a bottom-up decision method for G3f−G3f^{-}. Finally, in § 5, we outline directions for future research.

On the logics of evidence and truth

We begin by formally characterizing logics of formal inconsistency (LFIsLFIs) and logics of formal undeterminedness (LFUsLFUs). Logics of evidence and truth are simultaneously LFI\mathit{LFI}s and LFU\mathit{LFU}s.

Let L\mathbf{L} be a Tarskian, compact, and structural logic equipped with a negation ¬\neg, a standard disjunction ∨\lor, and a unary connective ∘\circ. Consider the following conditions:

(i) A,¬A⊬BA,\neg A \nvdash B for some AA and BB;

(ii) ∘A,A⊬B\circ A,A \nvdash B and ∘A,¬A⊬B\circ A,\neg A \nvdash B for some AA and BB;

(iii) ∘A,A,¬A⊢B\circ A,A,\neg A \vdash B for every AA and BB.

(iv) ⊬A∨¬A\nvdash A\lor\neg A for some AA;

(v) ∘A⊬A\circ A \nvdash A and ∘A⊬¬A\circ A \nvdash\neg A for some AA;

(vi) ∘A⊢A∨¬A\circ A \vdash A\lor\neg A for every AA.

L\mathbf{L} is a logic of formal inconsistency (LFI\mathit{LFI}) if conditions (i)–(iii) hold, and a logic of formal undeterminedness (LFU\mathit{LFU}) if conditions (iv)–(vi) hold. Conditions (ii) and (v) are needed to ensure that (iii) and (vi) hold in a non-trivial way. If all the above conditions hold, L\mathbf{L} is a logic of formal inconsistency and undeterminedness, i.e. an LFIU\mathit{LFIU}.

The terminology LFI\mathit{LFI} and LFU\mathit{LFU} was introduced by Carnielli [6] and Marcos [21]. The underlying ideas, however, can be traced back to da Costa’s earlier work: LFIs\mathit{LFIs} further develop the CnC_n hierarchy of paraconsistent logics introduced in the 1960s [12], and the recovery of the law of excluded middle in a way analogous to explosion was already investigated in the 1980s [13, 14]. LFIs\mathit{LFIs} and LFUs\mathit{LFUs} have been investigated by several authors, especially by those associated with the so-called Brazilian school of paraconsistency (see e.g. [5, 6, 9, 20, 22]). The idea of a logic of evidence and truth first appeared in [7 Section 3.3.2], where a minimal LFI\mathit{LFI} called mbC\mathit{mbC} was modified so as to be faithful to the intended interpretation in terms of conclusive and non-conclusive evidence. LET\mathit{LET}s, as well as LFIs\mathit{LFIs} and LFUs\mathit{LFUs}, thus, belong to the evolutionary line of paraconsistent and paracomplete logics initiated by da Costa’s pioneering work, which introduced systems with two notions of consequence: one sub-classical and one classical, the latter being recovered by means of a ∘\circ-style operator.

Let us now provide a more precise characterization of logics of evidence and truth. They are LFIU\mathit{LFIU}s that have FDE\mathit{FDE} as a fragment, and they come with an intended intuitive interpretation in terms of evidence that may fail to be conclusive (see e.g. [8, 25, 26]). In this setting, ∘A\circ A expresses that whatever evidence is available for AA, whether positive or negative, is taken to be conclusive; when ∘A\circ A does not hold, the evidence is non-conclusive. The intuitive interpretation assumes that conclusive evidence is governed by classical logic. Thus, a formula ∘A\circ A implies that classical reasoning holds for AA, as well as for all formulas built from AA using the connectives ∧\land, ∨\lor, and ¬\neg. In [27], an alternative but closely related intuitive interpretation in terms of information has been proposed for LETs. Accordingly, a sentence ∘A\circ A means that the information conveyed by AA, positive or negative, is reliable, and when ∘A\circ A does not hold, it means that there is no reliable information about AA. This reading appears as a natural development of the information-based interpretation of FDE, introduced by Belnap and Dunn in the 1970s (see e.g. [4, 16]).

The logic LETF−LET^{-}_{F} is a minimal LETLET, obtained by simply adding to FDEFDE rules validating the inferences below:

(1) ∘A,A,¬A⊢B and\text{(1) }\circ A, A, \neg A \vdash B\text{ and}
(2) ∘A⊢A∨¬A,\text{(2) }\circ A \vdash A \lor\neg A,

which recover classical logic for sentences in the scope of ∘\circ. LETF−LET^{-}_{F} is the →\to-free fragment of the logic LETJLET_{J}, introduced in [8] and further investigated in [2, 25]. LETJLET_{J} is equipped with a constructive implication – it is obtained by adding to Nelson’s logic N4N4 [1] the inferences (1) and (2) above. The proof theory of LETJLET_{J} was investigated in [25], which provides the basis for some of the results established here. LETF−LET^{-}_{F} is also the ∙\bullet-free fragment of the logic LETFLET_{F}, investigated in [27] (∙\bullet is a non-classicality operator: it has a deductive behavior dual to ∘\circ and ∙A\bullet A means that there is no conclusive evidence about AA – see [27 Section 3.1]). A first-order version of LETF−LET^{-}_{F} has been studied in [25].

The notion of evidence for a sentence AA that underlies the intuitive interpretation of LETs can ben explained as ‘reasons for believing in or accepting $A’. These reasons may be non-conclusive or wrong, and so evidence for AA does not imply the truth of AA. There may be simultaneous conflicting evidence for sentences AA and ¬A\neg A, and evidence for AA is meant to be objective in the sense that it is independent from the belief of an agent in AA. It must be observed that accepting a contradiction in a context of reasoning is not to be understood as a rational acceptance: the contradictory evidence is merely admitted, in the sense that one should be able to reason in its presence. The interpretation in terms of information takes the definition of information as meaningful data (see [17, 18]), which allows information to be false. A more detailed discussion of the notion of evidence and information can be found in [26 Section 2], and an exposition that emphasizes the interpretation in terms of information can be found in [25 Sections 2 and 3] and [3 Section 2].

The logic LET-F and the system G1f-

Consider a denumerable set V\mathcal{V} of sentential letters and the set of connectives S0={∧,∨,¬,∘}\mathcal{S}_0 = \{\wedge, \vee, \neg, \circ\}. The language L0\mathcal{L}_0 is the set of formulas generated by V\mathcal{V} over S0\mathcal{S}_0. Roman capitals AA, BB, CC, …\ldots will be used as metavariables for the formulas of L0\mathcal{L}_0, while Greek capitals Γ\Gamma, Δ\Delta, Σ\Sigma, …\ldots will be used as metavariables for finite sets of formulas.

Definition 3.1. (The natural deduction system Nf−N_{f-})

The deductive system Nf−N_{f-} is defined over the language L0\mathcal{L}_0 by the following rules:

D1D2AB ∧IDA∧B ∧EDA∧B ∧EDA ∨IDB ∨ID1[A]u[B]vA∨BCC ∨E,u,vD¬A ¬∧ID¬B ¬∧ID1[¬A]u[¬B]v¬(A∧B)CC ¬∧E,u,vD1D2¬A¬B ¬∨ID¬(A∨B) ¬∨ED¬(A∨B) ¬∨E\begin{aligned} &\frac{\mathcal{D}_1\quad\mathcal{D}_2}{A\quad B}\,\wedge I\qquad \frac{\mathcal{D}}{A\wedge B}\,\wedge E\qquad \frac{\mathcal{D}}{A\wedge B}\,\wedge E\\ &\frac{\mathcal{D}}{A}\,\vee I\qquad \frac{\mathcal{D}}{B}\,\vee I\qquad \frac{\mathcal{D}_1\quad[A]^u\quad[B]^v}{A\vee B\quad C\quad C}\,\vee E,u,v\\ &\frac{\mathcal{D}}{\neg A}\,\neg\wedge I\qquad \frac{\mathcal{D}}{\neg B}\,\neg\wedge I\qquad \frac{\mathcal{D}_1\quad[\neg A]^u\quad[\neg B]^v}{\neg(A\wedge B)\quad C\quad C}\,\neg\wedge E,u,v\\ &\frac{\mathcal{D}_1\quad\mathcal{D}_2}{\neg A\quad\neg B}\,\neg\vee I\qquad \frac{\mathcal{D}}{\neg(A\vee B)}\,\neg\vee E\qquad \frac{\mathcal{D}}{\neg(A\vee B)}\,\neg\vee E \end{aligned}
DA¬¬A ¬¬ID¬¬AA ¬¬E\frac{\mathcal{D}}{A \over\neg\neg A}\ \neg\neg I \qquad \frac{\mathcal{D}}{\neg\neg A \over A}\ \neg\neg E
D1D3D2∘A¬AAB EXP∘[A]u[¬A]vD1D2D3∘ABBB PEM∘,u,v\frac{\mathcal{D}_1\quad\mathcal{D}_3\quad\mathcal{D}_2}{\mathord{\circ}A\quad\neg A\quad A \over B}\ EXP^{\circ} \qquad \frac{[A]^u\quad[\neg A]^v\quad\mathcal{D}_1\quad\mathcal{D}_2\quad\mathcal{D}_3}{\mathord{\circ}A\quad B\quad B \over B}\ PEM^{\circ},u,v

The assumption classes [A]u[A]^u, [B]v[B]^v, [¬A]u[\neg A]^u, [¬B]v[\neg B]^v contain open assumptions of the deductions of the premises of the final inference, but are closed in the whole deduction. Also, we define major and minor premises as usual, except in the rule EXP∘EXP^{\circ}, where there is no notion of major or minor premises.

The definition of a derivation of AA from Γ\Gamma in Nf−N_{f-} is the usual one for natural deduction systems (recall that we assume here that Γ\Gamma is a finite set). It suffices to say that a derivation D\mathcal{D} is a tree of formulas whose nodes are either elements of Γ\Gamma or are obtained from earlier nodes by applications of the rules above, and whose bottom node is its conclusion. We write Γ⊢Nf−A\Gamma\vdash_{N_{f-}} A to mean that there exists a derivation in Nf−N_{f-} from the premises in Γ\Gamma with conclusion AA, omitting the subscript when there is no risk of confusion.

Definition 3.2. (Valuation semantics for LETF−LET_F^{-})

A bivalued semantics for LETF−LET_F^{-} is given by the class of functions v:L0→{0,1}v : L_0 \to\{0,1\} satisfying the following clauses:

v1. v(A∧B)=1v(A \land B) = 1 iff v(A)=1v(A) = 1 and v(B)=1v(B) = 1,

v2. v(A∨B)=1v(A \lor B) = 1 iff v(A)=1v(A) = 1 or v(B)=1v(B) = 1,

v3. v(¬(A∧B))=1v(\neg(A \land B)) = 1 iff v(¬A)=1v(\neg A) = 1 or v(¬B)=1v(\neg B) = 1,

v4. v(¬(A∨B))=1v(\neg(A \lor B)) = 1 iff v(¬A)=1v(\neg A) = 1 and v(¬B)=1v(\neg B) = 1,

v5. v(A)=1v(A) = 1 iff v(¬¬A)=1v(\neg\neg A) = 1,

v6. If v(∘A)=1v(\mathord{\circ}A) = 1, then v(A)=1v(A) = 1 if and only if v(¬A)=0v(\neg A) = 0.

We say that a formula AA is a semantic consequence of Γ\Gamma, written Γ⊨LETF−A\Gamma\models_{LET_F^{-}} A, if and only if for every valuation vv, whenever v(B)=1v(B) = 1 for all B∈ΓB \in\Gamma, then v(A)=1v(A) = 1.

As remarked in the Introduction, the logic LETF−LET_{F}^{-} is a fragment of both the sentential logics LETJLET_{J} and LETFLET_{F}, introduced in [8] and [27] respectively. LETFLET_{F} extends LETF−LET_{F}^{-} with the operator ∙\bullet, already mentioned in Section 2, together with its corresponding rules. The semantics presented above is obtained simply by suppressing the clause for the ∙\bullet connective in the semantics of LETFLET_{F} [27 Definition 26]. A natural deduction system for LETF−LET_{F}^{-} is obtained just by dropping the ∙\bullet-rules from the deductive system of LETFLET_{F} [27 Definition 23]. The system presented here differs from the ∙\bullet-free system of [27] only with respect to the rule that recovers excluded middle, but both are equivalent. A system identical to Nf−N_{f}^{-} is the sentential fragment of the first-order version of LETF−LET_{F}^{-}, investigated in [25].

Nf−N_{f}^{-} is sound and complete with respect to the bivalued semantics presented in Definition 3.2.

Theorem 3.3.

Γ⊢Nf−A if and only if Γ⊨LETF−A\Gamma\vdash_{N_f^{-}} A \text{ if and only if } \Gamma\models_{LET_F^{-}} A

Proof. Since the logic LETF−LET_{F}^{-} is contained in LETFLET_{F}, the soundness and completeness of the system Nf−N_{f}^{-} with respect to the semantics above follow immediately from the corresponding soundness and completeness results for LETFLET_{F} [27 Theorem 28].

The sequent calculus G1f−G_{1f}^{-}

Below, we present the sequent system G1f−G_{1f}^{-}, in which all structural rules are explicit. We discuss the features of this system and show its limitations with respect to our purposes. Later, in Section 4, we will introduce the system G3f−G_{3f}^{-}, with no explicit structural rules.1

Definition 3.4. (The system G1f−G_{1f}^{-})

The system G1f−G1f^{-} is defined over the language L0\mathcal{L}_0. Greek capitals Γ\Gamma, Δ\Delta, Σ\Sigma now denote multisets of formulas of formulas of L0\mathcal{L}_0, and AA, BB range over formulas of L0\mathcal{L}_0. The notions of principal, active and context formulas are understood in the standard way.

Axioms:

A⇒AIdA \Rightarrow A \quad Id

Structural rules:

Γ⇒CA,Γ⇒C LWΓ′⇒AA,Γ⇒CΓ′,Γ⇒C CutA,A,Γ⇒CA,Γ⇒C LC\frac{\Gamma\Rightarrow C}{A,\Gamma\Rightarrow C}\ LW \qquad \frac{\Gamma' \Rightarrow A \qquad A,\Gamma\Rightarrow C}{\Gamma',\Gamma\Rightarrow C}\ Cut \qquad \frac{A,A,\Gamma\Rightarrow C}{A,\Gamma\Rightarrow C}\ LC

Logical rules:

A,B,Γ⇒CA∧B,Γ⇒C L∧Γ⇒AΓ⇒BΓ⇒A∧B R∧\frac{A,B,\Gamma\Rightarrow C}{A \land B,\Gamma\Rightarrow C}\ L\land \qquad \frac{\Gamma\Rightarrow A \qquad\Gamma\Rightarrow B}{\Gamma\Rightarrow A \land B}\ R\land
A,Γ⇒CB,Γ⇒CA∨B,Γ⇒C L∨Γ⇒AΓ⇒A∨B R∨Γ⇒BΓ⇒A∨B R∨\frac{A,\Gamma\Rightarrow C \qquad B,\Gamma\Rightarrow C}{A \lor B,\Gamma\Rightarrow C}\ L\lor \qquad \frac{\Gamma\Rightarrow A}{\Gamma\Rightarrow A \lor B}\ R\lor \qquad \frac{\Gamma\Rightarrow B}{\Gamma\Rightarrow A \lor B}\ R\lor
¬A,¬B,Γ⇒C¬(A∨B),Γ⇒C L¬∨Γ⇒¬AΓ⇒¬BΓ⇒¬(A∨B) R¬∨\frac{\neg A,\neg B,\Gamma\Rightarrow C}{\neg(A \lor B),\Gamma\Rightarrow C}\ L_{\neg\lor} \qquad \frac{\Gamma\Rightarrow\neg A \qquad\Gamma\Rightarrow\neg B}{\Gamma\Rightarrow\neg(A \lor B)}\ R_{\neg\lor}
¬A,Γ⇒C¬B,Γ⇒C¬(A∧B),Γ⇒C L¬∧Γ⇒¬AΓ⇒¬(A∧B) R¬∧Γ⇒¬BΓ⇒¬(A∧B) R¬∧\frac{\neg A,\Gamma\Rightarrow C \qquad\neg B,\Gamma\Rightarrow C}{\neg(A \land B),\Gamma\Rightarrow C}\ L_{\neg\land} \qquad \frac{\Gamma\Rightarrow\neg A}{\Gamma\Rightarrow\neg(A \land B)}\ R_{\neg\land} \qquad \frac{\Gamma\Rightarrow\neg B}{\Gamma\Rightarrow\neg(A \land B)}\ R_{\neg\land}
A,Γ⇒C¬A,Γ⇒C∘A,Γ⇒C L∘1Γ⇒AΓ⇒¬A∘A,Γ⇒C L∘2\frac{A,\Gamma\Rightarrow C \qquad\neg A,\Gamma\Rightarrow C}{\mathord{\circ}A,\Gamma\Rightarrow C}\ L_{\circ1} \qquad \frac{\Gamma\Rightarrow A \qquad\Gamma\Rightarrow\neg A}{\mathord{\circ}A,\Gamma\Rightarrow C}\ L_{\circ2}
A,Γ⇒C¬¬A,Γ⇒C L¬¬Γ⇒AΓ⇒¬¬A R¬¬\frac{A,\Gamma\Rightarrow C}{\neg\neg A,\Gamma\Rightarrow C}\ L_{\neg\neg} \qquad \frac{\Gamma\Rightarrow A}{\Gamma\Rightarrow\neg\neg A}\ R_{\neg\neg}

A derivation in G1f−G1f^{-} is defined in the usual way as a finite tree of sequents such that each node of the tree is a sequent, the leaves are initial sequents of the calculus (axioms), and each non-leaf node is obtained from its immediate predecessors by an application of one of the inference rules. The bottom sequent of the tree is called the conclusion of the derivation. A sequent Γ⇒C\Gamma\Rightarrow C is said to be derivable in the G1f−G1f^{-} if there exists a derivation whose conclusion is Γ⇒C\Gamma\Rightarrow C.

We now introduce some definitions that will be useful in the remainder of the paper.

Definition 3.5. (Generalized subformulas, formula weight and proof height)

A literal, ll, is either an atomic formula pp or the negation ¬p\neg p of an atomic formula pp.

  1. The weight of a formula AA, denoted w(A)w(A), is defined as follows:

(a) w(l)=0w(l) = 0, where ll is a literal;

(b) w(¬¬A)=w(A)+1w(\neg\neg A) = w(A) + 1;

(c) w(A∗B)=w(A)+w(B)+1w(A \ast B) = w(A) + w(B) + 1, for ∗∈{∧,∨}\ast\in\{\land, \lor\};

(d) w(¬(A∗B))=w(¬A)+w(¬B)+1w(\neg(A \ast B)) = w(\neg A) + w(\neg B) + 1, for ∗∈{∧,∨}\ast\in\{\land, \lor\};

(e) w(∘A)=w(A)+w(¬A)+1w(\circ A) = w(A) + w(\neg A) + 1;

  1. We define the notion of generalized subformula as follows:

(a) AA is a generalized subformula of AA;

(b) AA is a generalized subformula of ¬A\neg A;

(c) AA and BB are generalized subformulas of both A∗BA \ast B, ∗∈{∨,∧}\ast\in\{\lor, \land\};

(d) ¬A\neg A and ¬B\neg B are generalized subformulas of ¬(A∗B)\neg(A \ast B), ∗∈{∨,∧}\ast\in\{\lor, \land\};

(e) AA and ¬A\neg A are generalized subformulas of ∘A\circ A.

  1. The height of a derivation DD, denoted h(D)h(D), is defined as follows:

(a) If DD is a derivation consisting of an initial (axiomatic) sequent, then h(D)=0h(D) = 0.

(b) If DD is a derivation of a sequent SS obtained from a single premise S′S' by an inference rule, and D′D' is a derivation of S′S', then h(D)=h(D′)+1h(D) = h(D') + 1.

(c) If DD is a derivation of a sequent SS obtained from two premises S′S' and S′′S'' by an inference rule, and D′D' and D′′D'' are derivations of S′S' and S′′S'', respectively, then h(D)=max⁡(h(D′),h(D′′))+1h(D) = \max(h(D'), h(D'')) + 1.

The definition extends in the obvious way to rules with more than two premises by taking the maximum over all immediate subderivations. Also, we can easily adapt this definition to natural deduction settings by replacing the word “sequent” by the word “formula”, and, in item (a), replacing “initial (axiomatic) sequent” for “open assumption”.

Theorem 3.6. For every derivation in G1f−G1f^{-} that uses the rule CutCut, there exists a derivation of the same end-sequent that does not use the rule CutCut.

Proof. In [11], cut-elimination is established for GLETJGLET_{J} through a proof of elimination of multicut. The logical rules of G1f−G1f^{-} are precisely the →\to-free fragment of those of GLETJGLET_{J}. While GLETJGLET_{J} treats contexts as sets, thus making explicit contraction unnecessary, G1f−G1f^{-} uses multisets and therefore requires an explicit contraction rule. Adapting the cut-elimination proof from GLETJGLET_{J} (with sets) to G1f−G1f^{-} (with multisets) is essentially routine, and the use of multicut accounts for the known problems caused by contraction. □

The system G1f−G1f^{-} is inspired by the systems G1iG1i and G3iG3i presented in Troelstra and Schwichtenberg [29 Chapter 3]. It extends G1iG1i with rules for ¬∧\neg\land and ¬∨\neg\lor, which behave as the positive rules for ∨\lor and ∧\land (with ∧\land formulated as in G3iG3i), and with rules for ∘\circ, taken from GLETJGLET_{J}, a sequent calculus for the logic of evidence and truth LETJLET_{J}, introduced in [11].

By contrast with G1iG1i and G3iG3i, which are able to prove the elimination of the non-atomic axiom rule (see [29 pp. 65]), in G1f−G1f^{-} we cannot restrict the axiom rule to literals as principal formulas. The reason is that, under such a restriction, we cannot derive ∘A⇒∘A\circ A \Rightarrow\circ A, since there is no right rule for ∘\circ.

Besides highlighting the peculiarities of a sequent system for LETF−LET_{F}^{-}, there is another reason for introducing G1f−G1f^{-} first. Its logical rules provide a more convenient setting for proving its equivalence with Nf−N_{f}^{-}. Indeed, this equivalence is established in Section 3.2 below, and soundness and completeness with respect to the bivaluation semantics of Definition 3.2 follow from it.

In the following we show some constructive features of G1f−G1f^{-} and we prove the equivalence between the natural deduction system Nf−N_{f}^{-} and G1f−G1f^{-}.

Proposition 3.7. (Disjunction property and constructive falsity)

(i) Disjunction property: if ⇒A∨B\Rightarrow A \lor B is derivable in G1f−G1f_{-}, then either ⇒A\Rightarrow A or ⇒B\Rightarrow B is derivable in G1f−G1f_{-}.

(ii) Constructive falsity: if ⇒¬(A∧B)\Rightarrow\neg(A \land B) is derivable in G1f−G1f_{-}, then either ⇒¬A\Rightarrow\neg A or ⇒¬B\Rightarrow\neg B is derivable in G1f−G1f_{-}.

Proof. For (i), given a cut-free derivation of ⇒A∨B\Rightarrow A \lor B, the only rule that can introduce the formula A∨BA \lor B on the right is R∨R\lor. For (ii), given a cut-free derivation of ⇒¬(A∧B)\Rightarrow\neg(A \land B), the only rule that can introduce the formula ¬(A∧B)\neg(A \land B) on the right is R¬∧R_{\neg\land}.

We can strengthen this result by adapting the notion of Harrop formulas to our setting.

Definition 3.8. The class H\mathcal{H} of Harrop-like formulas is defined as follows:

  1. Every literal is an H\mathcal{H}-formula.

  2. If AA and BB are H\mathcal{H}-formulas, then A∧BA \land B is a H\mathcal{H}-formula.

  3. If ¬A\neg A and ¬B\neg B are H\mathcal{H}-formulas, then ¬(A∨B)\neg(A \lor B) is a H\mathcal{H}-formula.

  4. For any AA, ¬∘A\neg_{\circ} A is an H\mathcal{H}-formula.

  5. Nothing else is an H\mathcal{H}-formula.

Proposition 3.9.

(i) Strong disjunction property: if Γ⇒A∨B\Gamma\Rightarrow A \lor B is derivable in G1f−G1f_{-} and Γ\Gamma consists only of H\mathcal{H}-formula, then either Γ⇒A\Gamma\Rightarrow A or Γ⇒B\Gamma\Rightarrow B is derivable in G1f−G1f_{-}.

(ii) Strong constructive falsity: if Γ⇒¬(A∧B)\Gamma\Rightarrow\neg(A \land B) is derivable in G1f−G1f_{-} and Γ\Gamma consists only of H\mathcal{H}-formula, then either Γ⇒¬A\Gamma\Rightarrow\neg A or Γ⇒¬B\Gamma\Rightarrow\neg B is derivable in G1f−G1f_{-}.

Proof.

(i) If n=0n = 0, then the derivation is an axiom, and hence it must have the form A⇒AA \Rightarrow A. Thus, the end-sequent cannot be Γ⇒A∨B\Gamma\Rightarrow A \lor B with Γ\Gamma consisting only of H\mathcal{H}-formulas. Now suppose n>0n > 0 and Γ\Gamma is composed of H\mathcal{H}-formulas. If the last rule applied is R∨R\lor, then Γ⇒A\Gamma\Rightarrow A or Γ⇒B\Gamma\Rightarrow B, respectively, is a premise of the last inference. If the last rule is L¬∨L\neg\lor, then Γ=¬(C∨D)\Gamma= \neg(C\lor D), Γ′\Gamma' and the premise is ¬C,¬D,Γ′⇒A∨B\neg C,\neg D,\Gamma' \Rightarrow A\lor B. Since ¬(C∨D)\neg(C\lor D) is a H\mathcal{H}-formula, ¬C\neg C and ¬D\neg D are H\mathcal{H}-formulas as well. By the inductive hypothesis, either ¬C,¬D,Γ′⇒A\neg C,\neg D,\Gamma' \Rightarrow A or ¬C,¬D,Γ′⇒B\neg C,\neg D,\Gamma' \Rightarrow B. If LWLW was used to derive Γ⇒A∨B\Gamma\Rightarrow A\lor B, introducing an H\mathcal{H}-formula on the left, we can proceed in the obvious way, since the induction hypothesis will apply to the premise. Analogous reasoning applies when the last rule is L∧L\land. If any other rule is the last rule, then Γ\Gamma is not composed of H\mathcal{H}-formulas.

(ii) This proof can be directly adapted to the case of the strong constructive falsity property by simply considering the rule R¬∧R\neg\land in the place of R∨R\lor. The cases of L∧L\land and L¬∨L\neg\lor are analogous.

Remark 3.10. (On the constructive character of LETF−\mathit{LET}_{F}^{-})

(i) The idea of a constructive negation was proposed by Nelson [24], where the first-order logic NN is introduced. The sentential fragment of NN is the logic N3N3, and N4N4 is obtained by dropping explosion from N3N3. Nelson’s motivation was to provide a logic that could serve as the underlying logic of a number theory with constructive features lacking in intuitionistic logic (see Nelson [24], pp. 16ff.). Both N3N3 and N4N4 have a constructive negation and also a constructive implication. That is, instead of proving the falsity of a formula AA by deriving a contradiction from the assumption AA, one proves ¬A\neg A directly (the notion of a proof of ¬p\neg p is primitive, just like that of a proof of pp). Nelson thus provided a negation that fits the underlying idea of information-based logics, namely, that positive and negative information must be treated independently of each other (see [30], pp. 13ff.). From the point of view of both the evidence interpretation and the information-based interpretation, the validity of the constructive falsity property is indeed as desirable as the disjunction property.

(ii) Roughly, the underlying idea behind Harrop formulas is to preserve the constructive content of proofs. Thus, positive occurrences of disjunction are restricted, ensuring that any proof of a disjunction provides a constructive choice, i.e. an effective method for determining which alternative holds. The same idea applies to ¬(A∧B)\neg(A\land B), which is equivalent to ¬A∨¬B\neg A\lor\neg B, in a context

with constructive negation. A formula ∘A\circ A cannot be an H\mathcal{H}-formula, since it implies A∨¬AA \lor\neg A, which is equivalent to ¬(A∧¬A)\neg(A \land\neg A). Whenever either formula holds, even if restricted to one or a few instances, we can derive formulas of the form A∨BA \lor B, as well as formulas of the form ¬(A∧B)\neg(A \land B), without a constructive choice. This is incompatible with both the disjunction property and the constructive falsity property. On the other hand, formulas of the form ¬∘A\neg\circ A are innocuous and do not compromise either of these properties.

It is also worth noting that Propositions 3.7 and 3.9 above are interesting, but not at all unexpected. The logic FDEFDE, which is the ∘\circ-free fragment of LETF−LET^{-}_{F}, and the →\to-free fragment of N4N4, is constructive. On the other hand, formulas in the scope of ∘\circ exhibit classical, non-constructive behavior.

(iii) Note that the results of Propositions 3.7 and 3.9 are features of LETF−LET^{-}_{F}, so they hold for the natural deduction system Nf−N_{f-} and are inherited by G3f−G_{3f-}, to be introduced in § 4.

Now, we turn to the equivalence between Nf−N_{f-} and G1f−G_{1f-}.

Equivalence between Nf−N_{f-} and G1f−G_{1f-}

The notation Nf−⊢Γ⇒CN_{f-} \vdash\Gamma\Rightarrow C means that there exists a derivation of CC in Nf−N_{f-} from the open assumptions in Γ\Gamma. The notation G1f−⊢Γ⇒CG_{1f-} \vdash\Gamma\Rightarrow C means that there exists a derivation of the sequent Γ⇒C\Gamma\Rightarrow C in G1f−G_{1f-}. Note that although Γ\Gamma is a set of formulas in natural deduction, in the translation of a derivation into a sequent we treat Γ\Gamma as a multiset: each open assumption class [A]u[A]^u (with a distinct label) contributes one occurrence of AA on the left-hand side of the corresponding sequent.

The derivability relation of Nf−N_{f-} admits left contraction and left weakening. More precisely, if Nf−⊢A,A,Γ⇒CN_{f-} \vdash A, A, \Gamma\Rightarrow C, then Nf−⊢A,Γ⇒CN_{f-} \vdash A, \Gamma\Rightarrow C, and if Nf−⊢Γ⇒CN_{f-} \vdash\Gamma\Rightarrow C, then Nf−⊢A,Γ⇒CN_{f-} \vdash A, \Gamma\Rightarrow C. Contraction is obtained by identifying the labels of two distinct assumption classes containing the same formula. Left weakening is obtained as follows:

Γ⇒CA,Γ⇒C LWbecomesΓ⋮[A]uCA∧CC\frac{\Gamma\Rightarrow C}{A,\Gamma\Rightarrow C}\ \mathrm{LW} \qquad\text{becomes}\qquad \frac{\begin{gathered}\Gamma\\ \vdots\\ [A]^u\quad C\end{gathered}}{\frac{A\land C}{C}}

Left weakening corresponds to the monotonicity of the derivability relation: if a formula CC is derivable from the assumptions Γ\Gamma, then CC is also derivable from Γ,A\Gamma,A, where the added assumption AA may remain unused in the derivation. These properties are required in order to establish the equivalence between Nf−N_{f-} and G1f−G1_{f-}, since G1f−G1_{f-} includes both weakening and contraction as explicit structural rules.

Theorem 3.11. G1f−⊢Γ⇒CG1_{f-}\vdash\Gamma\Rightarrow C if and only if Nf−⊢Γ⇒CN_{f-}\vdash\Gamma\Rightarrow C.

Proof. Assume that the proof of Γ⇒C\Gamma\Rightarrow C in G1f−G1_{f-} is cut-free.

From left to right, the proof proceeds by induction on the height nn of derivations in G1f−G1_{f-}. Let Γ\Gamma be a multiset. The notation set(Γ)set(\Gamma) denotes the underlying set associated with Γ\Gamma, that is, the set of formulas occurring in Γ\Gamma, ignoring multiplicities. If n=0n=0, then Γ⇒C\Gamma\Rightarrow C is an axiom. In Nf−N_{f-}, this corresponds to a deduction consisting of a single node CC. If n>0n>0, let D\mathcal{D} be a derivation of Γ⇒C\Gamma\Rightarrow C of height nn in G1f−G1_{f-}. We assume as induction hypothesis that the result holds for all derivations in G1f−G1_{f-} of height at most n−1n-1; that is, for every derivation D′\mathcal{D}' of Γ′⇒C′\Gamma'\Rightarrow C' in G1f−G1_{f-} of height at most n−1n-1, there exists a deduction D′∗\mathcal{D}'^* in Nf−N_{f-} deriving C′C' from set(Γ′)set(\Gamma'). We then consider all the inference rules of G1f−G1_{f-}.

D1D2Γ⇒¬AΓ⇒¬BΓ⇒¬(A∨B) R¬∨goes toD1∗D2∗¬(A∨B) I¬∨\frac{\mathcal{D}_1\quad\mathcal{D}_2} {\frac{\Gamma\Rightarrow\neg A\quad\Gamma\Rightarrow\neg B} {\Gamma\Rightarrow\neg(A\lor B)}}\ R_{\neg\lor} \qquad\text{goes to}\qquad \frac{\mathcal{D}_1^*\quad\mathcal{D}_2^*} {\neg(A\lor B)}\ I_{\neg\lor}
D1¬A,¬B,Γ⇒C¬(A∨B),Γ⇒C L¬∨goes to¬(A∨B)¬(A∨B)¬A¬BD1∗\frac{\mathcal{D}_1} {\frac{\neg A,\neg B,\Gamma\Rightarrow C} {\neg(A\lor B),\Gamma\Rightarrow C}}\ L_{\neg\lor} \qquad\text{goes to}\qquad \frac{\neg(A\lor B)\quad\neg(A\lor B)} {\frac{\neg A\quad\neg B}{\mathcal{D}_1^*}}
D1D2A,Γ⇒C¬A,Γ⇒C∘A,Γ⇒C L∘1goes to[A][¬A]D1∗D2∗∘ACCC PEM∘\frac{\begin{array}{c} D_1 \quad D_2\\ A,\Gamma\Rightarrow C \quad\neg A,\Gamma\Rightarrow C \end{array}}{\circ A,\Gamma\Rightarrow C}\ L_{\circ1} \quad\text{goes to}\quad \frac{\begin{array}{ccc} [A] & [\neg A]\\ D_1^{*} & D_2^{*}\\ \circ A & C \quad C \end{array}}{C}\ PEM^{\circ}

The remaining cases are left to the reader.

From right to left, the proof proceeds by induction on the height nn of deductions in Nf−N_{f-}. If n=0n = 0, then the deduction in Nf−N_{f-} consists of a single node CC. In G1f−G1f-, Γ⇒C\Gamma\Rightarrow C corresponds to an axiom. If n>0n > 0, let D\mathcal{D} be a deduction in Nf−N_{f-} of height nn deriving CC from a set of assumptions Γ\Gamma. As induction hypothesis, assume that the result holds for every deduction in Nf−N_{f-} of height at most n−1;n - 1; that is, for any deduction D′\mathcal{D}' of height at most n−1n - 1 deriving C′C' from a set of assumptions Γ′\Gamma', there exists a derivation D′+\mathcal{D}'^{+} in G1f−G1f- of the sequent Γ′′⇒C′\Gamma'' \Rightarrow C', where Γ′′\Gamma'' is the multiset corresponding to Γ′\Gamma'. We then examine the last inference rule applied in D\mathcal{D} and construct a corresponding derivation in G1f−G1f-. The double line denotes a (possibly empty) sequence of applications of WLWL or CLCL. Moreover, the notation (Γ1,…,Γn)(\Gamma_1,\ldots,\Gamma_n) stands for the multiset that contains exactly one occurrence of each distinct formula appearing in Γ1,…,Γn\Gamma_1,\ldots,\Gamma_n, that is, multiplicities in the original multisets are ignored.

D1D1ABA∧B I∧goes toΓ1⇒AΓ1,Γ2⇒AΓ2⇒BΓ1,Γ2⇒BΓ1,Γ2⇒A∧B(Γ1,Γ2)⇒A∧B R∧\frac{\begin{array}{c} \mathcal{D}_1\quad\mathcal{D}_1\\ A\quad B \end{array}}{A\land B}\ I\land \quad\text{goes to}\quad \frac{\frac{\Gamma_1\Rightarrow A}{\Gamma_1,\Gamma_2\Rightarrow A}\quad \frac{\Gamma_2\Rightarrow B}{\Gamma_1,\Gamma_2\Rightarrow B}} {\frac{\Gamma_1,\Gamma_2\Rightarrow A\land B}{(\Gamma_1,\Gamma_2)\Rightarrow A\land B}}\ R\land
D¬(A∨B)¬A E¬∨goes to¬A⇒¬A¬A,¬B⇒¬A LWΓ⇒¬(A∨B)¬(A∨B)⇒¬A L¬∨Γ⇒¬A Cut\frac{\mathcal{D}}{\frac{\neg(A\lor B)}{\neg A}}\ E_{\neg\lor} \quad\text{goes to}\quad \frac{\frac{\neg A\Rightarrow\neg A}{\neg A,\neg B\Rightarrow\neg A}\ LW\quad \frac{\Gamma\Rightarrow\neg(A\lor B)}{\neg(A\lor B)\Rightarrow\neg A}\ L\neg\lor} {\Gamma\Rightarrow\neg A}\ Cut
\frac{\begin{array}{ccc} \mathcal{D}_1&\mathcal{D}_2&\mathcal{D}_3\\ \circ A&A&\neg A\\ &C \end{array}}{C}\ EXP^{\circ} \quad\text{goes to}\quad \frac{ \frac{\Gamma_1\Rightarrow\circ A}{ \frac{\Gamma_1,\Gamma_2,\Gamma_3\Rightarrow C} {(\Gamma_1,\Gamma_2,\Gamma_3)\Rightarrow C} } \quad \frac{\frac{\Gamma_2\Rightarrow A}{\Gamma_2,\Gamma_3\Rightarrow A} \quad \frac{\Gamma_2\Rightarrow\neg A}{\Gamma_2,\Gamma_3\Rightarrow\neg A}} {\circ A,\Gamma_2,\Gamma_3\Rightarrow C} }

The remaining cases are left to the reader.

The cut-free sequent system Gf−3G^{3}_{f-}

We now introduce Gf−3G^{3}_{f-}, a sequent system for LETF−LET^{-}_{F} consisting solely of logical rules. Its design follows the style of the purely logical systems proposed by Kleene in [19 §80]. The concepts of context, side and principal formulas remains the same, but with the additional detail that the occurrence of the principal formula on the premise(s) of the logical rules is also called a active formula.

Definition 4.1. (The system Gf−3G^{3}_{f-})

Axioms:

Γ,A⇒A‾ Id\overline{\Gamma, A \Rightarrow A}\ Id

Logical rules:

A,B,A∧B,Γ⇒CA∧B,Γ⇒C L∧Γ⇒AΓ⇒BΓ⇒A∧B R∧A,A∨B,Γ⇒CB,A∨B,Γ⇒CA∨B,Γ⇒C L∨Γ⇒AΓ⇒A∨B R∨Γ⇒BΓ⇒A∨B R∨¬A,¬B,¬(A∨B),Γ⇒C¬(A∨B),Γ⇒C L¬∨Γ⇒¬AΓ⇒¬BΓ⇒¬(A∨B) R¬∨¬A,¬(A∧B),Γ⇒C¬B,¬(A∧B),Γ⇒C¬(A∧B),Γ⇒C L¬∧Γ⇒¬AΓ⇒¬(A∧B) R¬∧Γ⇒¬BΓ⇒¬(A∧B) R¬∧A,∘A,Γ⇒C¬A,∘A,Γ⇒C∘A,Γ⇒C L∘1∘A,Γ⇒A∘A,Γ⇒¬A∘A,Γ⇒C L∘2A,¬¬A,Γ⇒C¬¬A,Γ⇒C L¬¬Γ⇒AΓ⇒¬¬A R¬¬\begin{aligned} &\frac{A, B, A \land B, \Gamma\Rightarrow C}{A \land B, \Gamma\Rightarrow C}\ L_{\land} && \frac{\Gamma\Rightarrow A \qquad\Gamma\Rightarrow B}{\Gamma\Rightarrow A \land B}\ R_{\land} \\[1em] &\frac{A, A \lor B, \Gamma\Rightarrow C \qquad B, A \lor B, \Gamma\Rightarrow C}{A \lor B, \Gamma\Rightarrow C}\ L_{\lor} && \frac{\Gamma\Rightarrow A}{\Gamma\Rightarrow A \lor B}\ R_{\lor} \qquad \frac{\Gamma\Rightarrow B}{\Gamma\Rightarrow A \lor B}\ R_{\lor} \\[1em] &\frac{\neg A, \neg B, \neg(A \lor B), \Gamma\Rightarrow C}{\neg(A \lor B), \Gamma\Rightarrow C}\ L_{\neg\lor} && \frac{\Gamma\Rightarrow\neg A \qquad\Gamma\Rightarrow\neg B}{\Gamma\Rightarrow\neg(A \lor B)}\ R_{\neg\lor} \\[1em] &\frac{\neg A, \neg(A \land B), \Gamma\Rightarrow C \qquad\neg B, \neg(A \land B), \Gamma\Rightarrow C}{\neg(A \land B), \Gamma\Rightarrow C}\ L_{\neg\land} && \frac{\Gamma\Rightarrow\neg A}{\Gamma\Rightarrow\neg(A \land B)}\ R_{\neg\land} \qquad \frac{\Gamma\Rightarrow\neg B}{\Gamma\Rightarrow\neg(A \land B)}\ R_{\neg\land} \\[1em] &\frac{A, \circ A, \Gamma\Rightarrow C \qquad\neg A, \circ A, \Gamma\Rightarrow C}{\circ A, \Gamma\Rightarrow C}\ L_{\circ1} && \frac{\circ A, \Gamma\Rightarrow A \qquad\circ A, \Gamma\Rightarrow\neg A}{\circ A, \Gamma\Rightarrow C}\ L_{\circ2} \\[1em] &\frac{A, \neg\neg A, \Gamma\Rightarrow C}{\neg\neg A, \Gamma\Rightarrow C}\ L_{\neg\neg} && \frac{\Gamma\Rightarrow A}{\Gamma\Rightarrow\neg\neg A}\ R_{\neg\neg} \end{aligned}

The differences between G3f−G3_{f-} and G1f−G1_{f-} are the following: (i) the presence of multisets of formulas in the axiom rule; (ii) the repetition of the principal formulas of the rules in their premises (usually referred to as contraction-absorbing rules, or rules obtained by Kleene’s trick – see Remark 4.2 below); (iii) the absence of explicit structural rules. (i) and (ii) are motivated by the need to establish the admissibility of structural rules, which we will do below. These proofs will make precise the specific role played by each of these modifications.

Remark 4.2. (Kleene’s trick)

The so called Kleene’s trick is a reformulation of the logical rules of a sequent calculus, introduced by Kleene in [19 §80], whose main aim is to simplify decidability proofs through the absorption of contraction into the logical rules.

Let us compare the two systems by showing how an application of a rule in the contraction-absorbing G3f−G3_{f-} system is represented in G1f−G1_{f-} where contraction is an explicit rule. Consider the left conjunction rule of G3f−G3_{f-}.

(A∧B),A,B,Γ⇒C(A∧B),Γ⇒CL∧\frac{(A \land B), A, B, \Gamma\Rightarrow C}{(A \land B), \Gamma\Rightarrow C}\quad L\land

It is easy to see that this rule is really composed of two steps: the introduction of a conjunction followed by contraction. In G1f−G1_{f-}, an application of this rule can be represented as follows:

(A∧B),A,B,Γ⇒C(A∧B),(A∧B),Γ⇒CL∧(A∧B),Γ⇒CLC\frac{\frac{(A \land B), A, B, \Gamma\Rightarrow C}{(A \land B), (A \land B), \Gamma\Rightarrow C}\quad L\land}{(A \land B), \Gamma\Rightarrow C}\quad LC

Admissibility of structural rules in G3f−G3_{f-}

We now show that the structural rules are admissible in G3f−G3_{f-}. In the following we will write ⊢nS\vdash_n S (where SS is a sequent) to mean that SS has a derivation of height at most nn. When there is no risk of ambiguity, we omit the subscript and write ⊢S\vdash S to denote the derivability of SS.

Theorem 4.3. (Height-preserving weakening) If ⊢nΓ⇒C\vdash_n \Gamma\Rightarrow C and Γ⊆Γ′\Gamma\subseteq\Gamma', then ⊢nΓ′⇒C\vdash_n \Gamma' \Rightarrow C.

Proof. The proof is by induction on the height nn of the given derivation.

If n=0n = 0, then Γ⇒C\Gamma\Rightarrow C is an axiom. Hence, for any Γ′\Gamma' with Γ⊆Γ′\Gamma\subseteq\Gamma', the sequent Γ′⇒C\Gamma' \Rightarrow C is also an axiom, since adding formulas to the antecedent yields another axiom.

For n>0n > 0, we consider the last inference in the derivation of Γ⇒C\Gamma\Rightarrow C.

Suppose that Γ⇒C:=¬(A∧B),Σ⇒C\Gamma\Rightarrow C := \neg(A \wedge B), \Sigma\Rightarrow C, i.e. Γ⇒C\Gamma\Rightarrow C is obtained by an application of L¬∧L\neg\wedge. Then the premises of the last inference are ¬A,¬(A∧B),Σ⇒C\neg A, \neg(A \wedge B), \Sigma\Rightarrow C and ¬B,¬(A∧B),Σ⇒C\neg B, \neg(A \wedge B), \Sigma\Rightarrow C, each one having a derivation of height strictly less than nn. By the induction hypothesis, for any Σ′\Sigma' such that Σ⊆Σ′\Sigma\subseteq\Sigma', we obtain derivations of ¬A,¬(A∧B),Σ′⇒C\neg A, \neg(A \wedge B), \Sigma' \Rightarrow C and ¬B,¬(A∧B),Σ′⇒C\neg B, \neg(A \wedge B), \Sigma' \Rightarrow C of height strictly less than nn. Applying L¬∧L\neg\wedge to these sequents, we derive ¬(A∧B),Σ′⇒C\neg(A \wedge B), \Sigma' \Rightarrow C, that is, Γ′⇒C\Gamma' \Rightarrow C, with a derivation of height at most nn.

The other cases are left to the reader. □

Theorem 4.4. (Height-preserving contraction) If ⊢nA,A,Γ⇒C\vdash_n A, A, \Gamma\Rightarrow C, then ⊢nA,Γ⇒C\vdash_n A, \Gamma\Rightarrow C.

Proof. The proof is by induction on the height nn of the derivation.

If n=0n = 0, then A,A,Γ⇒CA, A, \Gamma\Rightarrow C is an axiom, and hence A,Γ⇒CA, \Gamma\Rightarrow C is also an axiom.

For n>0n > 0, we consider the last inference in the derivation of A,A,Γ⇒CA, A, \Gamma\Rightarrow C.

(i) If the contracted formula AA is not principal in the last inference, then the premises of that inference have derivations of height strictly less than nn. By the induction hypothesis, contraction is admissible in those premises, and reapplying the same inference yields a derivation of A,Γ⇒CA, \Gamma\Rightarrow C of height at most nn.

(ii) Now suppose the contracted formula AA is principal in the last inference.

:::

Suppose A=¬(D∨E)A = \neg(D \mathbin{\vee} E). In this case, the last rule is L¬∨L\neg\vee and the conclusion is ¬(D∨E),¬(D∨E),Γ⇒C\neg(D\mathbin{\vee}E),\neg(D\mathbin{\vee}E),\Gamma\Rightarrow C. The premise of this inference is ¬D,¬E,¬(D∨E),¬(D∨E),Γ⇒C\neg D,\neg E,\neg(D\mathbin{\vee}E),\neg(D\mathbin{\vee}E),\Gamma\Rightarrow C, which has a derivation of height strictly less than nn. By the induction hypothesis, we obtain a derivation of ¬D,¬E,¬(D∨E),Γ⇒C\neg D,\neg E,\neg(D\mathbin{\vee}E),\Gamma\Rightarrow C of height strictly less than nn. Applying L¬∨L\neg\vee, we derive ¬(D∨E),Γ⇒C\neg(D\mathbin{\vee}E),\Gamma\Rightarrow C, that is, A,Γ⇒CA,\Gamma\Rightarrow C, with a derivation of height at most nn.

Suppose A=∘BA = \circ B and the last rule is L∘2L_{\circ2}. In this case, the conclusion is ∘B,∘B,Γ⇒C\circ B,\circ B,\Gamma\Rightarrow C, and the premises are ∘B,∘B,Γ⇒B\circ B,\circ B,\Gamma\Rightarrow B and ∘B,∘B,Γ⇒¬B\circ B,\circ B,\Gamma\Rightarrow\neg B, both with derivations of height strictly less than nn. By the induction hypothesis, we obtain derivations of both premises with height strictly less than nn. Applying L∘2L_{\circ2}, we obtain ∘B,Γ⇒C\circ B,\Gamma\Rightarrow C, that is, A,Γ⇒CA,\Gamma\Rightarrow C, with a derivation of height at most nn.

The remaining cases are left to the reader. □

We now prove the admissibility of (multiplicative) Cut for G3f−G3f^{-} following the format established by [15]. The proof proceeds by a principal induction on the weight of the cut formula, together with a secondary induction on the height of the cut, i.e. the sum of the heights of the premises in the corresponding application of the rule.

Theorem 4.5. (The Cut rule is admissible in G3f−G3f^{-})

If ⊢Γ⇒D\vdash\Gamma\Rightarrow D and ⊢D,Γ′⇒C\vdash D,\Gamma' \Rightarrow C, then so is ⊢Γ,Γ′⇒C\vdash\Gamma,\Gamma' \Rightarrow C.

Proof.

We need to consider three cases:

  1. At least one of the premises of Cut is an axiom;

  2. The cut formula is principal in both premises;

  3. The cut formula is not principal in at least one of the premises.

Case 1: At least one of the premises is an axiom.

An application of Cut can be eliminated directly in one of two ways, depending on whether the cut formula is a principal formula or a context formula in the axiom rule.

(i) If the cut formula is principal in the axiom rule, then the two premises of the Cut are Γ,D⇒D\Gamma,D \Rightarrow D and D,Γ′⇒CD,\Gamma' \Rightarrow C, concluding Γ,Γ′,D⇒C\Gamma,\Gamma',D \Rightarrow C, which can be alternatively derived by zero or more applications of LWLW to the latter premise, deleting the application of CutCut and the former premise.

(ii) If the cut formula is not principal in the axiom rule, then it is part of the context, and the two premises of the CutCut are Γ⇒D\Gamma\Rightarrow D and D,Γ′,A⇒AD,\Gamma',A \Rightarrow A, concluding Γ,Γ′,A⇒A\Gamma,\Gamma',A \Rightarrow A, which is obviously also an axiom sequent, which can be derived without cut.

Case 2: The cut formula is principal in both premises. We proceed by replacing the original CutCut with one of less height and one or two of less weight. In what follows, the double line indicates one or more applications of LCLC.

(i) The cut-formula D=¬(A∨B)D = \neg(A \lor B).

Γ⇒¬AΓ⇒¬BΓ⇒¬(A∨B)R¬∨¬A,¬B,¬(A∨B),Γ′⇒C¬(A∨B),Γ′⇒CL¬∨Γ,Γ′⇒CCut\frac{ \frac{\Gamma\Rightarrow\neg A \qquad\Gamma\Rightarrow\neg B}{\Gamma\Rightarrow\neg(A \lor B)}R\neg\lor\qquad\frac{\neg A,\neg B,\neg(A \lor B),\Gamma' \Rightarrow C}{\neg(A \lor B),\Gamma' \Rightarrow C}L\neg\lor}{\Gamma,\Gamma' \Rightarrow C}Cut

is replaced with

Γ⇒¬AΓ⇒¬BΓ⇒¬(A∨B)R¬∨¬A,¬B,¬(A∨B),Γ′⇒C¬A,¬B,Γ,Γ′⇒CCutΓ⇒¬A¬A,¬B,Γ,Γ′⇒CCutΓ⇒¬B¬B,Γ,Γ,Γ′⇒CCutΓ,Γ,Γ,Γ′⇒CLC\frac{ \frac{ \frac{\Gamma\Rightarrow\neg A \qquad\Gamma\Rightarrow\neg B}{\Gamma\Rightarrow\neg(A \lor B)}R\neg\lor\qquad\neg A,\neg B,\neg(A \lor B),\Gamma' \Rightarrow C}{\neg A,\neg B,\Gamma,\Gamma' \Rightarrow C}Cut \qquad\frac{\Gamma\Rightarrow\neg A}{\neg A,\neg B,\Gamma,\Gamma' \Rightarrow C}Cut}{ \frac{\Gamma\Rightarrow\neg B}{\neg B,\Gamma,\Gamma,\Gamma' \Rightarrow C}Cut}{\Gamma,\Gamma,\Gamma,\Gamma' \Rightarrow C}LC

(ii) The cut formula D=A∨BD = A \lor B.

Γ⇒AΓ⇒A∨BR∨A,A∨B,Γ′⇒CB,A∨B,Γ′⇒CA∨B,Γ′⇒CL∨Γ,Γ′⇒CCut\frac{ \frac{\Gamma\Rightarrow A}{\Gamma\Rightarrow A \lor B}R\lor\qquad\frac{A,A \lor B,\Gamma' \Rightarrow C \qquad B,A \lor B,\Gamma' \Rightarrow C}{A \lor B,\Gamma' \Rightarrow C}L\lor}{\Gamma,\Gamma' \Rightarrow C}Cut

is replaced with

Γ⇒AΓ⇒A∨BR∨A,A∨B,Γ′⇒CA,Γ,Γ′⇒CCutΓ,Γ,Γ′⇒CCutΓ,Γ′⇒CLC\frac{ \frac{ \frac{\Gamma\Rightarrow A}{\Gamma\Rightarrow A \lor B}R\lor\qquad A,A \lor B,\Gamma' \Rightarrow C}{A,\Gamma,\Gamma' \Rightarrow C}Cut}{\Gamma,\Gamma,\Gamma' \Rightarrow C}Cut{\Gamma,\Gamma' \Rightarrow C}LC

The remaining cases are left to the reader.

  1. The cut formula is not principal in at least one of the premises. In this case, we proceed by reducing the height of the cut, except when the left premise has been obtained by the rule L∘2L_{\circ2}.

(i) The last rule of the right premise is L∘1L_{\circ1}.

Γ⇒DA,∘A,D,Γ′⇒C¬A,∘A,D,Γ′⇒C∘A,D,Γ′⇒C L∘1∘A,Γ,Γ′⇒C Cut\frac{\Gamma\Rightarrow D \qquad\frac{A,\circ A,D,\Gamma' \Rightarrow C \qquad\neg A,\circ A,D,\Gamma' \Rightarrow C}{\circ A,D,\Gamma' \Rightarrow C}\ L_{\circ1}}{\circ A,\Gamma,\Gamma' \Rightarrow C}\ Cut

is replaced with

Γ⇒DA,∘A,D,Γ′⇒CA,∘A,Γ,Γ′⇒C CutΓ⇒D¬A,∘A,D,Γ′⇒C¬A,∘A,Γ,Γ′⇒C Cut∘A,Γ,Γ′⇒C L∘1\frac{\frac{\Gamma\Rightarrow D \qquad A,\circ A,D,\Gamma' \Rightarrow C}{A,\circ A,\Gamma,\Gamma' \Rightarrow C}\ Cut \qquad\frac{\Gamma\Rightarrow D \qquad\neg A,\circ A,D,\Gamma' \Rightarrow C}{\neg A,\circ A,\Gamma,\Gamma' \Rightarrow C}\ Cut}{\circ A,\Gamma,\Gamma' \Rightarrow C}\ L_{\circ1}

(ii) The last rule of the left premise is L¬∨L_{\neg\vee}.

¬A,¬B,¬(A∨B),Γ⇒D¬(A∨B),Γ⇒D L¬∨D,Γ′⇒C¬(A∨B),Γ,Γ′⇒C Cut\frac{\frac{\neg A,\neg B,\neg(A\vee B),\Gamma\Rightarrow D}{\neg(A\vee B),\Gamma\Rightarrow D}\ L_{\neg\vee}\qquad D,\Gamma' \Rightarrow C}{\neg(A\vee B),\Gamma,\Gamma' \Rightarrow C}\ Cut

is replaced with

¬A,¬B,¬(A∨B),Γ⇒DD,Γ′⇒C¬A,¬B,¬(A∨B),Γ,Γ′⇒C¬(A∨B),Γ,Γ′⇒C L¬∨ Cut\frac{\neg A,\neg B,\neg(A\vee B),\Gamma\Rightarrow D \qquad D,\Gamma' \Rightarrow C}{\frac{\neg A,\neg B,\neg(A\vee B),\Gamma,\Gamma' \Rightarrow C}{\neg(A\vee B),\Gamma,\Gamma' \Rightarrow C}\ L_{\neg\vee}}\ Cut

(iii) The left premise has been obtained by L∘2L_{\circ2}.

∘A,Γ⇒A∘A,Γ⇒¬A∘A,Γ⇒D L∘2D,Γ′⇒C∘A,Γ,Γ′⇒C Cut\frac{\frac{\circ A,\Gamma\Rightarrow A \qquad\circ A,\Gamma\Rightarrow\neg A}{\circ A,\Gamma\Rightarrow D}\ L_{\circ2}\qquad D,\Gamma' \Rightarrow C}{\circ A,\Gamma,\Gamma' \Rightarrow C}\ Cut

is replaced with

∘A,Γ⇒A∘A,Γ⇒¬A∘A,Γ⇒C L∘2∘A,Γ,Γ′⇒C LW\frac{\frac{\circ A,\Gamma\Rightarrow A \qquad\circ A,\Gamma\Rightarrow\neg A}{\circ A,\Gamma\Rightarrow C}\ L_{\circ2}}{\circ A,\Gamma,\Gamma' \Rightarrow C}\ LW

The remaining cases are left to the reader.

Proposition 4.6. (Generalized subformula property) Let DD be a cut-free derivation of Γ⇒C\Gamma\Rightarrow C in G3f−G3f^{-}. Then, all formulas appearing in DD will be generalized subformulas of Γ\Gamma and CC

Proof. The claim is easily established by a simple inspection of the rules given of G3f−G3f^{-}.

Remark 4.7. Schellinx [28] explored (mainly in the context of linear logic) how the use of structural rules affects the reduction steps in a cut-elimination proof, as well as how the reduction steps can give information about the derivation itself. When contraction or weakening are used to derive a cut-formula, a corresponding operation at the level of (sub)derivations occurs during the reduction steps: either a (sub)derivation is deleted or it is duplicated. This allows for an interesting observation of how structural rules, even when “absorbed” by logical rules and made implicit, still produce similar effects of duplication, in the case of contraction, and deletion, in the case of weakening. In the proof above, this behavior is visible in Case 2, since contraction is “built into” the logical rules (see Remark 4.2), and in sub-case (iii) of Case 3, where weakening is implicit in the L∘2L_{\circ2} rule.

Remark 4.8. (On the path to G3f−G3f^{-}) In order to obtain a fully logical sequent calculus for LETF−LET_{F}^{-}, we must establish the admissibility of the structural rules. Weakening is straightforward: its admissibility could be achieved for our systems just by adding an axiom rule with contexts. Contraction, however, is not.

Our first attempt consisted in dropping contraction, cut, and weakening from G1f−G1f^{-}, adding the new axiom rule with contexts, and then trying to prove the height-preserving admissibility of contraction. This was a natural move, since the logical rules of G1f−G1f^{-} already resemble those of standard G3G3 systems for intuitionistic logic, where the result follows by a simple induction on derivation height. Unfortunately, this did not work, since the proof requires a height-preserving inversion lemma for the left rules. Intuitively, the demonstration proceeds by showing that contraction can be “pushed up”

the derivation by applying contraction to the subformulas of the contracted formula until it is eliminated. This can be achieved with the help of the height-preserving inversion lemma, which cannot be established for the ∘\circ-rules. Therefore, in order to make progress, we had to modify our calculus.

This led us to an intermediate system, all its logical rules coincided with those of our slightly modified and structural rule-free G1f−G1f_{-}, except for the ∘\circ-rules, which we reformulated as in G3f−G3f_{-}.2 Even so, the proof did not go through: it failed because we cannot restrict the axiom rule to literal principal formulas (as explained in Section 3), which blocks the proof of the height-preserving invertibility lemma, even for the non-∘\circ rules.

It was this failed attempt with the intermediate system that led us to apply Kleene’s trick to all logical rules of G1f−G1f_{-} to obtain G3f−G3f_{-}. This, in turn, enabled us to prove the admissibility of height-preserving LCLC without appealing to any invertibility lemma.

Soundness and completeness

We first establish the equivalence between G1f−G1f_{-} and G3f−G3f_{-}.

Theorem 4.9.

G1f−⊢Γ⇒C if and only if G3f−⊢Γ⇒CG1f_{-} \vdash\Gamma\Rightarrow C \text{ if and only if } G3f_{-} \vdash\Gamma\Rightarrow C

Proof. From left to right, all left structural rules, together with cut, were shown to be admissible in G3f−G3f_{-} in theorems 4.3, 4.4, and 4.5. All left logical rules of G1f−G1f_{-} can also be shown admissible in G3f−G3f_{-} through the help of Theorem 4.3. From right to left, all rules of G3f−G3f_{-} can also be shown admissible in G1f−G1f_{-}. The axiom rule follows from 0 or more uses of LWLW, and the other logical rules follow from a simple application of LCLC.

Now, soundness and completeness of G3f−G3f_{-} follow straightforwardly from the above result.

Theorem 4.10. G3f−G3_{f}^{-} is sound and complete with respect to the bivalued semantics of LETF−\mathrm{LET}_{F}^{-}:

Γ⊢G3f−A if and only if Γ⊨LETF−A\Gamma\vdash_{G3_{f}^{-}} A \text{ if and only if } \Gamma\models_{\mathrm{LET}_{F}^{-}} A

Proof. The result follows from Theorem 4.9 above, together with Theorems 3.3 and 3.11.

A decision method for LETF−\mathrm{LET}_{F}^{-}

Recall that the design of our rules is inspired by Kleene’s G3G3 systems. He introduced these systems primarily to obtain decidability results via a bottom-up proof-search procedure, precisely to control difficulties arising from contraction. In what follows, we follow the same lines as Kleene’s approach in [19 §80] to prove the decidability of G3f−G3_{f}^{-}.

Definition 4.11. (Cognate sequents)

(i) Two sequents Γ⇒A\Gamma\Rightarrow A and Γ′⇒A′\Gamma' \Rightarrow A' are said to be cognate if Γ\Gamma and Γ′\Gamma' contain the same formulas, possibly differing in multiplicity, that is, in the number of occurrences of each formula, and A=A′A = A'.

(ii) An irredundant proof in G1f−G1_{f}^{-} is a proof in which no pair of cognate sequents occurs one above the other along the same derivation branch.

Proposition 4.12. (Irredundant derivations)

Every cut-free derivation D\mathcal{D} of Γ⇒C\Gamma\Rightarrow C in G3f−G3_{f}^{-} can be transformed into an irredundant cut-free derivation D∗\mathcal{D}^{*} of the same sequent.

Proof.

If no branch of D\mathcal{D} contains a pair of cognate sequents such that one occurs above the other (possibly with intervening sequents), then D\mathcal{D} is already irredundant.

Otherwise, fix a branch and choose a pair of cognate sequents S1S_{1} and S2S_{2} on that branch such that S1S_{1} occurs above S2S_{2} and there is no cognate sequent strictly between them on that branch. Write S1S_{1} as Σ⇒A\Sigma\Rightarrow A and S2S_{2} as Σ′⇒A\Sigma' \Rightarrow A, where Σ\Sigma and Σ′\Sigma' contain the same formulas, possibly with different multiplicities.

Delete the subderivation leading from S1S_1 to S2S_2 (S2S_2 included) together with all branches contributing to it. Next, apply Theorem 4.4 to S1S_1 (possibly zero times), rendering it equal to S2S_2. The resulting derivation is still cut-free, derives Γ⇒C\Gamma\Rightarrow C, and strictly decreases the number of occurrences, along the branches of D\mathcal{D}, of pairs of cognate sequents with one occurring above the other.

By iterating this transformation, and since the number of occurrences of cognate sequents is finite, the process must terminate, yielding a cut-free, irredundant derivation of Γ⇒C\Gamma\Rightarrow C. □

The proof that G3f−G3_f^- provides a decision method to LETF−LET_F^- will be given after the following example illustrating the decision procedure.

Example 4.13.

(i) The sequent ¬p,p∨q⇒q\neg p, p \lor q \Rightarrow q (disjunctive syllogism) is not derivable in G3f−G3_f^-.

¬p,p,p,p∨q⇒q¬p,p,q,p∨q⇒q¬p,p,p∨q⇒q L∨¬p,q,p∨q⇒q¬p,p∨q⇒q L∨\frac{ \frac{\neg p,p,p,p\lor q\Rightarrow q \qquad\neg p,p,q,p\lor q\Rightarrow q}{\neg p,p,p\lor q\Rightarrow q}\ L\lor \qquad \neg p,q,p\lor q\Rightarrow q }{ \neg p,p\lor q\Rightarrow q }\ L\lor

Observe that further bottom-up applications of L∨L\lor will keep producing axioms on the right premise and cognate sequents on the left premise. The example above shows that disjunctive syllogism is not derivable, as expected, since in the context of LETLETs it is equivalent to explosion. Below, we show how its derivability can be recovered by means of the classicality connective.

(ii) The sequent ∘p,¬p,p∨q⇒q\circ p,\neg p,p\lor q\Rightarrow q is derivable in G3f−G3_f^-.

∘p,¬p,p,p∨q⇒p∘p,¬p,p,p∨q⇒¬p∘p,¬p,p,p∨q⇒q L∘2∘p,¬p,q,p∨q⇒q∘p,¬p,p∨q⇒q L∨\frac{ \frac{\circ p,\neg p,p,p\lor q\Rightarrow p \qquad\circ p,\neg p,p,p\lor q\Rightarrow\neg p}{\circ p,\neg p,p,p\lor q\Rightarrow q}\ L\circ_2 \qquad \circ p,\neg p,q,p\lor q\Rightarrow q }{ \circ p,\neg p,p\lor q\Rightarrow q }\ L\lor

A bottom-up application of the rule L∨L\lor yields an axiom as the right premise and a sequent as the left premise that is clearly derivable, since it is an instance of Γ,∘A,A,¬A⇒B\Gamma,\circ A,A,\neg A\Rightarrow B. The latter is derivable in G3f−G3_f^- and recovers the principle of explosion. By a further bottom-up application of L∘2L\circ_2, we obtain two axioms and close the proof.

(iii) The sequent ⇒∘p∨¬∘p\Rightarrow\circ p \lor\neg\circ p is not derivable in G3f−G3f^{-}.

⇒∘p⇒∘p∨¬∘p R∨⇒¬∘p⇒∘p∨¬∘p R∨\frac{\Rightarrow\circ p}{\Rightarrow\circ p \lor\neg\circ p}\ R\lor \qquad \frac{\Rightarrow\neg\circ p}{\Rightarrow\circ p \lor\neg\circ p}\ R\lor

It is clear from the constructions above that all possibilities for finding a proof have been considered. No further inference can be made from the premises resulting from bottom-up applications of R∨R\lor.

(iv) The sequent ∘p⇒p\circ p \Rightarrow p is not derivable in G3f−G3f^{-}.

Consider the constructions below:

∘p⇒p∘p⇒¬p∘p⇒p L∘2∘p,p⇒p∘p,¬p,p⇒p∘p,¬p,¬p⇒p∘p,¬p⇒p L∘1∘p⇒p L∘1\frac{\circ p \Rightarrow p \qquad\circ p \Rightarrow\neg p}{\circ p \Rightarrow p}\ L\circ_{2} \qquad\qquad \frac{\circ p,p \Rightarrow p \qquad\frac{\circ p,\neg p,p \Rightarrow p \qquad\circ p,\neg p,\neg p \Rightarrow p}{\circ p,\neg p \Rightarrow p}\ L\circ_{1}}{\circ p \Rightarrow p}\ L\circ_{1}

The construction on the left shows that a bottom-up application of L∘2L\circ_{2} yields a cognate sequent as the left premise, thereby stopping the search in that branch. Note that any application of L∘2L\circ_{2} to a sequent of the form Γ,∘A⇒A\Gamma,\circ A \Rightarrow A or Γ,∘A⇒¬A\Gamma,\circ A \Rightarrow\neg A yields a cognate sequent as the left or right premise. Thus, the only remaining possibility is to apply L∘1L\circ_{1}. However, two successive bottom-up applications of L∘1L\circ_{1} also yield cognate sequents, as the construction on the right shows.

We leave as an exercise to the reader to show that the sequents p∧¬p⇒qp \land\neg p \Rightarrow q and ⇒∘p∧p∧¬p\Rightarrow\circ p \land p \land\neg p are not derivable in G3f−G3f^{-}. The non-derivability of the latter sequent shows that G3f−G3f^{-} is syntactically consistent. Indeed, in LETF−\mathrm{LET}_{F}^{-} a bottom particle can be defined by ⊥=def∘A∧A∧¬A\bot\mathrel{\mathop{=}\limits^{\mathrm{def}}} \circ A \land A \land\neg A, for any AA. Hence, if ⇒⊥\Rightarrow\bot were derivable, then so would be ⇒∘p∧p∧¬p\Rightarrow\circ p \land p \land\neg p, which is impossible. Therefore, ⇒⊥\Rightarrow\bot is not derivable.

The reader should have noticed how the proof method proceeds. If the sequent is derivable, a choice of bottom-up rule applications that avoids producing cognate sequents will invariably end with axioms on every branch. If the sequent is not derivable, the proof search will eventually produce a cognate sequent, at which point the search stops. All possible bottom-up rule applications must be examined to confirm that no derivation can be completed.

Theorem 4.14. The question of determining whether or not a sequent Γ⇒C\Gamma\Rightarrow C is derivable in G3f−G3_{f-} is decidable.

Proof. Our strategy will be to show that we can generate all possible cut-free irredundant derivations of Γ⇒C\Gamma\Rightarrow C by constructing those derivations root first, choosing step by step a principal formula of the bottom-most sequent to analyze into its possible premises.

By Proposition 4.6 (generalized subformula property) and Theorem 4.5 (admissibility of cut), any derivation of Γ⇒C\Gamma\Rightarrow C can be assumed to be cut-free and to contain only generalized subformulas of Γ\Gamma and CC.

Proposition 4.12 allows us to restrict the search to irredundant derivations; that is, we may stop extending a branch whenever a pair of subsequent cognate sequent appears.

Since the set of generalized subformulas of Γ\Gamma and CC is finite and we may restrict to irredundant derivations (which avoid cognate sequents), only finitely many distinct sequents can appear in such a derivation.

Moreover, each inference rule has a fixed number of premises, so there are only finitely many ways to apply a rule to a given sequent.

Consequently, the bottom-up proof search tree is finite: every branch terminates either with an axiom or with a sequent to which no further rule can be applied without introducing a cognate sequent.

Thus, the number of possible irredundant, cut-free derivations built from generalized subformulas is finite. If among these we find a derivation whose leaves are all axioms, then Γ⇒C\Gamma\Rightarrow C is derivable; otherwise, it is not.

What's next

As future work, we plan to extend this proof-theoretic investigation to other logics in the LETsLET_s family, by developing G3G3-style sequent calculi together with bottom-up decision procedures for other sentential systems, in particular LETJLET_J and the six-valued logics LETF+LET^{+}_{F} and LETK+LET^{+}_{K} [10]. In a second stage, we also intend to investigate the proof theory of their corresponding first-order extensions.

References

  1. [1]A. Almukdad and D. Nelson. Constructible falsity and inexact predicates. The Journal of Symbolic Logic, 49(1):231–233, 1984.DOI
  2. [2]H. Antunes, W. Carnielli, A. Kapsner, and A. Rodrigues. Kripke-style models for logics of evidence and truth. Axioms, 9(3), 2020. URL https://www.mdpi.com/2075-1680/9/3/100.DOI
  3. [3]H. Antunes, A. Rodrigues, M.E. Coniglio, and W. Carnielli. Valuation semantics for first-order logics of evidence and truth. Journal of Philosophical Logic, 51(5):1141–1173, 2022.arxiv.org/abs/2106.09850
  4. [4]N.D. Belnap. How a computer should think. In H. Omori and H. Wansing, editors, New Essays on Belnap-Dunn Logic. Springer (2019), 1977.
  5. [5]W. Carnielli and M.E. Coniglio. Paraconsistent Logic: Consistency, Contradiction and Negation, volume 40 of Logic, Epistemology, and the Unity of Science series. Springer, 2016.
  6. [6]W. Carnielli and J. Marcos. A taxonomy of C-systems. In W. Carnielli, M. E. Coniglio, and I. M. L. D’Ottaviano, editors, Paraconsistency: The Logical Way to the Inconsistent. Marcel Dekker, New York, 2002.
  7. [7]W. Carnielli and A. Rodrigues. On the philosophy and mathematics of the logics of formal inconsistency. In J.-Y. Béziau, M. Chakraborty, and S. Dutta, editors, New Directions in Paraconsistent Logic, pages 57–88. Springer India, 2015.DOI
  8. [8]W. Carnielli and A. Rodrigues. An epistemic approach to paraconsistency: a logic of evidence and truth. Synthese, 196:3789–3813, 2017. URL https://rdcu.be/ctJRQ.DOI
  9. [9]W. Carnielli, M.E. Coniglio, and J. Marcos. Logics of formal inconsistency. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, volume 14, pages 1–93. Springer-Verlag, 2007.
  10. [10]M. E. Coniglio and A. Rodrigues. From belnap-dunn four-valued logic to six-valued logics of evidence and truth. Studia Logica, 112:561–606, 2024.
  11. [11]M. E. Coniglio, M. Figallo, and A. Rodrigues. Normalization and cut-elimination theorems for some logics of evidence and truth. Journal of Logic and Computation, 35, 4 2025.arxiv.org/abs/2405.20932
  12. [12]N. da Costa. Sistemas Formais Inconsistentes (Inconsistent Formal Systems, in Portuguese). Habilitation thesis, Universidade do Paraná, Curitiba, 1963. Republished by Editora UFPR, Brazil, 1963.
  13. [13]N. da Costa. Logics that are both paraconsistent and paracomplete. Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni, 83:29–32, 1989.
  14. [14]N. da Costa and D. Marconi. A note on paracomplete logic. Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni, 80:504–509, 1986.
  15. [15]A. G. Dragalin. Mathematical intuitionism: introduction to proof theory. American Mathematical Society, 1988.DOI
  16. [16]J.M. Dunn. Intuitive semantics for first-degree entailments and ‘coupled trees’. Philosophical Studies, 29:149–168, 1976. Reprinted in New Essays on Belnap-Dunn Logic,Springer,2019. Eds. Omori, H. and Wansing, H.DOI
  17. [17]J.M. Dunn. Information in computer science. In P. Adriaans and J. van Benthem, editors, Philosophy of Information. Volume 8 of Handbook of the Philosophy of Science, pages 581–608. Elsevier, 2008.DOI
  18. [18]J. Fetzer. Information: Does it have to be true? Minds and Machines, 14:223–229, 2004.DOI
  19. [19]S. C. Kleene. Introduction to Metamathematics. North-Holland, Amsterdam, 1952.
  20. [20]J. Marcos. Logics of Formal Inconsistency. PhD thesis, University of Campinas, 2005.
  21. [21]J. Marcos. Nearly every normal modal logic is parnormal. Logique et Analyse, 48:279–300, 2005.
  22. [22]C. Mortari, A. Rodrigues, G. Secco, E. Pimentel, and I. Dottaviano, editors. Andrea Loparic on Semantics for Non-Classical Logics. Coleção CLE Unicamp, Campinas, 2025.
  23. [23]S. Negri and J. von Plato. Structural Proof Theory. Cambridge University Press, 6 2001.
  24. [24]D. Nelson. Constructible falsity. The Journal of Symbolic Logic, 14, 1949.DOI
  25. [25]A. Rodrigues and H. Antunes. First-order logics of evidence and truth with constant and variable domains. Logica Universalis, 16:419–449, 2022.DOI
  26. [26]A. Rodrigues and W. Carnielli. On Barrio, Lo Guercio, and Szmuc on logics of evidence and truth. Logic and Logical Philosophy, 31:313–338, 2022.DOI
  27. [27]A. Rodrigues, J. Bueno-Soler, and W. Carnielli. Measuring evidence: a probabilistic approach to an extension of Belnap-Dunn Logic. Synthese, 198:5451–5480, 2020.DOI
  28. [28]H. Schellinx. The Noble Art of Linear Decorating. Doctoral thesis, University of Amsterdam, 1994. URL https://eprints.illc.uva.nl/id/eprint/1964/.
  29. [29]A. S. Troelstra and H. Schwichtenberg. Basic Proof Theory. Cambridge University Press, 2nd edition, 7 2000.
  30. [30]H. Wansing. The Logic of Information Structures. Springer, 1993.DOI

Paper details

vlnc:W_nypkpjwx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents