Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T16:14:28.729Z Has data issue: false hasContentIssue false

Stratification and cut-elimination

Published online by Cambridge University Press:  12 March 2014

Marcel Crabbé*
Affiliation:
Département de Philosophie, Université de Louvain, B-1348 Louvain-la-Neuve, Belgium

Extract

In this paper, we show the normalization of proofs of NF (Quine's New Foundations; see [15]) minus extensionality. This system, called SF (Stratified Foundations) differs in many respects from the associated system of simple type theory. It is written in a first order language and not in a multi-sorted one, and the formulas need not be stratifiable, except in the instances of the comprehension scheme. There is a universal set, but, for a similar reason as in type theory, the paradoxical sets cannot be formed.

It is not immediately apparent, however, that SF is essentially richer than type theory. But it follows from Specker's celebrated result (see [16] and [4]) that the stratifiable formula (extensionality → the universe is not well-orderable) is a theorem of SF.

It is known (see [11]) that this set theory is consistent, though the consistency of NF is still an open problem.

The connections between consistency and cut-elimination are rather loose. Cut-elimination generally implies consistency. But the converse is not true. In the case of set theory, for example, ZF-like systems, though consistent, cannot be freed of cuts because the separation axioms allow the formation of sets from unstratifiable formulas. There are nevertheless interesting partial results obtained when restrictions are imposed on the removable cuts (see [1] and [9]). The systems with stratifiable comprehension are the only known set-theoretic systems that enjoy full cut-elimination.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable