Modern Logic

Volume 8, Number 1/2 (January 1998–April 2000), pp. 154–158.

Review of
CRAIG SMORYŃSKI, LOGICAL NUMBER THEORY I,
AN INTRODUCTION
Berlin-Heidelberg-New York: Springer-Verlag Universitext, 1991
x + 405 pp. ISBN 3-540-53346-0 and ISBN 0-387-52236-0

RICHARD KAYE

Smoryński’s account of what he calls ‘logical number theory’ is an en-

tertaining account of some of the germs in mathematical logic and
‘arithmetic’, i.e., the theory of the natural number N, up to around
1970. The mathematics is sometimes very beautiful, the presentation
of it is always personal and highly idiosyncratic, and there are a great
number of remarks putting the material in its historical context. It
is intended to be read by anyone with sufficient mathematical back-
ground, such as an advanced undergraduate, or a beginning postgrad-
uate. Such a reader will find a combination of material from logic and
number theory with some interesting historical disgressions.
The title suggests that the book is concerned with number theory
first and foremost, and in particular those aspects of it that are best
studied using tools from a logician’s toolbox. The author has therefore
been able to make a rather free (and often refreshingly different) choice
of material. Typical here is the discussion of the Fueter-Pólya theorem
very early on in the book. This theorem concerns polynomials P (x, y)
that define bijections from N2 → N. One such polynomial, called
the pairing function was defined by Cantor, and is essentially hx, yi =
(x2 +2xy+y 2 +3x+y)/2. (Here, unlike, Cantor, we take the convention
that 0 is a natural number, so N = {0, 1, 2, 3, . . .}, and the definition of
Cantor’s pairing function has been modified accordingly.) The Fueter-
Pólya theorem states that the only quadratic polynomials P (x, y) over
the reals defining a bijection N2 → N are the Cantor pairings hx, yi
and hy, xi.
Of course, the pairing function or something like it is essential for any
study of logical number theory, but the Fueter-Pólya theorem, however
interesting it is, is not at all necessary, and is not referred to later
on in the book. Nevertheless, the issues it raises are fascinating and

c 2000 Modern Logic.

154
 REVIEW: LOGICAL NUMBER THEORY I 155

Smoryński gives a list of open problems, one of which asking whether

the assumption that P (x, y) be quadratic is necessary.
In fact, Smoryński does not give the full proof of the theorem just
stated — he gives an elementary case-by-case analysis proving a weaker
form of the theorem, and then quotes two results of number theory —
one being Lindemann’s theorem that eθ is transcendental for algebraic
θ 6= 0 and the other concerned with polynomial approximations of the
number of lattice points — to prove the main result. The decision to
do this seems to be the right one, since even this ‘shortened’ discussion
of the pairing function runs to some 28 pages.
The reviewed volume is organized into three long chapters on: arith-
metic definability; Hilbert’s tenth problem; and formal theories of arith-
metic. A second volume is promised, which would include amongst
other things, Gödel’s second incompleteness theorem, nonstandard mod-
els and the Paris-Harrington theorem, but to date (six years after the
publication of volume I) this sequel has not appeared yet.
The contents of the chapters can be summarized as follows. Chap-
ter I contains background on polynomials, the pairing function, the
Chinese remainder theorem and Gödel’s β function, primitive recur-
sion, the Ackermann function, computability, arithmetic definability
and the arithmetic hierarchy. Chapter II contains the negative solution
of Hilbert’s tenth problem on the solubility of diophantine equations,
firstly via Σ1 definability of r.e. predicates, exponential diophantine
equations and the Pell equation, then again via binomial coefficients
and register machines. A welcome discussion here concerns the (still
open) question concerning solubility of diophantine equations in the ra-
tionals and its equivalence to the problem of solving homogeneous equa-
tions over the integers. Chapter III starts with an outline of Hilbert’s
programme and an introduction to first-order logic via languages, struc-
tures and a Gentzen-style sequent calculus. The rest of this chapter
contains proofs of the decidability of the Presburger(-Skolem) arith-
metic of N with order and addition, and of Skolem arithmetic of N
with multiplication (for this, Cegielski’s axiomatization is presented),
and then (in contrast) the incompleteness and undecidability results of
Gödel, Rosser and others. It is pleasing to see Julia Robinson’s inter-
pretation of N in the ordered field of rationals appear in a text of this
type.
Smoryński’s style is characterized by a great number of lengthy —
some would say indulgent — digressions. In the main, these are histor-
ical remarks concerning the mathematics being discussed. Certainly,
I enjoyed these historical digressions hugely. Smoryński has read very
widely, and offers many insights into the historical background of his
156 RICHARD KAYE

