Normalization theorems for full first order classical natural deduction
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).
- A semantical proof of the strong normalization theorem for full propositional classical natural deduction
- Strong normalization of classical natural deduction with disjunctions
- Proofs of strong normalisation for second order classical natural deduction
- A normalization-procedure for the first order classical natural deduction with full logical symbols
- Normal natural deduction proofs (in classical logic)
- Peirce's rule in natural deduction.
- Bilateralism does not provide a proof theoretic treatment of classical logic (for technical reasons)
- Non-strictly positive fixed points for classical natural deduction
- Intrinsic reasoning about functional programs. II: Unipolar induction and primitive-recursion
- Church-Rosser property of a simple reduction for full first-order classical natural deduction
- A normalization-procedure for the first order classical natural deduction with full logical symbols
- Normalisation and subformula property for a system of classical logic with Tarski's rule
- Normality, non-contamination and logical depth in classical natural deduction
- Full classical S5 in natural deduction with weak normalization
- A normative model of classical reasoning in higher order languages
- Postponement of $\mathsf {raa}$ and Glivenko's theorem, revisited
- On natural deduction in classical first-order logic: Curry-Howard correspondence, strong normalization and Herbrand's theorem
- Normal derivability in classical natural deduction
- Gentzen's proof systems: byproducts in a work of genius
- Realizability Proof for Normalization of Full Differential Linear Logic
- HARMONISING HARMONY
- scientific article; zbMATH DE number 3853043 (Why is no real title available?)
- A new S4 classical modal logic in natural deduction
- Subformula and separation properties in natural deduction via small Kripke models
- Reduction in first-order logic compared with reduction in implicational logic
- Transformations via Geometric Perspective Techniques Augmented with Cycles Normalization
- scientific article; zbMATH DE number 3950526 (Why is no real title available?)
- Normalization of S-terms is decidable
- Proofs of strong normalisation for second order classical natural deduction
- A short proof of the strong normalization of classical natural deduction with disjunction
- A NORMAL FORM THEOREM FOR SECOND-ORDER CLASSICAL LOGIC WITH AN AXIOM OF CHOICE
- scientific article; zbMATH DE number 1406467 (Why is no real title available?)
- Normal Gentzen deductions in the classical case
- The normalization theorem for extended natural deduction
- A note on strong normalization in classical natural deduction
- Cut elimination and normalization for generalized single and multi-conclusion sequent and natural deduction calculi
- Peirce's rule in a full natural deduction system
- A note on how to extend Gentzen's second consistency proof to a proof of normalization for first order arithmetic
- Proof-theoretic semantics: an autobiographical survey
- A classical first-order normalization procedure with and based on the Milne-Kürbis approach
- Unified natural deduction for logics of strong negation
- Normalisation for negative free logics without and with definite descriptions
- Problems of a proof-theoretic characterization of paradoxes
- A semantical proof of the strong normalization theorem for full propositional classical natural deduction
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)