Namespaces
Variants
Actions

Difference between revisions of "Peano axioms"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A system of five axioms for the set of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p0718801.png" /> and a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p0718802.png" /> (successor) on it, introduced by G. Peano (1889):
+
{{TEX|done}}
 +
A system of five axioms for the set of natural numbers $\mathbf{N}$ and a function $S$ (successor) on it, introduced by G. Peano (1889):
  
1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p0718803.png" />;
+
# $0 \in \mathbf{N}$
 +
# $x \in \mathbf{N} \to Sx \in \mathbf{N}$
 +
# $x \in \mathbf{N} \to Sx \neq 0$
 +
# $x \in \mathbf{N} \wedge y \in \mathbf{N} \wedge Sx =Sy \to x = y$
 +
# $0 \in M \wedge \forall x (x\in M \to Sx\in M) \to \mathbf{N} \subseteq M$ for any property $M$ (axiom of induction).
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p0718804.png" />;
+
In the first version of his system, Peano used $1$ instead of $0$ in axioms 1, 3, and 5. Similar axioms were proposed by R. Dedekind (1888).
  
3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p0718805.png" />;
+
The axiom of induction (axiom 5) is a statement in second-order language. Dedekind proved that the system of Peano axioms with a second-order axiom of induction is categorical, that is, any two models $(\mathbf{N}, S, 0)$ and $(\mathbf{N}’, S', 0’)$ are mutually isomorphic. The isomorphism is determined by a function $f(x, y)$, where
  
4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p0718806.png" />;
+
::::$f(0,0) = 0’$, $f(Sx, Sx) = S’ f(x, x)$;
 +
::::$f(x, Sy) = f(x, y)$; $f(x, y) = 0$ for $y < x$.
  
5) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p0718807.png" /> for any property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p0718808.png" /> (axiom of induction).
+
The existence of $f(x, y)$ for all pairs $(x, y)$ and the mutual single-valuedness for $x \leq y$ are proved by induction.
  
In the first version 1 was used instead of 0. Similar axioms were proposed by R. Dedekind (1888). Peano's axioms are categorical, that is, any two systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p0718809.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188010.png" /> satisfying them are isomorphic. The isomorphism is determined by a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188011.png" />, where
+
Peano's axioms make it possible to develop number theory and, in particular, to introduce the usual arithmetic functions and to establish their properties.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188012.png" /></td> </tr></table>
+
All the axioms are independent, but (3) and (4) can be combined to a single one:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188013.png" /></td> </tr></table>
+
$$x\in\mathbf N\land y\in\mathbf N\land x<y\to x\neq y,$$
  
The existence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188014.png" /> for all pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188015.png" /> and the mutual single-valuedness for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188016.png" /> are proved by induction. Peano's axioms make it possible to develop number theory; in particular, to introduce the usual arithmetic functions and to establish their properties. All the axioms are independent, but
+
if one defines $x<y$ as
  
and
+
$$\forall M[M(Sx)\land\forall z(M(z)\to M(Sz))\to M(y)].$$
  
can be combined to a single one:
+
The independence of Peano’s axioms is proved by exhibiting, for each axiom, a model for which the axiom considered is false, but for which all the other axioms are true.
 +
For example:
 +
* for axiom 1, such a model is the set of natural numbers beginning with $1$
 +
* for axiom 2, it is the set $\mathbf{N} \cup \{1/2\}$, with $S0 = 1/2$ and $S1/2 =1$
 +
* for axiom 3, it is the set $\{0\}$
 +
* for axiom 4, it is the set $\{0, 1\}$, with $S0 = S1 = 1$
 +
* for axiom 5, it is the set $\mathbf{N} \cup \{-1\}$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188017.png" /></td> </tr></table>
+
Using this method, Peano provided a proof of independence for his axioms (1891).
  
if one defines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188018.png" /> as
+
Sometimes one understands by the term ''Peano arithmetic'' the system in the first-order language
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188019.png" /></td> </tr></table>
+
::with the function symbols
 +
::::$S, +, \cdot$,
 +
::consisting of axioms
 +
::::$Sx\neq 0$ and $Sx = Sy \to x = y$
 +
::defining equalities for $+$ and $\cdot$
 +
::::$x + 0 = x$ and $x + Sx = S(x + y)$
 +
::::$x \cdot 0 = 0$ and $x \cdot S(y) = x \cdot y + x$
 +
::and with the induction scheme
 +
::::$A (0) \wedge \forall x (A(x) \to A(Sx)) \to \forall x A(x)$
  
The independence is proved by exhibiting a model on which all the axioms are true except one. For
+
where $A$ is an arbitrary formula, known as the induction formula (see [[Arithmetic, formal|Arithmetic, formal]]).
  
such a model is the series of natural numbers beginning with 1; for
+
====References====
  
it is the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188020.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188022.png" />; for
+
* S.C. Kleene, ''Introduction to Metamathematics'', North-Holland (1951).
  
the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188023.png" />; for
+
====Comments====
 
 
the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188024.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188025.png" />; for
 
  
the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188026.png" />.
+
The system of Peano arithmetic in first-order language, mentioned at the end of the article, is no longer categorical (cf. also [[Categoric system of axioms|Categoric system of axioms]]), and gives rise to so-called non-standard models of arithmetic.
 
 
Sometimes one understands by Peano arithmetic the system in the first-order language with the function symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188027.png" />, consisting of the axioms
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188028.png" /></td> </tr></table>
 
 
 
