Universal proof theory: Semi-analytic rules and Craig interpolation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F25%3A00598219" target="_blank" >RIV/67985840:_____/25:00598219 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/67985807:_____/25:00598219

Výsledek na webu

<a href="https://doi.org/10.1016/j.apal.2024.103509" target="_blank" >https://doi.org/10.1016/j.apal.2024.103509</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.apal.2024.103509" target="_blank" >10.1016/j.apal.2024.103509</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Universal proof theory: Semi-analytic rules and Craig interpolation

Popis výsledku v původním jazyce

We provide a general and syntactically defined family of sequent calculi, called semi-analytic, to formalize the informal notion of a “nice” sequent calculus. We show that any sufficiently strong (multimodal) substructural logic with a semi-analytic sequent calculus enjoys the Craig Interpolation Property, CIP. As a positive application, our theorem provides a uniform and modular method to prove the CIP for several multimodal substructural logics, including many fragments and variants of linear logic. More interestingly, on the negative side, it employs the lack of the CIP in almost all substructural, superintuitionistic and modal logics to provide a formal proof for the well-known intuition that almost all logics do not have a “nice” sequent calculus. More precisely, we show that many substructural logics including UL−, MTL, R, Łn (for n⩾3), Gn (for n⩾4), and almost all extensions of IMTL, Ł, BL, RMe, IPC, S4, and Grz (except for at most 1, 1, 3, 8, 7, 37, and 6 of them, respectively) do not have a semi-analytic calculus.

Název v anglickém jazyce

Universal proof theory: Semi-analytic rules and Craig interpolation

Popis výsledku anglicky

We provide a general and syntactically defined family of sequent calculi, called semi-analytic, to formalize the informal notion of a “nice” sequent calculus. We show that any sufficiently strong (multimodal) substructural logic with a semi-analytic sequent calculus enjoys the Craig Interpolation Property, CIP. As a positive application, our theorem provides a uniform and modular method to prove the CIP for several multimodal substructural logics, including many fragments and variants of linear logic. More interestingly, on the negative side, it employs the lack of the CIP in almost all substructural, superintuitionistic and modal logics to provide a formal proof for the well-known intuition that almost all logics do not have a “nice” sequent calculus. More precisely, we show that many substructural logics including UL−, MTL, R, Łn (for n⩾3), Gn (for n⩾4), and almost all extensions of IMTL, Ł, BL, RMe, IPC, S4, and Grz (except for at most 1, 1, 3, 8, 7, 37, and 6 of them, respectively) do not have a semi-analytic calculus.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Annals of Pure and Applied Logic

ISSN

0168-0072

e-ISSN

1873-2461

Svazek periodika

176

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

26

Strana od-do

103509

Kód UT WoS článku

001307686700001

EID výsledku v databázi Scopus

2-s2.0-85202691079