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
22 February 1999
0 references
natural deduction
0 references
normalization
0 references
comprehension
0 references
0 references
0.7607995
0 references
0.7583345
0 references
0.75289834
0 references
0.7493683
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