TY - JOUR

T1 - Effectiveness for the dual ramsey theorem

AU - Dzhafarov, Damir

AU - Flood, Stephen

AU - Solomon, Reed

AU - Westrick, Linda

N1 - Funding Information:
Dzhafarov’s work was partially supported by National Science Foundation grant DMS-1400267.
Publisher Copyright:
© 2021 by University of Notre Dame.

PY - 2021

Y1 - 2021

N2 - We analyze the dual Ramsey theorem for k partitions and colors (DRTk ) in the context of reverse math, effective analysis, and strong reductions. Over RCA0, the dual Ramsey theorem stated for Baire colorings Baire-DRTk is equivalent to the statement for clopen colorings ODRTk and to a purely combinatorial theorem CDRTk. When the theorem is stated for Borel colorings and k ≥ 3, the resulting principles are essentially relativizations of CDRTk. For each α, there is a computable Borel code for a Δα0 -coloring such that any partition homogeneous for it computes Ø(α) or Ø(α-1) depending on whether α is infinite or finite. For k D 2, we present partial results giving bounds on the effective content of the principle. A weaker version for 0 n-reduced colorings is equivalent to Dn2 over RCA0 C IΣ0 n-1 and in the sense of strong Weihrauch reductions.

AB - We analyze the dual Ramsey theorem for k partitions and colors (DRTk ) in the context of reverse math, effective analysis, and strong reductions. Over RCA0, the dual Ramsey theorem stated for Baire colorings Baire-DRTk is equivalent to the statement for clopen colorings ODRTk and to a purely combinatorial theorem CDRTk. When the theorem is stated for Borel colorings and k ≥ 3, the resulting principles are essentially relativizations of CDRTk. For each α, there is a computable Borel code for a Δα0 -coloring such that any partition homogeneous for it computes Ø(α) or Ø(α-1) depending on whether α is infinite or finite. For k D 2, we present partial results giving bounds on the effective content of the principle. A weaker version for 0 n-reduced colorings is equivalent to Dn2 over RCA0 C IΣ0 n-1 and in the sense of strong Weihrauch reductions.

UR - http://www.scopus.com/inward/record.url?scp=85109556186&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85109556186&partnerID=8YFLogxK

U2 - 10.1215/00294527-2021-0024

DO - 10.1215/00294527-2021-0024

M3 - Article

AN - SCOPUS:85109556186

SN - 0029-4527

VL - 62

SP - 455

EP - 490

JO - Notre Dame Journal of Formal Logic

JF - Notre Dame Journal of Formal Logic

IS - 3

ER -