New Foundations 945957 225407234 2008-07-13T14:53:20Z CRGreathouse 1077900 links In [[mathematical logic]], '''''New Foundations''''' ('''NF''') is an [[axiomatic set theory]], conceived by [[Willard Van Orman Quine]] as a simplification of the [[theory of types]] of ''[[Principia Mathematica]]''. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name. Much of this entry discusses '''NFU''', an important variant of NF due to Jensen (1969) and exposited in Holmes (1998). ==The type theory TST== The primitive predicates of [[Russellian unramified typed set theory|TST]], a streamlined version of the [[Type theory|theory of types]], are equality and membership. TST has a linear hierarchy of types: type 0 consists of individuals otherwise undescribed. For each (meta-) natural number ''n'', type ''n''+1 objects are sets of type ''n'' objects; sets of type ''n'' have members of type ''n''-1. Objects connected by identity must have the same type. The following two atomic formulas succinctly describe the typing rules: <math>x^{n} = y^{n}\!</math> and <math>x^{n} \in y^{n+1}</math> (notation to be improved). The axioms of TST are: *[[axiom of extensionality|Extensionality]]: sets of the same (positive) type with the same members are equal; *An axiom schema of [[axiom of separation|comprehension]], namely: :If <math>\phi(x^n)\!</math> is a [[well-formed formula|formula]], then the set <math>\{x^n \mid \phi(x^n)\}^{n+1}\!</math> exists. :In other words, given any formula <math>\phi(x^n)\!</math>, the formula <math>\exists A^{n+1} \forall x^n [x^n \in A^{n+1} \leftrightarrow \phi(x^n)]</math> is an axiom where <math>A^{n+1}\!</math> represents the set <math>\{x^n \mid \phi(x^n)\}^{n+1}\!</math>. This type theory is much less complicated than the one first set out in the ''[[Principia Mathematica]]'', which included types for [[relation]]s whose arguments were not necessarily all of the same type. In 1914, [[Norbert Wiener]] showed how to code the [[ordered pair]] as a set of sets, making it possible to eliminate relation types in favor of the linear hierarchy of sets described here. ==Quinian set theory== ===Axioms and stratification=== New Foundations (NF) is obtained from TST by abandoning the distinctions of type. The axioms of NF are: *[[Extensionality]]: Two objects with the same elements are the same object; *A [[axiom of separation|comprehension schema]]: All instances of TST ''Comprehension'' but with type indices dropped (and without introducing new identifications between variables). By convention, NF's ''[[axiom of separation|Comprehension]]'' schema is stated using the concept of [[stratified formula]] and making no direct reference to types. A formula <math>\phi</math> is said to be [[stratified formula|stratified]] if there exists a [[function (mathematics)|function]] ''f'' from pieces of syntax to the natural numbers, such that for any atomic subformula <math>x \in y</math> of <math>\phi</math> we have ''f''(''y'') = ''f''(''x'') + 1, while for any atomic subformula <math>x=y</math> of <math>\phi</math>, we have ''f''(''x'') = ''f''(''y''). ''Comprehension'' then becomes: :<math>\{x \mid \phi \}</math> exists for each [[stratified formula]] <math>\phi</math>. Even the indirect reference to types implicit in the notion of [[stratification (mathematics)|stratification]] can be eliminated. [[Theodore Hailperin]] showed in 1944 that ''Comprehension'' is equivalent to a finite conjunction of its instances,<ref>Hailperin, T. “A set of axioms for logic,” [[Journal of Symbolic Logic]] 9, pp. 1-19.</ref> so that NF can be finitely axiomatized without any reference to the notion of type. ''Comprehension'' may seem inconsistent with [[naive set theory]], but this is not the case. For example, the impossible [[Russell's paradox|Russell class]] <math>\{x \mid x \not\in x\}</math> is not an NF set, because <math> x \not\in x </math> cannot be stratified. === Ordered pairs === [[Relation]]s and [[function (mathematics)|functions]] are defined in TST (and in NF and NFU) as sets of [[ordered pair]]s in the usual way. The usual definition of the ordered pair, first proposed by [[Kuratowski]] in 1921, has a serious drawback for NF and related theories: the resulting ordered pair necessarily has a type two higher than the type of its arguments (its left and right [[projection]]s). Hence for purposes of determining stratification, a function is three types higher than the members of its field. If one can define a pair in such a way that its type is the same type as that of its arguments (resulting in a '''type-level''' ordered pair), then a relation or function is merely one type higher than the type of the members of its field. Hence NF and related theories usually employ [[Willard van Orman Quine|Quine]]'s set-theoretic definition of the ordered pair, which yields a type-level ordered pair. Holmes (1998) takes the ordered pair and its left and right [[projection]]s as primitive. Fortunately, whether the ordered pair is type-level by definition or by assumption (i.e., taken as primitive) usually does not matter. The existence of a type-level ordered pair implies ''Infinity'', and NFU + ''Infinity'' interprets NFU + "there is a type level ordered pair" (they are not quite the same theory, but the differences are inessential). Conversely, NFU + ''Infinity'' + ''Choice'' proves the existence of a type-level ordered pair. ===Admissibility of useful large sets=== NF (and NFU + ''Infinity'' + ''Choice'', described below and known consistent) allow the construction of two kinds of sets that [[ZFC]] and its proper extensions disallow because they are "too large" (some set theories admit these entities under the heading of [[proper class]]es): *''The [[universal set]] V''. Because <math>x=x</math> is a [[stratified formula]], the [[universal set]] ''V'' = {''x'' | ''x=x''} exists by ''Comprehension''. An immediate consequence is that all sets have [[complement]]s, and the entire set-theoretic universe under NF has a [[Boolean algebra (structure)|Boolean]] structure. *''Cardinal and ordinal numbers''. In NF (and TST), the set of all sets having ''n'' elements (the [[circular reasoning|circularity]] here is only apparent) exists. Hence [[Frege]]'s definition of the [[cardinal number]]s works in NF and NFU: a cardinal number is an [[equivalence class]] of sets under the [[relation]] of [[equinumerosity]]: the sets ''A'' and ''B'' are equinumerous if there exists a [[bijection]] between them, in which case we write <math>A \sim B</math>. Likewise, an [[ordinal number]] is an [[equivalence class]] of [[well-ordering|well-ordered]] sets under the relation of [[similarity (mathematics)|similarity]]. ==The consistency problem and related partial results== The outstanding problem with NF is that it is not known to be [[equiconsistency|relatively consistent]] to anything. NF disproves ''Choice'', and so proves ''Infinity'' (Specker, 1953). But it is also known ([[Ronald Jensen|Jensen]], 1969) that the minor(?) modification of allowing [[urelement]]s (objects lacking members which are distinct from the empty set and from one another) yields NFU, a theory that is consistent relative to [[Peano axioms|Peano arithmetic]], with and without added ''Infinity'' and ''Choice''. (NFU corresponds to a type theory TSTU, where positive types may contain urelements.) There are other consistent variants of NF. NFU is, roughly speaking, weaker than NF because in NF, the power set of the universe is the universe itself, while in NFU, the power set of the universe is strictly smaller than the universe (the power set of the universe contains only one empty set, while in NFU the universe is assumed to contain more than one distinct empty set). Specker has shown that NF is [[equiconsistency|equiconsistent]] with TST + ''Amb'', where ''Amb'' is the axiom scheme of <strong>typical ambiguity</strong> which asserts <math>\phi \leftrightarrow \phi^+</math> for any formula <math>\phi</math>, <math>\phi^+</math> being the formula obtained by raising every type index in <math>\phi</math> by one. NF is also equiconsistent with the theory TST augmented with a "type shifting automorphism", an operation which raises type by one, mapping each type onto the next higher type, and preserves equality and membership relations (and which cannot be used in instances of ''Comprehension'': it is external to the theory). The same results hold for various fragments of TST in relation to the corresponding fragments of NF. In the same year (1969) that [[Ronald Jensen|Jensen]] proved NFU consistent, Grishin proved <math>NF_3</math> consistent. <math>NF_3</math> is the fragment of NF with full extensionality (no urelements) and those instances of ''Comprehension'' which can be stratified using just three types. This theory is a very awkward medium for mathematics (although there have been attempts to alleviate this awkwardness), largely because there is no obvious definition for an [[ordered pair]]. Despite this awkwardness, <math>NF_3</math> is very interesting because ''every'' infinite model of TST restricted to three types satisfies ''Amb''. Hence for every such model there is a model of <math>NF_3</math> with the same theory. This does not hold for four types: <math>NF_4</math> is the same theory as NF, and we have no idea how to obtain a model of TST with four types in which ''Amb'' holds. In 1983, Marcel Crabbé proved consistent a system he called NFI, whose axioms are unrestricted extensionality and those instances of ''Comprehension'' in which no variable is assigned a type higher than that of the set asserted to exist. This is a [[impredicative|predicativity]] restriction, though NFI is not a predicative theory: it admits enough impredicativity to define the set of natural numbers (defined as the intersection of all inductive sets; note that the inductive sets quantified over are of the same type as the set of natural numbers being defined). Crabbé also discussed a subtheory of NFI, in which only parameters (free variables) are allowed to have the type of the set asserted to exist by an instance of ''Comprehension''. He called the result "predicative NF" (NFP); it is, of course, doubtful whether any theory with a self-membered universe is truly predicative. Holmes has <date?> shown that NFP has the same consistency strength as the predicative theory of types of ''[[Principia Mathematica]]'' without the Axiom of [[Reduction (complexity)|Reducibility]]. ==How NF(U) avoids the set-theoretic paradoxes== NF steers clear of the three well-known [[paradox]]es of [[set theory]]. That NFU, a {relatively} [[consistent]] theory, also avoid the paradoxes increases our confidence in this fact. The ''[[Russell paradox]]'': An easy matter; <math>x \not\in x</math> is not a stratified formula, so the existence of <math>\{x \mid x \not\in x\}</math> 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]] <math>P(A)</math> of any set <math>A</math> is larger than <math>A</math> (there can be no [[Injective function|injection]] (one-to-one map) from <math>P(A)</math> into <math>A</math>). Now of course there is an [[Injective function|injection]] from <math>P(V)</math> into <math>V</math>, if <math>V</math> is the universal set! The resolution requires that we observe that <math>|A| < |P(A)|</math> makes no sense in the theory of types: the type of <math>P(A)</math> is one higher than the type of <math>A</math>. 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 <math>|P_1(A)| < |P(A)|</math>, where <math>P_1(A)</math> is the set of one-element subsets of <math>A</math>. The specific instance of this theorem that interests us is <math>|P_1(V)| < |P(V)|</math>: 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]] <math>x \mapsto \{x\}</math> 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 <math>|P_1(V)| < |P(V)| << |V|</math>; ''Choice'' allows one not only to prove that there are urelements but that there are many cardinals between <math>|P(V)|</math> and <math>|V|</math>. We now introduce some useful notions. A set <math>A</math> which satisfies the intuitively appealing <math>|A| = |P_1(A)|</math> is said to be '''cantorian''': a cantorian set satisfies the usual form of [[Cantor's theorem]]. A set <math>A</math> which satisfies the further condition that <math>(x \mapsto \{x\})\lceil A</math>, the [[restriction]] of the [[singleton]] map to ''A'', 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 class]]es of [[well-ordering]]s under [[similarity]]. There is an obvious natural well-ordering on the [[ordinal]]s; since it is a well-ordering it belongs to an ordinal <math>\Omega</math>. It is straightforward to prove (by [[transfinite induction]]) that the order type of the natural order on the ordinals less than a given ordinal <math>\alpha</math> is <math>\alpha</math> itself. But this means that <math>\Omega</math> is the order type of the ordinals <math> < \Omega </math> and so is strictly less than the order type of all the ordinals -- but the latter is, by definition, <math>\Omega</math> 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 <math>\alpha</math> is of a higher type than <math>\alpha</math>. 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 <math>\alpha</math>, we can define an order type <math>\alpha</math> one type higher: if <math>W \in \alpha</math>, then <math>T(\alpha)</math> is the order type of the order <math>W^{\iota} = \{(\{x\},\{y\}) \mid xWy\}</math>. 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 <math> < \alpha</math> is <math>T^2(\alpha)</math> or <math>T^4(\alpha)</math> depending on which pair is used (we assume the type level pair hereinafter). From this we deduce that the order type on the ordinals <math> <\Omega </math> is <math>T^2(\Omega)</math>, from which we deduce <math>T^2(\Omega)<\Omega</math>. 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 <math>\Omega > T^2(\Omega) > T^4(\Omega)\ldots</math>, 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 [[Willard Van Orman Quine|Quine]]'s ''Mathematical Logic'' married NF to the [[proper class]]es of [[Von Neumann-Bernays-Godel set theory|NBG set theory]], and included an axiom schema of unrestricted comprehension for proper classes. In 1942, [[J. Barkley Rosser]] proved that Quine's set theory was subject to the Burali-Forti paradox. Rosser's proof does ''not'' go through for NF(U). In 1950, [[Hao Wang (academic)|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''. ==Models of NFU== There is a fairly simple method for producing models of NFU in bulk. Using well-known techniques of [[model theory]], one can construct a nonstandard model of [[Zermelo set theory]] (nothing nearly as strong as full ZFC is needed for the basic technique) on which there is an external automorphism ''j'' (not a set of the model) which moves a [[rank (set theory)|rank]] <math>V_{\alpha}</math> of the cumulative [[hierarchy]] of sets. We may suppose without loss of generality that <math>j(\alpha)<\alpha</math>. We talk about the [[automorphism]] moving the rank rather than the ordinal because we do not want to assume that every ordinal in the model is the index of a rank. The domain of the model of NFU will be the nonstandard rank <math>V_{\alpha}</math>. The membership relation of the model of NFU will be *<math>x \in_{NFU} y \equiv_{def} j(x) \in y \wedge y \in V_{j(\alpha)+1}.</math> We now prove that this actually is a model of NFU. Let <math>\phi</math> be a stratified formula in the language of NFU. Choose an assignment of types to all variables in the formula which witnesses the fact that it is stratified. Choose a natural number ''N'' greater than all types assigned to variables by this stratification. Expand the formula <math>\phi</math> into a formula <math>\phi_1</math> in the language of the nonstandard model of [[Zermelo set theory]] with [[automorphism]] ''j'' using the definition of membership in the model of NFU. Application of any power of ''j'' to both sides of an equation or membership statement preserves its truth value because ''j'' is an automorphism. Make such an application to each [[atomic formula]] in <math>\phi_1</math> in such a way that each variable ''x'' assigned type ''i'' occurs with exactly <math>N-i</math> applications of ''j''. This is possible thanks to the form of the atomic membership statements derived from NFU membership statements, and to the formula being stratified. Each quantified sentence <math>(\forall x \in V_{\alpha}.\psi(j^{N-i}(x)))</math> can be converted to the form <math>(\forall x \in j^{N-i}(V_{\alpha}).\psi(x))</math> (and similarly for [[existential quantifier]]s). Carry out this transformation everywhere and obtain a formula <math>\phi_2</math> in which ''j'' is never applied to a bound variable. Choose any free variable ''y'' in <math>\phi</math> assigned type ''i''. Apply <math>j^{i-N}</math> uniformly to the entire formula to obtain a formula <math>\phi_3</math> in which ''y'' appears without any application of ''j''. Now <math>\{y \in V_{\alpha} \mid \phi_3\}</math> exists (because ''j'' appears applied only to free variables and constants), belongs to <math>V_{\alpha+1}</math>, and contains exactly those ''y'' which satisfy the original formula <math>\phi</math> in the model of NFU. <math>j(\{y \in V_{\alpha} \mid \phi_3\})</math> has this extension in the model of NFU (the application of ''j'' corrects for the different definition of membership in the model of NFU). This establishes that ''Stratified Comprehension'' holds in the model of NFU. To see that weak ''Extensionality'' holds is straightforward: each nonempty element of <math>V_{j(\alpha)+1}</math> inherits a unique extension from the nonstandard model, the empty set inherits its usual extension as well, and all other objects are urelements. The basic idea is that the automorphism ''j'' codes the "power set" <math>V_{\alpha+1}</math> of our "universe" <math>V_{\alpha}</math> into its externally isomorphic copy <math>V_{j(\alpha)+1}</math> inside our "universe." The remaining objects not coding subsets of the universe are treated as [[urelement]]s. If <math>\alpha</math> is a natural number ''n'', we get a model of NFU which claims that the universe is finite (it is externally infinite, of course). If <math>\alpha</math> is infinite and the ''[[Axiom of Choice|Choice]]'' holds in the nonstandard model of ZFC, we obtain a model of NFU + ''Infinity'' + ''Choice''. === Self-sufficiency of mathematical foundations in NFU === For philosophical reasons, it is important to note that it is not necessary to work in [[ZFC]] or any related system to carry out this proof. A common argument against the use of NFU as a foundation for mathematics is that our reasons for relying on it have to do with our intuition that ZFC is correct. We claim that it is sufficient to accept TST (in fact TSTU). We outline the approach: take the type theory TSTU (allowing urelements in each positive type) as our metatheory and consider the theory of set models of TSTU in TSTU (these models will be sequences of sets <math>T_i</math> (all of the same type in the metatheory) with embeddings of each <math>P(T_i)</math> into <math>P_1(T_{i+1})</math> coding embeddings of the power set of <math>T_i</math> into <br><math>T_{i+1}</math> in a type-respecting manner). Given an embedding of <math>T_0</math> into <math>T_1</math> (identifying elements of the base "type" with subsets of the base type), one can define embeddings from each "type" into its successor in a natural way. This can be generalized to transfinite sequences <math>T_{\alpha}</math> with care. Note that the construction of such sequences of sets is limited by the size of the type in which they are being constructed; this prevents TSTU from proving its own consistency (TSTU + ''Infinity'' can prove the consistency of TSTU; to prove the consistency of TSTU+''Infinity'' one needs a type containing a set of cardinality <math>\beth_{\omega}</math>, which cannot be proved to exist in TSTU+''Infinity'' without stronger assumptions). Now the same results of model theory can be used to build a model of NFU and verify that it is a model of NFU in much the same way, with the <math>T_{\alpha}</math>'s being used in place of <math>V_{\alpha}</math> in the usual construction. The final move is to observe that since NFU is consistent, we can drop the use of absolute types in our metatheory, bootstrapping the metatheory from TSTU to NFU. === Facts about the [[automorphism]] ''j'' === The [[automorphism]] ''j'' of a model of this kind is closely related to certain natural operations in NFU. For example, if ''W'' is a [[well-ordering]] in the nonstandard model (we suppose here that we use [[ordered pair|Kuratowski pairs]] so that the coding of functions in the two theories will agree to some extent) which is also a well-ordering in NFU (all well-orderings of NFU are well-orderings in the nonstandard model of Zermelo set theory, but not vice versa, due to the formation of [[urelement]]s in the construction of the model), and ''W'' has type α in NFU, then ''j''(''W'') will be a well-ordering of type ''T''(α) in NFU. In fact, ''j'' is coded by a function in the model of NFU. The function in the nonstandard model which sends the singleton of any element of <math>V_{j(\alpha)}</math> to its sole element, becomes in NFU a function which sends each singleton {''x''}, where ''x'' is any object in the universe, to ''j''(''x''). Call this function ''Endo'' and let it have the following properties: ''Endo'' is an [[Injective function|injection]] from the set of singletons into the set of sets, with the property that ''Endo''( {''x''} ) = {''Endo''( {''y''} ) | ''y''∈''x''} for each set ''x''. This function can define a type level "membership" relation on the universe, one reproducing the membership relation of the original nonstandard model. ==Strong axioms of Infinity== In this section we mainly discuss the effect of adding various "strong axioms of infinity" to our usual base theory, NFU + ''Infinity'' + ''Choice''. This base theory, known consistent, has the same strength as TST + ''Infinity'', or Zermelo set theory with ''Separation'' restricted to bounded formulas (Mac Lane set theory). One can add to this base theory strong axioms of infinity familiar from the [[ZFC]] context, such as "there exits an inaccessible cardinal," but it is more natural to consider assertions about cantorian and strongly cantorian sets. Such assertions not only bring into being [[large cardinal]]s of the usual sorts, but strengthen the theory on its own terms. The weakest of the usual strong principles is: *'''Rosser's Axiom of Counting'''. The set of natural numbers is a strongly cantorian set. To see how natural numbers are defined in NFU, see [[set-theoretic definition of natural numbers]]. The original form of this axiom given by Rosser was "the set {''m''|1≤''m''≤''n''} has ''n'' members", for each natural number ''n''". This intuitively obvious assertion is unstratified: what is provable in NFU is "the set {''m''|1≤''m''≤''n''} has <math>T^2(n)</math> members" (where the ''T'' operation on cardinals is defined by <math>T(|A|) = |P_1(A)|</math>; this raises the type of a cardinal by one). For any cardinal number (including natural numbers) to assert <math>T(|A|) = |A|</math> is equivalent to asserting that the sets ''A'' of that cardinality are cantorian (by a usual abuse of language, we refer to such cardinals as "cantorian cardinals"). It is straightforward to show that the assertion that each natural number is cantorian is equivalent to the assertion that the set of all natural numbers is strongly cantorian. ''Counting'' is consistent with NFU, but increases its consistency strength noticeably; not, as one would expect, in the area of arithmetic, but in higher set theory. NFU + ''Infinity'' proves that each <math>\beth_n</math> exists, but not that <math>\beth_{\omega}</math> exists; NFU + ''Counting'' (easily) proves ''Infinity'', and further proves the existence of <math>\beth_{\beth_n}</math> for each n, but not the existence of <math>\beth_{\beth_{\omega}}</math>. (See [[beth number]]s). ''Counting'' implies immediately that one does not need to assign types to variables restricted to the set <math>N</math> of natural numbers for purposes of stratification; it is a theorem that the [[power set]] of a strongly cantorian set is strongly cantorian, so it is further not necessary to assign types to variables restricted to any iterated power set of the natural numbers, or to such familiar sets as the set of real numbers, the set of functions from reals to reals, and so forth. The set-theoretical strength of ''Counting'' is less important in practice than the convenience of not having to annotate variables known to have natural number values (or related kinds of values) with singleton brackets, or to apply the ''T'' operation in order to get stratified set definitions. ''Counting'' implies ''Infinity''; each of the axioms below needs to be adjoined to NFU + ''Infinity'' to get the effect of strong variants of ''Infinity''; [[Ali Enayat]] has investigated the strength of some of these axioms in models of NFU + "the universe is finite". A model of the kind constructed above satisfies ''Counting'' just in case the automorphism ''j'' fixes all natural numbers in the underlying nonstandard model of Zermelo set theory. The next strong axiom we consider is the *'''Axiom of strongly cantorian separation''': For any strongly cantorian set ''A'' and any formula <math>\phi</math> (not necessarily stratified!) the set {''x''∈''A''|φ} exists. Immediate consequences include Mathematical Induction for unstratified conditions (which is not a consequence of ''Counting''; many but not all unstratified instances of induction on the natural numbers follow from ''Counting''). This axiom is surprisingly strong. Unpublished work of [[Robert Solovay]] shows that the consistency strength of the theory NFU* = NFU + ''Counting'' + ''Strongly Cantorian Separation'' is the same as that of Zermelo set theory + <math>\Sigma_2</math> ''Replacement''. This axiom holds in a model of the kind constructed above (with ''Choice'') if the ordinals which are fixed by ''j'' and dominate only ordinals fixed by ''j'' in the underlying nonstandard model of Zermelo set theory are standard, and the power set of any such ordinal in the model is also standard. This condition is sufficient but not necessary. Next is *'''Axiom of Cantorian Sets''': Every cantorian set is strongly cantorian. This very simple and appealing assertion is extremely strong. Solovay has shown the precise equivalence of the consistency strength of the theory NFUA = NFU + ''Infinity'' + ''Cantorian Sets'' with that of ZFC + a schema asserting the existence of an ''n''-Mahlo cardinal for each concrete natural number ''n''. Ali Enayat has shown that the theory of cantorian equivalence classes of well-founded extensional relations (which gives a natural picture of an initial segment of the cumulative hierarchy of ZFC) interprets the extension of ZFC with ''n''-Mahlo cardinals directly. A permutation technique can be applied to a model of this theory to give a model in which the hereditarily strongly cantorian sets with the usual membership relation model the strong extension of ZFC. This axiom holds in a model of the kind constructed above (with ''Choice'') just in case the ordinals fixed by ''j'' in the underlying nonstandard model of [[ZFC]] are an initial (proper class) segment of the ordinals of the model. Next consider the *'''Axiom of Cantorian Separation''': For any cantorian set A and any formula <math>\phi</math> (not necessarily stratified!) the set {''x''∈''A''|φ} exists. This combines the effect of the two preceding axioms and is actually even stronger (precisely how is not known). Unstratified mathematical induction enables proving that there are ''n''-Mahlo cardinals for every ''n'', given ''Cantorian Sets'', which gives an extension of [[ZFC]] that is even stronger than the previous one, which only asserts that there are ''n''-Mahlos for each concrete natural number (leaving open the possibility of nonstandard counterexamples). This axiom will hold in a model of the kind described above if every ordinal fixed by ''j'' is standard, and every [[power set]] of an ordinal fixed by ''j'' is also standard in the underlying model of [[ZFC]]. Again, this condition is sufficient but not necessary. An ordinal is said to be ''cantorian'' if it is fixed by ''T'', and ''strongly cantorian'' if it dominates only cantorian ordinals (this implies that it is itself cantorian). In models of the kind constructed above, cantorian ordinals of NFU correspond to ordinals fixed by ''j'' (they are not the same objects because different definitions of ordinal numbers are used in the two theories). Equal in strength to ''Cantorian Sets'' is the *'''Axiom of Large Ordinals''': For each noncantorian ordinal <math>\alpha</math>, there is a natural number ''n'' such that <math>T^n(\Omega) < \alpha</math>. Recall that <math>\Omega</math> is the order type of the natural order on all ordinals. This only implies ''Cantorian Sets'' if we have ''Choice'' (but is at that level of consistency strength in any case). It is remarkable that one can even define <math>T^n(\Omega)</math>: this is the ''n''th term <math>s_n</math> of any finite sequence of ordinals ''s'' of length ''n'' such that <math>s_0 = \Omega</math>, <math>s_{i+1} = T(s_i)</math> for each appropriate ''i''. This definition is completely unstratified. The uniqueness of <math>T^n(\Omega)</math> can be proved (for those ''n'' for which it exists) and a certain amount of common-sense reasoning about this notion can be carried out, enough to show that ''Large Ordinals'' implies ''Cantorian Sets'' in the presence of ''Choice''. In spite of the knotty formal statement of this axiom, it is a very natural assumption, amounting to making the action of ''T'' on the ordinals as simple as possible. A model of the kind constructed above will satisfy ''Large Ordinals'', if the ordinals moved by ''j'' are exactly the ordinals which dominate some <math>j^{-i}(\alpha)</math> in the underlying nonstandard model of [[ZFC]]. *'''Axiom of Small Ordinals''': For any formula φ, there is a set ''A'' such that the elements of ''A'' which are strongly Cantorian ordinals are exactly the strongly cantorian ordinals such that φ. Solovay has shown the precise equivalence in consistency strength of NFUB = NFU + ''Infinity'' + ''Cantorian Sets'' + ''Small Ordinals'' with [[Morse–Kelley set theory]] plus the assertion that the proper class ordinal (the class of all ordinals) is a [[weakly compact cardinal]]. This is very strong indeed! Moreover, NFUB-, which is NFUB with ''Cantorian Sets'' omitted, is easily seen to have the same strength as NFUB. A model of the kind constructed above will satisfy this axiom if every collection of ordinals fixed by ''j'' is the intersection of some set of ordinals with the ordinals fixed by ''j'', in the underlying nonstandard model of ZFC. Even stronger is the theory NFUM = NFU + ''Infinity'' + ''Large Ordinals'' + ''Small Ordinals''. This is equivalent to [[Morse–Kelley set theory]] with a predicate on the classes which is a κ-complete nonprincipal [[ultrafilter]] on the proper class ordinal κ; in effect, this is Morse–Kelley set theory + "the proper class ordinal is a [[measurable cardinal]]"! The technical details here are not the main point, which is that reasonable and natural (in the context of NFU) assertions turn out to be equivalent in power to very strong axioms of infinity in the [[ZFC]] context. This fact is related to the correlation between the existence of models of NFU, described above and satisfying these axioms, and the existence of models of [[ZFC]] with [[automorphism]]s having special properties. ==See also== *[[Alternative set theory]] *[[Axiomatic set theory]] *[[Implementation of mathematics in set theory]] *[[Positive set theory]] *[[Set-theoretic definition of natural numbers]] *[[Universal set]] == References == {{Reflist}} *Crabb&eacute; , Marcel, 1982, On the consistency of an impredicative fragment of Quine's NF, ''The Journal of Symbolic Logic 47'': 131-136. *Holmes , Randall, 1998. ''[http://math.boisestate.edu/~holmes/holmes/head.pdf Elementary Set Theory with a Universal Set]''. Academia-Bruylant. The publisher has graciously consented to permit diffusion of this introduction to NFU via the web. Copyright is reserved. *[[Ronald Jensen|Jensen, R. B.,]] 1969, "On the Consistency of a Slight(?) Modification of Quine's NF," ''Synthese 19'': 250-63. With discussion by Quine. *[[Willard Quine|Quine, W. V.,]] 1980, "New Foundations for Mathematical Logic" in ''From a Logical Point of View'', 2nd ed., revised. Harvard Univ. Press: 80-101. The definitive version of where it all began, namely Quine's 1937 paper in the ''American Mathematical Monthly''. == External links == * [[Stanford Encyclopedia of Philosophy]]: ** [http://plato.stanford.edu/entries/quine-nf Quine's New Foundations] -- by Thomas Forster. ** [http://setis.library.usyd.edu.au/stanford/entries/settheory-alternative/ Alternative axiomatic set theories] -- by Randall Holmes. * Randall Holmes: [http://math.boisestate.edu/~holmes/holmes/nf.html New Foundations Home Page.] *Randall Holmes: [http://math.boisestate.edu/~holmes/holmes/setbiblio.html Bibliography of Set Theory with a Universal Set.] [[Category:Mathematical logic]] [[Category:Systems of set theory]] [[Category:Urelements]] [[hu:New Foundations]] [[zh:新基础集合论]]