zbMATH — the first resource for mathematics

On normalization of proofs in set theory. (English) Zbl 0667.03041
The general framework of the various systems considered here is (inconsistent) naive set theory with \(\in\), \(=\) as atomic predicates and unrestricted comprehension expressed by forming terms \(\{\) \(x|\) A(x)\(\}\) and corresponding introduction and elimination rules for \(t\in \{x|\) A(x)\(\}\). Except other natural deduction rules (for \(\forall\), \(\to\), \(\perp\) in the classical case) there are substitution of equals \((=\)-elimination) and extensionality \((=\)-introduction). It turns out that (rather natural) conversion rules considered by the author do not allow complete normalization, one of the examples being the Russell’s paradox, i.e. the derivation of contradiction rom \(t\in t\), \(\sim t\in t\) for \(t=\{x|\) \(\sim x\in x\}\). This is extended to consistent theories such as ZF by taking \(t=\{x|\) \(x\in u\&\sim x\in x\}\) and deriving \(\sim t\in u\) from \(\sim t\in t\) and \(t\in u\to t\in t\). Nevertheless, partial normalization turns out to be possible assuring that derivation of a formula (without any assumptions) ends in an elimination rule. This is established by Girard’s method of computability predicates for (what the author calls) well-founded fragments N of naive set theory. They are determined by a restriction of the language (mainly of allowed comprehension terms) and the condition: there is no infinite chain \(...\in r_ 3\in r_ 2\in r_ 1\) with all \(r_{i+1}\in r_ i\) provable in N. Partial normalization is defined roughly speaking by the condition that only cuts immediately leading to formulas (without any assumptions) are to be eliminated. All developments are reproduced for intuitionistic systems. Examples of well-founded fragments are ZF and a semiformal system SET describing the cumulative hierarchy. The author uses his results to obtain usual consequences of normalization like E- theorems for intuitionistic systems.
Reviewer: G.Mints

03F05 Cut-elimination and normal-form theorems
03E99 Set theory