4
$\begingroup$

If I understand correctly, Gödel was the one to discover how to encode finite sequences of integers in Peano Arithmetic, with his Chinese Remainder Theorem trick (his "beta function"). As a consequence, one can do exponentiation in PA, and many other things.

My question is historical: What did people think PA was good for before Gödel? What did Peano think his arithmetic was good for? Didn't he want to state (and prove) things like Fermat's little theorem, for example?

$\endgroup$
4
$\begingroup$

When Gödel published his paper on the incompleteness theorems, nobody had identified "Peano arithmetic" as a particular theory. Gödel instead referred to a system based on Principia Mathematica. It quickly became clear to Gödel and others that the same principles would apply to any $\omega$-consistent, effective, consistent theory that includes a small amount of arithmetic.

But nobody had studied Peano Arithmetic in particular before the incompleteness theorems were published. The history of the development of logic is an epitome of how many mathematical areas are discovered: not in an orderly way, but in fits and starts with researchers working independently, duplicating some results and taking a long time to fill in what are later considered basic topics. In particular, the underlying topic of "first order logic" was not really clear until the late 1940s or 1950s, when people had finally had enough time to digest the various results of the previous 50 years and organize them into a coherent system.

Before Gödel, Peano and Dedekind had both proposed axiomatic systems for arithmetic. These systems were second-order, however - they presupposed a notion of "set", which they did not axiomatize. So proving things from these axioms requires using not only the axioms, but also principles about set existence. We often call these the Peano axioms or the Peano postulates to differentiate them from Peano Arithmetic.

One of the key differences between these systems and the theory called "Peano Arithmetic" is that Peano Arithmetic is fully axiomatized, without assuming any background theory of sets. So it is possible to write formal proofs of many arithmetical statements fully from the axioms of PA, unlike the Peano axioms.

I am not sure of the first appearance of the specific axioms for Peano Arithmetic in print, or who coined that name for it. If I had them at hand, I would look at Kleene's Introduction to Metamathematics and Robinson's paper establishing Robinson Arithmetic, both from the 1950s, to see if they give any clue.

$\endgroup$
  • $\begingroup$ So Gödel was purposely trying to see how much he could "lean out" a theory and still get his incompleteness result? I would gladly check out in Kleene's book, but the problem is that an interlibrary loan takes about three weeks... So I prefer asking here $\endgroup$ – Gabriel Nivasch Jan 3 '16 at 15:09
  • 1
    $\begingroup$ Gödel didn't do that at all - he just pointed out in his paper that what he did could be formalized in the system from Principia Mathematica, which was not at all a lean theory. Robinson's arithmetic Q was designed to be as lean as possible while still having enough arithmetic to satisfy the first incompleteness theorem. $\endgroup$ – Carl Mummert Jan 3 '16 at 15:31
3
$\begingroup$

Giuseppe Peano and Richard Dedekind proposed the (second order) set of axioms for arithmetic, now usually called Peano axioms, as a set of postulates sufficient to derive all known arithmetical theorems.

We usually refer to Peano arithmetic as the first-order version of Peano axioms.

The original versions of Peano : Arithmetices principia: nova methodo exposita (1889) and Dedekind : Was sind und was sollen die Zahlen? (1893) used the second-order version of the Induction axiom.

See Peano's version :

if $k$ is a Class and $1 \in k$ and $x \in \mathbb N$ and $\forall x ((x \in k) \to (x+1 \in k))$, then $\mathbb N \subseteq k$.


We can find the first-order version of Peano axioms in :

  • David Hilbert and Paul Bernays, Grundlagen der Mathematik (Vol. I, II), 1st German ed.1934/1939; see page 380 of 2nd German ed.1968 :

Axiomensystem Z :

$a = b \to (A(a) \to A(b))$,

$a' \ne 0$,

$a' = b' \to a = b$,

$a + 0 = a$,

$a + b' = (a + b)'$

$a' 0 = 0$,

$a . b' = a . b + a$,

$A (0) \land (x)(A (x) \to A (x')) \to A (a)$.


It seems that the use of "Peano arithmetic" to name the first-order theory of arithmetic is due to Undecidable Theories by A.Tarski, A.Mostowski, and R.M.Robinson (1953).

$\endgroup$
  • $\begingroup$ Thanks. So did they define both systems -- the stronger "Peano axioms" and the weaker "Peano arithmetic" -- at the same time? And what was their reason for defining them? And are the stronger "Peano axioms" equivalent in strength to ZFC, or are they built on top of ZFC? Sorry I'm kind of confused... $\endgroup$ – Gabriel Nivasch Jan 3 '16 at 14:23
  • $\begingroup$ Something is off here. The consistency of second-order arithmetic is a known arithmetical theorem, which is not derivable from the Peano axioms. A challenge with the Peano axioms is that they do not specify the set-theoretic assumptions that could be used, so it is actually hard to prove much at all from the Peano postulates alone. $\endgroup$ – Carl Mummert Jan 3 '16 at 14:32
  • 1
    $\begingroup$ 1889 and 1893 ... there was no ZF there was no ZFC. They used "sets", for which no axioms were given or desired at that time. $\endgroup$ – GEdgar Jan 3 '16 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.