Roads to Infinity

John Stillwell

A K Peters Ltd, 2010

In 1963, Edwin E. Moise published Elementary Geometry from an Advanced Standpoint and his book became a classic. Roads to Infinity could well be entitled Advanced Logic from an Elementary Standpoint and deserves the same outcome. Its subtitle is actually The Mathematics of Truth and Proof, which well describes its content.

The book consists of eight short chapters. Each chapter begins with a natural mathematical question involving logic or sets and proceeds with the historical sequence of responses to that question. For example, Chapter 1 concerns Cantor’s Diagonal Argument that there can be no countable list of real numbers and deals with the existence and construction of transcendentals, with applications to the cardinality of subsets, to measurability of sets of reals and to unprovability. Traces of the diagonal argument recur throughout the book.

Other chapters deal with ordinals, formal systems and non-decidability, computability and large cardinal axioms. One reason I call the book “elementary” is that certain technical details, such as Godel’s arithmetisation of predicate logic and the Proper Forcing Axiom to show independence of additional set theoretic axioms, are relegated to the references. On the other hand, the reasons for these omissions are carefully explained and a simple overview is always presented.

One of the most enjoyable features is Stillwell’s use of techniques of logic and set theory to solve real mathematical problems, concerning properties of measurability and the unsolvability of the word problem for semigroups and groups. He is particularly concerned with theorems that are true, but not provable within the theory in which they are stated. For example, one result in elementary number theory is Goodstein’s Theorem: take any positive integer n and express it in complete 2-adic form, i.e. as a sum of powers of 2 in which the powers themselves are also in 2-adic form, for example, $$34=2^{2^2+1}+2.$$ Now replace each 2 by 3, subtract 1 and write the result in 3-adic form, in this case $$3^{3^3+1}+2.$$ Repeat the procedure, replacing 3 by 4 and so on. Although the numbers you get seem to increase rapidly, Goodstein’s theorem states that after finitely many steps, you reach zero. This remarkable result has an even more remarkable proof. Suppose $$n_j$$ is the j-adic number constructed from n at the jth step. Replace each j in $$n_j$$ by w, to get $$n_j(w),$$ a countable ordinal in Cantor Normal Form. This sequence of ordinals satisfies $$n_jleq n_j(w)$$ and $$n_j(w)>n_{j+1}(w),$$ because of the subtraction of 1 in moving from $$n_j$$ to $$n_{j+1}.$$ But there is no infinite properly descending chain of ordinals, so after finitely many steps, you get $$0leq n_jleq n_j(w)=0.$$ Warning: don’t try this at home. Stillwell points out that the least j for which $$4_j=0$$ is $$3times 2^{2402653211}-1.$$

Another enjoyable feature is Stillwell’s uniform coverage of unprovability, undecidability and non-computability, leading naturally to the introduction of large cardinals. For example, inaccessible cardinals, which cannot be proved to exist in Zermelo–Fraenkel set theory with the axion of choice, are introduced to prove the consistency of ZFC, and so of predicate logic. Furthermore, he illustrates unprovability using natural mathematical examples such as the Paris–Harrington Theorem of combinatorics. Other examples, from graph theory, are Kruskal’s theorem that for every infinite sequence $$(T_k)$$ of trees there are indices i and j such that $$T_i$$ embeds in $$T_j,$$ and what Stillwell calls “the hardest theorem in graph theory”, the Graph Minor Theorem, which is Kruskal’s Theorem with “tree” replaced by “finite simple  graph”.

Among the many innovative features of the book is Stillwell’s decision to abandon material implication in formal predicate logic, replacing the proposition P ⇒ Q by its classical equivalent (not P or Q), and modus ponens as a rule of inference by the corresponding branching rules of Gentzen’s Natural Deduction. The advantage is that no formula appears in a proof other than one which is already a fragment of the hypothesis or the conclusion. Consequently, proofs are algorithmic. The disadvantage is that proofs are no longer linear, but have the form of a directed tree. Nevertheless, this proof tree is locally finite: its root is the conclusion of the theorem, each edge represents one of the rules of inference, and its leaves are tautologies of the form Pw￢P. Thus the validity of each leaf implies the validity of the root. This procedure mimics the way in which Gentzen proved the consistency of Peano arithmetic.

Another unusual feature is Stillwell’s emphasis on the “forgotten heroes” of Logic: Emil Post who anticipated both Godel and Turing, and Gerhard Gentzen who saw how to bypass Godel’s Incompleteness Theorems by introducing proofs based on induction on ordinals larger than w, which enabled his proof of consistency for arithmetic and later led to consistency proofs for set theory.

The omission of complete proofs mentioned earlier and of exercises means that the book must be supplemented in order to become a textbook for a course in logic. But that is not its stated intention. Rather, it is suitable for self-study by a diligent student in mainstream mathematics and it is excellent background material for computer scientists and mathematicians in other fields. The historical notes alone are worth perusing by anyone who is interested in the development of mathematical ideas.

Phill Schultz.

The University of Western Australia, Australia.

(Reproduced from Gazette of Australian Mathematical Society, Vol. 38, No.1, March 2011)

Source:- Asia Pacific Mathematics Newsletter, Volume 1 No. 3 (July 2011).

It has been republished here with a special permission from World Scientific.