Effectiveness for the Dual Ramsey Theorem

Publication date 29 September 2017

Abstract: We analyze the Dual Ramsey Theorem for

k

partitions and

e l l

colors (

m a t h s f {D R T}_{e}^{k} l l

) in the context of reverse math, effective analysis, and strong reductions. Over

m a t h s f {R C A}_{0}

, the Dual Ramsey Theorem stated for Baire colorings is equivalent to the statement for clopen colorings and to a purely combinatorial theorem

m a t h s f {c D R T}_{e}^{k} l l

. When the theorem is stated for Borel colorings and

k g e q 3

, the resulting principles are essentially relativizations of

m a t h s f {c D R T}_{e}^{k} l l

. For each

a l p h a

, there is a computable Borel code for a

D e l t a_{a}^{0} l p h a

coloring such that any partition homogeneous for it computes

e m p t y s e t^{(a l p h a)}

or

e m p t y s e t^{(a l p h a - 1)}

depending on whether

a l p h a

is infinite or finite. For

k = 2

, we present partial results giving bounds on the effective content of the principle. A weaker version for

D e l t a_{n}^{0}

reduced colorings is equivalent to

m a t h s f D_{2}^{n}

over

m a t h s f {R C A}_{0} + m a t h s f I S i g m a_{n - 1}^{0}

and in the sense of strong Weihrauch reductions.

This page was built for publication: Effectiveness for the Dual Ramsey Theorem