New Foundations
   HOME

TheInfoList



OR:

In
mathematical logic Mathematical logic is the study of formal logic within mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantiti ...
, New Foundations (NF) is an
axiomatic set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics Mathematic ...
, conceived by
Willard Van Orman Quine Willard Van Orman Quine (; known to his friends as "Van"; June 25, 1908 – December 25, 2000) was an American philosopher and logician in the analytic philosophy, analytic tradition, recognized as "one of the most influential philosophers of the ...
as a simplification of the theory of types of ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
''. 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 clarified by Holmes (1998). In 1940 and in a revision in 1951, Quine introduced an extension of NF sometimes called "Mathematical Logic" or "ML", that included proper classes as well as sets. New Foundations has a
universal set In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
, so it is a
non-well-founded set theory Non-well-founded set theories are variants of axiomatic set theory that allow sets to be elements of themselves and otherwise violate the rule of well-foundedness. In non-well-founded set theories, the axiom of regularity, foundation axiom of ZFC i ...
. That is to say, it is an axiomatic set theory that allows infinite descending chains of membership, such as …  xn ∈ xn-1 ∈ … ∈ x2 ∈ x1. It avoids
Russell's paradox In mathematical logic Mathematical logic is the study of formal logic within mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are ...
by permitting only stratifiable
formula In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the terminology, term ''formula'' in science refers to the Commensurability (philosophy o ...
s to be defined using the axiom schema of comprehension. For instance, x ∈ y is a stratifiable formula, but x ∈ x is not.


The Type Theory TST

The primitive predicates of Russellian unramified typed set theory (TST), a streamlined version of the theory of types, are equality (=) and
membership Member may refer to: * Military jury, referred to as "Members" in military jargon * Element (mathematics), an object that belongs to a mathematical set * In object-oriented programming, a member of a class ** Field (computer science), entries in ...
(\in). TST has a linear hierarchy of types: type 0 consists of individuals otherwise undescribed. For each (meta-)
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
''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: x^ = y^\! and x^ \in y^. (Quinean set theory seeks to eliminate the need for such superscripts to denote types.) The axioms of TST are: *
Extensionality In logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science inves ...
: sets of the same (positive) type with the same members are equal; * An axiom schema of comprehension, namely: ::If \phi(x^n)is a formula, then the set \^\! exists. :In other words, given any formula \phi(x^n)\!, the formula \exists A^ \forall x^n x^n \in A^ \leftrightarrow \phi(x^n) /math> is an axiom where A^\! represents the set \^\! and is not
free Free may refer to: Concept * Freedom, having the ability to do something, without having to obey anyone/anything * Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism * Emancipate, to procure ...
in \phi(x^n). This type theory is much less complicated than the one first set out in the ''Principia Mathematica'', which included types for relations whose arguments were not necessarily all of the same types. In 1914,
Norbert Wiener Norbert Wiener (November 26, 1894 – March 18, 1964) was an American mathematician and philosopher. He was a professor of mathematics at the Massachusetts Institute of Technology (MIT). A child prodigy, Wiener later became an early researcher i ...
showed how to code the
ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
as a set of sets, making it possible to eliminate relation types in favor of the linear hierarchy of sets described here.


Quinean set theory


Axioms and stratification

The well-formed formulas of New Foundations (NF) are the same as the well-formed formulas of TST, but with the type annotations erased. The axioms of NF are: *
Extensionality In logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science inves ...
: Two objects with the same elements are the same object; * A comprehension schema: All instances of TST ''Comprehension'' but with type, indices dropped (and without introducing new identifications between variables). By convention, NF's '' Comprehension'' schema is stated using the concept of stratified formula and making no direct reference to types. A formula \phi is said to be stratified if there exists a function ''f'' from pieces of \phi's syntax to the natural numbers, such that for any atomic subformula x \in y of \phi we have ''f''(''y'') = ''f''(''x'') + 1, while for any atomic subformula x=y of \phi, we have ''f''(''x'') = ''f''(''y''). ''Comprehension'' then becomes: :\ exists for each stratified formula \phi. Even the indirect reference to types implicit in the notion of stratification can be eliminated. Theodore Hailperin showed in 1944 that ''Comprehension'' is equivalent to a finite conjunction of its instances, so that NF can be finitely axiomatized without any reference to the notion of type. ''Comprehension'' may seem to run afoul of problems similar to those in
naive set theory Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language ...
, but this is not the case. For example, the existence of the impossible Russell class \ is not an axiom of NF, because x \not\in x cannot be stratified.


Ordered pairs

Relations and functions are defined in TST (and in NF and NFU) as sets of
ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
s in the usual way. The usual definition of the ordered pair, first proposed by
Kuratowski Kazimierz Kuratowski (; 2 February 1896 – 18 June 1980) was a Poles, Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics. Biography and studies Kazimierz Kuratowski was born in Wars ...
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 (it is left and right projections). 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 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 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 projections 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 Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol . Since the time of the Greek mathematics, ancient Greeks, the Infinity (philosophy), philosophical nature of infinit ...
'', 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 Proper may refer to: Mathematics * Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact * Proper morphism, in algebraic geometry, an analogue of a proper map for ...
es): * ''The
universal set In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
V''. Because x=x is a stratified formula, the
universal set In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
''V'' = exists by ''Comprehension''. An immediate consequence is that all sets have complements, and the entire set-theoretic universe under NF has a Boolean structure. * ''
Cardinal Cardinal or The Cardinal may refer to: Animals * Cardinal (bird) or Cardinalidae, a family of North and South American birds **''Cardinalis'', genus of cardinal in the family Cardinalidae **''Cardinalis cardinalis'', or northern cardinal, the ...
and ordinal numbers''. In NF (and TST), the set of all sets having ''n'' elements (the circularity here is only apparent) exists. Hence
Frege Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher A philosopher is a person who practices or investigates philosophy Philosophy (from , ) is the systematized study of general and fundam ...
's definition of the cardinal numbers works in NF and NFU: a cardinal number is an
equivalence class In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
of sets under the relation of equinumerosity: the sets ''A'' and ''B'' are equinumerous if there exists a
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function (mathematics), function between the elements of two set (mathematics), sets, where each element of one set is pair ...
between them, in which case we write A \sim B. Likewise, an ordinal number is an
equivalence class In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
of well-ordered sets.


