scientific article; zbMATH DE number 1302506

From MaRDI portal
Publication:4249036





Familiar conversion (cut-elimination) rules for natural deduction are asymmetric: very simple for some connectives (like \(\&\) and \(\forall)\) and more complicated for others (like \(\vee)\). This makes normalization proofs look unbalanced: \(\&,\forall\)-cases of inductive proofs of lemmata are simple, \(\to\)-cases more complicated and \(\vee\)-cases are much more complicated, since they have to deal with permutative conversions. The author proposes changing elimination rules for all connectives to make all of them similar to standard \(\vee\)-elimination. For example \(\to\)-elimination becomes (when \(\vdash\) divides undischarged assumptions from the goal): \[ {\Gamma\vdash A\to B;\;\Delta\vdash A;\;B,\Sigma\vdash C\over\Gamma,\Delta,\Sigma\vdash C}. \] The list of reductions for the resulting system includes a lot of additional (compared to standard proof) permutative conversions corresponding to new kinds of ``segments introduced in this way. After this a long normalization proof (looking similar enough to Prawitz' original proof) for the \((\neg,\to, \vee)\)-fragment of intuitionistic and classical logic is presented. For the entire collection see [Zbl 0905.00049].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249036)