Coarsening Natural Deduction Proofs I: Finding Perfect Proofs

Abstract

Abstract This paper explores how, given a proof, we can systematically transform it into a proof that contains no irrelevancies and which is as strong as possible. I define a weaker and stronger notion of what counts as a proof with no irrelevancies, calling them perfect proofs and gaunt proofs, respectively. Using classical core logic to study classical validities and core logic to study intuitionistic validities, I show that every core proof or classical core proof can be transformed into a perfect proof. In a sequel paper, I show how proofs in core logic can also be transformed into gaunt proofs and I observe that this property fails for classical core logic.