Finite axiomatizability

New Foundations can be finitely axiomatized.


Cartesian closure

The category whose objects are the sets of NF and whose arrows are the functions between those sets is not Cartesian closed; Since NF lacks Cartesian closure, not every function
curries A curry is a dish with a sauce seasoned with spices, mainly associated with South Asian cuisine. In South India, southern India, leaves from the curry tree may be included. There are many varieties of curry. The choice of spices for each di ...
as one might intuitively expect, and NF is not a
topos In mathematics, a topos (, ; plural topoi or , or toposes) is a category (mathematics), category that behaves like the category of Sheaf (mathematics), sheaves of Set (mathematics), sets on a topological space (or more generally: on a Site (math ...
.


The consistency problem and related partial results

For many years, the great problem with NF has been that it has not conclusively been proved to be relatively consistent with any other well-known axiomatic system in which arithmetic can be modeled. NF disproves
Choice A choice is the range of different things from which a being can choose. The arrival at a choice may incorporate Motivation, motivators and Choice modelling, models. For example, a traveler might choose a route for a journey based on the pref ...
, and thus proves
Infinity Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol . Since the time of the Greek mathematics, ancient Greeks, the Infinity (philosophy), philosophical nature of infinit ...
(Specker, 1953). But it is also known ( Jensen, 1969) that allowing
urelement In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
s (multiple distinct objects lacking members) yields NFU, a theory that is consistent relative to
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian people, Italian mathematician Giuseppe Peano. These axioms have be ...
; if Infinity and Choice are added, the resulting theory has the same consistency strength as type theory with infinity or bounded Zermelo set theory. (NFU corresponds to a type theory TSTU, where type 0 has urelements, not just a single empty set.) There are other relatively 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 may be strictly smaller than the universe (the power set of the universe contains only sets, while the universe may contain urelements). This is necessarily the case in NFU+"Choice".
Ernst Specker Ernst Paul Specker (11 February 1920, Zurich – 10 December 2011, Zurich) was a Swiss mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathemat ...
has shown that NF is equiconsistent with TST + ''Amb'', where ''Amb'' is the axiom scheme of typical ambiguity which asserts \phi \leftrightarrow \phi^+ for any formula \phi, \phi^+ being the formula obtained by raising every type index in \phi 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 about the corresponding fragments of NF. In the same year (1969) that Jensen proved NFU consistent, Grishin proved NF_3 consistent. NF_3 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 In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
. Despite this awkwardness, NF_3 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 NF_3 with the same theory. This does not hold for four types: NF_4 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
predicativity In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mo ...
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 is defined). Crabbé also discussed a sub theory of NFI, in which only parameters (
free variables In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
) 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 predictive. Does Holmes have shown that NFP has the same consistency strength as the predicative theory of types of ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
'' without the
Axiom of reducibility The axiom of reducibility was introduced by Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerab ...
. Since 2015, several candidate proofs by Randall Holmes of the consistency of NF relative to ZF have been available both on
arXiv arXiv (pronounced "archive"—the X represents the Chi (letter), Greek letter chi ⟨χ⟩) is an open-access repository of electronic preprints and postprints (known as e-prints) approved for posting after moderation, but not Scholarly peer re ...
and on the logician's home page. Holmes demonstrates the equiconsistency of a 'weird' variant of TST, namely TTTλ - 'tangled type theory with λ-types' - with NF. Holmes next shows that TTTλ is consistent relative to ZFA, that is, ZF with atoms but without choice. Holmes demonstrates this by constructing in ZFA+C, that is, ZF with atoms and choice, a class model of ZFA which includes 'tangled webs of cardinals'. The candidate proofs are all rather long, but no irrecoverable faults have been identified by the NF community as yet.


How NF(U) avoids the set-theoretic paradoxes

NF steers clear of the three well-known
paradox A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...
es of
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, ...
. That NFU, a
consistent In classical deductive logic, a consistent theory A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such proc ...
(relative to Peano arithmetic) theory, also avoids the paradoxes may increase one's confidence in this fact. ''
Russell's paradox In mathematical logic Mathematical logic is the study of formal logic within mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are ...
'': x \not\in x is not a stratified formula, so the existence of \ is not asserted by any instance of ''Comprehension''. Quine said that he constructed NF with this paradox uppermost in mind. ''
Cantor's paradox In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
'' of the largest
cardinal number In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented ...
exploits the application of
Cantor's theorem In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any Set (mathematics), set A, the set of all subsets of A, the power set of A, has a strictly greater cardinality than A itself. For finite sets, Cant ...
to the
universal set In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
.
Cantor's theorem In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any Set (mathematics), set A, the set of all subsets of A, the power set of A, has a strictly greater cardinality than A itself. For finite sets, Cant ...
says (given ZFC) that the
power set In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
P(A) of any set A is larger than A (there can be no
injection Injection or injected may refer to: Science and technology * Injective function In mathematics, an injective function (also known as injection, or one-to-one function) is a function (mathematics), function that maps Distinct (mathematics), d ...
(one-to-one map) from P(A) into A). Now of course there is an
injection Injection or injected may refer to: Science and technology * Injective function In mathematics, an injective function (also known as injection, or one-to-one function) is a function (mathematics), function that maps Distinct (mathematics), d ...
from P(V) into V, if V is the universal set! The resolution requires that one observes that , A, < , P(A), makes no sense in the theory of types: the type of P(A) is one higher than the type of A. 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 In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any Set (mathematics), set A, the set of all subsets of A, the power set of A, has a strictly greater cardinality than A itself. For finite sets, Cant ...
works in ZF) is , P_1(A), < , P(A), , where P_1(A) is the set of one-element subsets of A. The specific instance of this theorem of interest is , P_1(V), < , P(V), : 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 In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function (mathematics), function between the elements of two set (mathematics), sets, where each element of one set is pair ...
x \mapsto \ 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 , P_1(V), < , P(V), << , V, ; ''Choice'' allows one not only to prove that there are urelements but that there are many cardinals between , P(V), and , V, . One can now introduce some useful notions. A set A which satisfies the intuitively appealing , A, = , P_1(A), is said to be Cantorian: a Cantorian set satisfies the usual form of
Cantor's theorem In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any Set (mathematics), set A, the set of all subsets of A, the power set of A, has a strictly greater cardinality than A itself. For finite sets, Cant ...
. A set A which satisfies the further condition that (x \mapsto \)\lceil A, the restriction of the
singleton Singleton may refer to: Sciences, technology Mathematics * Singleton (mathematics) In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which t ...
map to ''A'', is a set is not only Cantorian set but strongly Cantorian. The ''
Burali-Forti paradox In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
'' of the largest
ordinal number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the least n ...
goes as follows. Define (following
naive set theory Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language ...
) the ordinals as
equivalence class In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
es of
well-ordering In mathematics, a well-order (or well-ordering or well-order relation) on a Set (mathematics), set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together ...
s under
isomorphism In mathematics, an isomorphism is a structure-preserving Map (mathematics), mapping between two Mathematical structure, structures of the same type that can be reversed by an inverse function, inverse mapping. Two mathematical structures are iso ...
. There is an obvious natural well-ordering on the ordinals; since it is a well-ordering it belongs to an ordinal \Omega. It is straightforward to prove (by
transfinite induction Transfinite induction is an extension of mathematical induction to well-order, well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of Zermelo–Fraenkel set theory, ZFC. Induction by cases ...
) that the order type of the natural order on the ordinals less than a given ordinal \alpha is \alpha itself. But this means that \Omega is the order type of the ordinals < \Omega and so is strictly less than the order type of all the ordinals — but the latter is, by definition, \Omega 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 \alpha is of a higher type than \alpha. Hence a type level
ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
is two types higher than the type of its arguments and the usual Kuratowski ordered pair four types higher. For any order type \alpha, we can define an order type \alpha one type higher: if W \in \alpha, then T(\alpha) is the order type of the order W^ = \. 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. Now the lemma on order types may be restated in a stratified manner: the order type of the natural order on the ordinals < \alpha is T^2(\alpha) or T^4(\alpha) depending on which pair is used (we assume the type level pair hereinafter). From this one may deduce that the order type on the ordinals <\Omega is T^2(\Omega), and thus T^2(\Omega)<\Omega. Hence the T operation is not a function; there cannot be a strictly monotone set map from ordinals to ordinals which sends an ordinal downward! Since T is monotone, we have \Omega > T^2(\Omega) > T^4(\Omega)\ldots, a "descending sequence" in the ordinals which cannot be a set. One might assert 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. One need not take a position on this, but can 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 system ML (Mathematical Logic)

