Peano axioms

From Wikipedia for FEVERv2
(Redirected from Peano arithmetic)
Jump to navigation Jump to search

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. Peano axioms_sentence_0

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. Peano axioms_sentence_1

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. Peano axioms_sentence_2

In 1881, Charles Sanders Peirce provided an axiomatization of natural-number arithmetic. Peano axioms_sentence_3

In 1888, Richard Dedekind proposed another axiomatization of natural-number 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 (Latin: Arithmetices principia, nova methodo exposita). Peano axioms_sentence_4

The nine Peano axioms contain three types of statements. Peano axioms_sentence_5

The first axiom asserts the existence of at least one member of the set of natural numbers. Peano axioms_sentence_6

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". Peano axioms_sentence_7

The next three axioms are first-order statements about natural numbers expressing the fundamental properties of the successor operation. Peano axioms_sentence_8

The ninth, final axiom is a second order statement of the principle of mathematical induction over the natural numbers. Peano axioms_sentence_9

A weaker first-order system called Peano arithmetic is obtained by explicitly adding the addition and multiplication operation symbols and replacing the second-order induction axiom with a first-order axiom schema. Peano axioms_sentence_10

Formulation Peano axioms_section_0

When Peano formulated his axioms, the language of mathematical logic was in its infancy. Peano axioms_sentence_11

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 axioms_sentence_12

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. Peano axioms_sentence_13

Peano was unaware of Frege's work and independently recreated his logical apparatus based on the work of Boole and Schröder. Peano axioms_sentence_14

The first axiom states that the constant 0 is a natural number: Peano axioms_sentence_15

The next four axioms describe the equality relation. Peano axioms_sentence_16

Since they are logically valid in first-order logic with equality, they are not considered to be part of "the Peano axioms" in modern treatments. Peano axioms_sentence_17

The remaining axioms define the arithmetical properties of the natural numbers. Peano axioms_sentence_18

The naturals are assumed to be closed under a single-valued "successor" function S. Peano axioms_sentence_19

Peano's original formulation of the axioms used 1 instead of 0 as the "first" natural number. Peano axioms_sentence_20

This choice is arbitrary, as these axioms do not endow the constant 0 with any additional properties. Peano axioms_sentence_21

However, because 0 is the additive identity in arithmetic, most modern formulations of the Peano axioms start from 0. Peano axioms_sentence_22

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. Peano axioms_sentence_23

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. Peano axioms_sentence_24

Put differently, they do not guarantee that every natural number other than zero must succeed some other natural number. Peano axioms_sentence_25

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. Peano axioms_sentence_26

The induction axiom is sometimes stated in the following form: Peano axioms_sentence_27

In Peano's original formulation, the induction axiom is a second-order axiom. Peano axioms_sentence_28

It is now common to replace this second-order principle with a weaker first-order induction scheme. Peano axioms_sentence_29

There are important differences between the second-order and first-order formulations, as discussed in the section § First-order theory of arithmetic below. Peano axioms_sentence_30

Arithmetic Peano axioms_section_1

The Peano axioms can be augmented with the operations of addition and multiplication and the usual total (linear) ordering on N. Peano axioms_sentence_31

The respective functions and relations are constructed in set theory or second-order logic, and can be shown to be unique using the Peano axioms. Peano axioms_sentence_32

Addition Peano axioms_section_2

Addition is a function that maps two natural numbers (two elements of N) to another one. Peano axioms_sentence_33

It is defined recursively as: Peano axioms_sentence_34

For example: Peano axioms_sentence_35

The structure (N, +) is a commutative monoid with identity element 0. Peano axioms_sentence_36

(N, +) is also a cancellative magma, and thus embeddable in a group. Peano axioms_sentence_37

The smallest group embedding N is the integers. Peano axioms_sentence_38

Multiplication Peano axioms_section_3

Similarly, multiplication is a function mapping two natural numbers to another one. Peano axioms_sentence_39

Given addition, it is defined recursively as: Peano axioms_sentence_40

Inequalities Peano axioms_section_4

The usual total order relation ≤ on natural numbers can be defined as follows, assuming 0 is a natural number: Peano axioms_sentence_41

Peano axioms_description_list_0

  • For all a, b ∈ N, a ≤ b if and only if there exists some c ∈ N such that a + c = b.Peano axioms_item_0_0

Peano axioms_unordered_list_1

  • a + c ≤ b + c, andPeano axioms_item_1_1
  • a · c ≤ b · c.Peano axioms_item_1_2

Thus, the structure (N, +, ·, 1, 0, ≤) is an ordered semiring; because there is no natural number between 0 and 1, it is a discrete ordered semiring. Peano axioms_sentence_42

The axiom of induction is sometimes stated in the following form that uses a stronger hypothesis, making use of the order relation "≤": Peano axioms_sentence_43

