Milliken's tree theorem and its applications : a computability-theoretic perspective / Paul Elliot Anglès d'Auriac, Peter A. Cholak, Damir D. Dzhafarov, Benoît Monin, Ludovic Patey.

Format:

Book

Author/Creator:

D'Auriac, Paul-Elliot Anglès, author.

Cholak, Peter, 1962- author.

Dzhafarov, Damir D., author.

Monin, Benoît, (Mathematician), author.

Patey, Ludovic, author.

Series:

Memoirs of the American Mathematical Society ; no. 1457.

Memoirs of the American Mathematical Society, 0065-9266 ; no. 1457

Language:

English

Subjects (All):

Logic, Symbolic and mathematical.

Physical Description:

vi, 118 pages : illustrations ; 26 cm.

Place of Publication:

Providence, RI, USA : American Mathematical Society, [2024]

Summary:

Milliken's tree theorem is a deep result in combinatorics that generalizes a vast number of other results in the subject, most notably Ramsey's theorem and its many variants and consequences. Motivated by a question of Dobrinen, we initiate the study of Milliken's tree theorem from the point of view of computability theory. Our advance here stems from a careful analysis of the Halpern-Laüchli theorem which shows that it can be carried out effectively (i.e., that it is computably true). We use this as the basis of a new inductive proof of Milliken's tree theorem that permits us to gauge its effectivity in turn. The principal outcome of this is a comprehensive classification of the computable content of Milliken's tree theorem. We apply our analysis also to several well-known applications of Milliken's tree theorem, namely Devlin's theorem, a partition theorem for Rado graphs, and a generalized version of the so-called tree theorem of Chubb, Hirst, and McNicholl. These are all certain kinds of extensions of Ramsey's theorem for different structures, namely the rational numbers, the Rado graph, and perfect binary trees, respectively. We obtain a number of new results about how these principles relate to Milliken's tree theorem and to each other, in terms of both their computability-theoretic and combinatorial aspects. We identify again the familiar dichotomy between coding the halting problem or not based on the size of instance, but this is more subtle here owing to the more complicated underlying structures, particularly in the case of Devlin's theorem. We also establish new structural Ramsey-theoretic properties of the Rado graph theorem and the generalized Chubb-Hirst-McNicholl tree theorem using Zucker's notion of big Ramsey structure.

Contents:

Chapter 1. Introduction

Chapter 2. Definitions

Chapter 3. The Halpern-Laüchli theorem

Chapter 4. Milliken's tree theorem

Chapter 5. Devlin's theorem

Chapter 6. The Rado graph theorem

Chapter 7. A generalized tree theorem

Chapter 8. Open questions

Bibliography

Index.

Notes:

"January 2024, volume 293, number 1457 (first of 7 numbers)"

Includes bibliographical references (pages 111-113) and index.

ISBN:

9781470467319

1470467313

OCLC:

1425314002