GetWiki
Peano axioms
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
Peano axioms
please note:
 the content below is remote from Wikipedia
 it has been imported raw for GetWiki
{{short descriptionaxioms for the natural numbers}}In mathematical logic, the Peano axioms, also known as the Dedekindâ€“Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.The need to formalize arithmetic was not well appreciated until the work of Hermann Grassmann, who showed in the 1860s that many facts in arithmetic could be derived from more basic facts about the successor operation and induction.{{sfnGrassmann1861}} In 1881, Charles Sanders Peirce provided an axiomatization of naturalnumber arithmetic.{{harvnbPeirce1881}}, {{harvnbShields1997}} In 1888, Richard Dedekind proposed another axiomatization of naturalnumber arithmetic, and in 1889, Peano published a simplified version of them as a collection of axioms in his book, The principles of arithmetic presented by a new method ().The Peano axioms contain three types of statements. The first axiom asserts the existence of at least one member of the set of natural numbers. The next four are general statements about equality; in modern treatments these are often not taken as part of the Peano axioms, but rather as axioms of the "underlying logic".{{sfnvan Heijenoort1967page=94}} The next three axioms are firstorder statements about natural numbers expressing the fundamental properties of the successor operation. The ninth, final axiom is a second order statement of the principle of mathematical induction over the natural numbers. A weaker firstorder system called Peano arithmetic is obtained by explicitly adding the addition and multiplication operation symbols and replacing the secondorder induction axiom with a firstorder axiom schema. the content below is remote from Wikipedia
 it has been imported raw for GetWiki
Formulation
When Peano formulated his axioms, the language of mathematical logic was in its infancy. The system of logical notation he created to present the axioms did not prove to be popular, although it was the genesis of the modern notation for set membership (âˆˆ, which comes from Peano's Îµ) and implication (âŠƒ, which comes from Peano's reversed 'C'.) Peano maintained a clear distinction between mathematical and logical symbols, which was not yet common in mathematics; such a separation had first been introduced in the Begriffsschrift by Gottlob Frege, published in 1879.{{sfnvan Heijenoort1967page=2}} Peano was unaware of Frege's work and independently recreated his logical apparatus based on the work of Boole and SchrÃ¶der.{{sfnvan Heijenoort1967page=83}}The Peano axioms define the arithmetical properties of natural numbers, usually represented as a set N or mathbb{N}. The nonlogical symbols for the axioms consist of a constant symbol 0 and a unary function symbol S.The first axiom states that the constant 0 is a natural number:{{ordered liststart=1 1= 0 is a natural number.}}The next four axioms describe the equality relation. Since they are logically valid in firstorder logic with equality, they are not considered to be part of "the Peano axioms" in modern treatments.{{sfnvan Heijenoort1967page=83}}{{ordered liststart=2< y land y < z Rightarrow x < z ), i.e., the '<' operator is transitive. forall x in mathbf{N} ( neg (x < x) ), i.e., the '<' operator is irreflexive.
 forall x, y in mathbf{N} ( x < y lor x = y lor y < x ), i.e., the ordering satisfies trichotomy.
 forall x, y, z in mathbf{N} ( x < y Rightarrow x + z < y + z ), i.e. the ordering is preserved under addition of the same element.
 forall x, y, z in mathbf{N} ( 0 < z land x < y Rightarrow x cdot z < y cdot z ), i.e. the ordering is preserved under multiplication by the same positive element.
 forall x, y in mathbf{N} ( x < y Rightarrow exists z in mathbf{N} ( x + z = y ) ), i.e. given any two distinct elements, the larger is the smaller plus another element.
 0 < 1 land forall x in mathbf{N} ( x > 0 Rightarrow x ge 1 ), i.e. zero and one are distinct and there is no element between them.
 forall x in mathbf{N} ( x ge 0 ), i.e. zero is the minimum element.