Peano axioms_description_list_2

  • For any predicate φ, ifPeano axioms_item_2_3
    • φ(0) is true, andPeano axioms_item_2_4
    • for every n, k ∈ N, if k ≤ n implies that φ(k) is true, then φ(S(n)) is true,Peano axioms_item_2_5
  • then for every n ∈ N, φ(n) is true.Peano axioms_item_2_6

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. Peano axioms_sentence_44

For example, to show that the naturals are well-ordered—every nonempty subset of N has a least element—one can reason as follows. Peano axioms_sentence_45

Let a nonempty X ⊆ N be given and assume X has no least element. Peano axioms_sentence_46

Peano axioms_unordered_list_3

  • Because 0 is the least element of N, it must be that 0 ∉ X.Peano axioms_item_3_7
  • For any n ∈ N, suppose for every k ≤ n, k ∉ X. Then S(n) ∉ X, for otherwise it would be the least element of X.Peano axioms_item_3_8

Thus, by the strong induction principle, for every n ∈ N, n ∉ X. Peano axioms_sentence_47

Thus, X ∩ N = ∅, which contradicts X being a nonempty subset of N. Thus X has a least element. Peano axioms_sentence_48

First-order theory of arithmetic Peano axioms_section_5

All of the Peano axioms except the ninth axiom (the induction axiom) are statements in first-order logic. Peano axioms_sentence_49

The arithmetical operations of addition and multiplication and the order relation can also be defined using first-order axioms. Peano axioms_sentence_50

The axiom of induction is in second-order, since it quantifies over predicates (equivalently, sets of natural numbers rather than natural numbers), but it can be transformed into a first-order axiom schema of induction. Peano axioms_sentence_51

Such a schema includes one axiom per predicate definable in the first-order language of Peano arithmetic, making it weaker than the second-order axiom. Peano axioms_sentence_52

The reason that it is weaker is that the number of predicates in first-order language is countable, whereas the number of sets of natural numbers is uncountable. Peano axioms_sentence_53

Thus, there exist sets that cannot be described in first-order language (in fact, most sets have this property). Peano axioms_sentence_54

First-order axiomatizations of Peano arithmetic have another technical limitation. Peano axioms_sentence_55

In second-order 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 first-order logic. Peano axioms_sentence_56

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. Peano axioms_sentence_57

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: Peano axioms_sentence_58

In addition to this list of numerical axioms, Peano arithmetic contains the induction schema, which consists of a recursively enumerable set of axioms. Peano axioms_sentence_59

For each formula φ(x, y1, ..., yk) in the language of Peano arithmetic, the first-order induction axiom for φ is the sentence Peano axioms_sentence_60

Equivalent axiomatizations Peano axioms_section_6

There are many different, but equivalent, axiomatizations of Peano arithmetic. Peano axioms_sentence_61

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. Peano axioms_sentence_62

One such axiomatization begins with the following axioms that describe a discrete ordered semiring. Peano axioms_sentence_63

Models Peano axioms_section_7

A model of the Peano axioms is a triple (N, 0, S), where N is a (necessarily infinite) set, 0 ∈ N and S: N → N satisfies the axioms above. Peano axioms_sentence_64

Dedekind proved in his 1888 book, The Nature and Meaning of Numbers (German: Was sind und was sollen die Zahlen?, i.e., “What are the numbers and what are they good for?”) that any two models of the Peano axioms (including the second-order induction axiom) are isomorphic. Peano axioms_sentence_65

In particular, given two models (NA, 0A, SA) and (NB, 0B, SB) of the Peano axioms, there is a unique homomorphism f : NA → NB satisfying Peano axioms_sentence_66

and it is a bijection. Peano axioms_sentence_67

This means that the second-order Peano axioms are categorical. Peano axioms_sentence_68

This is not the case with any first-order reformulation of the Peano axioms, however. Peano axioms_sentence_69

Set-theoretic models Peano axioms_section_8

Main article: Set-theoretic definition of natural numbers Peano axioms_sentence_70

The Peano axioms can be derived from set theoretic constructions of the natural numbers and axioms of set theory such as ZF. Peano axioms_sentence_71

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: Peano axioms_sentence_72

The set of natural numbers N is defined as the intersection of all sets closed under s that contain the empty set. Peano axioms_sentence_73

Each natural number is equal (as a set) to the set of natural numbers less than it: Peano axioms_sentence_74

and so on. Peano axioms_sentence_75

The set N together with 0 and the successor function s : N → N satisfies the Peano axioms. Peano axioms_sentence_76

Peano arithmetic is equiconsistent with several weak systems of set theory. Peano axioms_sentence_77

One such system is ZFC with the axiom of infinity replaced by its negation. Peano axioms_sentence_78

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. Peano axioms_sentence_79

Interpretation in category theory Peano axioms_section_9

The Peano axioms can also be understood using category theory. Peano axioms_sentence_80

Let C be a category with terminal object 1C, and define the category of pointed unary systems, US1(C) as follows: Peano axioms_sentence_81

