Effectiveness for the dual ramsey theorem

Damir Dzhafarov, Stephen Flood, Reed Solomon, Linda Westrick

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)455-490
Number of pages36
JournalNotre Dame Journal of Formal Logic
Volume62
Issue number3
DOIs
StatePublished - 2021

All Science Journal Classification (ASJC) codes

  • Logic

Fingerprint

Dive into the research topics of 'Effectiveness for the dual ramsey theorem'. Together they form a unique fingerprint.

Cite this