Models
A model of the Peano axioms is a triple {{nowrap(N, 0, S)}}, where N is a (necessarily infinite) set, {{nowrap0 âˆˆ N}} and {{nowrapS : N â†’ N}} satisfies the axioms above. Dedekind proved in his 1888 book, The Nature and Meaning of Numbers (, i.e., â€œWhat are the numbers and what are they good for?â€) that any two models of the Peano axioms (including the secondorder induction axiom) are isomorphic. In particular, given two models {{nowrap(NA, 0A, S'A)}} and {{nowrap(NB, 0B, S'B)}} of the Peano axioms, there is a unique homomorphism {{nowrapf : NA â†’ NB}} satisfying
begin{align}
f(0_A) &= 0_B f(S_A (n)) &= S_B (f (n))end{align}and it is a bijection. This means that the secondorder Peano axioms are categorical. This is not the case with any firstorder reformulation of the Peano axioms, however.Settheoretic models
The Peano axioms can be derived from set theoretic constructions of the natural numbers and axioms of set theory such as ZF.{{harvnbSuppes1960}}, {{harvnbHatcher1982}} The standard construction of the naturals, due to John von Neumann, starts from a definition of 0 as the empty set, âˆ…, and an operator s on sets defined as:
s(a) = a cup {a}
The set of natural numbers N is defined as the intersection of all sets closed under s that contain the empty set. Each natural number is equal (as a set) to the set of natural numbers less than it:
begin{align}
1 &= s(0) = s(emptyset) = emptyset cup { emptyset } = { emptyset } = { 0 } 2 &= s(1) = s({ 0 }) = { 0 } cup { { 0 } } = { 0 , { 0 } } = { 0, 1 } 3 &= s(2) = s({ 0, 1 }) = { 0, 1 } cup { { 0, 1 } } = { 0, 1, { 0, 1 } } = { 0, 1, 2 }end{align}and so on. The set N together with 0 and the successor function {{nowraps : N â†’ N}} satisfies the Peano axioms.Peano arithmetic is equiconsistent with several weak systems of set theory.{{sfnTarskiGivant1987loc=Section 7.6}} One such system is ZFC with the axiom of infinity replaced by its negation. Another such system consists of general set theory (extensionality, existence of the empty set, and the axiom of adjunction), augmented by an axiom schema stating that a property that holds for the empty set and holds of an adjunction whenever it holds of the adjunct must hold for all sets.Interpretation in category theory
The Peano axioms can also be understood using category theory. Let C be a category with terminal object 1C, and define the category of pointed unary systems, US1(C) as follows: The objects of US1(C) are triples {{nowrap(X, 0X, S'X)}} where X is an object of C, and {{nowrap0X : 1C â†’ X}} and {{nowrapS'X : X â†’ X}} are Cmorphisms.
 A morphism Ï† : (X, 0X, S'X) â†’ (Y, 0Y, S'Y) is a Cmorphism {{nowrapÏ† : X â†’ Y}} with {{nowrap1=Ï† 0X = 0Y}} and {{nowrap1=Ï† S'X = S'Y Ï†}}.
begin{align}
u 0 &= 0_X, u (S x) &= S_X (u x).end{align}This is precisely the recursive definition of 0X and SX.Nonstandard models
Although the usual natural numbers satisfy the axioms of PA, there are other models as well (called "nonstandard models"); the compactness theorem implies that the existence of nonstandard elements cannot be excluded in firstorder logic.{{sfnHermes1973loc=VI.4.3ps=, presenting a theorem of Thoralf Skolem}} The upward LÃ¶wenheimâ€“Skolem theorem shows that there are nonstandard models of PA of all infinite cardinalities. This is not the case for the original (secondorder) Peano axioms, which have only one model, up to isomorphism.{{sfnHermes1973loc=VI.3.1}} This illustrates one way the firstorder system PA is weaker than the secondorder Peano axioms.When interpreted as a proof within a firstorder set theory, such as ZFC, Dedekind's categoricity proof for PA shows that each model of set theory has a unique model of the Peano axioms, up to isomorphism, that embeds as an initial segment of all other models of PA contained within that model of set theory. In the standard model of set theory, this smallest model of PA is the standard model of PA; however, in a nonstandard model of set theory, it may be a nonstandard model of PA. This situation cannot be avoided with any firstorder formalization of set theory.It is natural to ask whether a countable nonstandard model can be explicitly constructed. The answer is affirmative as Skolem in 1933 provided an explicit construction of such a nonstandard model. On the other hand, Tennenbaum's theorem, proved in 1959, shows that there is no countable nonstandard model of PA in which either the addition or multiplication operation is computable.{{sfnKaye1991loc=Section 11.3}} This result shows it is difficult to be completely explicit in describing the addition and multiplication operations of a countable nonstandard model of PA. However, there is only one possible order type of a countable nonstandard model. Letting Ï‰ be the order type of the natural numbers, Î¶ be the order type of the integers, and Î· be the order type of the rationals, the order type of any countable nonstandard model of PA is {{nowrapÏ‰ + Î¶Â·Î·}}, which can be visualized as a copy of the natural numbers followed by a dense linear ordering of copies of the integers.Overspill
A cut in a nonstandard model M is a nonempty subset I of M so that I is downward closed ( x content above as imported from Wikipedia
 "Peano axioms" does not exist on GetWiki (yet)
 time: 6:00am EST  Thu, Dec 13 2018
 "Peano axioms" does not exist on GetWiki (yet)
 time: 6:00am EST  Thu, Dec 13 2018
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
Culture
© 2018 M.R.M. PARROTT  ALL RIGHTS RESERVED
x, {{nowrap>1=x = x}}. That is, equality is reflexive.  x and y, if {{nowrap>1=x = y}}, then {{nowrap  y = x}}. That is, equality is symmetric relation>symmetric.  x, y and z, if x = y and y = z, then {{nowrap>1=x = z}}. That is, equality is transitive.  a and b, if b is a natural number and {{nowrap>1=a = b}}, then a is also a natural number. That is, the natural numbers are closed under equality.}}The remaining axioms define the arithmetical properties of the natural numbers. The naturals are assumed to be closed under a singlevalued "successor" function S.{{ordered liststart=6 6=For every natural number n, S(n) is a natural number.  m and n, {{nowrap>1=m = n}} if and only if {{nowrap  S(m) = S(n)}}. That is, S is an injective function>injection.  n, {{nowrap>1=S(n) = 0}} is false. That is, there is no natural number whose successor is 0.}}Peano's original formulation of the axioms used 1 instead of 0 as the "first" natural number.{{sfnPeano1889page=1}} This choice is arbitrary, as axiom 1 does not endow the constant 0 with any additional properties. However, because 0 is the additive identity in arithmetic, most modern formulations of the Peano axioms start from 0. Axioms 1, 6, 7, 8 define a unary representation of the intuitive notion of natural numbers: the number 1 can be defined as S(0), 2 as S(S(0)), etc. However, considering the notion of natural numbers as being defined by these axioms, axioms 1, 6, 7, 8 do not imply that the successor function generates all the natural numbers different from 0. Put differently, they do not guarantee that every natural number other than zero must succeed some other natural number.The intuitive notion that each natural number can be obtained by applying successor sufficiently often to zero requires an additional axiom, which is sometimes called the axiom of induction.{{ordered liststart=9 9=If K is a set such that:
 Ï† is a unary predicate (mathematics)>predicate such that:
