View source for Talk:Peano axioms

The Peano axioms page has some problems, stemming (probably) from the its migration to the E of M Wiki-environment.

I noticed the problems while developing the [[Hilbert 2nd problem]] page, on which I will be putting a link to the Peano axioms page.

I have done the following:
* reconstructed much of the Peano axioms page using Tex
* added some material that was lost in the migration to E of M
* adjusted some spacing and wording for clarity
* added a few remarks of additional historical interest

There is still an outstanding problem: something is missing on the page with the following text, but I have not yet determined exactly what is missing:

::All the axioms are independent, but

::and

::can be combined to a single one:

The result of my work on this page is shown below.
I am loath to change the page before someone has looked at what I my results.
Please advise [[User:Whayes43|William Hayes]] ([[User talk:Whayes43|talk]]) 17:23, 12 June 2015 (CEST)

- - - - -

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

# $0 \in \mathbb{N}$
# $x \in \mathbb{N} \to Sx \in \mathbb{N}$
# $x \in \mathbb{N} \to Sx \neq 0$
# $x \in \mathbb{N} \wedge y \in \mathbb{N} \wedge Sx =Sy \to x = y$
# $0 \in M \wedge \forall x (x\in M \to Sx\in M) \to \mathbb{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

and

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/p07188017.png" /></td> </tr></table>

if one defines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071880/p07188018.png" /> as

<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>

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 $\mathbb{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 $\mathbb{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|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|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).

== Remark(s) ==

"Dedekind proved that all systems of Peano axioms with such a second-order axiom of induction are categorical. " — As for me, there is just one "system of Peano axioms" (and it is written above in full, 1-5), and this system of axioms is categorical (that is, all its models are mutually isomorphic). [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 18:52, 12 June 2015 (CEST)

:Apparently systems of Peano arithmetic axiomatized with a second-order axiom of induction are categorical, but systems of Peano arithmetic axiomatized with a first-order axiom of induction allow for both standard and non-standard models. The first-order induction axiom has the effect of producing a "weaker" system overall, with the result that its models are not all isomorphic. Here's a link to [http://www.xamuel.com/the-axioms-of-peano-arithmetic-modern-version/ First-Order Axioms of Peano Arithmetic]

::OK, I understand the difference between first and second order; my remark was more terminological: the word "categorical" applies to axiomatic systems (and not models), while the word "isomorphic" - to models (and not axiomatic systems). Accordingly, Dedekind proved categoricity for just a single object (the five-axiom system of second order). [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 19:29, 13 June 2015 (CEST)

"The isomorphism is determined by a function $f(x,y)$" — I am puzzled. Why not $f(x)$? True, this is written in the article, and still, I do not understand, how does it correspond to the notion of [[isomorphism]]. Do you? [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 19:00, 12 June 2015 (CEST)

:I must look at this, but feel that I may be over my head. Except for translating to TEX, I have left most of the formalizations as they were in the original article, hoping that the author knew what he was talking about! :-)

"for axiom 1, such a model is the set of natural numbers beginning with 1" — Really? What about the occurrence of "0" in axiom 5? [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 19:09, 12 June 2015 (CEST)

:Yes, there is $0$ in axiom 5, but that $0$ is said to be in set $M$.. Hence, $S0$ is also in set $M$. But neither $0$ nor $S0$ are in $\{1, 2,3, ...\}$. So axiom 1 is false, but since $\mathbb{N} \subseteq M$ then axiom 5 is true -- I think. [[User:Whayes43|William Hayes]] ([[User talk:Whayes43|talk]]) 03:03, 13 June 2015 (CEST)

"for axiom 5, it is the set $\mathbb{N} \cup \{-1\}$" — Really? What about $S(-1)$? [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 19:14, 12 June 2015 (CEST)

:Ah, I assume that whoever constructed the example intended something like $S-1 = -1$. This makes axiom 5 false, but none of the others -- I think. [[User:Whayes43|William Hayes]] ([[User talk:Whayes43|talk]]) 03:03, 13 June 2015 (CEST)

I considered replacing the example sets used in the original article with examples used by other authors, such as these below accessed at http://www.fen.bilkent.edu.tr/~franz/nt/ch1.pdf :
* the set N = {1, 2, 3, . . .}
* the set N = {0}
* the set N = {0}
*  the set N = {0, 1} with S0 = 1 and  S1 = 0
* the set N = N ∪ (N+ω), where ω is a symbol, N = {0, 1, 2, . . .} and N+ω = {0+ω, 1+ω, 2+ω . . .}, with Sn = n+1 and Sn+ω = (n+1)+ω for all n ∈ N
In the end, Ithought it best to leave the examples unchanged.[[User:Whayes43|William Hayes]] ([[User talk:Whayes43|talk]]) 12:31, 13 June 2015 (CEST)

:Rather strange; the author, G.E. Mints,  should indeed know what he is talking about, and still, some points are puzzling. Maybe one day someone acquainted better with works of Peano and Dedekind will improve the article (by corrections and/or clarifications, as needed). [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 13:38, 13 June 2015 (CEST)

::So, all things considered, I would like to update the page (converting to TEX and making other changes noted at the top of this discussion) by replacing it with my revision (shown immediately above). Doing this would, I feel, not only constitute a small step forward, but also facilitate any future clarifications/corrections by others. However, I will not do this unless you approve. :-) [[User:Whayes43|William Hayes]] ([[User talk:Whayes43|talk]]) 17:22, 13 June 2015 (CEST)

:::Hmmm, what should it really mean, my approval? I understand (and agree) that some troubles will remain for some unknown (but hopefully finite) time. I only add another remark about "all systems ... are categorical" (above); shouldn't it be "the system ... is categorical"? [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 19:29, 13 June 2015 (CEST)

::::Yes, of course, it's exactly as you wrote above!:
::::::the (single) system of Peano axioms with 2nd-order induction is categorical
::::::the (multiple) models of that system are isomorphic.
:::: I didn't take in that your concern was about my terminology, which I unwittingly carried forward from the original article -- my loss of focus from staring too long at a small screen. I will include a change that clarifies your point. Many thanks for your thoughtful help with this article. [[User:Whayes43|William Hayes]] ([[User talk:Whayes43|talk]]) 18:33, 14 June 2015 (CEST)

Nice. And for an indefinite future I cannot resist to note that the conditions on the function $f(x,y)$ are incompatible.  Indeed, $f(1,0)=0'$ (though, as written, it is $0$), since $0<1$; now, $f(1,1)=0'$ since $f(1,S0)=f(1,0)$; and on the other hand, $f(1,1)=1'$ since $f(S0,S0)=S'f(0,0)=S'0'$. [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 19:31, 14 June 2015 (CEST)

::Yes, the article's statement of the isomorphism function $f(x,y)$ for the models $(\mathbf{N}, S, 0)$ and $(\mathbf{N}', S', 0')$ is confounding. As you questioned above, why is it not stated simply as $f(x)$, with $f(0) = 0'$ and $f(Sx) = S'f(x)$?

:::I do not know. Nowadays, it should be so. But, again, I did not see the historic works... maybe Dedekind went that way, but something is a bit distorted in the article, and regretfully his idea is not explained here? Or maybe all that is a wild distortion of the original text of Mints? But no, the phrase
::::"The existence of $f(x, y)$ for all pairs $(x, y)$ and the mutual single-valuedness for $x \leq y$ are proved by induction"
:::shows that pairs are really meant. There should be a reason... [[User:Boris Tsirelson|Boris Tsirelson]] ([[User talk:Boris Tsirelson|talk]]) 17:35, 15 June 2015 (CEST)