Stable Ramsey's Theorem and Measure

被引:3
作者
Dzhafarov, Damir D. [1 ]
机构
[1] Univ Chicago, Dept Math, Chicago, IL 60637 USA
关键词
Ramsey's theorem; effective measure theory; reverse mathematics;
D O I
10.1215/00294527-2010-039
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are nonnull in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for nonnull many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below empty set' but not in general. We also answer the analogs of two well-known questions about the stable Ramsey's theorem by showing that our weaker principle does not imply COH or WKL0 in the context of reverse mathematics.
引用
收藏
页码:95 / 112
页数:18
相关论文
共 23 条
[1]   Comparing DNR and WWKL [J].
Ambos-Spies, K ;
Kjos-Hanssen, B ;
Lempp, S ;
Slaman, TA .
JOURNAL OF SYMBOLIC LOGIC, 2004, 69 (04) :1089-1104
[2]  
[Anonymous], 1987, PERSPECTIVES MATH LO
[3]   Embeddings into the Medvedev and Muchnik lattices of Π01 classes [J].
Binns, S ;
Simpson, SG .
ARCHIVE FOR MATHEMATICAL LOGIC, 2004, 43 (03) :399-414
[4]   On the strength of Ramsey's theorem for pairs [J].
Cholak, PA ;
Jockusch, CG ;
Slaman, TA .
JOURNAL OF SYMBOLIC LOGIC, 2001, 66 (01) :1-55
[5]   A Δ02 set with no infinite low subset in either it or its complement [J].
Downey, R ;
Hirschfeldt, DR ;
Lempp, S ;
Solomon, R .
JOURNAL OF SYMBOLIC LOGIC, 2001, 66 (03) :1371-1381
[6]  
Downey RG, 2010, THEOR APPL COMPUT, P401, DOI 10.1007/978-0-387-68441-3
[7]  
DZHAFAROV DD, THESIS U CHICAGO
[8]  
HIRSCHFELDT D. R., 2008, LECT NOTES SERIES, P143
[9]   RAMSEYS THEOREM AND RECURSION THEORY [J].
JOCKUSCH, CG .
JOURNAL OF SYMBOLIC LOGIC, 1972, 37 (02) :268-&
[10]  
Jockusch CG., 1989, Studies in Logic and the Foundations of Mathematics, P191