Split Interpolation Refining Craig’s Theorem via Three-Valued Logics

Quentin Blomet a,b · 2025

Read Split Interpolation Refining Craig’s Theorem via Three-Valued Logics by Quentin Blomet a,b (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20924.txt.

Introduction

Quentin Blomet, a solo author, asks a logic question in a 2025 paper about how two formulas can share a middle step. The classic result behind the work is Craig's theorem on interpolation. Blomet studies a split form of that result, where the middle formula must link to one side in one logic and to the other side in a second logic.

Both logics use three truth values and the same basic rules for joining statements. The paper finds which choices of truth tables and proof rules make the split property hold. Each case where it holds sharpens the classic theorem for these weaker logics.

Catalog record

CREATORQuentin Blomet a,b
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-20924

Browse the full library · About the Tower of Babel

Full text

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

Split Interpolation Refining Craig’s Theorem via Three-Valued Logics Quentin Blomet a,b Abstract Which choices of truth tables and consequence relations for two logics 𝖫 1 \mathsf{L}_{1} and 𝖫 2 \mathsf{L}_{2} ensure the satisfaction of the following split interpolation property: If two formulas ϕ \phi and ψ \psi share at least one propositional atom and ϕ \phi classically entails ψ \psi , then there is a formula χ \chi that shares all its propositional atoms with both ϕ \phi and ψ \psi , such that ϕ \phi entails χ \chi in 𝖫 1 \mathsf{L}_{1} and χ \chi entails ψ \psi in 𝖫 2 \mathsf{L}_{2} ? We identify the cases in which this property holds for any pair of propositional logics based on the same three-valued Boolean normal monotonic scheme for connectives and two monotonic consequence relations. Since the resulting logics are subclassical, every instance of this property constitutes a particular refinement of Craig’s deductive interpolation theorem, as it entails the latter and further restricts the range of possible interpolants. keywords Three-valued logics; Interpolation; Kleene logics; Non-classical logics; Strict-tolerant logic; Logic of paradox; Strong Kleene logic; Weak Kleene logic † † affiliation: a Institut Jean-Nicod (CNRS, ENS-PSL, EHESS), PSL University, 29 rue d’Ulm, Paris, 75005, France; b Department of Philosophy, University of Greifswald Baderstraße 6, Greifswald, 17489, Germany 1 Introduction Craig1957 ’s deductive interpolation theorem is a foundational result of classical logic that can be formulated along these lines: Given any two formulas \phi and \psi built from the classical propositional language, if \phi and \psi share some atom and \phi classically entails \psi , then there is a formula \chi such that each of its atoms is in \phi and \psi , and \phi classically entails \chi and \chi classically entails \psi . Since 1957, several interpolation results have been established for other logics: by Schutte1962 for first-order intuitionistic logic, by Maksimova1977 for superintuitionistic logics, or by NolaLettieri2000 for axiomatic extensions of Łukasiewicz logic, just to name a few. Interpolation results have been applied in a wide range of domains, from the study of explanation ( Hintikka1999 ) to SAT-based model checking ( McMillan2003 ) . In recent articles, milne2016refinement and Prenosil2017 presented a refined version of the deductive interpolation theorem, resorting to the three-valued logics \mathsf{K}_{3} and \mathsf{LP} . The Strong Kleene logic \mathsf{K}_{3} is a paracomplete logic developed by Kleene1952-KLEITM to account for partial functions, while Asenjo1966 and Priest1979 ’s Logic of Paradox \mathsf{LP} is a paraconsistent logic developed to account for paradoxical statements. Milne’s split interpolation theorem goes as follows: For any two formulas \phi and \psi , if \phi is satisfiable, \psi falsifiable, and \phi classically entails \psi , then there is a formula \chi such that each of its atoms is in \phi and \psi , and \phi entails \chi in \mathsf{K}_{3} and \chi entails \psi in \mathsf{LP} . 1 1 1 Note the difference in the antecedent of the conditional in Craig’s interpolation theorem compared to Milne’s. While Craig’s theorem requires that \phi and \psi share an atom, Milne’s requires that \phi is satisfiable and \psi falsifiable. The former condition is strictly weaker than the latter in the absence of constants in the language. If \phi is satisfiable, \psi falsifiable, and \phi classically entails \psi , then \phi and \psi must necessarily share some atom. For the remainder of this paper, we will focus exclusively on the former condition, as any interpolation result stated with this condition is strictly stronger than those stated with the latter. The refinement of Craig’s deductive interpolation theorem is evident from the fact that classical logic extends both \mathsf{K}_{3} and \mathsf{LP} . Specifically, if \phi entails \psi in \mathsf{K}_{3} or \mathsf{LP} , then \phi entails \psi in classical logic. Therefore, Craig’s theorem directly follows from Milne’s refinement. The operations of both \mathsf{K}_{3} and \mathsf{LP} are defined over the set \{0,\nicefrac{{1}}{{2}},1\} using the Strong Kleene truth tables. Negation is characterized as an order-reversing, involutive unary operation, while disjunction and conjunction are binary operations corresponding to the functions \mathit{max} and \mathit{min} over the total order 0<\nicefrac{{1}}{{2}}<1 . The distinction between \mathsf{K}_{3} and \mathsf{LP} lies in the preservation of different designated values from premises to conclusions in valid inferences. In \mathsf{LP} , if the premises take values in the set \mathbf{t}=\{\nicefrac{{1}}{{2}},1\} , then the conclusion does as well. In contrast, \mathsf{K}_{3} preserves the truth values within the set \mathbf{s}=\{1\} . The Strong Kleene truth tables belong to a class of truth tables referred to as Boolean normal monotonic schemes by da2023three . Informally, a scheme for the connectives is Boolean normal if all its operations coincide with the classical two-valued ones when applied to classical values. A scheme is monotonic if all its operations are monotonic with respect to the information order \leq_{I} , where \nicefrac{{1}}{{2}}<_{I}1 and \nicefrac{{1}}{{2}}<_{I}0 . Alongside the two standards of evaluation \mathbf{ss} (which ensures the preservation of 1 from premises to conclusion) and \mathbf{tt} (which ensures the preservation of both 1 and \nicefrac{{1}}{{2}} from premises to conclusion), Da Ré et al. examine the standards \mathbf{st} , \mathbf{ts} , and \mathbf{ss}\cap\mathbf{tt} . The \mathbf{st} standard is defined so that if the premises take a value in \mathbf{s} , the conclusion must take a value in \mathbf{t} , and conversely for \mathbf{ts} . The \mathbf{ss}\cap\mathbf{tt} standard, on the other hand, requires that an argument be valid under both the \mathbf{ss} and \mathbf{tt} conditions. All five standards correspond to the intersective mixed consequence relations over the set \{0,\nicefrac{{1}}{{2}},1\} , which naturally generate the class of three-valued monotonic consequence relations (see Chemlaetal2017 ). 2 2 2 This notion of monotonicity should not be confused with the one used to characterize schemes. It describes consequence relations such that for all set of formulas \Gamma,\Delta , if \Gamma entails \Delta , then \Gamma\cup\Gamma^{\prime} entails \Delta\cup\Delta^{\prime} , for any set of formulas \Gamma^{\prime},\Delta^{\prime} . Da Ré et al. show in particular that when combined with a Boolean normal monotonic scheme, the \mathbf{st} standard yields a logic in which the valid inferences align precisely with those of classical logic. These results provide an opportunity to extend Milne’s interpolation theorem and address an open problem posed by Přenosil, which seeks additional natural examples of the split interpolation property. 3 3 3 https://sites.google.com/site/adamprenosil/problems To achieve this, we will explore the following question: Which choice of three-valued logics \mathsf{L}_{1} and \mathsf{L}_{2} based on a Boolean normal monotonic scheme and a monotonic consequence relation guarantees that the following property holds true: If two formulas \phi and \psi share some atom, and \phi classically entails \psi , then there is a formula \chi such that each of its atoms is in \phi and \psi , and \phi entails \chi in the logic \mathsf{L}_{1} and \chi entails \psi in the logic \mathsf{L}_{2} . Out of the 400 possible combinations of the 25 couples of standards with the 16 Boolean normal monotonic schemes, we will see that 40 satisfy the split interpolation property, with 8 of these offering stronger refinements of Craig’s interpolation theorem than the others. To prove our claim, we start by defining the key notions used throughout the paper in Section 2 , in particular the notions of monotonicity and Boolean normality. In Section , we answer our main question for

Read the complete text