Logical number theory I. An introduction (Q1188945)

This book is a most enjoyable one to read, combining the spellbinding style of a good mystery novel with meticulous coverage of technical details. The author's numerous, personable remarks on the mathematical history of various developments, excellent exercises, alternate proofs of certain important results, together with extensive reading lists and an index create a most accessible introduction to formal arithmetic, elementary recursion theory and Hilbert's tenth problem for the advanced undergraduate or beginning graduate student. By taking the time to include certain developments not usually treated, Smoryński's book may as well prove valuable to active logicians --- for example, there is a good exposition of variants of Raphael Robinson's theories \({\mathcal R}\) and \(Q\) of arithmetic, a treatment of quantifier-elimination and decidability of Skolem arithmetic (the theory of multiplication without addition), and an exposition of Dirichlet's proof of existence of integral solutions to Pell's equation \(X^ 2 -dY^ 2 = 1\) for positive non-square \(d\). Some interesting but tangential topics are treated, such as the Fueter-Pólya result showing that the only real polynomial bijective pairing function is the usual Cantor function \(\langle x,y \rangle = {{(x + y)(x + y + 1)}\over {2}} + x\) or that obtained by permutation of \(x,y\). Quite in keeping with the personable style of the book, the author at times ventures onto ground upon which few would dare to trod. For instance, pp. 193-196 describe the controversy concerning whether and to what extent credit should be given for the independent (of Matijasevič) solution of Hilbert's tenth problem with the appearance of Chudnovsky's abstract in Russian in 1970. This discussion provides the occasion for other anecdotes concerning the priority of mathematical work and may shed light on the human activity of ``doing mathematics'' for undergraduate and beginning graduate students. This particular passage on p. 196 ends with ``But enough. My head is swimming with anecdotes that I'd love to tell, but I shall probably get into enough hot water over this last one \(\dots\)'' A brief overview of the book. \textit{Chapter I:} pairing functions and the Fueter-Pólya result, Chinese remainder theorem, \(\beta\) function, primitive recursive functions, elementary recursion theory. \textit{Chapter II:} exponential diophantine equals recursively enumerable (both the proof of Davis-Putnam-Robinson and of Jones-Matijasevič), Pell equation, diophantine equals recursively enumerable (with attention to the number of variables and degree of polynomial). \textit{Chapter III:} sequent calculus, completeness theorem, Presburger and Skolem arithmetic, quantifier elimination and decidability, Gödel incompleteness theorem, weak theories of arithmetic. I found very few typographic mistakes: for instance the correction on p. 224 line 9 should read ``\([m/p^ 2] - [m/p^ 3]\)''. Smoryński's treatment of Matijasevič's theorem (MT) is sufficiently detailed, that one might hope that the groundwork is set for an exposition in volume 2 of the work on formalizations of (MT) due to Dimitracopoulos-Gaifman (MT is provable in bounded induction arithmetic with exponentiation) and due to Kaye (MT is provable in the theory of induction for pure existential formulas, even without parameters). The forthcoming volume 2 promises to cover combinatorial independence results. Depending on the other contents of this forthcoming second volume, I would hope that Smoryński's work will provide the motivation, together with requisite background tools, to entice advanced undergraduates and beginning graduate students into this field in preparing the next generation of mathematical logicians to solve some of the main outstanding questions in the subject of arithmetic: such as (1) whether bounded arithmetic \(I\Delta_ 0\) proves the bounded Matijasevič theorem (posed by Paris and Wilkie, known that positive solution implies equality of NP and co-NP), (2) whether \(I\Delta_ 0\) proves the pigeonhole principle (posed by Macintyre), stated as a scheme for all \(\Delta_ 0\) graphs (work by Ajtai, and very recently by Beame, Impagliazzo, Krajíček, Pitassi, Pudlák and Woods shows the independence of the relativized version using boolean circuit complexity), (3) whether the property of having a proper end extension is equivalent to collection for \(\Sigma_ 1\) formulas (posed by Paris and Wilkie), etc.