ArithmeticThe Peano axioms can be augmented with the operations of addition and multiplication and the usual total (linear) ordering on N. The respective functions and relations are constructed in set theory or secondorder logic, and can be shown to be unique using the Peano axioms.AdditionAddition is a function that maps two natural numbers (two elements of N) to another one. It is defined recursively as:
begin{align}
a + 0 &= a , & textrm{(1)}a + S (b) &= S (a + b). & textrm{(2)}end{align}For example:
begin{align}
a + 1 &= a + S(0) & mbox{by definition}
&= S(a + 0) & mbox{using (2)}
a + 2 &= a + S(1) & mbox{by definition}
&= S(a), & mbox{using (1)}
&= S(a + 1) & mbox{using (2)}
a + 3 &= a + S(2) & mbox{by definition}
&= S(S(a)) & mbox{using } a + 1 = S(a)
&= S(a + 2) & mbox{using (2)}
text{etc.} & end{align}The structure {{nowrap(N, +)}} is a commutative monoid with identity element 0. {{nowrap(N, +)}} is also a cancellative magma, and thus embeddable in a group. The smallest group embedding N is the integers.&= S(S(S(a))) & mbox{using } a + 2 = S(S(a)) MultiplicationSimilarly, multiplication is a function mapping two natural numbers to another one. Given addition, it is defined recursively as:
begin{align}
a cdot 0 &= 0, a cdot S (b) &= a + (a cdot b).end{align}It is easy to see that S(0) (or "1", in the familiar language of decimal representation) is the multiplicative right identity:
a Â· S(0) = a + (a Â· 0) = a + 0 = a
To show that S(0) is also the multiplicative left identity requires the induction axiom due to the way multiplication is defined:
a Â· (b + c) = (a Â· b) + (a Â· c).
Thus, {{nowrap(N, +, 0, Â·, S(0))}} is a commutative semiring.InequalitiesThe usual total order relation â‰¤ on natural numbers can be defined as follows, assuming 0 is a natural number:
For all {{nowrapa, b âˆˆ N}}, {{nowrapa â‰¤ b}} if and only if there exists some {{nowrapc âˆˆ N}} such that {{nowrap1=a + c = b}}.
This relation is stable under addition and multiplication: for a, b, c in mathbf{N} , if {{nowrapa â‰¤ b}}, then:
For any predicate Ï†, if
* Ï†(0) is true, and
* for every {{nowrapn, k âˆˆ N}}, if {{nowrapk â‰¤ n}} implies that Ï†(k) is true, then Ï†(S(n)) is true,
then for every {{nowrapn âˆˆ N}}, Ï†(n) is true.
This form of the induction axiom, called strong induction, is a consequence of the standard formulation, but is often better suited for reasoning about the â‰¤ order. For example, to show that the naturals are wellorderedâ€”every nonempty subset of N has a least elementâ€”one can reason as follows. Let a nonempty {{nowrapX âŠ† N}} be given and assume X has no least element.
Firstorder theory of arithmeticAll of the Peano axioms except the ninth axiom (the induction axiom) are statements in firstorder logic.{{sfnParteeTer MeulenWall2012page=215}} The arithmetical operations of addition and multiplication and the order relation can also be defined using firstorder axioms. The axiom of induction is in secondorder, since it quantifies over predicates (equivalently, sets of natural numbers rather than natural numbers), but it can be transformed into a firstorder axiom schema of induction. Such a schema includes one axiom per predicate definable in the firstorder language of Peano arithmetic, making it weaker than the secondorder axiom.{{sfnpHarsanyi1983}}Firstorder axiomatizations of Peano arithmetic have an important limitation, however. In secondorder logic, it is possible to define the addition and multiplication operations from the successor operation, but this cannot be done in the more restrictive setting of firstorder logic. Therefore, the addition and multiplication operations are directly included in the signature of Peano arithmetic, and axioms are included that relate the three operations to each other.The following list of axioms (along with the usual axioms of equality), which contains six of the seven axioms of Robinson arithmetic, is sufficient for this purpose:{{sfnMendelson1997page=155}}
forall bar{y} (varphi(0,bar{y}) land forall x ( varphi(x,bar{y})Rightarrowvarphi(S(x),bar{y})) Rightarrow forall x varphi(x,bar{y}))
where bar{y} is an abbreviation for y1,...,yk. The firstorder induction schema includes every instance of the firstorder induction axiom, that is, it includes the induction axiom for every formula Ï†.Equivalent axiomatizationsThere are many different, but equivalent, axiomatizations of Peano arithmetic. While some axiomatizations, such as the one just described, use a signature that only has symbols for 0 and the successor, addition, and multiplications operations, other axiomatizations use the language of ordered semirings, including an additional order relation symbol. One such axiomatization begins with the following axioms that describe a discrete ordered semiring.{{sfnKaye1991pages=16â€“18}}
