Thomas Forster

The phrase ‘The iterative conception of sets’ conjures up a picture of a particular settheoretic universe – the cumulative hierarchy – and the constant conjunction of phrasewith-picture is so reliable that people tend to think that the cumulative hierarchy is all there is to the iterative conception of sets: if you conceive sets iteratively, then the result is the cumulative hierarchy. In this paper, I shall be arguing that this is a mistake: the iterative conception of set is a good one, for all the usual reasons. However, the cumulative hierarchy is merely one way among many of working out this conception, and arguments in favour of an iterative conception have been mistaken for arguments in favour of this one special instance of it. (This may be the point to get out of the way the observation that although philosophers of mathematics write of the iterative conception of set, what they really mean – in the terminology of modern computer science at least – is the recursive conception of sets. Nevertheless, having got that quibble off my chest, I shall continue to write of the iterative conception like everyone else.).

In general little thought is given to the general question of how to implement mathematical objects in set theory. It is clear that—at various times in the past—people have gone to considerable lengths to devise implementations with nice properties. There is a litera- ture on the evolution of the Wiener-Kuratowski ordered pair, and a discussion by Quine of the merits of an ordered-pair implemen- tation that makes every set an ordered pair. The implementation of ordinals as Von Neumann ordinals is so attractive that it is uni- versally used in all set theories which have enough replacement to prove Mostowski’s collapse lemma. I have frequently complained in the past about the widespread habit of referring to implementations of pairs (ordinals etc) as definitions of pairs (etc). My point here is a different one: generally little attention has been paid to the question of what makes an implementation a good implementation. In most cases of interest the merits of the candidates are uncontroversial. What I want to examine here is an example where there are com- peting implementations for ordered pairs, and—although it is clear to the cognoscenti and also (with a bit of arm-waving) plausible to the logician in the street that some of the impossible candidates are impossible, nobody has ever given a satisfactory explanation of why this is so

We identify complete fragments of the simple theory of types with infinity and Quine’s new foundations set theory. We show that TSTI decides every sentence ϕ in the language of type theory that is in one of the following forms: ϕ=∀x1r1⋯∀xkrk∃y1s1⋯∃ylslθ where the superscripts denote the types of the variables, s1>⋯>sl, and θ is quantifier-free, ϕ=∀x1r1⋯∀xkrk∃y1s⋯∃ylsθ where the superscripts denote the types of the variables and θ is quantifier-free. This shows that NF decides every stratified sentence ϕ in the language of set theory that is in one of the following forms: ϕ=∀x1⋯∀xk∃y1⋯∃ylθ where θ is quantifier-free and ϕ admits a stratification that assigns distinct values to all of the variables y1,…,yl, ϕ=∀x1⋯∀xk∃y1⋯∃ylθ where θ is quantifier-free and ϕ admits a stratification that assigns the same value to all of the variables y1,…,yl.

Many mathematical objects arise from equivalence classes and invite implementation as those classes. Set-existence principles that would enable this are incompatible with ZFC's unrestricted aussonderung but there are set theories which admit more instances than does ZF. NF provides equivalence classes for stratified relations only. Church's construction provides equivalence classes for “low” sets, and thus, for example, a set of all ordinals. However, that set has an ordinal in turn which is not a member of the set constructed; so no set of all ordinals is obtained thereby. This “recurrence problem” is discussed

Many mathematical objects arise from equivalence classes and invite implementation as those classes. Set-existence principles that would enable this are incompatible with ZFC's unrestricted _aussonderung_ but there are set theories which admit more instances than does ZF. NF provides equivalence classes for stratified relations only. Church's construction provides equivalence classes for "low" sets, and thus, for example, a set of all ordinals. However, that set has an ordinal in turn which is not a member of the set constructed; so no set of _all_ ordinals is obtained thereby. This "recurrence problem" is discussed.