Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: logic

Topic: (uniform) interpolation and proof equalities/normalization

zigzag (Mar 22 2021 at 11:13):

Hi! I have sort-of-recently learned about interpolation, and I'm curious about a few things.

In constructive proofs of Craig's interpolation, you typically produce from a proof of $\pi : \varphi \to \psi$ an interpolant $\theta$ which only mention relational symbols common to both $\varphi$ and $\psi$ as well as proofs $\pi_L : \varphi \to \theta$ and $\pi_R : \theta \to \psi$. One thing that struck me when first learning about this was that it seemed to me that for intuitionistic logic, if one takes the equational theory of proofs required by categorical logic, it would be likely that we additionally have $\pi = \pi_R \circ \pi_L$. After searching for a bit, I think I have found the relevant result for propositional logic https://link.springer.com/article/10.1007/BF01270628 Is it also true for FO?

I was also wondering if something like this could also apply to the proof of uniform interpolation for IPC https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/on-an-interpretation-of-second-order-quantification-in-first-order-intuitionistic-propositional-logic/91B1E19D796151CADA66E4BEDE8DBE9F Does this construction gives actual categorical quantifiers in the corresponding syntactic fibration?