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.



A book explaining power and limitations of Peano Axioms?
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](http://projecteuclid.org/euclid.pl/1235421927)) 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](http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems)
* [Paris–Harrington Theorem](http://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem)
* [Goodstein's Theorem](http://en.wikipedia.org/wiki/Goodstein%27s_theorem) (mentioned by Aaron Bergman)
* [Kirby–Paris Hydra Games](http://math.andrej.com/2008/02/02/the-hydra-game/)


