Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Reverse mathematics : proofs from the inside out
Stillwell J., PRINCETON UNIVERSITY PRESS, Princeton, NJ, 2018. 200 pp. Type: Book
Date Reviewed: Nov 23 2020

Reverse mathematics “seeks the axioms needed to prove given theorems.” The work of Emil Post and Kurt Gödel, in the 1920s and 1930s, permanently dashed the hope that axiom systems could formally generate all theorems for natural numbers, integers, rational numbers, and real numbers. (Incidentally, this book gives Emil Post his due as the superhero [my term] that he was.)

I’ve been following reverse mathematics, as a consumer, with great interest for a decade and a half [1], and find it impossible to overstate the virtues of the present book, both as they pertain to its title subject and also to the foundations of mathematics in general. Regarding the foundations of mathematics, the book’s very first sentence surprised me: “a topic once of interest to outstanding mathematicians, such as Dedekind, Poincaré, and Hilbert, but today sadly neglected.” Stillwell’s credibility [2] is such that I don’t question this unexpected conclusion.

Reverse mathematics is explicated in chapter 1 as an idea that is not new. This is incisively illustrated by the struggles regarding the independence of Euclid’s parallel axiom from the other four, and the more recent axiom of choice (AC) of set theory. Peano’s axioms (PA) for the natural numbers {0, 1, 2, 3, ...} are the base theory for the arithmetization--the “encoding” by sets of natural numbers--of analysis objects, that is, of the real number system. Chapter 2 elaborates “classical arithmetization,” wherein the integers Z are, in the fashion of Cantor’s and Dedekind’s treatment of the rational numbers Q, rendered as ordered pairs of natural numbers. The ever-intriguing (-1)(-1) = 1 is a theorem that follows from the appropriate definition of multiplication of ordered pairs of natural numbers that encode integers: “natural numbers are a foundation for the integer and rational numbers.” Infinite operations are subsequently admitted by sets of rational numbers; arithmetization aims to reduce all concepts, including functions, to natural numbers and sets thereof.

Chapter 3, “Classical Analysis,” treats the feasibility of arithmetizing the real number system, sequences, infinite series, and continuous functions via axiom systems of analysis, with the Peano axioms as base. It is by far the best treatment of household (my term) theorems in analysis: Bolzano-Weierstrass, Heine-Borel, intermediate value, extreme value, and Riemann integral. My own snarky thought over a lifetime has been: if you’ve never felt queasy about the standard proofs of these theorems, then you’ve not understood the problem. (I’ll state for completeness that the cause of such queasiness could also be a decided lack of insight.) “Trees [in the sense of graph theory and day-to-day computing] are a key concept of analysis,” as reverse mathematics has revealed. Hence the prominence here of König’s lemma for finitely branching but infinite trees. The arithmetization of trees is, again, via encoding by sets of natural numbers.

Chapter 4, “Computability,” “foreshadows a constructive [in the sense of L. E. J. Brouwer] approach to analysis.” The axiom that complements Peano’s here is RCA0, the recursive comprehension axiom--with “‘recursive’ going out of style” in favor of computable. Chapter 5 elaborates the arithmetization of computation as it relates to Peano arithmetic. The use of Smullyan’s elementary formal system (EFS) [3], including the encoding of axiom/theorem character strings by Smullyan’s dyadic numerals, seems a clarity-enhancing tour de force. But Stillwell’s pedagogy extends farther than any I’ve encountered: the footnote on Smullyan’s wish to “avoid using number theory” in his proof elicits Stillwell’s “it is not clear to me where to draw the ‘number theory’ line.” This is because the Chinese remainder theorem was invoked. (A long time ago, and for good and bad reasons, I had the uncomfortable feeling of circularity when I first nodded through Gödel’s incompleteness proof--with its Gödel numbers.)

Chapter 6 elaborates arithmetical comprehension and describes ACA0, which comprises the Peano axioms supplemented by set existence of subsets of N with Peano property φ; it is PA with set variables. ACA0 proves Bolzano-Weierstrass, least upper bound for sequences, Cauchy and monotone convergence--each to be equivalent to arithmetical comprehension. Chapter 7, on recursive (also known as computable) comprehension explains RCA0, which has the induction axiom (schema); it is a base theory that is, however, too weak to prove several of ACA0’s theorems.

The final chapter, “A Bigger Picture,” expounds, among other things, constructivism’s contribution to reverse mathematics “in fields of mathematics involving computation.” The remainder of the chapter reveals the essence of mathematics--reverse or otherwise--and its logic in a consummately informative and engaging way.

By way of a causality-violating fantasy, I wish that this outstanding book had existed (along with its predecessor) throughout my study of, and work in, physics, mathematics, and computing. The concomitant tacit treatment of forward mathematics is as good as mathematical exposition, knowledge, and insight get.

More reviews about this item: Amazon

Reviewer:  George Hacken Review #: CR147116 (2104-0076)
1) Foundations of Mathematics (FOM) list. https://cs.nyu.edu/mailman/listinfo/fom (accessed 03/27/2020).
2) Stillwell, J. Elements of mathematics: from Euclid to Gödel. Princeton University Press, Princeton, NJ, 2016.
3) Smullyan, R. M. Theory of formal systems. Princeton University Press, Princeton, NJ, 1961.
Bookmark and Share
  Featured Reviewer  
 
Mathematics And Statistics (J.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Mathematics And Statistics": Date
Microcomputers and mathematics
Bruce J., Giblin P., Rippon P., Cambridge University Press, New York, NY, 1990. Type: Book (9780521375160)
May 1 1992
Mathographics
Dixon R., Dover Publications, Inc., New York, NY, 1991. Type: Book (9780486266398)
Apr 1 1992
Quaternary quadratic forms
Nipp G., Springer-Verlag New York, Inc., New York, NY, 1991. Type: Book (9780387976013)
Apr 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy