P. S. Novikov, Elements of Mathematical Logic (Oliver and Boyd, Edinburgh, 1964), 308 pp., 50s.
Robert H. Stoothoff · Proceedings of the Edinburgh Mathematical Society · 1965
This textbook, originally published in Russian in 1959, concerns three main topics: propositional logic, first-order predicate logic, and number-theory.Propositional logic is presented initially as propositional algebra, and then as a propositional calculus along the lines of Hilbert and Bernays' Grundlagen derMathematik,\.Similarly, predicate logic is considered first from a model-theoretic (or set-theoretic) point of view, and then as an axiomatic system (again following Hilbert and Bernays).In the penultimate chapter two systems of number-theory are developed: Axiomatic Arithmetic (comparable to standard systems of arithmetic including unrestricted mathematical induction), and Restricted Arithmetic (obtained from Axiomatic Arithmetic by deleting the axiom-schema of mathematical induction).In the final chapter Novikov illustrates the techniques of proof-theory by constructing metamathematical proofs of (1) the consistency of Restricted Arithmetic, and (2) the independence of mathematical induction in Axiomatic Arithmetic.The four chapters on propositional and predicate logic are straightforward, containing few innovations and covering most of the important topics.Novikov confines his attention to classical logic, saying nothing about intuitionist.One suspects that this omission is quite intentional, for in his introductory remarks, and elsewhere in the book, Novikov makes it clear that he accepts the formalist finitism of Hilbert as opposed to the intuitionist finitism of Brouwer.Within the ambit of classical logic, however, the book provides a clear, rigorous and generally reliable exposition, with many examples and fully elaborated proofs.Indeed it might be complained that examples are too numerous and proofs excessively complete-in short, that Novikov should have left more for the reader to do.This would have allowed him to devote more space to subjects which he sketchily considers (e.g. the decision-problem), and some space to subjects which he ignores altogether (e.g.Gentzen-type systems).Turning to the chapter on number-theory, Novikov's system of Axiomatic Arithmetic is a cross-breed of axiomatic number-theory and formalised recursive number-theory.It consists of six axioms adjoined to first-order predicate logictwo equality axioms, three order axioms, and the axiom-schema of mathematical induction-together with all equations defining primitive recursive functions.As well as illustrating the adequacy of this system for defining number-theoretic concepts and for proving theorems of number-theory, Novikov also discusses very briefly the ideas of calculable (effectively computable) and general recursive functions.By far the most difficult part of the book is the chapter on proof-theory.Novikov's consistency-proof for Restricted Arithmetic (RA) follows the pattern of other such proofs: to prove the existence of a non-deducible formula, and hence the consistency of RA, it is shown that every formula deducible in RA must have a property, called " weak regularity ", which the formula 0=^0 lacks.Similarly, in order to prove the independence in Axiomatic Arithmetic of mathematical induction, it is shown that the schema A(0) & (x)(A(x)->A(x'))-*A(y) is not weakly regular, and so cannot be deduced in RA (i.e. from the other axioms of Axiomatic Arithmetic).The book opens with a useful, though occasionally obscure, introductory chapter in which Novikov expounds the aims and methods of Hilbert's finitism.Godel's