Peano axioms_unordered_list_4

  • The objects of US1(C) are triples (X, 0X, SX) where X is an object of C, and 0X : 1C → X and SX : X → X are C-morphisms.Peano axioms_item_4_9
  • A morphism φ : (X, 0X, SX) → (Y, 0Y, SY) is a C-morphism φ : X → Y with φ 0X = 0Y and φ SX = SY φ.Peano axioms_item_4_10

Then C is said to satisfy the Dedekind–Peano axioms if US1(C) has an initial object; this initial object is known as a natural number object in C. If (N, 0, S) is this initial object, and (X, 0X, SX) is any other object, then the unique map u : (N, 0, S) → (X, 0X, SX) is such that Peano axioms_sentence_82

This is precisely the recursive definition of 0X and SX. Peano axioms_sentence_83

Nonstandard models Peano axioms_section_10

Although the usual natural numbers satisfy the axioms of PA, there are other models as well (called "non-standard models"); the compactness theorem implies that the existence of nonstandard elements cannot be excluded in first-order logic. Peano axioms_sentence_84

The upward Löwenheim–Skolem theorem shows that there are nonstandard models of PA of all infinite cardinalities. Peano axioms_sentence_85

This is not the case for the original (second-order) Peano axioms, which have only one model, up to isomorphism. Peano axioms_sentence_86

This illustrates one way the first-order system PA is weaker than the second-order Peano axioms. Peano axioms_sentence_87

When interpreted as a proof within a first-order 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. Peano axioms_sentence_88

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. Peano axioms_sentence_89

This situation cannot be avoided with any first-order formalization of set theory. Peano axioms_sentence_90

It is natural to ask whether a countable nonstandard model can be explicitly constructed. Peano axioms_sentence_91

The answer is affirmative as Skolem in 1933 provided an explicit construction of such a nonstandard model. Peano axioms_sentence_92

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. Peano axioms_sentence_93

This result shows it is difficult to be completely explicit in describing the addition and multiplication operations of a countable nonstandard model of PA. Peano axioms_sentence_94

There is only one possible order type of a countable nonstandard model. Peano axioms_sentence_95

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 ω + ζ·η, which can be visualized as a copy of the natural numbers followed by a dense linear ordering of copies of the integers. Peano axioms_sentence_96

Overspill Peano axioms_section_11

A cut in a nonstandard model M is a nonempty subset C of M so that C is downward closed (x < y and y ∈ C ⇒ x ∈ C) and C is closed under successor. Peano axioms_sentence_97

A proper cut is a cut that is a proper subset of M. Each nonstandard model has many proper cuts, including one that corresponds to the standard natural numbers. Peano axioms_sentence_98

However, the induction scheme in Peano arithmetic prevents any proper cut from being definable. Peano axioms_sentence_99

The overspill lemma, first proved by Abraham Robinson, formalizes this fact. Peano axioms_sentence_100

Consistency Peano axioms_section_12

Further information: Hilbert's second problem and Consistency Peano axioms_sentence_101

When the Peano axioms were first proposed, Bertrand Russell and others agreed that these axioms implicitly defined what we mean by a "natural number". Peano axioms_sentence_102

Henri Poincaré was more cautious, saying they only defined natural numbers if they were consistent; if there is a proof that starts from just these axioms and derives a contradiction such as 0 = 1, then the axioms are inconsistent, and don't define anything. Peano axioms_sentence_103

In 1900, David Hilbert posed the problem of proving their consistency using only finitistic methods as the second of his twenty-three problems. Peano axioms_sentence_104

In 1931, Kurt Gödel proved his second incompleteness theorem, which shows that such a consistency proof cannot be formalized within Peano arithmetic itself. Peano axioms_sentence_105

Although it is widely claimed that Gödel's theorem rules out the possibility of a finitistic consistency proof for Peano arithmetic, this depends on exactly what one means by a finitistic proof. Peano axioms_sentence_106

Gödel himself pointed out the possibility of giving a finitistic consistency proof of Peano arithmetic or stronger systems by using finitistic methods that are not formalizable in Peano arithmetic, and in 1958, Gödel published a method for proving the consistency of arithmetic using type theory. Peano axioms_sentence_107

In 1936, Gerhard Gentzen gave a proof of the consistency of Peano's axioms, using transfinite induction up to an ordinal called ε0. Peano axioms_sentence_108

Gentzen explained: "The aim of the present paper is to prove the consistency of elementary number theory or, rather, to reduce the question of consistency to certain fundamental principles". Peano axioms_sentence_109

Gentzen's proof is arguably finitistic, since the transfinite ordinal ε0 can be encoded in terms of finite objects (for example, as a Turing machine describing a suitable order on the integers, or more abstractly as consisting of the finite trees, suitably linearly ordered). Peano axioms_sentence_110

Whether or not Gentzen's proof meets the requirements Hilbert envisioned is unclear: there is no generally accepted definition of exactly what is meant by a finitistic proof, and Hilbert himself never gave a precise definition. Peano axioms_sentence_111

See also Peano axioms_section_13

Peano axioms_unordered_list_5


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Peano axioms.