Set-theoretic definition of natural numbers


Set-theoretic definition of natural numbers

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

The contemporary standard

In standard (ZF) set theory the natural numbersare defined recursively by 0 = {} (the empty set) and "n"+1 = "n" ∪ {"n"}. Then "n" = {0,1,...,"n"−1} for each natural number "n". Thefirst 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.

The oldest definition

Frege (and Bertrand Russell independently) proposed the following definition. Fact|date=October 2007 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:: sigma(A) as {x cup {y} mid x in A wedge y otin x}.σ("A") is the set obtained by adding a new element "y" to every member "x" of "A". sigma is a set-theoretic operationalization of the successor function. With the function σ in hand, we can say 1 = sigma(0), 2 = sigma(1), 3 = sigma(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.

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.

ee also

* Peano arithmetic
* ZFC
* axiomatic set theory
* 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. " [http://math.boisestate.edu/~holmes/holmes/head.pdf 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:
** [http://plato.stanford.edu/entries/quine-nf Quine's New Foundations] — by Thomas Forster.
** [http://setis.library.usyd.edu.au/stanford/entries/settheory-alternative/ Alternative axiomatic set theories] — by Randall Holmes.
* McGuire, Gary, " [http://www.maths.may.ie/staff/gmg/nn.ps What are the Natural Numbers?] "
* Randall Holmes: [http://math.boisestate.edu/~holmes/holmes/nf.html New Foundations Home Page.]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Natural number — Natural numbers can be used for counting (one apple, two apples, three apples, ...) from top to bottom. In mathematics, the natural numbers are the ordinary whole numbers used for counting ( there are 6 coins on the table ) and ordering ( this is …   Wikipedia

  • set theory — the branch of mathematics that deals with relations between sets. [1940 45] * * * Branch of mathematics that deals with the properties of sets. It is most valuable as applied to other areas of mathematics, which borrow from and adapt its… …   Universalium

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • Set (mathematics) — This article gives an introduction to what mathematicians call intuitive or naive set theory; for a more detailed account see Naive set theory. For a rigorous modern axiomatic treatment of sets, see Set theory. The intersection of two sets is… …   Wikipedia

  • Implementation of mathematics in set theory — This article examines the implementation of mathematical concepts in set theory. The implementation of a number of basic mathematical concepts is carried out in parallel in ZFC (the dominant set theory) and in NFU, the version of Quine s New… …   Wikipedia

  • Empty set — ∅ redirects here. For similar looking symbols, see Ø (disambiguation). The empty set is the set containing no elements. In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality… …   Wikipedia

  • Internal set theory — (IST) is a mathematical theory of sets developed by Edward Nelson which provides an axiomatic basis for a portion of the non standard analysis introduced by Abraham Robinson. Instead of adding new elements to the real numbers, the axioms… …   Wikipedia

  • Naive set theory — This article is about the mathematical topic. For the book of the same name, see Naive Set Theory (book). Naive set theory is one of several theories of sets used in the discussion of the foundations of mathematics.[1] The informal content of… …   Wikipedia

  • Diophantine set — In mathematics, a Diophantine equation is an equation of the form P(x1, ..., xj, y1, ..., yk)=0 (usually abbreviated P(x,y)=0 ) where P(x,y) is a polynomial with integer coefficients. A Diophantine set is a subset S of Nj [1] so that for some… …   Wikipedia

  • Class (set theory) — In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) which can be unambiguously defined by a property that all its members share. The precise definition of class… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.