Set-theoretic definition of natural numbers

Several ways have been proposed to define the natural numbers using set theory.

Contemporary standard

In standard, Zermelo–Fraenkel (ZF) set theory the natural numbers are defined recursively by 0 = {} (the empty set) and n + 1 = n ∪ {n}. Then n = {0, 1, ..., n − 1} for each natural number n. The first few numbers defined this way are 0 = {}, 1 = {0} = {{}}, 2 = {0,1} = {{},{{}}}, 3 = {0,1,2} = {{},{{}},{{},{{}}}}.

The set N of natural numbers is defined as the smallest set containing 0 and closed under the successor function S defined by S(n) = n ∪ {n}. (For the existence of such a set we need an axiom of infinity.) The structure ⟨N,0,S⟩ is a model of Peano arithmetic.

File:Constructing The Natural Numbers.gif

The set theoretic construction of the Natural Numbers visualised, for the first few natural numbers

The set N and its elements, when constructed this way, are examples of von Neumann ordinals.

Oldest definition

Frege and Bertrand Russell each proposed the following definition. Informally, each natural number n is defined as the set whose members each have n elements. More formally, a natural number is an equivalence class of finite sets under the equivalence relation of equinumerosity. This may appear circular, but it is not since equinumerosity can be defined without resort to the actual number of elements (for example, inductively).

Even more formally, first define 0 as $\{\varnothing\}$ (this is the set whose only element is the empty set). Then given any set A, define σ(A) as

$\sigma(A) := \{x \cup \{y\} \mid x \in A \wedge y \notin x\}.$

Thus σ(A) is the set obtained by adding a new element y to every member x of A. This $\sigma$ is a set-theoretic operationalization of the successor function. With the function σ in hand, one can define 1 = σ(0), 2 = σ(1), 3 = σ(2), and so forth. This definition has the desired effect: the 3 we have just defined actually is the set whose members all have three elements.

This definition works in naive set theory, type theory, and in set theories that grew out of type theory, such as New Foundations and related systems. But it does not work in the axiomatic set theory ZFC and related systems, because in such systems the equivalence classes under equinumerosity are "too large" to be sets. For that matter, there is no universal set V in ZFC, under pain of the Russell paradox.

Hatcher (1982) derives Peano's axioms from several foundational systems, including ZFC and category theory. Most curious is his meticulous derivation of these axioms from the system of Frege's Grundgesetze using modern notation and natural deduction. The Russell paradox proved this system inconsistent, but George Boolos (1998) and Anderson and Zalta (2004) show how to repair it.

Problem

A consequence of Kurt Gödel's work on incompleteness is that in any effectively generated axiomatization of number theory (i.e. one containing minimal arithmetic), there will be true statements of number theory which cannot be proven in that system. So trivially it follows that ZFC or any other effectively generated formal system cannot capture entirely what a number is.

Whether this is a problem or not depends on whether a formal definition of the concept of number is required. For people such as Bertrand Russell (who thought number theory, and hence mathematics, was a branch of logic and number was something to be defined in terms of formal logic) it was an insurmountable problem. But if you take the concept of number as an absolutely fundamental and irreducible one, it is to be expected. After all, if any concept is to be left formally undefined in mathematics, it might as well be one which everyone understands.

Henri Poincaré, amongst others (Paul Bernays, Ludwig Wittgenstein), held that any attempt to define natural number as it is endeavored to do so above is doomed to failure by circularity. Informally, Gödel's theorem shows that a formal axiomatic definition is impossible (incompleteness), Poincaré claims that no definition, formal or informal, is possible (circularity). As such, they give two separate reasons why purported definitions of number must fail to define number.

Poincaré states:

The definitions of number are very numerous and of great variety, and I will not attempt to enumerate their names and their authors. We must not be surprised that there are so many. If any of them were satisfactory we should not get any new ones.

Wittgenstein states:

This is not a definition. This is nothing but the arithmetical calculus with frills tacked on.

Bernays states:

Thus in spite of the possibility of incorporating arithmetic into logistic, arithmetic constitutes the more abstract ('purer') schema; and this appears paradoxical only because of a traditional, but on closer examination unjustified view according to which logical generality is in every respect the highest generality.

Specifically, there are at least four points:

1. Zero is defined to be the number of things satisfying a condition which is satisfied in no case. It is not clear that a great deal of progress has been made.
2. It would be quite a challenge to enumerate the instances where Russell (or anyone else reading the definition out loud) refers to "an object" or "the class", phrases which are incomprehensible if one does not know that the speaker is speaking of one thing and one thing only.
3. The use of the concept of a relation, of any sort, presupposes the concept of two. For the idea of a relation is incomprehensible without the idea of two terms; that they must be two and only two.
4. Wittgenstein's "frills-tacked on comment". It is not at all clear how one would interpret the definitions at hand if one could not count.

These problems with defining number disappear if one takes, as Poincaré did, the concept of number as basic i.e. preliminary to and implicit in any logical thought whatsoever. Note that from such a viewpoint, set theory does not precede number theory.

See also

• Ackermann coding
• Foundations of mathematics
• New Foundations

References

• Anderson, D. J., and Edward Zalta, 2004, "Frege, Boolos, and Logical Objects," Journal of Philosophical Logic 33: 1–26.
• George Boolos, 1998. Logic, Logic, and Logic.
• Hatcher, William S., 1982. The Logical Foundations of Mathematics. Pergamon. In this text, S refers to the Peano axioms.
• Holmes, Randall, 1998. 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.
• Patrick Suppes, 1972 (1960). Axiomatic Set Theory. Dover.

External links

• Stanford Encyclopedia of Philosophy:
  • Quine's New Foundations — by Thomas Forster.
  • Alternative axiomatic set theories — by Randall Holmes.
• McGuire, Gary, "What are the Natural Numbers?"
• Randall Holmes: New Foundations Home Page.