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.
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 receptionedit
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 readingedit
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]
Referencesedit
^ abcHirst, 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
^ abcdeEastaugh, 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 linksedit
Slicing the Truth, Hirschfeldt's web site, including a preprint version of the book.
December 18, 2023
slicing, truth, computability, theoretic, reverse, mathematical, analysis, combinatorial, principles, book, reverse, mathematics, combinatorics, study, axioms, needed, prove, combinatorial, theorems, written, denis, hirschfeldt, based, course, given, hirschfel. 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 First edition Contents 1 Topics 2 Audience and reception 3 Related reading 4 References 5 External linksTopics editThe 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 editThis 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 Francois 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 editA 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 Francois 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 1667765External links editSlicing the Truth Hirschfeldt s web site including a preprint version of the book Retrieved from https en wikipedia org w index php title Slicing the Truth amp oldid 1188134819, wikipedia, wiki, book, books, library,
