A book explaining power and limitations of Peano Axioms? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T04:09:32Z http://mathoverflow.net/feeds/question/18922 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18922/a-book-explaining-power-and-limitations-of-peano-axioms A book explaining power and limitations of Peano Axioms? Sergei Ivanov 2010-03-21T11:37:54Z 2010-03-22T14:33:54Z <p>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.)</p> <p>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?</p> <p>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?)</p> <p>Background: I am as far from logic as a mathematician can be.</p> http://mathoverflow.net/questions/18922/a-book-explaining-power-and-limitations-of-peano-axioms/18943#18943 Answer by Aaron Bergman for A book explaining power and limitations of Peano Axioms? Aaron Bergman 2010-03-21T18:17:26Z 2010-03-21T18:17:26Z <p>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</p> <p><a href="http://www.math.niu.edu/~rusin/known-math/95/independence" rel="nofollow">http://www.math.niu.edu/~rusin/known-math/95/independence</a></p> http://mathoverflow.net/questions/18922/a-book-explaining-power-and-limitations-of-peano-axioms/18950#18950 Answer by François G. Dorais for A book explaining power and limitations of Peano Axioms? François G. Dorais 2010-03-21T19:45:17Z 2010-03-21T23:56:18Z <p>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.</p> <p>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 <em>Models of Peano Arithmetic</em> (Oxford Logic Guides 15, OUP, 1991). It's pretty accessible, but I think it's out of print. Another is <em>Metamathematics of First-Order Arithmetic</em> (available on <a href="http://projecteuclid.org/euclid.pl/1235421927" rel="nofollow">Project Euclid</a>) 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 <em>Subsystems of Second-Order Arithmetic</em> (2nd ed, CUP, 2010) is the canonical choice. The early parts are very accessible but the later chapters are much denser.</p> <hr> <p>Examples for (2) include:</p> <ul> <li><a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems" rel="nofollow">Gödel's Incompleteness Theorems</a></li> <li><a href="http://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem" rel="nofollow">Paris&ndash;Harrington Theorem</a></li> <li><a href="http://en.wikipedia.org/wiki/Goodstein%27s_theorem" rel="nofollow">Goodstein's Theorem</a> (mentioned by Aaron Bergman)</li> <li><a href="http://math.andrej.com/2008/02/02/the-hydra-game/" rel="nofollow">Kirby&ndash;Paris Hydra Games</a></li> </ul> http://mathoverflow.net/questions/18922/a-book-explaining-power-and-limitations-of-peano-axioms/19007#19007 Answer by Joel David Hamkins for A book explaining power and limitations of Peano Axioms? Joel David Hamkins 2010-03-22T12:49:36Z 2010-03-22T14:33:54Z <p>If one adopts a higher order attitude towards PA, then one makes the transition from reasoning <em>within</em> PA to wanting to understand the structure of all the <em>models</em> 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. </p> <p>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: </p> <ul> <li><a href="http://books.google.com/books?id=INxo07_kCCsC&amp;printsec=frontcover#v=onepage&amp;q=&amp;f=false" rel="nofollow">Roman Kossak and James Schmerl, The Structure of Models of Peano Arithmetic</a></li> </ul> <p>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.</p> http://mathoverflow.net/questions/18922/a-book-explaining-power-and-limitations-of-peano-axioms/19012#19012 Answer by Neel Krishnaswami for A book explaining power and limitations of Peano Axioms? Neel Krishnaswami 2010-03-22T13:46:06Z 2010-03-22T13:46:06Z <p>Several people have given excellent answers to your second question, so let me address the first. </p> <blockquote> <p>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?</p> </blockquote> <p>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. </p> <p>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). </p> <p>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 <em>Subsystems of Second-Order Arithmetic</em> is the standard reference here. </p>