2017/09/29 by Dzhafarov, Damir, Flood, Stephen, Solomon, Reed +1 · 1 citation
#03B30 #05D10 #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1710.00070
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 is equivalent to the statement for clopen colorings 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=2, we present partial results giving bounds on the effective content of the principle. A weaker version for Δ0n reduced colorings is equivalent to Dn2 over RCA0+IΣ0n-1 and in the sense of strong Weihrauch reductions.