ML is an extension of NF that includes proper classes as well as sets. The set theory of the 1940 first edition of Quine's ''Mathematical Logic'' married NF to the
proper class Proper may refer to: Mathematics * Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact * Proper morphism, in algebraic geometry, an analogue of a proper map for ...
es of NBG set theory and included an axiom schema of unrestricted comprehension for proper classes. However proved that the system presented in ''Mathematical Logic'' was subject to the Burali-Forti paradox. This result does not apply to NF. showed how to amend Quine's axioms for ML so as to avoid this problem, and Quine included the resulting axiomatization in the 1951 second and final edition of ''Mathematical Logic''. Wang proved that if NF is consistent then so is the revised ML, and also showed that the consistency of the revised ML implies the consistency of NF. That is, NF and the revised ML are equiconsistent.


Models of NFU

Where the starting point for the
metamathematics Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheory, metatheories, which are Mathematical theory, mathematical theories about other mathematical theories. Emphasis on metamathematics (and ...
of Zermelo-Fraenkel set theory is the easy-to-formalize intuition of the cumulative hierarchy, the non-well-foundedness of NF and NFU makes this intuition not directly applicable. However, the intuition of forming sets at a stage from sets developed at earlier stages can be augmented to allow forming sets at a stage consisting of all possible sets but given sets formed at earlier stages, giving an analogous iterative conception of set.Forster (2008). There is a fairly simple method for producing models of NFU in bulk. Using well-known techniques of
model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (math ...
, one can construct a nonstandard model of
Zermelo set theory Zermelo set theory (sometimes denoted by Z-), as set out in a seminal paper in 1908 by Ernst Zermelo, is the ancestor of modern Zermelo–Fraenkel set theory (ZF) and its extensions, such as von Neumann–Bernays–Gödel set theory (NBG). It be ...
(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 Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * H ...
V_ of the cumulative
hierarchy A hierarchy (from Greek: , from , 'president of sacred rites') is an arrangement of items (objects, names, values, categories, etc.) that are represented as being "above", "below", or "at the same level as" one another. Hierarchy is an important ...
of sets. We may suppose without loss of generality that j(\alpha)<\alpha. We talk about the
automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of map (mathematics), mapping the object to itself while preserving all of its structure. The Set (m ...
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 V_. The membership relation of the model of NFU will be * x \in_ y \equiv_ j(x) \in y \wedge y \in V_. It may now be proved that this actually is a model of NFU. Let \phi 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 \phi into a formula \phi_1 in the language of the nonstandard model of
Zermelo set theory Zermelo set theory (sometimes denoted by Z-), as set out in a seminal paper in 1908 by Ernst Zermelo, is the ancestor of modern Zermelo–Fraenkel set theory (ZF) and its extensions, such as von Neumann–Bernays–Gödel set theory (NBG). It be ...
with
automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of map (mathematics), mapping the object to itself while preserving all of its structure. The Set (m ...
''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 In logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science in ...
because ''j'' is an automorphism. Make such an application to each
atomic formula In mathematical logic, an atomic formula (also known as an atom or a prime formula) is a formula (mathematical logic), formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formul ...
in \phi_1 in such a way that each variable ''x'' assigned type ''i'' occurs with exactly N-i 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 (\forall x \in V_.\psi(j^(x))) can be converted to the form (\forall x \in j^(V_).\psi(x)) (and similarly for
existential quantifier In predicate logic, an existential quantification is a type of Quantifier (logic), quantifier, a logical constant which is interpretation (logic), interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by t ...
s). Carry out this transformation everywhere and obtain a formula \phi_2 in which ''j'' is never applied to a bound variable. Choose any free variable ''y'' in \phi assigned type ''i''. Apply j^ uniformly to the entire formula to obtain a formula \phi_3 in which ''y'' appears without any application of ''j''. Now \ exists (because ''j'' appears applied only to free variables and constants), belongs to V_, and contains exactly those ''y'' which satisfy the original formula \phi in the model of NFU. j(\) 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 V_ 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" V_ of our "universe" V_ into its externally isomorphic copy V_ inside our "universe." The remaining objects not coding subsets of the universe are treated as
urelement In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
s. If \alpha is a natural number ''n'', one gets a model of NFU which claims that the universe is finite (it is externally infinite, of course). If \alpha is infinite and the ''
Choice A choice is the range of different things from which a being can choose. The arrival at a choice may incorporate Motivation, motivators and Choice modelling, models. For example, a traveler might choose a route for a journey based on the pref ...
'' holds in the nonstandard model of ZFC, one obtains 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 the reasons for relying on it have to do with the intuition that ZFC is correct. It is sufficient to accept TST (in fact TSTU). In outline: take the type theory TSTU (allowing urelements in each positive type) as a metatheory and consider the theory of set models of TSTU in TSTU (these models will be sequences of sets T_i (all of the same type in the metatheory) with embeddings of each P(T_i) into P_1(T_) coding embeddings of the power set of T_i into T_ in a type-respecting manner). Given an embedding of T_0 into T_1 (identifying elements of the base "type" with subsets of the base type), embeddings may be defined from each "type" into its successor in a natural way. This can be generalized to transfinite sequences T_ 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 \beth_, 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 T_'s being used in place of V_ 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 In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of map (mathematics), mapping the object to itself while preserving all of its structure. The Set (m ...
''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 mathematics, a well-order (or well-ordering or well-order relation) on a Set (mathematics), set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together ...
in the nonstandard model (we suppose here that we use 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 In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
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 V_ to its sole element, becomes in NFU a function which sends each singleton , 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
injection Injection or injected may refer to: Science and technology * Injective function In mathematics, an injective function (also known as injection, or one-to-one function) is a function (mathematics), function that maps Distinct (mathematics), d ...
from the set of singletons into the set of sets, with the property that ''Endo''( ) = 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, the effect is considered 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 exists 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 In the mathematical field of set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set ...
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 In set theory, several ways have been proposed to construct the natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' l ...
. The original form of this axiom given by Rosser was "the set has ''n'' members", for each natural number ''n''. This intuitively obvious assertion is unstratified: what is provable in NFU is "the set has T^2(n) members" (where the ''T'' operation on cardinals is defined by T(, A, ) = , P_1(A), ; this raises the type of a cardinal by one). For any cardinal number (including natural numbers) to assert T(, A, ) = , A, 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 \beth_n exists, but not that \beth_ exists; NFU + ''Counting'' (easily) proves ''Infinity'', and further proves the existence of \beth_ for each n, but not the existence of \beth_. (See
beth number In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mod ...
s). ''Counting'' implies immediately that one does not need to assign types to variables restricted to the set N of natural numbers for purposes of stratification; it is a theorem that the
power set In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
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 \phi (not necessarily stratified!) the set \ 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 Robert Martin Solovay (born December 15, 1938) is an American mathematician specializing in set theory. Biography Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation on '' ...
shows that the consistency strength of the theory NFU* = NFU + ''Counting'' + ''Strongly Cantorian Separation'' is the same as that of Zermelo set theory + \Sigma_2 ''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 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 \phi (not necessarily stratified!) the set 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 In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
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 non-Cantorian ordinal \alpha, there is a natural number ''n'' such that T^n(\Omega) < \alpha. Recall that \Omega 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 T^n(\Omega): this is the ''n''th term s_n of any finite sequence of ordinals ''s'' of length ''n'' such that s_0 = \Omega, s_ = T(s_i) for each appropriate ''i''. This definition is completely unstratified. The uniqueness of T^n(\Omega) 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 j^(\alpha) 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 In the foundations of mathematics Foundations of mathematics is the study of the philosophy, philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philoso ...
plus the assertion that the proper class ordinal (the class of all ordinals) is a
weakly compact cardinal In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mode ...
. 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 In the foundations of mathematics Foundations of mathematics is the study of the philosophy, philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philoso ...
with a predicate on the classes which is a κ-complete non-principal
ultrafilter In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a maximal filter on P; that is, a proper filter on P that cannot be enlarged to a bigger proper filte ...
on the proper class ordinal κ; in effect, this is Morse–Kelley set theory + "the proper class ordinal is a
measurable cardinal In mathematics, a measurable cardinal is a certain kind of large cardinal number. In order to define the concept, one introduces a two-valued measure (mathematics), measure on a cardinal , or more generally on any set. For a cardinal , it can be de ...
"! 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 In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of map (mathematics), mapping the object to itself while preserving all of its structure. The Set (m ...
s having special properties.


See also

* Alternative set theory *
Axiomatic set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics Mathematic ...
* Implementation of mathematics in set theory *
Positive set theory In mathematical logic Mathematical logic is the study of formal logic within mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are ...
*
Set-theoretic definition of natural numbers In set theory, several ways have been proposed to construct the natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' l ...


Notes


References

* * * * * With discussion by 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


"Enriched Stratified systems for the Foundations of Category Theory"
by
Solomon Feferman Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher A philosopher is a person who practices or investigates philosophy Philosophy (from , ) is the systematized study of general and fundamental question ...
(2011) *
Stanford Encyclopedia of Philosophy The ''Stanford Encyclopedia of Philosophy'' (''SEP'') combines an online encyclopedia of philosophy with scholarly peer review, peer-reviewed publication of original papers in philosophy, freely accessible to Internet users. It is maintained by S ...
: *
Quine's New Foundations
— by Thomas Forster. *
Alternative axiomatic set theories
— by Randall Holmes. * Randall Holmes

* Randall Holmes

* Randall Holmes
A new pass at the NF consistency proof
{{Mathematical logic Systems of set theory Type theory Urelements Willard Van Orman Quine