Slicing the Truth

Last updated
First edition Slicing the Truth.jpg
First edition

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.

Contents

Topics

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

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]

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]

Related Research Articles

<span class="mw-page-title-main">Kőnig's lemma</span> Mathematical result on infinite trees

Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.

Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathematics. In this latter sense, the distinction between foundations of mathematics and philosophy of mathematics turns out to be vague. Foundations of mathematics can be conceived as the study of the basic mathematical concepts and how they form hierarchies of more complex structures and concepts, especially the fundamentally important structures that form the language of mathematics also called metamathematical concepts, with an eye to the philosophical aspects and the unity of mathematics. The search for foundations of mathematics is a central question of the philosophy of mathematics; the abstract nature of mathematical objects presents special philosophical challenges.

Proof theory is a major branch of mathematical logic and theoretical computer science within which proofs are treated as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as lists, boxed lists, or trees, which are constructed according to the axioms and rules of inference of a given logical system. Consequently, proof theory is syntactic in nature, in contrast to model theory, which is semantic in nature.

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones.

<span class="mw-page-title-main">Richard Rado</span> British mathematician

Richard Rado FRS was a German-born British mathematician whose research concerned combinatorics and graph theory. He was Jewish and left Germany to escape Nazi persecution. He earned two PhDs: in 1933 from the University of Berlin, and in 1935 from the University of Cambridge. He was interviewed in Berlin by Lord Cherwell for a scholarship given by the chemist Sir Robert Mond which provided financial support to study at Cambridge. After he was awarded the scholarship, Rado and his wife left for the UK in 1933. He was appointed Professor of Mathematics at the University of Reading in 1954 and remained there until he retired in 1971.

In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics.

In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, which is expressible in Peano arithmetic, is not provable in this system. The combinatorial principle is however provable in slightly stronger systems.

<span class="mw-page-title-main">James Earl Baumgartner</span> American logician

James Earl Baumgartner was an American mathematician who worked in set theory, mathematical logic and foundations, and topology.

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.

In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom. Recent developments concern combinatorics of the continuum and combinatorics on successors of singular cardinals.

A timeline of mathematical logic; see also history of logic.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.

In mathematics, the Dushnik–Miller theorem is a result in order theory stating that every infinite linear order has a non-identity order embedding into itself. It is named for Ben Dushnik and E. W. Miller, who published this theorem for countable linear orders in 1940. More strongly, they showed that in the countable case there exists an order embedding into a proper subset of the given order; however, they provided examples showing that this strengthening does not always hold for uncountable orders.

In proof theory, a branch of mathematical logic, elementary function arithmetic (EFA), also called elementary arithmetic and exponential function arithmetic, is the system of arithmetic with the usual elementary properties of 0, 1, +, ×, , together with induction for formulas with bounded quantifiers.

<i>Reverse Mathematics: Proofs from the Inside Out</i> Book by John Stillwell

Reverse Mathematics: Proofs from the Inside Out is a book by John Stillwell on reverse mathematics, the process of examining proofs in mathematics to determine which axioms are required by the proof. It was published in 2018 by the Princeton University Press (ISBN 978-0-691-17717-5).

The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators is a book on graph coloring, Ramsey theory, and the history of development of these areas, concentrating in particular on the Hadwiger–Nelson problem and on the biography of Bartel Leendert van der Waerden. It was written by Alexander Soifer and published by Springer-Verlag in 2009 (ISBN 978-0-387-74640-1).

Combinatorial Games: Tic-Tac-Toe Theory is a monograph on the mathematics of tic-tac-toe and other positional games, written by József Beck. It was published in 2008 by the Cambridge University Press as volume 114 of their Encyclopedia of Mathematics and its Applications book series (ISBN 978-0-521-46100-9).

References

  1. 1 2 3 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
  2. 1 2 3 4 5 6 7 Gasarch, William (March 2016), "Review of Slicing the Truth" (PDF), ACM SIGACT News , 47 (1): 21–24, doi:10.1145/2902945.2902952, S2CID   19457072
  3. 1 2 3 4 5 6 Dorais, François G., "Review of Slicing the Truth", Mathematical Reviews , MR   3244278
  4. 1 2 3 4 5 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
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.