subject. (I should state that I am not sufficiently expert to be sure

that the balance of his historical remarks is entirely fair to all the par-
ties he refers to, in particular in the questions of attribution of various
theorems.) In an ideal world, every mathematician would pay as much
attention to the history of his subject — but alas time is too short, or
general interest in such matters is too slight (especially by the funding
authorities, perhaps).
Occasionally Smoryński’s digressions are not quite as tangential as
they seem. For example, the machinery of finite differences, which
takes so much space at the very beginning of Chapter I, is apparently
only present to make the simple point that the standard convention
for
Pn−1writing a polynomial as a sum of powers with varying coefficients,
i
i=0 ai X , is not always the most convenient for all possible calcu-
lations. But to the author’s credit, this machinery is used profitably
later on in the chapter. It is somewhat irritating, however, that these
digressions and juxtapositions of seemingly unrelated material obscure
the overall direction of the book. His style will not be to everyone’s
taste, which is a pity as he has a great deal of interesting things to say.
Smoryński states in his preface that he ‘would not hesitate to use [the
book under discussion] as an introductory logic textbook in a mathe-
matics department’. As such he is presenting a quite refreshing view
of logic in the undergraduate curriculum as supporting mathematics,
presenting new methods, and giving an important methodological view
of mathematics. Whether his illustrations are intended for students or
professionals is another matter. For example, the notion of ‘definabil-
ity’ is introduced with the briefest mention of two classical nondefin-
ability results, Lindemann’s transcendence theorem and a reference to
Galois theory that may seem obscure to many readers.
The official definitions from logic that students typically find diffi-
cult, such as the notions of a first-order formula, a sentence, and of
bound and free variables, are put off as long as possible. Given suffi-
cient time in the undergraduate curriculum and provided the students
being taught have sufficient background mathematical knowledge and
motivation (two major provisos), this is a good starting point from
which to teach logic. But one of the effects of organizing the book
in this way is that its pace is rather uneven: much of the sections on
the more traditional aspects of logic are mathematically trivial (but
perhaps notationally complex), but these intersperse some much more
elegant and (for the typical undergraduate) sophisticated mathematics
in quite an unexpected and sometimes disconcerting way.
 REVIEW: LOGICAL NUMBER THEORY I 157

I agree with Smoryński that, as part of a mathematics degree, logic

should be taught in some context where interesting and nontrivial
mathematical conclusions can be drawn. Typical applications and ex-
ercises in standard logic textbooks rarely succeed in making the case
for logic as part of mathematics. A case in point is the familiar use
of the compactness theorem to reduce the problem of giving a four-
colouring of an infinite planar graph to the finite case, when quite
clearly all that is required is König’s lemma! On the other hand, non-
standard models and nonstandard methods are quite within the grasp
of those undergraduates who are able to follow the proof of the insol-
ubility of Hilbert’s tenth problem, and nonstandard number systems
present elegant and entirely adequate applications of first-order logic.
Unfortunately, although Smoryński does present the completeness and
compactness theorems, none of these applications — in particular ap-
plications to nonstandard models — appear, these apparently having
been relegated to the forthcoming (?) volume II.
Unless a lecturer gives a course on the nonalgorithmic solubility of
diophantine equations (which is presented in this book in a particularly
clear fashion), I doubt if this book really can be used as a student
textbook on elementary logic or ‘logical number theory’. There is too
much detail in some places, and rather too many other topics omitted
(or postponed for volume II) for students to see the overall shape of
the subject.
The final issue I would like to discuss here is whether there really is
a subject that should be called ‘logical number theory’ and if so what
it is, and whether this book really does serve as a useful introduction.
Smoryński, in his preface, invites comparisions with analytic number
theory, which is of course a major area of study in mathematics, and
he makes his wish that ‘number theorists’ should dip into his book to
see what logic has to offer number theory quite clear. Certainly there
is a lot to offer here already, most notably the chapter on Hilbert’s
tenth problem. Not so celebrated, perhaps, but nevertheless relevant to
this subject sitting on the boundary between logic and number theory,
are Presburger and Skolem arithmetic. (As it happens, I was slightly
disappointed with the presentation of quantifier elimination for these
theories — more modern treatments using back-and-forth seem rather
more enlightening and less pedestrian.) On the other hand, Smoryński
clearly sees Hilbert’s programme and the Gödel incompleteness results
as part of ‘logical number theory’. While not belittling their impor-
tance, I would not choose to put such a large emphasis on them as
he does here. Certainly, Gödel’s results show the possibility of very
158 RICHARD KAYE

straightforward number theoretic statements being independent of cer-

tain formal systems, or even of stating the consistency of formal sys-
tems. With the solution of Hilbert’s tenth problem, we even see that
these statements can be put in a form expressing the nonsolubility of
specific diophantine equations, but even so no such statement of gen-
uine number theoretic interest has been found. Of course, following
from the Paris-Harrington theorem, plenty of independent statements
of combinatorial interest are now known, but that is another matter
altogether.
It seems to me that, if there is a significant contribution at all to
number theory from logic, it has come from quite a different direction.
Most importantly of all, logic has supplied us with (or has given us
the tools to analyse) a vast number of interesting number systems. Of
obvious relevance are nonstandard models of arithmetic, not just of
the theory of the natural numbers with addition and multiplication,
but of Preburger and Skolem arithmetic and decidable extensions of
these, and of other weak systems such as the systems of open induction
where one can study the effect of algebraic axioms on the solubility of
diophantine equations. Going slightly beyond this, but still (at least to
me) within the scope of ‘logical number theory’ are the p-adic number
fields (with Macintyre’s quantifier elimination result giving the basic
tools required to analyse them) and the pseudofinite fields of Ax and
others. Tarski’s work on real closed fields has been given new rele-
vance recently with Wilkie’s model completeness result for exponential
fields and many interesting (and difficult) decidability and transcen-
dence questions that this raises. But a text on ‘logical number theory’
which aims to give a newcomer to logic the necessary background and
flavour of some of these topics would be quite a different sort of book
than the one reviewed here.
School of Mathematics and Statistics, University of Birmingham,
Edgbaston, Birmingham B15 2TT - U.K.
E-mail address: R.W.Kaye@bham.ac.uk
E-mail address: http://for.mat.bham.ac.uk/R.W.Kaye