New Foundations - How NF(U) Avoids The Set-theoretic Paradoxes

How NF(U) Avoids The Set-theoretic Paradoxes

NF steers clear of the three well-known paradoxes of set theory. That NFU, a (relatively) consistent theory, also avoids the paradoxes increases our confidence in this fact.

The Russell paradox: An easy matter; is not a stratified formula, so the existence of is not asserted by any instance of Comprehension. Quine presumably constructed NF with this paradox uppermost in mind.

Cantor's paradox of the largest cardinal number exploits the application of Cantor's theorem to the universal set. Cantor's theorem says (given ZFC) that the power set of any set is larger than (there can be no injection (one-to-one map) from into ). Now of course there is an injection from into, if is the universal set! The resolution requires that we observe that makes no sense in the theory of types: the type of is one higher than the type of . The correctly typed version (which is a theorem in the theory of types for essentially the same reasons that the original form of Cantor's theorem works in ZF) is, where is the set of one-element subsets of . The specific instance of this theorem that interests us is : there are fewer one-element sets than sets (and so fewer one-element sets than general objects, if we are in NFU). The "obvious" bijection from the universe to the one-element sets is not a set; it is not a set because its definition is unstratified. Note that in all known models of NFU it is the case that ; Choice allows one not only to prove that there are urelements but that there are many cardinals between and .

We now introduce some useful notions. A set which satisfies the intuitively appealing is said to be cantorian: a cantorian set satisfies the usual form of Cantor's theorem. A set which satisfies the further condition that, the restriction of the singleton map to A, is a set is not only cantorian set but strongly cantorian.

The Burali-Forti paradox of the largest ordinal number goes as follows. We define (following naive set theory) the ordinals as equivalence classes of well-orderings under similarity. There is an obvious natural well-ordering on the ordinals; since it is a well-ordering it belongs to an ordinal . It is straightforward to prove (by transfinite induction) that the order type of the natural order on the ordinals less than a given ordinal is itself. But this means that is the order type of the ordinals and so is strictly less than the order type of all the ordinals — but the latter is, by definition, itself!

The solution to the paradox in NF(U) starts with the observation that the order type of the natural order on the ordinals less than is of a higher type than . Hence a type level ordered pair is two, and the usual Kuratowski ordered pair, four, types higher than the type of its arguments. For any order type, we can define an order type one type higher: if, then is the order type of the order . The triviality of the T operation is only a seeming one; it is easy to show that T is a strictly monotone (order preserving) operation on the ordinals.

We can now restate the lemma on order types in a stratified manner: the order type of the natural order on the ordinals is or depending on which pair is used (we assume the type level pair hereinafter). From this we deduce that the order type on the ordinals is, from which we deduce . Hence the T operation is not a function; we cannot have a strictly monotone set map from ordinals to ordinals which sends an ordinal downward! Since T is monotone, we have, a "descending sequence" in the ordinals which cannot be a set.

Some have asserted that this result shows that no model of NF(U) is "standard", since the ordinals in any model of NFU are externally not well-ordered. We do not take a position on this, but we note that it is also a theorem of NFU that any set model of NFU has non-well-ordered "ordinals"; NFU does not conclude that the universe V is a model of NFU, despite V being a set, because the membership relation is not a set relation.

For a further development of mathematics in NFU, with a comparison to the development of the same in ZFC, see implementation of mathematics in set theory.

The set theory of the 1940 first edition of Quine's Mathematical Logic married NF to the proper classes of NBG set theory, and included an axiom schema of unrestricted comprehension for proper classes. In 1942, J. Barkley Rosser proved that the system presented in Mathematical Logic was subject to the Burali-Forti paradox. This result does not apply to NF. In 1950, Hao Wang showed how to amend Quine's axioms so as to avoid this problem, and Quine included the resulting axiomatization in the 1951 second and final edition of Mathematical Logic.