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 oldest definition
2 The contemporary standard
3 See also
4 References
5 External links

[edit] The oldest definition

Frege (and Bertrand Russell independently) 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 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 who 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.

If the universe V has finite cardinality n, then $n+1 = \sigma(V)= \emptyset$ , $\sigma(\emptyset)=\emptyset$ , and the sequence of natural numbers comes to an end. Hence if the Frege-Russell natural numbers are to satisfy the Peano axioms, the underlying axiomatic set theory must include an axiom of Infinity. The set of natural numbers can be defined as the intersection of all sets containing 0 and closed under σ.

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] The contemporary standard

A set-theoretic definition of the natural numbers which does work in ZFC and related theories is John von Neumann's definition of an ordinal number:

Define the empty set to be zero.
Define the successor of n as n ∪ {n}

The finite cardinal numbers can be defined from these numbers by means of the axiom of Choice; see Suppes (1972: chpt. 9).

The axiom of Infinity then assures that the set N of all natural numbers exists. It is easy to show that the above definition satisfies the Peano axioms. It also (in contrast to some alternative definitions) has the property that each natural number n is a set with exactly n elements: {0,1,2,...,n-1}

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