Propositions in Prepositional Logic Provable Only by Indirect Proofs (Q4379628)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1123539
Language Label Description Also known as
default for all languages
No label defined
    English
    Propositions in Prepositional Logic Provable Only by Indirect Proofs
    scientific article; zbMATH DE number 1123539

      Statements

      Propositions in Prepositional Logic Provable Only by Indirect Proofs (English)
      0 references
      0 references
      22 February 1999
      0 references
      natural deduction
      0 references
      normalization
      0 references
      comprehension
      0 references
      \textit{D. Prawitz} noticed [Natural deduction. A proof-theoretical study (1965; Zbl 0173.00205), p. 95] that normalization fails for ``naive'' set theory with the standard introduction and elimination rules for \(\in\): \[ \in I:\quad \Gamma \Rightarrow A[x/t]/ \Gamma \Rightarrow t\in \{x| A\}; \qquad \in E:\quad \Gamma \Rightarrow t\in \{x| A\}/ \Gamma \Rightarrow A[x/t] \] \textit{L. Hallnäs} developed this observation in his dissertation [``On normalization of proofs in set theory'', Diss. Math. 261 (1988; Zbl 0667.03041)]. The present paper brings this observation down to the propositional level (a similar observation was made by N. Tennant). By translating the ``naive'' comprehension axiom \(t\in t\leftrightarrow t\notin t\) (where \(t\equiv \{x| x\notin x\})\) by \(P\rightarrow \neg P\) it is shown that the intuitionistically deducible formula \(\neg(P \leftrightarrow \neg P)\) does not have a normal deduction \(d\) which is also ``extensively normal'': every subdeduction \(d'\) of \(d\) deriving a sequent \(\Gamma' \Rightarrow A\) contains no proper subdeduction \(d''\) of a sequent \(\Gamma'' \Rightarrow A\) with \(\Gamma'' \subseteq \Gamma'\). In particular normalization according to standard reductions plus reduction of \(d'\) to \(d''\) does not terminate. This observation is extended to classical logic and to a wider class of formulas. One of the corollaries: a provable propositional sequent having no extensively normal deduction has infinitely many different deductions.
      0 references

      Identifiers