imported>Daniel Mietchen |
imported>Peter Schmitt |
| Line 1: |
Line 1: |
| {{subpages}} | | {{subpages}} |
|
| |
| In [[mathematics]], a '''natural number''' can mean either an element of the set {1, 2, 3, ...} (i.e., the [[Positive number|positive]] [[integer]]s) or an element of the set {0, 1, 2, 3, ...} (i.e., the [[non-negative]] integers). The former is generally used in [[number theory]], while the latter is preferred in [[mathematical logic]], [[set theory]] and [[computer science]]. See below for a formal definition.
| |
|
| |
| Natural numbers have two main purposes: they can be used for [[counting]] ("there are 3 apples on the table"), and they can be used for [[partial order|ordering]] ("this is the 3<sup>rd</sup> largest city in the country").
| |
|
| |
| Properties of the natural numbers related to [[divisibility]], such as the distribution of [[prime number]]s, are studied in [[number theory]]. Problems concerning counting, such as [[Ramsey theory]], are studied in [[combinatorics]].
| |
|
| |
| ==History of natural numbers and the status of zero==
| |
| The natural numbers presumably had their origins in the words used to count things, beginning with the number one.
| |
|
| |
| The first major advance in abstraction was the use of [[numeral system|numerals]] to represent numbers. This allowed systems to be developed for recording large numbers. For example, the [[Babylonia]]ns developed a powerful [[Positional notation|place-value]] system based essentially on the numerals for 1 and 10. The ancient [[History of Ancient Egypt|Egyptians]] had a system of numerals with distinct [[Egyptian hieroglyphs|hieroglyph]]s for 1, 10, and all the powers of 10 up to one million. A stone carving from [[Karnak]], dating from around [[1500 BC]] and now at the [[Louvre]] in Paris, depicts 276 as 2 hundreds, 7 tens, and 6 ones; and similarly for the number 4,622.
| |
|
| |
| A much later advance in abstraction was the development of the idea of [[0 (number)|zero]] as a number with its own numeral. A zero [[numerical digit|digit]] had been used in place-value notation as early as [[700 BC]] by the Babylonians, but it was never used as a final element.<ref>"... a tablet found at Kish ... thought to date from around 700 BC, uses three hooks to denote an empty place in the positional notation. Other tablets dated from around the same time use a single hook for an empty place. [http://www-history.mcs.st-and.ac.uk/history/HistTopics/Zero.html]"</ref> The [[Olmec]] and [[Maya civilization]] used zero as a separate number as early as [[1st century BC]], apparently developed independently, but this usage did not spread beyond [[Mesoamerica]]. The concept as used in modern times originated with the [[India]]n mathematician [[Brahmagupta]] in [[628]]. Nevertheless, zero was used as a number by all medieval [[computus|computists]] (calculators of [[Easter]]) beginning with [[Dionysius Exiguus]] in [[525]], but in general no [[Roman numeral]] was used to write it. Instead, the Latin word for "nothing," ''nullus'', was employed.
| |
|
| |
| The first systematic study of numbers as [[abstraction]]s (that is, as abstract [[entity|entities]]) is usually credited to the [[ancient Greece|Greek]] philosophers [[Pythagoras]] and [[Archimedes]]. However, independent studies also occurred at around the same time in [[India]], [[China]], and [[Mesoamerica]].
| |
|
| |
| In the nineteenth century, a [[set theory|set-theoretical]] [[definition]] of natural numbers was developed. With this definition, it was more convenient to include zero (corresponding to the [[empty set]]) as a natural number. This convention is followed by [[set theory|set theorists]], [[logic|logicians]], and [[computer science|computer scientists]]. Other mathematicians, primarily [[number theory|number theorists]], often prefer to follow the older tradition and exclude zero from the natural numbers.
| |
|
| |
| ==Notation==
| |
| Mathematicians use '''N''' or <math>\mathbb{N}</math> (an N in [[blackboard bold]], Unicode ℕ) to refer to the [[set]] of all natural numbers. This set is [[Infinity|infinite]] but [[countable set|countable]] by definition.
| |
|
| |
| To be unambiguous about whether zero is included or not,
| |
| sometimes an index "0" is added in the former case, and a superscript "*" is added in the latter case:
| |
|
| |
| : '''N'''<sub>0</sub> = { 0, 1, 2, ... } ; '''N'''<sup>*</sup> = { 1, 2, ... }.
| |
|
| |
| (Sometimes, an index or [[superscript]] "+" is added to signify "positive". However, this is often used for "nonnegative" in other cases, as '''R'''<sup>+</sup> = <nowiki>[0,∞)</nowiki> and '''Z'''<sup>+</sup> = { 0, 1, 2,... }, at least in European literature. The notation "*", however, is standard for nonzero or rather [[invertible]] elements.)
| |
|
| |
| Some authors who exclude zero from the naturals use the term ''whole numbers'', denoted <math>\mathbb{W}</math>, for the set of nonnegative integers. Others use the notation <math>\mathbb{P}</math> for the positive integers.
| |
|
| |
| Set theorists often denote the set of all natural numbers by a lower-case Greek letter [[omega]]: ω. When this notation is used, zero is explicitly included as a natural number.
| |
|
| |
| ==Formal definitions==
| |
| Historically, the precise mathematical definition of the natural numbers developed with some difficulty. The [[Peano postulates]] state conditions that any successful definition must satisfy. Certain constructions show that, given [[set theory]], [[model theory|models]] of the Peano postulates must exist.
| |
|
| |
| ===Peano axioms===
| |
| *There is a natural number <font-size=3>'''0'''</font>.
| |
|
| |
| *Every natural number <font-size=3>'''''a'''''</font> has a natural number successor, denoted by <font-size=3>'''''S''(''a'')'''</font>.
| |
|
| |
| *There is no natural number whose successor is <font-size=3>'''0'''</font>.
| |
|
| |
| *Distinct natural numbers have distinct successors: if <font-size=3>'''''a'' ≠ ''b'''''</font>, then <font-size=3>'''''S''(''a'') ≠ ''S''(''b'')'''</font>
| |
|
| |
| *If a property is possessed by <font-size=3>'''0'''</font> and also by the successor of every natural number which possesses it, then it is possessed by all natural numbers. (This postulate ensures that the proof technique of [[mathematical induction]] is valid.)
| |
|
| |
| It should be noted that the "<font-size=3>'''0'''</font>" in the above definition need not correspond to what we normally consider to be the number zero. "<font-size=3>'''0'''</font>" simply means some object that when combined with an appropriate successor function, satisfies the Peano axioms. There are many systems that satisfy these axioms, including the natural numbers (either starting from zero or one).
| |
|
| |
| ===Constructions based on set theory===
| |
| ====A standard construction====
| |
| A standard construction in [[set theory]], a special case of the [[ordinal number#Von Neumann definition of ordinals|von Neumann ordinal]] construction, is to define the natural numbers as follows:
| |
| :We set 0 := { }, the [[empty set]],
| |
| :and define ''S''(''a'') = ''a'' ∪ {''a''} for every set ''a''. ''S''(''a'') is the successor of ''a'', and ''S'' is called the successor function.
| |
| :If the [[axiom of infinity]] holds, then the set of all natural numbers exists and is the intersection of all sets containing 0 which are closed under this successor function.
| |
| :If the set of all natural numbers exists, then it satisfies the [[Peano axioms]].
| |
| :Each natural number is then equal to the set of natural numbers less than it, so that
| |
|
| |
| :*0 = { }
| |
| :*1 = <nowiki>{0} = {{ }}</nowiki>
| |
| :*2 = <nowiki>{0,1} = {0, {0}} = {{ }, {{ }}}</nowiki>
| |
| :*3 = <nowiki>{0,1,2} = {0, {0}, {0, {0}}} = {{ }, {{ }}, {{ }, {{ }}}}</nowiki>
| |
| :*''n'' = {0,1,2,…,''n''−2,''n''−1} = {0,1,2,…,''n''−2} ∪ {''n''−1} = (''n''−1) ∪ {''n''−1}
| |
|
| |
| :and so on. When you see a natural number used as a set, this is typically what is meant. Under this definition, there are exactly ''n'' elements (in the naïve sense) in the set ''n'' and ''n'' ≤ ''m'' (in the naïve sense) [[if and only if]] ''n'' is a [[subset]] of ''m''.
| |
|
| |
| :Also, with this definition, different possible interpretations of notations like '''R'''<sup>''n''</sup> (''n-''tuples versus mappings of ''n'' into '''R''') coincide.
| |
|
| |
| :Even if the axiom of infinity fails and the set of all natural numbers does not exist, it is possible to define what it means to be one of these sets. A set ''n'' is a natural number means that it is either 0 (empty) or a successor, and each of its elements is either 0 or the successor of another of its elements.
| |
|
| |
| ====Other constructions====
| |
| Although the standard construction is useful, it is not the only possible construction. For example:
| |
| :one could define 0 = { }
| |
| :and ''S''(''a'') = {''a''},
| |
| :producing
| |
| :: 0 = { }
| |
| :: 1 = {0} = <nowiki>{{ }}</nowiki>
| |
| :: 2 = {1} = <nowiki>{{{ }}}</nowiki>, etc.
| |
| Or we could even define 0 = <nowiki>{{ }}</nowiki>
| |
| :and ''S''(''a'') = ''a'' U {''a''}
| |
| :producing
| |
| :: 0 = <nowiki>{{ }}</nowiki>
| |
| :: 1 = <nowiki>{{ }, 0} = {{ }, {{ }}}</nowiki>
| |
| :: 2 = <nowiki>{{ }, 0, 1}, etc.</nowiki>
| |
|
| |
| Arguably the oldest set-theoretic definition of the natural numbers is the definition commonly ascribed to [[Frege]] and [[Bertrand Russell|Russell]] under which each concrete natural number ''n'' is defined as the set of all sets with ''n'' elements. This may appear circular, but can be made rigorous with care. Define 0 as <math>\{\{\}\}</math> (clearly the set of all sets with 0 elements) and define <math>\sigma(A)</math> (for any set ''A'') as <math>\{x \cup \{y\} \mid x \in A \wedge y \not\in x\}</math>. Then 0 will be the set of all sets with 0 elements, <math>1=\sigma(0)</math> will be the set of all sets with 1 element, <math>2=\sigma(1)</math> will be the set of all sets with 2 elements, and so forth. The set of all natural numbers can be defined as the intersection of all sets containing 0 as an element and closed under <math>\sigma</math> (that is, if the set contains an element ''n'', it also contains <math>\sigma(n)</math>). This definition does not work in the usual systems of [[axiomatic set theory]] because the collections involved are too large (it will not work in any set theory with the [[axiom of separation]]); but it does work in [[New Foundations]] (and in related systems known to be consistent) and in some systems of [[type theory]].
| |
|
| |
| For the rest of this article, we follow the standard construction described above.
| |
|
| |
| ==Properties==
| |
| One can recursively define an [[Addition in N|addition]] on the natural numbers by setting ''a'' + 0 = ''a'' and ''a'' + ''S''(''b'') = ''S''(''a'' + ''b'') for all ''a'', ''b''. This turns the natural numbers ('''N''', +) into a [[commutative]] [[monoid]] with [[identity element]] 0, the so-called [[free monoid]] with one generator. This monoid satisfies the [[cancellation property]] and can be embedded in a [[group (mathematics)|group]]. The smallest group containing the natural numbers is the [[integer]]s.
| |
|
| |
| If we define 1 := ''S''(0), then ''b'' + 1 = ''b'' + ''S''(0) = ''S''(''b'' + 0) = ''S''(''b''). That is, ''b'' + 1 is simply the successor of ''b''.
| |
|
| |
| Analogously, given that addition has been defined, a [[multiplication]] × can be defined via ''a'' × 0 = 0 and ''a'' × S(''b'') = (''a'' × ''b'') + ''a''. This turns ('''N'''<sup>*</sup>, ×) into a free commutative monoid with identity element 1; a generator set for this monoid is the set of [[prime number]]s. Addition and multiplication are compatible, which is expressed in the [[distributivity|distribution law]]:
| |
| ''a'' × (''b'' + ''c'') = (''a'' × ''b'') + (''a'' × ''c''). These properties of addition and multiplication make the natural numbers an instance of a [[commutative]] [[semiring]]. Semirings are an algebraic generalization of the natural numbers where multiplication is not necessarily commutative.
| |
|
| |
| If we interpret the natural numbers as "excluding 0", and "starting at 1", the definitions of + and × are as above, except that we start with ''a'' + 1 = ''S''(''a'') and ''a'' × 1 = ''a''.
| |
|
| |
| For the remainder of the article, we write ''ab'' to indicate the product ''a'' × ''b'', and we also assume the standard [[order of operations]].
| |
|
| |
| Furthermore, one defines a [[total order]] on the natural numbers by writing ''a'' [[≤]] ''b'' if and only if there exists another natural number ''c'' with ''a'' + ''c'' = ''b''. This order is compatible with the arithmetical operations in the following sense: if ''a'', ''b'' and ''c'' are natural numbers and ''a'' ≤ ''b'', then ''a'' + ''c'' ≤ ''b'' + ''c'' and ''ac'' ≤ ''bc''. An important property of the natural numbers is that they are [[well-order|well-ordered]]: every non-empty set of natural numbers has a least element.
| |
|
| |
| While it is in general not possible to divide one natural number by another and get a natural number as result, the procedure of ''[[Division (mathematics)|division]] with remainder'' is available as a substitute: for any two natural numbers ''a'' and ''b'' with ''b'' ≠ 0 we can find natural numbers ''q'' and ''r'' such that
| |
|
| |
| :''a'' = ''bq'' + ''r'' and ''r'' < ''b''
| |
|
| |
| The number ''q'' is called the ''[[quotient]]'' and ''r'' is called the ''[[remainder]]'' of division of ''a'' by ''b''. The numbers ''q'' and ''r'' are uniquely determined by ''a'' and ''b''. This, the [[Division algorithm]], is key to several other properties ([[divisibility]]), algorithms (such as the [[Euclidean algorithm]]), and ideas in number theory.
| |
|
| |
| The natural numbers including zero form a [[commutative monoid]] under addition (with [[identity element]] zero), and under multiplication (with identity element one).
| |
|
| |
| ==Generalizations==
| |
| Two generalizations of natural numbers arise from the two uses: [[ordinal number]]s are used to describe the position of an element in an [[ordered sequence]] and [[cardinal number]]s are used to specify the size of a given [[set]].
| |
|
| |
| For [[Finite set|finite]] sequences or finite sets, both of these properties are embodied in the natural numbers.
| |
|
| |
| Other generalizations are discussed in the article on [[number]]s.
| |
|
| |
| == References ==
| |
| <references/>
| |
| *[[Edmund Landau]], Foundations of Analysis, Chelsea Pub Co. ISBN 0-8218-2693-X.
| |
|
| |
| == External links ==
| |
| *[http://www.apronus.com/provenmath/naturalaxioms.htm Axioms and Construction of Natural Numbers]
| |
