Interpolation conjecture for the calculus of structures

From papers

Let TT and RR be structures, and let SKS\mathsf{SKS} denote the calculus-of-structures system for classical propositional logic. Write SKS{-identity,-weakening}\mathsf{SKS}\setminus\{\mathord{\downarrow}\text{-identity},\mathord{\downarrow}\text{-weakening}\} and SKS{-identity,-weakening}\mathsf{SKS}\setminus\{\mathord{\uparrow}\text{-identity},\mathord{\uparrow}\text{-weakening}\} for the systems obtained by omitting the indicated rules.

Interpolation conjecture. For every derivation TSKSRT\vdash_{\mathsf{SKS}}R, there is a structure PP and derivations

TSKS{identity,weakening}PT\vdash_{\mathsf{SKS}\setminus\{\text{identity},\text{weakening}\}}P

and

PSKS{dual identity,dual weakening}R.P\vdash_{\mathsf{SKS}\setminus\{\text{dual identity},\text{dual weakening}\}}R.

The derivation is separated into a top phase whose rules do not introduce new atoms going down and a bottom phase whose rules do not introduce new atoms going up; consequently, PP contains only atoms occurring in both TT and RR and is an interpolant. The source states that a semantic proof is available in the propositional case, while a syntactic proof extending to predicate logic remains desirable.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Kai Bruennler, “Locality for Classical Logic”, arXiv:math/0301317 (2003).

Solutions 0

No solutions have been posted yet.