E. H. Haeusler: Compressing huge Natural Deduction proofs in the Minimal Purely Implicational Logic

Logic Supergroup — Online Colloquium, September 3, 2020

Edward Hermann Haeusler (PUC-Rio): Compressing huge Natural Deduction proofs in the Minimal Purely Implicational Logic

We estimate the size of a labelled tree by comparing the amount of (labelled) nodes with the size of the set of labels. Roughly speaking, a exponentially big labelled tree, is any labelled tree that has an exponential gap between its size, number of nodes, and the size of its labelling set. The number of sub-formulas of any formula is linear on the size of it, and hence any exponentially big proof has a size $a^n$, where $a>1$ and $n$ is the size of its conclusion. In this article, we show that the linearly height labelled trees whose sizes have an exponential gap with the size of their labelling sets posses at least one sub-tree that occurs exponentially many times in them. Natural Deduction normal proofs and derivations in minimal implicational logic ($M_\supset$) are essentially labelled trees. By the sub-formula principle any normal derivation of a formula $\alpha$ from a set of formulas $\Gamma=\{\gamma_1,\ldots,\gamma_n\}$ in $M_\supset$, establishing $\Gamma\vdash_{M_\supset}\alpha$, has only sub-formulas of the formulas $\alpha,\gamma_1,\ldots,\gamma_n$ occurring in it. By this relationship between labelled trees and normal derivations in $M_\supset$, we show that any normal proof of a tautology in $M_\supset$ that is exponential on the size of its conclusion has a sub-proof that occurs exponentially many times in it. Thus, any normal and linearly height bounded proof in $M_\supset$ is inherently redundant. Finally, we show how this redundancy provides us with a highly efficient compression method for propositional proofs. We also provide some examples that serve to convince us that exponentially big proofs are more frequent than one can imagine. We conclude by providing reasons to believe that the compression method discussed here can be applied to super-polynomial proofs.