Interpolation conjecture for the calculus of structures

About 23 years old · traced to

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 T⊢SKSRT\vdash_{\mathsf{SKS}}R, there is a structure PP and derivations

T⊢SKS∖{identity,weakening}PT\vdash_{\mathsf{SKS}\setminus\{\text{identity},\text{weakening}\}}P

and

P⊢SKS∖{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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.