Reverse Mathematics: Constructivism and Combinatorics

Research supported by the John Templeton Foundation

The research described below will be supported in part or entirely by Grant ID# 20800 from the John Templeton Foundation during the period from June 1, 2011 to July 31, 2012. Any opinions expressed here or in the linked materials are those of the author and do not necessarily reflect the views of the John Templeton Foundation.

Executive Summary

From the project proposal:

This project will contribute to the program of reverse mathematics by proving new reverse mathematics results in the area of combinatorics and by extending our understanding of the applicability of reverse mathematics to questions in constructive mathematics. The work addresses foundational questions in the mathematical sciences, specifically, “ What are the limits of mathematics in advancing human knowledge? ” Results will contribute to our understanding of the limits of mathematics within mathematics. By delimiting the nature and capabilities of formal reasoning, we can better understand and appreciate the potential of other, less formal means of gaining knowledge.

Funding will free Hirst from teaching duties and support some travel for dissemination. Foundation support paired with sabbatical support from Appalachian State and donated summer research will provide a 14 month period devoted entirely to this research. Expected outcomes include at least two research papers on the central projects, additional related research papers, and various presentations.

Two main projects are proposed. The first is extension of uniformization results that extract implications for constructive mathematics from results in reverse mathematics. The second is formalization of ultrafilter proofs of Hindman's theorem.

Presentations

A pdf file of the slides for Three tales about Weak Konig's Lemma, a talk given in the logic seminar at the Ohio State University on November 20, 2012.
A pdf file of the slides for Reverse mathematics and field extensions a talk given at the Association for Symbolic Logic 2012 North American Annual Meeting on April 1, 2012.
A pdf file of the slides for Reverse mathematics and dichotomy a talk given at the Joint Mathematics Meetings in Boston on January 6, 2012.
A pdf file of the slides for Reverse mathematics and persistent reals a talk given at the Midwest Computability Seminar X on November 1, 2011.
A pdf file of the slides for Two familiar principles in disguise a talk given in the Notre Dame Logic Seminar on October 27, 2011.
A pdf file of the slides for Two combinatorial proofs and some related questions a talk given at the Reverse Mathematics Workshop at the University of Chicago on September 17, 2011.
A pdf file of the slides for Reverse Mathematics: Constructivism and Combinatorics, a talk given at Foundational Questions in the Mathematical Sciences, a meeting sponsored by the John Templeton Foundation at the International Academy Traunkirchen, Austria on July 8-12, 2011.

Publications

On uniform relationships between combinatorial problems, with François Dorais, Damir Dzhafarov, Joseph Mileti, and Paul Shafer, Transactions of the American Mathematical Society, 368 (2016) 1321--1359. Available online (DOI) 10.1090/tran/6465 for subscribers. A draft is available.
Comparing the strength of diagonally non-recursive functions in the absence of Σ⁰₂ induction, with François Dorais and Paul Shafer, The Journal of Symbolic Logic, 80 no. 4, (2015) 1211--1235. Available online http://journals.cambridge.org/abstract_S0022481215000432 for subscribers. A draft is available.
Generics for computable Mathias forcing, with Peter Cholak, Damir Dzhafarov, and Theodore Slaman, Annals of Pure and Applied Logic 165:9, (2014) 1418-1428. Available online (DOI) 10.1016/j.apal.2014.04.011. A draft is available.
Reverse mathematics and algebraic field extensions, with François Dorais and Paul Shafer, Computability 2:2, (2013) 75-92. Available online (10.3233/COM-13021). A draft is available.
Disguising induction: Proofs of the pigeonhole principle for trees, in: Foundational Adventures: Essays in Honor of Harvey M. Friedman, (Neil Tennant, editor) Templeton Press (2012). Available online at foundationaladventures.wordpress.com. A draft is available in pdf format.
Reverse mathematics, trichotomy, and dichotomy, with François Dorais and Paul Shafer, Journal of Logic and Analysis 4:13, (2012) 1-14. Available online (DOI: 10.4115/jla.2012.4.13). A draft is available in pdf format.
On Mathias generic sets, with Peter Cholak and Damir Dzhafarov, pages 129-138 in: How the World Computes: Proceedings of the Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, LNCS 7318, (Cooper, Dawar, and Lowe, editors) Springer-Verlag (2012) ISBN: 978-3-642-30869-7. Available online (DOI: 10.1007/978-3-642-30870-3_14). A draft is available in pdf format.
More reverse mathematics of the Heine-Borel theorem, with Jessica Miller, Journal of Logic and Analysis 4:6, (2012) 1-10. Available online (DOI: 10.4115/jla.2012.4.6). A draft is available in pdf format.
Hilbert versus Hindman, Archive for Mathematical Logic 51:1-2, (2012) 123-125. Available online (DOI: 10.1007/s00153-011-0257-4) for subscribers. A draft is available in pdf format.

Other Activities and Materials

The web page for the AMS/ASL joint special session on the Life and Legacy of Alan Turing, to be held in January at the Joint Mathematics Meetings in Boston.
A press release from the University News service at Appalachian State University.