Peano arithmetic

The theory of Peano Arithmetic, or PA, is the theory in the formal language with usual logical symbols, symbols for +, ., <, 0, 1, variables x,y,z,... (thought as ranging over natural numbers). The axioms of PA state that the domain is the nonnegative part of a discretely ordered ring, satisfying the induction principle

phi(0) and  forall x ( phi(x) -> phi(x+1) ) implies forall x phi(x)
for all statements phi(x) expressible in the above language.

The theory of Presburger Arithmetic is essentially the same, but the language is restricted so that it only contains symbols for +, <, 0, 1, and the usual logical symbols.

Some introductory texts on Peano arithmetic include

  1. Richard Kaye, Models of Peano arithmetic. Oxford Logic Guides 15, OUP 1991, ISBN 0 19 853213 X, 292 pages. ---Concentrates of the model theory of PA, should be readable by any student with a minimal amount of background in first-order logic and in computability.
  2. Craig Smorynski, Logical Number Theory I. Springer Verlag Universitext, 1991, ISBN 0-387-52236-0. ---Idiosyncratic, but highly entertaining. Includes some material on Presburger[-Skolem] arithmetic.
  3. Petr Hajek and Pavel Pudlak, Metamathematics of First-order Arithmetic. Springer Verlag Perspectives in Mathematical Logic, 1993, ISBN 0-387-50632-2, ISBN 3-540-50632-2. ---Almost encyclopaedic in places, and probably difficult reading for a newcomer to the area. Contains a useful account of bounded arithmetic.

Back to Richard Kaye's home page