Set-theoretic definition of natural numbers

From Wikipedia, the free encyclopedia

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

1 The contemporary standard
2 The oldest definition
3 Problem
4 See also
5 References
6 External links

[edit] The contemporary standard

In standard (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 = {{}}, 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.

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

[edit] The oldest definition

Frege (and Bertrand Russell independently) proposed the following definition.^{[citation needed]} Informally, each natural number n is defined as the set whose members each have n elements. More formally, a natural number is the equivalence class of all sets under the relation of equinumerosity. This may appear circular but is not.

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

σ(A)

as $\{x \cup \{y\} \mid x \in A \wedge y \not\in x\}.$

σ(A) is the set obtained by adding a new element y to every member x of A. $σ$ is a set-theoretic operationalization of the successor function. With the function σ in hand, we can say 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, of course, but George Boolos (1998) and Anderson and Zalta (2004) show how to repair it.

[edit] Problem

A consequence of Kurt Gödel's work on incompleteness is that in any axiomatization of number theory (ie. 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 formal system cannot capture entirely what a number is.

Whether this is a problem or not depends on whether you were seeking a formal definition of the concept of number. 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.

Poincaré, amongst others (Bernays, Wittgenstein), held that any attempt to *define* natural number as it is endeavoured to do so above is doomed to failure by circularity. Informally, Godel'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. A quote from Poincaré: "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." A quote from Wittgenstein: "This is not a definition. This is nothing but the arithmetical calculus with frills tacked on." A quote from Bernays: "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 ie. preliminary to and implicit in any logical thought whatsoever. Note that from such a viewpoint, set theory does not precede number theory.

[edit] See also

[edit] 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.