Slicing the Truth
Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles is a book on reverse mathematics in combinatorics, the study of the axioms needed to prove combinatorial theorems. It was written by Denis R. Hirschfeldt, based on a course given by Hirschfeldt at the National University of Singapore in 2010,[1] and published in 2014 by World Scientific, as volume 28 of the Lecture Notes Series of the Institute for Mathematical Sciences, National University of Singapore.
Topics[edit]
The book begins with five chapters that discuss the field of reverse mathematics, which has the goal of classifying mathematical theorems by the axiom schemes needed to prove them, and the big five subsystems of second-order arithmetic into which many theorems of mathematics have been classified.[2][3] These chapters also review some of the tools needed in this study, including computability theory, forcing, and the low basis theorem.[4]
Chapter six, "the real heart of the book",[2] applies this method to an infinitary form of Ramsey's theorem: every edge coloring of a countably infinite complete graph or complete uniform hypergraph, using finitely many colors, contains a monochromatic infinite induced subgraph. The standard proof of this theorem uses the arithmetical comprehension axiom, falling into one of the big five subsystems, ACA0. However, as David Seetapun originally proved, the version of the theorem for graphs is weaker than ACA0, and it turns out to be inequivalent to any one of the big five subsystems. The version for uniform hypergraphs of fixed order greater than two is equivalent to ACA0, and the version of the theorem stated for all numbers of colors and all orders of hypergraphs simultaneously is stronger than ACA0.[2]
Chapter seven discusses conservative extensions of theories, in which the statements of a powerful theory (such as one of the forms of second-order arithmetic) that are both provable in that theory and expressible in a weaker theory (such as Peano arithmetic) are only the ones that are already provably in the weaker theory. Chapter eight summarizes the results so far in diagrammatic form. Chapter nine discusses ways to weaken Ramsey's theorem,[2] and the final chapter discusses stronger theorems in combinatorics including the Dushnik–Miller theorem on self-embedding of infinite linear orderings, Kruskal's tree theorem, Laver's theorem on order embedding of countable linear orders, and Hindman's theorem on IP sets.[3] An appendix provides a proof of a theorem of Jiayi Liu, part of the collection of results showing that the graph Ramsey theorem does not fall into the big five subsystems.[1][3][4]
Audience and reception[edit]
This is a technical monograph, requiring its readers to have some familiarity with computability theory and Ramsey theory. Prior knowledge of reverse mathematics is not required.[2] It is written in a somewhat informal style, and includes many exercises, making it usable as a graduate textbook or beginning work in reverse mathematics;[3][4] reviewer François Dorais writes that it is an "excellent introduction to reverse mathematics and the computability theory of combinatorial principles" as well as a case study in the methods available for proving results in reverse mathematics.[3]
Reviewer William Gasarch complains about two missing topics, the work of Joe Mileti on the reverse mathematics of canonical versions of Ramsey's theorem, and the work of James Schmerl on the reverse mathematics of graph coloring. Nevertheless he recommends this book to anyone interested in reverse mathematics and Ramsey theory.[2] And reviewer Benedict Eastaugh calls it "a welcome addition ... providing a fresh and accessible look at a central aspect of contemporary reverse mathematical research."[4]
Related reading[edit]
A "classic reference" in reverse mathematics is the book Subsystems of Second Order Arithmetic (2009) by Stephen Simpson;[4] it is centered around the big five subsystems and contains many more examples of results equivalent in strength to one of these five.[2] Dorais suggests using the two books together as companion volumes.[3]
Reviewer Jeffry Hirst suggests Computability Theory by Rebecca Weber as a good source for the background needed to read this book.[1]
References[edit]
- ^ a b c Hirst, Jeffry L. (September 2015), "Review of Slicing the Truth", Bulletin of Symbolic Logic, 21 (3): 338–339, doi:10.1017/bsl.2015.18, S2CID 61188908; see also Hirst's shorter review for zbMATH, Zbl 1304.03001
- ^ a b c d e f g Gasarch, William (March 2016), "Review of Slicing the Truth" (PDF), ACM SIGACT News, 47 (1): 21–24, doi:10.1145/2902945.2902952, S2CID 19457072
- ^ a b c d e f Dorais, François G., "Review of Slicing the Truth", Mathematical Reviews, MR 3244278
- ^ a b c d e Eastaugh, Benedict (July 2017), "Review of Slicing the Truth", Studia Logica, 105 (4): 873–879, doi:10.1007/s11225-017-9740-1, hdl:1983/1ed76e2d-9bc7-4529-b628-92791f631317, S2CID 1667765
External links[edit]
- Slicing the Truth, Hirschfeldt's web site, including a preprint version of the book.