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 (s) form a family of paraconsistent and paracomplete logics. They extend the logic of first-degree entailment (), also known as Belnap–Dunn four-valued logic (e.g. [4, 16]), with a unary operator designed to recover classical negation to formulas within its scope. The sentential logic is a minimal , obtained by adding and its inference rules to .
This paper investigates the proof theory of . More precisely, our aim is to present a sequent calculus for with purely logical rules, and to use it to obtain a simple bottom-up decision procedure. We do so by first introducing the system , 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 . The system is then modified into a system that we call , a -style system inspired by Kleene [19 §80, pp. 479ff.]. is obtained from 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 s, 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 , called , together with a sound and complete bivalued semantics. is the sentential fragment of a first-order version of , investigated in [25]. In § 3 we also introduce the sequent system , and show, based on results from [11], that the cut rule can be eliminated from deductions in . In § 4 we introduce the cut-free system , 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 by means of a bottom-up decision method for . 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 () and logics of formal undeterminedness (). Logics of evidence and truth are simultaneously s and s.
Let be a Tarskian, compact, and structural logic equipped with a negation , a standard disjunction , and a unary connective . Consider the following conditions:
(i) for some and ;
(ii) and for some and ;
(iii) for every and .
(iv) for some ;
(v) and for some ;
(vi) for every .
is a logic of formal inconsistency () if conditions (i)–(iii) hold, and a logic of formal undeterminedness () 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, is a logic of formal inconsistency and undeterminedness, i.e. an .
The terminology and was introduced by Carnielli [6] and Marcos [21]. The underlying ideas, however, can be traced back to da Costa’s earlier work: further develop the 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]. and 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 called was modified so as to be faithful to the intended interpretation in terms of conclusive and non-conclusive evidence. s, as well as and , 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 -style operator.
Let us now provide a more precise characterization of logics of evidence and truth. They are s that have 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, expresses that whatever evidence is available for , whether positive or negative, is taken to be conclusive; when does not hold, the evidence is non-conclusive. The intuitive interpretation assumes that conclusive evidence is governed by classical logic. Thus, a formula implies that classical reasoning holds for , as well as for all formulas built from using the connectives , , and . In [27], an alternative but closely related intuitive interpretation in terms of information has been proposed for LETs. Accordingly, a sentence means that the information conveyed by , positive or negative, is reliable, and when does not hold, it means that there is no reliable information about . 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 is a minimal , obtained by simply adding to rules validating the inferences below:
which recover classical logic for sentences in the scope of . is the -free fragment of the logic , introduced in [8] and further investigated in [2, 25]. is equipped with a constructive implication – it is obtained by adding to Nelson’s logic [1] the inferences (1) and (2) above. The proof theory of was investigated in [25], which provides the basis for some of the results established here. is also the -free fragment of the logic , investigated in [27] ( is a non-classicality operator: it has a deductive behavior dual to and means that there is no conclusive evidence about – see [27 Section 3.1]). A first-order version of has been studied in [25].
The notion of evidence for a sentence 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 does not imply the truth of . There may be simultaneous conflicting evidence for sentences and , and evidence for is meant to be objective in the sense that it is independent from the belief of an agent in . 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 of sentential letters and the set of connectives . The language is the set of formulas generated by over . Roman capitals , , , will be used as metavariables for the formulas of , while Greek capitals , , , will be used as metavariables for finite sets of formulas.
Definition 3.1. (The natural deduction system )
The deductive system is defined over the language by the following rules:
The assumption classes , , , 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 , where there is no notion of major or minor premises.
The definition of a derivation of from in is the usual one for natural deduction systems (recall that we assume here that is a finite set). It suffices to say that a derivation is a tree of formulas whose nodes are either elements of or are obtained from earlier nodes by applications of the rules above, and whose bottom node is its conclusion. We write to mean that there exists a derivation in from the premises in with conclusion , omitting the subscript when there is no risk of confusion.
Definition 3.2. (Valuation semantics for )
A bivalued semantics for is given by the class of functions satisfying the following clauses:
v1. iff and ,
v2. iff or ,
v3. iff or ,
v4. iff and ,
v5. iff ,
v6. If , then if and only if .
We say that a formula is a semantic consequence of , written , if and only if for every valuation , whenever for all , then .
As remarked in the Introduction, the logic is a fragment of both the sentential logics and , introduced in [8] and [27] respectively. extends with the operator , already mentioned in Section 2, together with its corresponding rules. The semantics presented above is obtained simply by suppressing the clause for the connective in the semantics of [27 Definition 26]. A natural deduction system for is obtained just by dropping the -rules from the deductive system of [27 Definition 23]. The system presented here differs from the -free system of [27] only with respect to the rule that recovers excluded middle, but both are equivalent. A system identical to is the sentential fragment of the first-order version of , investigated in [25].
is sound and complete with respect to the bivalued semantics presented in Definition 3.2.
Theorem 3.3.
Proof. Since the logic is contained in , the soundness and completeness of the system with respect to the semantics above follow immediately from the corresponding soundness and completeness results for [27 Theorem 28].
The sequent calculus
Below, we present the sequent system , 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 , with no explicit structural rules.1
Definition 3.4. (The system )
The system is defined over the language . Greek capitals , , now denote multisets of formulas of formulas of , and , range over formulas of . The notions of principal, active and context formulas are understood in the standard way.
Axioms:
Structural rules:
Logical rules:
A derivation in 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 is said to be derivable in the if there exists a derivation whose conclusion is .
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, , is either an atomic formula or the negation of an atomic formula .
The weight of a formula , denoted , is defined as follows:
(a) , where is a literal;
(b) ;
(c) , for ;
(d) , for ;
(e) ;
We define the notion of generalized subformula as follows:
(a) is a generalized subformula of ;
(b) is a generalized subformula of ;
(c) and are generalized subformulas of both , ;
(d) and are generalized subformulas of , ;
(e) and are generalized subformulas of .
The height of a derivation , denoted , is defined as follows:
(a) If is a derivation consisting of an initial (axiomatic) sequent, then .
(b) If is a derivation of a sequent obtained from a single premise by an inference rule, and is a derivation of , then .
(c) If is a derivation of a sequent obtained from two premises and by an inference rule, and and are derivations of and , respectively, then .
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 that uses the rule , there exists a derivation of the same end-sequent that does not use the rule .
Proof. In [11], cut-elimination is established for through a proof of elimination of multicut. The logical rules of are precisely the -free fragment of those of . While treats contexts as sets, thus making explicit contraction unnecessary, uses multisets and therefore requires an explicit contraction rule. Adapting the cut-elimination proof from (with sets) to (with multisets) is essentially routine, and the use of multicut accounts for the known problems caused by contraction. □
The system is inspired by the systems and presented in Troelstra and Schwichtenberg [29 Chapter 3]. It extends with rules for and , which behave as the positive rules for and (with formulated as in ), and with rules for , taken from , a sequent calculus for the logic of evidence and truth , introduced in [11].
By contrast with and , which are able to prove the elimination of the non-atomic axiom rule (see [29 pp. 65]), in we cannot restrict the axiom rule to literals as principal formulas. The reason is that, under such a restriction, we cannot derive , since there is no right rule for .
Besides highlighting the peculiarities of a sequent system for , there is another reason for introducing first. Its logical rules provide a more convenient setting for proving its equivalence with . 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 and we prove the equivalence between the natural deduction system and .
Proposition 3.7. (Disjunction property and constructive falsity)
(i) Disjunction property: if is derivable in , then either or is derivable in .
(ii) Constructive falsity: if is derivable in , then either or is derivable in .
Proof. For (i), given a cut-free derivation of , the only rule that can introduce the formula on the right is . For (ii), given a cut-free derivation of , the only rule that can introduce the formula on the right is .
We can strengthen this result by adapting the notion of Harrop formulas to our setting.
Definition 3.8. The class of Harrop-like formulas is defined as follows:
Every literal is an -formula.
If and are -formulas, then is a -formula.
If and are -formulas, then is a -formula.
For any , is an -formula.
Nothing else is an -formula.
Proposition 3.9.
(i) Strong disjunction property: if is derivable in and consists only of -formula, then either or is derivable in .
(ii) Strong constructive falsity: if is derivable in and consists only of -formula, then either or is derivable in .
Proof.
(i) If , then the derivation is an axiom, and hence it must have the form . Thus, the end-sequent cannot be with consisting only of -formulas. Now suppose and is composed of -formulas. If the last rule applied is , then or , respectively, is a premise of the last inference. If the last rule is , then , and the premise is . Since is a -formula, and are -formulas as well. By the inductive hypothesis, either or . If was used to derive , introducing an -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 . If any other rule is the last rule, then is not composed of -formulas.
(ii) This proof can be directly adapted to the case of the strong constructive falsity property by simply considering the rule in the place of . The cases of and are analogous.
Remark 3.10. (On the constructive character of )
(i) The idea of a constructive negation was proposed by Nelson [24], where the first-order logic is introduced. The sentential fragment of is the logic , and is obtained by dropping explosion from . 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 and have a constructive negation and also a constructive implication. That is, instead of proving the falsity of a formula by deriving a contradiction from the assumption , one proves directly (the notion of a proof of is primitive, just like that of a proof of ). 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 , which is equivalent to , in a context
with constructive negation. A formula cannot be an -formula, since it implies , which is equivalent to . Whenever either formula holds, even if restricted to one or a few instances, we can derive formulas of the form , as well as formulas of the form , 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 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 , which is the -free fragment of , and the -free fragment of , is constructive. On the other hand, formulas in the scope of exhibit classical, non-constructive behavior.
(iii) Note that the results of Propositions 3.7 and 3.9 are features of , so they hold for the natural deduction system and are inherited by , to be introduced in § 4.
Now, we turn to the equivalence between and .
Equivalence between and
The notation means that there exists a derivation of in from the open assumptions in . The notation means that there exists a derivation of the sequent in . Note that although is a set of formulas in natural deduction, in the translation of a derivation into a sequent we treat as a multiset: each open assumption class (with a distinct label) contributes one occurrence of on the left-hand side of the corresponding sequent.
The derivability relation of admits left contraction and left weakening. More precisely, if , then , and if , then . Contraction is obtained by identifying the labels of two distinct assumption classes containing the same formula. Left weakening is obtained as follows:
Left weakening corresponds to the monotonicity of the derivability relation: if a formula is derivable from the assumptions , then is also derivable from , where the added assumption may remain unused in the derivation. These properties are required in order to establish the equivalence between and , since includes both weakening and contraction as explicit structural rules.
Theorem 3.11. if and only if .
Proof. Assume that the proof of in is cut-free.
From left to right, the proof proceeds by induction on the height of derivations in . Let be a multiset. The notation denotes the underlying set associated with , that is, the set of formulas occurring in , ignoring multiplicities. If , then is an axiom. In , this corresponds to a deduction consisting of a single node . If , let be a derivation of of height in . We assume as induction hypothesis that the result holds for all derivations in of height at most ; that is, for every derivation of in of height at most , there exists a deduction in deriving from . We then consider all the inference rules of .
The remaining cases are left to the reader.
From right to left, the proof proceeds by induction on the height of deductions in . If , then the deduction in consists of a single node . In , corresponds to an axiom. If , let be a deduction in of height deriving from a set of assumptions . As induction hypothesis, assume that the result holds for every deduction in of height at most that is, for any deduction of height at most deriving from a set of assumptions , there exists a derivation in of the sequent , where is the multiset corresponding to . We then examine the last inference rule applied in and construct a corresponding derivation in . The double line denotes a (possibly empty) sequence of applications of or . Moreover, the notation stands for the multiset that contains exactly one occurrence of each distinct formula appearing in , that is, multiplicities in the original multisets are ignored.
The remaining cases are left to the reader.
The cut-free sequent system
We now introduce , a sequent system for 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 )
Axioms:
Logical rules:
The differences between and 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 system is represented in where contraction is an explicit rule. Consider the left conjunction rule of .
It is easy to see that this rule is really composed of two steps: the introduction of a conjunction followed by contraction. In , an application of this rule can be represented as follows:
Admissibility of structural rules in
We now show that the structural rules are admissible in . In the following we will write (where is a sequent) to mean that has a derivation of height at most . When there is no risk of ambiguity, we omit the subscript and write to denote the derivability of .
Theorem 4.3. (Height-preserving weakening) If and , then .
Proof. The proof is by induction on the height of the given derivation.
If , then is an axiom. Hence, for any with , the sequent is also an axiom, since adding formulas to the antecedent yields another axiom.
For , we consider the last inference in the derivation of .
Suppose that , i.e. is obtained by an application of . Then the premises of the last inference are and , each one having a derivation of height strictly less than . By the induction hypothesis, for any such that , we obtain derivations of and of height strictly less than . Applying to these sequents, we derive , that is, , with a derivation of height at most .
The other cases are left to the reader. □
Theorem 4.4. (Height-preserving contraction) If , then .
Proof. The proof is by induction on the height of the derivation.
If , then is an axiom, and hence is also an axiom.
For , we consider the last inference in the derivation of .
(i) If the contracted formula is not principal in the last inference, then the premises of that inference have derivations of height strictly less than . By the induction hypothesis, contraction is admissible in those premises, and reapplying the same inference yields a derivation of of height at most .
(ii) Now suppose the contracted formula is principal in the last inference.
:::
Suppose . In this case, the last rule is and the conclusion is . The premise of this inference is , which has a derivation of height strictly less than . By the induction hypothesis, we obtain a derivation of of height strictly less than . Applying , we derive , that is, , with a derivation of height at most .
Suppose and the last rule is . In this case, the conclusion is , and the premises are and , both with derivations of height strictly less than . By the induction hypothesis, we obtain derivations of both premises with height strictly less than . Applying , we obtain , that is, , with a derivation of height at most .
The remaining cases are left to the reader. □
We now prove the admissibility of (multiplicative) Cut for 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 )
If and , then so is .
Proof.
We need to consider three cases:
At least one of the premises of Cut is an axiom;
The cut formula is principal in both premises;
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 and , concluding , which can be alternatively derived by zero or more applications of to the latter premise, deleting the application of 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 are and , concluding , 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 with one of less height and one or two of less weight. In what follows, the double line indicates one or more applications of .
(i) The cut-formula .
is replaced with
(ii) The cut formula .
is replaced with
The remaining cases are left to the reader.
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 .
(i) The last rule of the right premise is .
is replaced with
(ii) The last rule of the left premise is .
is replaced with
(iii) The left premise has been obtained by .
is replaced with
The remaining cases are left to the reader.
Proposition 4.6. (Generalized subformula property) Let be a cut-free derivation of in . Then, all formulas appearing in will be generalized subformulas of and
Proof. The claim is easily established by a simple inspection of the rules given of .
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 rule.
Remark 4.8. (On the path to ) In order to obtain a fully logical sequent calculus for , 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 , 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 already resemble those of standard 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 -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 , except for the -rules, which we reformulated as in .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- rules.
It was this failed attempt with the intermediate system that led us to apply Kleene’s trick to all logical rules of to obtain . This, in turn, enabled us to prove the admissibility of height-preserving without appealing to any invertibility lemma.
Soundness and completeness
We first establish the equivalence between and .
Theorem 4.9.
Proof. From left to right, all left structural rules, together with cut, were shown to be admissible in in theorems 4.3, 4.4, and 4.5. All left logical rules of can also be shown admissible in through the help of Theorem 4.3. From right to left, all rules of can also be shown admissible in . The axiom rule follows from 0 or more uses of , and the other logical rules follow from a simple application of .
Now, soundness and completeness of follow straightforwardly from the above result.
Theorem 4.10. is sound and complete with respect to the bivalued semantics of :
Proof. The result follows from Theorem 4.9 above, together with Theorems 3.3 and 3.11.
A decision method for
Recall that the design of our rules is inspired by Kleene’s 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 .
Definition 4.11. (Cognate sequents)
(i) Two sequents and are said to be cognate if and contain the same formulas, possibly differing in multiplicity, that is, in the number of occurrences of each formula, and .
(ii) An irredundant proof in 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 of in can be transformed into an irredundant cut-free derivation of the same sequent.
Proof.
If no branch of contains a pair of cognate sequents such that one occurs above the other (possibly with intervening sequents), then is already irredundant.
Otherwise, fix a branch and choose a pair of cognate sequents and on that branch such that occurs above and there is no cognate sequent strictly between them on that branch. Write as and as , where and contain the same formulas, possibly with different multiplicities.
Delete the subderivation leading from to ( included) together with all branches contributing to it. Next, apply Theorem 4.4 to (possibly zero times), rendering it equal to . The resulting derivation is still cut-free, derives , and strictly decreases the number of occurrences, along the branches of , 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 . □
The proof that provides a decision method to will be given after the following example illustrating the decision procedure.
Example 4.13.
(i) The sequent (disjunctive syllogism) is not derivable in .
Observe that further bottom-up applications of 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 s it is equivalent to explosion. Below, we show how its derivability can be recovered by means of the classicality connective.
(ii) The sequent is derivable in .
A bottom-up application of the rule yields an axiom as the right premise and a sequent as the left premise that is clearly derivable, since it is an instance of . The latter is derivable in and recovers the principle of explosion. By a further bottom-up application of , we obtain two axioms and close the proof.
(iii) The sequent is not derivable in .
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 .
(iv) The sequent is not derivable in .
Consider the constructions below:
The construction on the left shows that a bottom-up application of yields a cognate sequent as the left premise, thereby stopping the search in that branch. Note that any application of to a sequent of the form or yields a cognate sequent as the left or right premise. Thus, the only remaining possibility is to apply . However, two successive bottom-up applications of also yield cognate sequents, as the construction on the right shows.
We leave as an exercise to the reader to show that the sequents and are not derivable in . The non-derivability of the latter sequent shows that is syntactically consistent. Indeed, in a bottom particle can be defined by , for any . Hence, if were derivable, then so would be , which is impossible. Therefore, 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 is derivable in is decidable.
Proof. Our strategy will be to show that we can generate all possible cut-free irredundant derivations of 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 can be assumed to be cut-free and to contain only generalized subformulas of and .
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 and 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 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 family, by developing -style sequent calculi together with bottom-up decision procedures for other sentential systems, in particular and the six-valued logics and [10]. In a second stage, we also intend to investigate the proof theory of their corresponding first-order extensions.
References
- [1]A. Almukdad and D. Nelson. Constructible falsity and inexact predicates. The Journal of Symbolic Logic, 49(1):231–233, 1984.DOI
- [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]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]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]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]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]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]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]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]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]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]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]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]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]A. G. Dragalin. Mathematical intuitionism: introduction to proof theory. American Mathematical Society, 1988.DOI
- [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]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]J. Fetzer. Information: Does it have to be true? Minds and Machines, 14:223–229, 2004.DOI
- [19]S. C. Kleene. Introduction to Metamathematics. North-Holland, Amsterdam, 1952.
- [20]J. Marcos. Logics of Formal Inconsistency. PhD thesis, University of Campinas, 2005.
- [21]J. Marcos. Nearly every normal modal logic is parnormal. Logique et Analyse, 48:279–300, 2005.
- [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]S. Negri and J. von Plato. Structural Proof Theory. Cambridge University Press, 6 2001.
- [24]D. Nelson. Constructible falsity. The Journal of Symbolic Logic, 14, 1949.DOI
- [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]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]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]H. Schellinx. The Noble Art of Linear Decorating. Doctoral thesis, University of Amsterdam, 1994. URL https://eprints.illc.uva.nl/id/eprint/1964/.
- [29]A. S. Troelstra and H. Schwichtenberg. Basic Proof Theory. Cambridge University Press, 2nd edition, 7 2000.
- [30]H. Wansing. The Logic of Information Structures. Springer, 1993.DOI