Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
A packed Ramsey’s theorem and computability theory
Beteiligte:
Flood, Stephen
Erschienen:
American Mathematical Society (AMS), 2015
Erschienen in:
Transactions of the American Mathematical Society, 367 (2015) 7, Seite 4957-4982
Sprache:
Englisch
DOI:
10.1090/s0002-9947-2015-06164-9
ISSN:
0002-9947;
1088-6850
Entstehung:
Anmerkungen:
Beschreibung:
Ramsey’s theorem states that each coloring has an infinite homogeneous set, but these sets can be arbitrarily spread out. Paul Erdős and Fred Galvin proved that for each coloring f f , there is an infinite set that is “packed together” which is given “a small number” of colors by f f .
We analyze the strength of this theorem from the perspective of computability theory and reverse mathematics. We show that this theorem is close in computational strength to the standard Ramsey’s theorem by giving arithmetical upper and lower bounds for solutions to computable instances. In reverse mathematics, we show that that this packed Ramsey’s theorem is equivalent to Ramsey’s theorem for exponents n ≠ 2 n\neq 2 . When n = 2 n=2 , we show that it implies Ramsey’s theorem and that it does not imply A C A 0 \mathsf {ACA}_0 .