A book explaining power and limitations of Peano Axioms?

Question

Are there books or survey articles explaining the subject to a non-expert? To clarify what I mean, here is a couple of issues that I would like to read about. (I am mainly interested in references but would appreciate answers to these specific questions.)

1) As far as I remember, PA do not have a "built-in" scheme for inductive definitions. So I assume that it is not immediately clear how to define things like $x^n$ or the $n$th Fibonacci number. How do they do things like that? One can define some specific coding of finite sequences of numbers and use that, but this is so ugly and so specific to aritmetics, it there a better way?

2) I vaguely remember that there are arithmetic facts provable in ZF but not in PA. Is this indeed the case? Are there simple explicit examples? Is there a way to understand, at least informally, why PA is not enough? (E.g. a proof may use analysis but why cannot it be reformulated in terms of some kind of "constructible" numbers and functions?)

Background: I am as far from logic as a mathematician can be.

Answer 1

For obvious reasons, foundations textbooks (undergraduate or beginning graduate level) tend to have essentially no prerequisites, so I suspect you will find most of them to be accessible.

Here are some higher level recommendations that are more to the point. These assume some rudimentary knowledge of Computability Theory and Model Theory. One well-written book that directly addresses your question is Richard Kaye's Models of Peano Arithmetic (Oxford Logic Guides 15, OUP, 1991). It's pretty accessible, but I think it's out of print. Another is Metamathematics of First-Order Arithmetic (available on Project Euclid) by Hájek and Pudlák. This one is still available but I wouldn't recommend it to a beginner. For second-order arithmetic and it's relationship to mainstream mathematics, Simpson's Subsystems of Second-Order Arithmetic (2nd ed, CUP, 2010) is the canonical choice. The early parts are very accessible but the later chapters are much denser.

---

Examples for (2) include:

• Gödel's Incompleteness Theorems
• Paris–Harrington Theorem
• Goodstein's Theorem (mentioned by Aaron Bergman)
• Kirby–Paris Hydra Games

Answer 2

Several people have given excellent answers to your second question, so let me address the first.

2) As far as I remember, PA do not have a "built-in" scheme for inductive definitions. So I assume that it is not immediately clear how to define things like $x_n$ or the $n$-th Fibonacci number. How do they do things like that? One can define some specific coding of finite sequences of numbers and use that, but this is so ugly and so specific to aritmetics, it there a better way?

Permitting definitions by primitive recursion moves you from Peano arithmetic to Godel's System T. This is a conservative extension of Peano arithmetic, which also allows defining functions by recursion over the natural numbers.

In the modern presentation (due to Tait, IIRC), the idea is that we move from a first-order logic with a domain of natural numbers, to a multi-sorted first-order logic, where quantification is permitted over functions of higher type in addition. So the sorts of the logic are types like $\mathbb{N}$, $\mathbb{N} \to \mathbb{N}$, $(\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$, and so on. The terms of higher type are given by a simple typed lambda calculus (i.e., a simple functional programming language).

One of the nice things about System T is that even though it is conservative over Peano arithmetic, it also makes the step from arithmetic to analysis much easier to see. Since a real number can be represented by a term of type $\mathbb{N} \to \mathbb{N} \times \mathbb{N}$ (e.g, as a Cauchy sequence of rationals), in this setting it's easy to understand exactly how much extra axiomatic strength various theorems of analysis need beyond basic Peano arithmetic. As F.G. Dorais has already mentioned, Simpson's Subsystems of Second-Order Arithmetic is the standard reference here.

Answer 3

If one adopts a higher order attitude towards PA, then one makes the transition from reasoning within PA to wanting to understand the structure of all the models of PA, of which there is a rich diversity. This move is analogous to the common change in viewpoint one undergoes in abstract algebra, moving at first from studying an individual group or ring from inside, using the axioms directly, to studying structure theorems about all groups or all rings from the outside, and exploring especially how they relate to each other.

Indeed, many of the most fascinating aspects of PA as a first order theory, such as the independence results mentioned in the other answers, flow from the fact that there are so many different models of PA. Perhaps the most authoritive book on the structure of the models of Peano Arithmetic is:

• Roman Kossak and James Schmerl, The Structure of Models of Peano Arithmetic

This book investigates the collection of all models of PA, analyzing their substructure lattices, saturation properties, various kinds of extensions, cuts, automorphisms, order types and so on. I highly recommend it. It appears to be aimed at students who have had already had some exposure to basic mathematical logic, and for this reason may be more advanced than you wanted.

Answer 4

There are people far more expert on this than I, but for the answer to (2), Goodstein's theorem is a famous example. There's a bit about it here

http://www.math.niu.edu/~rusin/known-math/95/independence

Answer 5

Regarding your first question ("How to define things like $x^n$ or the $n$-th Fibonacci number; one can define a coding of finite sequences but this is so ugly, is there a better way?")

No, that's the way. Using e.g. Gödel's "beta function" (which is based on the Chinese remainder theorem) you can code a finite sequence $(a_1, \ldots, a_k)$ by a pair of numbers $(a,m)$ (which, if desired, can be encoded as a single number using a pairing function).

Then, to write "$a^b=c$" you write "There exists a sequence $(a_0, \ldots, a_b)$ such that $a_0=1$, $a_b=c$, and $a_{i+1} = a\cdot a_i$ for each $i<b$."

(Or else you can write "For every finite sequence $(a_0, \ldots)$, if $a_0=1$ and $a_{i+1} = a\cdot a_i$ for each $i<b$, then $a_b=c$" -- if a "$\forall$" suits better than an "$\exists$" for your particular purpose.)

(There are other alternatives besides the beta function; see e.g. Nelson for a cute way of representing finite sets using binary notation inside base-4 notation.)