Normalization theorems for full first order classical natural deduction

From MaRDI portal





We prove the strong normalization theorem for full first order classical N.D. (natural deduction) --- full in the sense that all logical constants are taken as primitive. We also give a syntactic proof of the normal form theorem and (weak) normalization for the same system. The theorem has been stated several times, and some proofs appear in the literature. The first proof occurs in \textit{R. Statman}'s Ph. D. Thesis [Structural complexity of proofs, Stanford Univ. (1974)], where full first order classical N.D. (with the elimination rules for \(\lor\) and \(\exists\) restricted to atomic conclusions) is embedded in a system for second order (propositional) intuitionistic N.D., for which a strong normalization theorem is proved using strongly impredicative methods. A proof of the normal form theorem and (weak) normalization theorem occurs in a paper of \textit{J. P. Seldin} [J. Symb. Log. 52, 626-647 (1986; Zbl 0639.03022)]as an extension of a proof of the same theorem for an N.D.-system for the intermediate logic called MH. The proof of the strong normalization theorem presented in this paper is obtained by proving that a certain kind of validity applies to all derivations in the system considered. The notion validity is adopted from \textit{D. Prawitz} [Proc. 2nd Scandinav. Logic Symp. 1970, Stud. Logic Found. Math. 63, 235-307 (1971; Zbl 0226.02031)], where it is used to prove the strong normalization theorem for a restricted version of first order classical N.D., and is extended to cover the full system. Notions similar to validity have been used earlier by Tait (convertibility), Girard (réducibilité) and Martin-Löf (computability).




Cited in
(40)








This page was built for publication: Normalization theorems for full first order classical natural deduction

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