Peano arithmetic

The Peano arithmetic (first-level, short- PA ) is a theory of arithmetic , so the natural numbers , within the predicate logic of first order. As axioms are Peano axioms used where the induction axiom by an axiom schema needs to be replaced. Since no statement about sets of objects is possible in first-order predicate logic, the axiom is required for every formula ${\displaystyle \phi (x,y_{1},\dots ,y_{k})}$

${\displaystyle \forall y_{1}\dots \forall y_{k}(\phi (0,y_{1},\dots ,y_{k})\land \forall x(\phi (x,y_{1},\dots ,y_{k})\rightarrow \phi (x+1,y_{1},\dots ,y_{k}))\rightarrow \forall x\phi (x,y_{1},\dots ,y_{k}))}$

Other first-level formalizations of the natural numbers that are related to Peano arithmetic are, for example, Robinson arithmetic and primitive recursive arithmetic , which also use parts of the Peano axioms.

incompleteness

According to Gödel's incompleteness theorems , Peano arithmetic is incomplete, that is, there are formulas in its language that it can neither prove nor disprove. In the proof of the first incompleteness theorem, Gödel constructs a rather artificial formula that only serves the purpose of proof and claims that it cannot be proven itself. In addition, there are also more natural mathematical statements that are known to be neither provable nor refutable. According to the second incompleteness theorem, these include the consistency of Peano arithmetic as well as Goodstein's theorem and the transfinite induction up to the ordinal number ε ₀ .

In fact, the Peano arithmetic is essentially incomplete ; That is, there is no (complete) extension that is consistent and whose axiomatization can be recursively enumerated.

Non-standard models

As with all theories of first order predicate logic that have an infinite model, the Löwenheim-Skolem-Tarski theorem can also be applied here. According to this, Peano arithmetic has models for every infinite cardinal number . The compactness theorem also implies the existence of countable models of arithmetic that are not too isomorphic, as Thoralf Skolem showed in 1934. To do this, consider the countable set of propositions as the set of axioms in Peano arithmetic , whose finite subsets are all satisfiable. ${\displaystyle \mathbb {N} }$ ${\displaystyle \Phi }$ ${\displaystyle \Phi \cup \{\,\neg x=n\mid n\in \{\mathbf {0} ,\mathbf {1} ,\dots \}\}}$

Because of the special importance of natural numbers, the PA standard model is often mentioned in this context . The other models are accordingly called non-standard models . ${\displaystyle \mathbb {N} }$

All non-standard countable models have the order type ω + η · π, where ω is the order type of natural numbers, π is the order type of integers and η is the order type of rational numbers. This corresponds to a copy of the natural numbers, followed by a countably infinite, dense set of copies of the whole numbers. In addition, the structure of the non-standard models can only be examined to a limited extent. According to Tennenbaum's theorem, there is no countable non-standard model in which addition or multiplication can be calculated .

consistency

In 1900, David Hilbert posed the second of the so-called Hilbert problems, the problem of proving the consistency of the Peano axioms only with finite means. In 1931 Kurt Gödel proved his incompleteness theorem , which shows that such a proof of consistency is not possible with the means of Peano arithmetic and thus with weaker means. A proof in the stronger, but not recognized as finite, Zermelo-Fraenkel set theory is possible. Whether a finite proof is still possible depends on the definition of “finite” means. Various proofs have been published that prove the consistency of arithmetic using means that cannot be proven in Peano arithmetic itself, but are nevertheless recognized as finite by many mathematicians. In 1936 Gerhard Gentzen published a proof of consistency using transfinite induction down to ε ₀ . In 1958 Gödel traced the consistency back to a type-theoretical system.

literature

• Hans Hermes : Introduction to Mathematical Logic . 2nd Edition. BG Teubner, Stuttgart 1969.
• H .-. D- Ebbinghaus, J. Flum, W. Thomas: Introduction to mathematical logic . 5th edition. Spectrum, 2007.
• Gerhard Gentzen : The consistency of pure number theory . In: Mathematische Annalen , 112, 1936, pp. 132-213.
• Kurt Godel : On formally undecidable propositions of Principia Mathematica and related systems I . In: Monthly books for mathematics and physics , 38. 1931, pp. 173–98.
• Kurt Gödel : About a previously unused extension of the finite point of view. In: Dialectica , 12, 1958, pp. 280-87.
• Richard Kaye: Models of Peano arithmetic . Oxford University Press, 1991. ISBN 0-19-853213-X .
• Wolfgang Rautenberg : measuring and counting . A simple construction of the real numbers. Heldermann Verlag, Lemgo 2007, ISBN 978-3-88538-118-1 .

Individual evidence

1. ↑ Thoralf Skolem: About the non-characterisability of the number series by means of finitely or countably infinite number of statements with only number variables . In: Fundam. Math. Band 23 , 1934, pp. 150-161 .