Gabriele Pulcini (New University of Lisbon): From Complementary Logic to Proof-Theoretic Semantics

Two proof-systems P and P* are said to be complementary when one proves exactly the non-theorems of the other. Complementary systems come as a particular kind of refutation calculi whose patterns of inference always work by inferring unprovable conclusions form unprovable premises. In the first part of my talk, I will focus on LK*, the sequent system complementing Gentzen’s system LK for classical logic. I will show, then, how to enrich LK* with two admissible (unary) cut rules, which allow for a simple and efficient cut-elimination algorithm. In particular, two facts will be highlighted: 1) for any given provable sequent, complementary cut-elimination always returns one of its simplest proofs, and 2) provable LK* sequents turn out to be “deductively polarized” by the empty sequent. In the second part, I will observe how an alternative complementary sequent system can be obtained by slightly modifying the Gentzen-Schütte system G3. I will finally show how this move could pave the way for a novel approach to multi-valuedness and proof-theoretic semantics for classical logic.