defining equalities for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188030.png" />, and the induction scheme
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188031.png" /></td> </tr></table>
 
 
 
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188032.png" /> is an arbitrary formula, known as the induction formula (see [[Arithmetic, formal|Arithmetic, formal]]).
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.C. Kleene,  "Introduction to metamathematics" , North-Holland  (1951)</TD></TR></table>
 
 
 
 
====Comments====
 
The system of Peano arithmetic mentioned at the end of the article above is no longer categorical (cf. also [[Categoric system of axioms|Categoric system of axioms]]), and gives rise to so-called non-standard models of arithmetic.
 
  
====References====
+
* H.C. Kennedy, ‘’Peano. Life and works of Giuseppe Peano’’, Reidel (1980).
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H.C. Kennedy,   "Peano. Life and works of Giuseppe Peano" , Reidel (1980)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H.C. Kennedy,   "Selected works of Giuseppe Peano" , Allen &amp; Unwin (1973)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  E. Landau,   "Grundlagen der Analysis" , Akad. Verlagsgesellschaft (1930)</TD></TR></table>
+
* H.C. Kennedy, ‘’Selected works of Giuseppe Peano’’, Allen & Unwin (1973).
 +
* E. Landau, ‘’Grundlagen der Analysis’’, Akad. Verlagsgesellschaft (1930).

Latest revision as of 00:01, 1 December 2018

A system of five axioms for the set of natural numbers $\mathbf{N}$ and a function $S$ (successor) on it, introduced by G. Peano (1889):

  1. $0 \in \mathbf{N}$
  2. $x \in \mathbf{N} \to Sx \in \mathbf{N}$
  3. $x \in \mathbf{N} \to Sx \neq 0$
  4. $x \in \mathbf{N} \wedge y \in \mathbf{N} \wedge Sx =Sy \to x = y$
  5. $0 \in M \wedge \forall x (x\in M \to Sx\in M) \to \mathbf{N} \subseteq M$ for any property $M$ (axiom of induction).

In the first version of his system, Peano used $1$ instead of $0$ in axioms 1, 3, and 5. Similar axioms were proposed by R. Dedekind (1888).

The axiom of induction (axiom 5) is a statement in second-order language. Dedekind proved that the system of Peano axioms with a second-order axiom of induction is categorical, that is, any two models $(\mathbf{N}, S, 0)$ and $(\mathbf{N}’, S', 0’)$ are mutually isomorphic. The isomorphism is determined by a function $f(x, y)$, where

$f(0,0) = 0’$, $f(Sx, Sx) = S’ f(x, x)$; ::::$f(x, Sy) = f(x, y)$; $f(x, y) = 0$ for $y < x$. The existence of $f(x, y)$ for all pairs $(x, y)$ and the mutual single-valuedness for $x \leq y$ are proved by induction. Peano's axioms make it possible to develop number theory and, in particular, to introduce the usual arithmetic functions and to establish their properties. All the axioms are independent, but (3) and (4) can be combined to a single one: '"`UNIQ-MathJax2-QINU`"' if one defines $x<y$ as '"`UNIQ-MathJax3-QINU`"' The independence of Peano’s axioms is proved by exhibiting, for each axiom, a model for which the axiom considered is false, but for which all the other axioms are true. For example: * for axiom 1, such a model is the set of natural numbers beginning with $1$ * for axiom 2, it is the set $\mathbf{N} \cup \{1/2\}$, with $S0 = 1/2$ and $S1/2 =1$ * for axiom 3, it is the set $\{0\}$ * for axiom 4, it is the set $\{0, 1\}$, with $S0 = S1 = 1$ * for axiom 5, it is the set $\mathbf{N} \cup \{-1\}$ Using this method, Peano provided a proof of independence for his axioms (1891). Sometimes one understands by the term ''Peano arithmetic'' the system in the first-order language ::with the function symbols ::::$S, +, \cdot$, ::consisting of axioms ::::$Sx\neq 0$ and $Sx = Sy \to x = y$ ::defining equalities for $+$ and $\cdot$ ::::$x + 0 = x$ and $x + Sx = S(x + y)$ ::::$x \cdot 0 = 0$ and $x \cdot S(y) = x \cdot y + x$ ::and with the induction scheme ::::$A (0) \wedge \forall x (A(x) \to A(Sx)) \to \forall x A(x)$ where $A$ is an arbitrary formula, known as the induction formula (see Arithmetic, formal).

References

  • S.C. Kleene, Introduction to Metamathematics, North-Holland (1951).

Comments

The system of Peano arithmetic in first-order language, mentioned at the end of the article, is no longer categorical (cf. also Categoric system of axioms), and gives rise to so-called non-standard models of arithmetic.

References

  • H.C. Kennedy, ‘’Peano. Life and works of Giuseppe Peano’’, Reidel (1980).
  • H.C. Kennedy, ‘’Selected works of Giuseppe Peano’’, Allen & Unwin (1973).
  • E. Landau, ‘’Grundlagen der Analysis’’, Akad. Verlagsgesellschaft (1930).
How to Cite This Entry:
Peano axioms. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Peano_axioms&oldid=11715
This article was adapted from an original article by G.E. Mints (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article