Editing New Foundations (section)

=== Natural numbers and the axiom of infinity ===
The usual form of the [[axiom of infinity]] is based on the [[Set-theoretic definition of natural numbers|von Neumann construction of the natural numbers]], which is not suitable for NF, since the description of the successor operation (and many other aspects of von Neumann numerals) is necessarily unstratified. The usual form of natural numbers used in NF follows [[Set-theoretic definition of natural numbers#Frege and Russell|Frege's definition]], i.e., the natural number ''n'' is represented by the set of all sets with ''n'' elements. Under this definition, 0 is easily defined as <math>\{\varnothing\}</math>, and the successor operation can be defined in a stratified way: <math>S(A) = \{a \cup \{x\} \mid a \in A \wedge x \notin a\}.</math> Under this definition, one can write down a statement analogous to the usual form of the axiom of infinity. However, that statement would be trivially true, since the universal set <math>V</math> would be an [[Axiom of infinity|inductive set]].

Since inductive sets always exist, the set of natural numbers <math>\mathbf{N}</math> can be defined as the intersection of all inductive sets. This definition enables [[mathematical induction]] for stratified statements <math>P(n)</math>, because the set <math>\{n \in \mathbf{N} \mid P(n)\}</math> can be constructed, and when <math>P(n)</math> satisfies the conditions for mathematical induction, this set is an inductive set.

Finite sets can then be defined as sets that belong to a natural number. However, it is not trivial to prove that <math>V</math> is not a "finite set", i.e., that the size of the universe <math>|V|</math> is not a natural number. Suppose that <math>|V| = n \in \mathbf{N}</math>. Then <math>n = \{V\}</math> (it can be shown inductively that a finite set is not [[equinumerous]] with any of its proper subsets), <math>n + 1 = S(n) = \varnothing</math>, and each subsequent natural number would be <math>\varnothing</math> too, causing arithmetic to break down. To prevent this, one can introduce the '''axiom of infinity''' for NF: <math>\varnothing \notin \mathbf{N}.</math>{{sfn|Holmes|1998|loc=sec. 12.1}}

It may intuitively seem that one should be able to prove ''Infinity'' in NF(U) by constructing any "externally" infinite sequence of sets, such as <math>\varnothing, \{\varnothing\}, \{\{{\varnothing}\}\}, \ldots</math>. However, such a sequence could only be constructed through unstratified constructions (evidenced by the fact that TST itself has finite models), so such a proof could not be carried out in NF(U). In fact, ''Infinity'' is [[Independence (mathematical logic)|logically independent]] of NFU: There exists models of NFU where <math>|V|</math> is a [[Non-standard model of arithmetic|non-standard natural number]]. In such models, mathematical induction can prove statements about <math>|V|</math>, making it impossible to "distinguish" <math>|V|</math> from standard natural numbers.

However, there are some cases where ''Infinity'' can be proven (in which cases it may be referred to as the '''theorem of infinity'''):

* In NF (without [[urelement]]s), Specker{{sfn|Specker|1953}} has shown that the [[axiom of choice]] is false. Since it can be proved through induction that every finite set has a choice function (a stratified condition), it follows that <math>V</math> is infinite.
* In NFU with axioms asserting the existence of a type-level ordered pair, <math>V</math> is equinumerous with its proper subset <math>V \times \{0\}</math>, which implies ''Infinity''.{{sfn|Holmes|1998|loc=sec. 12.1}} Conversely, NFU + ''Infinity'' + ''Choice'' proves the existence of a type-level ordered pair.{{Citation needed|date=July 2020|reason=I searched for quite a while and was unable to find a source for this statement. It is repeated in several online sources, but without proof or reference.}} NFU + ''Infinity'' interprets NFU + "there is a type-level ordered pair" (they are not quite the same theory, but the differences are inessential).{{Citation needed|date=March 2023|reason=What does the word "interpret" mean here?}}

Stronger axioms of infinity exist, such as that the set of natural numbers is a strongly Cantorian set, or NFUM = NFU + ''Infinity'' + ''Large Ordinals'' + ''Small Ordinals'' which is equivalent to [[Morse–Kelley set theory]] plus a predicate on proper classes which is a ''κ''-complete nonprincipal ultrafilter on the proper class ordinal ''κ''.<ref>{{cite journal |last1=Holmes |first1=M. Randall |title=Strong axioms of infinity in NFU |journal=Journal of Symbolic Logic |date=March 2001 |volume=66 |issue=1 |pages=87–116 |doi=10.2307/2694912 |jstor=2694912 |url=https://randall-holmes.github.io/Papers/nfumcorrected.pdf}}</ref>