 First edition | |
| Author | Denis R. Hirschfeldt |
|---|---|
| Language | English |
| Genre | Non-fiction |
| Publisher | World Scientific |
Publication date | 2014 |
Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles is a book onreverse mathematics incombinatorics, the study of theaxioms needed to prove combinatorial theorems. It was written by Denis R. Hirschfeldt, based on a course given by Hirschfeldt at theNational University of Singapore in 2010,[1] and published in 2014 byWorld Scientific, as volume 28 of the Lecture Notes Series of the Institute for Mathematical Sciences, National University of Singapore.
The book begins with five chapters that discuss the field ofreverse mathematics, which has the goal of classifying mathematical theorems by the axiom schemes needed to prove them, and thebig five subsystems ofsecond-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, includingcomputability theory,forcing, and thelow basis theorem.[4]
Chapter six, "the real heart of the book",[2] applies this method to aninfinitary form ofRamsey's theorem: everyedge coloring of a countably infinite complete graph or complete uniformhypergraph, using finitely many colors, contains a monochromatic infiniteinduced subgraph. The standard proof of this theorem uses thearithmetical comprehension axiom, falling into one of the big five subsystems, ACA0. However, asDavid 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 discussesconservative 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 asPeano 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 theDushnik–Miller theorem on self-embedding of infinite linear orderings,Kruskal's tree theorem,Laver's theorem onorder embedding of countablelinear orders, and Hindman's theorem onIP 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]
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]
ReviewerWilliam 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 ofgraph 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]
A "classic reference" in reverse mathematics is the bookSubsystems of Second Order Arithmetic (2009) byStephen 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 suggestsComputability Theory by Rebecca Weber as a good source for the background needed to read this book.[1]