Thin set theorems and cone avoidance

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35)

Abstract: The thin set theorem

m a t h s f {R T}_{< i n f t y, e l l}^{n}

asserts the existence, for every

k

-coloring of the subsets of natural numbers of size

n

, of an infinite set of natural numbers, all of whose subsets of size

n

use at most

e l l

colors. Whenever

e l l = 1

, the statement corresponds to Ramsey's theorem. From a computational viewpoint, the thin set theorem admits a threshold phenomenon, in that whenever the number of colors

e l l

is sufficiently large with respect to the size

n

of the tuples, then the thin set theorem admits strong cone avoidance. Let

d_{0}, d_{1}, d o t s

be the sequence of Catalan numbers. For

n g e q 1

,

m a t h s f {R T}_{< i n f t y, e l l}^{n}

admits strong cone avoidance if and only if

e l l g e q d_{n}

and cone avoidance if and only if

e l l g e q d_{n - 1}

. We say that a set

A

is

m a t h s f {R T}_{< i n f t y, e l l}^{n}

-encodable if there is an instance of

m a t h s f {R T}_{< i n f t y, e l l}^{n}

such that every solution computes

A

. The

m a t h s f {R T}_{< i n f t y, e l l}^{n}

-encodable sets are precisely the hyperarithmetic sets if and only if

e l l < 2^{n - 1}

, the arithmetic sets if and only if

2^{n - 1} l e q e l l < d_{n}

, and the computable sets if and only if

d_{n} l e q e l l

.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Thin set theorems and cone avoidance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5218249)