Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs
- PDF / 373,360 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 193 Views
Selecta Mathematica New Series
Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs Leszek Aleksander Kołodziejczyk1 · Keita Yokoyama2
© Springer Nature Switzerland AG 2020
Abstract We study Ramsey’s theorem for pairs and two colours in the context of the theory of α-large sets introduced by Ketonen and Solovay. We prove that any 2-colouring of pairs from an ω300n -large set admits an ωn -large homogeneous set. We explain how a formalized version of this bound gives a more direct proof, and a strengthening, of the recent result of Patey and Yokoyama (Adv Math 330: 1034–1070, 2018) stating that Ramsey’s theorem for pairs and two colours is ∀20 -conservative over the axiomatic theory RCA0 (recursive comprehension). Keywords Ramsey’s theorem · Paris–Harrington principle · α-Large sets · Proof theory · Reverse mathematics Mathematics Subject Classification Primary 05D10; Secondary 03F30 · 03F35 · 03B30
Introduction The work described in this paper is mostly finite combinatorics. Much of the motivation, on the other hand, comes from logic.
The work of the first author is partially supported by Grant No. 2017/27/B/ST1/01951 of the National Science Centre, Poland. The work of the second author is partially supported by JSPS KAKENHI (Grant Nos. 16K17640 and 15H03634) and JSPS Core-to-Core Program (A. Advanced Research Networks), and JAIST Research Grant 2018 (Houga).
B
Keita Yokoyama [email protected] Leszek Aleksander Kołodziejczyk [email protected]
1
Institute of Mathematics, University of Warsaw, Warsaw, Poland
2
School of Information Science, Japan Advanced Institute of Science and Technology, Nomi, Japan 0123456789().: V,-vol
56
Page 2 of 18
L. A. Kołodziejczyk, K. Yokoyama
We contribute to the study of bounds on Ramsey’s theorem for pairs in a setting where the pairs being coloured always come from a finite subset of N, but the “size” of that subset can be described by a countable, possibly infinite ordinal rather than just by a natural number, and it depends not only on the cardinality of the set but also on which specific numbers it contains. More concretely, we use the framework of α-large sets originally due to Ketonen and Solovay [11], in which, for instance: • a set X ⊆ N is n-large, for n ∈ N, exactly if X has at least n elements, • a nonempty set X is ω-large if X \{min X } is min X -large, that is, if X has strictly more than min X elements, • a nonempty set X is ω2 -large if X \{min X } can be split into min X many sets X 1 , . . . , X min X such that max X i < min X i+1 and each X i is ω-large, and so on. A precise definition of α-largeness in the case that will matter to us, namely when α < ωω , is given in Sect. 1 below. Our main aim is to obtain a good upper bound on the size of a set X guaranteeing that each 2-colouring of pairs from X will have an ωn -large homogeneous set, for n ∈ N. This sort of work can be viewed simply as a particular kind of finite combinatorics: essentially, the study of bounds on Ramsey numbers that happen to take ordinal values rather th
Data Loading...
