Slicing the Truth: On the Computability Theoretic and Reverse Mathematical
Analysis of Combinatorial Principles
Lecture
Notes Series of the Institute
for Mathematical
Sciences, National University of Singapore, published by World
Scientific
preprint version
Abstract. In this expository article, we discuss two closely
related approaches to studying the relative strength of mathematical
principles: computable mathematics and reverse mathematics. Drawing our
examples from combinatorics and model theory, we explore a variety of
phenomena and techniques in these areas. We begin with variations on
König's Lemma, and give an introduction to reverse mathematics and
related parts of computability theory. We then focus on Ramsey's Theorem
as a case study in the computability theoretic and reverse mathematical
analysis of combinatorial principles. We study Ramsey's Theorem for Pairs
(RT22) in detail, focusing on fundamental tools such
as stability, cohesiveness, and Mathias forcing; and on combinatorial and
model theoretic consequences of RT22. We also
discuss the important theme of conservativity results. In the final
section, we explore several topics that reveal various aspects of
computable mathematics and reverse mathematics. An appendix contains a
proof of Liu's recent result that RT22 does not
imply Weak König's Lemma. There are exercises and open questions
throughout the article.
drh@math.uchicago.edu